Now that we use an ilist of machine instructions, iterators are more robust

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

diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp
index 42029dc6b0af062eb0fbe276a1e6b65758b95a17..ed7da0f8c8fef56c3e43544d57946171434b0cf4 100644 (file)
--- a/lib/CodeGen/RegAllocLinearScan.cpp
+++ b/lib/CodeGen/RegAllocLinearScan.cpp
@@ -25,6 +25,7 @@
 #include "PhysRegTracker.h"
 #include "VirtRegMap.h"
 #include <algorithm>
+#include <cmath>
 #include <iostream>
 
 using namespace llvm;
@@ -41,6 +42,7 @@ namespace {
 
         std::auto_ptr<PhysRegTracker> prt_;
         std::auto_ptr<VirtRegMap> vrm_;
+        std::auto_ptr<Spiller> spiller_;
 
         typedef std::vector<float> SpillWeights;
         SpillWeights spillWeights_;
@@ -134,9 +136,9 @@ namespace {
 void RA::releaseMemory()
 {
     unhandled_.clear();
+    fixed_.clear();
     active_.clear();
     inactive_.clear();
-    fixed_.clear();
     handled_.clear();
 }
 
@@ -147,12 +149,13 @@ bool RA::runOnMachineFunction(MachineFunction &fn) {
     li_ = &getAnalysis<LiveIntervals>();
     if (!prt_.get()) prt_.reset(new PhysRegTracker(*mri_));
     vrm_.reset(new VirtRegMap(*mf_));
+    if (!spiller_.get()) spiller_.reset(createSpiller());
 
     initIntervalSets(li_->getIntervals());
 
     linearScan();
 
-    eliminateVirtRegs(*mf_, *vrm_);
+    spiller_->runOnMachineFunction(*mf_, *vrm_);
 
     return true;
 }
@@ -169,25 +172,10 @@ void RA::linearScan()
     DEBUG(printIntervals("active", active_.begin(), active_.end()));
     DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
 
-    while (!unhandled_.empty() || !fixed_.empty()) {
+    while (!unhandled_.empty()) {
         // pick the interval with the earliest start point
-        IntervalPtrs::value_type cur;
-        if (fixed_.empty()) {
-            cur = unhandled_.front();
-            unhandled_.pop_front();
-        }
-        else if (unhandled_.empty()) {
-            cur = fixed_.front();
-            fixed_.pop_front();
-        }
-        else if (unhandled_.front()->start() < fixed_.front()->start()) {
-            cur = unhandled_.front();
-            unhandled_.pop_front();
-        }
-        else {
-            cur = fixed_.front();
-            fixed_.pop_front();
-        }
+        IntervalPtrs::value_type cur = unhandled_.front();
+        unhandled_.pop_front();
 
         DEBUG(std::cerr << "\n*** CURRENT ***: " << *cur << '\n');
 
@@ -232,10 +220,9 @@ void RA::initIntervalSets(LiveIntervals::Intervals& li)
 
     for (LiveIntervals::Intervals::iterator i = li.begin(), e = li.end();
          i != e; ++i) {
+        unhandled_.push_back(&*i);
         if (MRegisterInfo::isPhysicalRegister(i->reg))
             fixed_.push_back(&*i);
-        else
-            unhandled_.push_back(&*i);
     }
 }
 
@@ -365,7 +352,7 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur)
 
     DEBUG(std::cerr << "\tassigning stack slot at interval "<< *cur << ":\n");
 
-    float minWeight = std::numeric_limits<float>::infinity();
+    float minWeight = HUGE_VAL;
     unsigned minReg = 0;
     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
     for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
@@ -385,7 +372,7 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur)
     if (cur->weight <= minWeight) {
         DEBUG(std::cerr << "\t\t\tspilling(c): " << *cur << '\n';);
         int slot = vrm_->assignVirt2StackSlot(cur->reg);
-        li_->updateSpilledInterval(*cur, slot);
+        li_->updateSpilledInterval(*cur, *vrm_, slot);
 
         // if we didn't eliminate the interval find where to add it
         // back to unhandled. We need to scan since unhandled are
@@ -424,7 +411,7 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur)
             DEBUG(std::cerr << "\t\t\tspilling(a): " << **i << '\n');
             earliestStart = std::min(earliestStart, (*i)->start());
             int slot = vrm_->assignVirt2StackSlot((*i)->reg);
-            li_->updateSpilledInterval(**i, slot);
+            li_->updateSpilledInterval(**i, *vrm_, slot);
         }
     }
     for (IntervalPtrs::iterator i = inactive_.begin();
@@ -436,13 +423,13 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur)
             DEBUG(std::cerr << "\t\t\tspilling(i): " << **i << '\n');
             earliestStart = std::min(earliestStart, (*i)->start());
             int slot = vrm_->assignVirt2StackSlot((*i)->reg);
-            li_->updateSpilledInterval(**i, slot);
+            li_->updateSpilledInterval(**i, *vrm_, slot);
         }
     }
 
     DEBUG(std::cerr << "\t\trolling back to: " << earliestStart << '\n');
     // scan handled in reverse order and undo each one, restoring the
-    // state of unhandled and fixed
+    // state of unhandled
     while (!handled_.empty()) {
         IntervalPtrs::value_type i = handled_.back();
         // if this interval starts before t we are done
@@ -454,12 +441,12 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur)
         if ((it = find(active_.begin(), active_.end(), i)) != active_.end()) {
             active_.erase(it);
             if (MRegisterInfo::isPhysicalRegister(i->reg)) {
-                fixed_.push_front(i);
                 prt_->delRegUse(i->reg);
+                unhandled_.push_front(i);
             }
             else {
                 prt_->delRegUse(vrm_->getPhys(i->reg));
-                vrm_->clearVirtReg(i->reg);
+                vrm_->clearVirt(i->reg);
                 if (i->spilled()) {
                     if (!i->empty()) {
                         IntervalPtrs::iterator it = unhandled_.begin();
@@ -477,9 +464,9 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur)
         else if ((it = find(inactive_.begin(), inactive_.end(), i)) != inactive_.end()) {
             inactive_.erase(it);
             if (MRegisterInfo::isPhysicalRegister(i->reg))
-                fixed_.push_front(i);
+                unhandled_.push_front(i);
             else {
-                vrm_->clearVirtReg(i->reg);
+                vrm_->clearVirt(i->reg);
                 if (i->spilled()) {
                     if (!i->empty()) {
                         IntervalPtrs::iterator it = unhandled_.begin();
@@ -494,12 +481,9 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur)
             }
         }
         else {
-            if (MRegisterInfo::isPhysicalRegister(i->reg))
-                fixed_.push_front(i);
-            else {
-                vrm_->clearVirtReg(i->reg);
-                unhandled_.push_front(i);
-            }
+            if (MRegisterInfo::isVirtualRegister(i->reg))
+                vrm_->clearVirt(i->reg);
+            unhandled_.push_front(i);
         }
     }