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