X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveIntervalUnion.cpp;h=025d99ce78812c8f42a003a1cda8b9d206b56b97;hb=25103832b272eaa009fd56d3fc9eb98ebb7c2f1a;hp=b22f466367edbfa4cb54c4fd6f093ea2fa5acf8d;hpb=14e8d71cc945034d4ee6e76be00e00f14efac62f;p=oota-llvm.git diff --git a/lib/CodeGen/LiveIntervalUnion.cpp b/lib/CodeGen/LiveIntervalUnion.cpp index b22f466367e..025d99ce788 100644 --- a/lib/CodeGen/LiveIntervalUnion.cpp +++ b/lib/CodeGen/LiveIntervalUnion.cpp @@ -13,155 +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; +#define DEBUG_TYPE "regalloc" + + // Merge a LiveInterval's segments. Guarantee no overlaps. -void LiveIntervalUnion::unify(LiveInterval &lvr) { - // Add this live virtual register to the union - LiveVirtRegs::iterator pos = std::upper_bound(lvrs_.begin(), lvrs_.end(), - &lvr, less_ptr()); - assert(pos == lvrs_.end() || *pos != &lvr && "duplicate LVR insertion"); - lvrs_.insert(pos, &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"); +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); } -namespace { +// Remove a live virtual register's segments from this union. +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. + 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; -// Keep LVRs sorted for fast membership test and extraction. -struct LessReg - : public std::binary_function { - bool operator()(const LiveInterval *left, const LiveInterval *right) const { - return left->reg < right->reg; + SegPos.advanceTo(RegPos->start); } -}; - -// 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. -// -// FIXME: support extract(), handle tombstones of extracted lvrs. -typedef LiveIntervalUnion::SegmentIter SegmentIter; -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; +} + +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); } - return segI; + OS << '\n'; } -} // end anonymous namespace -// 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" - ir.liuSegI_ = upperBound(ir.liuSegI_, liuEnd, *ir.lvrSegI_); - // 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; }