LLVM API Documentation
00001 //===-- RegisterScavenging.cpp - Machine register scavenging --------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements the machine register scavenger. It can provide 00011 // information, such as unused registers, at any point in a machine basic block. 00012 // It also provides a mechanism to make registers available by evicting them to 00013 // spill slots. 00014 // 00015 //===----------------------------------------------------------------------===// 00016 00017 #define DEBUG_TYPE "reg-scavenging" 00018 #include "llvm/CodeGen/RegisterScavenging.h" 00019 #include "llvm/CodeGen/MachineFrameInfo.h" 00020 #include "llvm/CodeGen/MachineFunction.h" 00021 #include "llvm/CodeGen/MachineBasicBlock.h" 00022 #include "llvm/CodeGen/MachineInstr.h" 00023 #include "llvm/CodeGen/MachineRegisterInfo.h" 00024 #include "llvm/Support/ErrorHandling.h" 00025 #include "llvm/Target/TargetRegisterInfo.h" 00026 #include "llvm/Target/TargetInstrInfo.h" 00027 #include "llvm/Target/TargetMachine.h" 00028 #include "llvm/ADT/DenseMap.h" 00029 #include "llvm/ADT/SmallPtrSet.h" 00030 #include "llvm/ADT/SmallVector.h" 00031 #include "llvm/ADT/STLExtras.h" 00032 using namespace llvm; 00033 00034 /// setUsed - Set the register and its sub-registers as being used. 00035 void RegScavenger::setUsed(unsigned Reg) { 00036 RegsAvailable.reset(Reg); 00037 00038 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 00039 unsigned SubReg = *SubRegs; ++SubRegs) 00040 RegsAvailable.reset(SubReg); 00041 } 00042 00043 bool RegScavenger::isAliasUsed(unsigned Reg) const { 00044 if (isUsed(Reg)) 00045 return true; 00046 for (const unsigned *R = TRI->getAliasSet(Reg); *R; ++R) 00047 if (isUsed(*R)) 00048 return true; 00049 return false; 00050 } 00051 00052 void RegScavenger::initRegState() { 00053 ScavengedReg = 0; 00054 ScavengedRC = NULL; 00055 ScavengeRestore = NULL; 00056 00057 // All registers started out unused. 00058 RegsAvailable.set(); 00059 00060 // Reserved registers are always used. 00061 RegsAvailable ^= ReservedRegs; 00062 00063 if (!MBB) 00064 return; 00065 00066 // Live-in registers are in use. 00067 for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(), 00068 E = MBB->livein_end(); I != E; ++I) 00069 setUsed(*I); 00070 00071 // Pristine CSRs are also unavailable. 00072 BitVector PR = MBB->getParent()->getFrameInfo()->getPristineRegs(MBB); 00073 for (int I = PR.find_first(); I>0; I = PR.find_next(I)) 00074 setUsed(I); 00075 } 00076 00077 void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) { 00078 MachineFunction &MF = *mbb->getParent(); 00079 const TargetMachine &TM = MF.getTarget(); 00080 TII = TM.getInstrInfo(); 00081 TRI = TM.getRegisterInfo(); 00082 MRI = &MF.getRegInfo(); 00083 00084 assert((NumPhysRegs == 0 || NumPhysRegs == TRI->getNumRegs()) && 00085 "Target changed?"); 00086 00087 // Self-initialize. 00088 if (!MBB) { 00089 NumPhysRegs = TRI->getNumRegs(); 00090 RegsAvailable.resize(NumPhysRegs); 00091 00092 // Create reserved registers bitvector. 00093 ReservedRegs = TRI->getReservedRegs(MF); 00094 00095 // Create callee-saved registers bitvector. 00096 CalleeSavedRegs.resize(NumPhysRegs); 00097 const unsigned *CSRegs = TRI->getCalleeSavedRegs(); 00098 if (CSRegs != NULL) 00099 for (unsigned i = 0; CSRegs[i]; ++i) 00100 CalleeSavedRegs.set(CSRegs[i]); 00101 } 00102 00103 // RS used within emit{Pro,Epi}logue() 00104 if (mbb != MBB) { 00105 MBB = mbb; 00106 initRegState(); 00107 } 00108 00109 Tracking = false; 00110 } 00111 00112 #ifndef NDEBUG 00113 /// isLiveInButUnusedBefore - Return true if register is livein the MBB not 00114 /// not used before it reaches the MI that defines register. 00115 static bool isLiveInButUnusedBefore(unsigned Reg, MachineInstr *MI, 00116 MachineBasicBlock *MBB, 00117 const TargetRegisterInfo *TRI, 00118 MachineRegisterInfo* MRI) { 00119 // First check if register is livein. 00120 bool isLiveIn = false; 00121 for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(), 00122 E = MBB->livein_end(); I != E; ++I) 00123 if (Reg == *I || TRI->isSuperRegister(Reg, *I)) { 00124 isLiveIn = true; 00125 break; 00126 } 00127 if (!isLiveIn) 00128 return false; 00129 00130 // Is there any use of it before the specified MI? 00131 SmallPtrSet<MachineInstr*, 4> UsesInMBB; 00132 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg), 00133 UE = MRI->use_end(); UI != UE; ++UI) { 00134 MachineOperand &UseMO = UI.getOperand(); 00135 if (UseMO.isReg() && UseMO.isUndef()) 00136 continue; 00137 MachineInstr *UseMI = &*UI; 00138 if (UseMI->getParent() == MBB) 00139 UsesInMBB.insert(UseMI); 00140 } 00141 if (UsesInMBB.empty()) 00142 return true; 00143 00144 for (MachineBasicBlock::iterator I = MBB->begin(), E = MI; I != E; ++I) 00145 if (UsesInMBB.count(&*I)) 00146 return false; 00147 return true; 00148 } 00149 #endif 00150 00151 void RegScavenger::addRegWithSubRegs(BitVector &BV, unsigned Reg) { 00152 BV.set(Reg); 00153 for (const unsigned *R = TRI->getSubRegisters(Reg); *R; R++) 00154 BV.set(*R); 00155 } 00156 00157 void RegScavenger::addRegWithAliases(BitVector &BV, unsigned Reg) { 00158 BV.set(Reg); 00159 for (const unsigned *R = TRI->getAliasSet(Reg); *R; R++) 00160 BV.set(*R); 00161 } 00162 00163 void RegScavenger::forward() { 00164 // Move ptr forward. 00165 if (!Tracking) { 00166 MBBI = MBB->begin(); 00167 Tracking = true; 00168 } else { 00169 assert(MBBI != MBB->end() && "Already at the end of the basic block!"); 00170 MBBI = next(MBBI); 00171 } 00172 00173 MachineInstr *MI = MBBI; 00174 00175 if (MI == ScavengeRestore) { 00176 ScavengedReg = 0; 00177 ScavengedRC = NULL; 00178 ScavengeRestore = NULL; 00179 } 00180 00181 // Find out which registers are early clobbered, killed, defined, and marked 00182 // def-dead in this instruction. 00183 BitVector EarlyClobberRegs(NumPhysRegs); 00184 BitVector KillRegs(NumPhysRegs); 00185 BitVector DefRegs(NumPhysRegs); 00186 BitVector DeadRegs(NumPhysRegs); 00187 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 00188 const MachineOperand &MO = MI->getOperand(i); 00189 if (!MO.isReg() || MO.isUndef()) 00190 continue; 00191 unsigned Reg = MO.getReg(); 00192 if (!Reg || isReserved(Reg)) 00193 continue; 00194 00195 if (MO.isUse()) { 00196 // Two-address operands implicitly kill. 00197 if (MO.isKill() || MI->isRegTiedToDefOperand(i)) 00198 addRegWithSubRegs(KillRegs, Reg); 00199 } else { 00200 assert(MO.isDef()); 00201 if (MO.isDead()) 00202 addRegWithSubRegs(DeadRegs, Reg); 00203 else 00204 addRegWithSubRegs(DefRegs, Reg); 00205 if (MO.isEarlyClobber()) 00206 addRegWithAliases(EarlyClobberRegs, Reg); 00207 } 00208 } 00209 00210 // Verify uses and defs. 00211 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 00212 const MachineOperand &MO = MI->getOperand(i); 00213 if (!MO.isReg() || MO.isUndef()) 00214 continue; 00215 unsigned Reg = MO.getReg(); 00216 if (!Reg || isReserved(Reg)) 00217 continue; 00218 if (MO.isUse()) { 00219 assert(isUsed(Reg) && "Using an undefined register!"); 00220 assert((!EarlyClobberRegs.test(Reg) || MI->isRegTiedToDefOperand(i)) && 00221 "Using an early clobbered register!"); 00222 } else { 00223 assert(MO.isDef()); 00224 assert((KillRegs.test(Reg) || isUnused(Reg) || 00225 isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) && 00226 "Re-defining a live register!"); 00227 } 00228 } 00229 00230 // Commit the changes. 00231 setUnused(KillRegs); 00232 setUnused(DeadRegs); 00233 setUsed(DefRegs); 00234 } 00235 00236 void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) { 00237 if (includeReserved) 00238 used = ~RegsAvailable; 00239 else 00240 used = ~RegsAvailable & ~ReservedRegs; 00241 } 00242 00243 /// CreateRegClassMask - Set the bits that represent the registers in the 00244 /// TargetRegisterClass. 00245 static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) { 00246 for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E; 00247 ++I) 00248 Mask.set(*I); 00249 } 00250 00251 unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const { 00252 for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); 00253 I != E; ++I) 00254 if (!isAliasUsed(*I)) 00255 return *I; 00256 return 0; 00257 } 00258 00259 /// findSurvivorReg - Return the candidate register that is unused for the 00260 /// longest after MBBI. UseMI is set to the instruction where the search 00261 /// stopped. 00262 /// 00263 /// No more than InstrLimit instructions are inspected. 00264 /// 00265 unsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator MI, 00266 BitVector &Candidates, 00267 unsigned InstrLimit, 00268 MachineBasicBlock::iterator &UseMI) { 00269 int Survivor = Candidates.find_first(); 00270 assert(Survivor > 0 && "No candidates for scavenging"); 00271 00272 MachineBasicBlock::iterator ME = MBB->getFirstTerminator(); 00273 assert(MI != ME && "MI already at terminator"); 00274 00275 for (++MI; InstrLimit > 0 && MI != ME; ++MI, --InstrLimit) { 00276 // Remove any candidates touched by instruction. 00277 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 00278 const MachineOperand &MO = MI->getOperand(i); 00279 if (!MO.isReg() || MO.isUndef() || !MO.getReg()) 00280 continue; 00281 Candidates.reset(MO.getReg()); 00282 for (const unsigned *R = TRI->getAliasSet(MO.getReg()); *R; R++) 00283 Candidates.reset(*R); 00284 } 00285 00286 // Was our survivor untouched by this instruction? 00287 if (Candidates.test(Survivor)) 00288 continue; 00289 00290 // All candidates gone? 00291 if (Candidates.none()) 00292 break; 00293 00294 Survivor = Candidates.find_first(); 00295 } 00296 00297 // We ran out of candidates, so stop the search. 00298 UseMI = MI; 00299 return Survivor; 00300 } 00301 00302 unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, 00303 MachineBasicBlock::iterator I, 00304 int SPAdj) { 00305 assert(ScavengingFrameIndex >= 0 && 00306 "Cannot scavenge a register without an emergency spill slot!"); 00307 00308 // Mask off the registers which are not in the TargetRegisterClass. 00309 BitVector Candidates(NumPhysRegs, false); 00310 CreateRegClassMask(RC, Candidates); 00311 // Do not include reserved registers. 00312 Candidates ^= ReservedRegs & Candidates; 00313 00314 // Exclude all the registers being used by the instruction. 00315 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 00316 MachineOperand &MO = I->getOperand(i); 00317 if (MO.isReg()) 00318 Candidates.reset(MO.getReg()); 00319 } 00320 00321 // Find the register whose use is furthest away. 00322 MachineBasicBlock::iterator UseMI; 00323 unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI); 00324 00325 // If we found an unused register there is no reason to spill it. We have 00326 // probably found a callee-saved register that has been saved in the 00327 // prologue, but happens to be unused at this point. 00328 if (!isAliasUsed(SReg)) 00329 return SReg; 00330 00331 assert(ScavengedReg == 0 && 00332 "Scavenger slot is live, unable to scavenge another register!"); 00333 00334 // Avoid infinite regress 00335 ScavengedReg = SReg; 00336 00337 // Spill the scavenged register before I. 00338 TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC); 00339 MachineBasicBlock::iterator II = prior(I); 00340 TRI->eliminateFrameIndex(II, SPAdj, this); 00341 00342 // Restore the scavenged register before its use (or first terminator). 00343 TII->loadRegFromStackSlot(*MBB, UseMI, SReg, ScavengingFrameIndex, RC); 00344 ScavengeRestore = prior(UseMI); 00345 // Doing this here leads to infinite regress. 00346 // ScavengedReg = SReg; 00347 ScavengedRC = RC; 00348 00349 return SReg; 00350 }