diff options
| -rw-r--r-- | lib/CodeGen/LiveIntervalUnion.cpp | 30 | ||||
| -rw-r--r-- | lib/CodeGen/LiveIntervalUnion.h | 41 | ||||
| -rw-r--r-- | lib/CodeGen/RegAllocBase.h | 107 | ||||
| -rw-r--r-- | lib/CodeGen/RegAllocBasic.cpp | 95 |
4 files changed, 160 insertions, 113 deletions
diff --git a/lib/CodeGen/LiveIntervalUnion.cpp b/lib/CodeGen/LiveIntervalUnion.cpp index dea228300e..6e2cd0fc31 100644 --- a/lib/CodeGen/LiveIntervalUnion.cpp +++ b/lib/CodeGen/LiveIntervalUnion.cpp @@ -21,6 +21,9 @@ using namespace llvm; // 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) { // Add this live virtual register to the union LiveVirtRegs::iterator pos = std::upper_bound(lvrs_.begin(), lvrs_.end(), @@ -34,19 +37,21 @@ void LiveIntervalUnion::unify(LiveInterval &lvr) { LiveSegment segment(lvrI->start, lvrI->end, lvr); segPos = segments_.insert(segPos, segment); assert(*segPos == segment && "need equal val for equal key"); +#ifndef NDEBUG + // check for overlap (inductively) + if (segPos != segments_.begin()) { + SegmentIter prevPos = segPos; + --prevPos; + assert(prevPos->end <= segment.start && "overlapping segments" ); + } + SegmentIter nextPos = segPos; + ++nextPos; + if (nextPos != segments_.end()) + assert(segment.end <= nextPos->start && "overlapping segments" ); +#endif // NDEBUG } } -namespace { - -// Keep LVRs sorted for fast membership test and extraction. -struct LessReg - : public std::binary_function<LiveInterval*, LiveInterval*, bool> { - bool operator()(const LiveInterval *left, const LiveInterval *right) const { - return left->reg < right->reg; - } -}; - // 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 // @@ -67,10 +72,8 @@ struct LessReg // 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, +static SegmentIter upperBound(SegmentIter segBegin, SegmentIter segEnd, const LiveRange &lvrSeg) { assert(lvrSeg.end > segBegin->start && "segment iterator precondition"); @@ -84,7 +87,6 @@ SegmentIter upperBound(SegmentIter segBegin, } return segI; } -} // end anonymous namespace // Private interface accessed by Query. // diff --git a/lib/CodeGen/LiveIntervalUnion.h b/lib/CodeGen/LiveIntervalUnion.h index 3953c5930a..1eb380fa17 100644 --- a/lib/CodeGen/LiveIntervalUnion.h +++ b/lib/CodeGen/LiveIntervalUnion.h @@ -23,13 +23,16 @@ namespace llvm { -// A LiveSegment is a copy of a LiveRange object used within -// LiveIntervalUnion. LiveSegment additionally contains a pointer to its -// original live virtual register (LiveInterval). This allows quick lookup of -// the live virtual register as we iterate over live segments in a union. Note -// that LiveRange is misnamed and actually represents only a single contiguous -// interval within a virtual register's liveness. To limit confusion, in this -// file we refer it as a live segment. +/// A LiveSegment is a copy of a LiveRange object used within +/// LiveIntervalUnion. LiveSegment additionally contains a pointer to its +/// original live virtual register (LiveInterval). This allows quick lookup of +/// the live virtual register as we iterate over live segments in a union. Note +/// that LiveRange is misnamed and actually represents only a single contiguous +/// 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). +/// If LiveRange is modified to represent a closed interval, so should this. struct LiveSegment { SlotIndex start; SlotIndex end; @@ -46,16 +49,10 @@ struct LiveSegment { return !operator==(ls); } - bool operator<(const LiveSegment &ls) const { - return start < ls.start || (start == ls.start && end < ls.end); - } + // Order segments by starting point only--we expect them to be disjoint. + bool operator<(const LiveSegment &ls) const { return start < ls.start; } }; -/// 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 operator<(SlotIndex V, const LiveSegment &ls) { return V < ls.start; } @@ -64,6 +61,11 @@ inline bool operator<(const LiveSegment &ls, SlotIndex V) { return ls.start < V; } +/// 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; +} + /// Union of live intervals that are strong candidates for coalescing into a /// single register (either physical or virtual depending on the context). We /// expect the constituent live intervals to be disjoint, although we may @@ -100,13 +102,18 @@ private: public: // default ctor avoids placement new LiveIntervalUnion() : repReg_(0) {} - + + // Initialize the union by associating it with a representative register + // number. void init(unsigned repReg) { repReg_ = repReg; } + // 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(); } - /// FIXME: !!!!!!!!!!! Keeps a non-const ref + // 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); // FIXME: needed by RegAllocGreedy diff --git a/lib/CodeGen/RegAllocBase.h b/lib/CodeGen/RegAllocBase.h index d54363536f..1534c0d7eb 100644 --- a/lib/CodeGen/RegAllocBase.h +++ b/lib/CodeGen/RegAllocBase.h @@ -37,17 +37,29 @@ #ifndef LLVM_CODEGEN_REGALLOCBASE #define LLVM_CODEGEN_REGALLOCBASE -#include "LiveIntervalUnion.h" -#include "VirtRegMap.h" -#include "llvm/CodeGen/LiveIntervalAnalysis.h" -#include "llvm/Target/TargetRegisterInfo.h" #include "llvm/ADT/OwningPtr.h" -#include <vector> -#include <queue> namespace llvm { +template<typename T> class SmallVectorImpl; +class TargetRegisterInfo; class VirtRegMap; +class LiveIntervals; + +// Heuristic that determines the priority of assigning virtual to physical +// registers. The main impact of the heuristic is expected to be compile time. +// 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; + } +}; + +// Forward declare a priority queue of live virtual registers. If an +// implementation needs to prioritize by anything other than spill weight, then +// this will become an abstract base class with virtual calls to push/get. +class LiveVirtRegQueue; /// RegAllocBase provides the register allocation driver and interface that can /// be extended to add interesting heuristics. @@ -58,9 +70,6 @@ class VirtRegMap; /// standard comparator. class RegAllocBase { protected: - typedef SmallVector<LiveInterval*, 4> LiveVirtRegs; - typedef LiveVirtRegs::iterator LVRIter; - // Array of LiveIntervalUnions indexed by physical register. class LIUArray { unsigned nRegs_; @@ -92,18 +101,20 @@ protected: // A RegAlloc pass should call this before allocatePhysRegs. void init(const TargetRegisterInfo &tri, VirtRegMap &vrm, LiveIntervals &lis); - // The top-level driver. Specialize with the comparator that determines the - // priority of assigning live virtual registers. The output is a VirtRegMap - // that us updated with physical register assignments. - template<typename LICompare> - void allocatePhysRegs(LICompare liCompare); + // The top-level driver. The output is a VirtRegMap that us updated with + // physical register assignments. + // + // If an implementation wants to override the LiveInterval comparator, we + // should modify this interface to allow passing in an instance derived from + // LiveVirtRegQueue. + void allocatePhysRegs(); // 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 LiveVirtRegs. It is up to the splitter to + // 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, - LiveVirtRegs &splitLVRs) = 0; + SmallVectorImpl<LiveInterval*> &splitLVRs) = 0; // A RegAlloc pass should call this when PassManager releases its memory. virtual void releaseMemory(); @@ -113,69 +124,9 @@ protected: bool checkPhysRegInterference(LiveIntervalUnion::Query &query, unsigned preg); private: - template<typename PQ> - void seedLiveVirtRegs(PQ &lvrQ); + void seedLiveVirtRegs(LiveVirtRegQueue &lvrQ); }; -// Heuristic that determines the priority of assigning virtual to physical -// registers. The main impact of the heuristic is expected to be compile time. -// 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; - } -}; - -// 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. -template<typename PQ> -void RegAllocBase::seedLiveVirtRegs(PQ &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); - } - else { - lvrQ.push(&li); - } - } -} - -// Top-level driver to manage the queue of unassigned LiveVirtRegs and call the -// selectOrSplit implementation. -template<typename LICompare> -void RegAllocBase::allocatePhysRegs(LICompare liCompare) { - typedef std::priority_queue - <LiveInterval*, std::vector<LiveInterval*>, LICompare> LiveVirtRegQueue; - - LiveVirtRegQueue lvrQ(liCompare); - seedLiveVirtRegs(lvrQ); - while (!lvrQ.empty()) { - LiveInterval *lvr = lvrQ.top(); - lvrQ.pop(); - LiveVirtRegs splitLVRs; - unsigned availablePhysReg = selectOrSplit(*lvr, splitLVRs); - if (availablePhysReg) { - assert(splitLVRs.empty() && "inconsistent splitting"); - assert(!vrm_->hasPhys(lvr->reg) && "duplicate vreg in interval unions"); - vrm_->assignVirt2Phys(lvr->reg, availablePhysReg); - physReg2liu_[availablePhysReg].unify(*lvr); - } - else { - for (LVRIter lvrI = splitLVRs.begin(), lvrEnd = splitLVRs.end(); - lvrI != lvrEnd; ++lvrI ) { - assert(TargetRegisterInfo::isVirtualRegister((*lvrI)->reg) && - "expect split value in virtual register"); - lvrQ.push(*lvrI); - } - } - } -} - } // end namespace llvm #endif // !defined(LLVM_CODEGEN_REGALLOCBASE) diff --git a/lib/CodeGen/RegAllocBasic.cpp b/lib/CodeGen/RegAllocBasic.cpp index ce5f9cfce8..83999d9eb1 100644 --- a/lib/CodeGen/RegAllocBasic.cpp +++ b/lib/CodeGen/RegAllocBasic.cpp @@ -13,6 +13,7 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "regalloc" +#include "LiveIntervalUnion.h" #include "RegAllocBase.h" #include "RenderMachineFunction.h" #include "Spiller.h" @@ -33,6 +34,14 @@ #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" +#include "VirtRegMap.h" +#include "llvm/CodeGen/LiveIntervalAnalysis.h" +#include "llvm/Target/TargetRegisterInfo.h" + + +#include <vector> +#include <queue> + using namespace llvm; static RegisterRegAlloc basicRegAlloc("basic", "basic register allocator", @@ -72,7 +81,8 @@ public: virtual void releaseMemory(); - virtual unsigned selectOrSplit(LiveInterval &lvr, LiveVirtRegs &splitLVRs); + virtual unsigned selectOrSplit(LiveInterval &lvr, + SmallVectorImpl<LiveInterval*> &splitLVRs); /// Perform register allocation. virtual bool runOnMachineFunction(MachineFunction &mf); @@ -101,7 +111,7 @@ INITIALIZE_PASS_DEPENDENCY(RenderMachineFunction) #endif INITIALIZE_PASS_END(RABasic, "basic-regalloc", "Basic Register Allocator", false, false) -#endif // INITIALIZE_PASS +#endif // disable INITIALIZE_PASS RABasic::RABasic(): MachineFunctionPass(ID) { initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); @@ -168,6 +178,79 @@ void RegAllocBase::releaseMemory() { physReg2liu_.clear(); } +namespace llvm { +/// This class defines a queue of live virtual registers prioritized by spill +/// weight. The heaviest vreg is popped first. +/// +/// Currently, this is trivial wrapper that gives us an opaque type in the +/// header, but we may later give it a virtual interface for register allocators +/// to override the priority queue comparator. +class LiveVirtRegQueue { + typedef std::priority_queue + <LiveInterval*, std::vector<LiveInterval*>, LessSpillWeightPriority> PQ; + PQ pq_; + +public: + // Is the queue empty? + bool empty() { return pq_.empty(); } + + // Get the highest priority lvr (top + pop) + LiveInterval *get() { + LiveInterval *lvr = pq_.top(); + pq_.pop(); + return lvr; + } + // Add this lvr to the queue + void push(LiveInterval *lvr) { + pq_.push(lvr); + } +}; +} // end namespace llvm + +// 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); + } + else { + lvrQ.push(&li); + } + } +} + +// Top-level driver to manage the queue of unassigned LiveVirtRegs 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) { + assert(splitLVRs.empty() && "inconsistent splitting"); + assert(!vrm_->hasPhys(lvr->reg) && "duplicate vreg in interval unions"); + vrm_->assignVirt2Phys(lvr->reg, availablePhysReg); + physReg2liu_[availablePhysReg].unify(*lvr); + } + else { + for (LVRVec::iterator lvrI = splitLVRs.begin(), lvrEnd = splitLVRs.end(); + lvrI != lvrEnd; ++lvrI) { + assert(TargetRegisterInfo::isVirtualRegister((*lvrI)->reg) && + "expect split value in virtual register"); + lvrQ.push(*lvrI); + } + } + } +} + // 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. @@ -201,7 +284,8 @@ bool RegAllocBase::checkPhysRegInterference(LiveIntervalUnion::Query &query, // 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, LiveVirtRegs &splitLVRs) { +unsigned RABasic::selectOrSplit(LiveInterval &lvr, + SmallVectorImpl<LiveInterval*> &splitLVRs) { // Check for an available reg in this class. const TargetRegisterClass *trc = mri_->getRegClass(lvr.reg); for (TargetRegisterClass::iterator trcI = trc->allocation_order_begin(*mf_), @@ -238,7 +322,7 @@ bool RABasic::runOnMachineFunction(MachineFunction &mf) { spiller_.reset(createSpiller(*this, *mf_, *vrm_)); - allocatePhysRegs(LessSpillWeightPriority()); + allocatePhysRegs(); // Diagnostic output before rewriting DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm_ << "\n"); @@ -249,6 +333,9 @@ bool RABasic::runOnMachineFunction(MachineFunction &mf) { // Run rewriter std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter()); rewriter->runOnMachineFunction(*mf_, *vrm_, lis_); + + // The pass output is in VirtRegMap. Release all the transient data. + releaseMemory(); return true; } |