1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
//===-- llvm/CodeGen/LiveInterval.h - Interval representation ---*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the LiveRange and LiveInterval classes. Given some
// numbering of each the machine instructions an interval [i, j) is said to be a
// live interval for register v if there is no instruction with number j' > j
// such that v is live at j' abd there is no instruction with number i' < i such
// that v is live at i'. In this implementation intervals can have holes,
// i.e. an interval might look like [1,20), [50,65), [1000,1001). Each
// individual range is represented as an instance of LiveRange, and the whole
// interval is represented as an instance of LiveInterval.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_CODEGEN_LIVEINTERVAL_H
#define LLVM_CODEGEN_LIVEINTERVAL_H
#include <iosfwd>
#include <vector>
#include <cassert>
namespace llvm {
/// LiveRange structure - This represents a simple register range in the
/// program, with an inclusive start point and an exclusive end point.
/// These ranges are rendered as [start,end).
struct LiveRange {
unsigned start; // Start point of the interval (inclusive)
unsigned end; // End point of the interval (exclusive)
LiveRange(unsigned S, unsigned E) : start(S), end(E) {
assert(S < E && "Cannot create empty or backwards range");
}
bool operator<(const LiveRange &LR) const {
return start < LR.start || (start == LR.start && end < LR.end);
}
bool operator==(const LiveRange &LR) const {
return start == LR.start && end == LR.end;
}
private:
LiveRange(); // DO NOT IMPLEMENT
};
std::ostream& operator<<(std::ostream& os, const LiveRange &LR);
/// LiveInterval - This class represents some number of live ranges for a
/// register or value. This class also contains a bit of register allocator
/// state.
struct LiveInterval {
typedef std::vector<LiveRange> Ranges;
unsigned reg; // the register of this interval
float weight; // weight of this interval
Ranges ranges; // the ranges in which this register is live
bool isDefinedOnce; // True if this interval contains one value.
LiveInterval(unsigned Reg, float Weight)
: reg(Reg), weight(Weight), isDefinedOnce(false) {
}
bool containsOneValue() const { return isDefinedOnce; }
bool empty() const { return ranges.empty(); }
/// start - Return the lowest numbered slot covered by interval.
unsigned start() const {
assert(!empty() && "empty interval for register");
return ranges.front().start;
}
/// end - return the maximum point of the interval of the whole,
/// exclusive.
unsigned end() const {
assert(!empty() && "empty interval for register");
return ranges.back().end;
}
bool expiredAt(unsigned index) const {
return end() <= (index + 1);
}
bool liveAt(unsigned index) const;
bool overlaps(const LiveInterval& other) const;
void addRange(LiveRange R);
void join(const LiveInterval& other);
bool operator<(const LiveInterval& other) const {
return start() < other.start();
}
bool operator==(const LiveInterval& other) const {
return reg == other.reg;
}
private:
Ranges::iterator mergeRangesForward(Ranges::iterator it);
Ranges::iterator mergeRangesBackward(Ranges::iterator it);
};
std::ostream& operator<<(std::ostream& os, const LiveInterval& li);
}
#endif
|
