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