-// 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 live vreg 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);
-}
-
-// Scan the vector of interfering virtual registers in this union. Assuming it's