diff options
| -rw-r--r-- | lib/CodeGen/RegAllocBase.h | 15 | ||||
| -rw-r--r-- | lib/CodeGen/RegAllocBasic.cpp | 60 | ||||
| -rw-r--r-- | lib/CodeGen/RegAllocGreedy.cpp | 41 |
3 files changed, 69 insertions, 47 deletions
diff --git a/lib/CodeGen/RegAllocBase.h b/lib/CodeGen/RegAllocBase.h index 8c7e5f53b8..5af0ce79ac 100644 --- a/lib/CodeGen/RegAllocBase.h +++ b/lib/CodeGen/RegAllocBase.h @@ -39,7 +39,6 @@ #include "llvm/ADT/OwningPtr.h" #include "LiveIntervalUnion.h" -#include <queue> namespace llvm { @@ -58,8 +57,8 @@ class LiveVirtRegQueue; /// be extended to add interesting heuristics. /// /// Register allocators must override the selectOrSplit() method to implement -/// live range splitting. They may also override getPriority() which otherwise -/// defaults to the spill weight computed by CalculateSpillWeights. +/// live range splitting. They must also override enqueue/dequeue to provide an +/// assignment order. class RegAllocBase { LiveIntervalUnion::Allocator UnionAllocator; protected: @@ -120,9 +119,11 @@ 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; + /// enqueue - Add VirtReg to the priority queue of unassigned registers. + virtual void enqueue(LiveInterval *LI) = 0; + + /// dequeue - Return the next unassigned register, or NULL. + virtual LiveInterval *dequeue() = 0; // A RegAlloc pass should override this to provide the allocation heuristics. // Each call must guarantee forward progess by returning an available PhysReg @@ -170,7 +171,7 @@ public: static bool VerifyEnabled; private: - void seedLiveVirtRegs(std::priority_queue<std::pair<float, unsigned> >&); + void seedLiveRegs(); void spillReg(LiveInterval &VirtReg, unsigned PhysReg, SmallVectorImpl<LiveInterval*> &SplitVRegs); diff --git a/lib/CodeGen/RegAllocBasic.cpp b/lib/CodeGen/RegAllocBasic.cpp index 045c8db9da..6923908a32 100644 --- a/lib/CodeGen/RegAllocBasic.cpp +++ b/lib/CodeGen/RegAllocBasic.cpp @@ -45,6 +45,7 @@ #include "llvm/Support/Timer.h" #include <cstdlib> +#include <queue> using namespace llvm; @@ -65,6 +66,14 @@ const char *RegAllocBase::TimerGroupName = "Register Allocation"; bool RegAllocBase::VerifyEnabled = false; namespace { + struct CompSpillWeight { + bool operator()(LiveInterval *A, LiveInterval *B) const { + return A->weight < B->weight; + } + }; +} + +namespace { /// RABasic provides a minimal implementation of the basic register allocation /// algorithm. It prioritizes live virtual registers by spill weight and spills /// whenever a register is unavailable. This is not practical in production but @@ -82,7 +91,8 @@ class RABasic : public MachineFunctionPass, public RegAllocBase // state std::auto_ptr<Spiller> SpillerInstance; - + std::priority_queue<LiveInterval*, std::vector<LiveInterval*>, + CompSpillWeight> Queue; public: RABasic(); @@ -100,6 +110,18 @@ public: virtual float getPriority(LiveInterval *LI) { return LI->weight; } + virtual void enqueue(LiveInterval *LI) { + Queue.push(LI); + } + + virtual LiveInterval *dequeue() { + if (Queue.empty()) + return 0; + LiveInterval *LI = Queue.top(); + Queue.pop(); + return LI; + } + virtual unsigned selectOrSplit(LiveInterval &VirtReg, SmallVectorImpl<LiveInterval*> &SplitVRegs); @@ -227,18 +249,17 @@ void RegAllocBase::releaseMemory() { PhysReg2LiveUnion.clear(); } -// 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(std::priority_queue<std::pair<float, unsigned> > &VirtRegQ) { +// Visit all the live 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::seedLiveRegs() { 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 - VirtRegQ.push(std::make_pair(getPriority(&VirtReg), RegNum)); + enqueue(&VirtReg); } } @@ -263,38 +284,31 @@ void RegAllocBase::unassign(LiveInterval &VirtReg, unsigned PhysReg) { // Top-level driver to manage the queue of unassigned VirtRegs and call the // selectOrSplit implementation. void RegAllocBase::allocatePhysRegs() { - - // Push each vreg onto a queue or "precolor" by adding it to a physreg union. - std::priority_queue<std::pair<float, unsigned> > VirtRegQ; - seedLiveVirtRegs(VirtRegQ); + seedLiveRegs(); // Continue assigning vregs one at a time to available physical registers. - while (!VirtRegQ.empty()) { - // Pop the highest priority vreg. - LiveInterval &VirtReg = LIS->getInterval(VirtRegQ.top().second); - VirtRegQ.pop(); - + while (LiveInterval *VirtReg = dequeue()) { // selectOrSplit requests the allocator to return an available physical // register if possible and populate a list of new live intervals that // result from splitting. - DEBUG(dbgs() << "\nselectOrSplit " << MRI->getRegClass(VirtReg.reg)->getName() - << ':' << VirtReg << '\n'); + DEBUG(dbgs() << "\nselectOrSplit " + << MRI->getRegClass(VirtReg->reg)->getName() + << ':' << *VirtReg << '\n'); typedef SmallVector<LiveInterval*, 4> VirtRegVec; VirtRegVec SplitVRegs; - unsigned AvailablePhysReg = selectOrSplit(VirtReg, SplitVRegs); + unsigned AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs); if (AvailablePhysReg) - assign(VirtReg, AvailablePhysReg); + assign(*VirtReg, AvailablePhysReg); for (VirtRegVec::iterator I = SplitVRegs.begin(), E = SplitVRegs.end(); I != E; ++I) { - LiveInterval* SplitVirtReg = *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"); - VirtRegQ.push(std::make_pair(getPriority(SplitVirtReg), - SplitVirtReg->reg)); + enqueue(SplitVirtReg); ++NumNewQueued; } } diff --git a/lib/CodeGen/RegAllocGreedy.cpp b/lib/CodeGen/RegAllocGreedy.cpp index 378219b97b..e1b9f3702f 100644 --- a/lib/CodeGen/RegAllocGreedy.cpp +++ b/lib/CodeGen/RegAllocGreedy.cpp @@ -43,6 +43,8 @@ #include "llvm/Support/raw_ostream.h" #include "llvm/Support/Timer.h" +#include <queue> + using namespace llvm; STATISTIC(NumGlobalSplits, "Number of split global live ranges"); @@ -71,6 +73,7 @@ class RAGreedy : public MachineFunctionPass, public RegAllocBase { // state std::auto_ptr<Spiller> SpillerInstance; std::auto_ptr<SplitAnalysis> SA; + std::priority_queue<std::pair<unsigned, unsigned> > Queue; // splitting state. @@ -91,13 +94,10 @@ public: /// RAGreedy analysis usage. virtual void getAnalysisUsage(AnalysisUsage &AU) const; - virtual void releaseMemory(); - virtual Spiller &spiller() { return *SpillerInstance; } - - virtual float getPriority(LiveInterval *LI); - + virtual void enqueue(LiveInterval *LI); + virtual LiveInterval *dequeue(); virtual unsigned selectOrSplit(LiveInterval&, SmallVectorImpl<LiveInterval*>&); @@ -186,22 +186,29 @@ void RAGreedy::releaseMemory() { RegAllocBase::releaseMemory(); } -float RAGreedy::getPriority(LiveInterval *LI) { - float Priority = LI->weight; +void RAGreedy::enqueue(LiveInterval *LI) { + // Prioritize live ranges by size, assigning larger ranges first. + // The queue holds (size, reg) pairs. + unsigned Size = LI->getSize(); + unsigned Reg = LI->reg; + assert(TargetRegisterInfo::isVirtualRegister(Reg) && + "Can only enqueue virtual registers"); - // Prioritize hinted registers so they are allocated first. - std::pair<unsigned, unsigned> Hint; - if (Hint.first || Hint.second) { - // The hint can be target specific, a virtual register, or a physreg. - Priority *= 2; + // Boost ranges that have a physical register hint. + unsigned Hint = VRM->getRegAllocPref(Reg); + if (TargetRegisterInfo::isPhysicalRegister(Hint)) + Size |= (1u << 30); - // Prefer physreg hints above anything else. - if (Hint.first == 0 && TargetRegisterInfo::isPhysicalRegister(Hint.second)) - Priority *= 2; - } - return Priority; + Queue.push(std::make_pair(Size, Reg)); } +LiveInterval *RAGreedy::dequeue() { + if (Queue.empty()) + return 0; + LiveInterval *LI = &LIS->getInterval(Queue.top().second); + Queue.pop(); + return LI; +} //===----------------------------------------------------------------------===// // Register Reassignment |