Change weight into a float so that we can take into account the

nesting level when computing it. Right now the allocator uses:

    w = sum_over_defs_uses( 10 ^ nesting level );


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

3 files changed, 31 insertions, 15 deletions

diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index 2a0ab9e..05b4f5a 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -18,6 +18,7 @@
 #define DEBUG_TYPE "liveintervals"
 #include "llvm/CodeGen/LiveIntervals.h"
 #include "llvm/Function.h"
+#include "llvm/Analysis/LoopInfo.h"
 #include "llvm/CodeGen/LiveVariables.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
@@ -32,8 +33,9 @@
 #include "Support/Debug.h"
 #include "Support/DepthFirstIterator.h"
 #include "Support/Statistic.h"
-#include <limits>
+#include <cmath>
 #include <iostream>
+#include <limits>
 
 using namespace llvm;
 
@@ -51,6 +53,7 @@ void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const
     AU.addPreservedID(PHIEliminationID);
     AU.addRequiredID(PHIEliminationID);
     AU.addRequiredID(TwoAddressInstructionPassID);
+    AU.addRequired<LoopInfo>();
     MachineFunctionPass::getAnalysisUsage(AU);
 }
 
@@ -251,12 +254,17 @@ void LiveIntervals::computeIntervals()
 {
     DEBUG(std::cerr << "computing live intervals:\n");
 
+    const LoopInfo& loopInfo = getAnalysis<LoopInfo>();
+
     for (MbbIndex2MbbMap::iterator
              it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end();
          it != itEnd; ++it) {
         MachineBasicBlock* mbb = it->second;
         DEBUG(std::cerr << "machine basic block: "
               << mbb->getBasicBlock()->getName() << "\n");
+
+        unsigned loopDepth = loopInfo.getLoopDepth(mbb->getBasicBlock());
+
         for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end();
              mi != miEnd; ++mi) {
             MachineInstr* instr = *mi;
@@ -292,7 +300,7 @@ void LiveIntervals::computeIntervals()
                 Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg);
                 if (r2iit != r2iMap_.end() &&
                     reg >= MRegisterInfo::FirstVirtualRegister)
-                    ++intervals_[r2iit->second].weight;
+                    intervals_[r2iit->second].weight += pow(10.0F, loopDepth);
             }
         }
     }
@@ -305,7 +313,7 @@ void LiveIntervals::computeIntervals()
 LiveIntervals::Interval::Interval(unsigned r)
     : reg(r),
       weight((r < MRegisterInfo::FirstVirtualRegister ?
-              std::numeric_limits<unsigned>::max() : 0))
+              std::numeric_limits<float>::max() : 0.0F))
 {
 
 }
diff --git a/lib/CodeGen/LiveIntervalAnalysis.h b/lib/CodeGen/LiveIntervalAnalysis.h
index 7ef2e78..cecfbba 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.h
+++ b/lib/CodeGen/LiveIntervalAnalysis.h
@@ -38,8 +38,9 @@ namespace llvm {
             typedef std::pair<unsigned, unsigned> Range;
             typedef std::vector<Range> Ranges;
             unsigned reg;   // the register of this interval
-            unsigned weight; // weight of this interval (number of uses)
-            Ranges ranges; // the ranges this register is valid
+            float weight;   // weight of this interval (number of uses
+                            // * 10^loopDepth)
+            Ranges ranges;  // the ranges this register is valid
 
             Interval(unsigned r);
 
diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp
index 561448b..9538e04 100644
--- a/lib/CodeGen/RegAllocLinearScan.cpp
+++ b/lib/CodeGen/RegAllocLinearScan.cpp
@@ -524,11 +524,12 @@ void RA::processInactiveIntervals(Intervals::const_iterator cur)
 }
 
 namespace {
-    void updateWeight(unsigned rw[], unsigned reg, unsigned w)
+    template <typename T>
+    void updateWeight(T rw[], int reg, T w)
     {
-        if (rw[reg] == std::numeric_limits<unsigned>::max() ||
-            w == std::numeric_limits<unsigned>::max())
-            rw[reg] = std::numeric_limits<unsigned>::max();
+        if (rw[reg] == std::numeric_limits<T>::max() ||
+            w == std::numeric_limits<T>::max())
+            rw[reg] = std::numeric_limits<T>::max();
         else
             rw[reg] += w;
     }
@@ -543,8 +544,9 @@ void RA::assignStackSlotAtInterval(Intervals::const_iterator cur)
            "a register to spill");
 
     // set all weights to zero
-    unsigned regWeight[MRegisterInfo::FirstVirtualRegister];
-    memset(regWeight, 0, sizeof(regWeight));
+    float regWeight[MRegisterInfo::FirstVirtualRegister];
+    for (unsigned i = 0; i < MRegisterInfo::FirstVirtualRegister; ++i)
+        regWeight[i] = 0.0F;
 
     for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
 //         if (!cur->overlaps(**i))
@@ -573,7 +575,7 @@ void RA::assignStackSlotAtInterval(Intervals::const_iterator cur)
             updateWeight(regWeight, *as, (*i)->weight);
     }
 
-    unsigned minWeight = std::numeric_limits<unsigned>::max();
+    float minWeight = std::numeric_limits<float>::max();
     unsigned minReg = 0;
     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
     for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
@@ -585,10 +587,9 @@ void RA::assignStackSlotAtInterval(Intervals::const_iterator cur)
         }
     }
 
-    DEBUG(std::cerr << "\t\t\t\tspill candidate: "
-          << mri_->getName(minReg) << '\n');
-
     if (cur->weight < minWeight) {
+        DEBUG(std::cerr << "\t\t\t\tspilling : " << mri_->getName(minReg)
+              << ", weight: " << cur->weight << '\n');
         assignVirt2StackSlot(cur->reg);
     }
     else {
@@ -602,6 +603,9 @@ void RA::assignStackSlotAtInterval(Intervals::const_iterator cur)
             unsigned reg = (*i)->reg;
             if (reg >= MRegisterInfo::FirstVirtualRegister &&
                 toSpill.find(v2pMap_[reg]) != toSpill.end()) {
+                DEBUG(std::cerr << "\t\t\t\tspilling : "
+                      << mri_->getName(minReg) << ", weight: "
+                      << (*i)->weight << '\n');
                 assignVirt2StackSlot(reg);
                 i = active_.erase(i);
             }
@@ -614,6 +618,9 @@ void RA::assignStackSlotAtInterval(Intervals::const_iterator cur)
             unsigned reg = (*i)->reg;
             if (reg >= MRegisterInfo::FirstVirtualRegister &&
                 toSpill.find(v2pMap_[reg]) != toSpill.end()) {
+                DEBUG(std::cerr << "\t\t\t\tspilling : "
+                      << mri_->getName(minReg) << ", weight: "
+                      << (*i)->weight << '\n');
                 assignVirt2StackSlot(reg);
                 i = inactive_.erase(i);
             }