X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveIntervalUnion.cpp;h=025d99ce78812c8f42a003a1cda8b9d206b56b97;hb=d1a0b9f13e60483ba64036f599cf2064704e6773;hp=ec502cd51ec421dd512f46935167712027bdc351;hpb=e141a4960f702bef957b28abde3801ec64e32d87;p=oota-llvm.git diff --git a/lib/CodeGen/LiveIntervalUnion.cpp b/lib/CodeGen/LiveIntervalUnion.cpp index ec502cd51ec..025d99ce788 100644 --- a/lib/CodeGen/LiveIntervalUnion.cpp +++ b/lib/CodeGen/LiveIntervalUnion.cpp @@ -13,168 +13,193 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "regalloc" -#include "LiveIntervalUnion.h" +#include "llvm/CodeGen/LiveIntervalUnion.h" +#include "llvm/ADT/SparseBitVector.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetRegisterInfo.h" #include + using namespace llvm; -// Find the first segment in the range [segBegin,segments_.end()) that -// intersects with seg. If no intersection is found, return the first segI -// such that segI.start >= seg.end -// -// This logic is tied to the underlying LiveSegments data structure. For now, we -// use set::upper_bound to find the nearest starting position, -// then reverse iterate to find the first overlap. -// -// Upon entry we have segBegin.start < seg.end -// seg |--... -// \ . -// lvr ...-| -// -// After set::upper_bound, we have segI.start >= seg.start: -// seg |--... -// / -// lvr |--... -// -// Assuming intervals are disjoint, if an intersection exists, it must be the -// segment found or the one immediately preceeding it. We continue reverse -// iterating to return the first overlapping segment. -LiveIntervalUnion::SegmentIter -LiveIntervalUnion::upperBound(SegmentIter segBegin, - const LiveSegment &seg) { - assert(seg.end > segBegin->start && "segment iterator precondition"); - // get the next LIU segment such that segI->start is not less than seg.start - // - // FIXME: Once we have a B+tree, we can make good use of segBegin as a hint to - // upper_bound. For now, we're forced to search again from the root each time. - SegmentIter segI = segments_.upper_bound(seg); - while (segI != segBegin) { - --segI; - if (seg.start >= segI->end) - return ++segI; - } - return segI; -} +#define DEBUG_TYPE "regalloc" + // Merge a LiveInterval's segments. Guarantee no overlaps. -// -// Consider coalescing adjacent segments to save space, even though it makes -// extraction more complicated. -void LiveIntervalUnion::unify(LiveInterval &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"); -#ifndef NDEBUG - // check for overlap (inductively) - if (segPos != segments_.begin()) { - SegmentIter prevPos = segPos; - --prevPos; - assert(prevPos->end <= segment.start && "overlapping segments" ); - } - SegmentIter nextPos = segPos; - ++nextPos; - if (nextPos != segments_.end()) - assert(segment.end <= nextPos->start && "overlapping segments" ); -#endif // NDEBUG +void LiveIntervalUnion::unify(LiveInterval &VirtReg, const LiveRange &Range) { + if (Range.empty()) + return; + ++Tag; + + // Insert each of the virtual register's live segments into the map. + LiveRange::const_iterator RegPos = Range.begin(); + LiveRange::const_iterator RegEnd = Range.end(); + SegmentIter SegPos = Segments.find(RegPos->start); + + while (SegPos.valid()) { + SegPos.insert(RegPos->start, RegPos->end, &VirtReg); + if (++RegPos == RegEnd) + return; + SegPos.advanceTo(RegPos->start); } + + // We have reached the end of Segments, so it is no longer necessary to search + // for the insertion position. + // It is faster to insert the end first. + --RegEnd; + SegPos.insert(RegEnd->start, RegEnd->end, &VirtReg); + for (; RegPos != RegEnd; ++RegPos, ++SegPos) + SegPos.insert(RegPos->start, RegPos->end, &VirtReg); } // Remove a live virtual register's segments from this union. -void LiveIntervalUnion::extract(const LiveInterval &lvr) { +void LiveIntervalUnion::extract(LiveInterval &VirtReg, const LiveRange &Range) { + if (Range.empty()) + return; + ++Tag; + // Remove each of the virtual register's live segments from the map. - SegmentIter segPos = segments_.begin(); - for (LiveInterval::const_iterator lvrI = lvr.begin(), lvrEnd = lvr.end(); - lvrI != lvrEnd; ++lvrI) { - LiveSegment seg(lvrI->start, lvrI->end, const_cast(&lvr)); - segPos = upperBound(segPos, seg); - assert(segPos != segments_.end() && "missing lvr segment"); - segments_.erase(segPos++); + LiveRange::const_iterator RegPos = Range.begin(); + LiveRange::const_iterator RegEnd = Range.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 = Range.advanceTo(RegPos, SegPos.start()); + if (RegPos == RegEnd) + return; + + SegPos.advanceTo(RegPos->start); + } +} + +void +LiveIntervalUnion::print(raw_ostream &OS, const TargetRegisterInfo *TRI) const { + if (empty()) { + OS << " empty\n"; + return; + } + for (LiveSegments::const_iterator SI = Segments.begin(); SI.valid(); ++SI) { + OS << " [" << SI.start() << ' ' << SI.stop() << "):" + << PrintReg(SI.value()->reg, TRI); } + OS << '\n'; } -// Private interface accessed by Query. +#ifndef NDEBUG +// Verify the live intervals in this union and add them to the visited set. +void LiveIntervalUnion::verify(LiveVirtRegBitSet& VisitedVRegs) { + for (SegmentIter SI = Segments.begin(); SI.valid(); ++SI) + VisitedVRegs.set(SI.value()->reg); +} +#endif //!NDEBUG + +// Scan the vector of interfering virtual registers in this union. Assume it's +// quite small. +bool LiveIntervalUnion::Query::isSeenInterference(LiveInterval *VirtReg) const { + SmallVectorImpl::const_iterator I = + std::find(InterferingVRegs.begin(), InterferingVRegs.end(), VirtReg); + return I != InterferingVRegs.end(); +} + +// Collect virtual registers in this union that interfere with this +// query's live virtual register. // -// 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. +// The query state is one of: // -// If no intersection exists, set lvrI = lvrEnd, and set segI to the first -// segment whose start point is greater than LiveInterval's end point. +// 1. CheckedFirstInterference == false: Iterators are uninitialized. +// 2. SeenAllInterferences == true: InterferingVRegs complete, iterators unused. +// 3. Iterators left at the last seen intersection. // -// 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" - 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; +unsigned LiveIntervalUnion::Query:: +collectInterferingVRegs(unsigned MaxInterferingRegs) { + // Fast path return if we already have the desired information. + if (SeenAllInterferences || InterferingVRegs.size() >= MaxInterferingRegs) + return InterferingVRegs.size(); + + // Set up iterators on the first call. + if (!CheckedFirstInterference) { + CheckedFirstInterference = true; + + // Quickly skip interference check for empty sets. + if (VirtReg->empty() || LiveUnion->empty()) { + SeenAllInterferences = true; + return 0; } - } - 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_; + // In most cases, the union will start before VirtReg. + VirtRegI = VirtReg->begin(); + LiveUnionI.setMap(LiveUnion->getMap()); + LiveUnionI.find(VirtRegI->start); } - 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; + LiveInterval::iterator VirtRegEnd = VirtReg->end(); + LiveInterval *RecentReg = nullptr; + while (LiveUnionI.valid()) { + assert(VirtRegI != VirtRegEnd && "Reached end of VirtReg"); + + // Check for overlapping interference. + while (VirtRegI->start < LiveUnionI.stop() && + VirtRegI->end > LiveUnionI.start()) { + // This is an overlap, record the interfering register. + LiveInterval *VReg = LiveUnionI.value(); + if (VReg != RecentReg && !isSeenInterference(VReg)) { + RecentReg = VReg; + InterferingVRegs.push_back(VReg); + if (InterferingVRegs.size() >= MaxInterferingRegs) + return InterferingVRegs.size(); + } + // This LiveUnion segment is no longer interesting. + if (!(++LiveUnionI).valid()) { + SeenAllInterferences = true; + return InterferingVRegs.size(); + } } + + // The iterators are now not overlapping, LiveUnionI has been advanced + // beyond VirtRegI. + assert(VirtRegI->end <= LiveUnionI.start() && "Expected non-overlap"); + + // Advance the iterator that ends first. + VirtRegI = VirtReg->advanceTo(VirtRegI, LiveUnionI.start()); + if (VirtRegI == VirtRegEnd) + break; + + // Detect overlap, handle above. + if (VirtRegI->start < LiveUnionI.stop()) + continue; + + // Still not overlapping. Catch up LiveUnionI. + LiveUnionI.advanceTo(VirtRegI->start); } - if (overlap(*ir.lvrSegI_, *ir.liuSegI_)) - return true; - // find the next intersection - findIntersection(ir); - return isInterference(ir); + SeenAllInterferences = true; + return InterferingVRegs.size(); +} + +void LiveIntervalUnion::Array::init(LiveIntervalUnion::Allocator &Alloc, + unsigned NSize) { + // Reuse existing allocation. + if (NSize == Size) + return; + clear(); + Size = NSize; + LIUs = static_cast( + malloc(sizeof(LiveIntervalUnion)*NSize)); + for (unsigned i = 0; i != Size; ++i) + new(LIUs + i) LiveIntervalUnion(Alloc); +} + +void LiveIntervalUnion::Array::clear() { + if (!LIUs) + return; + for (unsigned i = 0; i != Size; ++i) + LIUs[i].~LiveIntervalUnion(); + free(LIUs); + Size = 0; + LIUs = nullptr; }