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