Update to in-place spilling framework. Includes live interval scaling and trivial rewriter.

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

1 files changed, 132 insertions, 9 deletions

diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp
index ac6ab32..ee118de 100644
--- a/lib/CodeGen/RegAllocLinearScan.cpp
+++ b/lib/CodeGen/RegAllocLinearScan.cpp
@@ -40,6 +40,8 @@
 #include <queue>
 #include <memory>
 #include <cmath>
+#include <iostream>
+
 using namespace llvm;
 
 STATISTIC(NumIters     , "Number of iterations performed");
@@ -310,6 +312,93 @@ namespace {
 static RegisterPass<RALinScan>
 X("linearscan-regalloc", "Linear Scan Register Allocator");
 
+bool validateRegAlloc(MachineFunction *mf, LiveIntervals *lis,
+                      VirtRegMap *vrm) {
+
+  MachineRegisterInfo *mri = &mf->getRegInfo();
+  const TargetRegisterInfo *tri = mf->getTarget().getRegisterInfo();
+  bool allocationValid = true;
+
+
+  for (LiveIntervals::iterator itr = lis->begin(), end = lis->end();
+       itr != end; ++itr) {
+
+    LiveInterval *li = itr->second;
+
+    if (TargetRegisterInfo::isPhysicalRegister(li->reg)) {
+      continue;
+    }
+
+    if (vrm->hasPhys(li->reg)) {
+      const TargetRegisterClass *trc = mri->getRegClass(li->reg);
+      
+      if (lis->hasInterval(vrm->getPhys(li->reg))) {
+        if (li->overlaps(lis->getInterval(vrm->getPhys(li->reg)))) {
+          std::cerr << "vreg " << li->reg << " overlaps its assigned preg "
+                    << vrm->getPhys(li->reg) << "(" << tri->getName(vrm->getPhys(li->reg)) << ")\n";
+        }
+      }
+
+      TargetRegisterClass::iterator fReg =
+        std::find(trc->allocation_order_begin(*mf), trc->allocation_order_end(*mf),
+                  vrm->getPhys(li->reg));
+
+      if (fReg == trc->allocation_order_end(*mf)) {
+        std::cerr << "preg " << vrm->getPhys(li->reg) 
+                  << "(" << tri->getName(vrm->getPhys(li->reg)) << ") is not in the allocation set for vreg "
+                  << li->reg << "\n";
+        allocationValid &= false;
+      }
+    }
+    else {
+      std::cerr << "No preg for vreg " << li->reg << "\n";
+      // What about conflicting loads/stores?
+      continue;
+    }
+
+    for (LiveIntervals::iterator itr2 = next(itr); itr2 != end; ++itr2) {
+
+      LiveInterval *li2 = itr2->second;
+
+      if (li2->empty())
+        continue;
+
+      if (TargetRegisterInfo::isPhysicalRegister(li2->reg)) {
+        if (li->overlaps(*li2)) {
+          if (vrm->getPhys(li->reg) == li2->reg ||
+              tri->areAliases(vrm->getPhys(li->reg), li2->reg)) {
+            std::cerr << "vreg " << li->reg << " overlaps preg "
+                      << li2->reg << "(" << tri->getName(li2->reg) << ") which aliases "
+                      << vrm->getPhys(li->reg) << "(" << tri->getName(vrm->getPhys(li->reg)) << ")\n";
+            allocationValid &= false;
+          }
+        }
+      }
+      else {
+
+        if (!vrm->hasPhys(li2->reg)) {
+          continue;
+        }
+
+        if (li->overlaps(*li2)) {
+          if (vrm->getPhys(li->reg) == vrm->getPhys(li2->reg) ||
+              tri->areAliases(vrm->getPhys(li->reg), vrm->getPhys(li2->reg))) {
+            std::cerr << "vreg " << li->reg << " (preg " << vrm->getPhys(li->reg)
+                      << ") overlaps vreg " << li2->reg << " (preg " << vrm->getPhys(li2->reg)
+                      << ") and " << vrm->getPhys(li->reg) << " aliases " << vrm->getPhys(li2->reg) << "\n";
+            allocationValid &= false;
+          } 
+        }
+      }
+    } 
+
+  } 
+
+  return allocationValid;
+
+}
+
+
 void RALinScan::ComputeRelatedRegClasses() {
   // First pass, add all reg classes to the union, and determine at least one
   // reg class that each register is in.
@@ -430,16 +519,17 @@ bool RALinScan::runOnMachineFunction(MachineFunction &fn) {
   if (!rewriter_.get()) rewriter_.reset(createVirtRegRewriter());
   
   if (NewSpillFramework) {
-    spiller_.reset(createSpiller(mf_, li_, vrm_));
-  }
-  else {
-    spiller_.reset(0);
+    spiller_.reset(createSpiller(mf_, li_, ls_, vrm_));
   }
-
+  
   initIntervalSets();
 
   linearScan();
 
+  if (NewSpillFramework) {
+    bool allocValid = validateRegAlloc(mf_, li_, vrm_);
+  }
+
   // Rewrite spill code and update the PhysRegsUsed set.
   rewriter_->runOnMachineFunction(*mf_, *vrm_, li_);
 
@@ -454,6 +544,7 @@ bool RALinScan::runOnMachineFunction(MachineFunction &fn) {
   NextReloadMap.clear();
   DowngradedRegs.clear();
   DowngradeMap.clear();
+  spiller_.reset(0);
 
   return true;
 }
@@ -1127,8 +1218,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur)
     
     if (!NewSpillFramework) {
       added = li_->addIntervalsForSpills(*cur, spillIs, loopInfo, *vrm_);
-    }
-    else {
+    } else {
       added = spiller_->spill(cur); 
     }
 
@@ -1192,7 +1282,9 @@ 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
@@ -1201,17 +1293,48 @@ 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;
+    
+    if (earliestStartInterval->beginNumber()!=earliestStart) {
+      epicFail |= true;
+      std::cerr << "What the 1 - "
+      		<< "earliestStart = " << earliestStart
+      		<< "earliestStartInterval = " << earliestStartInterval->beginNumber()
+      		<< "\n";
+    }
+   
+    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 (earliestStartInterval->beginNumber()!=earliestStart) {
+      epicFail |= true;
+      std::cerr << "What the 2 - "
+      		<< "earliestStart = " << earliestStart
+      		<< "earliestStartInterval = " << earliestStartInterval->beginNumber()
+      		<< "\n";
+    }
+
+    if (epicFail) {
+      //abort();
+    }
   }
 
+  earliestStart = earliestStartInterval->beginNumber();
+
   DOUT << "\t\trolling back to: " << earliestStart << '\n';
 
   // Scan handled in reverse order up to the earliest start of a