MachineRegisterInfo.cpp revision 84be3d5a73313eb19f2f9e0512153cd2e6f46c54
139213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant//===-- lib/Codegen/MachineRegisterInfo.cpp -------------------------------===// 239213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant// 339213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant// The LLVM Compiler Infrastructure 439213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant// 539213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant// This file is distributed under the University of Illinois Open Source 639213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant// License. See LICENSE.TXT for details. 739213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant// 839213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant//===----------------------------------------------------------------------===// 939213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant// 1039213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant// Implementation of the MachineRegisterInfo class. 1139213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant// 1239213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant//===----------------------------------------------------------------------===// 1339213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant 145e57142c5902c3f73a6fdcb8cab55e88ffb43a56Howard Hinnant#include "llvm/CodeGen/MachineRegisterInfo.h" 1539213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant#include "llvm/CodeGen/MachineInstrBuilder.h" 1639213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant#include "llvm/Target/TargetInstrInfo.h" 1739213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant#include "llvm/Target/TargetMachine.h" 1839213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnantusing namespace llvm; 1939213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant 2039213641f4dbaa2f412bd6cceb57f81edcae95f9Howard HinnantMachineRegisterInfo::MachineRegisterInfo(const TargetRegisterInfo &TRI) 2139213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant : TRI(&TRI), IsSSA(true), TracksLiveness(true) { 2239213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant VRegInfo.reserve(256); 2339213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant RegAllocHints.reserve(256); 2439213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant UsedRegUnits.resize(TRI.getNumRegUnits()); 2539213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant UsedPhysRegMask.resize(TRI.getNumRegs()); 2639213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant 2739213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant // Create the physreg use/def lists. 2839213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant PhysRegUseDefLists = new MachineOperand*[TRI.getNumRegs()]; 2939213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant memset(PhysRegUseDefLists, 0, sizeof(MachineOperand*)*TRI.getNumRegs()); 3039213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant} 3139213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant 3239213641f4dbaa2f412bd6cceb57f81edcae95f9Howard HinnantMachineRegisterInfo::~MachineRegisterInfo() { 3339213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant delete [] PhysRegUseDefLists; 3439213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant} 3539213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant 3639213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant/// setRegClass - Set the register class of the specified virtual register. 3739213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant/// 3839213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnantvoid 3939213641f4dbaa2f412bd6cceb57f81edcae95f9Howard HinnantMachineRegisterInfo::setRegClass(unsigned Reg, const TargetRegisterClass *RC) { 4039213641f4dbaa2f412bd6cceb57f81edcae95f9Howard Hinnant VRegInfo[Reg].first = RC; 41} 42 43const TargetRegisterClass * 44MachineRegisterInfo::constrainRegClass(unsigned Reg, 45 const TargetRegisterClass *RC, 46 unsigned MinNumRegs) { 47 const TargetRegisterClass *OldRC = getRegClass(Reg); 48 if (OldRC == RC) 49 return RC; 50 const TargetRegisterClass *NewRC = TRI->getCommonSubClass(OldRC, RC); 51 if (!NewRC || NewRC == OldRC) 52 return NewRC; 53 if (NewRC->getNumRegs() < MinNumRegs) 54 return 0; 55 setRegClass(Reg, NewRC); 56 return NewRC; 57} 58 59bool 60MachineRegisterInfo::recomputeRegClass(unsigned Reg, const TargetMachine &TM) { 61 const TargetInstrInfo *TII = TM.getInstrInfo(); 62 const TargetRegisterClass *OldRC = getRegClass(Reg); 63 const TargetRegisterClass *NewRC = TRI->getLargestLegalSuperClass(OldRC); 64 65 // Stop early if there is no room to grow. 66 if (NewRC == OldRC) 67 return false; 68 69 // Accumulate constraints from all uses. 70 for (reg_nodbg_iterator I = reg_nodbg_begin(Reg), E = reg_nodbg_end(); I != E; 71 ++I) { 72 const TargetRegisterClass *OpRC = 73 I->getRegClassConstraint(I.getOperandNo(), TII, TRI); 74 if (unsigned SubIdx = I.getOperand().getSubReg()) { 75 if (OpRC) 76 NewRC = TRI->getMatchingSuperRegClass(NewRC, OpRC, SubIdx); 77 else 78 NewRC = TRI->getSubClassWithSubReg(NewRC, SubIdx); 79 } else if (OpRC) 80 NewRC = TRI->getCommonSubClass(NewRC, OpRC); 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 return Reg; 103} 104 105/// clearVirtRegs - Remove all virtual registers (after physreg assignment). 106void MachineRegisterInfo::clearVirtRegs() { 107#ifndef NDEBUG 108 for (unsigned i = 0, e = getNumVirtRegs(); i != e; ++i) 109 assert(VRegInfo[TargetRegisterInfo::index2VirtReg(i)].second == 0 && 110 "Vreg use list non-empty still?"); 111#endif 112 VRegInfo.clear(); 113} 114 115/// Add MO to the linked list of operands for its register. 116void MachineRegisterInfo::addRegOperandToUseList(MachineOperand *MO) { 117 assert(!MO->isOnRegUseList() && "Already on list"); 118 MachineOperand *&HeadRef = getRegUseDefListHead(MO->getReg()); 119 MachineOperand *const Head = HeadRef; 120 121 // Head points to the first list element. 122 // Next is NULL on the last list element. 123 // Prev pointers are circular, so Head->Prev == Last. 124 125 // Head is NULL for an empty list. 126 if (!Head) { 127 MO->Contents.Reg.Prev = MO; 128 MO->Contents.Reg.Next = 0; 129 HeadRef = MO; 130 return; 131 } 132 assert(MO->getReg() == Head->getReg() && "Different regs on the same list!"); 133 134 // Insert MO between Last and Head in the circular Prev chain. 135 MachineOperand *Last = Head->Contents.Reg.Prev; 136 assert(Last && "Inconsistent use list"); 137 assert(MO->getReg() == Last->getReg() && "Different regs on the same list!"); 138 Head->Contents.Reg.Prev = MO; 139 MO->Contents.Reg.Prev = Last; 140 141 // Def operands always precede uses. This allows def_iterator to stop early. 142 // Insert def operands at the front, and use operands at the back. 143 if (MO->isDef()) { 144 // Insert def at the front. 145 MO->Contents.Reg.Next = Head; 146 HeadRef = MO; 147 } else { 148 // Insert use at the end. 149 MO->Contents.Reg.Next = 0; 150 Last->Contents.Reg.Next = MO; 151 } 152} 153 154/// Remove MO from its use-def list. 155void MachineRegisterInfo::removeRegOperandFromUseList(MachineOperand *MO) { 156 assert(MO->isOnRegUseList() && "Operand not on use list"); 157 MachineOperand *&HeadRef = getRegUseDefListHead(MO->getReg()); 158 MachineOperand *const Head = HeadRef; 159 assert(Head && "List already empty"); 160 161 // Unlink this from the doubly linked list of operands. 162 MachineOperand *Next = MO->Contents.Reg.Next; 163 MachineOperand *Prev = MO->Contents.Reg.Prev; 164 165 // Prev links are circular, next link is NULL instead of looping back to Head. 166 if (MO == Head) 167 HeadRef = Next; 168 else 169 Prev->Contents.Reg.Next = Next; 170 171 (Next ? Next : Head)->Contents.Reg.Prev = Prev; 172 173 MO->Contents.Reg.Prev = 0; 174 MO->Contents.Reg.Next = 0; 175} 176 177/// Move NumOps operands from Src to Dst, updating use-def lists as needed. 178/// 179/// The Dst range is assumed to be uninitialized memory. (Or it may contain 180/// operands that won't be destroyed, which is OK because the MO destructor is 181/// trivial anyway). 182/// 183/// The Src and Dst ranges may overlap. 184void MachineRegisterInfo::moveOperands(MachineOperand *Dst, 185 MachineOperand *Src, 186 unsigned NumOps) { 187 assert(Src != Dst && NumOps && "Noop moveOperands"); 188 189 // Copy backwards if Dst is within the Src range. 190 int Stride = 1; 191 if (Dst >= Src && Dst < Src + NumOps) { 192 Stride = -1; 193 Dst += NumOps - 1; 194 Src += NumOps - 1; 195 } 196 197 // Copy one operand at a time. 198 do { 199 new (Dst) MachineOperand(*Src); 200 201 // Dst takes Src's place in the use-def chain. 202 if (Src->isReg()) { 203 MachineOperand *&Head = getRegUseDefListHead(Src->getReg()); 204 MachineOperand *Prev = Src->Contents.Reg.Prev; 205 MachineOperand *Next = Src->Contents.Reg.Next; 206 assert(Head && "List empty, but operand is chained"); 207 assert(Prev && "Operand was not on use-def list"); 208 209 // Prev links are circular, next link is NULL instead of looping back to 210 // Head. 211 if (Src == Head) 212 Head = Dst; 213 else 214 Prev->Contents.Reg.Next = Dst; 215 216 // Update Prev pointer. This also works when Src was pointing to itself 217 // in a 1-element list. In that case Head == Dst. 218 (Next ? Next : Head)->Contents.Reg.Prev = Dst; 219 } 220 221 Dst += Stride; 222 Src += Stride; 223 } while (--NumOps); 224} 225 226/// replaceRegWith - Replace all instances of FromReg with ToReg in the 227/// machine function. This is like llvm-level X->replaceAllUsesWith(Y), 228/// except that it also changes any definitions of the register as well. 229void MachineRegisterInfo::replaceRegWith(unsigned FromReg, unsigned ToReg) { 230 assert(FromReg != ToReg && "Cannot replace a reg with itself"); 231 232 // TODO: This could be more efficient by bulk changing the operands. 233 for (reg_iterator I = reg_begin(FromReg), E = reg_end(); I != E; ) { 234 MachineOperand &O = I.getOperand(); 235 ++I; 236 O.setReg(ToReg); 237 } 238} 239 240 241/// getVRegDef - Return the machine instr that defines the specified virtual 242/// register or null if none is found. This assumes that the code is in SSA 243/// form, so there should only be one definition. 244MachineInstr *MachineRegisterInfo::getVRegDef(unsigned Reg) const { 245 // Since we are in SSA form, we can use the first definition. 246 def_iterator I = def_begin(Reg); 247 assert((I.atEnd() || llvm::next(I) == def_end()) && 248 "getVRegDef assumes a single definition or no definition"); 249 return !I.atEnd() ? &*I : 0; 250} 251 252/// getUniqueVRegDef - Return the unique machine instr that defines the 253/// specified virtual register or null if none is found. If there are 254/// multiple definitions or no definition, return null. 255MachineInstr *MachineRegisterInfo::getUniqueVRegDef(unsigned Reg) const { 256 if (def_empty(Reg)) return 0; 257 def_iterator I = def_begin(Reg); 258 if (llvm::next(I) != def_end()) 259 return 0; 260 return &*I; 261} 262 263bool MachineRegisterInfo::hasOneNonDBGUse(unsigned RegNo) const { 264 use_nodbg_iterator UI = use_nodbg_begin(RegNo); 265 if (UI == use_nodbg_end()) 266 return false; 267 return ++UI == use_nodbg_end(); 268} 269 270/// clearKillFlags - Iterate over all the uses of the given register and 271/// clear the kill flag from the MachineOperand. This function is used by 272/// optimization passes which extend register lifetimes and need only 273/// preserve conservative kill flag information. 274void MachineRegisterInfo::clearKillFlags(unsigned Reg) const { 275 for (use_iterator UI = use_begin(Reg), UE = use_end(); UI != UE; ++UI) 276 UI.getOperand().setIsKill(false); 277} 278 279bool MachineRegisterInfo::isLiveIn(unsigned Reg) const { 280 for (livein_iterator I = livein_begin(), E = livein_end(); I != E; ++I) 281 if (I->first == Reg || I->second == Reg) 282 return true; 283 return false; 284} 285 286bool MachineRegisterInfo::isLiveOut(unsigned Reg) const { 287 for (liveout_iterator I = liveout_begin(), E = liveout_end(); I != E; ++I) 288 if (*I == Reg) 289 return true; 290 return false; 291} 292 293/// getLiveInPhysReg - If VReg is a live-in virtual register, return the 294/// corresponding live-in physical register. 295unsigned MachineRegisterInfo::getLiveInPhysReg(unsigned VReg) const { 296 for (livein_iterator I = livein_begin(), E = livein_end(); I != E; ++I) 297 if (I->second == VReg) 298 return I->first; 299 return 0; 300} 301 302/// getLiveInVirtReg - If PReg is a live-in physical register, return the 303/// corresponding live-in physical register. 304unsigned MachineRegisterInfo::getLiveInVirtReg(unsigned PReg) const { 305 for (livein_iterator I = livein_begin(), E = livein_end(); I != E; ++I) 306 if (I->first == PReg) 307 return I->second; 308 return 0; 309} 310 311/// EmitLiveInCopies - Emit copies to initialize livein virtual registers 312/// into the given entry block. 313void 314MachineRegisterInfo::EmitLiveInCopies(MachineBasicBlock *EntryMBB, 315 const TargetRegisterInfo &TRI, 316 const TargetInstrInfo &TII) { 317 // Emit the copies into the top of the block. 318 for (unsigned i = 0, e = LiveIns.size(); i != e; ++i) 319 if (LiveIns[i].second) { 320 if (use_empty(LiveIns[i].second)) { 321 // The livein has no uses. Drop it. 322 // 323 // It would be preferable to have isel avoid creating live-in 324 // records for unused arguments in the first place, but it's 325 // complicated by the debug info code for arguments. 326 LiveIns.erase(LiveIns.begin() + i); 327 --i; --e; 328 } else { 329 // Emit a copy. 330 BuildMI(*EntryMBB, EntryMBB->begin(), DebugLoc(), 331 TII.get(TargetOpcode::COPY), LiveIns[i].second) 332 .addReg(LiveIns[i].first); 333 334 // Add the register to the entry block live-in set. 335 EntryMBB->addLiveIn(LiveIns[i].first); 336 } 337 } else { 338 // Add the register to the entry block live-in set. 339 EntryMBB->addLiveIn(LiveIns[i].first); 340 } 341} 342 343#ifndef NDEBUG 344void MachineRegisterInfo::dumpUses(unsigned Reg) const { 345 for (use_iterator I = use_begin(Reg), E = use_end(); I != E; ++I) 346 I.getOperand().getParent()->dump(); 347} 348#endif 349 350void MachineRegisterInfo::freezeReservedRegs(const MachineFunction &MF) { 351 ReservedRegs = TRI->getReservedRegs(MF); 352 assert(ReservedRegs.size() == TRI->getNumRegs() && 353 "Invalid ReservedRegs vector from target"); 354} 355 356bool MachineRegisterInfo::isConstantPhysReg(unsigned PhysReg, 357 const MachineFunction &MF) const { 358 assert(TargetRegisterInfo::isPhysicalRegister(PhysReg)); 359 360 // Check if any overlapping register is modified, or allocatable so it may be 361 // used later. 362 for (MCRegAliasIterator AI(PhysReg, TRI, true); AI.isValid(); ++AI) 363 if (!def_empty(*AI) || isAllocatable(*AI)) 364 return false; 365 return true; 366} 367