1 files changed, 172 insertions, 128 deletions

diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp
index 83d90936c2..8aa06bd789 100644
--- a/lib/CodeGen/RegAllocLinearScan.cpp
+++ b/lib/CodeGen/RegAllocLinearScan.cpp
@@ -29,6 +29,7 @@
 #include <cmath>
 #include <set>
 #include <queue>
+
 using namespace llvm;
 
 namespace {
@@ -39,16 +40,33 @@ namespace {
   static unsigned numIterations = 0;
   static unsigned numIntervals = 0;
 
-  class RA : public MachineFunctionPass {
+  struct RA : public MachineFunctionPass {
+    typedef std::pair<LiveInterval*, LiveInterval::iterator> IntervalPtr;
+    typedef std::vector<IntervalPtr> IntervalPtrs;
+  private:
     MachineFunction* mf_;
     const TargetMachine* tm_;
     const MRegisterInfo* mri_;
     LiveIntervals* li_;
-    typedef LiveInterval* IntervalPtr;
-    typedef std::vector<IntervalPtr> IntervalPtrs;
-    IntervalPtrs handled_, fixed_, active_, inactive_;
+
+    /// handled_ - Intervals are added to the handled_ set in the order of their
+    /// start value.  This is uses for backtracking.
+    std::vector<LiveInterval*> handled_;
+
+    /// fixed_ - Intervals that correspond to machine registers.
+    ///
+    IntervalPtrs fixed_;
+
+    /// active_ - Intervals that are currently being processed, and which have a
+    /// live range active for the current point.
+    IntervalPtrs active_;
+
+    /// inactive_ - Intervals that are currently being processed, but which have
+    /// a hold at the current point.
+    IntervalPtrs inactive_;
+
     typedef std::priority_queue<LiveInterval*,
-                                IntervalPtrs,
+                                std::vector<LiveInterval*>,
                                 greater_ptr<LiveInterval> > IntervalHeap;
     IntervalHeap unhandled_;
     std::auto_ptr<PhysRegTracker> prt_;
@@ -71,26 +89,24 @@ namespace {
     /// runOnMachineFunction - register allocate the whole function
     bool runOnMachineFunction(MachineFunction&);
 
-    void releaseMemory();
-
   private:
     /// linearScan - the linear scan algorithm
     void linearScan();
 
-    /// initIntervalSets - initializa the four interval sets:
-    /// unhandled, fixed, active and inactive
+    /// initIntervalSets - initialize the interval sets.
+    ///
     void initIntervalSets();
 
-    /// processActiveIntervals - expire old intervals and move
-    /// non-overlapping ones to the incative list
-    void processActiveIntervals(LiveInterval* cur);
+    /// processActiveIntervals - expire old intervals and move non-overlapping
+    /// ones to the inactive list.
+    void processActiveIntervals(unsigned CurPoint);
 
-    /// processInactiveIntervals - expire old intervals and move
-    /// overlapping ones to the active list
-    void processInactiveIntervals(LiveInterval* cur);
+    /// processInactiveIntervals - expire old intervals and move overlapping
+    /// ones to the active list.
+    void processInactiveIntervals(unsigned CurPoint);
 
     /// updateSpillWeights - updates the spill weights of the
-    /// specifed physical register and its weight
+    /// specifed physical register and its weight.
     void updateSpillWeights(unsigned reg, SpillWeights::value_type weight);
 
     /// assignRegOrStackSlotAtInterval - assign a register if one
@@ -101,9 +117,8 @@ namespace {
     /// register handling helpers
     ///
 
-    /// getFreePhysReg - return a free physical register for this
-    /// virtual register interval if we have one, otherwise return
-    /// 0
+    /// getFreePhysReg - return a free physical register for this virtual
+    /// register interval if we have one, otherwise return 0.
     unsigned getFreePhysReg(LiveInterval* cur);
 
     /// assignVirt2StackSlot - assigns this virtual register to a
@@ -114,8 +129,8 @@ namespace {
     void printIntervals(const char* const str, ItTy i, ItTy e) const {
       if (str) std::cerr << str << " intervals:\n";
       for (; i != e; ++i) {
-        std::cerr << "\t" << **i << " -> ";
-        unsigned reg = (*i)->reg;
+        std::cerr << "\t" << *i->first << " -> ";
+        unsigned reg = i->first->reg;
         if (MRegisterInfo::isVirtualRegister(reg)) {
           reg = vrm_->getPhys(reg);
         }
@@ -125,15 +140,6 @@ namespace {
   };
 }
 
-void RA::releaseMemory()
-{
-  while (!unhandled_.empty()) unhandled_.pop();
-  fixed_.clear();
-  active_.clear();
-  inactive_.clear();
-  handled_.clear();
-}
-
 bool RA::runOnMachineFunction(MachineFunction &fn) {
   mf_ = &fn;
   tm_ = &fn.getTarget();
@@ -150,6 +156,14 @@ bool RA::runOnMachineFunction(MachineFunction &fn) {
   spiller_->runOnMachineFunction(*mf_, *vrm_);
 
   vrm_.reset();  // Free the VirtRegMap
+
+
+  while (!unhandled_.empty()) unhandled_.pop();
+  fixed_.clear();
+  active_.clear();
+  inactive_.clear();
+  handled_.clear();
+
   return true;
 }
 
@@ -172,19 +186,18 @@ void RA::linearScan()
     ++numIterations;
     DEBUG(std::cerr << "\n*** CURRENT ***: " << *cur << '\n');
 
-    processActiveIntervals(cur);
-    processInactiveIntervals(cur);
+    processActiveIntervals(cur->beginNumber());
+    processInactiveIntervals(cur->beginNumber());
 
     // if this register is fixed we are done
     if (MRegisterInfo::isPhysicalRegister(cur->reg)) {
       prt_->addRegUse(cur->reg);
-      active_.push_back(cur);
+      active_.push_back(std::make_pair(cur, cur->begin()));
       handled_.push_back(cur);
-    }
-    // otherwise we are allocating a virtual register. try to find
-    // a free physical register or spill an interval in order to
-    // assign it one (we could spill the current though).
-    else {
+    } else {
+      // otherwise we are allocating a virtual register. try to find a free
+      // physical register or spill an interval in order to assign it one (we
+      // could spill the current though).
       assignRegOrStackSlotAtInterval(cur);
     }
 
@@ -197,8 +210,8 @@ void RA::linearScan()
   // expire any remaining active intervals
   for (IntervalPtrs::reverse_iterator
          i = active_.rbegin(); i != active_.rend(); ) {
-    unsigned reg = (*i)->reg;
-    DEBUG(std::cerr << "\tinterval " << **i << " expired\n");
+    unsigned reg = i->first->reg;
+    DEBUG(std::cerr << "\tinterval " << *i->first << " expired\n");
     if (MRegisterInfo::isVirtualRegister(reg))
       reg = vrm_->getPhys(reg);
     prt_->delRegUse(reg);
@@ -208,13 +221,15 @@ void RA::linearScan()
   // expire any remaining inactive intervals
   for (IntervalPtrs::reverse_iterator
          i = inactive_.rbegin(); i != inactive_.rend(); ) {
-    DEBUG(std::cerr << "\tinterval " << **i << " expired\n");
+    DEBUG(std::cerr << "\tinterval " << *i->first << " expired\n");
     i = IntervalPtrs::reverse_iterator(inactive_.erase(i.base()-1));
   }
 
   DEBUG(std::cerr << *vrm_);
 }
 
+/// initIntervalSets - initialize the interval sets.
+///
 void RA::initIntervalSets()
 {
   assert(unhandled_.empty() && fixed_.empty() &&
@@ -224,79 +239,95 @@ void RA::initIntervalSets()
   for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i){
     unhandled_.push(&i->second);
     if (MRegisterInfo::isPhysicalRegister(i->second.reg))
-      fixed_.push_back(&i->second);
+      fixed_.push_back(std::make_pair(&i->second, i->second.begin()));
   }
 }
 
-void RA::processActiveIntervals(IntervalPtrs::value_type cur)
+/// processActiveIntervals - expire old intervals and move non-overlapping ones
+/// to the inactive list.
+void RA::processActiveIntervals(unsigned CurPoint)
 {
   DEBUG(std::cerr << "\tprocessing active intervals:\n");
 
-  IntervalPtrs::iterator ii = active_.begin(), ie = active_.end();
-  while (ii != ie) {
-    LiveInterval* i = *ii;
-    unsigned reg = i->reg;
+  for (unsigned i = 0, e = active_.size(); i != e; ++i) {
+    LiveInterval *Interval = active_[i].first;
+    LiveInterval::iterator IntervalPos = active_[i].second;
+    unsigned reg = Interval->reg;
+
+    IntervalPos = Interval->advanceTo(IntervalPos, CurPoint);
 
-    // remove expired intervals
-    if (i->expiredAt(cur->beginNumber())) {
-      DEBUG(std::cerr << "\t\tinterval " << *i << " expired\n");
+    if (IntervalPos == Interval->end()) {     // Remove expired intervals.
+      DEBUG(std::cerr << "\t\tinterval " << *Interval << " expired\n");
       if (MRegisterInfo::isVirtualRegister(reg))
         reg = vrm_->getPhys(reg);
       prt_->delRegUse(reg);
-      // swap with last element and move end iterator back one position
-      std::iter_swap(ii, --ie);
-    }
-    // move inactive intervals to inactive list
-    else if (!i->liveAt(cur->beginNumber())) {
-      DEBUG(std::cerr << "\t\tinterval " << *i << " inactive\n");
+
+      // Pop off the end of the list.
+      active_[i] = active_.back();
+      active_.pop_back();
+      --i; --e;
+      
+    } else if (IntervalPos->start > CurPoint) {
+      // Move inactive intervals to inactive list.
+      DEBUG(std::cerr << "\t\tinterval " << *Interval << " inactive\n");
       if (MRegisterInfo::isVirtualRegister(reg))
         reg = vrm_->getPhys(reg);
       prt_->delRegUse(reg);
-      // add to inactive
-      inactive_.push_back(i);
-      // swap with last element and move end iterator back one postion
-      std::iter_swap(ii, --ie);
-    }
-    else {
-      ++ii;
+      // add to inactive.
+      inactive_.push_back(std::make_pair(Interval, IntervalPos));
+
+      // Pop off the end of the list.
+      active_[i] = active_.back();
+      active_.pop_back();
+      --i; --e;
+    } else {
+      // Otherwise, just update the iterator position.
+      active_[i].second = IntervalPos;
     }
   }
-  active_.erase(ie, active_.end());
 }
 
-void RA::processInactiveIntervals(IntervalPtrs::value_type cur)
+/// processInactiveIntervals - expire old intervals and move overlapping
+/// ones to the active list.
+void RA::processInactiveIntervals(unsigned CurPoint)
 {
   DEBUG(std::cerr << "\tprocessing inactive intervals:\n");
-  IntervalPtrs::iterator ii = inactive_.begin(), ie = inactive_.end();
-
-  while (ii != ie) {
-    LiveInterval* i = *ii;
-    unsigned reg = i->reg;
-
-    // remove expired intervals
-    if (i->expiredAt(cur->beginNumber())) {
-      DEBUG(std::cerr << "\t\tinterval " << *i << " expired\n");
-      // swap with last element and move end iterator back one position
-      std::iter_swap(ii, --ie);
-    }
-    // move re-activated intervals in active list
-    else if (i->liveAt(cur->beginNumber())) {
-      DEBUG(std::cerr << "\t\tinterval " << *i << " active\n");
+  for (unsigned i = 0, e = inactive_.size(); i != e; ++i) {
+    LiveInterval *Interval = inactive_[i].first;
+    LiveInterval::iterator IntervalPos = inactive_[i].second;
+    unsigned reg = Interval->reg;
+
+    IntervalPos = Interval->advanceTo(IntervalPos, CurPoint);
+    
+    if (IntervalPos == Interval->end()) {       // remove expired intervals.
+      DEBUG(std::cerr << "\t\tinterval " << *Interval << " expired\n");
+
+      // Pop off the end of the list.
+      inactive_[i] = inactive_.back();
+      inactive_.pop_back();
+      --i; --e;
+    } else if (IntervalPos->start <= CurPoint) {
+      // move re-activated intervals in active list
+      DEBUG(std::cerr << "\t\tinterval " << *Interval << " active\n");
       if (MRegisterInfo::isVirtualRegister(reg))
         reg = vrm_->getPhys(reg);
       prt_->addRegUse(reg);
       // add to active
-      active_.push_back(i);
-      // swap with last element and move end iterator back one position
-      std::iter_swap(ii, --ie);
-    }
-    else {
-      ++ii;
+      active_.push_back(std::make_pair(Interval, IntervalPos));
+
+      // Pop off the end of the list.
+      inactive_[i] = inactive_.back();
+      inactive_.pop_back();
+      --i; --e;
+    } else {
+      // Otherwise, just update the iterator position.
+      inactive_[i].second = IntervalPos;
     }
   }
-  inactive_.erase(ie, inactive_.end());
 }
 
+/// updateSpillWeights - updates the spill weights of the specifed physical
+/// register and its weight.
 void RA::updateSpillWeights(unsigned reg, SpillWeights::value_type weight)
 {
   spillWeights_[reg] += weight;
@@ -304,6 +335,17 @@ void RA::updateSpillWeights(unsigned reg, SpillWeights::value_type weight)
     spillWeights_[*as] += weight;
 }
 
+static RA::IntervalPtrs::iterator FindIntervalInVector(RA::IntervalPtrs &IP,
+                                                       LiveInterval *LI) {
+  for (RA::IntervalPtrs::iterator I = IP.begin(), E = IP.end(); I != E; ++I)
+    if (I->first == LI) return I;
+  return IP.end();
+}
+
+
+
+/// assignRegOrStackSlotAtInterval - assign a register if one is available, or
+/// spill.
 void RA::assignRegOrStackSlotAtInterval(LiveInterval* cur)
 {
   DEBUG(std::cerr << "\tallocating current interval: ");
@@ -315,22 +357,22 @@ void RA::assignRegOrStackSlotAtInterval(LiveInterval* cur)
   // for each interval in active update spill weights
   for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
        i != e; ++i) {
-    unsigned reg = (*i)->reg;
+    unsigned reg = i->first->reg;
     if (MRegisterInfo::isVirtualRegister(reg))
       reg = vrm_->getPhys(reg);
-    updateSpillWeights(reg, (*i)->weight);
+    updateSpillWeights(reg, i->first->weight);
   }
 
   // for every interval in inactive we overlap with, mark the
   // register as not free and update spill weights
   for (IntervalPtrs::const_iterator i = inactive_.begin(),
          e = inactive_.end(); i != e; ++i) {
-    if (cur->overlaps(**i)) {
-      unsigned reg = (*i)->reg;
+    if (cur->overlaps(*i->first)) {
+      unsigned reg = i->first->reg;
       if (MRegisterInfo::isVirtualRegister(reg))
         reg = vrm_->getPhys(reg);
       prt_->addRegUse(reg);
-      updateSpillWeights(reg, (*i)->weight);
+      updateSpillWeights(reg, i->first->weight);
     }
   }
 
@@ -338,10 +380,10 @@ void RA::assignRegOrStackSlotAtInterval(LiveInterval* cur)
   // mark the register as not free and update spill weights
   for (IntervalPtrs::const_iterator i = fixed_.begin(),
          e = fixed_.end(); i != e; ++i) {
-    if (cur->overlaps(**i)) {
-      unsigned reg = (*i)->reg;
+    if (cur->overlaps(*i->first)) {
+      unsigned reg = i->first->reg;
       prt_->addRegUse(reg);
-      updateSpillWeights(reg, (*i)->weight);
+      updateSpillWeights(reg, i->first->weight);
     }
   }
 
@@ -355,7 +397,7 @@ void RA::assignRegOrStackSlotAtInterval(LiveInterval* cur)
     DEBUG(std::cerr <<  mri_->getName(physReg) << '\n');
     vrm_->assignVirt2Phys(cur->reg, physReg);
     prt_->addRegUse(physReg);
-    active_.push_back(cur);
+    active_.push_back(std::make_pair(cur, cur->begin()));
     handled_.push_back(cur);
     return;
   }
@@ -428,64 +470,63 @@ void RA::assignRegOrStackSlotAtInterval(LiveInterval* cur)
   // point
   for (IntervalPtrs::iterator
          i = active_.begin(); i != active_.end(); ++i) {
-    unsigned reg = (*i)->reg;
+    unsigned reg = i->first->reg;
     if (MRegisterInfo::isVirtualRegister(reg) &&
         toSpill[vrm_->getPhys(reg)] &&
-        cur->overlaps(**i)) {
-      DEBUG(std::cerr << "\t\t\tspilling(a): " << **i << '\n');
-      earliestStart = std::min(earliestStart, (*i)->beginNumber());
-      int slot = vrm_->assignVirt2StackSlot((*i)->reg);
+        cur->overlaps(*i->first)) {
+      DEBUG(std::cerr << "\t\t\tspilling(a): " << *i->first << '\n');
+      earliestStart = std::min(earliestStart, i->first->beginNumber());
+      int slot = vrm_->assignVirt2StackSlot(i->first->reg);
       std::vector<LiveInterval*> newIs =
-        li_->addIntervalsForSpills(**i, *vrm_, slot);
+        li_->addIntervalsForSpills(*i->first, *vrm_, slot);
       std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
       spilled.insert(reg);
     }
   }
   for (IntervalPtrs::iterator
          i = inactive_.begin(); i != inactive_.end(); ++i) {
-    unsigned reg = (*i)->reg;
+    unsigned reg = i->first->reg;
     if (MRegisterInfo::isVirtualRegister(reg) &&
         toSpill[vrm_->getPhys(reg)] &&
-        cur->overlaps(**i)) {
-      DEBUG(std::cerr << "\t\t\tspilling(i): " << **i << '\n');
-      earliestStart = std::min(earliestStart, (*i)->beginNumber());
-      int slot = vrm_->assignVirt2StackSlot((*i)->reg);
+        cur->overlaps(*i->first)) {
+      DEBUG(std::cerr << "\t\t\tspilling(i): " << *i->first << '\n');
+      earliestStart = std::min(earliestStart, i->first->beginNumber());
+      int slot = vrm_->assignVirt2StackSlot(reg);
       std::vector<LiveInterval*> newIs =
-        li_->addIntervalsForSpills(**i, *vrm_, slot);
+        li_->addIntervalsForSpills(*i->first, *vrm_, slot);
       std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
       spilled.insert(reg);
     }
   }
 
   DEBUG(std::cerr << "\t\trolling back to: " << earliestStart << '\n');
-  // scan handled in reverse order up to the earliaset start of a
+
+  // Scan handled in reverse order up to the earliest start of a
   // spilled live interval and undo each one, restoring the state of
-  // unhandled
+  // unhandled.
   while (!handled_.empty()) {
     LiveInterval* i = handled_.back();
-    // if this interval starts before t we are done
+    // If this interval starts before t we are done.
     if (i->beginNumber() < earliestStart)
       break;
     DEBUG(std::cerr << "\t\t\tundo changes for: " << *i << '\n');
     handled_.pop_back();
-    // when undoing a live interval allocation we must know if it
-    // is active or inactive to properly update the PhysRegTracker
-    // and the VirtRegMap
+
+    // When undoing a live interval allocation we must know if it is active or
+    // inactive to properly update the PhysRegTracker and the VirtRegMap.
     IntervalPtrs::iterator it;
-    if ((it = std::find(active_.begin(), active_.end(), i)) != active_.end()) {
+    if ((it = FindIntervalInVector(active_, i)) != active_.end()) {
       active_.erase(it);
       if (MRegisterInfo::isPhysicalRegister(i->reg)) {
         prt_->delRegUse(i->reg);
         unhandled_.push(i);
-      }
-      else {
+      } else {
         if (!spilled.count(i->reg))
           unhandled_.push(i);
         prt_->delRegUse(vrm_->getPhys(i->reg));
         vrm_->clearVirt(i->reg);
       }
-    }
-    else if ((it = std::find(inactive_.begin(), inactive_.end(), i)) != inactive_.end()) {
+    } else if ((it = FindIntervalInVector(inactive_, i)) != inactive_.end()) {
       inactive_.erase(it);
       if (MRegisterInfo::isPhysicalRegister(i->reg))
         unhandled_.push(i);
@@ -505,15 +546,16 @@ void RA::assignRegOrStackSlotAtInterval(LiveInterval* cur)
   // scan the rest and undo each interval that expired after t and
   // insert it in active (the next iteration of the algorithm will
   // put it in inactive if required)
-  for (IntervalPtrs::iterator i = handled_.begin(), e = handled_.end(); 
-       i != e; ++i) {
-    if (!(*i)->expiredAt(earliestStart) && (*i)->expiredAt(cur->beginNumber())){
-      DEBUG(std::cerr << "\t\t\tundo changes for: " << **i << '\n');
-      active_.push_back(*i);
-      if (MRegisterInfo::isPhysicalRegister((*i)->reg))
-        prt_->addRegUse((*i)->reg);
+  for (unsigned i = 0, e = handled_.size(); i != e; ++i) {
+    LiveInterval *HI = handled_[i];
+    if (!HI->expiredAt(earliestStart) &&
+        HI->expiredAt(cur->beginNumber())) {
+      DEBUG(std::cerr << "\t\t\tundo changes for: " << *HI << '\n');
+      active_.push_back(std::make_pair(HI, HI->begin()));
+      if (MRegisterInfo::isPhysicalRegister(HI->reg))
+        prt_->addRegUse(HI->reg);
       else
-        prt_->addRegUse(vrm_->getPhys((*i)->reg));
+        prt_->addRegUse(vrm_->getPhys(HI->reg));
     }
   }
 
@@ -522,12 +564,14 @@ void RA::assignRegOrStackSlotAtInterval(LiveInterval* cur)
     unhandled_.push(added[i]);
 }
 
+/// getFreePhysReg - return a free physical register for this virtual register
+/// interval if we have one, otherwise return 0.
 unsigned RA::getFreePhysReg(LiveInterval* cur)
 {
   std::vector<unsigned> inactiveCounts(mri_->getNumRegs(), 0);
   for (IntervalPtrs::iterator i = inactive_.begin(), e = inactive_.end();
        i != e; ++i) {
-    unsigned reg = (*i)->reg;
+    unsigned reg = i->first->reg;
     if (MRegisterInfo::isVirtualRegister(reg))
       reg = vrm_->getPhys(reg);
     ++inactiveCounts[reg];