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