LLVM API Documentation

RegisterScavenging.cpp

Go to the documentation of this file.
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 }