1 //===-- lib/Codegen/MachineRegisterInfo.cpp -------------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // Implementation of the MachineRegisterInfo class. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/CodeGen/MachineRegisterInfo.h" 15 #include "llvm/CodeGen/MachineInstrBuilder.h" 16 #include "llvm/Target/TargetInstrInfo.h" 17 #include "llvm/Target/TargetMachine.h" 18 #include "llvm/Support/raw_os_ostream.h" 19 20 using namespace llvm; 21 22 // Pin the vtable to this file. 23 void MachineRegisterInfo::Delegate::anchor() {} 24 25 MachineRegisterInfo::MachineRegisterInfo(const TargetMachine &TM) 26 : TM(TM), TheDelegate(0), IsSSA(true), TracksLiveness(true) { 27 VRegInfo.reserve(256); 28 RegAllocHints.reserve(256); 29 UsedRegUnits.resize(getTargetRegisterInfo()->getNumRegUnits()); 30 UsedPhysRegMask.resize(getTargetRegisterInfo()->getNumRegs()); 31 32 // Create the physreg use/def lists. 33 PhysRegUseDefLists = 34 new MachineOperand*[getTargetRegisterInfo()->getNumRegs()]; 35 memset(PhysRegUseDefLists, 0, 36 sizeof(MachineOperand*)*getTargetRegisterInfo()->getNumRegs()); 37 } 38 39 MachineRegisterInfo::~MachineRegisterInfo() { 40 delete [] PhysRegUseDefLists; 41 } 42 43 /// setRegClass - Set the register class of the specified virtual register. 44 /// 45 void 46 MachineRegisterInfo::setRegClass(unsigned Reg, const TargetRegisterClass *RC) { 47 assert(RC && RC->isAllocatable() && "Invalid RC for virtual register"); 48 VRegInfo[Reg].first = RC; 49 } 50 51 const TargetRegisterClass * 52 MachineRegisterInfo::constrainRegClass(unsigned Reg, 53 const TargetRegisterClass *RC, 54 unsigned MinNumRegs) { 55 const TargetRegisterClass *OldRC = getRegClass(Reg); 56 if (OldRC == RC) 57 return RC; 58 const TargetRegisterClass *NewRC = 59 getTargetRegisterInfo()->getCommonSubClass(OldRC, RC); 60 if (!NewRC || NewRC == OldRC) 61 return NewRC; 62 if (NewRC->getNumRegs() < MinNumRegs) 63 return 0; 64 setRegClass(Reg, NewRC); 65 return NewRC; 66 } 67 68 bool 69 MachineRegisterInfo::recomputeRegClass(unsigned Reg, const TargetMachine &TM) { 70 const TargetInstrInfo *TII = TM.getInstrInfo(); 71 const TargetRegisterClass *OldRC = getRegClass(Reg); 72 const TargetRegisterClass *NewRC = 73 getTargetRegisterInfo()->getLargestLegalSuperClass(OldRC); 74 75 // Stop early if there is no room to grow. 76 if (NewRC == OldRC) 77 return false; 78 79 // Accumulate constraints from all uses. 80 for (reg_nodbg_iterator I = reg_nodbg_begin(Reg), E = reg_nodbg_end(); I != E; 81 ++I) { 82 const TargetRegisterClass *OpRC = 83 I->getRegClassConstraint(I.getOperandNo(), TII, 84 getTargetRegisterInfo()); 85 if (unsigned SubIdx = I.getOperand().getSubReg()) { 86 if (OpRC) 87 NewRC = getTargetRegisterInfo()->getMatchingSuperRegClass(NewRC, OpRC, 88 SubIdx); 89 else 90 NewRC = getTargetRegisterInfo()->getSubClassWithSubReg(NewRC, SubIdx); 91 } else if (OpRC) 92 NewRC = getTargetRegisterInfo()->getCommonSubClass(NewRC, OpRC); 93 if (!NewRC || NewRC == OldRC) 94 return false; 95 } 96 setRegClass(Reg, NewRC); 97 return true; 98 } 99 100 /// createVirtualRegister - Create and return a new virtual register in the 101 /// function with the specified register class. 102 /// 103 unsigned 104 MachineRegisterInfo::createVirtualRegister(const TargetRegisterClass *RegClass){ 105 assert(RegClass && "Cannot create register without RegClass!"); 106 assert(RegClass->isAllocatable() && 107 "Virtual register RegClass must be allocatable."); 108 109 // New virtual register number. 110 unsigned Reg = TargetRegisterInfo::index2VirtReg(getNumVirtRegs()); 111 VRegInfo.grow(Reg); 112 VRegInfo[Reg].first = RegClass; 113 RegAllocHints.grow(Reg); 114 if (TheDelegate) 115 TheDelegate->MRI_NoteNewVirtualRegister(Reg); 116 return Reg; 117 } 118 119 /// clearVirtRegs - Remove all virtual registers (after physreg assignment). 120 void MachineRegisterInfo::clearVirtRegs() { 121 #ifndef NDEBUG 122 for (unsigned i = 0, e = getNumVirtRegs(); i != e; ++i) { 123 unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 124 if (!VRegInfo[Reg].second) 125 continue; 126 verifyUseList(Reg); 127 llvm_unreachable("Remaining virtual register operands"); 128 } 129 #endif 130 VRegInfo.clear(); 131 } 132 133 void MachineRegisterInfo::verifyUseList(unsigned Reg) const { 134 #ifndef NDEBUG 135 bool Valid = true; 136 for (reg_iterator I = reg_begin(Reg), E = reg_end(); I != E; ++I) { 137 MachineOperand *MO = &I.getOperand(); 138 MachineInstr *MI = MO->getParent(); 139 if (!MI) { 140 errs() << PrintReg(Reg, getTargetRegisterInfo()) 141 << " use list MachineOperand " << MO 142 << " has no parent instruction.\n"; 143 Valid = false; 144 } 145 MachineOperand *MO0 = &MI->getOperand(0); 146 unsigned NumOps = MI->getNumOperands(); 147 if (!(MO >= MO0 && MO < MO0+NumOps)) { 148 errs() << PrintReg(Reg, getTargetRegisterInfo()) 149 << " use list MachineOperand " << MO 150 << " doesn't belong to parent MI: " << *MI; 151 Valid = false; 152 } 153 if (!MO->isReg()) { 154 errs() << PrintReg(Reg, getTargetRegisterInfo()) 155 << " MachineOperand " << MO << ": " << *MO 156 << " is not a register\n"; 157 Valid = false; 158 } 159 if (MO->getReg() != Reg) { 160 errs() << PrintReg(Reg, getTargetRegisterInfo()) 161 << " use-list MachineOperand " << MO << ": " 162 << *MO << " is the wrong register\n"; 163 Valid = false; 164 } 165 } 166 assert(Valid && "Invalid use list"); 167 #endif 168 } 169 170 void MachineRegisterInfo::verifyUseLists() const { 171 #ifndef NDEBUG 172 for (unsigned i = 0, e = getNumVirtRegs(); i != e; ++i) 173 verifyUseList(TargetRegisterInfo::index2VirtReg(i)); 174 for (unsigned i = 1, e = getTargetRegisterInfo()->getNumRegs(); i != e; ++i) 175 verifyUseList(i); 176 #endif 177 } 178 179 /// Add MO to the linked list of operands for its register. 180 void MachineRegisterInfo::addRegOperandToUseList(MachineOperand *MO) { 181 assert(!MO->isOnRegUseList() && "Already on list"); 182 MachineOperand *&HeadRef = getRegUseDefListHead(MO->getReg()); 183 MachineOperand *const Head = HeadRef; 184 185 // Head points to the first list element. 186 // Next is NULL on the last list element. 187 // Prev pointers are circular, so Head->Prev == Last. 188 189 // Head is NULL for an empty list. 190 if (!Head) { 191 MO->Contents.Reg.Prev = MO; 192 MO->Contents.Reg.Next = 0; 193 HeadRef = MO; 194 return; 195 } 196 assert(MO->getReg() == Head->getReg() && "Different regs on the same list!"); 197 198 // Insert MO between Last and Head in the circular Prev chain. 199 MachineOperand *Last = Head->Contents.Reg.Prev; 200 assert(Last && "Inconsistent use list"); 201 assert(MO->getReg() == Last->getReg() && "Different regs on the same list!"); 202 Head->Contents.Reg.Prev = MO; 203 MO->Contents.Reg.Prev = Last; 204 205 // Def operands always precede uses. This allows def_iterator to stop early. 206 // Insert def operands at the front, and use operands at the back. 207 if (MO->isDef()) { 208 // Insert def at the front. 209 MO->Contents.Reg.Next = Head; 210 HeadRef = MO; 211 } else { 212 // Insert use at the end. 213 MO->Contents.Reg.Next = 0; 214 Last->Contents.Reg.Next = MO; 215 } 216 } 217 218 /// Remove MO from its use-def list. 219 void MachineRegisterInfo::removeRegOperandFromUseList(MachineOperand *MO) { 220 assert(MO->isOnRegUseList() && "Operand not on use list"); 221 MachineOperand *&HeadRef = getRegUseDefListHead(MO->getReg()); 222 MachineOperand *const Head = HeadRef; 223 assert(Head && "List already empty"); 224 225 // Unlink this from the doubly linked list of operands. 226 MachineOperand *Next = MO->Contents.Reg.Next; 227 MachineOperand *Prev = MO->Contents.Reg.Prev; 228 229 // Prev links are circular, next link is NULL instead of looping back to Head. 230 if (MO == Head) 231 HeadRef = Next; 232 else 233 Prev->Contents.Reg.Next = Next; 234 235 (Next ? Next : Head)->Contents.Reg.Prev = Prev; 236 237 MO->Contents.Reg.Prev = 0; 238 MO->Contents.Reg.Next = 0; 239 } 240 241 /// Move NumOps operands from Src to Dst, updating use-def lists as needed. 242 /// 243 /// The Dst range is assumed to be uninitialized memory. (Or it may contain 244 /// operands that won't be destroyed, which is OK because the MO destructor is 245 /// trivial anyway). 246 /// 247 /// The Src and Dst ranges may overlap. 248 void MachineRegisterInfo::moveOperands(MachineOperand *Dst, 249 MachineOperand *Src, 250 unsigned NumOps) { 251 assert(Src != Dst && NumOps && "Noop moveOperands"); 252 253 // Copy backwards if Dst is within the Src range. 254 int Stride = 1; 255 if (Dst >= Src && Dst < Src + NumOps) { 256 Stride = -1; 257 Dst += NumOps - 1; 258 Src += NumOps - 1; 259 } 260 261 // Copy one operand at a time. 262 do { 263 new (Dst) MachineOperand(*Src); 264 265 // Dst takes Src's place in the use-def chain. 266 if (Src->isReg()) { 267 MachineOperand *&Head = getRegUseDefListHead(Src->getReg()); 268 MachineOperand *Prev = Src->Contents.Reg.Prev; 269 MachineOperand *Next = Src->Contents.Reg.Next; 270 assert(Head && "List empty, but operand is chained"); 271 assert(Prev && "Operand was not on use-def list"); 272 273 // Prev links are circular, next link is NULL instead of looping back to 274 // Head. 275 if (Src == Head) 276 Head = Dst; 277 else 278 Prev->Contents.Reg.Next = Dst; 279 280 // Update Prev pointer. This also works when Src was pointing to itself 281 // in a 1-element list. In that case Head == Dst. 282 (Next ? Next : Head)->Contents.Reg.Prev = Dst; 283 } 284 285 Dst += Stride; 286 Src += Stride; 287 } while (--NumOps); 288 } 289 290 /// replaceRegWith - Replace all instances of FromReg with ToReg in the 291 /// machine function. This is like llvm-level X->replaceAllUsesWith(Y), 292 /// except that it also changes any definitions of the register as well. 293 void MachineRegisterInfo::replaceRegWith(unsigned FromReg, unsigned ToReg) { 294 assert(FromReg != ToReg && "Cannot replace a reg with itself"); 295 296 // TODO: This could be more efficient by bulk changing the operands. 297 for (reg_iterator I = reg_begin(FromReg), E = reg_end(); I != E; ) { 298 MachineOperand &O = I.getOperand(); 299 ++I; 300 O.setReg(ToReg); 301 } 302 } 303 304 305 /// getVRegDef - Return the machine instr that defines the specified virtual 306 /// register or null if none is found. This assumes that the code is in SSA 307 /// form, so there should only be one definition. 308 MachineInstr *MachineRegisterInfo::getVRegDef(unsigned Reg) const { 309 // Since we are in SSA form, we can use the first definition. 310 def_iterator I = def_begin(Reg); 311 assert((I.atEnd() || llvm::next(I) == def_end()) && 312 "getVRegDef assumes a single definition or no definition"); 313 return !I.atEnd() ? &*I : 0; 314 } 315 316 /// getUniqueVRegDef - Return the unique machine instr that defines the 317 /// specified virtual register or null if none is found. If there are 318 /// multiple definitions or no definition, return null. 319 MachineInstr *MachineRegisterInfo::getUniqueVRegDef(unsigned Reg) const { 320 if (def_empty(Reg)) return 0; 321 def_iterator I = def_begin(Reg); 322 if (llvm::next(I) != def_end()) 323 return 0; 324 return &*I; 325 } 326 327 bool MachineRegisterInfo::hasOneNonDBGUse(unsigned RegNo) const { 328 use_nodbg_iterator UI = use_nodbg_begin(RegNo); 329 if (UI == use_nodbg_end()) 330 return false; 331 return ++UI == use_nodbg_end(); 332 } 333 334 /// clearKillFlags - Iterate over all the uses of the given register and 335 /// clear the kill flag from the MachineOperand. This function is used by 336 /// optimization passes which extend register lifetimes and need only 337 /// preserve conservative kill flag information. 338 void MachineRegisterInfo::clearKillFlags(unsigned Reg) const { 339 for (use_iterator UI = use_begin(Reg), UE = use_end(); UI != UE; ++UI) 340 UI.getOperand().setIsKill(false); 341 } 342 343 bool MachineRegisterInfo::isLiveIn(unsigned Reg) const { 344 for (livein_iterator I = livein_begin(), E = livein_end(); I != E; ++I) 345 if (I->first == Reg || I->second == Reg) 346 return true; 347 return false; 348 } 349 350 /// getLiveInPhysReg - If VReg is a live-in virtual register, return the 351 /// corresponding live-in physical register. 352 unsigned MachineRegisterInfo::getLiveInPhysReg(unsigned VReg) const { 353 for (livein_iterator I = livein_begin(), E = livein_end(); I != E; ++I) 354 if (I->second == VReg) 355 return I->first; 356 return 0; 357 } 358 359 /// getLiveInVirtReg - If PReg is a live-in physical register, return the 360 /// corresponding live-in physical register. 361 unsigned MachineRegisterInfo::getLiveInVirtReg(unsigned PReg) const { 362 for (livein_iterator I = livein_begin(), E = livein_end(); I != E; ++I) 363 if (I->first == PReg) 364 return I->second; 365 return 0; 366 } 367 368 /// EmitLiveInCopies - Emit copies to initialize livein virtual registers 369 /// into the given entry block. 370 void 371 MachineRegisterInfo::EmitLiveInCopies(MachineBasicBlock *EntryMBB, 372 const TargetRegisterInfo &TRI, 373 const TargetInstrInfo &TII) { 374 // Emit the copies into the top of the block. 375 for (unsigned i = 0, e = LiveIns.size(); i != e; ++i) 376 if (LiveIns[i].second) { 377 if (use_empty(LiveIns[i].second)) { 378 // The livein has no uses. Drop it. 379 // 380 // It would be preferable to have isel avoid creating live-in 381 // records for unused arguments in the first place, but it's 382 // complicated by the debug info code for arguments. 383 LiveIns.erase(LiveIns.begin() + i); 384 --i; --e; 385 } else { 386 // Emit a copy. 387 BuildMI(*EntryMBB, EntryMBB->begin(), DebugLoc(), 388 TII.get(TargetOpcode::COPY), LiveIns[i].second) 389 .addReg(LiveIns[i].first); 390 391 // Add the register to the entry block live-in set. 392 EntryMBB->addLiveIn(LiveIns[i].first); 393 } 394 } else { 395 // Add the register to the entry block live-in set. 396 EntryMBB->addLiveIn(LiveIns[i].first); 397 } 398 } 399 400 #ifndef NDEBUG 401 void MachineRegisterInfo::dumpUses(unsigned Reg) const { 402 for (use_iterator I = use_begin(Reg), E = use_end(); I != E; ++I) 403 I.getOperand().getParent()->dump(); 404 } 405 #endif 406 407 void MachineRegisterInfo::freezeReservedRegs(const MachineFunction &MF) { 408 ReservedRegs = getTargetRegisterInfo()->getReservedRegs(MF); 409 assert(ReservedRegs.size() == getTargetRegisterInfo()->getNumRegs() && 410 "Invalid ReservedRegs vector from target"); 411 } 412 413 bool MachineRegisterInfo::isConstantPhysReg(unsigned PhysReg, 414 const MachineFunction &MF) const { 415 assert(TargetRegisterInfo::isPhysicalRegister(PhysReg)); 416 417 // Check if any overlapping register is modified, or allocatable so it may be 418 // used later. 419 for (MCRegAliasIterator AI(PhysReg, getTargetRegisterInfo(), true); 420 AI.isValid(); ++AI) 421 if (!def_empty(*AI) || isAllocatable(*AI)) 422 return false; 423 return true; 424 } 425