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