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 bool operator<(const LiveRange &LR) const {
40 return start < LR.start || (start == LR.start && end < LR.end);
42 bool operator==(const LiveRange &LR) const {
43 return start == LR.start && end == LR.end;
46 LiveRange(); // DO NOT IMPLEMENT
48 std::ostream& operator<<(std::ostream& os, const LiveRange &LR);
50 /// LiveInterval - This class represents some number of live ranges for a
51 /// register or value. This class also contains a bit of register allocator
54 typedef std::vector<LiveRange> Ranges;
55 unsigned reg; // the register of this interval
56 float weight; // weight of this interval
57 Ranges ranges; // the ranges in which this register is live
58 bool isDefinedOnce; // True if this interval contains one value.
60 LiveInterval(unsigned Reg, float Weight)
61 : reg(Reg), weight(Weight), isDefinedOnce(false) {
64 bool containsOneValue() const { return isDefinedOnce; }
66 bool empty() const { return ranges.empty(); }
68 /// start - Return the lowest numbered slot covered by interval.
69 unsigned start() const {
70 assert(!empty() && "empty interval for register");
71 return ranges.front().start;
74 /// end - return the maximum point of the interval of the whole,
76 unsigned end() const {
77 assert(!empty() && "empty interval for register");
78 return ranges.back().end;
81 bool expiredAt(unsigned index) const {
82 return end() <= (index + 1);
85 bool liveAt(unsigned index) const;
87 bool overlaps(const LiveInterval& other) const;
89 void addRange(LiveRange R);
91 void join(const LiveInterval& other);
93 bool operator<(const LiveInterval& other) const {
94 return start() < other.start();
97 bool operator==(const LiveInterval& other) const {
98 return reg == other.reg;
102 Ranges::iterator mergeRangesForward(Ranges::iterator it);
103 Ranges::iterator mergeRangesBackward(Ranges::iterator it);
106 std::ostream& operator<<(std::ostream& os, const LiveInterval& li);