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
|
//===-- 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;
// Merge a LiveInterval's segments. Guarantee no overlaps.
void LiveIntervalUnion::unify(LiveInterval &lvr) {
// Add this live virtual register to the union
LiveVirtRegs::iterator pos = std::upper_bound(lvrs_.begin(), lvrs_.end(),
&lvr, less_ptr<LiveInterval>());
assert(pos == lvrs_.end() || *pos != &lvr && "duplicate LVR insertion");
lvrs_.insert(pos, &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");
}
}
namespace {
// Keep LVRs sorted for fast membership test and extraction.
struct LessReg
: public std::binary_function<LiveInterval*, LiveInterval*, bool> {
bool operator()(const LiveInterval *left, const LiveInterval *right) const {
return left->reg < right->reg;
}
};
// Low-level helper to find the first segment in the range [segI,segEnd) that
// intersects with a live virtual register segment, or segI.start >= lvr.end
//
// This logic is tied to the underlying LiveSegments data structure. For now, we
// use a binary search within the vector to find the nearest starting position,
// then reverse iterate to find the first overlap.
//
// Upon entry we have segI.start < lvrSeg.end
// seg |--...
// \ .
// lvr ...-|
//
// After binary search, we have segI.start >= lvrSeg.start:
// seg |--...
// /
// lvr |--...
//
// Assuming intervals are disjoint, if an intersection exists, it must be the
// segment found or immediately behind it. We continue reverse iterating to
// return the first overlap.
//
// FIXME: support extract(), handle tombstones of extracted lvrs.
typedef LiveIntervalUnion::SegmentIter SegmentIter;
SegmentIter upperBound(SegmentIter segBegin,
SegmentIter segEnd,
const LiveRange &lvrSeg) {
assert(lvrSeg.end > segBegin->start && "segment iterator precondition");
// get the next LIU segment such that setg.start is not less than
// lvrSeg.start
SegmentIter segI = std::upper_bound(segBegin, segEnd, lvrSeg.start);
while (segI != segBegin) {
--segI;
if (lvrSeg.start >= segI->end)
return ++segI;
}
return segI;
}
} // end anonymous namespace
// 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"
ir.liuSegI_ = upperBound(ir.liuSegI_, liuEnd, *ir.lvrSegI_);
// 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);
}
|
