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