Deleted Added
sdiff udiff text old ( 224145 ) new ( 226633 )
full compact
LiveIntervalUnion.cpp (224145) LiveIntervalUnion.cpp (226633)
1//===-- LiveIntervalUnion.cpp - Live interval union data structure --------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//

--- 77 unchanged lines hidden (view full) ---

86 }
87 for (LiveSegments::const_iterator SI = Segments.begin(); SI.valid(); ++SI) {
88 OS << " [" << SI.start() << ' ' << SI.stop() << "):"
89 << PrintReg(SI.value()->reg, TRI);
90 }
91 OS << '\n';
92}
93
1//===-- LiveIntervalUnion.cpp - Live interval union data structure --------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//

--- 77 unchanged lines hidden (view full) ---

86 }
87 for (LiveSegments::const_iterator SI = Segments.begin(); SI.valid(); ++SI) {
88 OS << " [" << SI.start() << ' ' << SI.stop() << "):"
89 << PrintReg(SI.value()->reg, TRI);
90 }
91 OS << '\n';
92}
93
94void LiveIntervalUnion::InterferenceResult::print(raw_ostream &OS,
95 const TargetRegisterInfo *TRI) const {
96 OS << '[' << start() << ';' << stop() << "):"
97 << PrintReg(interference()->reg, TRI);
98}
99
100void LiveIntervalUnion::Query::print(raw_ostream &OS,
101 const TargetRegisterInfo *TRI) {
102 OS << "Interferences with ";
103 LiveUnion->print(OS, TRI);
104 InterferenceResult IR = firstInterference();
105 while (isInterference(IR)) {
106 OS << " ";
107 IR.print(OS, TRI);
108 OS << '\n';
109 nextInterference(IR);
110 }
111}
112
113#ifndef NDEBUG
114// Verify the live intervals in this union and add them to the visited set.
115void LiveIntervalUnion::verify(LiveVirtRegBitSet& VisitedVRegs) {
116 for (SegmentIter SI = Segments.begin(); SI.valid(); ++SI)
117 VisitedVRegs.set(SI.value()->reg);
118}
119#endif //!NDEBUG
120
94#ifndef NDEBUG
95// Verify the live intervals in this union and add them to the visited set.
96void LiveIntervalUnion::verify(LiveVirtRegBitSet& VisitedVRegs) {
97 for (SegmentIter SI = Segments.begin(); SI.valid(); ++SI)
98 VisitedVRegs.set(SI.value()->reg);
99}
100#endif //!NDEBUG
101
121// Private interface accessed by Query.
122//
123// Find a pair of segments that intersect, one in the live virtual register
124// (LiveInterval), and the other in this LiveIntervalUnion. The caller (Query)
125// is responsible for advancing the LiveIntervalUnion segments to find a
126// "notable" intersection, which requires query-specific logic.
127//
128// This design assumes only a fast mechanism for intersecting a single live
129// virtual register segment with a set of LiveIntervalUnion segments. This may
130// be ok since most virtual registers have very few segments. If we had a data
131// structure that optimizd MxN intersection of segments, then we would bypass
132// the loop that advances within the LiveInterval.
133//
134// If no intersection exists, set VirtRegI = VirtRegEnd, and set SI to the first
135// segment whose start point is greater than LiveInterval's end point.
136//
137// Assumes that segments are sorted by start position in both
138// LiveInterval and LiveSegments.
139void LiveIntervalUnion::Query::findIntersection(InterferenceResult &IR) const {
140 // Search until reaching the end of the LiveUnion segments.
141 LiveInterval::iterator VirtRegEnd = VirtReg->end();
142 if (IR.VirtRegI == VirtRegEnd)
143 return;
144 while (IR.LiveUnionI.valid()) {
145 // Slowly advance the live virtual reg iterator until we surpass the next
146 // segment in LiveUnion.
147 //
148 // Note: If this is ever used for coalescing of fixed registers and we have
149 // a live vreg with thousands of segments, then change this code to use
150 // upperBound instead.
151 IR.VirtRegI = VirtReg->advanceTo(IR.VirtRegI, IR.LiveUnionI.start());
152 if (IR.VirtRegI == VirtRegEnd)
153 break; // Retain current (nonoverlapping) LiveUnionI
154
155 // VirtRegI may have advanced far beyond LiveUnionI, catch up.
156 IR.LiveUnionI.advanceTo(IR.VirtRegI->start);
157
158 // Check if no LiveUnionI exists with VirtRegI->Start < LiveUnionI.end
159 if (!IR.LiveUnionI.valid())
160 break;
161 if (IR.LiveUnionI.start() < IR.VirtRegI->end) {
162 assert(overlap(*IR.VirtRegI, IR.LiveUnionI) &&
163 "upperBound postcondition");
164 break;
165 }
166 }
167 if (!IR.LiveUnionI.valid())
168 IR.VirtRegI = VirtRegEnd;
169}
170
171// Find the first intersection, and cache interference info
172// (retain segment iterators into both VirtReg and LiveUnion).
173const LiveIntervalUnion::InterferenceResult &
174LiveIntervalUnion::Query::firstInterference() {
175 if (CheckedFirstInterference)
176 return FirstInterference;
177 CheckedFirstInterference = true;
178 InterferenceResult &IR = FirstInterference;
179 IR.LiveUnionI.setMap(LiveUnion->getMap());
180
181 // Quickly skip interference check for empty sets.
182 if (VirtReg->empty() || LiveUnion->empty()) {
183 IR.VirtRegI = VirtReg->end();
184 } else if (VirtReg->beginIndex() < LiveUnion->startIndex()) {
185 // VirtReg starts first, perform double binary search.
186 IR.VirtRegI = VirtReg->find(LiveUnion->startIndex());
187 if (IR.VirtRegI != VirtReg->end())
188 IR.LiveUnionI.find(IR.VirtRegI->start);
189 } else {
190 // LiveUnion starts first, perform double binary search.
191 IR.LiveUnionI.find(VirtReg->beginIndex());
192 if (IR.LiveUnionI.valid())
193 IR.VirtRegI = VirtReg->find(IR.LiveUnionI.start());
194 else
195 IR.VirtRegI = VirtReg->end();
196 }
197 findIntersection(FirstInterference);
198 assert((IR.VirtRegI == VirtReg->end() || IR.LiveUnionI.valid())
199 && "Uninitialized iterator");
200 return FirstInterference;
201}
202
203// Treat the result as an iterator and advance to the next interfering pair
204// of segments. This is a plain iterator with no filter.
205bool LiveIntervalUnion::Query::nextInterference(InterferenceResult &IR) const {
206 assert(isInterference(IR) && "iteration past end of interferences");
207
208 // Advance either the VirtReg or LiveUnion segment to ensure that we visit all
209 // unique overlapping pairs.
210 if (IR.VirtRegI->end < IR.LiveUnionI.stop()) {
211 if (++IR.VirtRegI == VirtReg->end())
212 return false;
213 }
214 else {
215 if (!(++IR.LiveUnionI).valid()) {
216 IR.VirtRegI = VirtReg->end();
217 return false;
218 }
219 }
220 // Short-circuit findIntersection() if possible.
221 if (overlap(*IR.VirtRegI, IR.LiveUnionI))
222 return true;
223
224 // Find the next intersection.
225 findIntersection(IR);
226 return isInterference(IR);
227}
228
229// Scan the vector of interfering virtual registers in this union. Assume it's
230// quite small.
231bool LiveIntervalUnion::Query::isSeenInterference(LiveInterval *VirtReg) const {
232 SmallVectorImpl<LiveInterval*>::const_iterator I =
233 std::find(InterferingVRegs.begin(), InterferingVRegs.end(), VirtReg);
234 return I != InterferingVRegs.end();
235}
236
102// Scan the vector of interfering virtual registers in this union. Assume it's
103// quite small.
104bool LiveIntervalUnion::Query::isSeenInterference(LiveInterval *VirtReg) const {
105 SmallVectorImpl<LiveInterval*>::const_iterator I =
106 std::find(InterferingVRegs.begin(), InterferingVRegs.end(), VirtReg);
107 return I != InterferingVRegs.end();
108}
109
237// Count the number of virtual registers in this union that interfere with this
110// Collect virtual registers in this union that interfere with this
238// query's live virtual register.
239//
111// query's live virtual register.
112//
240// The number of times that we either advance IR.VirtRegI or call
241// LiveUnion.upperBound() will be no more than the number of holes in
242// VirtReg. So each invocation of collectInterferingVRegs() takes
243// time proportional to |VirtReg Holes| * time(LiveUnion.upperBound()).
113// The query state is one of:
244//
114//
245// For comments on how to speed it up, see Query::findIntersection().
115// 1. CheckedFirstInterference == false: Iterators are uninitialized.
116// 2. SeenAllInterferences == true: InterferingVRegs complete, iterators unused.
117// 3. Iterators left at the last seen intersection.
118//
246unsigned LiveIntervalUnion::Query::
247collectInterferingVRegs(unsigned MaxInterferingRegs) {
119unsigned LiveIntervalUnion::Query::
120collectInterferingVRegs(unsigned MaxInterferingRegs) {
248 InterferenceResult IR = firstInterference();
249 LiveInterval::iterator VirtRegEnd = VirtReg->end();
250 LiveInterval *RecentInterferingVReg = NULL;
251 if (IR.VirtRegI != VirtRegEnd) while (IR.LiveUnionI.valid()) {
252 // Advance the union's iterator to reach an unseen interfering vreg.
253 do {
254 if (IR.LiveUnionI.value() == RecentInterferingVReg)
255 continue;
121 // Fast path return if we already have the desired information.
122 if (SeenAllInterferences || InterferingVRegs.size() >= MaxInterferingRegs)
123 return InterferingVRegs.size();
256
124
257 if (!isSeenInterference(IR.LiveUnionI.value()))
258 break;
125 // Set up iterators on the first call.
126 if (!CheckedFirstInterference) {
127 CheckedFirstInterference = true;
259
128
260 // Cache the most recent interfering vreg to bypass isSeenInterference.
261 RecentInterferingVReg = IR.LiveUnionI.value();
129 // Quickly skip interference check for empty sets.
130 if (VirtReg->empty() || LiveUnion->empty()) {
131 SeenAllInterferences = true;
132 return 0;
133 }
262
134
263 } while ((++IR.LiveUnionI).valid());
264 if (!IR.LiveUnionI.valid())
265 break;
135 // In most cases, the union will start before VirtReg.
136 VirtRegI = VirtReg->begin();
137 LiveUnionI.setMap(LiveUnion->getMap());
138 LiveUnionI.find(VirtRegI->start);
139 }
266
140
267 // Advance the VirtReg iterator until surpassing the next segment in
268 // LiveUnion.
269 IR.VirtRegI = VirtReg->advanceTo(IR.VirtRegI, IR.LiveUnionI.start());
270 if (IR.VirtRegI == VirtRegEnd)
271 break;
141 LiveInterval::iterator VirtRegEnd = VirtReg->end();
142 LiveInterval *RecentReg = 0;
143 while (LiveUnionI.valid()) {
144 assert(VirtRegI != VirtRegEnd && "Reached end of VirtReg");
272
145
273 // Check for intersection with the union's segment.
274 if (overlap(*IR.VirtRegI, IR.LiveUnionI)) {
146 // Check for overlapping interference.
147 while (VirtRegI->start < LiveUnionI.stop() &&
148 VirtRegI->end > LiveUnionI.start()) {
149 // This is an overlap, record the interfering register.
150 LiveInterval *VReg = LiveUnionI.value();
151 if (VReg != RecentReg && !isSeenInterference(VReg)) {
152 RecentReg = VReg;
153 InterferingVRegs.push_back(VReg);
154 if (InterferingVRegs.size() >= MaxInterferingRegs)
155 return InterferingVRegs.size();
156 }
157 // This LiveUnion segment is no longer interesting.
158 if (!(++LiveUnionI).valid()) {
159 SeenAllInterferences = true;
160 return InterferingVRegs.size();
161 }
162 }
275
163
276 if (!IR.LiveUnionI.value()->isSpillable())
277 SeenUnspillableVReg = true;
164 // The iterators are now not overlapping, LiveUnionI has been advanced
165 // beyond VirtRegI.
166 assert(VirtRegI->end <= LiveUnionI.start() && "Expected non-overlap");
278
167
279 if (InterferingVRegs.size() == MaxInterferingRegs)
280 // Leave SeenAllInterferences set to false to indicate that at least one
281 // interference exists beyond those we collected.
282 return MaxInterferingRegs;
168 // Advance the iterator that ends first.
169 VirtRegI = VirtReg->advanceTo(VirtRegI, LiveUnionI.start());
170 if (VirtRegI == VirtRegEnd)
171 break;
283
172
284 InterferingVRegs.push_back(IR.LiveUnionI.value());
285
286 // Cache the most recent interfering vreg to bypass isSeenInterference.
287 RecentInterferingVReg = IR.LiveUnionI.value();
288 ++IR.LiveUnionI;
289
173 // Detect overlap, handle above.
174 if (VirtRegI->start < LiveUnionI.stop())
290 continue;
175 continue;
291 }
292 // VirtRegI may have advanced far beyond LiveUnionI,
293 // do a fast intersection test to "catch up"
294 IR.LiveUnionI.advanceTo(IR.VirtRegI->start);
176
177 // Still not overlapping. Catch up LiveUnionI.
178 LiveUnionI.advanceTo(VirtRegI->start);
295 }
296 SeenAllInterferences = true;
297 return InterferingVRegs.size();
298}
299
300bool LiveIntervalUnion::Query::checkLoopInterference(MachineLoopRange *Loop) {
301 // VirtReg is likely live throughout the loop, so start by checking LIU-Loop
302 // overlaps.

--- 23 unchanged lines hidden --- 		179 }
180 SeenAllInterferences = true;
181 return InterferingVRegs.size();
182}
183
184bool LiveIntervalUnion::Query::checkLoopInterference(MachineLoopRange *Loop) {
185 // VirtReg is likely live throughout the loop, so start by checking LIU-Loop
186 // overlaps.

--- 23 unchanged lines hidden ---