commit 98d9648de7d571b2e6d139b65961a70d1833b0d7
author Jakob Stoklund Olesen <stoklund@2pi.dk> Tue Feb 22 23:01:52 2011 +0000
committer Jakob Stoklund Olesen <stoklund@2pi.dk> Tue Feb 22 23:01:52 2011 +0000
tree f48577311d98fe78b4eca6fa2498a89d5ad9eb07
parent 75b5409d3a9eb9b7dadcd13fff69590df94122dd

Change the RAGreedy register assignment order so large live ranges are allocated first.

This is based on the observation that long live ranges are more difficult to
allocate, so there is a better chance of solving the puzzle by handling the big
pieces first. The allocator will evict and split long alive ranges when they get
in the way.

RABasic is still using spill weights for its priority queue, so the interface to
the queue has been virtualized.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126259 91177308-0d34-0410-b5e6-96231b3b80d8

lib/CodeGen/RegAllocBasic.cpp

diff --git a/lib/CodeGen/RegAllocBasic.cpp b/lib/CodeGen/RegAllocBasic.cpp
index 045c8db..6923908 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 @@
 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 @@
 
   // state
   std::auto_ptr<Spiller> SpillerInstance;
-
+  std::priority_queue<LiveInterval*, std::vector<LiveInterval*>,
+                      CompSpillWeight> Queue;
 public:
   RABasic();
 
@@ -100,6 +110,18 @@
 
   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 @@
   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 @@
 // 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;
     }
   }