-// 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 virtual registers 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 VirtRegI = VirtRegEnd, and set SI 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 {
- // Search until reaching the end of the LiveUnion segments.
- LiveInterval::iterator VirtRegEnd = VirtReg->end();
- if (IR.VirtRegI == VirtRegEnd)
- return;
- while (IR.LiveUnionI.valid()) {
- // Slowly advance the live virtual reg iterator until we surpass the next
- // segment in LiveUnion.
- //
- // Note: If this is ever used for coalescing of fixed registers and we have
- // a live vreg with thousands of segments, then change this code to use
- // upperBound instead.
- IR.VirtRegI = VirtReg->advanceTo(IR.VirtRegI, IR.LiveUnionI.start());
- if (IR.VirtRegI == VirtRegEnd)
- break; // Retain current (nonoverlapping) LiveUnionI
-
- // VirtRegI may have advanced far beyond LiveUnionI, catch up.
- IR.LiveUnionI.advanceTo(IR.VirtRegI->start);
-
- // Check if no LiveUnionI exists with VirtRegI->Start < LiveUnionI.end
- if (!IR.LiveUnionI.valid())
- break;
- if (IR.LiveUnionI.start() < IR.VirtRegI->end) {
- assert(overlap(*IR.VirtRegI, IR.LiveUnionI) &&
- "upperBound postcondition");
- break;
- }
- }
- if (!IR.LiveUnionI.valid())
- IR.VirtRegI = VirtRegEnd;
-}
-
-// Find the first intersection, and cache interference info
-// (retain segment iterators into both VirtReg and LiveUnion).
-const LiveIntervalUnion::InterferenceResult &
-LiveIntervalUnion::Query::firstInterference() {
- if (CheckedFirstInterference)
- return FirstInterference;
- CheckedFirstInterference = true;
- InterferenceResult &IR = FirstInterference;
- IR.LiveUnionI.setMap(LiveUnion->getMap());
-
- // Quickly skip interference check for empty sets.
- if (VirtReg->empty() || LiveUnion->empty()) {
- IR.VirtRegI = VirtReg->end();
- } else if (VirtReg->beginIndex() < LiveUnion->startIndex()) {
- // VirtReg starts first, perform double binary search.
- IR.VirtRegI = VirtReg->find(LiveUnion->startIndex());
- if (IR.VirtRegI != VirtReg->end())
- IR.LiveUnionI.find(IR.VirtRegI->start);
- } else {
- // LiveUnion starts first, perform double binary search.
- IR.LiveUnionI.find(VirtReg->beginIndex());
- if (IR.LiveUnionI.valid())
- IR.VirtRegI = VirtReg->find(IR.LiveUnionI.start());
- else
- IR.VirtRegI = VirtReg->end();
- }
- findIntersection(FirstInterference);
- assert((IR.VirtRegI == VirtReg->end() || IR.LiveUnionI.valid())
- && "Uninitialized iterator");
- 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 VirtReg or LiveUnion segment to ensure that we visit all
- // unique overlapping pairs.
- if (IR.VirtRegI->end < IR.LiveUnionI.stop()) {
- if (++IR.VirtRegI == VirtReg->end())
- return false;
- }
- else {
- if (!(++IR.LiveUnionI).valid()) {
- IR.VirtRegI = VirtReg->end();
- return false;
- }
- }
- // Short-circuit findIntersection() if possible.
- if (overlap(*IR.VirtRegI, IR.LiveUnionI))
- return true;
-
- // Find the next intersection.
- findIntersection(IR);
- return isInterference(IR);
-}
-