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 inline bool operator<(unsigned V, const LiveRange &LR) {
55 /// LiveInterval - This class represents some number of live ranges for a
56 /// register or value. This class also contains a bit of register allocator
59 typedef std::vector<LiveRange> Ranges;
60 unsigned reg; // the register of this interval
61 float weight; // weight of this interval
62 Ranges ranges; // the ranges in which this register is live
63 bool isDefinedOnce; // True if this interval contains one value.
65 LiveInterval(unsigned Reg, float Weight)
66 : reg(Reg), weight(Weight), isDefinedOnce(false) {
69 bool containsOneValue() const { return isDefinedOnce; }
71 bool empty() const { return ranges.empty(); }
73 /// start - Return the lowest numbered slot covered by interval.
74 unsigned start() const {
75 assert(!empty() && "empty interval for register");
76 return ranges.front().start;
79 /// end - return the maximum point of the interval of the whole,
81 unsigned end() const {
82 assert(!empty() && "empty interval for register");
83 return ranges.back().end;
86 bool expiredAt(unsigned index) const {
87 return end() <= (index + 1);
90 bool liveAt(unsigned index) const;
92 bool overlaps(const LiveInterval& other) const;
94 void addRange(LiveRange R);
96 void join(const LiveInterval& other);
98 bool operator<(const LiveInterval& other) const {
99 return start() < other.start();
102 bool operator==(const LiveInterval& other) const {
103 return reg == other.reg;
107 Ranges::iterator mergeRangesForward(Ranges::iterator it);
108 Ranges::iterator mergeRangesBackward(Ranges::iterator it);
111 std::ostream& operator<<(std::ostream& os, const LiveInterval& li);