LiveIntervalAnalysis.h revision 0cc83b6e851a16292a39d9529ba8aab9b07f0bf0 
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' abd 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 <cmath>
31
32namespace llvm {
33
34  class LiveVariables;
35  class MachineLoopInfo;
36  class TargetRegisterInfo;
37  class MachineRegisterInfo;
38  class TargetInstrInfo;
39  class TargetRegisterClass;
40  class VirtRegMap;
41  typedef std::pair<unsigned, MachineBasicBlock*> IdxMBBPair;
42
43  inline bool operator<(unsigned V, const IdxMBBPair &IM) {
44    return V < IM.first;
45  }
46
47  inline bool operator<(const IdxMBBPair &IM, unsigned V) {
48    return IM.first < V;
49  }
50
51  struct Idx2MBBCompare {
52    bool operator()(const IdxMBBPair &LHS, const IdxMBBPair &RHS) const {
53      return LHS.first < RHS.first;
54    }
55  };
56
57  class LiveIntervals : public MachineFunctionPass {
58    MachineFunction* mf_;
59    MachineRegisterInfo* mri_;
60    const TargetMachine* tm_;
61    const TargetRegisterInfo* tri_;
62    const TargetInstrInfo* tii_;
63    LiveVariables* lv_;
64
65    /// Special pool allocator for VNInfo's (LiveInterval val#).
66    ///
67    BumpPtrAllocator VNInfoAllocator;
68
69    /// MBB2IdxMap - The indexes of the first and last instructions in the
70    /// specified basic block.
71    std::vector<std::pair<unsigned, unsigned> > MBB2IdxMap;
72
73    /// Idx2MBBMap - Sorted list of pairs of index of first instruction
74    /// and MBB id.
75    std::vector<IdxMBBPair> Idx2MBBMap;
76
77    typedef std::map<MachineInstr*, unsigned> Mi2IndexMap;
78    Mi2IndexMap mi2iMap_;
79
80    typedef std::vector<MachineInstr*> Index2MiMap;
81    Index2MiMap i2miMap_;
82
83    typedef std::map<unsigned, LiveInterval> Reg2IntervalMap;
84    Reg2IntervalMap r2iMap_;
85
86    BitVector allocatableRegs_;
87
88    std::vector<MachineInstr*> ClonedMIs;
89
90  public:
91    static char ID; // Pass identification, replacement for typeid
92    LiveIntervals() : MachineFunctionPass((intptr_t)&ID) {}
93
94    struct InstrSlots {
95      enum {
96        LOAD  = 0,
97        USE   = 1,
98        DEF   = 2,
99        STORE = 3,
100        NUM   = 4
101      };
102    };
103
104    static unsigned getBaseIndex(unsigned index) {
105      return index - (index % InstrSlots::NUM);
106    }
107    static unsigned getBoundaryIndex(unsigned index) {
108      return getBaseIndex(index + InstrSlots::NUM - 1);
109    }
110    static unsigned getLoadIndex(unsigned index) {
111      return getBaseIndex(index) + InstrSlots::LOAD;
112    }
113    static unsigned getUseIndex(unsigned index) {
114      return getBaseIndex(index) + InstrSlots::USE;
115    }
116    static unsigned getDefIndex(unsigned index) {
117      return getBaseIndex(index) + InstrSlots::DEF;
118    }
119    static unsigned getStoreIndex(unsigned index) {
120      return getBaseIndex(index) + InstrSlots::STORE;
121    }
122
123    static float getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) {
124      return (isDef + isUse) * powf(10.0F, (float)loopDepth);
125    }
126
127    typedef Reg2IntervalMap::iterator iterator;
128    typedef Reg2IntervalMap::const_iterator const_iterator;
129    const_iterator begin() const { return r2iMap_.begin(); }
130    const_iterator end() const { return r2iMap_.end(); }
131    iterator begin() { return r2iMap_.begin(); }
132    iterator end() { return r2iMap_.end(); }
133    unsigned getNumIntervals() const { return r2iMap_.size(); }
134
135    LiveInterval &getInterval(unsigned reg) {
136      Reg2IntervalMap::iterator I = r2iMap_.find(reg);
137      assert(I != r2iMap_.end() && "Interval does not exist for register");
138      return I->second;
139    }
140
141    const LiveInterval &getInterval(unsigned reg) const {
142      Reg2IntervalMap::const_iterator I = r2iMap_.find(reg);
143      assert(I != r2iMap_.end() && "Interval does not exist for register");
144      return I->second;
145    }
146
147    bool hasInterval(unsigned reg) const {
148      return r2iMap_.count(reg);
149    }
150
151    /// getMBBStartIdx - Return the base index of the first instruction in the
152    /// specified MachineBasicBlock.
153    unsigned getMBBStartIdx(MachineBasicBlock *MBB) const {
154      return getMBBStartIdx(MBB->getNumber());
155    }
156    unsigned getMBBStartIdx(unsigned MBBNo) const {
157      assert(MBBNo < MBB2IdxMap.size() && "Invalid MBB number!");
158      return MBB2IdxMap[MBBNo].first;
159    }
160
161    /// getMBBEndIdx - Return the store index of the last instruction in the
162    /// specified MachineBasicBlock.
163    unsigned getMBBEndIdx(MachineBasicBlock *MBB) const {
164      return getMBBEndIdx(MBB->getNumber());
165    }
166    unsigned getMBBEndIdx(unsigned MBBNo) const {
167      assert(MBBNo < MBB2IdxMap.size() && "Invalid MBB number!");
168      return MBB2IdxMap[MBBNo].second;
169    }
170
171    /// getMBBFromIndex - given an index in any instruction of an
172    /// MBB return a pointer the MBB
173    MachineBasicBlock* getMBBFromIndex(unsigned index) const {
174      std::vector<IdxMBBPair>::const_iterator I =
175	    std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), index);
176      // Take the pair containing the index
177      std::vector<IdxMBBPair>::const_iterator J =
178	  ((I != Idx2MBBMap.end() && I->first > index) ||
179	   (I == Idx2MBBMap.end() && Idx2MBBMap.size()>0)) ? (I-1): I;
180
181      assert(J != Idx2MBBMap.end() && J->first < index+1 &&
182	     index <= getMBBEndIdx(J->second) &&
183	     "index does not correspond to an MBB");
184      return J->second;
185    }
186
187    /// getInstructionIndex - returns the base index of instr
188    unsigned getInstructionIndex(MachineInstr* instr) const {
189      Mi2IndexMap::const_iterator it = mi2iMap_.find(instr);
190      assert(it != mi2iMap_.end() && "Invalid instruction!");
191      return it->second;
192    }
193
194    /// getInstructionFromIndex - given an index in any slot of an
195    /// instruction return a pointer the instruction
196    MachineInstr* getInstructionFromIndex(unsigned index) const {
197      index /= InstrSlots::NUM; // convert index to vector index
198      assert(index < i2miMap_.size() &&
199             "index does not correspond to an instruction");
200      return i2miMap_[index];
201    }
202
203    /// conflictsWithPhysRegDef - Returns true if the specified register
204    /// is defined during the duration of the specified interval.
205    bool conflictsWithPhysRegDef(const LiveInterval &li, VirtRegMap &vrm,
206                                 unsigned reg);
207
208    /// findLiveInMBBs - Given a live range, if the value of the range
209    /// is live in any MBB returns true as well as the list of basic blocks
210    /// where the value is live in.
211    bool findLiveInMBBs(const LiveRange &LR,
212                        SmallVectorImpl<MachineBasicBlock*> &MBBs) const;
213
214    // Interval creation
215
216    LiveInterval &getOrCreateInterval(unsigned reg) {
217      Reg2IntervalMap::iterator I = r2iMap_.find(reg);
218      if (I == r2iMap_.end())
219        I = r2iMap_.insert(I, std::make_pair(reg, createInterval(reg)));
220      return I->second;
221    }
222
223    // Interval removal
224
225    void removeInterval(unsigned Reg) {
226      r2iMap_.erase(Reg);
227    }
228
229    /// isRemoved - returns true if the specified machine instr has been
230    /// removed.
231    bool isRemoved(MachineInstr* instr) const {
232      return !mi2iMap_.count(instr);
233    }
234
235    /// RemoveMachineInstrFromMaps - This marks the specified machine instr as
236    /// deleted.
237    void RemoveMachineInstrFromMaps(MachineInstr *MI) {
238      // remove index -> MachineInstr and
239      // MachineInstr -> index mappings
240      Mi2IndexMap::iterator mi2i = mi2iMap_.find(MI);
241      if (mi2i != mi2iMap_.end()) {
242        i2miMap_[mi2i->second/InstrSlots::NUM] = 0;
243        mi2iMap_.erase(mi2i);
244      }
245    }
246
247    /// ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in
248    /// maps used by register allocator.
249    void ReplaceMachineInstrInMaps(MachineInstr *MI, MachineInstr *NewMI) {
250      Mi2IndexMap::iterator mi2i = mi2iMap_.find(MI);
251      if (mi2i == mi2iMap_.end())
252        return;
253      i2miMap_[mi2i->second/InstrSlots::NUM] = NewMI;
254      Mi2IndexMap::iterator it = mi2iMap_.find(MI);
255      assert(it != mi2iMap_.end() && "Invalid instruction!");
256      unsigned Index = it->second;
257      mi2iMap_.erase(it);
258      mi2iMap_[NewMI] = Index;
259    }
260
261    BumpPtrAllocator& getVNInfoAllocator() { return VNInfoAllocator; }
262
263    /// getVNInfoSourceReg - Helper function that parses the specified VNInfo
264    /// copy field and returns the source register that defines it.
265    unsigned getVNInfoSourceReg(const VNInfo *VNI) const;
266
267    virtual void getAnalysisUsage(AnalysisUsage &AU) const;
268    virtual void releaseMemory();
269
270    /// runOnMachineFunction - pass entry point
271    virtual bool runOnMachineFunction(MachineFunction&);
272
273    /// print - Implement the dump method.
274    virtual void print(std::ostream &O, const Module* = 0) const;
275    void print(std::ostream *O, const Module* M = 0) const {
276      if (O) print(*O, M);
277    }
278
279    /// addIntervalsForSpills - Create new intervals for spilled defs / uses of
280    /// the given interval.
281    std::vector<LiveInterval*>
282    addIntervalsForSpills(const LiveInterval& i,
283                          const MachineLoopInfo *loopInfo, VirtRegMap& vrm);
284
285    /// isReMaterializable - Returns true if every definition of MI of every
286    /// val# of the specified interval is re-materializable. Also returns true
287    /// by reference if all of the defs are load instructions.
288    bool isReMaterializable(const LiveInterval &li, bool &isLoad);
289
290  private:
291    /// computeIntervals - Compute live intervals.
292    void computeIntervals();
293
294    /// handleRegisterDef - update intervals for a register def
295    /// (calls handlePhysicalRegisterDef and
296    /// handleVirtualRegisterDef)
297    void handleRegisterDef(MachineBasicBlock *MBB,
298                           MachineBasicBlock::iterator MI, unsigned MIIdx,
299                           unsigned reg);
300
301    /// handleVirtualRegisterDef - update intervals for a virtual
302    /// register def
303    void handleVirtualRegisterDef(MachineBasicBlock *MBB,
304                                  MachineBasicBlock::iterator MI,
305                                  unsigned MIIdx,
306                                  LiveInterval& interval);
307
308    /// handlePhysicalRegisterDef - update intervals for a physical register
309    /// def.
310    void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
311                                   MachineBasicBlock::iterator mi,
312                                   unsigned MIIdx,
313                                   LiveInterval &interval,
314                                   MachineInstr *CopyMI);
315
316    /// handleLiveInRegister - Create interval for a livein register.
317    void handleLiveInRegister(MachineBasicBlock* mbb,
318                              unsigned MIIdx,
319                              LiveInterval &interval, bool isAlias = false);
320
321    /// getReMatImplicitUse - If the remat definition MI has one (for now, we
322    /// only allow one) virtual register operand, then its uses are implicitly
323    /// using the register. Returns the virtual register.
324    unsigned getReMatImplicitUse(const LiveInterval &li,
325                                 MachineInstr *MI) const;
326
327    /// isValNoAvailableAt - Return true if the val# of the specified interval
328    /// which reaches the given instruction also reaches the specified use
329    /// index.
330    bool isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI,
331                            unsigned UseIdx) const;
332
333    /// isReMaterializable - Returns true if the definition MI of the specified
334    /// val# of the specified interval is re-materializable. Also returns true
335    /// by reference if the def is a load.
336    bool isReMaterializable(const LiveInterval &li, const VNInfo *ValNo,
337                            MachineInstr *MI, bool &isLoad);
338
339    /// tryFoldMemoryOperand - Attempts to fold either a spill / restore from
340    /// slot / to reg or any rematerialized load into ith operand of specified
341    /// MI. If it is successul, MI is updated with the newly created MI and
342    /// returns true.
343    bool tryFoldMemoryOperand(MachineInstr* &MI, VirtRegMap &vrm,
344                              MachineInstr *DefMI, unsigned InstrIdx,
345                              SmallVector<unsigned, 2> &Ops,
346                              bool isSS, int Slot, unsigned Reg);
347
348    /// canFoldMemoryOperand - Return true if the specified load / store
349    /// folding is possible.
350    bool canFoldMemoryOperand(MachineInstr *MI,
351                              SmallVector<unsigned, 2> &Ops) const;
352    bool canFoldMemoryOperand(MachineInstr *MI, unsigned Reg) const;
353
354    /// anyKillInMBBAfterIdx - Returns true if there is a kill of the specified
355    /// VNInfo that's after the specified index but is within the basic block.
356    bool anyKillInMBBAfterIdx(const LiveInterval &li, const VNInfo *VNI,
357                              MachineBasicBlock *MBB, unsigned Idx) const;
358
359    /// intervalIsInOneMBB - Returns true if the specified interval is entirely
360    /// within a single basic block.
361    bool intervalIsInOneMBB(const LiveInterval &li) const;
362
363    /// SRInfo - Spill / restore info.
364    struct SRInfo {
365      int index;
366      unsigned vreg;
367      bool canFold;
368      SRInfo(int i, unsigned vr, bool f) : index(i), vreg(vr), canFold(f) {};
369    };
370
371    bool alsoFoldARestore(int Id, int index, unsigned vr,
372                          BitVector &RestoreMBBs,
373                          std::map<unsigned,std::vector<SRInfo> >&RestoreIdxes);
374    void eraseRestoreInfo(int Id, int index, unsigned vr,
375                          BitVector &RestoreMBBs,
376                          std::map<unsigned,std::vector<SRInfo> >&RestoreIdxes);
377
378    /// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of
379    /// interval on to-be re-materialized operands of MI) with new register.
380    void rewriteImplicitOps(const LiveInterval &li,
381                           MachineInstr *MI, unsigned NewVReg, VirtRegMap &vrm);
382
383    /// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper
384    /// functions for addIntervalsForSpills to rewrite uses / defs for the given
385    /// live range.
386    bool rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
387        bool TrySplit, unsigned index, unsigned end, MachineInstr *MI,
388        MachineInstr *OrigDefMI, MachineInstr *DefMI, unsigned Slot, int LdSlot,
389        bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
390        VirtRegMap &vrm, const TargetRegisterClass* rc,
391        SmallVector<int, 4> &ReMatIds, const MachineLoopInfo *loopInfo,
392        unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse,
393        std::map<unsigned,unsigned> &MBBVRegsMap,
394        std::vector<LiveInterval*> &NewLIs);
395    void rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
396        LiveInterval::Ranges::const_iterator &I,
397        MachineInstr *OrigDefMI, MachineInstr *DefMI, unsigned Slot, int LdSlot,
398        bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
399        VirtRegMap &vrm, const TargetRegisterClass* rc,
400        SmallVector<int, 4> &ReMatIds, const MachineLoopInfo *loopInfo,
401        BitVector &SpillMBBs,
402        std::map<unsigned,std::vector<SRInfo> > &SpillIdxes,
403        BitVector &RestoreMBBs,
404        std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes,
405        std::map<unsigned,unsigned> &MBBVRegsMap,
406        std::vector<LiveInterval*> &NewLIs);
407
408    static LiveInterval createInterval(unsigned Reg);
409
410    void printRegName(unsigned reg) const;
411  };
412
413} // End llvm namespace
414
415#endif
416