LLVM API Documentation

Spiller.cpp

Go to the documentation of this file.
00001 //===-- llvm/CodeGen/Spiller.cpp -  Spiller -------------------------------===//
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 #define DEBUG_TYPE "spiller"
00011 
00012 #include "Spiller.h"
00013 #include "VirtRegMap.h"
00014 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
00015 #include "llvm/CodeGen/LiveStackAnalysis.h"
00016 #include "llvm/CodeGen/MachineFunction.h"
00017 #include "llvm/CodeGen/MachineRegisterInfo.h"
00018 #include "llvm/CodeGen/MachineFrameInfo.h"
00019 #include "llvm/Target/TargetMachine.h"
00020 #include "llvm/Target/TargetInstrInfo.h"
00021 #include "llvm/Support/Debug.h"
00022 
00023 using namespace llvm;
00024 
00025 Spiller::~Spiller() {}
00026 
00027 namespace {
00028 
00029 /// Utility class for spillers.
00030 class SpillerBase : public Spiller {
00031 protected:
00032 
00033   MachineFunction *mf;
00034   LiveIntervals *lis;
00035   LiveStacks *ls;
00036   MachineFrameInfo *mfi;
00037   MachineRegisterInfo *mri;
00038   const TargetInstrInfo *tii;
00039   VirtRegMap *vrm;
00040   
00041   /// Construct a spiller base. 
00042   SpillerBase(MachineFunction *mf, LiveIntervals *lis, LiveStacks *ls,
00043               VirtRegMap *vrm) :
00044     mf(mf), lis(lis), ls(ls), vrm(vrm)
00045   {
00046     mfi = mf->getFrameInfo();
00047     mri = &mf->getRegInfo();
00048     tii = mf->getTarget().getInstrInfo();
00049   }
00050 
00051   /// Ensures there is space before the given machine instruction, returns the
00052   /// instruction's new number.
00053   unsigned makeSpaceBefore(MachineInstr *mi) {
00054     if (!lis->hasGapBeforeInstr(lis->getInstructionIndex(mi))) {
00055       lis->scaleNumbering(2);
00056       ls->scaleNumbering(2);
00057     }
00058 
00059     unsigned miIdx = lis->getInstructionIndex(mi);
00060 
00061     assert(lis->hasGapBeforeInstr(miIdx));
00062     
00063     return miIdx;
00064   }
00065 
00066   /// Ensure there is space after the given machine instruction, returns the
00067   /// instruction's new number.
00068   unsigned makeSpaceAfter(MachineInstr *mi) {
00069     if (!lis->hasGapAfterInstr(lis->getInstructionIndex(mi))) {
00070       lis->scaleNumbering(2);
00071       ls->scaleNumbering(2);
00072     }
00073 
00074     unsigned miIdx = lis->getInstructionIndex(mi);
00075 
00076     assert(lis->hasGapAfterInstr(miIdx));
00077 
00078     return miIdx;
00079   }  
00080 
00081   /// Insert a store of the given vreg to the given stack slot immediately
00082   /// after the given instruction. Returns the base index of the inserted
00083   /// instruction. The caller is responsible for adding an appropriate
00084   /// LiveInterval to the LiveIntervals analysis.
00085   unsigned insertStoreAfter(MachineInstr *mi, unsigned ss,
00086                           unsigned vreg,
00087                           const TargetRegisterClass *trc) {
00088 
00089     MachineBasicBlock::iterator nextInstItr(next(mi)); 
00090 
00091     unsigned miIdx = makeSpaceAfter(mi);
00092 
00093     tii->storeRegToStackSlot(*mi->getParent(), nextInstItr, vreg,
00094                              true, ss, trc);
00095     MachineBasicBlock::iterator storeInstItr(next(mi));
00096     MachineInstr *storeInst = &*storeInstItr;
00097     unsigned storeInstIdx = miIdx + LiveInterval::InstrSlots::NUM;
00098 
00099     assert(lis->getInstructionFromIndex(storeInstIdx) == 0 &&
00100            "Store inst index already in use.");
00101     
00102     lis->InsertMachineInstrInMaps(storeInst, storeInstIdx);
00103 
00104     return storeInstIdx;
00105   }
00106 
00107   /// Insert a store of the given vreg to the given stack slot immediately
00108   /// before the given instructnion. Returns the base index of the inserted
00109   /// Instruction.
00110   unsigned insertStoreBefore(MachineInstr *mi, unsigned ss,
00111                             unsigned vreg,
00112                             const TargetRegisterClass *trc) {
00113     unsigned miIdx = makeSpaceBefore(mi);
00114   
00115     tii->storeRegToStackSlot(*mi->getParent(), mi, vreg, true, ss, trc);
00116     MachineBasicBlock::iterator storeInstItr(prior(mi));
00117     MachineInstr *storeInst = &*storeInstItr;
00118     unsigned storeInstIdx = miIdx - LiveInterval::InstrSlots::NUM;
00119 
00120     assert(lis->getInstructionFromIndex(storeInstIdx) == 0 &&
00121            "Store inst index already in use.");
00122 
00123     lis->InsertMachineInstrInMaps(storeInst, storeInstIdx);
00124 
00125     return storeInstIdx;
00126   }
00127 
00128   void insertStoreAfterInstOnInterval(LiveInterval *li,
00129                                       MachineInstr *mi, unsigned ss,
00130                                       unsigned vreg,
00131                                       const TargetRegisterClass *trc) {
00132 
00133     unsigned storeInstIdx = insertStoreAfter(mi, ss, vreg, trc);
00134     unsigned start = lis->getDefIndex(lis->getInstructionIndex(mi)),
00135              end = lis->getUseIndex(storeInstIdx);
00136 
00137     VNInfo *vni =
00138       li->getNextValue(storeInstIdx, 0, true, lis->getVNInfoAllocator());
00139     li->addKill(vni, storeInstIdx, false);
00140     DOUT << "    Inserting store range: [" << start << ", " << end << ")\n";
00141     LiveRange lr(start, end, vni);
00142       
00143     li->addRange(lr);
00144   }
00145 
00146   /// Insert a load of the given vreg from the given stack slot immediately
00147   /// after the given instruction. Returns the base index of the inserted
00148   /// instruction. The caller is responsibel for adding/removing an appropriate
00149   /// range vreg's LiveInterval.
00150   unsigned insertLoadAfter(MachineInstr *mi, unsigned ss,
00151                           unsigned vreg,
00152                           const TargetRegisterClass *trc) {
00153 
00154     MachineBasicBlock::iterator nextInstItr(next(mi)); 
00155 
00156     unsigned miIdx = makeSpaceAfter(mi);
00157 
00158     tii->loadRegFromStackSlot(*mi->getParent(), nextInstItr, vreg, ss, trc);
00159     MachineBasicBlock::iterator loadInstItr(next(mi));
00160     MachineInstr *loadInst = &*loadInstItr;
00161     unsigned loadInstIdx = miIdx + LiveInterval::InstrSlots::NUM;
00162 
00163     assert(lis->getInstructionFromIndex(loadInstIdx) == 0 &&
00164            "Store inst index already in use.");
00165     
00166     lis->InsertMachineInstrInMaps(loadInst, loadInstIdx);
00167 
00168     return loadInstIdx;
00169   }
00170 
00171   /// Insert a load of the given vreg from the given stack slot immediately
00172   /// before the given instruction. Returns the base index of the inserted
00173   /// instruction. The caller is responsible for adding an appropriate
00174   /// LiveInterval to the LiveIntervals analysis.
00175   unsigned insertLoadBefore(MachineInstr *mi, unsigned ss,
00176                             unsigned vreg,
00177                             const TargetRegisterClass *trc) {  
00178     unsigned miIdx = makeSpaceBefore(mi);
00179   
00180     tii->loadRegFromStackSlot(*mi->getParent(), mi, vreg, ss, trc);
00181     MachineBasicBlock::iterator loadInstItr(prior(mi));
00182     MachineInstr *loadInst = &*loadInstItr;
00183     unsigned loadInstIdx = miIdx - LiveInterval::InstrSlots::NUM;
00184 
00185     assert(lis->getInstructionFromIndex(loadInstIdx) == 0 &&
00186            "Load inst index already in use.");
00187 
00188     lis->InsertMachineInstrInMaps(loadInst, loadInstIdx);
00189 
00190     return loadInstIdx;
00191   }
00192 
00193   void insertLoadBeforeInstOnInterval(LiveInterval *li,
00194                                       MachineInstr *mi, unsigned ss, 
00195                                       unsigned vreg,
00196                                       const TargetRegisterClass *trc) {
00197 
00198     unsigned loadInstIdx = insertLoadBefore(mi, ss, vreg, trc);
00199     unsigned start = lis->getDefIndex(loadInstIdx),
00200              end = lis->getUseIndex(lis->getInstructionIndex(mi));
00201 
00202     VNInfo *vni =
00203       li->getNextValue(loadInstIdx, 0, true, lis->getVNInfoAllocator());
00204     li->addKill(vni, lis->getInstructionIndex(mi), false);
00205     DOUT << "    Intserting load range: [" << start << ", " << end << ")\n";
00206     LiveRange lr(start, end, vni);
00207 
00208     li->addRange(lr);
00209   }
00210 
00211 
00212 
00213   /// Add spill ranges for every use/def of the live interval, inserting loads
00214   /// immediately before each use, and stores after each def. No folding is
00215   /// attempted.
00216   std::vector<LiveInterval*> trivialSpillEverywhere(LiveInterval *li) {
00217     DOUT << "Spilling everywhere " << *li << "\n";
00218 
00219     assert(li->weight != HUGE_VALF &&
00220            "Attempting to spill already spilled value.");
00221 
00222     assert(!li->isStackSlot() &&
00223            "Trying to spill a stack slot.");
00224 
00225     DOUT << "Trivial spill everywhere of reg" << li->reg << "\n";
00226 
00227     std::vector<LiveInterval*> added;
00228     
00229     const TargetRegisterClass *trc = mri->getRegClass(li->reg);
00230     unsigned ss = vrm->assignVirt2StackSlot(li->reg);
00231 
00232     for (MachineRegisterInfo::reg_iterator
00233          regItr = mri->reg_begin(li->reg); regItr != mri->reg_end();) {
00234 
00235       MachineInstr *mi = &*regItr;
00236 
00237       DOUT << "  Processing " << *mi;
00238 
00239       do {
00240         ++regItr;
00241       } while (regItr != mri->reg_end() && (&*regItr == mi));
00242       
00243       SmallVector<unsigned, 2> indices;
00244       bool hasUse = false;
00245       bool hasDef = false;
00246     
00247       for (unsigned i = 0; i != mi->getNumOperands(); ++i) {
00248         MachineOperand &op = mi->getOperand(i);
00249 
00250         if (!op.isReg() || op.getReg() != li->reg)
00251           continue;
00252       
00253         hasUse |= mi->getOperand(i).isUse();
00254         hasDef |= mi->getOperand(i).isDef();
00255       
00256         indices.push_back(i);
00257       }
00258 
00259       unsigned newVReg = mri->createVirtualRegister(trc);
00260       vrm->grow();
00261       vrm->assignVirt2StackSlot(newVReg, ss);
00262 
00263       LiveInterval *newLI = &lis->getOrCreateInterval(newVReg);
00264       newLI->weight = HUGE_VALF;
00265       
00266       for (unsigned i = 0; i < indices.size(); ++i) {
00267         mi->getOperand(indices[i]).setReg(newVReg);
00268 
00269         if (mi->getOperand(indices[i]).isUse()) {
00270           mi->getOperand(indices[i]).setIsKill(true);
00271         }
00272       }
00273 
00274       assert(hasUse || hasDef);
00275 
00276       if (hasUse) {
00277         insertLoadBeforeInstOnInterval(newLI, mi, ss, newVReg, trc);
00278       }
00279 
00280       if (hasDef) {
00281         insertStoreAfterInstOnInterval(newLI, mi, ss, newVReg, trc);
00282       }
00283 
00284       added.push_back(newLI);
00285     }
00286 
00287     return added;
00288   }
00289 
00290 };
00291 
00292 
00293 /// Spills any live range using the spill-everywhere method with no attempt at
00294 /// folding.
00295 class TrivialSpiller : public SpillerBase {
00296 public:
00297 
00298   TrivialSpiller(MachineFunction *mf, LiveIntervals *lis, LiveStacks *ls,
00299                  VirtRegMap *vrm) :
00300     SpillerBase(mf, lis, ls, vrm) {}
00301 
00302   std::vector<LiveInterval*> spill(LiveInterval *li) {
00303     return trivialSpillEverywhere(li);
00304   }
00305 
00306   std::vector<LiveInterval*> intraBlockSplit(LiveInterval *li, VNInfo *valno)  {
00307     std::vector<LiveInterval*> spillIntervals;
00308 
00309     if (!valno->isDefAccurate() && !valno->isPHIDef()) {
00310       // Early out for values which have no well defined def point.
00311       return spillIntervals;
00312     }
00313 
00314     // Ok.. we should be able to proceed...
00315     const TargetRegisterClass *trc = mri->getRegClass(li->reg);
00316     unsigned ss = vrm->assignVirt2StackSlot(li->reg);    
00317     vrm->grow();
00318     vrm->assignVirt2StackSlot(li->reg, ss);
00319 
00320     MachineInstr *mi = 0;
00321     unsigned storeIdx = 0;
00322 
00323     if (valno->isDefAccurate()) {
00324       // If we have an accurate def we can just grab an iterator to the instr
00325       // after the def.
00326       mi = lis->getInstructionFromIndex(valno->def);
00327       storeIdx = insertStoreAfter(mi, ss, li->reg, trc) +
00328         LiveInterval::InstrSlots::DEF;
00329     } else {
00330       // if we get here we have a PHI def.
00331       mi = &lis->getMBBFromIndex(valno->def)->front();
00332       storeIdx = insertStoreBefore(mi, ss, li->reg, trc) +
00333         LiveInterval::InstrSlots::DEF;
00334     }
00335 
00336     MachineBasicBlock *defBlock = mi->getParent();
00337     unsigned loadIdx = 0;
00338 
00339     // Now we need to find the load...
00340     MachineBasicBlock::iterator useItr(mi);
00341     for (; !useItr->readsRegister(li->reg); ++useItr) {}
00342 
00343     if (useItr != defBlock->end()) {
00344       MachineInstr *loadInst = useItr;
00345       loadIdx = insertLoadBefore(loadInst, ss, li->reg, trc) +
00346         LiveInterval::InstrSlots::USE;
00347     }
00348     else {
00349       MachineInstr *loadInst = &defBlock->back();
00350       loadIdx = insertLoadAfter(loadInst, ss, li->reg, trc) +
00351         LiveInterval::InstrSlots::USE;
00352     }
00353 
00354     li->removeRange(storeIdx, loadIdx, true);
00355 
00356     return spillIntervals;
00357   }
00358 
00359 };
00360 
00361 }
00362 
00363 llvm::Spiller* llvm::createSpiller(MachineFunction *mf, LiveIntervals *lis,
00364                                    LiveStacks *ls, VirtRegMap *vrm) {
00365   return new TrivialSpiller(mf, lis, ls, vrm);
00366 }