Switch spill weights from a basic loop depth estimation to BlockFrequencyInfo.

The main advantages here are way better heuristics, taking into account not
just loop depth but also __builtin_expect and other static heuristics and will
eventually learn how to use profile info. Most of the work in this patch is
pushing the MachineBlockFrequencyInfo analysis into the right places.

This is good for a 5% speedup on zlib's deflate (x86_64), there were some very
unfortunate spilling decisions in its hottest loop in longest_match(). Other
benchmarks I tried were mostly neutral.

This changes register allocation in subtle ways, update the tests for it.
2012-02-20-MachineCPBug.ll was deleted as it's very fragile and the instruction
it looked for was gone already (but the FileCheck pattern picked up unrelated
stuff).

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

4 files changed, 13 insertions, 7 deletions

diff --git a/include/llvm/CodeGen/CalcSpillWeights.h b/include/llvm/CodeGen/CalcSpillWeights.h
index 9cd2dec..c8ec764 100644
--- a/include/llvm/CodeGen/CalcSpillWeights.h
+++ b/include/llvm/CodeGen/CalcSpillWeights.h
@@ -18,6 +18,7 @@ namespace llvm {
 
   class LiveInterval;
   class LiveIntervals;
+  class MachineBlockFrequencyInfo;
   class MachineLoopInfo;
 
   /// normalizeSpillWeight - The spill weight of a live interval is computed as:
@@ -43,11 +44,13 @@ namespace llvm {
     MachineFunction &MF;
     LiveIntervals &LIS;
     const MachineLoopInfo &Loops;
+    const MachineBlockFrequencyInfo &MBFI;
     DenseMap<unsigned, float> Hint;
   public:
     VirtRegAuxInfo(MachineFunction &mf, LiveIntervals &lis,
-                   const MachineLoopInfo &loops) :
-      MF(mf), LIS(lis), Loops(loops) {}
+                   const MachineLoopInfo &loops,
+                   const MachineBlockFrequencyInfo &mbfi)
+        : MF(mf), LIS(lis), Loops(loops), MBFI(mbfi) {}
 
     /// CalculateWeightAndHint - (re)compute li's spill weight and allocation
     /// hint.
diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h
index 7d72f37..ffb07a5 100644
--- a/include/llvm/CodeGen/LiveIntervalAnalysis.h
+++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h
@@ -35,6 +35,7 @@ namespace llvm {
 
   class AliasAnalysis;
   class BitVector;
+  class BlockFrequency;
   class LiveRangeCalc;
   class LiveVariables;
   class MachineDominatorTree;
@@ -99,7 +100,7 @@ namespace llvm {
     virtual ~LiveIntervals();
 
     // Calculate the spill weight to assign to a single instruction.
-    static float getSpillWeight(bool isDef, bool isUse, unsigned loopDepth);
+    static float getSpillWeight(bool isDef, bool isUse, BlockFrequency freq);
 
     LiveInterval &getInterval(unsigned Reg) {
       LiveInterval *LI = VirtRegIntervals[Reg];
diff --git a/include/llvm/CodeGen/LiveRangeEdit.h b/include/llvm/CodeGen/LiveRangeEdit.h
index e59276f..545bd0c 100644
--- a/include/llvm/CodeGen/LiveRangeEdit.h
+++ b/include/llvm/CodeGen/LiveRangeEdit.h
@@ -27,6 +27,7 @@ namespace llvm {
 
 class AliasAnalysis;
 class LiveIntervals;
+class MachineBlockFrequencyInfo;
 class MachineLoopInfo;
 class MachineRegisterInfo;
 class VirtRegMap;
@@ -201,7 +202,8 @@ public:
   /// calculateRegClassAndHint - Recompute register class and hint for each new
   /// register.
   void calculateRegClassAndHint(MachineFunction&,
-                                const MachineLoopInfo&);
+                                const MachineLoopInfo&,
+                                const MachineBlockFrequencyInfo&);
 };
 
 }
diff --git a/include/llvm/CodeGen/RegAllocPBQP.h b/include/llvm/CodeGen/RegAllocPBQP.h
index 8b8e3d9..6f2d139 100644
--- a/include/llvm/CodeGen/RegAllocPBQP.h
+++ b/include/llvm/CodeGen/RegAllocPBQP.h
@@ -26,8 +26,8 @@
 namespace llvm {
 
   class LiveIntervals;
+  class MachineBlockFrequencyInfo;
   class MachineFunction;
-  class MachineLoopInfo;
   class TargetRegisterInfo;
   template<class T> class OwningPtr;
 
@@ -125,7 +125,7 @@ namespace llvm {
     /// Build a PBQP instance to represent the register allocation problem for
     /// the given MachineFunction.
     virtual PBQPRAProblem *build(MachineFunction *mf, const LiveIntervals *lis,
-                                 const MachineLoopInfo *loopInfo,
+                                 const MachineBlockFrequencyInfo *mbfi,
                                  const RegSet &vregs);
   private:
 
@@ -144,7 +144,7 @@ namespace llvm {
     /// Build a PBQP instance to represent the register allocation problem for
     /// the given MachineFunction.
     virtual PBQPRAProblem *build(MachineFunction *mf, const LiveIntervals *lis,
-                                 const MachineLoopInfo *loopInfo,
+                                 const MachineBlockFrequencyInfo *mbfi,
                                  const RegSet &vregs);   
 
   private: