From d0bec3e62c98b1f0ef3a41db8f95599b2014c131 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Wed, 8 Dec 2010 22:22:41 +0000 Subject: [PATCH] Store (priority,regnum) pairs in the priority queue instead of providing an abstract priority queue interface in subclasses that want to override the priority calculations. Subclasses must provide a getPriority() implementation instead. This approach requires less code as long as priorities are expressable as simple floats, and it avoids the dangers of defining potentially expensive priority comparison functions. It also should speed up priority_queue operations since they no longer have to chase pointers when comparing registers. This is not measurable, though. Preferably, we shouldn't use floats to guide code generation. The use of floats here is derived from the use of floats for spill weights. Spill weights have a dynamic range that doesn't lend itself easily to a fixpoint implementation. When someone invents a stable spill weight representation, it can be reused for allocation priorities. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121294 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/RegAllocBase.h | 17 ++++-------- lib/CodeGen/RegAllocBasic.cpp | 63 ++++++++++++------------------------------ lib/CodeGen/RegAllocGreedy.cpp | 2 ++ 3 files changed, 25 insertions(+), 57 deletions(-) diff --git a/lib/CodeGen/RegAllocBase.h b/lib/CodeGen/RegAllocBase.h index 7f38c9b95a9..65bec06c712 100644 --- a/lib/CodeGen/RegAllocBase.h +++ b/lib/CodeGen/RegAllocBase.h @@ -39,6 +39,7 @@ #include "llvm/ADT/OwningPtr.h" #include "LiveIntervalUnion.h" +#include namespace llvm { @@ -48,16 +49,6 @@ class VirtRegMap; class LiveIntervals; class Spiller; -// 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 { - 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. @@ -128,6 +119,10 @@ protected: // Get a temporary reference to a Spiller instance. virtual Spiller &spiller() = 0; + // getPriority - Calculate the allocation priority for VirtReg. + // Virtual registers with higher priorities are allocated first. + virtual float getPriority(LiveInterval *LI) = 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 @@ -158,7 +153,7 @@ protected: #endif private: - void seedLiveVirtRegs(LiveVirtRegQueue &VirtRegQ); + void seedLiveVirtRegs(std::priority_queue >&); void spillReg(LiveInterval &VirtReg, unsigned PhysReg, SmallVectorImpl &SplitVRegs); diff --git a/lib/CodeGen/RegAllocBasic.cpp b/lib/CodeGen/RegAllocBasic.cpp index d0e63551290..88446aa5056 100644 --- a/lib/CodeGen/RegAllocBasic.cpp +++ b/lib/CodeGen/RegAllocBasic.cpp @@ -43,8 +43,6 @@ #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" -#include -#include #include using namespace llvm; @@ -103,6 +101,8 @@ public: virtual Spiller &spiller() { return *SpillerInstance; } + virtual float getPriority(LiveInterval *LI) { return LI->weight; } + virtual unsigned selectOrSplit(LiveInterval &VirtReg, SmallVectorImpl &SplitVRegs); @@ -230,49 +230,18 @@ void RegAllocBase::releaseMemory() { PhysReg2LiveUnion.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 - , LessSpillWeightPriority> - PriorityQ; - PriorityQ PQ; - -public: - // Is the queue empty? - bool empty() { return PQ.empty(); } - - // Get the highest priority lvr (top + pop) - LiveInterval *get() { - LiveInterval *VirtReg = PQ.top(); - PQ.pop(); - return VirtReg; - } - // Add this lvr to the queue - void push(LiveInterval *VirtReg) { - PQ.push(VirtReg); - } -}; -} // 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 &VirtRegQ) { +void RegAllocBase:: +seedLiveVirtRegs(std::priority_queue > &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)) { + if (TargetRegisterInfo::isPhysicalRegister(RegNum)) PhysReg2LiveUnion[RegNum].unify(VirtReg); - } - else { - VirtRegQ.push(&VirtReg); - } + else + VirtRegQ.push(std::make_pair(getPriority(&VirtReg), RegNum)); } } @@ -281,27 +250,28 @@ void RegAllocBase::seedLiveVirtRegs(LiveVirtRegQueue &VirtRegQ) { void RegAllocBase::allocatePhysRegs() { // Push each vreg onto a queue or "precolor" by adding it to a physreg union. - LiveVirtRegQueue VirtRegQ; + std::priority_queue > 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(); + LiveInterval &VirtReg = LIS->getInterval(VirtRegQ.top().second); + VirtRegQ.pop(); // 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 VirtRegVec; VirtRegVec SplitVRegs; - unsigned AvailablePhysReg = selectOrSplit(*VirtReg, 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); + " " << VirtReg << '\n'); + assert(!VRM->hasPhys(VirtReg.reg) && "duplicate vreg in union"); + VRM->assignVirt2Phys(VirtReg.reg, AvailablePhysReg); + PhysReg2LiveUnion[AvailablePhysReg].unify(VirtReg); } for (VirtRegVec::iterator I = SplitVRegs.begin(), E = SplitVRegs.end(); I != E; ++I) { @@ -310,7 +280,8 @@ void RegAllocBase::allocatePhysRegs() { DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n"); assert(TargetRegisterInfo::isVirtualRegister(SplitVirtReg->reg) && "expect split value in virtual register"); - VirtRegQ.push(SplitVirtReg); + VirtRegQ.push(std::make_pair(getPriority(SplitVirtReg), + SplitVirtReg->reg)); } } } diff --git a/lib/CodeGen/RegAllocGreedy.cpp b/lib/CodeGen/RegAllocGreedy.cpp index 96e5531840b..5f2be811aa6 100644 --- a/lib/CodeGen/RegAllocGreedy.cpp +++ b/lib/CodeGen/RegAllocGreedy.cpp @@ -70,6 +70,8 @@ public: virtual Spiller &spiller() { return *SpillerInstance; } + virtual float getPriority(LiveInterval *LI) { return LI->weight; } + virtual unsigned selectOrSplit(LiveInterval &VirtReg, SmallVectorImpl &SplitVRegs); -- 2.11.0