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

1 files changed, 8 insertions, 7 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);