LiveIntervalAnalysis.h revision db1c2c57ffe1b905c0ae71bc5c806b14f170903b 
1//===-- LiveIntervalAnalysis.h - Live Interval Analysis ---------*- C++ -*-===//
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// This file implements the LiveInterval analysis pass.  Given some numbering of
11// each the machine instructions (in this implemention depth-first order) an
12// interval [i, j) is said to be a live interval for register v if there is no
13// instruction with number j' > j such that v is live at j' and there is no
14// instruction with number i' < i such that v is live at i'. In this
15// implementation intervals can have holes, i.e. an interval might look like
16// [1,20), [50,65), [1000,1001).
17//
18//===----------------------------------------------------------------------===//
19
20#ifndef LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H
21#define LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H
22
23#include "llvm/CodeGen/MachineBasicBlock.h"
24#include "llvm/CodeGen/MachineFunctionPass.h"
25#include "llvm/CodeGen/LiveInterval.h"
26#include "llvm/ADT/BitVector.h"
27#include "llvm/ADT/DenseMap.h"
28#include "llvm/ADT/SmallPtrSet.h"
29#include "llvm/ADT/SmallVector.h"
30#include "llvm/Support/Allocator.h"
31#include <cmath>
32
33namespace llvm {
34
35  class AliasAnalysis;
36  class LiveVariables;
37  class MachineLoopInfo;
38  class TargetRegisterInfo;
39  class MachineRegisterInfo;
40  class TargetInstrInfo;
41  class TargetRegisterClass;
42  class VirtRegMap;
43  typedef std::pair<MachineInstrIndex, MachineBasicBlock*> IdxMBBPair;
44
45  inline bool operator<(MachineInstrIndex V, const IdxMBBPair &IM) {
46    return V < IM.first;
47  }
48
49  inline bool operator<(const IdxMBBPair &IM, MachineInstrIndex V) {
50    return IM.first < V;
51  }
52
53  struct Idx2MBBCompare {
54    bool operator()(const IdxMBBPair &LHS, const IdxMBBPair &RHS) const {
55      return LHS.first < RHS.first;
56    }
57  };
58
59  class LiveIntervals : public MachineFunctionPass {
60    MachineFunction* mf_;
61    MachineRegisterInfo* mri_;
62    const TargetMachine* tm_;
63    const TargetRegisterInfo* tri_;
64    const TargetInstrInfo* tii_;
65    AliasAnalysis *aa_;
66    LiveVariables* lv_;
67
68    /// Special pool allocator for VNInfo's (LiveInterval val#).
69    ///
70    BumpPtrAllocator VNInfoAllocator;
71
72    /// MBB2IdxMap - The indexes of the first and last instructions in the
73    /// specified basic block.
74    std::vector<std::pair<MachineInstrIndex, MachineInstrIndex> > MBB2IdxMap;
75
76    /// Idx2MBBMap - Sorted list of pairs of index of first instruction
77    /// and MBB id.
78    std::vector<IdxMBBPair> Idx2MBBMap;
79
80    /// FunctionSize - The number of instructions present in the function
81    uint64_t FunctionSize;
82
83    typedef DenseMap<const MachineInstr*, MachineInstrIndex> Mi2IndexMap;
84    Mi2IndexMap mi2iMap_;
85
86    typedef std::vector<MachineInstr*> Index2MiMap;
87    Index2MiMap i2miMap_;
88
89    typedef DenseMap<unsigned, LiveInterval*> Reg2IntervalMap;
90    Reg2IntervalMap r2iMap_;
91
92    DenseMap<MachineBasicBlock*, MachineInstrIndex> terminatorGaps;
93
94    /// phiJoinCopies - Copy instructions which are PHI joins.
95    SmallVector<MachineInstr*, 16> phiJoinCopies;
96
97    /// allocatableRegs_ - A bit vector of allocatable registers.
98    BitVector allocatableRegs_;
99
100    /// CloneMIs - A list of clones as result of re-materialization.
101    std::vector<MachineInstr*> CloneMIs;
102
103    typedef LiveInterval::InstrSlots InstrSlots;
104
105  public:
106    static char ID; // Pass identification, replacement for typeid
107    LiveIntervals() : MachineFunctionPass(&ID) {}
108
109    MachineInstrIndex getBaseIndex(MachineInstrIndex index) {
110      return MachineInstrIndex(index, MachineInstrIndex::LOAD);
111    }
112    MachineInstrIndex getBoundaryIndex(MachineInstrIndex index) {
113      return MachineInstrIndex(index,
114        (MachineInstrIndex::Slot)(MachineInstrIndex::NUM - 1));
115    }
116    MachineInstrIndex getLoadIndex(MachineInstrIndex index) {
117      return MachineInstrIndex(index, MachineInstrIndex::LOAD);
118    }
119    MachineInstrIndex getUseIndex(MachineInstrIndex index) {
120      return MachineInstrIndex(index, MachineInstrIndex::USE);
121    }
122    MachineInstrIndex getDefIndex(MachineInstrIndex index) {
123      return MachineInstrIndex(index, MachineInstrIndex::DEF);
124    }
125    MachineInstrIndex getStoreIndex(MachineInstrIndex index) {
126      return MachineInstrIndex(index, MachineInstrIndex::STORE);
127    }
128
129    MachineInstrIndex getNextSlot(MachineInstrIndex m) const {
130      return m.nextSlot_();
131    }
132
133    MachineInstrIndex getNextIndex(MachineInstrIndex m) const {
134      return m.nextIndex_();
135    }
136
137    MachineInstrIndex getPrevSlot(MachineInstrIndex m) const {
138      return m.prevSlot_();
139    }
140
141    MachineInstrIndex getPrevIndex(MachineInstrIndex m) const {
142      return m.prevIndex_();
143    }
144
145    static float getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) {
146      return (isDef + isUse) * powf(10.0F, (float)loopDepth);
147    }
148
149    typedef Reg2IntervalMap::iterator iterator;
150    typedef Reg2IntervalMap::const_iterator const_iterator;
151    const_iterator begin() const { return r2iMap_.begin(); }
152    const_iterator end() const { return r2iMap_.end(); }
153    iterator begin() { return r2iMap_.begin(); }
154    iterator end() { return r2iMap_.end(); }
155    unsigned getNumIntervals() const { return (unsigned)r2iMap_.size(); }
156
157    LiveInterval &getInterval(unsigned reg) {
158      Reg2IntervalMap::iterator I = r2iMap_.find(reg);
159      assert(I != r2iMap_.end() && "Interval does not exist for register");
160      return *I->second;
161    }
162
163    const LiveInterval &getInterval(unsigned reg) const {
164      Reg2IntervalMap::const_iterator I = r2iMap_.find(reg);
165      assert(I != r2iMap_.end() && "Interval does not exist for register");
166      return *I->second;
167    }
168
169    bool hasInterval(unsigned reg) const {
170      return r2iMap_.count(reg);
171    }
172
173    /// getMBBStartIdx - Return the base index of the first instruction in the
174    /// specified MachineBasicBlock.
175    MachineInstrIndex getMBBStartIdx(MachineBasicBlock *MBB) const {
176      return getMBBStartIdx(MBB->getNumber());
177    }
178    MachineInstrIndex getMBBStartIdx(unsigned MBBNo) const {
179      assert(MBBNo < MBB2IdxMap.size() && "Invalid MBB number!");
180      return MBB2IdxMap[MBBNo].first;
181    }
182
183    /// getMBBEndIdx - Return the store index of the last instruction in the
184    /// specified MachineBasicBlock.
185    MachineInstrIndex getMBBEndIdx(MachineBasicBlock *MBB) const {
186      return getMBBEndIdx(MBB->getNumber());
187    }
188    MachineInstrIndex getMBBEndIdx(unsigned MBBNo) const {
189      assert(MBBNo < MBB2IdxMap.size() && "Invalid MBB number!");
190      return MBB2IdxMap[MBBNo].second;
191    }
192
193    /// getScaledIntervalSize - get the size of an interval in "units,"
194    /// where every function is composed of one thousand units.  This
195    /// measure scales properly with empty index slots in the function.
196    double getScaledIntervalSize(LiveInterval& I) {
197      return (1000.0 / InstrSlots::NUM * I.getSize()) / i2miMap_.size();
198    }
199
200    /// getApproximateInstructionCount - computes an estimate of the number
201    /// of instructions in a given LiveInterval.
202    unsigned getApproximateInstructionCount(LiveInterval& I) {
203      double IntervalPercentage = getScaledIntervalSize(I) / 1000.0;
204      return (unsigned)(IntervalPercentage * FunctionSize);
205    }
206
207    /// getMBBFromIndex - given an index in any instruction of an
208    /// MBB return a pointer the MBB
209    MachineBasicBlock* getMBBFromIndex(MachineInstrIndex index) const {
210      std::vector<IdxMBBPair>::const_iterator I =
211        std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), index);
212      // Take the pair containing the index
213      std::vector<IdxMBBPair>::const_iterator J =
214        ((I != Idx2MBBMap.end() && I->first > index) ||
215         (I == Idx2MBBMap.end() && Idx2MBBMap.size()>0)) ? (I-1): I;
216
217      assert(J != Idx2MBBMap.end() && J->first <= index &&
218             index <= getMBBEndIdx(J->second) &&
219             "index does not correspond to an MBB");
220      return J->second;
221    }
222
223    /// getInstructionIndex - returns the base index of instr
224    MachineInstrIndex getInstructionIndex(const MachineInstr* instr) const {
225      Mi2IndexMap::const_iterator it = mi2iMap_.find(instr);
226      assert(it != mi2iMap_.end() && "Invalid instruction!");
227      return it->second;
228    }
229
230    /// getInstructionFromIndex - given an index in any slot of an
231    /// instruction return a pointer the instruction
232    MachineInstr* getInstructionFromIndex(MachineInstrIndex index) const {
233      // convert index to vector index
234      unsigned i = index.getVecIndex();
235      assert(i < i2miMap_.size() &&
236             "index does not correspond to an instruction");
237      return i2miMap_[i];
238    }
239
240    /// hasGapBeforeInstr - Return true if the previous instruction slot,
241    /// i.e. Index - InstrSlots::NUM, is not occupied.
242    bool hasGapBeforeInstr(MachineInstrIndex Index) {
243      Index = getBaseIndex(getPrevIndex(Index));
244      return getInstructionFromIndex(Index) == 0;
245    }
246
247    /// hasGapAfterInstr - Return true if the successive instruction slot,
248    /// i.e. Index + InstrSlots::Num, is not occupied.
249    bool hasGapAfterInstr(MachineInstrIndex Index) {
250      Index = getBaseIndex(getNextIndex(Index));
251      return getInstructionFromIndex(Index) == 0;
252    }
253
254    /// findGapBeforeInstr - Find an empty instruction slot before the
255    /// specified index. If "Furthest" is true, find one that's furthest
256    /// away from the index (but before any index that's occupied).
257    MachineInstrIndex findGapBeforeInstr(MachineInstrIndex Index,
258                                         bool Furthest = false) {
259      Index = getBaseIndex(getPrevIndex(Index));
260      if (getInstructionFromIndex(Index))
261        return MachineInstrIndex();  // No gap!
262      if (!Furthest)
263        return Index;
264      MachineInstrIndex PrevIndex = getBaseIndex(getPrevIndex(Index));
265      while (getInstructionFromIndex(Index)) {
266        Index = PrevIndex;
267        PrevIndex = getBaseIndex(getPrevIndex(Index));
268      }
269      return Index;
270    }
271
272    /// InsertMachineInstrInMaps - Insert the specified machine instruction
273    /// into the instruction index map at the given index.
274    void InsertMachineInstrInMaps(MachineInstr *MI, MachineInstrIndex Index) {
275      i2miMap_[Index.getVecIndex()] = MI;
276      Mi2IndexMap::iterator it = mi2iMap_.find(MI);
277      assert(it == mi2iMap_.end() && "Already in map!");
278      mi2iMap_[MI] = Index;
279    }
280
281    /// conflictsWithPhysRegDef - Returns true if the specified register
282    /// is defined during the duration of the specified interval.
283    bool conflictsWithPhysRegDef(const LiveInterval &li, VirtRegMap &vrm,
284                                 unsigned reg);
285
286    /// conflictsWithPhysRegRef - Similar to conflictsWithPhysRegRef except
287    /// it can check use as well.
288    bool conflictsWithPhysRegRef(LiveInterval &li, unsigned Reg,
289                                 bool CheckUse,
290                                 SmallPtrSet<MachineInstr*,32> &JoinedCopies);
291
292    /// findLiveInMBBs - Given a live range, if the value of the range
293    /// is live in any MBB returns true as well as the list of basic blocks
294    /// in which the value is live.
295    bool findLiveInMBBs(MachineInstrIndex Start, MachineInstrIndex End,
296                        SmallVectorImpl<MachineBasicBlock*> &MBBs) const;
297
298    /// findReachableMBBs - Return a list MBB that can be reached via any
299    /// branch or fallthroughs. Return true if the list is not empty.
300    bool findReachableMBBs(MachineInstrIndex Start, MachineInstrIndex End,
301                        SmallVectorImpl<MachineBasicBlock*> &MBBs) const;
302
303    // Interval creation
304
305    LiveInterval &getOrCreateInterval(unsigned reg) {
306      Reg2IntervalMap::iterator I = r2iMap_.find(reg);
307      if (I == r2iMap_.end())
308        I = r2iMap_.insert(std::make_pair(reg, createInterval(reg))).first;
309      return *I->second;
310    }
311
312    /// dupInterval - Duplicate a live interval. The caller is responsible for
313    /// managing the allocated memory.
314    LiveInterval *dupInterval(LiveInterval *li);
315
316    /// addLiveRangeToEndOfBlock - Given a register and an instruction,
317    /// adds a live range from that instruction to the end of its MBB.
318    LiveRange addLiveRangeToEndOfBlock(unsigned reg,
319                                       MachineInstr* startInst);
320
321    // Interval removal
322
323    void removeInterval(unsigned Reg) {
324      DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.find(Reg);
325      delete I->second;
326      r2iMap_.erase(I);
327    }
328
329    /// isNotInMIMap - returns true if the specified machine instr has been
330    /// removed or was never entered in the map.
331    bool isNotInMIMap(MachineInstr* instr) const {
332      return !mi2iMap_.count(instr);
333    }
334
335    /// RemoveMachineInstrFromMaps - This marks the specified machine instr as
336    /// deleted.
337    void RemoveMachineInstrFromMaps(MachineInstr *MI) {
338      // remove index -> MachineInstr and
339      // MachineInstr -> index mappings
340      Mi2IndexMap::iterator mi2i = mi2iMap_.find(MI);
341      if (mi2i != mi2iMap_.end()) {
342        i2miMap_[mi2i->second.index/InstrSlots::NUM] = 0;
343        mi2iMap_.erase(mi2i);
344      }
345    }
346
347    /// ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in
348    /// maps used by register allocator.
349    void ReplaceMachineInstrInMaps(MachineInstr *MI, MachineInstr *NewMI) {
350      Mi2IndexMap::iterator mi2i = mi2iMap_.find(MI);
351      if (mi2i == mi2iMap_.end())
352        return;
353      i2miMap_[mi2i->second.index/InstrSlots::NUM] = NewMI;
354      Mi2IndexMap::iterator it = mi2iMap_.find(MI);
355      assert(it != mi2iMap_.end() && "Invalid instruction!");
356      MachineInstrIndex Index = it->second;
357      mi2iMap_.erase(it);
358      mi2iMap_[NewMI] = Index;
359    }
360
361    BumpPtrAllocator& getVNInfoAllocator() { return VNInfoAllocator; }
362
363    /// getVNInfoSourceReg - Helper function that parses the specified VNInfo
364    /// copy field and returns the source register that defines it.
365    unsigned getVNInfoSourceReg(const VNInfo *VNI) const;
366
367    virtual void getAnalysisUsage(AnalysisUsage &AU) const;
368    virtual void releaseMemory();
369
370    /// runOnMachineFunction - pass entry point
371    virtual bool runOnMachineFunction(MachineFunction&);
372
373    /// print - Implement the dump method.
374    virtual void print(raw_ostream &O, const Module* = 0) const;
375
376    /// addIntervalsForSpills - Create new intervals for spilled defs / uses of
377    /// the given interval. FIXME: It also returns the weight of the spill slot
378    /// (if any is created) by reference. This is temporary.
379    std::vector<LiveInterval*>
380    addIntervalsForSpills(const LiveInterval& i,
381                          SmallVectorImpl<LiveInterval*> &SpillIs,
382                          const MachineLoopInfo *loopInfo, VirtRegMap& vrm);
383
384    /// addIntervalsForSpillsFast - Quickly create new intervals for spilled
385    /// defs / uses without remat or splitting.
386    std::vector<LiveInterval*>
387    addIntervalsForSpillsFast(const LiveInterval &li,
388                              const MachineLoopInfo *loopInfo, VirtRegMap &vrm);
389
390    /// spillPhysRegAroundRegDefsUses - Spill the specified physical register
391    /// around all defs and uses of the specified interval. Return true if it
392    /// was able to cut its interval.
393    bool spillPhysRegAroundRegDefsUses(const LiveInterval &li,
394                                       unsigned PhysReg, VirtRegMap &vrm);
395
396    /// isReMaterializable - Returns true if every definition of MI of every
397    /// val# of the specified interval is re-materializable. Also returns true
398    /// by reference if all of the defs are load instructions.
399    bool isReMaterializable(const LiveInterval &li,
400                            SmallVectorImpl<LiveInterval*> &SpillIs,
401                            bool &isLoad);
402
403    /// isReMaterializable - Returns true if the definition MI of the specified
404    /// val# of the specified interval is re-materializable.
405    bool isReMaterializable(const LiveInterval &li, const VNInfo *ValNo,
406                            MachineInstr *MI);
407
408    /// getRepresentativeReg - Find the largest super register of the specified
409    /// physical register.
410    unsigned getRepresentativeReg(unsigned Reg) const;
411
412    /// getNumConflictsWithPhysReg - Return the number of uses and defs of the
413    /// specified interval that conflicts with the specified physical register.
414    unsigned getNumConflictsWithPhysReg(const LiveInterval &li,
415                                        unsigned PhysReg) const;
416
417    /// processImplicitDefs - Process IMPLICIT_DEF instructions. Add isUndef
418    /// marker to implicit_def defs and their uses.
419    void processImplicitDefs();
420
421    /// computeNumbering - Compute the index numbering.
422    void computeNumbering();
423
424    /// scaleNumbering - Rescale interval numbers to introduce gaps for new
425    /// instructions
426    void scaleNumbering(int factor);
427
428    /// intervalIsInOneMBB - Returns true if the specified interval is entirely
429    /// within a single basic block.
430    bool intervalIsInOneMBB(const LiveInterval &li) const;
431
432  private:
433    /// computeIntervals - Compute live intervals.
434    void computeIntervals();
435
436    bool isProfitableToCoalesce(LiveInterval &DstInt, LiveInterval &SrcInt,
437                                SmallVector<MachineInstr*,16> &IdentCopies,
438                                SmallVector<MachineInstr*,16> &OtherCopies);
439
440    void performEarlyCoalescing();
441
442    /// handleRegisterDef - update intervals for a register def
443    /// (calls handlePhysicalRegisterDef and
444    /// handleVirtualRegisterDef)
445    void handleRegisterDef(MachineBasicBlock *MBB,
446                           MachineBasicBlock::iterator MI,
447                           MachineInstrIndex MIIdx,
448                           MachineOperand& MO, unsigned MOIdx);
449
450    /// handleVirtualRegisterDef - update intervals for a virtual
451    /// register def
452    void handleVirtualRegisterDef(MachineBasicBlock *MBB,
453                                  MachineBasicBlock::iterator MI,
454                                  MachineInstrIndex MIIdx, MachineOperand& MO,
455                                  unsigned MOIdx,
456                                  LiveInterval& interval);
457
458    /// handlePhysicalRegisterDef - update intervals for a physical register
459    /// def.
460    void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
461                                   MachineBasicBlock::iterator mi,
462                                   MachineInstrIndex MIIdx, MachineOperand& MO,
463                                   LiveInterval &interval,
464                                   MachineInstr *CopyMI);
465
466    /// handleLiveInRegister - Create interval for a livein register.
467    void handleLiveInRegister(MachineBasicBlock* mbb,
468                              MachineInstrIndex MIIdx,
469                              LiveInterval &interval, bool isAlias = false);
470
471    /// getReMatImplicitUse - If the remat definition MI has one (for now, we
472    /// only allow one) virtual register operand, then its uses are implicitly
473    /// using the register. Returns the virtual register.
474    unsigned getReMatImplicitUse(const LiveInterval &li,
475                                 MachineInstr *MI) const;
476
477    /// isValNoAvailableAt - Return true if the val# of the specified interval
478    /// which reaches the given instruction also reaches the specified use
479    /// index.
480    bool isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI,
481                            MachineInstrIndex UseIdx) const;
482
483    /// isReMaterializable - Returns true if the definition MI of the specified
484    /// val# of the specified interval is re-materializable. Also returns true
485    /// by reference if the def is a load.
486    bool isReMaterializable(const LiveInterval &li, const VNInfo *ValNo,
487                            MachineInstr *MI,
488                            SmallVectorImpl<LiveInterval*> &SpillIs,
489                            bool &isLoad);
490
491    /// tryFoldMemoryOperand - Attempts to fold either a spill / restore from
492    /// slot / to reg or any rematerialized load into ith operand of specified
493    /// MI. If it is successul, MI is updated with the newly created MI and
494    /// returns true.
495    bool tryFoldMemoryOperand(MachineInstr* &MI, VirtRegMap &vrm,
496                              MachineInstr *DefMI, MachineInstrIndex InstrIdx,
497                              SmallVector<unsigned, 2> &Ops,
498                              bool isSS, int FrameIndex, unsigned Reg);
499
500    /// canFoldMemoryOperand - Return true if the specified load / store
501    /// folding is possible.
502    bool canFoldMemoryOperand(MachineInstr *MI,
503                              SmallVector<unsigned, 2> &Ops,
504                              bool ReMatLoadSS) const;
505
506    /// anyKillInMBBAfterIdx - Returns true if there is a kill of the specified
507    /// VNInfo that's after the specified index but is within the basic block.
508    bool anyKillInMBBAfterIdx(const LiveInterval &li, const VNInfo *VNI,
509                              MachineBasicBlock *MBB,
510                              MachineInstrIndex Idx) const;
511
512    /// hasAllocatableSuperReg - Return true if the specified physical register
513    /// has any super register that's allocatable.
514    bool hasAllocatableSuperReg(unsigned Reg) const;
515
516    /// SRInfo - Spill / restore info.
517    struct SRInfo {
518      MachineInstrIndex index;
519      unsigned vreg;
520      bool canFold;
521      SRInfo(MachineInstrIndex i, unsigned vr, bool f)
522        : index(i), vreg(vr), canFold(f) {}
523    };
524
525    bool alsoFoldARestore(int Id, MachineInstrIndex index, unsigned vr,
526                          BitVector &RestoreMBBs,
527                          DenseMap<unsigned,std::vector<SRInfo> >&RestoreIdxes);
528    void eraseRestoreInfo(int Id, MachineInstrIndex index, unsigned vr,
529                          BitVector &RestoreMBBs,
530                          DenseMap<unsigned,std::vector<SRInfo> >&RestoreIdxes);
531
532    /// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being
533    /// spilled and create empty intervals for their uses.
534    void handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm,
535                              const TargetRegisterClass* rc,
536                              std::vector<LiveInterval*> &NewLIs);
537
538    /// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of
539    /// interval on to-be re-materialized operands of MI) with new register.
540    void rewriteImplicitOps(const LiveInterval &li,
541                           MachineInstr *MI, unsigned NewVReg, VirtRegMap &vrm);
542
543    /// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper
544    /// functions for addIntervalsForSpills to rewrite uses / defs for the given
545    /// live range.
546    bool rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
547        bool TrySplit, MachineInstrIndex index, MachineInstrIndex end,
548        MachineInstr *MI, MachineInstr *OrigDefMI, MachineInstr *DefMI,
549        unsigned Slot, int LdSlot,
550        bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
551        VirtRegMap &vrm, const TargetRegisterClass* rc,
552        SmallVector<int, 4> &ReMatIds, const MachineLoopInfo *loopInfo,
553        unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse,
554        DenseMap<unsigned,unsigned> &MBBVRegsMap,
555        std::vector<LiveInterval*> &NewLIs);
556    void rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
557        LiveInterval::Ranges::const_iterator &I,
558        MachineInstr *OrigDefMI, MachineInstr *DefMI, unsigned Slot, int LdSlot,
559        bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
560        VirtRegMap &vrm, const TargetRegisterClass* rc,
561        SmallVector<int, 4> &ReMatIds, const MachineLoopInfo *loopInfo,
562        BitVector &SpillMBBs,
563        DenseMap<unsigned,std::vector<SRInfo> > &SpillIdxes,
564        BitVector &RestoreMBBs,
565        DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes,
566        DenseMap<unsigned,unsigned> &MBBVRegsMap,
567        std::vector<LiveInterval*> &NewLIs);
568
569    static LiveInterval* createInterval(unsigned Reg);
570
571    void printInstrs(raw_ostream &O) const;
572    void dumpInstrs() const;
573  };
574} // End llvm namespace
575
576#endif
577