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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
|
//===-- LiveIntervalUnion.cpp - Live interval union data structure --------===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// LiveIntervalUnion represents a coalesced set of live intervals. This may be
// used during coalescing to represent a congruence class, or during register
// allocation to model liveness of a physical register.
//
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "regalloc"
#include "LiveIntervalUnion.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
using namespace llvm;
// Find the first segment in the range [segBegin,segments_.end()) that
// intersects with seg. If no intersection is found, return the first segI
// such that segI.start >= seg.end
//
// This logic is tied to the underlying LiveSegments data structure. For now, we
// use set::upper_bound to find the nearest starting position,
// then reverse iterate to find the first overlap.
//
// Upon entry we have segBegin.start < seg.end
// seg |--...
// \ .
// lvr ...-|
//
// After set::upper_bound, we have segI.start >= seg.start:
// seg |--...
// /
// lvr |--...
//
// Assuming intervals are disjoint, if an intersection exists, it must be the
// segment found or the one immediately preceeding it. We continue reverse
// iterating to return the first overlapping segment.
LiveIntervalUnion::SegmentIter
LiveIntervalUnion::upperBound(SegmentIter segBegin,
const LiveSegment &seg) {
assert(seg.end > segBegin->start && "segment iterator precondition");
// get the next LIU segment such that segI->start is not less than seg.start
//
// FIXME: Once we have a B+tree, we can make good use of segBegin as a hint to
// upper_bound. For now, we're forced to search again from the root each time.
SegmentIter segI = segments_.upper_bound(seg);
while (segI != segBegin) {
--segI;
if (seg.start >= segI->end)
return ++segI;
}
return segI;
}
// Merge a LiveInterval's segments. Guarantee no overlaps.
//
// Consider coalescing adjacent segments to save space, even though it makes
// extraction more complicated.
void LiveIntervalUnion::unify(LiveInterval &lvr) {
// Insert each of the virtual register's live segments into the map
SegmentIter segPos = segments_.begin();
for (LiveInterval::iterator lvrI = lvr.begin(), lvrEnd = lvr.end();
lvrI != lvrEnd; ++lvrI ) {
LiveSegment segment(lvrI->start, lvrI->end, &lvr);
segPos = segments_.insert(segPos, segment);
assert(*segPos == segment && "need equal val for equal key");
#ifndef NDEBUG
// check for overlap (inductively)
if (segPos != segments_.begin()) {
SegmentIter prevPos = segPos;
--prevPos;
assert(prevPos->end <= segment.start && "overlapping segments" );
}
SegmentIter nextPos = segPos;
++nextPos;
if (nextPos != segments_.end())
assert(segment.end <= nextPos->start && "overlapping segments" );
#endif // NDEBUG
}
}
// Remove a live virtual register's segments from this union.
void LiveIntervalUnion::extract(const LiveInterval &lvr) {
// Remove each of the virtual register's live segments from the map.
SegmentIter segPos = segments_.begin();
for (LiveInterval::const_iterator lvrI = lvr.begin(), lvrEnd = lvr.end();
lvrI != lvrEnd; ++lvrI) {
LiveSegment seg(lvrI->start, lvrI->end, const_cast<LiveInterval*>(&lvr));
segPos = upperBound(segPos, seg);
assert(segPos != segments_.end() && "missing lvr segment");
segments_.erase(segPos++);
}
}
// Private interface accessed by Query.
//
// Find a pair of segments that intersect, one in the live virtual register
// (LiveInterval), and the other in this LiveIntervalUnion. The caller (Query)
// is responsible for advancing the LiveIntervalUnion segments to find a
// "notable" intersection, which requires query-specific logic.
//
// This design assumes only a fast mechanism for intersecting a single live
// virtual register segment with a set of LiveIntervalUnion segments. This may
// be ok since most LVRs have very few segments. If we had a data
// structure that optimizd MxN intersection of segments, then we would bypass
// the loop that advances within the LiveInterval.
//
// If no intersection exists, set lvrI = lvrEnd, and set segI to the first
// segment whose start point is greater than LiveInterval's end point.
//
// Assumes that segments are sorted by start position in both
// LiveInterval and LiveSegments.
void LiveIntervalUnion::Query::findIntersection(InterferenceResult &ir) const {
LiveInterval::iterator lvrEnd = lvr_->end();
SegmentIter liuEnd = liu_->end();
while (ir.liuSegI_ != liuEnd) {
// Slowly advance the live virtual reg iterator until we surpass the next
// segment in this union. If this is ever used for coalescing of fixed
// registers and we have a LiveInterval with thousands of segments, then use
// upper bound instead.
while (ir.lvrSegI_ != lvrEnd && ir.lvrSegI_->end <= ir.liuSegI_->start)
++ir.lvrSegI_;
if (ir.lvrSegI_ == lvrEnd)
break;
// lvrSegI_ may have advanced far beyond liuSegI_,
// do a fast intersection test to "catch up"
LiveSegment seg(ir.lvrSegI_->start, ir.lvrSegI_->end, lvr_);
ir.liuSegI_ = liu_->upperBound(ir.liuSegI_, seg);
// Check if no liuSegI_ exists with lvrSegI_->start < liuSegI_.end
if (ir.liuSegI_ == liuEnd)
break;
if (ir.liuSegI_->start < ir.lvrSegI_->end) {
assert(overlap(*ir.lvrSegI_, *ir.liuSegI_) && "upperBound postcondition");
break;
}
}
if (ir.liuSegI_ == liuEnd)
ir.lvrSegI_ = lvrEnd;
}
// Find the first intersection, and cache interference info
// (retain segment iterators into both lvr_ and liu_).
LiveIntervalUnion::InterferenceResult
LiveIntervalUnion::Query::firstInterference() {
if (firstInterference_ != LiveIntervalUnion::InterferenceResult()) {
return firstInterference_;
}
firstInterference_ = InterferenceResult(lvr_->begin(), liu_->begin());
findIntersection(firstInterference_);
return firstInterference_;
}
// Treat the result as an iterator and advance to the next interfering pair
// of segments. This is a plain iterator with no filter.
bool LiveIntervalUnion::Query::nextInterference(InterferenceResult &ir) const {
assert(isInterference(ir) && "iteration past end of interferences");
// Advance either the lvr or liu segment to ensure that we visit all unique
// overlapping pairs.
if (ir.lvrSegI_->end < ir.liuSegI_->end) {
if (++ir.lvrSegI_ == lvr_->end())
return false;
}
else {
if (++ir.liuSegI_ == liu_->end()) {
ir.lvrSegI_ = lvr_->end();
return false;
}
}
if (overlap(*ir.lvrSegI_, *ir.liuSegI_))
return true;
// find the next intersection
findIntersection(ir);
return isInterference(ir);
}
|
