diff options
Diffstat (limited to 'lib/CodeGen/LiveIntervalUnion.cpp')
-rw-r--r-- | lib/CodeGen/LiveIntervalUnion.cpp | 332 |
1 files changed, 178 insertions, 154 deletions
diff --git a/lib/CodeGen/LiveIntervalUnion.cpp b/lib/CodeGen/LiveIntervalUnion.cpp index 46e83f80f8..3da201e0cc 100644 --- a/lib/CodeGen/LiveIntervalUnion.cpp +++ b/lib/CodeGen/LiveIntervalUnion.cpp @@ -21,85 +21,92 @@ #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 +// Find the first segment in the range [SegBegin,Segments.end()) that +// intersects with LS. If no intersection is found, return the first SI +// such that SI.start >= LS.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 |--... +// Upon entry we have SegBegin.Start < LS.End +// SegBegin |--... +// \ . +// LS ...-| +// +// After set::upper_bound, we have SI.start >= LS.start: +// SI |--... +// / +// LS |--... // // 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 +LiveIntervalUnion::upperBound(SegmentIter SegBegin, + const LiveSegment &LS) { + assert(LS.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; + SegmentIter SI = Segments.upper_bound(LS); + while (SI != SegBegin) { + --SI; + if (LS.Start >= SI->End) + return ++SI; } - return segI; + return SI; } // 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"); +// After implementing B+tree, segments will be coalesced. +void LiveIntervalUnion::unify(LiveInterval &VirtReg) { + + // Insert each of the virtual register's live segments into the map. + SegmentIter SegPos = Segments.begin(); + for (LiveInterval::iterator VirtRegI = VirtReg.begin(), + VirtRegEnd = VirtReg.end(); + VirtRegI != VirtRegEnd; ++VirtRegI ) { + + LiveSegment Seg(*VirtRegI, &VirtReg); + SegPos = Segments.insert(SegPos, Seg); + + assert(*SegPos == Seg && "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" ); + // Check for overlap (inductively). + if (SegPos != Segments.begin()) { + assert(llvm::prior(SegPos)->End <= Seg.Start && "overlapping segments" ); } - SegmentIter nextPos = llvm::next(segPos); - if (nextPos != segments_.end()) - assert(segment.end <= nextPos->start && "overlapping segments" ); + SegmentIter NextPos = llvm::next(SegPos); + if (NextPos != Segments.end()) + assert(Seg.End <= NextPos->Start && "overlapping segments" ); #endif // NDEBUG } } // Remove a live virtual register's segments from this union. -void LiveIntervalUnion::extract(const LiveInterval &lvr) { +void LiveIntervalUnion::extract(const LiveInterval &VirtReg) { + // 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++); + SegmentIter SegPos = Segments.begin(); + for (LiveInterval::const_iterator VirtRegI = VirtReg.begin(), + VirtRegEnd = VirtReg.end(); + VirtRegI != VirtRegEnd; ++VirtRegI) { + + LiveSegment Seg(*VirtRegI, const_cast<LiveInterval*>(&VirtReg)); + SegPos = upperBound(SegPos, Seg); + assert(SegPos != Segments.end() && "missing VirtReg segment"); + + Segments.erase(SegPos++); } } -raw_ostream& llvm::operator<<(raw_ostream& os, const LiveSegment &ls) { - return os << '[' << ls.start << ',' << ls.end << ':' << - ls.liveVirtReg->reg << ")"; +raw_ostream& llvm::operator<<(raw_ostream& OS, const LiveSegment &LS) { + return OS << '[' << LS.Start << ',' << LS.End << ':' << + LS.VirtReg->reg << ")"; } void LiveSegment::dump() const { @@ -107,35 +114,35 @@ void LiveSegment::dump() const { } void -LiveIntervalUnion::print(raw_ostream &os, - const AbstractRegisterDescription *rdesc) const { - os << "LIU "; - if (rdesc != NULL) - os << rdesc->getName(repReg_); +LiveIntervalUnion::print(raw_ostream &OS, + const AbstractRegisterDescription *RegDesc) const { + OS << "LIU "; + if (RegDesc != NULL) + OS << RegDesc->getName(RepReg); else { - os << repReg_; + OS << RepReg; } - for (LiveSegments::const_iterator segI = segments_.begin(), - segEnd = segments_.end(); segI != segEnd; ++segI) { - dbgs() << " " << *segI; + for (LiveSegments::const_iterator SI = Segments.begin(), + SegEnd = Segments.end(); SI != SegEnd; ++SI) { + dbgs() << " " << *SI; } - os << "\n"; + OS << "\n"; } -void LiveIntervalUnion::dump(const AbstractRegisterDescription *rdesc) const { - print(dbgs(), rdesc); +void LiveIntervalUnion::dump(const AbstractRegisterDescription *RegDesc) const { + print(dbgs(), RegDesc); } #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" ); +void LiveIntervalUnion::verify(LiveVirtRegBitSet& VisitedVRegs) { + SegmentIter SI = Segments.begin(); + SegmentIter SegEnd = Segments.end(); + if (SI == SegEnd) return; + VisitedVRegs.set(SI->VirtReg->reg); + for (++SI; SI != SegEnd; ++SI) { + VisitedVRegs.set(SI->VirtReg->reg); + assert(llvm::prior(SI)->End <= SI->Start && "overlapping segments" ); } } #endif //!NDEBUG @@ -146,147 +153,164 @@ void LiveIntervalUnion::verify(LvrBitSet& visitedVRegs) { // (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 +// be ok since most VIRTREGs 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 +// 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 { - LiveInterval::iterator lvrEnd = lvr_->end(); - SegmentIter liuEnd = liu_->end(); - while (ir.liuSegI_ != liuEnd) { +void LiveIntervalUnion::Query::findIntersection(InterferenceResult &IR) const { + + // Search until reaching the end of the LiveUnion segments. + LiveInterval::iterator VirtRegEnd = VirtReg->end(); + SegmentIter LiveUnionEnd = LiveUnion->end(); + while (IR.LiveUnionI != LiveUnionEnd) { + // 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_, + // 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. + while (IR.VirtRegI != VirtRegEnd && + IR.VirtRegI->end <= IR.LiveUnionI->Start) + ++IR.VirtRegI; + if (IR.VirtRegI == VirtRegEnd) + break; // Retain current (nonoverlapping) LiveUnionI + + // VirtRegI may have advanced far beyond LiveUnionI, // 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) + LiveSegment Seg(*IR.VirtRegI, VirtReg); + IR.LiveUnionI = LiveUnion->upperBound(IR.LiveUnionI, Seg); + + // Check if no LiveUnionI exists with VirtRegI->Start < LiveUnionI.end + if (IR.LiveUnionI == LiveUnionEnd) break; - if (ir.liuSegI_->start < ir.lvrSegI_->end) { - assert(overlap(*ir.lvrSegI_, *ir.liuSegI_) && "upperBound postcondition"); + if (IR.LiveUnionI->Start < IR.VirtRegI->end) { + assert(overlap(*IR.VirtRegI, *IR.LiveUnionI) && + "upperBound postcondition"); break; } } - if (ir.liuSegI_ == liuEnd) - ir.lvrSegI_ = lvrEnd; + if (IR.LiveUnionI == LiveUnionEnd) + IR.VirtRegI = VirtRegEnd; } // Find the first intersection, and cache interference info -// (retain segment iterators into both lvr_ and liu_). +// (retain segment iterators into both VirtReg and LiveUnion). LiveIntervalUnion::InterferenceResult LiveIntervalUnion::Query::firstInterference() { - if (firstInterference_ != LiveIntervalUnion::InterferenceResult()) { - return firstInterference_; + if (FirstInterference != LiveIntervalUnion::InterferenceResult()) { + return FirstInterference; } - firstInterference_ = InterferenceResult(lvr_->begin(), liu_->begin()); - findIntersection(firstInterference_); - return firstInterference_; + FirstInterference = InterferenceResult(VirtReg->begin(), LiveUnion->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()) +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->End) { + if (++IR.VirtRegI == VirtReg->end()) return false; } else { - if (++ir.liuSegI_ == liu_->end()) { - ir.lvrSegI_ = lvr_->end(); + if (++IR.LiveUnionI == LiveUnion->end()) { + IR.VirtRegI = VirtReg->end(); return false; } } - if (overlap(*ir.lvrSegI_, *ir.liuSegI_)) + // Short-circuit findIntersection() if possible. + if (overlap(*IR.VirtRegI, *IR.LiveUnionI)) return true; - // find the next intersection - findIntersection(ir); - return isInterference(ir); + + // Find the next intersection. + findIntersection(IR); + return isInterference(IR); } -// Scan the vector of interfering virtual registers in this union. Assuming it's +// Scan the vector of interfering virtual registers in this union. Assume it's // quite small. -bool LiveIntervalUnion::Query::isSeenInterference(LiveInterval *lvr) const { +bool LiveIntervalUnion::Query::isSeenInterference(LiveInterval *VirtReg) const { SmallVectorImpl<LiveInterval*>::const_iterator I = - std::find(interferingVRegs_.begin(), interferingVRegs_.end(), lvr); - return I != interferingVRegs_.end(); + std::find(InterferingVRegs.begin(), InterferingVRegs.end(), VirtReg); + 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()). +// query's live virtual register. +// +// The number of times that we either advance IR.VirtRegI or call +// LiveUnion.upperBound() will be no more than the number of holes in +// VirtReg. So each invocation of collectInterferingVRegs() takes +// time proportional to |VirtReg Holes| * time(LiveUnion.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) { +collectInterferingVRegs(unsigned MaxInterferingRegs) { + InterferenceResult IR = firstInterference(); + LiveInterval::iterator VirtRegEnd = VirtReg->end(); + SegmentIter LiveUnionEnd = LiveUnion->end(); + LiveInterval *RecentInterferingVReg = NULL; + while (IR.LiveUnionI != LiveUnionEnd) { // Advance the union's iterator to reach an unseen interfering vreg. do { - if (ir.liuSegI_->liveVirtReg == recentInterferingVReg) + if (IR.LiveUnionI->VirtReg == RecentInterferingVReg) continue; - if (!isSeenInterference(ir.liuSegI_->liveVirtReg)) + if (!isSeenInterference(IR.LiveUnionI->VirtReg)) break; // Cache the most recent interfering vreg to bypass isSeenInterference. - recentInterferingVReg = ir.liuSegI_->liveVirtReg; + RecentInterferingVReg = IR.LiveUnionI->VirtReg; - } while( ++ir.liuSegI_ != liuEnd); - if (ir.liuSegI_ == liuEnd) + } while( ++IR.LiveUnionI != LiveUnionEnd); + if (IR.LiveUnionI == LiveUnionEnd) 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) + // Advance the VirtReg iterator until surpassing the next segment in + // LiveUnion. + // + // Note: If this is ever used for coalescing of fixed registers and we have + // a live virtual register with thousands of segments, then use upperBound + // instead. + while (IR.VirtRegI != VirtRegEnd && + IR.VirtRegI->end <= IR.LiveUnionI->Start) + ++IR.VirtRegI; + if (IR.VirtRegI == VirtRegEnd) 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; + if (overlap(*IR.VirtRegI, *IR.LiveUnionI)) { + + if (!IR.LiveUnionI->VirtReg->isSpillable()) + SeenUnspillableVReg = true; + + InterferingVRegs.push_back(IR.LiveUnionI->VirtReg); + if (InterferingVRegs.size() == MaxInterferingRegs) + return MaxInterferingRegs; // Cache the most recent interfering vreg to bypass isSeenInterference. - recentInterferingVReg = ir.liuSegI_->liveVirtReg; - ++ir.liuSegI_; + RecentInterferingVReg = IR.LiveUnionI->VirtReg; + ++IR.LiveUnionI; continue; } - // lvrSegI_ may have advanced far beyond liuSegI_, + // VirtRegI may have advanced far beyond LiveUnionI, // do a fast intersection test to "catch up" - LiveSegment seg(ir.lvrSegI_->start, ir.lvrSegI_->end, lvr_); - ir.liuSegI_ = liu_->upperBound(ir.liuSegI_, seg); + LiveSegment Seg(*IR.VirtRegI, VirtReg); + IR.LiveUnionI = LiveUnion->upperBound(IR.LiveUnionI, Seg); } - return interferingVRegs_.size(); + SeenAllInterferences = true; + return InterferingVRegs.size(); } |