LLVM API Documentation

LiveIntervalAnalysis.h

Go to the documentation of this file.
00001 //===-- LiveIntervalAnalysis.h - Live Interval Analysis ---------*- C++ -*-===//
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 LiveInterval analysis pass.  Given some numbering of
00011 // each the machine instructions (in this implemention depth-first order) an
00012 // interval [i, j) is said to be a live interval for register v if there is no
00013 // instruction with number j' > j such that v is live at j' and there is no
00014 // instruction with number i' < i such that v is live at i'. In this
00015 // implementation intervals can have holes, i.e. an interval might look like
00016 // [1,20), [50,65), [1000,1001).
00017 //
00018 //===----------------------------------------------------------------------===//
00019 
00020 #ifndef LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H
00021 #define LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H
00022 
00023 #include "llvm/CodeGen/MachineBasicBlock.h"
00024 #include "llvm/CodeGen/MachineFunctionPass.h"
00025 #include "llvm/CodeGen/LiveInterval.h"
00026 #include "llvm/ADT/BitVector.h"
00027 #include "llvm/ADT/DenseMap.h"
00028 #include "llvm/ADT/SmallPtrSet.h"
00029 #include "llvm/ADT/SmallVector.h"
00030 #include "llvm/Support/Allocator.h"
00031 #include <cmath>
00032 
00033 namespace llvm {
00034 
00035   class AliasAnalysis;
00036   class LiveVariables;
00037   class MachineLoopInfo;
00038   class TargetRegisterInfo;
00039   class MachineRegisterInfo;
00040   class TargetInstrInfo;
00041   class TargetRegisterClass;
00042   class VirtRegMap;
00043   typedef std::pair<unsigned, MachineBasicBlock*> IdxMBBPair;
00044 
00045   inline bool operator<(unsigned V, const IdxMBBPair &IM) {
00046     return V < IM.first;
00047   }
00048 
00049   inline bool operator<(const IdxMBBPair &IM, unsigned V) {
00050     return IM.first < V;
00051   }
00052 
00053   struct Idx2MBBCompare {
00054     bool operator()(const IdxMBBPair &LHS, const IdxMBBPair &RHS) const {
00055       return LHS.first < RHS.first;
00056     }
00057   };
00058   
00059   class LiveIntervals : public MachineFunctionPass {
00060     MachineFunction* mf_;
00061     MachineRegisterInfo* mri_;
00062     const TargetMachine* tm_;
00063     const TargetRegisterInfo* tri_;
00064     const TargetInstrInfo* tii_;
00065     AliasAnalysis *aa_;
00066     LiveVariables* lv_;
00067 
00068     /// Special pool allocator for VNInfo's (LiveInterval val#).
00069     ///
00070     BumpPtrAllocator VNInfoAllocator;
00071 
00072     /// MBB2IdxMap - The indexes of the first and last instructions in the
00073     /// specified basic block.
00074     std::vector<std::pair<unsigned, unsigned> > MBB2IdxMap;
00075 
00076     /// Idx2MBBMap - Sorted list of pairs of index of first instruction
00077     /// and MBB id.
00078     std::vector<IdxMBBPair> Idx2MBBMap;
00079 
00080     /// FunctionSize - The number of instructions present in the function
00081     uint64_t FunctionSize;
00082 
00083     typedef DenseMap<const MachineInstr*, unsigned> Mi2IndexMap;
00084     Mi2IndexMap mi2iMap_;
00085 
00086     typedef std::vector<MachineInstr*> Index2MiMap;
00087     Index2MiMap i2miMap_;
00088 
00089     typedef DenseMap<unsigned, LiveInterval*> Reg2IntervalMap;
00090     Reg2IntervalMap r2iMap_;
00091 
00092     DenseMap<MachineBasicBlock*, unsigned> terminatorGaps;
00093 
00094     BitVector allocatableRegs_;
00095 
00096     std::vector<MachineInstr*> ClonedMIs;
00097 
00098     typedef LiveInterval::InstrSlots InstrSlots;
00099 
00100   public:
00101     static char ID; // Pass identification, replacement for typeid
00102     LiveIntervals() : MachineFunctionPass(&ID) {}
00103 
00104     static unsigned getBaseIndex(unsigned index) {
00105       return index - (index % InstrSlots::NUM);
00106     }
00107     static unsigned getBoundaryIndex(unsigned index) {
00108       return getBaseIndex(index + InstrSlots::NUM - 1);
00109     }
00110     static unsigned getLoadIndex(unsigned index) {
00111       return getBaseIndex(index) + InstrSlots::LOAD;
00112     }
00113     static unsigned getUseIndex(unsigned index) {
00114       return getBaseIndex(index) + InstrSlots::USE;
00115     }
00116     static unsigned getDefIndex(unsigned index) {
00117       return getBaseIndex(index) + InstrSlots::DEF;
00118     }
00119     static unsigned getStoreIndex(unsigned index) {
00120       return getBaseIndex(index) + InstrSlots::STORE;
00121     }
00122 
00123     static float getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) {
00124       return (isDef + isUse) * powf(10.0F, (float)loopDepth);
00125     }
00126 
00127     typedef Reg2IntervalMap::iterator iterator;
00128     typedef Reg2IntervalMap::const_iterator const_iterator;
00129     const_iterator begin() const { return r2iMap_.begin(); }
00130     const_iterator end() const { return r2iMap_.end(); }
00131     iterator begin() { return r2iMap_.begin(); }
00132     iterator end() { return r2iMap_.end(); }
00133     unsigned getNumIntervals() const { return (unsigned)r2iMap_.size(); }
00134 
00135     LiveInterval &getInterval(unsigned reg) {
00136       Reg2IntervalMap::iterator I = r2iMap_.find(reg);
00137       assert(I != r2iMap_.end() && "Interval does not exist for register");
00138       return *I->second;
00139     }
00140 
00141     const LiveInterval &getInterval(unsigned reg) const {
00142       Reg2IntervalMap::const_iterator I = r2iMap_.find(reg);
00143       assert(I != r2iMap_.end() && "Interval does not exist for register");
00144       return *I->second;
00145     }
00146 
00147     bool hasInterval(unsigned reg) const {
00148       return r2iMap_.count(reg);
00149     }
00150 
00151     /// getMBBStartIdx - Return the base index of the first instruction in the
00152     /// specified MachineBasicBlock.
00153     unsigned getMBBStartIdx(MachineBasicBlock *MBB) const {
00154       return getMBBStartIdx(MBB->getNumber());
00155     }
00156     unsigned getMBBStartIdx(unsigned MBBNo) const {
00157       assert(MBBNo < MBB2IdxMap.size() && "Invalid MBB number!");
00158       return MBB2IdxMap[MBBNo].first;
00159     }
00160 
00161     /// getMBBEndIdx - Return the store index of the last instruction in the
00162     /// specified MachineBasicBlock.
00163     unsigned getMBBEndIdx(MachineBasicBlock *MBB) const {
00164       return getMBBEndIdx(MBB->getNumber());
00165     }
00166     unsigned getMBBEndIdx(unsigned MBBNo) const {
00167       assert(MBBNo < MBB2IdxMap.size() && "Invalid MBB number!");
00168       return MBB2IdxMap[MBBNo].second;
00169     }
00170 
00171     /// getScaledIntervalSize - get the size of an interval in "units,"
00172     /// where every function is composed of one thousand units.  This
00173     /// measure scales properly with empty index slots in the function.
00174     double getScaledIntervalSize(LiveInterval& I) {
00175       return (1000.0 / InstrSlots::NUM * I.getSize()) / i2miMap_.size();
00176     }
00177     
00178     /// getApproximateInstructionCount - computes an estimate of the number
00179     /// of instructions in a given LiveInterval.
00180     unsigned getApproximateInstructionCount(LiveInterval& I) {
00181       double IntervalPercentage = getScaledIntervalSize(I) / 1000.0;
00182       return (unsigned)(IntervalPercentage * FunctionSize);
00183     }
00184 
00185     /// getMBBFromIndex - given an index in any instruction of an
00186     /// MBB return a pointer the MBB
00187     MachineBasicBlock* getMBBFromIndex(unsigned index) const {
00188       std::vector<IdxMBBPair>::const_iterator I =
00189         std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), index);
00190       // Take the pair containing the index
00191       std::vector<IdxMBBPair>::const_iterator J =
00192         ((I != Idx2MBBMap.end() && I->first > index) ||
00193          (I == Idx2MBBMap.end() && Idx2MBBMap.size()>0)) ? (I-1): I;
00194 
00195       assert(J != Idx2MBBMap.end() && J->first < index+1 &&
00196              index <= getMBBEndIdx(J->second) &&
00197              "index does not correspond to an MBB");
00198       return J->second;
00199     }
00200 
00201     /// getInstructionIndex - returns the base index of instr
00202     unsigned getInstructionIndex(const MachineInstr* instr) const {
00203       Mi2IndexMap::const_iterator it = mi2iMap_.find(instr);
00204       assert(it != mi2iMap_.end() && "Invalid instruction!");
00205       return it->second;
00206     }
00207 
00208     /// getInstructionFromIndex - given an index in any slot of an
00209     /// instruction return a pointer the instruction
00210     MachineInstr* getInstructionFromIndex(unsigned index) const {
00211       index /= InstrSlots::NUM; // convert index to vector index
00212       assert(index < i2miMap_.size() &&
00213              "index does not correspond to an instruction");
00214       return i2miMap_[index];
00215     }
00216 
00217     /// hasGapBeforeInstr - Return true if the previous instruction slot,
00218     /// i.e. Index - InstrSlots::NUM, is not occupied.
00219     bool hasGapBeforeInstr(unsigned Index) {
00220       Index = getBaseIndex(Index - InstrSlots::NUM);
00221       return getInstructionFromIndex(Index) == 0;
00222     }
00223 
00224     /// hasGapAfterInstr - Return true if the successive instruction slot,
00225     /// i.e. Index + InstrSlots::Num, is not occupied.
00226     bool hasGapAfterInstr(unsigned Index) {
00227       Index = getBaseIndex(Index + InstrSlots::NUM);
00228       return getInstructionFromIndex(Index) == 0;
00229     }
00230 
00231     /// findGapBeforeInstr - Find an empty instruction slot before the
00232     /// specified index. If "Furthest" is true, find one that's furthest
00233     /// away from the index (but before any index that's occupied).
00234     unsigned findGapBeforeInstr(unsigned Index, bool Furthest = false) {
00235       Index = getBaseIndex(Index - InstrSlots::NUM);
00236       if (getInstructionFromIndex(Index))
00237         return 0;  // No gap!
00238       if (!Furthest)
00239         return Index;
00240       unsigned PrevIndex = getBaseIndex(Index - InstrSlots::NUM);
00241       while (getInstructionFromIndex(Index)) {
00242         Index = PrevIndex;
00243         PrevIndex = getBaseIndex(Index - InstrSlots::NUM);
00244       }
00245       return Index;
00246     }
00247 
00248     /// InsertMachineInstrInMaps - Insert the specified machine instruction
00249     /// into the instruction index map at the given index.
00250     void InsertMachineInstrInMaps(MachineInstr *MI, unsigned Index) {
00251       i2miMap_[Index / InstrSlots::NUM] = MI;
00252       Mi2IndexMap::iterator it = mi2iMap_.find(MI);
00253       assert(it == mi2iMap_.end() && "Already in map!");
00254       mi2iMap_[MI] = Index;
00255     }
00256 
00257     /// conflictsWithPhysRegDef - Returns true if the specified register
00258     /// is defined during the duration of the specified interval.
00259     bool conflictsWithPhysRegDef(const LiveInterval &li, VirtRegMap &vrm,
00260                                  unsigned reg);
00261 
00262     /// conflictsWithPhysRegRef - Similar to conflictsWithPhysRegRef except
00263     /// it can check use as well.
00264     bool conflictsWithPhysRegRef(LiveInterval &li, unsigned Reg,
00265                                  bool CheckUse,
00266                                  SmallPtrSet<MachineInstr*,32> &JoinedCopies);
00267 
00268     /// findLiveInMBBs - Given a live range, if the value of the range
00269     /// is live in any MBB returns true as well as the list of basic blocks
00270     /// in which the value is live.
00271     bool findLiveInMBBs(unsigned Start, unsigned End,
00272                         SmallVectorImpl<MachineBasicBlock*> &MBBs) const;
00273 
00274     /// findReachableMBBs - Return a list MBB that can be reached via any
00275     /// branch or fallthroughs. Return true if the list is not empty.
00276     bool findReachableMBBs(unsigned Start, unsigned End,
00277                         SmallVectorImpl<MachineBasicBlock*> &MBBs) const;
00278 
00279     // Interval creation
00280 
00281     LiveInterval &getOrCreateInterval(unsigned reg) {
00282       Reg2IntervalMap::iterator I = r2iMap_.find(reg);
00283       if (I == r2iMap_.end())
00284         I = r2iMap_.insert(std::make_pair(reg, createInterval(reg))).first;
00285       return *I->second;
00286     }
00287 
00288     /// dupInterval - Duplicate a live interval. The caller is responsible for
00289     /// managing the allocated memory.
00290     LiveInterval *dupInterval(LiveInterval *li);
00291     
00292     /// addLiveRangeToEndOfBlock - Given a register and an instruction,
00293     /// adds a live range from that instruction to the end of its MBB.
00294     LiveRange addLiveRangeToEndOfBlock(unsigned reg,
00295                                         MachineInstr* startInst);
00296 
00297     // Interval removal
00298 
00299     void removeInterval(unsigned Reg) {
00300       DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.find(Reg);
00301       delete I->second;
00302       r2iMap_.erase(I);
00303     }
00304 
00305     /// isNotInMIMap - returns true if the specified machine instr has been
00306     /// removed or was never entered in the map.
00307     bool isNotInMIMap(MachineInstr* instr) const {
00308       return !mi2iMap_.count(instr);
00309     }
00310 
00311     /// RemoveMachineInstrFromMaps - This marks the specified machine instr as
00312     /// deleted.
00313     void RemoveMachineInstrFromMaps(MachineInstr *MI) {
00314       // remove index -> MachineInstr and
00315       // MachineInstr -> index mappings
00316       Mi2IndexMap::iterator mi2i = mi2iMap_.find(MI);
00317       if (mi2i != mi2iMap_.end()) {
00318         i2miMap_[mi2i->second/InstrSlots::NUM] = 0;
00319         mi2iMap_.erase(mi2i);
00320       }
00321     }
00322 
00323     /// ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in
00324     /// maps used by register allocator.
00325     void ReplaceMachineInstrInMaps(MachineInstr *MI, MachineInstr *NewMI) {
00326       Mi2IndexMap::iterator mi2i = mi2iMap_.find(MI);
00327       if (mi2i == mi2iMap_.end())
00328         return;
00329       i2miMap_[mi2i->second/InstrSlots::NUM] = NewMI;
00330       Mi2IndexMap::iterator it = mi2iMap_.find(MI);
00331       assert(it != mi2iMap_.end() && "Invalid instruction!");
00332       unsigned Index = it->second;
00333       mi2iMap_.erase(it);
00334       mi2iMap_[NewMI] = Index;
00335     }
00336 
00337     BumpPtrAllocator& getVNInfoAllocator() { return VNInfoAllocator; }
00338 
00339     /// getVNInfoSourceReg - Helper function that parses the specified VNInfo
00340     /// copy field and returns the source register that defines it.
00341     unsigned getVNInfoSourceReg(const VNInfo *VNI) const;
00342 
00343     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
00344     virtual void releaseMemory();
00345 
00346     /// runOnMachineFunction - pass entry point
00347     virtual bool runOnMachineFunction(MachineFunction&);
00348 
00349     /// print - Implement the dump method.
00350     virtual void print(std::ostream &O, const Module* = 0) const;
00351     void print(std::ostream *O, const Module* M = 0) const {
00352       if (O) print(*O, M);
00353     }
00354 
00355     /// addIntervalsForSpills - Create new intervals for spilled defs / uses of
00356     /// the given interval. FIXME: It also returns the weight of the spill slot
00357     /// (if any is created) by reference. This is temporary.
00358     std::vector<LiveInterval*>
00359     addIntervalsForSpills(const LiveInterval& i,
00360                           SmallVectorImpl<LiveInterval*> &SpillIs,
00361                           const MachineLoopInfo *loopInfo, VirtRegMap& vrm);
00362     
00363     /// addIntervalsForSpillsFast - Quickly create new intervals for spilled
00364     /// defs / uses without remat or splitting.
00365     std::vector<LiveInterval*>
00366     addIntervalsForSpillsFast(const LiveInterval &li,
00367                               const MachineLoopInfo *loopInfo, VirtRegMap &vrm);
00368 
00369     /// spillPhysRegAroundRegDefsUses - Spill the specified physical register
00370     /// around all defs and uses of the specified interval. Return true if it
00371     /// was able to cut its interval.
00372     bool spillPhysRegAroundRegDefsUses(const LiveInterval &li,
00373                                        unsigned PhysReg, VirtRegMap &vrm);
00374 
00375     /// isReMaterializable - Returns true if every definition of MI of every
00376     /// val# of the specified interval is re-materializable. Also returns true
00377     /// by reference if all of the defs are load instructions.
00378     bool isReMaterializable(const LiveInterval &li,
00379                             SmallVectorImpl<LiveInterval*> &SpillIs,
00380                             bool &isLoad);
00381 
00382     /// isReMaterializable - Returns true if the definition MI of the specified
00383     /// val# of the specified interval is re-materializable.
00384     bool isReMaterializable(const LiveInterval &li, const VNInfo *ValNo,
00385                             MachineInstr *MI);
00386 
00387     /// getRepresentativeReg - Find the largest super register of the specified
00388     /// physical register.
00389     unsigned getRepresentativeReg(unsigned Reg) const;
00390 
00391     /// getNumConflictsWithPhysReg - Return the number of uses and defs of the
00392     /// specified interval that conflicts with the specified physical register.
00393     unsigned getNumConflictsWithPhysReg(const LiveInterval &li,
00394                                         unsigned PhysReg) const;
00395 
00396     /// processImplicitDefs - Process IMPLICIT_DEF instructions. Add isUndef
00397     /// marker to implicit_def defs and their uses.
00398     void processImplicitDefs();
00399 
00400     /// computeNumbering - Compute the index numbering.
00401     void computeNumbering();
00402 
00403     /// scaleNumbering - Rescale interval numbers to introduce gaps for new
00404     /// instructions
00405     void scaleNumbering(int factor);
00406 
00407     /// intervalIsInOneMBB - Returns true if the specified interval is entirely
00408     /// within a single basic block.
00409     bool intervalIsInOneMBB(const LiveInterval &li) const;
00410 
00411   private:      
00412     /// computeIntervals - Compute live intervals.
00413     void computeIntervals();
00414     
00415     /// handleRegisterDef - update intervals for a register def
00416     /// (calls handlePhysicalRegisterDef and
00417     /// handleVirtualRegisterDef)
00418     void handleRegisterDef(MachineBasicBlock *MBB,
00419                            MachineBasicBlock::iterator MI, unsigned MIIdx,
00420                            MachineOperand& MO, unsigned MOIdx);
00421 
00422     /// handleVirtualRegisterDef - update intervals for a virtual
00423     /// register def
00424     void handleVirtualRegisterDef(MachineBasicBlock *MBB,
00425                                   MachineBasicBlock::iterator MI,
00426                                   unsigned MIIdx, MachineOperand& MO,
00427                                   unsigned MOIdx, LiveInterval& interval);
00428 
00429     /// handlePhysicalRegisterDef - update intervals for a physical register
00430     /// def.
00431     void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
00432                                    MachineBasicBlock::iterator mi,
00433                                    unsigned MIIdx, MachineOperand& MO,
00434                                    LiveInterval &interval,
00435                                    MachineInstr *CopyMI);
00436 
00437     /// handleLiveInRegister - Create interval for a livein register.
00438     void handleLiveInRegister(MachineBasicBlock* mbb,
00439                               unsigned MIIdx,
00440                               LiveInterval &interval, bool isAlias = false);
00441 
00442     /// getReMatImplicitUse - If the remat definition MI has one (for now, we
00443     /// only allow one) virtual register operand, then its uses are implicitly
00444     /// using the register. Returns the virtual register.
00445     unsigned getReMatImplicitUse(const LiveInterval &li,
00446                                  MachineInstr *MI) const;
00447 
00448     /// isValNoAvailableAt - Return true if the val# of the specified interval
00449     /// which reaches the given instruction also reaches the specified use
00450     /// index.
00451     bool isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI,
00452                             unsigned UseIdx) const;
00453 
00454     /// isReMaterializable - Returns true if the definition MI of the specified
00455     /// val# of the specified interval is re-materializable. Also returns true
00456     /// by reference if the def is a load.
00457     bool isReMaterializable(const LiveInterval &li, const VNInfo *ValNo,
00458                             MachineInstr *MI,
00459                             SmallVectorImpl<LiveInterval*> &SpillIs,
00460                             bool &isLoad);
00461 
00462     /// tryFoldMemoryOperand - Attempts to fold either a spill / restore from
00463     /// slot / to reg or any rematerialized load into ith operand of specified
00464     /// MI. If it is successul, MI is updated with the newly created MI and
00465     /// returns true.
00466     bool tryFoldMemoryOperand(MachineInstr* &MI, VirtRegMap &vrm,
00467                               MachineInstr *DefMI, unsigned InstrIdx,
00468                               SmallVector<unsigned, 2> &Ops,
00469                               bool isSS, int Slot, unsigned Reg);
00470 
00471     /// canFoldMemoryOperand - Return true if the specified load / store
00472     /// folding is possible.
00473     bool canFoldMemoryOperand(MachineInstr *MI,
00474                               SmallVector<unsigned, 2> &Ops,
00475                               bool ReMatLoadSS) const;
00476 
00477     /// anyKillInMBBAfterIdx - Returns true if there is a kill of the specified
00478     /// VNInfo that's after the specified index but is within the basic block.
00479     bool anyKillInMBBAfterIdx(const LiveInterval &li, const VNInfo *VNI,
00480                               MachineBasicBlock *MBB, unsigned Idx) const;
00481 
00482     /// hasAllocatableSuperReg - Return true if the specified physical register
00483     /// has any super register that's allocatable.
00484     bool hasAllocatableSuperReg(unsigned Reg) const;
00485 
00486     /// SRInfo - Spill / restore info.
00487     struct SRInfo {
00488       int index;
00489       unsigned vreg;
00490       bool canFold;
00491       SRInfo(int i, unsigned vr, bool f) : index(i), vreg(vr), canFold(f) {};
00492     };
00493 
00494     bool alsoFoldARestore(int Id, int index, unsigned vr,
00495                           BitVector &RestoreMBBs,
00496                           DenseMap<unsigned,std::vector<SRInfo> >&RestoreIdxes);
00497     void eraseRestoreInfo(int Id, int index, unsigned vr,
00498                           BitVector &RestoreMBBs,
00499                           DenseMap<unsigned,std::vector<SRInfo> >&RestoreIdxes);
00500 
00501     /// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being
00502     /// spilled and create empty intervals for their uses.
00503     void handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm,
00504                               const TargetRegisterClass* rc,
00505                               std::vector<LiveInterval*> &NewLIs);
00506 
00507     /// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of
00508     /// interval on to-be re-materialized operands of MI) with new register.
00509     void rewriteImplicitOps(const LiveInterval &li,
00510                            MachineInstr *MI, unsigned NewVReg, VirtRegMap &vrm);
00511 
00512     /// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper
00513     /// functions for addIntervalsForSpills to rewrite uses / defs for the given
00514     /// live range.
00515     bool rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
00516         bool TrySplit, unsigned index, unsigned end, MachineInstr *MI,
00517         MachineInstr *OrigDefMI, MachineInstr *DefMI, unsigned Slot, int LdSlot,
00518         bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
00519         VirtRegMap &vrm, const TargetRegisterClass* rc,
00520         SmallVector<int, 4> &ReMatIds, const MachineLoopInfo *loopInfo,
00521         unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse,
00522         DenseMap<unsigned,unsigned> &MBBVRegsMap,
00523         std::vector<LiveInterval*> &NewLIs);
00524     void rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
00525         LiveInterval::Ranges::const_iterator &I,
00526         MachineInstr *OrigDefMI, MachineInstr *DefMI, unsigned Slot, int LdSlot,
00527         bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
00528         VirtRegMap &vrm, const TargetRegisterClass* rc,
00529         SmallVector<int, 4> &ReMatIds, const MachineLoopInfo *loopInfo,
00530         BitVector &SpillMBBs,
00531         DenseMap<unsigned,std::vector<SRInfo> > &SpillIdxes,
00532         BitVector &RestoreMBBs,
00533         DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes,
00534         DenseMap<unsigned,unsigned> &MBBVRegsMap,
00535         std::vector<LiveInterval*> &NewLIs);
00536 
00537     static LiveInterval* createInterval(unsigned Reg);
00538 
00539     void printRegName(unsigned reg) const;
00540   };
00541 
00542   /// IntervalPrefixPrinter - Print live interval indices before each
00543   /// instruction.
00544   class IntervalPrefixPrinter : public PrefixPrinter {
00545   private:
00546     const LiveIntervals &liinfo;
00547 
00548   public:
00549     IntervalPrefixPrinter(const LiveIntervals &lii)
00550         : liinfo(lii) {};
00551 
00552     // We need null implementations of the other virtual functions to
00553     // avoid warnings about hidden virtual functions.
00554 
00555     raw_ostream &operator()(raw_ostream &out,
00556                             const MachineBasicBlock &instr) const {
00557       return out;
00558     }
00559     
00560     raw_ostream &operator()(raw_ostream &out,
00561                             const MachineInstr &instr) const;
00562 
00563     std::ostream &operator()(std::ostream &out,
00564                              const MachineBasicBlock &instr) const {
00565       return out;
00566     }
00567     
00568     std::ostream &operator()(std::ostream &out,
00569                              const MachineInstr &instr) const {
00570       return out;
00571     }
00572   };
00573 } // End llvm namespace
00574 
00575 #endif