LiveInterval.h revision 1bcf7a309eb46c66adc154ad9c8f0562653a8e13 
1//===-- llvm/CodeGen/LiveInterval.h - Interval representation ---*- 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 LiveRange and LiveInterval classes.  Given some
11// numbering of each the machine instructions an interval [i, j) is said to be a
12// live interval for register v if there is no instruction with number j' > j
13// such that v is live at j' and there is no instruction with number i' < i such
14// that v is live at i'. In this implementation intervals can have holes,
15// i.e. an interval might look like [1,20), [50,65), [1000,1001).  Each
16// individual range is represented as an instance of LiveRange, and the whole
17// interval is represented as an instance of LiveInterval.
18//
19//===----------------------------------------------------------------------===//
20
21#ifndef LLVM_CODEGEN_LIVEINTERVAL_H
22#define LLVM_CODEGEN_LIVEINTERVAL_H
23
24#include "llvm/ADT/SmallVector.h"
25#include <iosfwd>
26#include <vector>
27#include <cassert>
28
29namespace llvm {
30  class MRegisterInfo;
31
32  /// LiveRange structure - This represents a simple register range in the
33  /// program, with an inclusive start point and an exclusive end point.
34  /// These ranges are rendered as [start,end).
35  struct LiveRange {
36    unsigned start;  // Start point of the interval (inclusive)
37    unsigned end;    // End point of the interval (exclusive)
38    unsigned ValId;  // identifier for the value contained in this interval.
39
40    LiveRange(unsigned S, unsigned E, unsigned V) : start(S), end(E), ValId(V) {
41      assert(S < E && "Cannot create empty or backwards range");
42    }
43
44    /// contains - Return true if the index is covered by this range.
45    ///
46    bool contains(unsigned I) const {
47      return start <= I && I < end;
48    }
49
50    bool operator<(const LiveRange &LR) const {
51      return start < LR.start || (start == LR.start && end < LR.end);
52    }
53    bool operator==(const LiveRange &LR) const {
54      return start == LR.start && end == LR.end;
55    }
56
57    void dump() const;
58
59  private:
60    LiveRange(); // DO NOT IMPLEMENT
61  };
62  std::ostream& operator<<(std::ostream& os, const LiveRange &LR);
63
64  inline bool operator<(unsigned V, const LiveRange &LR) {
65    return V < LR.start;
66  }
67
68  inline bool operator<(const LiveRange &LR, unsigned V) {
69    return LR.start < V;
70  }
71
72  /// LiveInterval - This class represents some number of live ranges for a
73  /// register or value.  This class also contains a bit of register allocator
74  /// state.
75  struct LiveInterval {
76    typedef SmallVector<LiveRange,4> Ranges;
77    unsigned reg;        // the register of this interval
78    float weight;        // weight of this interval
79    Ranges ranges;       // the ranges in which this register is live
80  private:
81    /// ValueNumberInfo - If this value number is not defined by a copy, this
82    /// holds ~0,x.  If the value number is not in use, it contains ~1,x to
83    /// indicate that the value # is not used.  If the val# is defined by a
84    /// copy, the first entry is the instruction # of the copy, and the second
85    /// is the register number copied from.
86    SmallVector<std::pair<unsigned,unsigned>, 4> ValueNumberInfo;
87  public:
88
89    LiveInterval(unsigned Reg, float Weight)
90      : reg(Reg), weight(Weight) {
91    }
92
93    typedef Ranges::iterator iterator;
94    iterator begin() { return ranges.begin(); }
95    iterator end()   { return ranges.end(); }
96
97    typedef Ranges::const_iterator const_iterator;
98    const_iterator begin() const { return ranges.begin(); }
99    const_iterator end() const  { return ranges.end(); }
100
101
102    /// advanceTo - Advance the specified iterator to point to the LiveRange
103    /// containing the specified position, or end() if the position is past the
104    /// end of the interval.  If no LiveRange contains this position, but the
105    /// position is in a hole, this method returns an iterator pointing the the
106    /// LiveRange immediately after the hole.
107    iterator advanceTo(iterator I, unsigned Pos) {
108      if (Pos >= endNumber())
109        return end();
110      while (I->end <= Pos) ++I;
111      return I;
112    }
113
114    void swap(LiveInterval& other) {
115      std::swap(reg, other.reg);
116      std::swap(weight, other.weight);
117      std::swap(ranges, other.ranges);
118      std::swap(ValueNumberInfo, other.ValueNumberInfo);
119    }
120
121    bool containsOneValue() const { return ValueNumberInfo.size() == 1; }
122
123    unsigned getNumValNums() const { return ValueNumberInfo.size(); }
124
125    /// getNextValue - Create a new value number and return it.  MIIdx specifies
126    /// the instruction that defines the value number.
127    unsigned getNextValue(unsigned MIIdx, unsigned SrcReg) {
128      ValueNumberInfo.push_back(std::make_pair(MIIdx, SrcReg));
129      return ValueNumberInfo.size()-1;
130    }
131
132    /// getInstForValNum - Return the machine instruction index that defines the
133    /// specified value number.
134    unsigned getInstForValNum(unsigned ValNo) const {
135      //assert(ValNo < ValueNumberInfo.size());
136      return ValueNumberInfo[ValNo].first;
137    }
138
139    unsigned getSrcRegForValNum(unsigned ValNo) const {
140      //assert(ValNo < ValueNumberInfo.size());
141      if (ValueNumberInfo[ValNo].first < ~2U)
142        return ValueNumberInfo[ValNo].second;
143      return 0;
144    }
145
146    std::pair<unsigned, unsigned> getValNumInfo(unsigned ValNo) const {
147      //assert(ValNo < ValueNumberInfo.size());
148      return ValueNumberInfo[ValNo];
149    }
150
151    /// setValueNumberInfo - Change the value number info for the specified
152    /// value number.
153    void setValueNumberInfo(unsigned ValNo,
154                            const std::pair<unsigned, unsigned> &I){
155      ValueNumberInfo[ValNo] = I;
156    }
157
158    /// MergeValueNumberInto - This method is called when two value nubmers
159    /// are found to be equivalent.  This eliminates V1, replacing all
160    /// LiveRanges with the V1 value number with the V2 value number.  This can
161    /// cause merging of V1/V2 values numbers and compaction of the value space.
162    void MergeValueNumberInto(unsigned V1, unsigned V2);
163
164    /// MergeInClobberRanges - For any live ranges that are not defined in the
165    /// current interval, but are defined in the Clobbers interval, mark them
166    /// used with an unknown definition value.
167    void MergeInClobberRanges(const LiveInterval &Clobbers);
168
169
170    /// MergeRangesInAsValue - Merge all of the intervals in RHS into this live
171    /// interval as the specified value number.  The LiveRanges in RHS are
172    /// allowed to overlap with LiveRanges in the current interval, but only if
173    /// the overlapping LiveRanges have the specified value number.
174    void MergeRangesInAsValue(const LiveInterval &RHS, unsigned LHSValNo);
175
176    bool empty() const { return ranges.empty(); }
177
178    /// beginNumber - Return the lowest numbered slot covered by interval.
179    unsigned beginNumber() const {
180      assert(!empty() && "empty interval for register");
181      return ranges.front().start;
182    }
183
184    /// endNumber - return the maximum point of the interval of the whole,
185    /// exclusive.
186    unsigned endNumber() const {
187      assert(!empty() && "empty interval for register");
188      return ranges.back().end;
189    }
190
191    bool expiredAt(unsigned index) const {
192      return index >= endNumber();
193    }
194
195    bool liveAt(unsigned index) const;
196
197    /// getLiveRangeContaining - Return the live range that contains the
198    /// specified index, or null if there is none.
199    const LiveRange *getLiveRangeContaining(unsigned Idx) const {
200      const_iterator I = FindLiveRangeContaining(Idx);
201      return I == end() ? 0 : &*I;
202    }
203
204    /// FindLiveRangeContaining - Return an iterator to the live range that
205    /// contains the specified index, or end() if there is none.
206    const_iterator FindLiveRangeContaining(unsigned Idx) const;
207
208    /// FindLiveRangeContaining - Return an iterator to the live range that
209    /// contains the specified index, or end() if there is none.
210    iterator FindLiveRangeContaining(unsigned Idx);
211
212    /// getOverlapingRanges - Given another live interval which is defined as a
213    /// copy from this one, return a list of all of the live ranges where the
214    /// two overlap and have different value numbers.
215    void getOverlapingRanges(const LiveInterval &Other, unsigned CopyIdx,
216                             std::vector<LiveRange*> &Ranges);
217
218    /// overlaps - Return true if the intersection of the two live intervals is
219    /// not empty.
220    bool overlaps(const LiveInterval& other) const {
221      return overlapsFrom(other, other.begin());
222    }
223
224    /// overlapsFrom - Return true if the intersection of the two live intervals
225    /// is not empty.  The specified iterator is a hint that we can begin
226    /// scanning the Other interval starting at I.
227    bool overlapsFrom(const LiveInterval& other, const_iterator I) const;
228
229    /// addRange - Add the specified LiveRange to this interval, merging
230    /// intervals as appropriate.  This returns an iterator to the inserted live
231    /// range (which may have grown since it was inserted.
232    void addRange(LiveRange LR) {
233      addRangeFrom(LR, ranges.begin());
234    }
235
236    /// join - Join two live intervals (this, and other) together.  This applies
237    /// mappings to the value numbers in the LHS/RHS intervals as specified.  If
238    /// the intervals are not joinable, this aborts.
239    void join(LiveInterval &Other, int *ValNoAssignments,
240              int *RHSValNoAssignments,
241              SmallVector<std::pair<unsigned,unsigned>,16> &NewValueNumberInfo);
242
243    /// removeRange - Remove the specified range from this interval.  Note that
244    /// the range must already be in this interval in its entirety.
245    void removeRange(unsigned Start, unsigned End);
246
247    void removeRange(LiveRange LR) {
248      removeRange(LR.start, LR.end);
249    }
250
251    bool operator<(const LiveInterval& other) const {
252      return beginNumber() < other.beginNumber();
253    }
254
255    void print(std::ostream &OS, const MRegisterInfo *MRI = 0) const;
256    void dump() const;
257
258  private:
259    Ranges::iterator addRangeFrom(LiveRange LR, Ranges::iterator From);
260    void extendIntervalEndTo(Ranges::iterator I, unsigned NewEnd);
261    Ranges::iterator extendIntervalStartTo(Ranges::iterator I, unsigned NewStr);
262    LiveInterval& operator=(const LiveInterval& rhs); // DO NOT IMPLEMENT
263  };
264
265  inline std::ostream &operator<<(std::ostream &OS, const LiveInterval &LI) {
266    LI.print(OS);
267    return OS;
268  }
269}
270
271#endif
272