LiveIntervalAnalysis.h revision 48bff92b60d3c657704aa97b47b2b104cb9d1550 
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<LiveIndex, MachineBasicBlock*> IdxMBBPair;
44
45  inline bool operator<(LiveIndex V, const IdxMBBPair &IM) {
46    return V < IM.first;
47  }
48
49  inline bool operator<(const IdxMBBPair &IM, LiveIndex 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<LiveIndex, LiveIndex> > 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*, LiveIndex> 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*, LiveIndex> 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    LiveIndex getBaseIndex(LiveIndex index) {
110      return LiveIndex(index, LiveIndex::LOAD);
111    }
112    LiveIndex getBoundaryIndex(LiveIndex index) {
113      return LiveIndex(index,
114        (LiveIndex::Slot)(LiveIndex::NUM - 1));
115    }
116    LiveIndex getLoadIndex(LiveIndex index) {
117      return LiveIndex(index, LiveIndex::LOAD);
118    }
119    LiveIndex getUseIndex(LiveIndex index) {
120      return LiveIndex(index, LiveIndex::USE);
121    }
122    LiveIndex getDefIndex(LiveIndex index) {
123      return LiveIndex(index, LiveIndex::DEF);
124    }
125    LiveIndex getStoreIndex(LiveIndex index) {
126      return LiveIndex(index, LiveIndex::STORE);
127    }
128
129    LiveIndex getNextSlot(LiveIndex m) const {
130      return m.nextSlot_();
131    }
132
133    LiveIndex getNextIndex(LiveIndex m) const {
134      return m.nextIndex_();
135    }
136
137    LiveIndex getPrevSlot(LiveIndex m) const {
138      return m.prevSlot_();
139    }
140
141    LiveIndex getPrevIndex(LiveIndex 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    LiveIndex getMBBStartIdx(MachineBasicBlock *MBB) const {
176      return getMBBStartIdx(MBB->getNumber());
177    }
178    LiveIndex 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    LiveIndex getMBBEndIdx(MachineBasicBlock *MBB) const {
186      return getMBBEndIdx(MBB->getNumber());
187    }
188    LiveIndex 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(LiveIndex 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    LiveIndex 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(LiveIndex 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(LiveIndex 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(LiveIndex 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    LiveIndex findGapBeforeInstr(LiveIndex Index, bool Furthest = false) {
258      Index = getBaseIndex(getPrevIndex(Index));
259      if (getInstructionFromIndex(Index))
260        return LiveIndex();  // No gap!
261      if (!Furthest)
262        return Index;
263      LiveIndex PrevIndex = getBaseIndex(getPrevIndex(Index));
264      while (getInstructionFromIndex(Index)) {
265        Index = PrevIndex;
266        PrevIndex = getBaseIndex(getPrevIndex(Index));
267      }
268      return Index;
269    }
270
271    /// InsertMachineInstrInMaps - Insert the specified machine instruction
272    /// into the instruction index map at the given index.
273    void InsertMachineInstrInMaps(MachineInstr *MI, LiveIndex Index) {
274      i2miMap_[Index.getVecIndex()] = MI;
275      Mi2IndexMap::iterator it = mi2iMap_.find(MI);
276      assert(it == mi2iMap_.end() && "Already in map!");
277      mi2iMap_[MI] = Index;
278    }
279
280    /// conflictsWithPhysRegDef - Returns true if the specified register
281    /// is defined during the duration of the specified interval.
282    bool conflictsWithPhysRegDef(const LiveInterval &li, VirtRegMap &vrm,
283                                 unsigned reg);
284
285    /// conflictsWithPhysRegRef - Similar to conflictsWithPhysRegRef except
286    /// it can check use as well.
287    bool conflictsWithPhysRegRef(LiveInterval &li, unsigned Reg,
288                                 bool CheckUse,
289                                 SmallPtrSet<MachineInstr*,32> &JoinedCopies);
290
291    /// findLiveInMBBs - Given a live range, if the value of the range
292    /// is live in any MBB returns true as well as the list of basic blocks
293    /// in which the value is live.
294    bool findLiveInMBBs(LiveIndex Start, LiveIndex End,
295                        SmallVectorImpl<MachineBasicBlock*> &MBBs) const;
296
297    /// findReachableMBBs - Return a list MBB that can be reached via any
298    /// branch or fallthroughs. Return true if the list is not empty.
299    bool findReachableMBBs(LiveIndex Start, LiveIndex End,
300                        SmallVectorImpl<MachineBasicBlock*> &MBBs) const;
301
302    // Interval creation
303
304    LiveInterval &getOrCreateInterval(unsigned reg) {
305      Reg2IntervalMap::iterator I = r2iMap_.find(reg);
306      if (I == r2iMap_.end())
307        I = r2iMap_.insert(std::make_pair(reg, createInterval(reg))).first;
308      return *I->second;
309    }
310
311    /// dupInterval - Duplicate a live interval. The caller is responsible for
312    /// managing the allocated memory.
313    LiveInterval *dupInterval(LiveInterval *li);
314
315    /// addLiveRangeToEndOfBlock - Given a register and an instruction,
316    /// adds a live range from that instruction to the end of its MBB.
317    LiveRange addLiveRangeToEndOfBlock(unsigned reg,
318                                       MachineInstr* startInst);
319
320    // Interval removal
321
322    void removeInterval(unsigned Reg) {
323      DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.find(Reg);
324      delete I->second;
325      r2iMap_.erase(I);
326    }
327
328    /// isNotInMIMap - returns true if the specified machine instr has been
329    /// removed or was never entered in the map.
330    bool isNotInMIMap(MachineInstr* instr) const {
331      return !mi2iMap_.count(instr);
332    }
333
334    /// RemoveMachineInstrFromMaps - This marks the specified machine instr as
335    /// deleted.
336    void RemoveMachineInstrFromMaps(MachineInstr *MI) {
337      // remove index -> MachineInstr and
338      // MachineInstr -> index mappings
339      Mi2IndexMap::iterator mi2i = mi2iMap_.find(MI);
340      if (mi2i != mi2iMap_.end()) {
341        i2miMap_[mi2i->second.index/InstrSlots::NUM] = 0;
342        mi2iMap_.erase(mi2i);
343      }
344    }
345
346    /// ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in
347    /// maps used by register allocator.
348    void ReplaceMachineInstrInMaps(MachineInstr *MI, MachineInstr *NewMI) {
349      Mi2IndexMap::iterator mi2i = mi2iMap_.find(MI);
350      if (mi2i == mi2iMap_.end())
351        return;
352      i2miMap_[mi2i->second.index/InstrSlots::NUM] = NewMI;
353      Mi2IndexMap::iterator it = mi2iMap_.find(MI);
354      assert(it != mi2iMap_.end() && "Invalid instruction!");
355      LiveIndex Index = it->second;
356      mi2iMap_.erase(it);
357      mi2iMap_[NewMI] = Index;
358    }
359
360    BumpPtrAllocator& getVNInfoAllocator() { return VNInfoAllocator; }
361
362    /// getVNInfoSourceReg - Helper function that parses the specified VNInfo
363    /// copy field and returns the source register that defines it.
364    unsigned getVNInfoSourceReg(const VNInfo *VNI) const;
365
366    virtual void getAnalysisUsage(AnalysisUsage &AU) const;
367    virtual void releaseMemory();
368
369    /// runOnMachineFunction - pass entry point
370    virtual bool runOnMachineFunction(MachineFunction&);
371
372    /// print - Implement the dump method.
373    virtual void print(raw_ostream &O, const Module* = 0) const;
374
375    /// addIntervalsForSpills - Create new intervals for spilled defs / uses of
376    /// the given interval. FIXME: It also returns the weight of the spill slot
377    /// (if any is created) by reference. This is temporary.
378    std::vector<LiveInterval*>
379    addIntervalsForSpills(const LiveInterval& i,
380                          SmallVectorImpl<LiveInterval*> &SpillIs,
381                          const MachineLoopInfo *loopInfo, VirtRegMap& vrm);
382
383    /// addIntervalsForSpillsFast - Quickly create new intervals for spilled
384    /// defs / uses without remat or splitting.
385    std::vector<LiveInterval*>
386    addIntervalsForSpillsFast(const LiveInterval &li,
387                              const MachineLoopInfo *loopInfo, VirtRegMap &vrm);
388
389    /// spillPhysRegAroundRegDefsUses - Spill the specified physical register
390    /// around all defs and uses of the specified interval. Return true if it
391    /// was able to cut its interval.
392    bool spillPhysRegAroundRegDefsUses(const LiveInterval &li,
393                                       unsigned PhysReg, VirtRegMap &vrm);
394
395    /// isReMaterializable - Returns true if every definition of MI of every
396    /// val# of the specified interval is re-materializable. Also returns true
397    /// by reference if all of the defs are load instructions.
398    bool isReMaterializable(const LiveInterval &li,
399                            SmallVectorImpl<LiveInterval*> &SpillIs,
400                            bool &isLoad);
401
402    /// isReMaterializable - Returns true if the definition MI of the specified
403    /// val# of the specified interval is re-materializable.
404    bool isReMaterializable(const LiveInterval &li, const VNInfo *ValNo,
405                            MachineInstr *MI);
406
407    /// getRepresentativeReg - Find the largest super register of the specified
408    /// physical register.
409    unsigned getRepresentativeReg(unsigned Reg) const;
410
411    /// getNumConflictsWithPhysReg - Return the number of uses and defs of the
412    /// specified interval that conflicts with the specified physical register.
413    unsigned getNumConflictsWithPhysReg(const LiveInterval &li,
414                                        unsigned PhysReg) const;
415
416    /// processImplicitDefs - Process IMPLICIT_DEF instructions. Add isUndef
417    /// marker to implicit_def defs and their uses.
418    void processImplicitDefs();
419
420    /// computeNumbering - Compute the index numbering.
421    void computeNumbering();
422
423    /// scaleNumbering - Rescale interval numbers to introduce gaps for new
424    /// instructions
425    void scaleNumbering(int factor);
426
427    /// intervalIsInOneMBB - Returns true if the specified interval is entirely
428    /// within a single basic block.
429    bool intervalIsInOneMBB(const LiveInterval &li) const;
430
431  private:
432    /// computeIntervals - Compute live intervals.
433    void computeIntervals();
434
435    bool isProfitableToCoalesce(LiveInterval &DstInt, LiveInterval &SrcInt,
436                                SmallVector<MachineInstr*,16> &IdentCopies,
437                                SmallVector<MachineInstr*,16> &OtherCopies);
438
439    void performEarlyCoalescing();
440
441    /// handleRegisterDef - update intervals for a register def
442    /// (calls handlePhysicalRegisterDef and
443    /// handleVirtualRegisterDef)
444    void handleRegisterDef(MachineBasicBlock *MBB,
445                           MachineBasicBlock::iterator MI,
446                           LiveIndex MIIdx,
447                           MachineOperand& MO, unsigned MOIdx);
448
449    /// handleVirtualRegisterDef - update intervals for a virtual
450    /// register def
451    void handleVirtualRegisterDef(MachineBasicBlock *MBB,
452                                  MachineBasicBlock::iterator MI,
453                                  LiveIndex MIIdx, MachineOperand& MO,
454                                  unsigned MOIdx,
455                                  LiveInterval& interval);
456
457    /// handlePhysicalRegisterDef - update intervals for a physical register
458    /// def.
459    void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
460                                   MachineBasicBlock::iterator mi,
461                                   LiveIndex MIIdx, MachineOperand& MO,
462                                   LiveInterval &interval,
463                                   MachineInstr *CopyMI);
464
465    /// handleLiveInRegister - Create interval for a livein register.
466    void handleLiveInRegister(MachineBasicBlock* mbb,
467                              LiveIndex MIIdx,
468                              LiveInterval &interval, bool isAlias = false);
469
470    /// getReMatImplicitUse - If the remat definition MI has one (for now, we
471    /// only allow one) virtual register operand, then its uses are implicitly
472    /// using the register. Returns the virtual register.
473    unsigned getReMatImplicitUse(const LiveInterval &li,
474                                 MachineInstr *MI) const;
475
476    /// isValNoAvailableAt - Return true if the val# of the specified interval
477    /// which reaches the given instruction also reaches the specified use
478    /// index.
479    bool isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI,
480                            LiveIndex UseIdx) const;
481
482    /// isReMaterializable - Returns true if the definition MI of the specified
483    /// val# of the specified interval is re-materializable. Also returns true
484    /// by reference if the def is a load.
485    bool isReMaterializable(const LiveInterval &li, const VNInfo *ValNo,
486                            MachineInstr *MI,
487                            SmallVectorImpl<LiveInterval*> &SpillIs,
488                            bool &isLoad);
489
490    /// tryFoldMemoryOperand - Attempts to fold either a spill / restore from
491    /// slot / to reg or any rematerialized load into ith operand of specified
492    /// MI. If it is successul, MI is updated with the newly created MI and
493    /// returns true.
494    bool tryFoldMemoryOperand(MachineInstr* &MI, VirtRegMap &vrm,
495                              MachineInstr *DefMI, LiveIndex InstrIdx,
496                              SmallVector<unsigned, 2> &Ops,
497                              bool isSS, int FrameIndex, unsigned Reg);
498
499    /// canFoldMemoryOperand - Return true if the specified load / store
500    /// folding is possible.
501    bool canFoldMemoryOperand(MachineInstr *MI,
502                              SmallVector<unsigned, 2> &Ops,
503                              bool ReMatLoadSS) const;
504
505    /// anyKillInMBBAfterIdx - Returns true if there is a kill of the specified
506    /// VNInfo that's after the specified index but is within the basic block.
507    bool anyKillInMBBAfterIdx(const LiveInterval &li, const VNInfo *VNI,
508                              MachineBasicBlock *MBB,
509                              LiveIndex Idx) const;
510
511    /// hasAllocatableSuperReg - Return true if the specified physical register
512    /// has any super register that's allocatable.
513    bool hasAllocatableSuperReg(unsigned Reg) const;
514
515    /// SRInfo - Spill / restore info.
516    struct SRInfo {
517      LiveIndex index;
518      unsigned vreg;
519      bool canFold;
520      SRInfo(LiveIndex i, unsigned vr, bool f)
521        : index(i), vreg(vr), canFold(f) {}
522    };
523
524    bool alsoFoldARestore(int Id, LiveIndex index, unsigned vr,
525                          BitVector &RestoreMBBs,
526                          DenseMap<unsigned,std::vector<SRInfo> >&RestoreIdxes);
527    void eraseRestoreInfo(int Id, LiveIndex index, unsigned vr,
528                          BitVector &RestoreMBBs,
529                          DenseMap<unsigned,std::vector<SRInfo> >&RestoreIdxes);
530
531    /// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being
532    /// spilled and create empty intervals for their uses.
533    void handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm,
534                              const TargetRegisterClass* rc,
535                              std::vector<LiveInterval*> &NewLIs);
536
537    /// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of
538    /// interval on to-be re-materialized operands of MI) with new register.
539    void rewriteImplicitOps(const LiveInterval &li,
540                           MachineInstr *MI, unsigned NewVReg, VirtRegMap &vrm);
541
542    /// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper
543    /// functions for addIntervalsForSpills to rewrite uses / defs for the given
544    /// live range.
545    bool rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
546        bool TrySplit, LiveIndex index, LiveIndex end,
547        MachineInstr *MI, MachineInstr *OrigDefMI, MachineInstr *DefMI,
548        unsigned Slot, int LdSlot,
549        bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
550        VirtRegMap &vrm, const TargetRegisterClass* rc,
551        SmallVector<int, 4> &ReMatIds, const MachineLoopInfo *loopInfo,
552        unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse,
553        DenseMap<unsigned,unsigned> &MBBVRegsMap,
554        std::vector<LiveInterval*> &NewLIs);
555    void rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
556        LiveInterval::Ranges::const_iterator &I,
557        MachineInstr *OrigDefMI, MachineInstr *DefMI, unsigned Slot, int LdSlot,
558        bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
559        VirtRegMap &vrm, const TargetRegisterClass* rc,
560        SmallVector<int, 4> &ReMatIds, const MachineLoopInfo *loopInfo,
561        BitVector &SpillMBBs,
562        DenseMap<unsigned,std::vector<SRInfo> > &SpillIdxes,
563        BitVector &RestoreMBBs,
564        DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes,
565        DenseMap<unsigned,unsigned> &MBBVRegsMap,
566        std::vector<LiveInterval*> &NewLIs);
567
568    static LiveInterval* createInterval(unsigned Reg);
569
570    void printInstrs(raw_ostream &O) const;
571    void dumpInstrs() const;
572  };
573} // End llvm namespace
574
575#endif
576