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/IR/Function.h" 17 #include "llvm/Support/raw_os_ostream.h" 18 #include "llvm/Target/TargetInstrInfo.h" 19 #include "llvm/Target/TargetMachine.h" 20 #include "llvm/Target/TargetSubtargetInfo.h" 21 22 using namespace llvm; 23 24 // Pin the vtable to this file. 25 void MachineRegisterInfo::Delegate::anchor() {} 26 27 MachineRegisterInfo::MachineRegisterInfo(MachineFunction *MF) 28 : MF(MF), TheDelegate(nullptr), TracksSubRegLiveness(false) { 29 unsigned NumRegs = getTargetRegisterInfo()->getNumRegs(); 30 VRegInfo.reserve(256); 31 RegAllocHints.reserve(256); 32 UsedPhysRegMask.resize(NumRegs); 33 PhysRegUseDefLists.reset(new MachineOperand*[NumRegs]()); 34 } 35 36 /// setRegClass - Set the register class of the specified virtual register. 37 /// 38 void 39 MachineRegisterInfo::setRegClass(unsigned Reg, const TargetRegisterClass *RC) { 40 assert(RC && RC->isAllocatable() && "Invalid RC for virtual register"); 41 VRegInfo[Reg].first = RC; 42 } 43 44 void MachineRegisterInfo::setRegBank(unsigned Reg, 45 const RegisterBank &RegBank) { 46 VRegInfo[Reg].first = &RegBank; 47 } 48 49 const TargetRegisterClass * 50 MachineRegisterInfo::constrainRegClass(unsigned Reg, 51 const TargetRegisterClass *RC, 52 unsigned MinNumRegs) { 53 const TargetRegisterClass *OldRC = getRegClass(Reg); 54 if (OldRC == RC) 55 return RC; 56 const TargetRegisterClass *NewRC = 57 getTargetRegisterInfo()->getCommonSubClass(OldRC, RC); 58 if (!NewRC || NewRC == OldRC) 59 return NewRC; 60 if (NewRC->getNumRegs() < MinNumRegs) 61 return nullptr; 62 setRegClass(Reg, NewRC); 63 return NewRC; 64 } 65 66 bool 67 MachineRegisterInfo::recomputeRegClass(unsigned Reg) { 68 const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo(); 69 const TargetRegisterClass *OldRC = getRegClass(Reg); 70 const TargetRegisterClass *NewRC = 71 getTargetRegisterInfo()->getLargestLegalSuperClass(OldRC, *MF); 72 73 // Stop early if there is no room to grow. 74 if (NewRC == OldRC) 75 return false; 76 77 // Accumulate constraints from all uses. 78 for (MachineOperand &MO : reg_nodbg_operands(Reg)) { 79 // Apply the effect of the given operand to NewRC. 80 MachineInstr *MI = MO.getParent(); 81 unsigned OpNo = &MO - &MI->getOperand(0); 82 NewRC = MI->getRegClassConstraintEffect(OpNo, NewRC, TII, 83 getTargetRegisterInfo()); 84 if (!NewRC || NewRC == OldRC) 85 return false; 86 } 87 setRegClass(Reg, NewRC); 88 return true; 89 } 90 91 /// createVirtualRegister - Create and return a new virtual register in the 92 /// function with the specified register class. 93 /// 94 unsigned 95 MachineRegisterInfo::createVirtualRegister(const TargetRegisterClass *RegClass){ 96 assert(RegClass && "Cannot create register without RegClass!"); 97 assert(RegClass->isAllocatable() && 98 "Virtual register RegClass must be allocatable."); 99 100 // New virtual register number. 101 unsigned Reg = TargetRegisterInfo::index2VirtReg(getNumVirtRegs()); 102 VRegInfo.grow(Reg); 103 VRegInfo[Reg].first = RegClass; 104 RegAllocHints.grow(Reg); 105 if (TheDelegate) 106 TheDelegate->MRI_NoteNewVirtualRegister(Reg); 107 return Reg; 108 } 109 110 unsigned 111 MachineRegisterInfo::getSize(unsigned VReg) const { 112 VRegToSizeMap::const_iterator SizeIt = getVRegToSize().find(VReg); 113 return SizeIt != getVRegToSize().end() ? SizeIt->second : 0; 114 } 115 116 void MachineRegisterInfo::setSize(unsigned VReg, unsigned Size) { 117 getVRegToSize()[VReg] = Size; 118 } 119 120 unsigned 121 MachineRegisterInfo::createGenericVirtualRegister(unsigned Size) { 122 assert(Size && "Cannot create empty virtual register"); 123 124 // New virtual register number. 125 unsigned Reg = TargetRegisterInfo::index2VirtReg(getNumVirtRegs()); 126 VRegInfo.grow(Reg); 127 // FIXME: Should we use a dummy register class? 128 VRegInfo[Reg].first = static_cast<TargetRegisterClass *>(nullptr); 129 getVRegToSize()[Reg] = Size; 130 RegAllocHints.grow(Reg); 131 if (TheDelegate) 132 TheDelegate->MRI_NoteNewVirtualRegister(Reg); 133 return Reg; 134 } 135 136 /// clearVirtRegs - Remove all virtual registers (after physreg assignment). 137 void MachineRegisterInfo::clearVirtRegs() { 138 #ifndef NDEBUG 139 for (unsigned i = 0, e = getNumVirtRegs(); i != e; ++i) { 140 unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 141 if (!VRegInfo[Reg].second) 142 continue; 143 verifyUseList(Reg); 144 llvm_unreachable("Remaining virtual register operands"); 145 } 146 #endif 147 VRegInfo.clear(); 148 for (auto &I : LiveIns) 149 I.second = 0; 150 } 151 152 void MachineRegisterInfo::verifyUseList(unsigned Reg) const { 153 #ifndef NDEBUG 154 bool Valid = true; 155 for (MachineOperand &M : reg_operands(Reg)) { 156 MachineOperand *MO = &M; 157 MachineInstr *MI = MO->getParent(); 158 if (!MI) { 159 errs() << PrintReg(Reg, getTargetRegisterInfo()) 160 << " use list MachineOperand " << MO 161 << " has no parent instruction.\n"; 162 Valid = false; 163 continue; 164 } 165 MachineOperand *MO0 = &MI->getOperand(0); 166 unsigned NumOps = MI->getNumOperands(); 167 if (!(MO >= MO0 && MO < MO0+NumOps)) { 168 errs() << PrintReg(Reg, getTargetRegisterInfo()) 169 << " use list MachineOperand " << MO 170 << " doesn't belong to parent MI: " << *MI; 171 Valid = false; 172 } 173 if (!MO->isReg()) { 174 errs() << PrintReg(Reg, getTargetRegisterInfo()) 175 << " MachineOperand " << MO << ": " << *MO 176 << " is not a register\n"; 177 Valid = false; 178 } 179 if (MO->getReg() != Reg) { 180 errs() << PrintReg(Reg, getTargetRegisterInfo()) 181 << " use-list MachineOperand " << MO << ": " 182 << *MO << " is the wrong register\n"; 183 Valid = false; 184 } 185 } 186 assert(Valid && "Invalid use list"); 187 #endif 188 } 189 190 void MachineRegisterInfo::verifyUseLists() const { 191 #ifndef NDEBUG 192 for (unsigned i = 0, e = getNumVirtRegs(); i != e; ++i) 193 verifyUseList(TargetRegisterInfo::index2VirtReg(i)); 194 for (unsigned i = 1, e = getTargetRegisterInfo()->getNumRegs(); i != e; ++i) 195 verifyUseList(i); 196 #endif 197 } 198 199 /// Add MO to the linked list of operands for its register. 200 void MachineRegisterInfo::addRegOperandToUseList(MachineOperand *MO) { 201 assert(!MO->isOnRegUseList() && "Already on list"); 202 MachineOperand *&HeadRef = getRegUseDefListHead(MO->getReg()); 203 MachineOperand *const Head = HeadRef; 204 205 // Head points to the first list element. 206 // Next is NULL on the last list element. 207 // Prev pointers are circular, so Head->Prev == Last. 208 209 // Head is NULL for an empty list. 210 if (!Head) { 211 MO->Contents.Reg.Prev = MO; 212 MO->Contents.Reg.Next = nullptr; 213 HeadRef = MO; 214 return; 215 } 216 assert(MO->getReg() == Head->getReg() && "Different regs on the same list!"); 217 218 // Insert MO between Last and Head in the circular Prev chain. 219 MachineOperand *Last = Head->Contents.Reg.Prev; 220 assert(Last && "Inconsistent use list"); 221 assert(MO->getReg() == Last->getReg() && "Different regs on the same list!"); 222 Head->Contents.Reg.Prev = MO; 223 MO->Contents.Reg.Prev = Last; 224 225 // Def operands always precede uses. This allows def_iterator to stop early. 226 // Insert def operands at the front, and use operands at the back. 227 if (MO->isDef()) { 228 // Insert def at the front. 229 MO->Contents.Reg.Next = Head; 230 HeadRef = MO; 231 } else { 232 // Insert use at the end. 233 MO->Contents.Reg.Next = nullptr; 234 Last->Contents.Reg.Next = MO; 235 } 236 } 237 238 /// Remove MO from its use-def list. 239 void MachineRegisterInfo::removeRegOperandFromUseList(MachineOperand *MO) { 240 assert(MO->isOnRegUseList() && "Operand not on use list"); 241 MachineOperand *&HeadRef = getRegUseDefListHead(MO->getReg()); 242 MachineOperand *const Head = HeadRef; 243 assert(Head && "List already empty"); 244 245 // Unlink this from the doubly linked list of operands. 246 MachineOperand *Next = MO->Contents.Reg.Next; 247 MachineOperand *Prev = MO->Contents.Reg.Prev; 248 249 // Prev links are circular, next link is NULL instead of looping back to Head. 250 if (MO == Head) 251 HeadRef = Next; 252 else 253 Prev->Contents.Reg.Next = Next; 254 255 (Next ? Next : Head)->Contents.Reg.Prev = Prev; 256 257 MO->Contents.Reg.Prev = nullptr; 258 MO->Contents.Reg.Next = nullptr; 259 } 260 261 /// Move NumOps operands from Src to Dst, updating use-def lists as needed. 262 /// 263 /// The Dst range is assumed to be uninitialized memory. (Or it may contain 264 /// operands that won't be destroyed, which is OK because the MO destructor is 265 /// trivial anyway). 266 /// 267 /// The Src and Dst ranges may overlap. 268 void MachineRegisterInfo::moveOperands(MachineOperand *Dst, 269 MachineOperand *Src, 270 unsigned NumOps) { 271 assert(Src != Dst && NumOps && "Noop moveOperands"); 272 273 // Copy backwards if Dst is within the Src range. 274 int Stride = 1; 275 if (Dst >= Src && Dst < Src + NumOps) { 276 Stride = -1; 277 Dst += NumOps - 1; 278 Src += NumOps - 1; 279 } 280 281 // Copy one operand at a time. 282 do { 283 new (Dst) MachineOperand(*Src); 284 285 // Dst takes Src's place in the use-def chain. 286 if (Src->isReg()) { 287 MachineOperand *&Head = getRegUseDefListHead(Src->getReg()); 288 MachineOperand *Prev = Src->Contents.Reg.Prev; 289 MachineOperand *Next = Src->Contents.Reg.Next; 290 assert(Head && "List empty, but operand is chained"); 291 assert(Prev && "Operand was not on use-def list"); 292 293 // Prev links are circular, next link is NULL instead of looping back to 294 // Head. 295 if (Src == Head) 296 Head = Dst; 297 else 298 Prev->Contents.Reg.Next = Dst; 299 300 // Update Prev pointer. This also works when Src was pointing to itself 301 // in a 1-element list. In that case Head == Dst. 302 (Next ? Next : Head)->Contents.Reg.Prev = Dst; 303 } 304 305 Dst += Stride; 306 Src += Stride; 307 } while (--NumOps); 308 } 309 310 /// replaceRegWith - Replace all instances of FromReg with ToReg in the 311 /// machine function. This is like llvm-level X->replaceAllUsesWith(Y), 312 /// except that it also changes any definitions of the register as well. 313 /// If ToReg is a physical register we apply the sub register to obtain the 314 /// final/proper physical register. 315 void MachineRegisterInfo::replaceRegWith(unsigned FromReg, unsigned ToReg) { 316 assert(FromReg != ToReg && "Cannot replace a reg with itself"); 317 318 const TargetRegisterInfo *TRI = getTargetRegisterInfo(); 319 320 // TODO: This could be more efficient by bulk changing the operands. 321 for (reg_iterator I = reg_begin(FromReg), E = reg_end(); I != E; ) { 322 MachineOperand &O = *I; 323 ++I; 324 if (TargetRegisterInfo::isPhysicalRegister(ToReg)) { 325 O.substPhysReg(ToReg, *TRI); 326 } else { 327 O.setReg(ToReg); 328 } 329 } 330 } 331 332 /// getVRegDef - Return the machine instr that defines the specified virtual 333 /// register or null if none is found. This assumes that the code is in SSA 334 /// form, so there should only be one definition. 335 MachineInstr *MachineRegisterInfo::getVRegDef(unsigned Reg) const { 336 // Since we are in SSA form, we can use the first definition. 337 def_instr_iterator I = def_instr_begin(Reg); 338 assert((I.atEnd() || std::next(I) == def_instr_end()) && 339 "getVRegDef assumes a single definition or no definition"); 340 return !I.atEnd() ? &*I : nullptr; 341 } 342 343 /// getUniqueVRegDef - Return the unique machine instr that defines the 344 /// specified virtual register or null if none is found. If there are 345 /// multiple definitions or no definition, return null. 346 MachineInstr *MachineRegisterInfo::getUniqueVRegDef(unsigned Reg) const { 347 if (def_empty(Reg)) return nullptr; 348 def_instr_iterator I = def_instr_begin(Reg); 349 if (std::next(I) != def_instr_end()) 350 return nullptr; 351 return &*I; 352 } 353 354 bool MachineRegisterInfo::hasOneNonDBGUse(unsigned RegNo) const { 355 use_nodbg_iterator UI = use_nodbg_begin(RegNo); 356 if (UI == use_nodbg_end()) 357 return false; 358 return ++UI == use_nodbg_end(); 359 } 360 361 /// clearKillFlags - Iterate over all the uses of the given register and 362 /// clear the kill flag from the MachineOperand. This function is used by 363 /// optimization passes which extend register lifetimes and need only 364 /// preserve conservative kill flag information. 365 void MachineRegisterInfo::clearKillFlags(unsigned Reg) const { 366 for (MachineOperand &MO : use_operands(Reg)) 367 MO.setIsKill(false); 368 } 369 370 bool MachineRegisterInfo::isLiveIn(unsigned Reg) const { 371 for (livein_iterator I = livein_begin(), E = livein_end(); I != E; ++I) 372 if (I->first == Reg || I->second == Reg) 373 return true; 374 return false; 375 } 376 377 /// getLiveInPhysReg - If VReg is a live-in virtual register, return the 378 /// corresponding live-in physical register. 379 unsigned MachineRegisterInfo::getLiveInPhysReg(unsigned VReg) const { 380 for (livein_iterator I = livein_begin(), E = livein_end(); I != E; ++I) 381 if (I->second == VReg) 382 return I->first; 383 return 0; 384 } 385 386 /// getLiveInVirtReg - If PReg is a live-in physical register, return the 387 /// corresponding live-in physical register. 388 unsigned MachineRegisterInfo::getLiveInVirtReg(unsigned PReg) const { 389 for (livein_iterator I = livein_begin(), E = livein_end(); I != E; ++I) 390 if (I->first == PReg) 391 return I->second; 392 return 0; 393 } 394 395 /// EmitLiveInCopies - Emit copies to initialize livein virtual registers 396 /// into the given entry block. 397 void 398 MachineRegisterInfo::EmitLiveInCopies(MachineBasicBlock *EntryMBB, 399 const TargetRegisterInfo &TRI, 400 const TargetInstrInfo &TII) { 401 // Emit the copies into the top of the block. 402 for (unsigned i = 0, e = LiveIns.size(); i != e; ++i) 403 if (LiveIns[i].second) { 404 if (use_empty(LiveIns[i].second)) { 405 // The livein has no uses. Drop it. 406 // 407 // It would be preferable to have isel avoid creating live-in 408 // records for unused arguments in the first place, but it's 409 // complicated by the debug info code for arguments. 410 LiveIns.erase(LiveIns.begin() + i); 411 --i; --e; 412 } else { 413 // Emit a copy. 414 BuildMI(*EntryMBB, EntryMBB->begin(), DebugLoc(), 415 TII.get(TargetOpcode::COPY), LiveIns[i].second) 416 .addReg(LiveIns[i].first); 417 418 // Add the register to the entry block live-in set. 419 EntryMBB->addLiveIn(LiveIns[i].first); 420 } 421 } else { 422 // Add the register to the entry block live-in set. 423 EntryMBB->addLiveIn(LiveIns[i].first); 424 } 425 } 426 427 LaneBitmask MachineRegisterInfo::getMaxLaneMaskForVReg(unsigned Reg) const { 428 // Lane masks are only defined for vregs. 429 assert(TargetRegisterInfo::isVirtualRegister(Reg)); 430 const TargetRegisterClass &TRC = *getRegClass(Reg); 431 return TRC.getLaneMask(); 432 } 433 434 #ifndef NDEBUG 435 void MachineRegisterInfo::dumpUses(unsigned Reg) const { 436 for (MachineInstr &I : use_instructions(Reg)) 437 I.dump(); 438 } 439 #endif 440 441 void MachineRegisterInfo::freezeReservedRegs(const MachineFunction &MF) { 442 ReservedRegs = getTargetRegisterInfo()->getReservedRegs(MF); 443 assert(ReservedRegs.size() == getTargetRegisterInfo()->getNumRegs() && 444 "Invalid ReservedRegs vector from target"); 445 } 446 447 bool MachineRegisterInfo::isConstantPhysReg(unsigned PhysReg, 448 const MachineFunction &MF) const { 449 assert(TargetRegisterInfo::isPhysicalRegister(PhysReg)); 450 451 // Check if any overlapping register is modified, or allocatable so it may be 452 // used later. 453 for (MCRegAliasIterator AI(PhysReg, getTargetRegisterInfo(), true); 454 AI.isValid(); ++AI) 455 if (!def_empty(*AI) || isAllocatable(*AI)) 456 return false; 457 return true; 458 } 459 460 /// markUsesInDebugValueAsUndef - Mark every DBG_VALUE referencing the 461 /// specified register as undefined which causes the DBG_VALUE to be 462 /// deleted during LiveDebugVariables analysis. 463 void MachineRegisterInfo::markUsesInDebugValueAsUndef(unsigned Reg) const { 464 // Mark any DBG_VALUE that uses Reg as undef (but don't delete it.) 465 MachineRegisterInfo::use_instr_iterator nextI; 466 for (use_instr_iterator I = use_instr_begin(Reg), E = use_instr_end(); 467 I != E; I = nextI) { 468 nextI = std::next(I); // I is invalidated by the setReg 469 MachineInstr *UseMI = &*I; 470 if (UseMI->isDebugValue()) 471 UseMI->getOperand(0).setReg(0U); 472 } 473 } 474 475 static const Function *getCalledFunction(const MachineInstr &MI) { 476 for (const MachineOperand &MO : MI.operands()) { 477 if (!MO.isGlobal()) 478 continue; 479 const Function *Func = dyn_cast<Function>(MO.getGlobal()); 480 if (Func != nullptr) 481 return Func; 482 } 483 return nullptr; 484 } 485 486 static bool isNoReturnDef(const MachineOperand &MO) { 487 // Anything which is not a noreturn function is a real def. 488 const MachineInstr &MI = *MO.getParent(); 489 if (!MI.isCall()) 490 return false; 491 const MachineBasicBlock &MBB = *MI.getParent(); 492 if (!MBB.succ_empty()) 493 return false; 494 const MachineFunction &MF = *MBB.getParent(); 495 // We need to keep correct unwind information even if the function will 496 // not return, since the runtime may need it. 497 if (MF.getFunction()->hasFnAttribute(Attribute::UWTable)) 498 return false; 499 const Function *Called = getCalledFunction(MI); 500 return !(Called == nullptr || !Called->hasFnAttribute(Attribute::NoReturn) || 501 !Called->hasFnAttribute(Attribute::NoUnwind)); 502 } 503 504 bool MachineRegisterInfo::isPhysRegModified(unsigned PhysReg, 505 bool SkipNoReturnDef) const { 506 if (UsedPhysRegMask.test(PhysReg)) 507 return true; 508 const TargetRegisterInfo *TRI = getTargetRegisterInfo(); 509 for (MCRegAliasIterator AI(PhysReg, TRI, true); AI.isValid(); ++AI) { 510 for (const MachineOperand &MO : make_range(def_begin(*AI), def_end())) { 511 if (!SkipNoReturnDef && isNoReturnDef(MO)) 512 continue; 513 return true; 514 } 515 } 516 return false; 517 } 518 519 bool MachineRegisterInfo::isPhysRegUsed(unsigned PhysReg) const { 520 if (UsedPhysRegMask.test(PhysReg)) 521 return true; 522 const TargetRegisterInfo *TRI = getTargetRegisterInfo(); 523 for (MCRegAliasIterator AliasReg(PhysReg, TRI, true); AliasReg.isValid(); 524 ++AliasReg) { 525 if (!reg_nodbg_empty(*AliasReg)) 526 return true; 527 } 528 return false; 529 } 530