LiveIntervalAnalysis.h revision 5c7e326585f3a543388ba871c3425f7664cd9143 
1//===-- LiveIntervalAnalysis.h - Live Interval Analysis ---------*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file was developed by the LLVM research group and is distributed under
6// the University of Illinois Open Source 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/ADT/DenseMap.h"
24#include "llvm/CodeGen/MachineFunctionPass.h"
25#include "llvm/CodeGen/LiveInterval.h"
26
27namespace llvm {
28
29  class LiveVariables;
30  class MRegisterInfo;
31  class TargetInstrInfo;
32  class VirtRegMap;
33
34  class LiveIntervals : public MachineFunctionPass {
35    MachineFunction* mf_;
36    const TargetMachine* tm_;
37    const MRegisterInfo* mri_;
38    const TargetInstrInfo* tii_;
39    LiveVariables* lv_;
40
41    /// MBB2IdxMap - The index of the first instruction in the specified basic
42    /// block.
43    std::vector<unsigned> MBB2IdxMap;
44
45    typedef std::map<MachineInstr*, unsigned> Mi2IndexMap;
46    Mi2IndexMap mi2iMap_;
47
48    typedef std::vector<MachineInstr*> Index2MiMap;
49    Index2MiMap i2miMap_;
50
51    typedef std::map<unsigned, LiveInterval> Reg2IntervalMap;
52    Reg2IntervalMap r2iMap_;
53
54    typedef DenseMap<unsigned> Reg2RegMap;
55    Reg2RegMap r2rMap_;
56
57    std::vector<bool> allocatableRegs_;
58
59  public:
60    struct CopyRec {
61      MachineInstr *MI;
62      unsigned SrcReg, DstReg;
63    };
64    CopyRec getCopyRec(MachineInstr *MI, unsigned SrcReg, unsigned DstReg) {
65      CopyRec R;
66      R.MI = MI;
67      R.SrcReg = SrcReg;
68      R.DstReg = DstReg;
69      return R;
70    }
71    struct InstrSlots {
72      enum {
73        LOAD  = 0,
74        USE   = 1,
75        DEF   = 2,
76        STORE = 3,
77        NUM   = 4
78      };
79    };
80
81    static unsigned getBaseIndex(unsigned index) {
82      return index - (index % InstrSlots::NUM);
83    }
84    static unsigned getBoundaryIndex(unsigned index) {
85      return getBaseIndex(index + InstrSlots::NUM - 1);
86    }
87    static unsigned getLoadIndex(unsigned index) {
88      return getBaseIndex(index) + InstrSlots::LOAD;
89    }
90    static unsigned getUseIndex(unsigned index) {
91      return getBaseIndex(index) + InstrSlots::USE;
92    }
93    static unsigned getDefIndex(unsigned index) {
94      return getBaseIndex(index) + InstrSlots::DEF;
95    }
96    static unsigned getStoreIndex(unsigned index) {
97      return getBaseIndex(index) + InstrSlots::STORE;
98    }
99
100    typedef Reg2IntervalMap::iterator iterator;
101    typedef Reg2IntervalMap::const_iterator const_iterator;
102    const_iterator begin() const { return r2iMap_.begin(); }
103    const_iterator end() const { return r2iMap_.end(); }
104    iterator begin() { return r2iMap_.begin(); }
105    iterator end() { return r2iMap_.end(); }
106    unsigned getNumIntervals() const { return r2iMap_.size(); }
107
108    LiveInterval &getInterval(unsigned reg) {
109      Reg2IntervalMap::iterator I = r2iMap_.find(reg);
110      assert(I != r2iMap_.end() && "Interval does not exist for register");
111      return I->second;
112    }
113
114    const LiveInterval &getInterval(unsigned reg) const {
115      Reg2IntervalMap::const_iterator I = r2iMap_.find(reg);
116      assert(I != r2iMap_.end() && "Interval does not exist for register");
117      return I->second;
118    }
119
120    /// getMBBStartIdx - Return the base index of the first instruction in the
121    /// specified MachineBasicBlock.
122    unsigned getMBBStartIdx(MachineBasicBlock *MBB) const {
123      return getMBBStartIdx(MBB->getNumber());
124    }
125
126    unsigned getMBBStartIdx(unsigned MBBNo) const {
127      assert(MBBNo < MBB2IdxMap.size() && "Invalid MBB number!");
128      return MBB2IdxMap[MBBNo];
129    }
130
131    /// getInstructionIndex - returns the base index of instr
132    unsigned getInstructionIndex(MachineInstr* instr) const {
133      Mi2IndexMap::const_iterator it = mi2iMap_.find(instr);
134      assert(it != mi2iMap_.end() && "Invalid instruction!");
135      return it->second;
136    }
137
138    /// getInstructionFromIndex - given an index in any slot of an
139    /// instruction return a pointer the instruction
140    MachineInstr* getInstructionFromIndex(unsigned index) const {
141      index /= InstrSlots::NUM; // convert index to vector index
142      assert(index < i2miMap_.size() &&
143             "index does not correspond to an instruction");
144      return i2miMap_[index];
145    }
146
147    std::vector<LiveInterval*> addIntervalsForSpills(const LiveInterval& i,
148                                                     VirtRegMap& vrm,
149                                                     int slot);
150
151    /// CreateNewLiveInterval - Create a new live interval with the given live
152    /// ranges. The new live interval will have an infinite spill weight.
153    LiveInterval &CreateNewLiveInterval(const LiveInterval *LI,
154                                        const std::vector<LiveRange> &LRs);
155
156    virtual void getAnalysisUsage(AnalysisUsage &AU) const;
157    virtual void releaseMemory();
158
159    /// runOnMachineFunction - pass entry point
160    virtual bool runOnMachineFunction(MachineFunction&);
161
162    /// print - Implement the dump method.
163    virtual void print(std::ostream &O, const Module* = 0) const;
164    void print(std::ostream *O, const Module* M = 0) const {
165      if (O) print(*O, M);
166    }
167
168  private:
169    /// RemoveMachineInstrFromMaps - This marks the specified machine instr as
170    /// deleted.
171    void RemoveMachineInstrFromMaps(MachineInstr *MI) {
172      // remove index -> MachineInstr and
173      // MachineInstr -> index mappings
174      Mi2IndexMap::iterator mi2i = mi2iMap_.find(MI);
175      if (mi2i != mi2iMap_.end()) {
176        i2miMap_[mi2i->second/InstrSlots::NUM] = 0;
177        mi2iMap_.erase(mi2i);
178      }
179    }
180
181    /// computeIntervals - Compute live intervals.
182    void computeIntervals();
183
184    /// joinIntervals - join compatible live intervals
185    void joinIntervals();
186
187    /// CopyCoallesceInMBB - Coallsece copies in the specified MBB, putting
188    /// copies that cannot yet be coallesced into the "TryAgain" list.
189    void CopyCoallesceInMBB(MachineBasicBlock *MBB,
190                            std::vector<CopyRec> &TryAgain);
191    /// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg,
192    /// which are the src/dst of the copy instruction CopyMI.  This returns true
193    /// if the copy was successfully coallesced away, or if it is never possible
194    /// to coallesce these this copy, due to register constraints.  It returns
195    /// false if it is not currently possible to coallesce this interval, but
196    /// it may be possible if other things get coallesced.
197    bool JoinCopy(MachineInstr *CopyMI, unsigned SrcReg, unsigned DstReg);
198
199    /// JoinIntervals - Attempt to join these two intervals.  On failure, this
200    /// returns false.  Otherwise, if one of the intervals being joined is a
201    /// physreg, this method always canonicalizes DestInt to be it.  The output
202    /// "SrcInt" will not have been modified, so we can use this information
203    /// below to update aliases.
204    bool JoinIntervals(LiveInterval &LHS, LiveInterval &RHS);
205
206    /// SimpleJoin - Attempt to join the specified interval into this one. The
207    /// caller of this method must guarantee that the RHS only contains a single
208    /// value number and that the RHS is not defined by a copy from this
209    /// interval.  This returns false if the intervals are not joinable, or it
210    /// joins them and returns true.
211    bool SimpleJoin(LiveInterval &LHS, LiveInterval &RHS);
212
213    /// handleRegisterDef - update intervals for a register def
214    /// (calls handlePhysicalRegisterDef and
215    /// handleVirtualRegisterDef)
216    void handleRegisterDef(MachineBasicBlock *MBB,
217                           MachineBasicBlock::iterator MI, unsigned MIIdx,
218                           unsigned reg);
219
220    /// handleVirtualRegisterDef - update intervals for a virtual
221    /// register def
222    void handleVirtualRegisterDef(MachineBasicBlock *MBB,
223                                  MachineBasicBlock::iterator MI,
224                                  unsigned MIIdx,
225                                  LiveInterval& interval);
226
227    /// handlePhysicalRegisterDef - update intervals for a physical register
228    /// def.
229    void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
230                                   MachineBasicBlock::iterator mi,
231                                   unsigned MIIdx,
232                                   LiveInterval &interval,
233                                   unsigned SrcReg);
234
235    /// Return true if the two specified registers belong to different
236    /// register classes.  The registers may be either phys or virt regs.
237    bool differingRegisterClasses(unsigned RegA, unsigned RegB) const;
238
239
240    bool AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB,
241                              MachineInstr *CopyMI);
242
243    bool overlapsAliases(const LiveInterval *lhs,
244                         const LiveInterval *rhs) const;
245
246    static LiveInterval createInterval(unsigned Reg);
247
248    LiveInterval &getOrCreateInterval(unsigned reg) {
249      Reg2IntervalMap::iterator I = r2iMap_.find(reg);
250      if (I == r2iMap_.end())
251        I = r2iMap_.insert(I, std::make_pair(reg, createInterval(reg)));
252      return I->second;
253    }
254
255    /// rep - returns the representative of this register
256    unsigned rep(unsigned Reg) {
257      unsigned Rep = r2rMap_[Reg];
258      if (Rep)
259        return r2rMap_[Reg] = rep(Rep);
260      return Reg;
261    }
262
263    void printRegName(unsigned reg) const;
264  };
265
266} // End llvm namespace
267
268#endif
269