-// 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.
-typedef LiveIntervalUnion::SegmentIter SegmentIter;
-static 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;
+// Remove a live virtual register's segments from this union.
+void LiveIntervalUnion::extract(LiveInterval &VirtReg) {
+ if (VirtReg.empty())
+ return;
+ ++Tag;
+
+ // Remove each of the virtual register's live segments from the map.
+ LiveInterval::iterator RegPos = VirtReg.begin();
+ LiveInterval::iterator RegEnd = VirtReg.end();
+ SegmentIter SegPos = Segments.find(RegPos->start);
+
+ for (;;) {
+ assert(SegPos.value() == &VirtReg && "Inconsistent LiveInterval");
+ SegPos.erase();
+ if (!SegPos.valid())
+ return;
+
+ // Skip all segments that may have been coalesced.
+ RegPos = VirtReg.advanceTo(RegPos, SegPos.start());
+ if (RegPos == RegEnd)
+ return;
+
+ SegPos.advanceTo(RegPos->start);