diff options
Diffstat (limited to 'lib/CodeGen/LiveIntervalUnion.cpp')
| -rw-r--r-- | lib/CodeGen/LiveIntervalUnion.cpp | 292 |
1 files changed, 292 insertions, 0 deletions
diff --git a/lib/CodeGen/LiveIntervalUnion.cpp b/lib/CodeGen/LiveIntervalUnion.cpp new file mode 100644 index 0000000..46e83f8 --- /dev/null +++ b/lib/CodeGen/LiveIntervalUnion.cpp @@ -0,0 +1,292 @@ +//===-- LiveIntervalUnion.cpp - Live interval union data structure --------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// LiveIntervalUnion represents a coalesced set of live intervals. This may be +// used during coalescing to represent a congruence class, or during register +// allocation to model liveness of a physical register. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "regalloc" +#include "LiveIntervalUnion.h" +#include "llvm/ADT/SparseBitVector.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +#include <algorithm> +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; +} + +// 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()) { + assert(llvm::prior(segPos)->end <= segment.start && + "overlapping segments" ); + } + SegmentIter nextPos = llvm::next(segPos); + if (nextPos != segments_.end()) + assert(segment.end <= nextPos->start && "overlapping segments" ); +#endif // NDEBUG + } +} + +// Remove a live virtual register's segments from this union. +void LiveIntervalUnion::extract(const LiveInterval &lvr) { + // 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<LiveInterval*>(&lvr)); + segPos = upperBound(segPos, seg); + assert(segPos != segments_.end() && "missing lvr segment"); + segments_.erase(segPos++); + } +} + +raw_ostream& llvm::operator<<(raw_ostream& os, const LiveSegment &ls) { + return os << '[' << ls.start << ',' << ls.end << ':' << + ls.liveVirtReg->reg << ")"; +} + +void LiveSegment::dump() const { + dbgs() << *this << "\n"; +} + +void +LiveIntervalUnion::print(raw_ostream &os, + const AbstractRegisterDescription *rdesc) const { + os << "LIU "; + if (rdesc != NULL) + os << rdesc->getName(repReg_); + else { + os << repReg_; + } + for (LiveSegments::const_iterator segI = segments_.begin(), + segEnd = segments_.end(); segI != segEnd; ++segI) { + dbgs() << " " << *segI; + } + os << "\n"; +} + +void LiveIntervalUnion::dump(const AbstractRegisterDescription *rdesc) const { + print(dbgs(), rdesc); +} + +#ifndef NDEBUG +// Verify the live intervals in this union and add them to the visited set. +void LiveIntervalUnion::verify(LvrBitSet& visitedVRegs) { + SegmentIter segI = segments_.begin(); + SegmentIter segEnd = segments_.end(); + if (segI == segEnd) return; + visitedVRegs.set(segI->liveVirtReg->reg); + for (++segI; segI != segEnd; ++segI) { + visitedVRegs.set(segI->liveVirtReg->reg); + assert(llvm::prior(segI)->end <= segI->start && "overlapping segments" ); + } +} +#endif //!NDEBUG + +// 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 +// quite small. +bool LiveIntervalUnion::Query::isSeenInterference(LiveInterval *lvr) const { + SmallVectorImpl<LiveInterval*>::const_iterator I = + std::find(interferingVRegs_.begin(), interferingVRegs_.end(), lvr); + return I != interferingVRegs_.end(); +} + +// Count the number of virtual registers in this union that interfere with this +// query's live virtual register. +// +// The number of times that we either advance ir.lvrSegI_ or call +// liu_.upperBound() will be no more than the number of holes in +// lvr_. So each invocation of collectInterferingVirtReg() takes +// time proportional to |lvr-holes| * time(liu_.upperBound()). +// +// For comments on how to speed it up, see Query::findIntersection(). +unsigned LiveIntervalUnion::Query:: +collectInterferingVRegs(unsigned maxInterferingRegs) { + InterferenceResult ir = firstInterference(); + LiveInterval::iterator lvrEnd = lvr_->end(); + SegmentIter liuEnd = liu_->end(); + LiveInterval *recentInterferingVReg = NULL; + while (ir.liuSegI_ != liuEnd) { + // Advance the union's iterator to reach an unseen interfering vreg. + do { + if (ir.liuSegI_->liveVirtReg == recentInterferingVReg) + continue; + + if (!isSeenInterference(ir.liuSegI_->liveVirtReg)) + break; + + // Cache the most recent interfering vreg to bypass isSeenInterference. + recentInterferingVReg = ir.liuSegI_->liveVirtReg; + + } while( ++ir.liuSegI_ != liuEnd); + if (ir.liuSegI_ == liuEnd) + break; + + // Advance the live vreg reg iterator until surpassing 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; + + // Check for intersection with the union's segment. + if (overlap(*ir.lvrSegI_, *ir.liuSegI_)) { + if (!ir.liuSegI_->liveVirtReg->isSpillable()) + seenUnspillableVReg_ = true; + + interferingVRegs_.push_back(ir.liuSegI_->liveVirtReg); + if (interferingVRegs_.size() == maxInterferingRegs) + return maxInterferingRegs; + + // Cache the most recent interfering vreg to bypass isSeenInterference. + recentInterferingVReg = ir.liuSegI_->liveVirtReg; + ++ir.liuSegI_; + continue; + } + // 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); + } + return interferingVRegs_.size(); +} |