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