1 //===-- llvm/CodeGen/LiveInterval.h - Interval representation ---*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
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' abd 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.
19 //===----------------------------------------------------------------------===//
21 #ifndef LLVM_CODEGEN_LIVEINTERVAL_H
22 #define LLVM_CODEGEN_LIVEINTERVAL_H
29 /// LiveRange structure - This represents a simple register range in the
30 /// program, with an inclusive start point and an exclusive end point.
31 /// These ranges are rendered as [start,end).
33 unsigned start; // Start point of the interval (inclusive)
34 unsigned end; // End point of the interval (exclusive)
35 LiveRange(unsigned S, unsigned E) : start(S), end(E) {
36 assert(S < E && "Cannot create empty or backwards range");
39 /// contains - Return true if the index is covered by this range.
41 bool contains(unsigned I) const {
42 return start <= I && I < end;
45 bool operator<(const LiveRange &LR) const {
46 return start < LR.start || (start == LR.start && end < LR.end);
48 bool operator==(const LiveRange &LR) const {
49 return start == LR.start && end == LR.end;
52 LiveRange(); // DO NOT IMPLEMENT
54 std::ostream& operator<<(std::ostream& os, const LiveRange &LR);
56 inline bool operator<(unsigned V, const LiveRange &LR) {
61 /// LiveInterval - This class represents some number of live ranges for a
62 /// register or value. This class also contains a bit of register allocator
65 typedef std::vector<LiveRange> Ranges;
66 unsigned reg; // the register of this interval
67 float weight; // weight of this interval
68 Ranges ranges; // the ranges in which this register is live
69 bool isDefinedOnce; // True if this interval contains one value.
71 LiveInterval(unsigned Reg, float Weight)
72 : reg(Reg), weight(Weight), isDefinedOnce(false) {
75 bool containsOneValue() const { return isDefinedOnce; }
77 bool empty() const { return ranges.empty(); }
79 /// start - Return the lowest numbered slot covered by interval.
80 unsigned start() const {
81 assert(!empty() && "empty interval for register");
82 return ranges.front().start;
85 /// end - return the maximum point of the interval of the whole,
87 unsigned end() const {
88 assert(!empty() && "empty interval for register");
89 return ranges.back().end;
92 bool expiredAt(unsigned index) const {
93 return end() <= (index + 1);
96 bool liveAt(unsigned index) const;
98 bool overlaps(const LiveInterval& other) const;
100 void addRange(LiveRange R);
102 void join(const LiveInterval& other);
104 bool operator<(const LiveInterval& other) const {
105 return start() < other.start();
108 bool operator==(const LiveInterval& other) const {
109 return reg == other.reg;
113 Ranges::iterator mergeRangesForward(Ranges::iterator it);
114 Ranges::iterator mergeRangesBackward(Ranges::iterator it);
117 std::ostream& operator<<(std::ostream& os, const LiveInterval& li);