diff options
| -rw-r--r-- | lib/CodeGen/LiveIntervalUnion.cpp | 332 | ||||
| -rw-r--r-- | lib/CodeGen/LiveIntervalUnion.h | 191 | ||||
| -rw-r--r-- | lib/CodeGen/RegAllocBase.h | 79 | ||||
| -rw-r--r-- | lib/CodeGen/RegAllocBasic.cpp | 470 |
4 files changed, 548 insertions, 524 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(); } diff --git a/lib/CodeGen/LiveIntervalUnion.h b/lib/CodeGen/LiveIntervalUnion.h index 38f6ac3abd..153ee2d669 100644 --- a/lib/CodeGen/LiveIntervalUnion.h +++ b/lib/CodeGen/LiveIntervalUnion.h @@ -26,7 +26,7 @@ namespace llvm { #ifndef NDEBUG // forward declaration template <unsigned Element> class SparseBitVector; -typedef SparseBitVector<128> LvrBitSet; +typedef SparseBitVector<128> LiveVirtRegBitSet; #endif /// A LiveSegment is a copy of a LiveRange object used within @@ -37,52 +37,54 @@ typedef SparseBitVector<128> LvrBitSet; /// interval within a virtual register's liveness. To limit confusion, in this /// file we refer it as a live segment. /// -/// Note: This currently represents a half-open interval [start,end). +/// Note: This currently represents a half-open interval [Start,End). /// If LiveRange is modified to represent a closed interval, so should this. struct LiveSegment { - SlotIndex start; - SlotIndex end; - LiveInterval *liveVirtReg; + SlotIndex Start; + SlotIndex End; + LiveInterval *VirtReg; - LiveSegment(SlotIndex s, SlotIndex e, LiveInterval *lvr) - : start(s), end(e), liveVirtReg(lvr) {} + LiveSegment(const LiveRange& LR, LiveInterval *VReg) + : Start(LR.start), End(LR.end), VirtReg(VReg) {} - bool operator==(const LiveSegment &ls) const { - return start == ls.start && end == ls.end && liveVirtReg == ls.liveVirtReg; + bool operator==(const LiveSegment &LS) const { + return Start == LS.Start && End == LS.End && VirtReg == LS.VirtReg; } - bool operator!=(const LiveSegment &ls) const { - return !operator==(ls); + bool operator!=(const LiveSegment &LS) const { + return !operator==(LS); } // Order segments by starting point only--we expect them to be disjoint. - bool operator<(const LiveSegment &ls) const { return start < ls.start; } + bool operator<(const LiveSegment &LS) const { return Start < LS.Start; } void dump() const; - void print(raw_ostream &os) const; + void print(raw_ostream &OS) const; }; -inline bool operator<(SlotIndex V, const LiveSegment &ls) { - return V < ls.start; +inline bool operator<(SlotIndex Idx, const LiveSegment &LS) { + return Idx < LS.Start; } -inline bool operator<(const LiveSegment &ls, SlotIndex V) { - return ls.start < V; +inline bool operator<(const LiveSegment &LS, SlotIndex Idx) { + return LS.Start < Idx; } /// Compare a live virtual register segment to a LiveIntervalUnion segment. -inline bool overlap(const LiveRange &lvrSeg, const LiveSegment &liuSeg) { - return lvrSeg.start < liuSeg.end && liuSeg.start < lvrSeg.end; +inline bool overlap(const LiveRange &VirtRegSegment, + const LiveSegment &LiveUnionSegment) { + return VirtRegSegment.start < LiveUnionSegment.End && + LiveUnionSegment.Start < VirtRegSegment.end; } template <> struct isPodLike<LiveSegment> { static const bool value = true; }; -raw_ostream& operator<<(raw_ostream& os, const LiveSegment &ls); +raw_ostream& operator<<(raw_ostream& OS, const LiveSegment &LS); /// Abstraction to provide info for the representative register. class AbstractRegisterDescription { public: - virtual const char *getName(unsigned reg) const = 0; + virtual const char *getName(unsigned Reg) const = 0; virtual ~AbstractRegisterDescription() {} }; @@ -92,7 +94,7 @@ public: /// eventually make exceptions to handle value-based interference. class LiveIntervalUnion { // A set of live virtual register segments that supports fast insertion, - // intersection, and removal. + // intersection, and removal. // // FIXME: std::set is a placeholder until we decide how to // efficiently represent it. Probably need to roll our own B-tree. @@ -103,7 +105,7 @@ class LiveIntervalUnion { // This is traditionally known as a live range, but we refer is as a live // virtual register to avoid confusing it with the misnamed LiveRange // class. - typedef std::vector<LiveInterval*> LiveVirtRegs; + typedef std::vector<LiveInterval*> LiveVRegs; public: // SegmentIter can advance to the next segment ordered by starting position @@ -115,41 +117,41 @@ public: class Query; private: - unsigned repReg_; // representative register number - LiveSegments segments_; // union of virtual reg segements + unsigned RepReg; // representative register number + LiveSegments Segments; // union of virtual reg segements public: // default ctor avoids placement new - LiveIntervalUnion() : repReg_(0) {} + LiveIntervalUnion() : RepReg(0) {} // Initialize the union by associating it with a representative register // number. - void init(unsigned repReg) { repReg_ = repReg; } + void init(unsigned Reg) { RepReg = Reg; } // Iterate over all segments in the union of live virtual registers ordered // by their starting position. - SegmentIter begin() { return segments_.begin(); } - SegmentIter end() { return segments_.end(); } + SegmentIter begin() { return Segments.begin(); } + SegmentIter end() { return Segments.end(); } // Return an iterator to the first segment after or including begin that - // intersects with lvrSeg. - SegmentIter upperBound(SegmentIter begin, const LiveSegment &seg); + // intersects with LS. + SegmentIter upperBound(SegmentIter SegBegin, const LiveSegment &LS); // Add a live virtual register to this union and merge its segments. - // Holds a nonconst reference to the LVR for later maniplution. - void unify(LiveInterval &lvr); + // Holds a nonconst reference to the VirtReg for later maniplution. + void unify(LiveInterval &VirtReg); // Remove a live virtual register's segments from this union. - void extract(const LiveInterval &lvr); + void extract(const LiveInterval &VirtReg); - void dump(const AbstractRegisterDescription *regInfo) const; + void dump(const AbstractRegisterDescription *RegDesc) const; + + // If tri != NULL, use it to decode RepReg + void print(raw_ostream &OS, const AbstractRegisterDescription *RegDesc) const; - // If tri != NULL, use it to decode repReg_ - void print(raw_ostream &os, const AbstractRegisterDescription *rdesc) const; - #ifndef NDEBUG // Verify the live intervals in this union and add them to the visited set. - void verify(LvrBitSet& visitedVRegs); + void verify(LiveVirtRegBitSet& VisitedVRegs); #endif /// Cache a single interference test result in the form of two intersecting @@ -159,85 +161,89 @@ public: class InterferenceResult { friend class Query; - LiveInterval::iterator lvrSegI_; // current position in _lvr - SegmentIter liuSegI_; // current position in _liu - + LiveInterval::iterator VirtRegI; // current position in VirtReg + SegmentIter LiveUnionI; // current position in LiveUnion + // Internal ctor. - InterferenceResult(LiveInterval::iterator lvrSegI, SegmentIter liuSegI) - : lvrSegI_(lvrSegI), liuSegI_(liuSegI) {} + InterferenceResult(LiveInterval::iterator VRegI, SegmentIter UnionI) + : VirtRegI(VRegI), LiveUnionI(UnionI) {} public: // Public default ctor. - InterferenceResult(): lvrSegI_(), liuSegI_() {} + InterferenceResult(): VirtRegI(), LiveUnionI() {} // Note: this interface provides raw access to the iterators because the // result has no way to tell if it's valid to dereference them. - // Access the lvr segment. - LiveInterval::iterator lvrSegPos() const { return lvrSegI_; } + // Access the VirtReg segment. + LiveInterval::iterator virtRegPos() const { return VirtRegI; } - // Access the liu segment. - SegmentIter liuSegPos() const { return liuSegI_; } + // Access the LiveUnion segment. + SegmentIter liveUnionPos() const { return LiveUnionI; } - bool operator==(const InterferenceResult &ir) const { - return lvrSegI_ == ir.lvrSegI_ && liuSegI_ == ir.liuSegI_; + bool operator==(const InterferenceResult &IR) const { + return VirtRegI == IR.VirtRegI && LiveUnionI == IR.LiveUnionI; } - bool operator!=(const InterferenceResult &ir) const { - return !operator==(ir); + bool operator!=(const InterferenceResult &IR) const { + return !operator==(IR); } }; /// Query interferences between a single live virtual register and a live /// interval union. class Query { - LiveIntervalUnion *liu_; - LiveInterval *lvr_; - InterferenceResult firstInterference_; - SmallVector<LiveInterval*,4> interferingVRegs_; - bool seenUnspillableVReg_; + LiveIntervalUnion *LiveUnion; + LiveInterval *VirtReg; + InterferenceResult FirstInterference; + SmallVector<LiveInterval*,4> InterferingVRegs; + bool SeenAllInterferences; + bool SeenUnspillableVReg; public: - Query(): liu_(), lvr_() {} + Query(): LiveUnion(), VirtReg() {} - Query(LiveInterval *lvr, LiveIntervalUnion *liu): - liu_(liu), lvr_(lvr), seenUnspillableVReg_(false) {} + Query(LiveInterval *VReg, LiveIntervalUnion *LIU): + LiveUnion(LIU), VirtReg(VReg), SeenAllInterferences(false), + SeenUnspillableVReg(false) + {} void clear() { - liu_ = NULL; - lvr_ = NULL; - firstInterference_ = InterferenceResult(); - interferingVRegs_.clear(); - seenUnspillableVReg_ = false; + LiveUnion = NULL; + VirtReg = NULL; + FirstInterference = InterferenceResult(); + InterferingVRegs.clear(); + SeenAllInterferences = false; + SeenUnspillableVReg = false; } - - void init(LiveInterval *lvr, LiveIntervalUnion *liu) { - if (lvr_ == lvr) { + + void init(LiveInterval *VReg, LiveIntervalUnion *LIU) { + if (VirtReg == VReg) { // We currently allow query objects to be reused acrossed live virtual // registers, but always for the same live interval union. - assert(liu_ == liu && "inconsistent initialization"); + assert(LiveUnion == LIU && "inconsistent initialization"); // Retain cached results, e.g. firstInterference. return; } - liu_ = liu; - lvr_ = lvr; - // Clear cached results. - firstInterference_ = InterferenceResult(); - interferingVRegs_.clear(); - seenUnspillableVReg_ = false; + clear(); + LiveUnion = LIU; + VirtReg = VReg; } - LiveInterval &lvr() const { assert(lvr_ && "uninitialized"); return *lvr_; } + LiveInterval &virtReg() const { + assert(VirtReg && "uninitialized"); + return *VirtReg; + } - bool isInterference(const InterferenceResult &ir) const { - if (ir.lvrSegI_ != lvr_->end()) { - assert(overlap(*ir.lvrSegI_, *ir.liuSegI_) && + bool isInterference(const InterferenceResult &IR) const { + if (IR.VirtRegI != VirtReg->end()) { + assert(overlap(*IR.VirtRegI, *IR.LiveUnionI) && "invalid segment iterators"); return true; } return false; } - // Does this live virtual register interfere with the union. + // Does this live virtual register interfere with the union? bool checkInterference() { return isInterference(firstInterference()); } // Get the first pair of interfering segments, or a noninterfering result. @@ -246,32 +252,33 @@ public: // Treat the result as an iterator and advance to the next interfering pair // of segments. Visiting each unique interfering pairs means that the same - // lvr or liu segment may be visited multiple times. - bool nextInterference(InterferenceResult &ir) const; + // VirtReg or LiveUnion segment may be visited multiple times. + bool nextInterference(InterferenceResult &IR) const; // Count the virtual registers in this union that interfere with this // query's live virtual register, up to maxInterferingRegs. - unsigned collectInterferingVRegs(unsigned maxInterferingRegs = UINT_MAX); + unsigned collectInterferingVRegs(unsigned MaxInterferingRegs = UINT_MAX); // Was this virtual register visited during collectInterferingVRegs? - bool isSeenInterference(LiveInterval *lvr) const; + bool isSeenInterference(LiveInterval *VReg) const; + + // Did collectInterferingVRegs collect all interferences? + bool seenAllInterferences() const { return SeenAllInterferences; } // Did collectInterferingVRegs encounter an unspillable vreg? - bool seenUnspillableVReg() const { - return seenUnspillableVReg_; - } + bool seenUnspillableVReg() const { return SeenUnspillableVReg; } // Vector generated by collectInterferingVRegs. const SmallVectorImpl<LiveInterval*> &interferingVRegs() const { - return interferingVRegs_; + return InterferingVRegs; } - + private: Query(const Query&); // DO NOT IMPLEMENT void operator=(const Query&); // DO NOT IMPLEMENT - + // Private interface for queries - void findIntersection(InterferenceResult &ir) const; + void findIntersection(InterferenceResult &IR) const; }; }; diff --git a/lib/CodeGen/RegAllocBase.h b/lib/CodeGen/RegAllocBase.h index c8c78567f8..8044a19238 100644 --- a/lib/CodeGen/RegAllocBase.h +++ b/lib/CodeGen/RegAllocBase.h @@ -11,11 +11,11 @@ // register allocation algorithm and interface for extending it. It provides the // building blocks on which to construct other experimental allocators and test // the validity of two principles: -// +// // - If virtual and physical register liveness is modeled using intervals, then // on-the-fly interference checking is cheap. Furthermore, interferences can be // lazily cached and reused. -// +// // - Register allocation complexity, and generated code performance is // determined by the effectiveness of live range splitting rather than optimal // coloring. @@ -52,8 +52,8 @@ class Spiller; // The default is to simply compare spill weights. struct LessSpillWeightPriority : public std::binary_function<LiveInterval,LiveInterval, bool> { - bool operator()(const LiveInterval *left, const LiveInterval *right) const { - return left->weight < right->weight; + bool operator()(const LiveInterval *Left, const LiveInterval *Right) const { + return Left->weight < Right->weight; } }; @@ -65,41 +65,40 @@ class LiveVirtRegQueue; /// RegAllocBase provides the register allocation driver and interface that can /// be extended to add interesting heuristics. /// -/// More sophisticated allocators must override the selectOrSplit() method to -/// implement live range splitting and must specify a comparator to determine -/// register assignment priority. LessSpillWeightPriority is provided as a -/// standard comparator. +/// Register allocators must override the selectOrSplit() method to implement +/// live range splitting. LessSpillWeightPriority is provided as a standard +/// comparator, but we may add an interface to override it if necessary. class RegAllocBase { protected: // Array of LiveIntervalUnions indexed by physical register. - class LIUArray { - unsigned nRegs_; - OwningArrayPtr<LiveIntervalUnion> array_; + class LiveUnionArray { + unsigned NumRegs; + OwningArrayPtr<LiveIntervalUnion> Array; public: - LIUArray(): nRegs_(0) {} + LiveUnionArray(): NumRegs(0) {} - unsigned numRegs() const { return nRegs_; } + unsigned numRegs() const { return NumRegs; } - void init(unsigned nRegs); + void init(unsigned NRegs); void clear(); - - LiveIntervalUnion& operator[](unsigned physReg) { - assert(physReg < nRegs_ && "physReg out of bounds"); - return array_[physReg]; + + LiveIntervalUnion& operator[](unsigned PhysReg) { + assert(PhysReg < NumRegs && "physReg out of bounds"); + return Array[PhysReg]; } }; - - const TargetRegisterInfo *tri_; - VirtRegMap *vrm_; - LiveIntervals *lis_; - LIUArray physReg2liu_; + + const TargetRegisterInfo *TRI; + VirtRegMap *VRM; + LiveIntervals *LIS; + LiveUnionArray PhysReg2LiveUnion; // Current queries, one per physreg. They must be reinitialized each time we // query on a new live virtual register. - OwningArrayPtr<LiveIntervalUnion::Query> queries_; + OwningArrayPtr<LiveIntervalUnion::Query> Queries; - RegAllocBase(): tri_(0), vrm_(0), lis_(0) {} + RegAllocBase(): TRI(0), VRM(0), LIS(0) {} virtual ~RegAllocBase() {} @@ -108,13 +107,13 @@ protected: // Get an initialized query to check interferences between lvr and preg. Note // that Query::init must be called at least once for each physical register - // before querying a new live virtual register. This ties queries_ and - // physReg2liu_ together. - LiveIntervalUnion::Query &query(LiveInterval &lvr, unsigned preg) { - queries_[preg].init(&lvr, &physReg2liu_[preg]); - return queries_[preg]; + // before querying a new live virtual register. This ties Queries and + // PhysReg2LiveUnion together. + LiveIntervalUnion::Query &query(LiveInterval &VirtReg, unsigned PhysReg) { + Queries[PhysReg].init(&VirtReg, &PhysReg2LiveUnion[PhysReg]); + return Queries[PhysReg]; } - + // The top-level driver. The output is a VirtRegMap that us updated with // physical register assignments. // @@ -125,12 +124,12 @@ protected: // Get a temporary reference to a Spiller instance. virtual Spiller &spiller() = 0; - + // A RegAlloc pass should override this to provide the allocation heuristics. // Each call must guarantee forward progess by returning an available PhysReg // or new set of split live virtual registers. It is up to the splitter to // converge quickly toward fully spilled live ranges. - virtual unsigned selectOrSplit(LiveInterval &lvr, + virtual unsigned selectOrSplit(LiveInterval &VirtReg, SmallVectorImpl<LiveInterval*> &splitLVRs) = 0; // A RegAlloc pass should call this when PassManager releases its memory. @@ -139,24 +138,24 @@ protected: // Helper for checking interference between a live virtual register and a // physical register, including all its register aliases. If an interference // exists, return the interfering register, which may be preg or an alias. - unsigned checkPhysRegInterference(LiveInterval& lvr, unsigned preg); + unsigned checkPhysRegInterference(LiveInterval& VirtReg, unsigned PhysReg); // Helper for spilling all live virtual registers currently unified under preg // that interfere with the most recently queried lvr. Return true if spilling // was successful, and append any new spilled/split intervals to splitLVRs. - bool spillInterferences(LiveInterval &lvr, unsigned preg, - SmallVectorImpl<LiveInterval*> &splitLVRs); + bool spillInterferences(LiveInterval &VirtReg, unsigned PhysReg, + SmallVectorImpl<LiveInterval*> &SplitVRegs); #ifndef NDEBUG // Verify each LiveIntervalUnion. void verify(); #endif - + private: - void seedLiveVirtRegs(LiveVirtRegQueue &lvrQ); + void seedLiveVirtRegs(LiveVirtRegQueue &VirtRegQ); - void spillReg(LiveInterval &lvr, unsigned reg, - SmallVectorImpl<LiveInterval*> &splitLVRs); + void spillReg(LiveInterval &VirtReg, unsigned PhysReg, + SmallVectorImpl<LiveInterval*> &SplitVRegs); }; } // end namespace llvm diff --git a/lib/CodeGen/RegAllocBasic.cpp b/lib/CodeGen/RegAllocBasic.cpp index 6af5e6c889..545a6bd5bc 100644 --- a/lib/CodeGen/RegAllocBasic.cpp +++ b/lib/CodeGen/RegAllocBasic.cpp @@ -59,10 +59,10 @@ VerifyRegAlloc("verify-regalloc", namespace { class PhysicalRegisterDescription : public AbstractRegisterDescription { - const TargetRegisterInfo *tri_; + const TargetRegisterInfo *TRI; public: - PhysicalRegisterDescription(const TargetRegisterInfo *tri): tri_(tri) {} - virtual const char *getName(unsigned reg) const { return tri_->getName(reg); } + PhysicalRegisterDescription(const TargetRegisterInfo *T): TRI(T) {} + virtual const char *getName(unsigned Reg) const { return TRI->getName(Reg); } }; /// RABasic provides a minimal implementation of the basic register allocation @@ -73,17 +73,18 @@ public: class RABasic : public MachineFunctionPass, public RegAllocBase { // context - MachineFunction *mf_; - const TargetMachine *tm_; - MachineRegisterInfo *mri_; - BitVector reservedRegs_; + MachineFunction *MF; + const TargetMachine *TM; + MachineRegisterInfo *MRI; + + BitVector ReservedRegs; // analyses - LiveStacks *ls_; - RenderMachineFunction *rmf_; + LiveStacks *LS; + RenderMachineFunction *RMF; // state - std::auto_ptr<Spiller> spiller_; + std::auto_ptr<Spiller> SpillerInstance; public: RABasic(); @@ -94,14 +95,14 @@ public: } /// RABasic analysis usage. - virtual void getAnalysisUsage(AnalysisUsage &au) const; + virtual void getAnalysisUsage(AnalysisUsage &AU) const; virtual void releaseMemory(); - virtual Spiller &spiller() { return *spiller_; } + virtual Spiller &spiller() { return *SpillerInstance; } - virtual unsigned selectOrSplit(LiveInterval &lvr, - SmallVectorImpl<LiveInterval*> &splitLVRs); + virtual unsigned selectOrSplit(LiveInterval &VirtReg, + SmallVectorImpl<LiveInterval*> &SplitVRegs); /// Perform register allocation. virtual bool runOnMachineFunction(MachineFunction &mf); @@ -116,25 +117,6 @@ char RABasic::ID = 0; } // end anonymous namespace -// We should not need to publish the initializer as long as no other passes -// require RABasic. -#if 0 // disable INITIALIZE_PASS -INITIALIZE_PASS_BEGIN(RABasic, "basic-regalloc", - "Basic Register Allocator", false, false) -INITIALIZE_PASS_DEPENDENCY(LiveIntervals) -INITIALIZE_PASS_DEPENDENCY(StrongPHIElimination) -INITIALIZE_AG_DEPENDENCY(RegisterCoalescer) -INITIALIZE_PASS_DEPENDENCY(CalculateSpillWeights) -INITIALIZE_PASS_DEPENDENCY(LiveStacks) -INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) -INITIALIZE_PASS_DEPENDENCY(VirtRegMap) -#ifndef NDEBUG -INITIALIZE_PASS_DEPENDENCY(RenderMachineFunction) -#endif -INITIALIZE_PASS_END(RABasic, "basic-regalloc", - "Basic Register Allocator", false, false) -#endif // disable INITIALIZE_PASS - RABasic::RABasic(): MachineFunctionPass(ID) { initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); @@ -148,58 +130,62 @@ RABasic::RABasic(): MachineFunctionPass(ID) { initializeRenderMachineFunctionPass(*PassRegistry::getPassRegistry()); } -void RABasic::getAnalysisUsage(AnalysisUsage &au) const { - au.setPreservesCFG(); - au.addRequired<AliasAnalysis>(); - au.addPreserved<AliasAnalysis>(); - au.addRequired<LiveIntervals>(); - au.addPreserved<SlotIndexes>(); +void RABasic::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesCFG(); + AU.addRequired<AliasAnalysis>(); + AU.addPreserved<AliasAnalysis>(); + AU.addRequired<LiveIntervals>(); + AU.addPreserved<SlotIndexes>(); if (StrongPHIElim) - au.addRequiredID(StrongPHIEliminationID); - au.addRequiredTransitive<RegisterCoalescer>(); - au.addRequired<CalculateSpillWeights>(); - au.addRequired<LiveStacks>(); - au.addPreserved<LiveStacks>(); - au.addRequiredID(MachineDominatorsID); - au.addPreservedID(MachineDominatorsID); - au.addRequired<MachineLoopInfo>(); - au.addPreserved<MachineLoopInfo>(); - au.addRequired<VirtRegMap>(); - au.addPreserved<VirtRegMap>(); - DEBUG(au.addRequired<RenderMachineFunction>()); - MachineFunctionPass::getAnalysisUsage(au); + AU.addRequiredID(StrongPHIEliminationID); + AU.addRequiredTransitive<RegisterCoalescer>(); + AU.addRequired<CalculateSpillWeights>(); + AU.addRequired<LiveStacks>(); + AU.addPreserved<LiveStacks>(); + AU.addRequiredID(MachineDominatorsID); + AU.addPreservedID(MachineDominatorsID); + AU.addRequired<MachineLoopInfo>(); + AU.addPreserved<MachineLoopInfo>(); + AU.addRequired<VirtRegMap>(); + AU.addPreserved<VirtRegMap>(); + DEBUG(AU.addRequired<RenderMachineFunction>()); + MachineFunctionPass::getAnalysisUsage(AU); } void RABasic::releaseMemory() { - spiller_.reset(0); + SpillerInstance.reset(0); RegAllocBase::releaseMemory(); } #ifndef NDEBUG // Verify each LiveIntervalUnion. void RegAllocBase::verify() { - LvrBitSet visitedVRegs; - OwningArrayPtr<LvrBitSet> unionVRegs(new LvrBitSet[physReg2liu_.numRegs()]); + LiveVirtRegBitSet VisitedVRegs; + OwningArrayPtr<LiveVirtRegBitSet> + unionVRegs(new LiveVirtRegBitSet[PhysReg2LiveUnion.numRegs()]); + // Verify disjoint unions. - for (unsigned preg = 0; preg < physReg2liu_.numRegs(); ++preg) { - DEBUG(PhysicalRegisterDescription prd(tri_); physReg2liu_[preg].dump(&prd)); - LvrBitSet &vregs = unionVRegs[preg]; - physReg2liu_[preg].verify(vregs); + for (unsigned PhysReg = 0; PhysReg < PhysReg2LiveUnion.numRegs(); ++PhysReg) { + DEBUG(PhysicalRegisterDescription PRD(TRI); + PhysReg2LiveUnion[PhysReg].dump(&PRD)); + LiveVirtRegBitSet &VRegs = unionVRegs[PhysReg]; + PhysReg2LiveUnion[PhysReg].verify(VRegs); // Union + intersection test could be done efficiently in one pass, but // don't add a method to SparseBitVector unless we really need it. - assert(!visitedVRegs.intersects(vregs) && "vreg in multiple unions"); - visitedVRegs |= vregs; + assert(!VisitedVRegs.intersects(VRegs) && "vreg in multiple unions"); + VisitedVRegs |= VRegs; } + // Verify vreg coverage. - for (LiveIntervals::iterator liItr = lis_->begin(), liEnd = lis_->end(); + for (LiveIntervals::iterator liItr = LIS->begin(), liEnd = LIS->end(); liItr != liEnd; ++liItr) { unsigned reg = liItr->first; if (TargetRegisterInfo::isPhysicalRegister(reg)) continue; - if (!vrm_->hasPhys(reg)) continue; // spilled? - unsigned preg = vrm_->getPhys(reg); - if (!unionVRegs[preg].test(reg)) { + if (!VRM->hasPhys(reg)) continue; // spilled? + unsigned PhysReg = VRM->getPhys(reg); + if (!unionVRegs[PhysReg].test(reg)) { dbgs() << "LiveVirtReg " << reg << " not in union " << - tri_->getName(preg) << "\n"; + TRI->getName(PhysReg) << "\n"; llvm_unreachable("unallocated live vreg"); } } @@ -212,31 +198,31 @@ void RegAllocBase::verify() { //===----------------------------------------------------------------------===// // Instantiate a LiveIntervalUnion for each physical register. -void RegAllocBase::LIUArray::init(unsigned nRegs) { - array_.reset(new LiveIntervalUnion[nRegs]); - nRegs_ = nRegs; - for (unsigned pr = 0; pr < nRegs; ++pr) { - array_[pr].init(pr); +void RegAllocBase::LiveUnionArray::init(unsigned NRegs) { + Array.reset(new LiveIntervalUnion[NRegs]); + NumRegs = NRegs; + for (unsigned RegNum = 0; RegNum < NRegs; ++RegNum) { + Array[RegNum].init(RegNum); } } void RegAllocBase::init(const TargetRegisterInfo &tri, VirtRegMap &vrm, LiveIntervals &lis) { - tri_ = &tri; - vrm_ = &vrm; - lis_ = &lis; - physReg2liu_.init(tri_->getNumRegs()); + TRI = &tri; + VRM = &vrm; + LIS = &lis; + PhysReg2LiveUnion.init(TRI->getNumRegs()); // Cache an interferece query for each physical reg - queries_.reset(new LiveIntervalUnion::Query[physReg2liu_.numRegs()]); + Queries.reset(new LiveIntervalUnion::Query[PhysReg2LiveUnion.numRegs()]); } -void RegAllocBase::LIUArray::clear() { - nRegs_ = 0; - array_.reset(0); +void RegAllocBase::LiveUnionArray::clear() { + NumRegs = 0; + Array.reset(0); } void RegAllocBase::releaseMemory() { - physReg2liu_.clear(); + PhysReg2LiveUnion.clear(); } namespace llvm { @@ -248,22 +234,23 @@ namespace llvm { /// to override the priority queue comparator. class LiveVirtRegQueue { typedef std::priority_queue - <LiveInterval*, std::vector<LiveInterval*>, LessSpillWeightPriority> PQ; - PQ pq_; + <LiveInterval*, std::vector<LiveInterval*>, LessSpillWeightPriority> + PriorityQ; + PriorityQ PQ; public: // Is the queue empty? - bool empty() { return pq_.empty(); } + bool empty() { return PQ.empty(); } // Get the highest priority lvr (top + pop) LiveInterval *get() { - LiveInterval *lvr = pq_.top(); - pq_.pop(); - return lvr; + LiveInterval *VirtReg = PQ.top(); + PQ.pop(); + return VirtReg; } // Add this lvr to the queue - void push(LiveInterval *lvr) { - pq_.push(lvr); + void push(LiveInterval *VirtReg) { + PQ.push(VirtReg); } }; } // end namespace llvm @@ -271,128 +258,132 @@ public: // Visit all the live virtual registers. If they are already assigned to a // physical register, unify them with the corresponding LiveIntervalUnion, // otherwise push them on the priority queue for later assignment. -void RegAllocBase::seedLiveVirtRegs(LiveVirtRegQueue &lvrQ) { - for (LiveIntervals::iterator liItr = lis_->begin(), liEnd = lis_->end(); - liItr != liEnd; ++liItr) { - unsigned reg = liItr->first; - LiveInterval &li = *liItr->second; - if (TargetRegisterInfo::isPhysicalRegister(reg)) { - physReg2liu_[reg].unify(li); +void RegAllocBase::seedLiveVirtRegs(LiveVirtRegQueue &VirtRegQ) { + for (LiveIntervals::iterator I = LIS->begin(), E = LIS->end(); I != E; ++I) { + unsigned RegNum = I->first; + LiveInterval &VirtReg = *I->second; + if (TargetRegisterInfo::isPhysicalRegister(RegNum)) { + PhysReg2LiveUnion[RegNum].unify(VirtReg); } else { - lvrQ.push(&li); + VirtRegQ.push(&VirtReg); } } } -// Top-level driver to manage the queue of unassigned LiveVirtRegs and call the +// Top-level driver to manage the queue of unassigned VirtRegs and call the // selectOrSplit implementation. void RegAllocBase::allocatePhysRegs() { - LiveVirtRegQueue lvrQ; - seedLiveVirtRegs(lvrQ); - while (!lvrQ.empty()) { - LiveInterval *lvr = lvrQ.get(); - typedef SmallVector<LiveInterval*, 4> LVRVec; - LVRVec splitLVRs; - unsigned availablePhysReg = selectOrSplit(*lvr, splitLVRs); - if (availablePhysReg) { - DEBUG(dbgs() << "allocating: " << tri_->getName(availablePhysReg) << - " " << *lvr << '\n'); - assert(!vrm_->hasPhys(lvr->reg) && "duplicate vreg in interval unions"); - vrm_->assignVirt2Phys(lvr->reg, availablePhysReg); - physReg2liu_[availablePhysReg].unify(*lvr); + + // Push each vreg onto a queue or "precolor" by adding it to a physreg union. + LiveVirtRegQueue VirtRegQ; + seedLiveVirtRegs(VirtRegQ); + + // Continue assigning vregs one at a time to available physical registers. + while (!VirtRegQ.empty()) { + // Pop the highest priority vreg. + LiveInterval *VirtReg = VirtRegQ.get(); + + // selectOrSplit requests the allocator to return an available physical + // register if possible and populate a list of new live intervals that + // result from splitting. + typedef SmallVector<LiveInterval*, 4> VirtRegVec; + VirtRegVec SplitVRegs; + unsigned AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs); + + if (AvailablePhysReg) { + DEBUG(dbgs() << "allocating: " << TRI->getName(AvailablePhysReg) << + " " << *VirtReg << '\n'); + assert(!VRM->hasPhys(VirtReg->reg) && "duplicate vreg in union"); + VRM->assignVirt2Phys(VirtReg->reg, AvailablePhysReg); + PhysReg2LiveUnion[AvailablePhysReg].unify(*VirtReg); } - for (LVRVec::iterator lvrI = splitLVRs.begin(), lvrEnd = splitLVRs.end(); - lvrI != lvrEnd; ++lvrI) { - if ((*lvrI)->empty()) continue; - DEBUG(dbgs() << "queuing new interval: " << **lvrI << "\n"); - assert(TargetRegisterInfo::isVirtualRegister((*lvrI)->reg) && + for (VirtRegVec::iterator I = SplitVRegs.begin(), E = SplitVRegs.end(); + I != E; ++I) { + LiveInterval* SplitVirtReg = *I; + if (SplitVirtReg->empty()) continue; + DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n"); + assert(TargetRegisterInfo::isVirtualRegister(SplitVirtReg->reg) && "expect split value in virtual register"); - lvrQ.push(*lvrI); + VirtRegQ.push(SplitVirtReg); } } } -// Check if this live virtual reg interferes with a physical register. If not, -// then check for interference on each register that aliases with the physical -// register. Return the interfering register. -unsigned RegAllocBase::checkPhysRegInterference(LiveInterval &lvr, - unsigned preg) { - if (query(lvr, preg).checkInterference()) - return preg; - for (const unsigned *asI = tri_->getAliasSet(preg); *asI; ++asI) { - if (query(lvr, *asI).checkInterference()) - return *asI; +// Check if this live virtual register interferes with a physical register. If +// not, then check for interference on each register that aliases with the +// physical register. Return the interfering register. +unsigned RegAllocBase::checkPhysRegInterference(LiveInterval &VirtReg, + unsigned PhysReg) { + if (query(VirtReg, PhysReg).checkInterference()) + return PhysReg; + for (const unsigned *AliasI = TRI->getAliasSet(PhysReg); *AliasI; ++AliasI) { + if (query(VirtReg, *AliasI).checkInterference()) + return *AliasI; } return 0; } -// Sort live virtual registers by their register number. -struct LessLiveVirtualReg - : public std::binary_function<LiveInterval, LiveInterval, bool> { - bool operator()(const LiveInterval *left, const LiveInterval *right) const { - return left->reg < right->reg; - } -}; - -// Spill all interferences currently assigned to this physical register. -void RegAllocBase::spillReg(LiveInterval& lvr, unsigned reg, - SmallVectorImpl<LiveInterval*> &splitLVRs) { - LiveIntervalUnion::Query &Q = query(lvr, reg); - const SmallVectorImpl<LiveInterval*> &pendingSpills = Q.interferingVRegs(); - - for (SmallVectorImpl<LiveInterval*>::const_iterator I = pendingSpills.begin(), - E = pendingSpills.end(); I != E; ++I) { - LiveInterval &spilledLVR = **I; +// Helper for spillInteferences() that spills all interfering vregs currently +// assigned to this physical register. +void RegAllocBase::spillReg(LiveInterval& VirtReg, unsigned PhysReg, + SmallVectorImpl<LiveInterval*> &SplitVRegs) { + LiveIntervalUnion::Query &Q = query(VirtReg, PhysReg); + assert(Q.seenAllInterferences() && "need collectInterferences()"); + const SmallVectorImpl<LiveInterval*> &PendingSpills = Q.interferingVRegs(); + + for (SmallVectorImpl<LiveInterval*>::const_iterator I = PendingSpills.begin(), + E = PendingSpills.end(); I != E; ++I) { + LiveInterval &SpilledVReg = **I; DEBUG(dbgs() << "extracting from " << - tri_->getName(reg) << " " << spilledLVR << '\n'); + TRI->getName(PhysReg) << " " << SpilledVReg << '\n'); // Deallocate the interfering vreg by removing it from the union. // A LiveInterval instance may not be in a union during modification! - physReg2liu_[reg].extract(spilledLVR); + PhysReg2LiveUnion[PhysReg].extract(SpilledVReg); // Clear the vreg assignment. - vrm_->clearVirt(spilledLVR.reg); + VRM->clearVirt(SpilledVReg.reg); // Spill the extracted interval. - spiller().spill(&spilledLVR, splitLVRs, pendingSpills); + spiller().spill(&SpilledVReg, SplitVRegs, PendingSpills); } // After extracting segments, the query's results are invalid. But keep the // contents valid until we're done accessing pendingSpills. Q.clear(); } -// Spill or split all live virtual registers currently unified under preg that -// interfere with lvr. The newly spilled or split live intervals are returned by -// appending them to splitLVRs. +// Spill or split all live virtual registers currently unified under PhysReg +// that interfere with VirtReg. The newly spilled or split live intervals are +// returned by appending them to SplitVRegs. bool -RegAllocBase::spillInterferences(LiveInterval &lvr, unsigned preg, - SmallVectorImpl<LiveInterval*> &splitLVRs) { +RegAllocBase::spillInterferences(LiveInterval &VirtReg, unsigned PhysReg, + SmallVectorImpl<LiveInterval*> &SplitVRegs) { // Record each interference and determine if all are spillable before mutating // either the union or live intervals. // Collect interferences assigned to the requested physical register. - LiveIntervalUnion::Query &QPreg = query(lvr, preg); - unsigned numInterferences = QPreg.collectInterferingVRegs(); + LiveIntervalUnion::Query &QPreg = query(VirtReg, PhysReg); + unsigned NumInterferences = QPreg.collectInterferingVRegs(); if (QPreg.seenUnspillableVReg()) { return false; } // Collect interferences assigned to any alias of the physical register. - for (const unsigned *asI = tri_->getAliasSet(preg); *asI; ++asI) { - LiveIntervalUnion::Query &QAlias = query(lvr, *asI); - numInterferences += QAlias.collectInterferingVRegs(); + for (const unsigned *asI = TRI->getAliasSet(PhysReg); *asI; ++asI) { + LiveIntervalUnion::Query &QAlias = query(VirtReg, *asI); + NumInterferences += QAlias.collectInterferingVRegs(); if (QAlias.seenUnspillableVReg()) { return false; } } - DEBUG(dbgs() << "spilling " << tri_->getName(preg) << - " interferences with " << lvr << "\n"); - assert(numInterferences > 0 && "expect interference"); - - // Spill each interfering vreg allocated to preg or an alias. - spillReg(lvr, preg, splitLVRs); - for (const unsigned *asI = tri_->getAliasSet(preg); *asI; ++asI) - spillReg(lvr, *asI, splitLVRs); + DEBUG(dbgs() << "spilling " << TRI->getName(PhysReg) << + " interferences with " << VirtReg << "\n"); + assert(NumInterferences > 0 && "expect interference"); + + // Spill each interfering vreg allocated to PhysReg or an alias. + spillReg(VirtReg, PhysReg, SplitVRegs); + for (const unsigned *AliasI = TRI->getAliasSet(PhysReg); *AliasI; ++AliasI) + spillReg(VirtReg, *AliasI, SplitVRegs); return true; } @@ -403,134 +394,135 @@ RegAllocBase::spillInterferences(LiveInterval &lvr, unsigned preg, // Driver for the register assignment and splitting heuristics. // Manages iteration over the LiveIntervalUnions. // -// Minimal implementation of register assignment and splitting--spills whenever -// we run out of registers. +// This is a minimal implementation of register assignment and splitting that +// spills whenever we run out of registers. // // selectOrSplit can only be called once per live virtual register. We then do a // single interference test for each register the correct class until we find an // available register. So, the number of interference tests in the worst case is // |vregs| * |machineregs|. And since the number of interference tests is -// minimal, there is no value in caching them. -unsigned RABasic::selectOrSplit(LiveInterval &lvr, - SmallVectorImpl<LiveInterval*> &splitLVRs) { +// minimal, there is no value in caching them outside the scope of +// selectOrSplit(). +unsigned RABasic::selectOrSplit(LiveInterval &VirtReg, + SmallVectorImpl<LiveInterval*> &SplitVRegs) { // Populate a list of physical register spill candidates. - SmallVector<unsigned, 8> pregSpillCands; + SmallVector<unsigned, 8> PhysRegSpillCands; // Check for an available register in this class. - const TargetRegisterClass *trc = mri_->getRegClass(lvr.reg); - for (TargetRegisterClass::iterator trcI = trc->allocation_order_begin(*mf_), - trcEnd = trc->allocation_order_end(*mf_); - trcI != trcEnd; ++trcI) { - unsigned preg = *trcI; - if (reservedRegs_.test(preg)) continue; - - // Check interference and intialize queries for this lvr as a side effect. - unsigned interfReg = checkPhysRegInterference(lvr, preg); + const TargetRegisterClass *TRC = MRI->getRegClass(VirtReg.reg); + DEBUG(dbgs() << "RegClass: " << TRC->getName() << ' '); + + for (TargetRegisterClass::iterator I = TRC->allocation_order_begin(*MF), + E = TRC->allocation_order_end(*MF); + I != E; ++I) { + + unsigned PhysReg = *I; + if (ReservedRegs.test(PhysReg)) continue; + + // Check interference and as a side effect, intialize queries for this + // VirtReg and its aliases. + unsigned interfReg = checkPhysRegInterference(VirtReg, PhysReg); if (interfReg == 0) { // Found an available register. - return preg; + return PhysReg; } LiveInterval *interferingVirtReg = - queries_[interfReg].firstInterference().liuSegPos()->liveVirtReg; + Queries[interfReg].firstInterference().liveUnionPos()->VirtReg; - // The current lvr must either spillable, or one of its interferences must - // have less spill weight. - if (interferingVirtReg->weight < lvr.weight ) { - pregSpillCands.push_back(preg); + // The current VirtReg must either spillable, or one of its interferences + // must have less spill weight. + if (interferingVirtReg->weight < VirtReg.weight ) { + PhysRegSpillCands.push_back(PhysReg); } } // Try to spill another interfering reg with less spill weight. // // FIXME: RAGreedy will sort this list by spill weight. - for (SmallVectorImpl<unsigned>::iterator pregI = pregSpillCands.begin(), - pregE = pregSpillCands.end(); pregI != pregE; ++pregI) { + for (SmallVectorImpl<unsigned>::iterator PhysRegI = PhysRegSpillCands.begin(), + PhysRegE = PhysRegSpillCands.end(); PhysRegI != PhysRegE; ++PhysRegI) { - if (!spillInterferences(lvr, *pregI, splitLVRs)) continue; + if (!spillInterferences(VirtReg, *PhysRegI, SplitVRegs)) continue; - unsigned interfReg = checkPhysRegInterference(lvr, *pregI); - if (interfReg != 0) { + unsigned InterferingReg = checkPhysRegInterference(VirtReg, *PhysRegI); + if (InterferingReg != 0) { const LiveSegment &seg = - *queries_[interfReg].firstInterference().liuSegPos(); - dbgs() << "spilling cannot free " << tri_->getName(*pregI) << - " for " << lvr.reg << " with interference " << *seg.liveVirtReg << "\n"; + *Queries[InterferingReg].firstInterference().liveUnionPos(); + + dbgs() << "spilling cannot free " << TRI->getName(*PhysRegI) << + " for " << VirtReg.reg << " with interference " << *seg.VirtReg << "\n"; llvm_unreachable("Interference after spill."); } // Tell the caller to allocate to this newly freed physical register. - return *pregI; + return *PhysRegI; } - // No other spill candidates were found, so spill the current lvr. - DEBUG(dbgs() << "spilling: " << lvr << '\n'); + // No other spill candidates were found, so spill the current VirtReg. + DEBUG(dbgs() << "spilling: " << VirtReg << '\n'); SmallVector<LiveInterval*, 1> pendingSpills; - spiller().spill(&lvr, splitLVRs, pendingSpills); + + spiller().spill(&VirtReg, SplitVRegs, pendingSpills); // The live virtual register requesting allocation was spilled, so tell // the caller not to allocate anything during this round. return 0; } -// Add newly allocated physical register to the MBB live in sets. +// Add newly allocated physical registers to the MBB live in sets. void RABasic::addMBBLiveIns() { - SmallVector<MachineBasicBlock*, 8> liveInMBBs; - MachineBasicBlock &entryMBB = *mf_->begin(); + typedef SmallVector<MachineBasicBlock*, 8> MBBVec; + MBBVec liveInMBBs; + MachineBasicBlock &entryMBB = *MF->begin(); + + for (unsigned PhysReg = 0; PhysReg < PhysReg2LiveUnion.numRegs(); ++PhysReg) { + LiveIntervalUnion &LiveUnion = PhysReg2LiveUnion[PhysReg]; + + for (LiveIntervalUnion::SegmentIter SI = LiveUnion.begin(), + SegEnd = LiveUnion.end(); + SI != SegEnd; ++SI) { - for (unsigned preg = 0; preg < physReg2liu_.numRegs(); ++preg) { - LiveIntervalUnion &liu = physReg2liu_[preg]; - for (LiveIntervalUnion::SegmentIter segI = liu.begin(), segE = liu.end(); - segI != segE; ++segI) { // Find the set of basic blocks which this range is live into... - if (lis_->findLiveInMBBs(segI->start, segI->end, liveInMBBs)) { - // And add the physreg for this interval to their live-in sets. - for (unsigned i = 0; i != liveInMBBs.size(); ++i) { - if (liveInMBBs[i] != &entryMBB) { - if (!liveInMBBs[i]->isLiveIn(preg)) { - liveInMBBs[i]->addLiveIn(preg); - } - } - } - liveInMBBs.clear(); + liveInMBBs.clear(); + if (!LIS->findLiveInMBBs(SI->Start, SI->End, liveInMBBs)) continue; + + // And add the physreg for this interval to their live-in sets. + for (MBBVec::iterator I = liveInMBBs.begin(), E = liveInMBBs.end(); + I != E; ++I) { + MachineBasicBlock *MBB = *I; + if (MBB == &entryMBB) continue; + if (MBB->isLiveIn(PhysReg)) continue; + MBB->addLiveIn(PhysReg); } } } } -namespace llvm { -Spiller *createInlineSpiller(MachineFunctionPass &pass, - MachineFunction &mf, - VirtRegMap &vrm); -} - bool RABasic::runOnMachineFunction(MachineFunction &mf) { DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n" << "********** Function: " << ((Value*)mf.getFunction())->getName() << '\n'); - mf_ = &mf; - tm_ = &mf.getTarget(); - mri_ = &mf.getRegInfo(); + MF = &mf; + TM = &mf.getTarget(); + MRI = &mf.getRegInfo(); - DEBUG(rmf_ = &getAnalysis<RenderMachineFunction>()); + DEBUG(RMF = &getAnalysis<RenderMachineFunction>()); - const TargetRegisterInfo *TRI = tm_->getRegisterInfo(); + const TargetRegisterInfo *TRI = TM->getRegisterInfo(); RegAllocBase::init(*TRI, getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>()); - reservedRegs_ = TRI->getReservedRegs(*mf_); + ReservedRegs = TRI->getReservedRegs(*MF); - // We may want to force InlineSpiller for this register allocator. For - // now we're also experimenting with the standard spiller. - // - //spiller_.reset(createInlineSpiller(*this, *mf_, *vrm_)); - spiller_.reset(createSpiller(*this, *mf_, *vrm_)); + SpillerInstance.reset(createSpiller(*this, *MF, *VRM)); allocatePhysRegs(); addMBBLiveIns(); // Diagnostic output before rewriting - DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm_ << "\n"); + DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *VRM << "\n"); // optional HTML output - DEBUG(rmf_->renderMachineFunction("After basic register allocation.", vrm_)); + DEBUG(RMF->renderMachineFunction("After basic register allocation.", VRM)); // FIXME: Verification currently must run before VirtRegRewriter. We should // make the rewriter a separate pass and override verifyAnalysis instead. When @@ -540,9 +532,11 @@ bool RABasic::runOnMachineFunction(MachineFunction &mf) { // Verify accuracy of LiveIntervals. The standard machine code verifier // ensures that each LiveIntervals covers all uses of the virtual reg. - // FIXME: MachineVerifier is currently broken when using the standard - // spiller. Enable it for InlineSpiller only. - // mf_->verify(this); + // FIXME: MachineVerifier is badly broken when using the standard + // spiller. Always use -spiller=inline with -verify-regalloc. Even with the + // inline spiller, some tests fail to verify because the coalescer does not + // always generate verifiable code. + MF->verify(this); // Verify that LiveIntervals are partitioned into unions and disjoint within // the unions. @@ -552,7 +546,7 @@ bool RABasic::runOnMachineFunction(MachineFunction &mf) { // Run rewriter std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter()); - rewriter->runOnMachineFunction(*mf_, *vrm_, lis_); + rewriter->runOnMachineFunction(*MF, *VRM, LIS); // The pass output is in VirtRegMap. Release all the transient data. releaseMemory(); |