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

1 files changed, 6 insertions, 11 deletions

diff --git a/lib/CodeGen/RegAllocBase.h b/lib/CodeGen/RegAllocBase.h
index 7f38c9b..65bec06 100644
--- a/lib/CodeGen/RegAllocBase.h
+++ b/lib/CodeGen/RegAllocBase.h
@@ -39,6 +39,7 @@
 
 #include "llvm/ADT/OwningPtr.h"
 #include "LiveIntervalUnion.h"
+#include <queue>
 
 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<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.
@@ -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<std::pair<float, unsigned> >&);
 
   void spillReg(LiveInterval &VirtReg, unsigned PhysReg,
                 SmallVectorImpl<LiveInterval*> &SplitVRegs);