Clear spilled list at once. Remove unused vector.

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

diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp
index 0e52f46c6f2c19056539144e29ffe4f518de5f15..4a55df189369f51c65db08e06cb0d575f28ea7b2 100644 (file)
--- a/lib/CodeGen/RegAllocLinearScan.cpp
+++ b/lib/CodeGen/RegAllocLinearScan.cpp
@@ -38,6 +38,9 @@ namespace {
     Statistic<double> efficiency
     ("regalloc", "Ratio of intervals processed over total intervals");
 
+    static unsigned numIterations = 0;
+    static unsigned numIntervals = 0;
+
     class RA : public MachineFunctionPass {
     private:
         MachineFunction* mf_;
@@ -120,23 +123,6 @@ namespace {
                 std::cerr << mri_->getName(reg) << '\n';
             }
         }
-
-//         void verifyAssignment() const {
-//             for (Virt2PhysMap::const_iterator i = v2pMap_.begin(),
-//                      e = v2pMap_.end(); i != e; ++i)
-//                 for (Virt2PhysMap::const_iterator i2 = next(i); i2 != e; ++i2)
-//                     if (MRegisterInfo::isVirtualRegister(i->second) &&
-//                         (i->second == i2->second ||
-//                          mri_->areAliases(i->second, i2->second))) {
-//                         const Interval
-//                             &in = li_->getInterval(i->second),
-//                             &in2 = li_->getInterval(i2->second);
-//                         if (in.overlaps(in2)) {
-//                             std::cerr << in << " overlaps " << in2 << '\n';
-//                             assert(0);
-//                         }
-//                     }
-//         }
     };
 }
 
@@ -183,7 +169,7 @@ void RA::linearScan()
         // pick the interval with the earliest start point
         IntervalPtrs::value_type cur = unhandled_.front();
         unhandled_.pop_front();
-        ++efficiency;
+        ++numIterations;
         DEBUG(std::cerr << "\n*** CURRENT ***: " << *cur << '\n');
 
         processActiveIntervals(cur);
@@ -206,7 +192,8 @@ void RA::linearScan()
         DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
         // DEBUG(verifyAssignment());
     }
-    efficiency /= li_->getIntervals().size();
+    numIntervals += li_->getIntervals().size();
+    efficiency = double(numIterations) / double(numIntervals);
 
     // expire any remaining active intervals
     for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
@@ -382,18 +369,42 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur)
         int slot = vrm_->assignVirt2StackSlot(cur->reg);
         std::vector<LiveInterval*> added =
             li_->addIntervalsForSpills(*cur, *vrm_, slot);
-
-        // merge added with unhandled
+        if (added.empty())
+          return;  // Early exit if all spills were folded.
+#ifndef NDEBUG
+        int OldStart = -1;
+#endif
+
+        // Merge added with unhandled.  Note that we know that 
+        // addIntervalsForSpills returns intervals sorted by their starting
+        // point.
         std::vector<LiveInterval*>::iterator addedIt = added.begin();
         std::vector<LiveInterval*>::iterator addedItEnd = added.end();
-        for (IntervalPtrs::iterator i = unhandled_.begin(), e = unhandled_.end();
+        for (IntervalPtrs::iterator i = unhandled_.begin(), e =unhandled_.end();
              i != e && addedIt != addedItEnd; ++i) {
-            if ((*i)->start() > (*addedIt)->start())
+            while (addedIt != addedItEnd &&
+                   (*i)->start() > (*addedIt)->start()) {
+#ifndef NDEBUG
+                // This code only works if addIntervalsForSpills retursn a
+                // sorted interval list.  Assert this is the case now.
+                assert(OldStart <= (int)(*addedIt)->start() && 
+                   "addIntervalsForSpills didn't return sorted interval list!");
+                OldStart = (*addedIt)->start();
+#endif
                 i = unhandled_.insert(i, *(addedIt++));
+            }
         }
-        while (addedIt != addedItEnd)
-            unhandled_.push_back(*(addedIt++));
 
+        while (addedIt != addedItEnd) {
+#ifndef NDEBUG
+                // This code only works if addIntervalsForSpills retursn a
+                // sorted interval list.  Assert this is the case now.
+                assert(OldStart <= (int)(*addedIt)->start() && 
+                   "addIntervalsForSpills didn't return sorted interval list!");
+                OldStart = (*addedIt)->start();
+#endif
+            unhandled_.push_back(*(addedIt++));
+        }
         return;
     }