lib/CodeGen/RegAllocLinearScan.cpp

   1 //===-- RegAllocLinearScan.cpp - Linear Scan register allocator -----------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements a linear scan register allocator.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #define DEBUG_TYPE "regalloc"
  15 #include "llvm/Function.h"
  16 #include "llvm/CodeGen/MachineFunctionPass.h"
  17 #include "llvm/CodeGen/MachineInstr.h"
  18 #include "llvm/CodeGen/Passes.h"
  19 #include "llvm/CodeGen/SSARegMap.h"
  20 #include "llvm/Target/MRegisterInfo.h"
  21 #include "llvm/Target/TargetMachine.h"
  22 #include "llvm/Support/Debug.h"
  23 #include "llvm/ADT/Statistic.h"
  24 #include "llvm/ADT/STLExtras.h"
  25 #include "LiveIntervalAnalysis.h"
  26 #include "PhysRegTracker.h"
  27 #include "VirtRegMap.h"
  28 #include <algorithm>
  29 #include <cmath>
  30 #include <set>
  31 #include <queue>
  32 using namespace llvm;
  33
  34 namespace {
  35
  36   Statistic<double> efficiency
  37   ("regalloc", "Ratio of intervals processed over total intervals");
  38   Statistic<> NumBacktracks("regalloc", "Number of times we had to backtrack");
  39
  40   static unsigned numIterations = 0;
  41   static unsigned numIntervals = 0;
  42
  43   struct RA : public MachineFunctionPass {
  44     typedef std::pair<LiveInterval*, LiveInterval::iterator> IntervalPtr;
  45     typedef std::vector<IntervalPtr> IntervalPtrs;
  46   private:
  47     MachineFunction* mf_;
  48     const TargetMachine* tm_;
  49     const MRegisterInfo* mri_;
  50     LiveIntervals* li_;
  51     bool *PhysRegsUsed;
  52
  53     /// handled_ - Intervals are added to the handled_ set in the order of their
  54     /// start value.  This is uses for backtracking.
  55     std::vector<LiveInterval*> handled_;
  56
  57     /// fixed_ - Intervals that correspond to machine registers.
  58     ///
  59     IntervalPtrs fixed_;
  60
  61     /// active_ - Intervals that are currently being processed, and which have a
  62     /// live range active for the current point.
  63     IntervalPtrs active_;
  64
  65     /// inactive_ - Intervals that are currently being processed, but which have
  66     /// a hold at the current point.
  67     IntervalPtrs inactive_;
  68
  69     typedef std::priority_queue<LiveInterval*,
  70                                 std::vector<LiveInterval*>,
  71                                 greater_ptr<LiveInterval> > IntervalHeap;
  72     IntervalHeap unhandled_;
  73     std::auto_ptr<PhysRegTracker> prt_;
  74     std::auto_ptr<VirtRegMap> vrm_;
  75     std::auto_ptr<Spiller> spiller_;
  76
  77   public:
  78     virtual const char* getPassName() const {
  79       return "Linear Scan Register Allocator";
  80     }
  81
  82     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  83       AU.addRequired<LiveIntervals>();
  84       MachineFunctionPass::getAnalysisUsage(AU);
  85     }
  86
  87     /// runOnMachineFunction - register allocate the whole function
  88     bool runOnMachineFunction(MachineFunction&);
  89
  90   private:
  91     /// linearScan - the linear scan algorithm
  92     void linearScan();
  93
  94     /// initIntervalSets - initialize the interval sets.
  95     ///
  96     void initIntervalSets();
  97
  98     /// processActiveIntervals - expire old intervals and move non-overlapping
  99     /// ones to the inactive list.
 100     void processActiveIntervals(unsigned CurPoint);
 101
 102     /// processInactiveIntervals - expire old intervals and move overlapping
 103     /// ones to the active list.
 104     void processInactiveIntervals(unsigned CurPoint);
 105
 106     /// assignRegOrStackSlotAtInterval - assign a register if one
 107     /// is available, or spill.
 108     void assignRegOrStackSlotAtInterval(LiveInterval* cur);
 109
 110     ///
 111     /// register handling helpers
 112     ///
 113
 114     /// getFreePhysReg - return a free physical register for this virtual
 115     /// register interval if we have one, otherwise return 0.
 116     unsigned getFreePhysReg(LiveInterval* cur);
 117
 118     /// assignVirt2StackSlot - assigns this virtual register to a
 119     /// stack slot. returns the stack slot
 120     int assignVirt2StackSlot(unsigned virtReg);
 121
 122     template <typename ItTy>
 123     void printIntervals(const char* const str, ItTy i, ItTy e) const {
 124       if (str) std::cerr << str << " intervals:\n";
 125       for (; i != e; ++i) {
 126         std::cerr << "\t" << *i->first << " -> ";
 127         unsigned reg = i->first->reg;
 128         if (MRegisterInfo::isVirtualRegister(reg)) {
 129           reg = vrm_->getPhys(reg);
 130         }
 131         std::cerr << mri_->getName(reg) << '\n';
 132       }
 133     }
 134   };
 135 }
 136
 137 bool RA::runOnMachineFunction(MachineFunction &fn) {
 138   mf_ = &fn;
 139   tm_ = &fn.getTarget();
 140   mri_ = tm_->getRegisterInfo();
 141   li_ = &getAnalysis<LiveIntervals>();
 142
 143   PhysRegsUsed = new bool[mri_->getNumRegs()];
 144   std::fill(PhysRegsUsed, PhysRegsUsed+mri_->getNumRegs(), false);
 145   fn.setUsedPhysRegs(PhysRegsUsed);
 146
 147   if (!prt_.get()) prt_.reset(new PhysRegTracker(*mri_));
 148   vrm_.reset(new VirtRegMap(*mf_));
 149   if (!spiller_.get()) spiller_.reset(createSpiller());
 150
 151   initIntervalSets();
 152
 153   linearScan();
 154
 155   // Rewrite spill code and update the PhysRegsUsed set.
 156   spiller_->runOnMachineFunction(*mf_, *vrm_);
 157
 158   vrm_.reset();  // Free the VirtRegMap
 159
 160
 161   while (!unhandled_.empty()) unhandled_.pop();
 162   fixed_.clear();
 163   active_.clear();
 164   inactive_.clear();
 165   handled_.clear();
 166
 167   return true;
 168 }
 169
 170 /// initIntervalSets - initialize the interval sets.
 171 ///
 172 void RA::initIntervalSets()
 173 {
 174   assert(unhandled_.empty() && fixed_.empty() &&
 175          active_.empty() && inactive_.empty() &&
 176          "interval sets should be empty on initialization");
 177
 178   for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) {
 179     if (MRegisterInfo::isPhysicalRegister(i->second.reg)) {
 180       PhysRegsUsed[i->second.reg] = true;
 181       fixed_.push_back(std::make_pair(&i->second, i->second.begin()));
 182     } else
 183       unhandled_.push(&i->second);
 184   }
 185 }
 186
 187 void RA::linearScan()
 188 {
 189   // linear scan algorithm
 190   DEBUG(std::cerr << "********** LINEAR SCAN **********\n");
 191   DEBUG(std::cerr << "********** Function: "
 192         << mf_->getFunction()->getName() << '\n');
 193
 194   // DEBUG(printIntervals("unhandled", unhandled_.begin(), unhandled_.end()));
 195   DEBUG(printIntervals("fixed", fixed_.begin(), fixed_.end()));
 196   DEBUG(printIntervals("active", active_.begin(), active_.end()));
 197   DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
 198
 199   while (!unhandled_.empty()) {
 200     // pick the interval with the earliest start point
 201     LiveInterval* cur = unhandled_.top();
 202     unhandled_.pop();
 203     ++numIterations;
 204     DEBUG(std::cerr << "\n*** CURRENT ***: " << *cur << '\n');
 205
 206     processActiveIntervals(cur->beginNumber());
 207     processInactiveIntervals(cur->beginNumber());
 208
 209     assert(MRegisterInfo::isVirtualRegister(cur->reg) &&
 210            "Can only allocate virtual registers!");
 211
 212     // Allocating a virtual register. try to find a free
 213     // physical register or spill an interval (possibly this one) in order to
 214     // assign it one.
 215     assignRegOrStackSlotAtInterval(cur);
 216
 217     DEBUG(printIntervals("active", active_.begin(), active_.end()));
 218     DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
 219   }
 220   numIntervals += li_->getNumIntervals();
 221   efficiency = double(numIterations) / double(numIntervals);
 222
 223   // expire any remaining active intervals
 224   for (IntervalPtrs::reverse_iterator
 225          i = active_.rbegin(); i != active_.rend(); ) {
 226     unsigned reg = i->first->reg;
 227     DEBUG(std::cerr << "\tinterval " << *i->first << " expired\n");
 228     assert(MRegisterInfo::isVirtualRegister(reg) &&
 229            "Can only allocate virtual registers!");
 230     reg = vrm_->getPhys(reg);
 231     prt_->delRegUse(reg);
 232     i = IntervalPtrs::reverse_iterator(active_.erase(i.base()-1));
 233   }
 234
 235   // expire any remaining inactive intervals
 236   for (IntervalPtrs::reverse_iterator
 237          i = inactive_.rbegin(); i != inactive_.rend(); ) {
 238     DEBUG(std::cerr << "\tinterval " << *i->first << " expired\n");
 239     i = IntervalPtrs::reverse_iterator(inactive_.erase(i.base()-1));
 240   }
 241
 242   DEBUG(std::cerr << *vrm_);
 243 }
 244
 245 /// processActiveIntervals - expire old intervals and move non-overlapping ones
 246 /// to the inactive list.
 247 void RA::processActiveIntervals(unsigned CurPoint)
 248 {
 249   DEBUG(std::cerr << "\tprocessing active intervals:\n");
 250
 251   for (unsigned i = 0, e = active_.size(); i != e; ++i) {
 252     LiveInterval *Interval = active_[i].first;
 253     LiveInterval::iterator IntervalPos = active_[i].second;
 254     unsigned reg = Interval->reg;
 255
 256     IntervalPos = Interval->advanceTo(IntervalPos, CurPoint);
 257
 258     if (IntervalPos == Interval->end()) {     // Remove expired intervals.
 259       DEBUG(std::cerr << "\t\tinterval " << *Interval << " expired\n");
 260       assert(MRegisterInfo::isVirtualRegister(reg) &&
 261              "Can only allocate virtual registers!");
 262       reg = vrm_->getPhys(reg);
 263       prt_->delRegUse(reg);
 264
 265       // Pop off the end of the list.
 266       active_[i] = active_.back();
 267       active_.pop_back();
 268       --i; --e;
 269
 270     } else if (IntervalPos->start > CurPoint) {
 271       // Move inactive intervals to inactive list.
 272       DEBUG(std::cerr << "\t\tinterval " << *Interval << " inactive\n");
 273       assert(MRegisterInfo::isVirtualRegister(reg) &&
 274              "Can only allocate virtual registers!");
 275       reg = vrm_->getPhys(reg);
 276       prt_->delRegUse(reg);
 277       // add to inactive.
 278       inactive_.push_back(std::make_pair(Interval, IntervalPos));
 279
 280       // Pop off the end of the list.
 281       active_[i] = active_.back();
 282       active_.pop_back();
 283       --i; --e;
 284     } else {
 285       // Otherwise, just update the iterator position.
 286       active_[i].second = IntervalPos;
 287     }
 288   }
 289 }
 290
 291 /// processInactiveIntervals - expire old intervals and move overlapping
 292 /// ones to the active list.
 293 void RA::processInactiveIntervals(unsigned CurPoint)
 294 {
 295   DEBUG(std::cerr << "\tprocessing inactive intervals:\n");
 296
 297   for (unsigned i = 0, e = inactive_.size(); i != e; ++i) {
 298     LiveInterval *Interval = inactive_[i].first;
 299     LiveInterval::iterator IntervalPos = inactive_[i].second;
 300     unsigned reg = Interval->reg;
 301
 302     IntervalPos = Interval->advanceTo(IntervalPos, CurPoint);
 303
 304     if (IntervalPos == Interval->end()) {       // remove expired intervals.
 305       DEBUG(std::cerr << "\t\tinterval " << *Interval << " expired\n");
 306
 307       // Pop off the end of the list.
 308       inactive_[i] = inactive_.back();
 309       inactive_.pop_back();
 310       --i; --e;
 311     } else if (IntervalPos->start <= CurPoint) {
 312       // move re-activated intervals in active list
 313       DEBUG(std::cerr << "\t\tinterval " << *Interval << " active\n");
 314       assert(MRegisterInfo::isVirtualRegister(reg) &&
 315              "Can only allocate virtual registers!");
 316       reg = vrm_->getPhys(reg);
 317       prt_->addRegUse(reg);
 318       // add to active
 319       active_.push_back(std::make_pair(Interval, IntervalPos));
 320
 321       // Pop off the end of the list.
 322       inactive_[i] = inactive_.back();
 323       inactive_.pop_back();
 324       --i; --e;
 325     } else {
 326       // Otherwise, just update the iterator position.
 327       inactive_[i].second = IntervalPos;
 328     }
 329   }
 330 }
 331
 332 /// updateSpillWeights - updates the spill weights of the specifed physical
 333 /// register and its weight.
 334 static void updateSpillWeights(std::vector<float> &Weights,
 335                                unsigned reg, float weight,
 336                                const MRegisterInfo *MRI) {
 337   Weights[reg] += weight;
 338   for (const unsigned* as = MRI->getAliasSet(reg); *as; ++as)
 339     Weights[*as] += weight;
 340 }
 341
 342 static RA::IntervalPtrs::iterator FindIntervalInVector(RA::IntervalPtrs &IP,
 343                                                        LiveInterval *LI) {
 344   for (RA::IntervalPtrs::iterator I = IP.begin(), E = IP.end(); I != E; ++I)
 345     if (I->first == LI) return I;
 346   return IP.end();
 347 }
 348
 349 static void RevertVectorIteratorsTo(RA::IntervalPtrs &V, unsigned Point) {
 350   for (unsigned i = 0, e = V.size(); i != e; ++i) {
 351     RA::IntervalPtr &IP = V[i];
 352     LiveInterval::iterator I = std::upper_bound(IP.first->begin(),
 353                                                 IP.second, Point);
 354     if (I != IP.first->begin()) --I;
 355     IP.second = I;
 356   }
 357 }
 358
 359
 360 /// assignRegOrStackSlotAtInterval - assign a register if one is available, or
 361 /// spill.
 362 void RA::assignRegOrStackSlotAtInterval(LiveInterval* cur)
 363 {
 364   DEBUG(std::cerr << "\tallocating current interval: ");
 365
 366   PhysRegTracker backupPrt = *prt_;
 367
 368   std::vector<std::pair<unsigned, float> > SpillWeightsToAdd;
 369   unsigned StartPosition = cur->beginNumber();
 370
 371   // for every interval in inactive we overlap with, mark the
 372   // register as not free and update spill weights.
 373   for (IntervalPtrs::const_iterator i = inactive_.begin(),
 374          e = inactive_.end(); i != e; ++i) {
 375     if (cur->overlapsFrom(*i->first, i->second-1)) {
 376       unsigned reg = i->first->reg;
 377       assert(MRegisterInfo::isVirtualRegister(reg) &&
 378              "Can only allocate virtual registers!");
 379       reg = vrm_->getPhys(reg);
 380       prt_->addRegUse(reg);
 381       SpillWeightsToAdd.push_back(std::make_pair(reg, i->first->weight));
 382     }
 383   }
 384
 385   // For every interval in fixed we overlap with, mark the register as not free
 386   // and update spill weights.
 387   for (unsigned i = 0, e = fixed_.size(); i != e; ++i) {
 388     IntervalPtr &IP = fixed_[i];
 389     LiveInterval *I = IP.first;
 390     if (I->endNumber() > StartPosition) {
 391       LiveInterval::iterator II = I->advanceTo(IP.second, StartPosition);
 392       IP.second = II;
 393       if (II != I->begin() && II->start > StartPosition)
 394         --II;
 395       if (cur->overlapsFrom(*I, II)) {
 396         unsigned reg = I->reg;
 397         prt_->addRegUse(reg);
 398         SpillWeightsToAdd.push_back(std::make_pair(reg, I->weight));
 399       }
 400     }
 401   }
 402
 403   // Using the newly updated prt_ object, which includes conflicts in the
 404   // future, see if there are any registers available.
 405   unsigned physReg = getFreePhysReg(cur);
 406
 407   // Restore the physical register tracker, removing information about the
 408   // future.
 409   *prt_ = backupPrt;
 410
 411   // if we find a free register, we are done: assign this virtual to
 412   // the free physical register and add this interval to the active
 413   // list.
 414   if (physReg) {
 415     DEBUG(std::cerr <<  mri_->getName(physReg) << '\n');
 416     vrm_->assignVirt2Phys(cur->reg, physReg);
 417     prt_->addRegUse(physReg);
 418     active_.push_back(std::make_pair(cur, cur->begin()));
 419     handled_.push_back(cur);
 420     return;
 421   }
 422   DEBUG(std::cerr << "no free registers\n");
 423
 424   // Compile the spill weights into an array that is better for scanning.
 425   std::vector<float> SpillWeights(mri_->getNumRegs(), 0.0);
 426   for (std::vector<std::pair<unsigned, float> >::iterator
 427        I = SpillWeightsToAdd.begin(), E = SpillWeightsToAdd.end(); I != E; ++I)
 428     updateSpillWeights(SpillWeights, I->first, I->second, mri_);
 429
 430   // for each interval in active, update spill weights.
 431   for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
 432        i != e; ++i) {
 433     unsigned reg = i->first->reg;
 434     assert(MRegisterInfo::isVirtualRegister(reg) &&
 435            "Can only allocate virtual registers!");
 436     reg = vrm_->getPhys(reg);
 437     updateSpillWeights(SpillWeights, reg, i->first->weight, mri_);
 438   }
 439
 440   DEBUG(std::cerr << "\tassigning stack slot at interval "<< *cur << ":\n");
 441
 442   float minWeight = float(HUGE_VAL);
 443   unsigned minReg = 0;
 444   const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
 445   for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_),
 446        e = rc->allocation_order_end(*mf_); i != e; ++i) {
 447     unsigned reg = *i;
 448     if (minWeight > SpillWeights[reg]) {
 449       minWeight = SpillWeights[reg];
 450       minReg = reg;
 451     }
 452   }
 453   DEBUG(std::cerr << "\t\tregister with min weight: "
 454         << mri_->getName(minReg) << " (" << minWeight << ")\n");
 455
 456   // if the current has the minimum weight, we need to spill it and
 457   // add any added intervals back to unhandled, and restart
 458   // linearscan.
 459   if (cur->weight <= minWeight) {
 460     DEBUG(std::cerr << "\t\t\tspilling(c): " << *cur << '\n';);
 461     int slot = vrm_->assignVirt2StackSlot(cur->reg);
 462     std::vector<LiveInterval*> added =
 463       li_->addIntervalsForSpills(*cur, *vrm_, slot);
 464     if (added.empty())
 465       return;  // Early exit if all spills were folded.
 466
 467     // Merge added with unhandled.  Note that we know that
 468     // addIntervalsForSpills returns intervals sorted by their starting
 469     // point.
 470     for (unsigned i = 0, e = added.size(); i != e; ++i)
 471       unhandled_.push(added[i]);
 472     return;
 473   }
 474
 475   ++NumBacktracks;
 476
 477   // push the current interval back to unhandled since we are going
 478   // to re-run at least this iteration. Since we didn't modify it it
 479   // should go back right in the front of the list
 480   unhandled_.push(cur);
 481
 482   // otherwise we spill all intervals aliasing the register with
 483   // minimum weight, rollback to the interval with the earliest
 484   // start point and let the linear scan algorithm run again
 485   std::vector<LiveInterval*> added;
 486   assert(MRegisterInfo::isPhysicalRegister(minReg) &&
 487          "did not choose a register to spill?");
 488   std::vector<bool> toSpill(mri_->getNumRegs(), false);
 489
 490   // We are going to spill minReg and all its aliases.
 491   toSpill[minReg] = true;
 492   for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as)
 493     toSpill[*as] = true;
 494
 495   // the earliest start of a spilled interval indicates up to where
 496   // in handled we need to roll back
 497   unsigned earliestStart = cur->beginNumber();
 498
 499   // set of spilled vregs (used later to rollback properly)
 500   std::set<unsigned> spilled;
 501
 502   // spill live intervals of virtual regs mapped to the physical register we
 503   // want to clear (and its aliases).  We only spill those that overlap with the
 504   // current interval as the rest do not affect its allocation. we also keep
 505   // track of the earliest start of all spilled live intervals since this will
 506   // mark our rollback point.
 507   for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
 508     unsigned reg = i->first->reg;
 509     if (//MRegisterInfo::isVirtualRegister(reg) &&
 510         toSpill[vrm_->getPhys(reg)] &&
 511         cur->overlapsFrom(*i->first, i->second)) {
 512       DEBUG(std::cerr << "\t\t\tspilling(a): " << *i->first << '\n');
 513       earliestStart = std::min(earliestStart, i->first->beginNumber());
 514       int slot = vrm_->assignVirt2StackSlot(i->first->reg);
 515       std::vector<LiveInterval*> newIs =
 516         li_->addIntervalsForSpills(*i->first, *vrm_, slot);
 517       std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
 518       spilled.insert(reg);
 519     }
 520   }
 521   for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end(); ++i){
 522     unsigned reg = i->first->reg;
 523     if (//MRegisterInfo::isVirtualRegister(reg) &&
 524         toSpill[vrm_->getPhys(reg)] &&
 525         cur->overlapsFrom(*i->first, i->second-1)) {
 526       DEBUG(std::cerr << "\t\t\tspilling(i): " << *i->first << '\n');
 527       earliestStart = std::min(earliestStart, i->first->beginNumber());
 528       int slot = vrm_->assignVirt2StackSlot(reg);
 529       std::vector<LiveInterval*> newIs =
 530         li_->addIntervalsForSpills(*i->first, *vrm_, slot);
 531       std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
 532       spilled.insert(reg);
 533     }
 534   }
 535
 536   DEBUG(std::cerr << "\t\trolling back to: " << earliestStart << '\n');
 537
 538   // Scan handled in reverse order up to the earliest start of a
 539   // spilled live interval and undo each one, restoring the state of
 540   // unhandled.
 541   while (!handled_.empty()) {
 542     LiveInterval* i = handled_.back();
 543     // If this interval starts before t we are done.
 544     if (i->beginNumber() < earliestStart)
 545       break;
 546     DEBUG(std::cerr << "\t\t\tundo changes for: " << *i << '\n');
 547     handled_.pop_back();
 548
 549     // When undoing a live interval allocation we must know if it is active or
 550     // inactive to properly update the PhysRegTracker and the VirtRegMap.
 551     IntervalPtrs::iterator it;
 552     if ((it = FindIntervalInVector(active_, i)) != active_.end()) {
 553       active_.erase(it);
 554       if (MRegisterInfo::isPhysicalRegister(i->reg)) {
 555         assert(0 && "daksjlfd");
 556         prt_->delRegUse(i->reg);
 557         unhandled_.push(i);
 558       } else {
 559         if (!spilled.count(i->reg))
 560           unhandled_.push(i);
 561         prt_->delRegUse(vrm_->getPhys(i->reg));
 562         vrm_->clearVirt(i->reg);
 563       }
 564     } else if ((it = FindIntervalInVector(inactive_, i)) != inactive_.end()) {
 565       inactive_.erase(it);
 566       if (MRegisterInfo::isPhysicalRegister(i->reg)) {
 567         assert(0 && "daksjlfd");
 568         unhandled_.push(i);
 569       } else {
 570         if (!spilled.count(i->reg))
 571           unhandled_.push(i);
 572         vrm_->clearVirt(i->reg);
 573       }
 574     } else {
 575       assert(MRegisterInfo::isVirtualRegister(i->reg) &&
 576              "Can only allocate virtual registers!");
 577       vrm_->clearVirt(i->reg);
 578       unhandled_.push(i);
 579     }
 580   }
 581
 582   // Rewind the iterators in the active, inactive, and fixed lists back to the
 583   // point we reverted to.
 584   RevertVectorIteratorsTo(active_, earliestStart);
 585   RevertVectorIteratorsTo(inactive_, earliestStart);
 586   RevertVectorIteratorsTo(fixed_, earliestStart);
 587
 588   // scan the rest and undo each interval that expired after t and
 589   // insert it in active (the next iteration of the algorithm will
 590   // put it in inactive if required)
 591   for (unsigned i = 0, e = handled_.size(); i != e; ++i) {
 592     LiveInterval *HI = handled_[i];
 593     if (!HI->expiredAt(earliestStart) &&
 594         HI->expiredAt(cur->beginNumber())) {
 595       DEBUG(std::cerr << "\t\t\tundo changes for: " << *HI << '\n');
 596       active_.push_back(std::make_pair(HI, HI->begin()));
 597       if (MRegisterInfo::isPhysicalRegister(HI->reg)) {
 598         assert(0 &&"sdflkajsdf");
 599         prt_->addRegUse(HI->reg);
 600       } else
 601         prt_->addRegUse(vrm_->getPhys(HI->reg));
 602     }
 603   }
 604
 605   // merge added with unhandled
 606   for (unsigned i = 0, e = added.size(); i != e; ++i)
 607     unhandled_.push(added[i]);
 608 }
 609
 610 /// getFreePhysReg - return a free physical register for this virtual register
 611 /// interval if we have one, otherwise return 0.
 612 unsigned RA::getFreePhysReg(LiveInterval* cur)
 613 {
 614   std::vector<unsigned> inactiveCounts(mri_->getNumRegs(), 0);
 615   unsigned MaxInactiveCount = 0;
 616
 617   for (IntervalPtrs::iterator i = inactive_.begin(), e = inactive_.end();
 618        i != e; ++i) {
 619     unsigned reg = i->first->reg;
 620     assert(MRegisterInfo::isVirtualRegister(reg) &&
 621            "Can only allocate virtual registers!");
 622     reg = vrm_->getPhys(reg);
 623     ++inactiveCounts[reg];
 624     MaxInactiveCount = std::max(MaxInactiveCount, inactiveCounts[reg]);
 625   }
 626
 627   const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
 628
 629   unsigned FreeReg = 0;
 630   unsigned FreeRegInactiveCount = 0;
 631
 632   // Scan for the first available register.
 633   TargetRegisterClass::iterator I = rc->allocation_order_begin(*mf_);
 634   TargetRegisterClass::iterator E = rc->allocation_order_end(*mf_);
 635   for (; I != E; ++I)
 636     if (prt_->isRegAvail(*I)) {
 637       FreeReg = *I;
 638       FreeRegInactiveCount = inactiveCounts[FreeReg];
 639       break;
 640     }
 641
 642   // If there are no free regs, or if this reg has the max inactive count,
 643   // return this register.
 644   if (FreeReg == 0 || FreeRegInactiveCount == MaxInactiveCount) return FreeReg;
 645
 646   // Continue scanning the registers, looking for the one with the highest
 647   // inactive count.  Alkis found that this reduced register pressure very
 648   // slightly on X86 (in rev 1.94 of this file), though this should probably be
 649   // reevaluated now.
 650   for (; I != E; ++I) {
 651     unsigned Reg = *I;
 652     if (prt_->isRegAvail(Reg) && FreeRegInactiveCount < inactiveCounts[Reg]) {
 653       FreeReg = Reg;
 654       FreeRegInactiveCount = inactiveCounts[Reg];
 655       if (FreeRegInactiveCount == MaxInactiveCount)
 656         break;    // We found the one with the max inactive count.
 657     }
 658   }
 659
 660   return FreeReg;
 661 }
 662
 663 FunctionPass* llvm::createLinearScanRegisterAllocator() {
 664   return new RA();
 665 }