A value defined by an implicit_def can be liven to a use BB. This is unfortunate...

[oota-llvm.git] / lib / CodeGen / RegAllocLinearScan.cpp

diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp
index c5ce455b0ae5f636642fed1b80ca4747706d4a4b..ab4068e6e4c30ef44c2bd1a68f60b0236fa8e44e 100644 (file)
--- a/lib/CodeGen/RegAllocLinearScan.cpp
+++ b/lib/CodeGen/RegAllocLinearScan.cpp
@@ -14,6 +14,7 @@
 #define DEBUG_TYPE "regalloc"
 #include "VirtRegMap.h"
 #include "VirtRegRewriter.h"
+#include "Spiller.h"
 #include "llvm/Function.h"
 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "llvm/CodeGen/LiveStackAnalysis.h"
@@ -39,6 +40,7 @@
 #include <queue>
 #include <memory>
 #include <cmath>
+
 using namespace llvm;
 
 STATISTIC(NumIters     , "Number of iterations performed");
@@ -56,6 +58,11 @@ PreSplitIntervals("pre-alloc-split",
                   cl::desc("Pre-register allocation live interval splitting"),
                   cl::init(false), cl::Hidden);
 
+static cl::opt<bool>
+NewSpillFramework("new-spill-framework",
+                  cl::desc("New spilling framework"),
+                  cl::init(false), cl::Hidden);
+
 static RegisterRegAlloc
 linearscanRegAlloc("linearscan", "linear scan register allocator",
                    createLinearScanRegisterAllocator);
@@ -127,6 +134,8 @@ namespace {
 
     std::auto_ptr<VirtRegRewriter> rewriter_;
 
+    std::auto_ptr<Spiller> spiller_;
+
   public:
     virtual const char* getPassName() const {
       return "Linear Scan Register Allocator";
@@ -420,7 +429,11 @@ bool RALinScan::runOnMachineFunction(MachineFunction &fn) {
 
   vrm_ = &getAnalysis<VirtRegMap>();
   if (!rewriter_.get()) rewriter_.reset(createVirtRegRewriter());
-
+  
+  if (NewSpillFramework) {
+    spiller_.reset(createSpiller(mf_, li_, ls_, vrm_));
+  }
+  
   initIntervalSets();
 
   linearScan();
@@ -439,6 +452,7 @@ bool RALinScan::runOnMachineFunction(MachineFunction &fn) {
   NextReloadMap.clear();
   DowngradedRegs.clear();
   DowngradeMap.clear();
+  spiller_.reset(0);
 
   return true;
 }
@@ -528,6 +542,24 @@ void RALinScan::linearScan()
     // Ignore splited live intervals.
     if (!isPhys && vrm_->getPreSplitReg(cur.reg))
       continue;
+
+    // A register defined by an implicit_def can be liveout the def BB and livein
+    // to a use BB. Add it to the livein set of the use BB's.
+    if (!isPhys && cur.empty()) {
+      if (MachineInstr *DefMI = mri_->getVRegDef(cur.reg)) {
+        assert(DefMI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF);
+        MachineBasicBlock *DefMBB = DefMI->getParent();
+        SmallPtrSet<MachineBasicBlock*, 4> Seen;
+        Seen.insert(DefMBB);
+        for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(cur.reg),
+               re = mri_->reg_end(); ri != re; ++ri) {
+          MachineInstr *UseMI = &*ri;
+          MachineBasicBlock *UseMBB = UseMI->getParent();
+          if (Seen.insert(UseMBB))
+            UseMBB->addLiveIn(Reg);
+        }
+      }
+    }
     for (LiveInterval::Ranges::const_iterator I = cur.begin(), E = cur.end();
          I != E; ++I) {
       const LiveRange &LR = *I;
@@ -1108,8 +1140,14 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur)
   if (cur->weight != HUGE_VALF && cur->weight <= minWeight) {
     DOUT << "\t\t\tspilling(c): " << *cur << '\n';
     SmallVector<LiveInterval*, 8> spillIs;
-    std::vector<LiveInterval*> added =
-      li_->addIntervalsForSpills(*cur, spillIs, loopInfo, *vrm_);
+    std::vector<LiveInterval*> added;
+    
+    if (!NewSpillFramework) {
+      added = li_->addIntervalsForSpills(*cur, spillIs, loopInfo, *vrm_);
+    } else {
+      added = spiller_->spill(cur); 
+    }
+
     std::sort(added.begin(), added.end(), LISorter());
     addStackInterval(cur, ls_, li_, mri_, *vrm_);
     if (added.empty())
@@ -1170,7 +1208,8 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur)
 
   // The earliest start of a Spilled interval indicates up to where
   // in handled we need to roll back
-  unsigned earliestStart = cur->beginNumber();
+  
+  LiveInterval *earliestStartInterval = cur;
 
   // Spill live intervals of virtual regs mapped to the physical register we
   // want to clear (and its aliases).  We only spill those that overlap with the
@@ -1179,17 +1218,31 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur)
   // mark our rollback point.
   std::vector<LiveInterval*> added;
   while (!spillIs.empty()) {
+    bool epicFail = false;
     LiveInterval *sli = spillIs.back();
     spillIs.pop_back();
     DOUT << "\t\t\tspilling(a): " << *sli << '\n';
-    earliestStart = std::min(earliestStart, sli->beginNumber());
-    std::vector<LiveInterval*> newIs =
-      li_->addIntervalsForSpills(*sli, spillIs, loopInfo, *vrm_);
+    earliestStartInterval =
+      (earliestStartInterval->beginNumber() < sli->beginNumber()) ?
+         earliestStartInterval : sli;
+       
+    std::vector<LiveInterval*> newIs;
+    if (!NewSpillFramework) {
+      newIs = li_->addIntervalsForSpills(*sli, spillIs, loopInfo, *vrm_);
+    } else {
+      newIs = spiller_->spill(sli);
+    }
     addStackInterval(sli, ls_, li_, mri_, *vrm_);
     std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
     spilled.insert(sli->reg);
+
+    if (epicFail) {
+      //abort();
+    }
   }
 
+  unsigned earliestStart = earliestStartInterval->beginNumber();
+
   DOUT << "\t\trolling back to: " << earliestStart << '\n';
 
   // Scan handled in reverse order up to the earliest start of a