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