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 #define DEBUG_TYPE "regalloc"
  14 #include "llvm/Function.h"
  15 #include "llvm/CodeGen/LiveVariables.h"
  16 #include "llvm/CodeGen/MachineFrameInfo.h"
  17 #include "llvm/CodeGen/MachineFunctionPass.h"
  18 #include "llvm/CodeGen/MachineInstr.h"
  19 #include "llvm/CodeGen/Passes.h"
  20 #include "llvm/CodeGen/SSARegMap.h"
  21 #include "llvm/Target/MRegisterInfo.h"
  22 #include "llvm/Target/TargetInstrInfo.h"
  23 #include "llvm/Target/TargetMachine.h"
  24 #include "llvm/Support/CFG.h"
  25 #include "Support/Debug.h"
  26 #include "Support/DepthFirstIterator.h"
  27 #include "Support/Statistic.h"
  28 #include "Support/STLExtras.h"
  29 #include "LiveIntervals.h"
  30 #include <algorithm>
  31 using namespace llvm;
  32
  33 namespace {
  34     Statistic<> numStores("ra-linearscan", "Number of stores added");
  35     Statistic<> numLoads ("ra-linearscan", "Number of loads added");
  36
  37     class PhysRegTracker {
  38     private:
  39         const MRegisterInfo* mri_;
  40         std::vector<unsigned> regUse_;
  41
  42     public:
  43         PhysRegTracker(MachineFunction* mf)
  44             : mri_(mf ? mf->getTarget().getRegisterInfo() : NULL) {
  45             if (mri_) {
  46                 regUse_.assign(mri_->getNumRegs(), 0);
  47             }
  48         }
  49
  50         PhysRegTracker(const PhysRegTracker& rhs)
  51             : mri_(rhs.mri_),
  52               regUse_(rhs.regUse_) {
  53         }
  54
  55         const PhysRegTracker& operator=(const PhysRegTracker& rhs) {
  56             mri_ = rhs.mri_;
  57             regUse_ = rhs.regUse_;
  58             return *this;
  59         }
  60
  61         void addPhysRegUse(unsigned physReg) {
  62             ++regUse_[physReg];
  63             for (const unsigned* as = mri_->getAliasSet(physReg); *as; ++as) {
  64                 physReg = *as;
  65                 ++regUse_[physReg];
  66             }
  67         }
  68
  69         void delPhysRegUse(unsigned physReg) {
  70             assert(regUse_[physReg] != 0);
  71             --regUse_[physReg];
  72             for (const unsigned* as = mri_->getAliasSet(physReg); *as; ++as) {
  73                 physReg = *as;
  74                 assert(regUse_[physReg] != 0);
  75                 --regUse_[physReg];
  76             }
  77         }
  78
  79         bool isPhysRegAvail(unsigned physReg) const {
  80             return regUse_[physReg] == 0;
  81         }
  82     };
  83
  84     class RA : public MachineFunctionPass {
  85     private:
  86         MachineFunction* mf_;
  87         const TargetMachine* tm_;
  88         const TargetInstrInfo* tii_;
  89         const MRegisterInfo* mri_;
  90         LiveIntervals* li_;
  91         typedef std::list<LiveIntervals::Interval*> IntervalPtrs;
  92         IntervalPtrs unhandled_, fixed_, active_, inactive_, handled_;
  93
  94         PhysRegTracker prt_;
  95
  96         typedef std::map<unsigned, unsigned> Virt2PhysMap;
  97         Virt2PhysMap v2pMap_;
  98
  99         typedef std::map<unsigned, int> Virt2StackSlotMap;
 100         Virt2StackSlotMap v2ssMap_;
 101
 102         int instrAdded_;
 103
 104         typedef std::vector<float> SpillWeights;
 105         SpillWeights spillWeights_;
 106
 107     public:
 108         RA()
 109             : prt_(NULL) {
 110
 111         }
 112
 113         virtual const char* getPassName() const {
 114             return "Linear Scan Register Allocator";
 115         }
 116
 117         virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 118             AU.addRequired<LiveVariables>();
 119             AU.addRequired<LiveIntervals>();
 120             MachineFunctionPass::getAnalysisUsage(AU);
 121         }
 122
 123         /// runOnMachineFunction - register allocate the whole function
 124         bool runOnMachineFunction(MachineFunction&);
 125
 126         void releaseMemory();
 127
 128     private:
 129         /// initIntervalSets - initializa the four interval sets:
 130         /// unhandled, fixed, active and inactive
 131         void initIntervalSets(LiveIntervals::Intervals& li);
 132
 133         /// processActiveIntervals - expire old intervals and move
 134         /// non-overlapping ones to the incative list
 135         void processActiveIntervals(IntervalPtrs::value_type cur);
 136
 137         /// processInactiveIntervals - expire old intervals and move
 138         /// overlapping ones to the active list
 139         void processInactiveIntervals(IntervalPtrs::value_type cur);
 140
 141         /// updateSpillWeights - updates the spill weights of the
 142         /// specifed physical register and its weight
 143         void updateSpillWeights(unsigned reg, SpillWeights::value_type weight);
 144
 145         /// assignRegOrStackSlotAtInterval - assign a register if one
 146         /// is available, or spill.
 147         void assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur);
 148
 149         /// addSpillCode - adds spill code for interval. The interval
 150         /// must be modified by LiveIntervals::updateIntervalForSpill.
 151         void addSpillCode(IntervalPtrs::value_type li, int slot);
 152
 153         ///
 154         /// register handling helpers
 155         ///
 156
 157         /// getFreePhysReg - return a free physical register for this
 158         /// virtual register interval if we have one, otherwise return
 159         /// 0
 160         unsigned getFreePhysReg(IntervalPtrs::value_type cur);
 161
 162         /// assignVirt2PhysReg - assigns the free physical register to
 163         /// the virtual register passed as arguments
 164         Virt2PhysMap::iterator
 165         assignVirt2PhysReg(unsigned virtReg, unsigned physReg);
 166
 167         /// clearVirtReg - free the physical register associated with this
 168         /// virtual register and disassociate virtual->physical and
 169         /// physical->virtual mappings
 170         void clearVirtReg(Virt2PhysMap::iterator it);
 171
 172         /// assignVirt2StackSlot - assigns this virtual register to a
 173         /// stack slot. returns the stack slot
 174         int assignVirt2StackSlot(unsigned virtReg);
 175
 176         /// getStackSlot - returns the offset of the specified
 177         /// register on the stack
 178         int getStackSlot(unsigned virtReg);
 179
 180         void printVirtRegAssignment() const {
 181             std::cerr << "register assignment:\n";
 182
 183             for (Virt2PhysMap::const_iterator
 184                      i = v2pMap_.begin(), e = v2pMap_.end(); i != e; ++i) {
 185                 assert(i->second != 0);
 186                 std::cerr << "[reg" << i->first << " -> "
 187                           << mri_->getName(i->second) << "]\n";
 188             }
 189             for (Virt2StackSlotMap::const_iterator
 190                      i = v2ssMap_.begin(), e = v2ssMap_.end(); i != e; ++i) {
 191                 std::cerr << '[' << i->first << " -> ss#" << i->second << "]\n";
 192             }
 193             std::cerr << '\n';
 194         }
 195
 196         void printIntervals(const char* const str,
 197                             RA::IntervalPtrs::const_iterator i,
 198                             RA::IntervalPtrs::const_iterator e) const {
 199             if (str) std::cerr << str << " intervals:\n";
 200             for (; i != e; ++i) {
 201                 std::cerr << "\t" << **i << " -> ";
 202                 unsigned reg = (*i)->reg;
 203                 if (MRegisterInfo::isVirtualRegister(reg)) {
 204                     Virt2PhysMap::const_iterator it = v2pMap_.find(reg);
 205                     reg = (it == v2pMap_.end() ? 0 : it->second);
 206                 }
 207                 std::cerr << mri_->getName(reg) << '\n';
 208             }
 209         }
 210
 211         void verifyAssignment() const {
 212             for (Virt2PhysMap::const_iterator i = v2pMap_.begin(),
 213                      e = v2pMap_.end(); i != e; ++i)
 214                 for (Virt2PhysMap::const_iterator i2 = next(i); i2 != e; ++i2)
 215                     if (MRegisterInfo::isVirtualRegister(i->second) &&
 216                         (i->second == i2->second ||
 217                          mri_->areAliases(i->second, i2->second))) {
 218                         const LiveIntervals::Interval
 219                             &in = li_->getInterval(i->second),
 220                             &in2 = li_->getInterval(i2->second);
 221                         if (in.overlaps(in2)) {
 222                             std::cerr << in << " overlaps " << in2 << '\n';
 223                             assert(0);
 224                         }
 225                     }
 226         }
 227     };
 228 }
 229
 230 void RA::releaseMemory()
 231 {
 232     v2pMap_.clear();
 233     v2ssMap_.clear();
 234     unhandled_.clear();
 235     active_.clear();
 236     inactive_.clear();
 237     fixed_.clear();
 238     handled_.clear();
 239 }
 240
 241 bool RA::runOnMachineFunction(MachineFunction &fn) {
 242     mf_ = &fn;
 243     tm_ = &fn.getTarget();
 244     tii_ = &tm_->getInstrInfo();
 245     mri_ = tm_->getRegisterInfo();
 246     li_ = &getAnalysis<LiveIntervals>();
 247     prt_ = PhysRegTracker(mf_);
 248
 249     initIntervalSets(li_->getIntervals());
 250
 251     // linear scan algorithm
 252     DEBUG(std::cerr << "********** LINEAR SCAN **********\n");
 253     DEBUG(std::cerr << "********** Function: "
 254           << mf_->getFunction()->getName() << '\n');
 255
 256     DEBUG(printIntervals("unhandled", unhandled_.begin(), unhandled_.end()));
 257     DEBUG(printIntervals("fixed", fixed_.begin(), fixed_.end()));
 258     DEBUG(printIntervals("active", active_.begin(), active_.end()));
 259     DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
 260
 261     while (!unhandled_.empty() || !fixed_.empty()) {
 262         // pick the interval with the earliest start point
 263         IntervalPtrs::value_type cur;
 264         if (fixed_.empty()) {
 265             cur = unhandled_.front();
 266             unhandled_.pop_front();
 267         }
 268         else if (unhandled_.empty()) {
 269             cur = fixed_.front();
 270             fixed_.pop_front();
 271         }
 272         else if (unhandled_.front()->start() < fixed_.front()->start()) {
 273             cur = unhandled_.front();
 274             unhandled_.pop_front();
 275         }
 276         else {
 277             cur = fixed_.front();
 278             fixed_.pop_front();
 279         }
 280
 281         DEBUG(std::cerr << "\n*** CURRENT ***: " << *cur << '\n');
 282
 283         processActiveIntervals(cur);
 284         processInactiveIntervals(cur);
 285
 286         // if this register is fixed we are done
 287         if (MRegisterInfo::isPhysicalRegister(cur->reg)) {
 288             prt_.addPhysRegUse(cur->reg);
 289             active_.push_back(cur);
 290             handled_.push_back(cur);
 291         }
 292         // otherwise we are allocating a virtual register. try to find
 293         // a free physical register or spill an interval in order to
 294         // assign it one (we could spill the current though).
 295         else {
 296             assignRegOrStackSlotAtInterval(cur);
 297         }
 298
 299         DEBUG(printIntervals("active", active_.begin(), active_.end()));
 300         DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
 301         // DEBUG(verifyAssignment());
 302     }
 303
 304     // expire any remaining active intervals
 305     for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
 306         unsigned reg = (*i)->reg;
 307         DEBUG(std::cerr << "\tinterval " << **i << " expired\n");
 308         if (MRegisterInfo::isVirtualRegister(reg)) {
 309             reg = v2pMap_[reg];
 310         }
 311         prt_.delPhysRegUse(reg);
 312     }
 313
 314     DEBUG(printVirtRegAssignment());
 315
 316     DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n");
 317     DEBUG(std::cerr << "********** Function: "
 318           << mf_->getFunction()->getName() << '\n');
 319
 320     for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
 321          mbbi != mbbe; ++mbbi) {
 322         instrAdded_ = 0;
 323
 324         for (MachineBasicBlock::iterator mii = mbbi->begin(), mie = mbbi->end();
 325              mii != mie; ++mii) {
 326             DEBUG(
 327                 std::cerr << '[';
 328                 unsigned index = li_->getInstructionIndex(mii);
 329                 if (index == std::numeric_limits<unsigned>::max())
 330                     std::cerr << '*';
 331                 else
 332                     std::cerr << index;
 333                 std::cerr << "]\t";
 334                 mii->print(std::cerr, *tm_));
 335
 336             // use our current mapping and actually replace every
 337             // virtual register with its allocated physical registers
 338             DEBUG(std::cerr << "\t");
 339             for (unsigned i = 0, e = mii->getNumOperands();
 340                  i != e; ++i) {
 341                 MachineOperand& op = mii->getOperand(i);
 342                 if (op.isRegister() &&
 343                     MRegisterInfo::isVirtualRegister(op.getReg())) {
 344                     unsigned virtReg = op.getReg();
 345                     Virt2PhysMap::iterator it = v2pMap_.find(virtReg);
 346                     assert(it != v2pMap_.end() &&
 347                            "all virtual registers must be allocated");
 348                     unsigned physReg = it->second;
 349                     assert(MRegisterInfo::isPhysicalRegister(physReg));
 350                     DEBUG(std::cerr << "\t[reg" << virtReg
 351                           << " -> " << mri_->getName(physReg) << ']');
 352                     mii->SetMachineOperandReg(i, physReg);
 353                 }
 354             }
 355             DEBUG(std::cerr << '\n');
 356         }
 357     }
 358
 359     DEBUG(std::cerr << "********** MACHINEINSTRS **********\n");
 360     DEBUG(
 361         for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
 362              mbbi != mbbe; ++mbbi) {
 363             std::cerr << mbbi->getBasicBlock()->getName() << ":\n";
 364             for (MachineBasicBlock::iterator mii = mbbi->begin(),
 365                      mie = mbbi->end(); mii != mie; ++mii) {
 366                 unsigned index = li_->getInstructionIndex(mii);
 367                 if (index == std::numeric_limits<unsigned>::max())
 368                     std::cerr << "*\t";
 369                 else
 370                     std::cerr << index << '\t';
 371                 mii->print(std::cerr, *tm_);
 372             }
 373         });
 374
 375     return true;
 376 }
 377
 378 void RA::initIntervalSets(LiveIntervals::Intervals& li)
 379 {
 380     assert(unhandled_.empty() && fixed_.empty() &&
 381            active_.empty() && inactive_.empty() &&
 382            "interval sets should be empty on initialization");
 383
 384     for (LiveIntervals::Intervals::iterator i = li.begin(), e = li.end();
 385          i != e; ++i) {
 386         if (MRegisterInfo::isPhysicalRegister(i->reg))
 387             fixed_.push_back(&*i);
 388         else
 389             unhandled_.push_back(&*i);
 390     }
 391 }
 392
 393 void RA::processActiveIntervals(IntervalPtrs::value_type cur)
 394 {
 395     DEBUG(std::cerr << "\tprocessing active intervals:\n");
 396     for (IntervalPtrs::iterator i = active_.begin(); i != active_.end();) {
 397         unsigned reg = (*i)->reg;
 398         // remove expired intervals
 399         if ((*i)->expiredAt(cur->start())) {
 400             DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n");
 401             if (MRegisterInfo::isVirtualRegister(reg)) {
 402                 reg = v2pMap_[reg];
 403             }
 404             prt_.delPhysRegUse(reg);
 405             // remove from active
 406             i = active_.erase(i);
 407         }
 408         // move inactive intervals to inactive list
 409         else if (!(*i)->liveAt(cur->start())) {
 410             DEBUG(std::cerr << "\t\tinterval " << **i << " inactive\n");
 411             if (MRegisterInfo::isVirtualRegister(reg)) {
 412                 reg = v2pMap_[reg];
 413             }
 414             prt_.delPhysRegUse(reg);
 415             // add to inactive
 416             inactive_.push_back(*i);
 417             // remove from active
 418             i = active_.erase(i);
 419         }
 420         else {
 421             ++i;
 422         }
 423     }
 424 }
 425
 426 void RA::processInactiveIntervals(IntervalPtrs::value_type cur)
 427 {
 428     DEBUG(std::cerr << "\tprocessing inactive intervals:\n");
 429     for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end();) {
 430         unsigned reg = (*i)->reg;
 431
 432         // remove expired intervals
 433         if ((*i)->expiredAt(cur->start())) {
 434             DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n");
 435             // remove from inactive
 436             i = inactive_.erase(i);
 437         }
 438         // move re-activated intervals in active list
 439         else if ((*i)->liveAt(cur->start())) {
 440             DEBUG(std::cerr << "\t\tinterval " << **i << " active\n");
 441             if (MRegisterInfo::isVirtualRegister(reg)) {
 442                 reg = v2pMap_[reg];
 443             }
 444             prt_.addPhysRegUse(reg);
 445             // add to active
 446             active_.push_back(*i);
 447             // remove from inactive
 448             i = inactive_.erase(i);
 449         }
 450         else {
 451             ++i;
 452         }
 453     }
 454 }
 455
 456 void RA::updateSpillWeights(unsigned reg, SpillWeights::value_type weight)
 457 {
 458     spillWeights_[reg] += weight;
 459     for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as)
 460         spillWeights_[*as] += weight;
 461 }
 462
 463 void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur)
 464 {
 465     DEBUG(std::cerr << "\tallocating current interval: ");
 466
 467     PhysRegTracker backupPrt = prt_;
 468
 469     spillWeights_.assign(mri_->getNumRegs(), 0.0);
 470
 471     // for each interval in active update spill weights
 472     for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
 473          i != e; ++i) {
 474         unsigned reg = (*i)->reg;
 475         if (MRegisterInfo::isVirtualRegister(reg))
 476             reg = v2pMap_[reg];
 477         updateSpillWeights(reg, (*i)->weight);
 478     }
 479
 480     // for every interval in inactive we overlap with, mark the
 481     // register as not free and update spill weights
 482     for (IntervalPtrs::const_iterator i = inactive_.begin(),
 483              e = inactive_.end(); i != e; ++i) {
 484         if (cur->overlaps(**i)) {
 485             unsigned reg = (*i)->reg;
 486             if (MRegisterInfo::isVirtualRegister(reg))
 487                 reg = v2pMap_[reg];
 488             prt_.addPhysRegUse(reg);
 489             updateSpillWeights(reg, (*i)->weight);
 490         }
 491     }
 492
 493     // for every interval in fixed we overlap with,
 494     // mark the register as not free and update spill weights
 495     for (IntervalPtrs::const_iterator i = fixed_.begin(),
 496              e = fixed_.end(); i != e; ++i) {
 497         if (cur->overlaps(**i)) {
 498             unsigned reg = (*i)->reg;
 499             prt_.addPhysRegUse(reg);
 500             updateSpillWeights(reg, (*i)->weight);
 501         }
 502     }
 503
 504     unsigned physReg = getFreePhysReg(cur);
 505     // restore the physical register tracker
 506     prt_ = backupPrt;
 507     // if we find a free register, we are done: assign this virtual to
 508     // the free physical register and add this interval to the active
 509     // list.
 510     if (physReg) {
 511         DEBUG(std::cerr <<  mri_->getName(physReg) << '\n');
 512         assignVirt2PhysReg(cur->reg, physReg);
 513         active_.push_back(cur);
 514         handled_.push_back(cur);
 515         return;
 516     }
 517     DEBUG(std::cerr << "no free registers\n");
 518
 519     DEBUG(std::cerr << "\tassigning stack slot at interval "<< *cur << ":\n");
 520
 521     float minWeight = std::numeric_limits<float>::infinity();
 522     unsigned minReg = 0;
 523     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
 524     for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
 525          i != rc->allocation_order_end(*mf_); ++i) {
 526         unsigned reg = *i;
 527         if (minWeight > spillWeights_[reg]) {
 528             minWeight = spillWeights_[reg];
 529             minReg = reg;
 530         }
 531     }
 532     DEBUG(std::cerr << "\t\tregister with min weight: "
 533           << mri_->getName(minReg) << " (" << minWeight << ")\n");
 534
 535     // if the current has the minimum weight, we need to modify it,
 536     // push it back in unhandled and let the linear scan algorithm run
 537     // again
 538     if (cur->weight <= minWeight) {
 539         DEBUG(std::cerr << "\t\t\tspilling(c): " << *cur << '\n';);
 540         int slot = assignVirt2StackSlot(cur->reg);
 541         li_->updateSpilledInterval(*cur, slot);
 542
 543         // if we didn't eliminate the interval find where to add it
 544         // back to unhandled. We need to scan since unhandled are
 545         // sorted on earliest start point and we may have changed our
 546         // start point.
 547         if (!cur->empty()) {
 548             addSpillCode(cur, slot);
 549             IntervalPtrs::iterator it = unhandled_.begin();
 550             while (it != unhandled_.end() && (*it)->start() < cur->start())
 551                 ++it;
 552             unhandled_.insert(it, cur);
 553         }
 554         return;
 555     }
 556
 557     // push the current interval back to unhandled since we are going
 558     // to re-run at least this iteration. Since we didn't modify it it
 559     // should go back right in the front of the list
 560     unhandled_.push_front(cur);
 561
 562     // otherwise we spill all intervals aliasing the register with
 563     // minimum weight, rollback to the interval with the earliest
 564     // start point and let the linear scan algorithm run again
 565     assert(MRegisterInfo::isPhysicalRegister(minReg) &&
 566            "did not choose a register to spill?");
 567     std::vector<bool> toSpill(mri_->getNumRegs(), false);
 568     toSpill[minReg] = true;
 569     for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as)
 570         toSpill[*as] = true;
 571     unsigned earliestStart = cur->start();
 572
 573     for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
 574         unsigned reg = (*i)->reg;
 575         if (MRegisterInfo::isVirtualRegister(reg) &&
 576             toSpill[v2pMap_[reg]] &&
 577             cur->overlaps(**i)) {
 578             DEBUG(std::cerr << "\t\t\tspilling(a): " << **i << '\n');
 579             earliestStart = std::min(earliestStart, (*i)->start());
 580             int slot = assignVirt2StackSlot((*i)->reg);
 581             li_->updateSpilledInterval(**i, slot);
 582             addSpillCode(*i, slot);
 583         }
 584     }
 585     for (IntervalPtrs::iterator i = inactive_.begin();
 586          i != inactive_.end(); ++i) {
 587         unsigned reg = (*i)->reg;
 588         if (MRegisterInfo::isVirtualRegister(reg) &&
 589             toSpill[v2pMap_[reg]] &&
 590             cur->overlaps(**i)) {
 591             DEBUG(std::cerr << "\t\t\tspilling(i): " << **i << '\n');
 592             earliestStart = std::min(earliestStart, (*i)->start());
 593             int slot = assignVirt2StackSlot((*i)->reg);
 594             li_->updateSpilledInterval(**i, slot);
 595             addSpillCode(*i, slot);
 596         }
 597     }
 598
 599     DEBUG(std::cerr << "\t\trolling back to: " << earliestStart << '\n');
 600     // scan handled in reverse order and undo each one, restoring the
 601     // state of unhandled and fixed
 602     while (!handled_.empty()) {
 603         IntervalPtrs::value_type i = handled_.back();
 604         // if this interval starts before t we are done
 605         if (!i->empty() && i->start() < earliestStart)
 606             break;
 607         DEBUG(std::cerr << "\t\t\tundo changes for: " << *i << '\n');
 608         handled_.pop_back();
 609         IntervalPtrs::iterator it;
 610         if ((it = find(active_.begin(), active_.end(), i)) != active_.end()) {
 611             active_.erase(it);
 612             if (MRegisterInfo::isPhysicalRegister(i->reg)) {
 613                 fixed_.push_front(i);
 614                 prt_.delPhysRegUse(i->reg);
 615             }
 616             else {
 617                 Virt2PhysMap::iterator v2pIt = v2pMap_.find(i->reg);
 618                 clearVirtReg(v2pIt);
 619                 prt_.delPhysRegUse(v2pIt->second);
 620                 if (i->spilled()) {
 621                     if (!i->empty()) {
 622                         IntervalPtrs::iterator it = unhandled_.begin();
 623                         while (it != unhandled_.end() &&
 624                                (*it)->start() < i->start())
 625                             ++it;
 626                         unhandled_.insert(it, i);
 627                     }
 628                 }
 629                 else
 630                     unhandled_.push_front(i);
 631
 632             }
 633         }
 634         else if ((it = find(inactive_.begin(), inactive_.end(), i)) != inactive_.end()) {
 635             inactive_.erase(it);
 636             if (MRegisterInfo::isPhysicalRegister(i->reg))
 637                 fixed_.push_front(i);
 638             else {
 639                 Virt2PhysMap::iterator v2pIt = v2pMap_.find(i->reg);
 640                 clearVirtReg(v2pIt);
 641                 if (i->spilled()) {
 642                     if (!i->empty()) {
 643                         IntervalPtrs::iterator it = unhandled_.begin();
 644                         while (it != unhandled_.end() &&
 645                                (*it)->start() < i->start())
 646                             ++it;
 647                         unhandled_.insert(it, i);
 648                     }
 649                 }
 650                 else
 651                     unhandled_.push_front(i);
 652             }
 653         }
 654         else {
 655             if (MRegisterInfo::isPhysicalRegister(i->reg))
 656                 fixed_.push_front(i);
 657             else {
 658                 Virt2PhysMap::iterator v2pIt = v2pMap_.find(i->reg);
 659                 clearVirtReg(v2pIt);
 660                 unhandled_.push_front(i);
 661             }
 662         }
 663     }
 664
 665     // scan the rest and undo each interval that expired after t and
 666     // insert it in active (the next iteration of the algorithm will
 667     // put it in inactive if required)
 668     IntervalPtrs::iterator i = handled_.begin(), e = handled_.end();
 669     for (; i != e; ++i) {
 670         if (!(*i)->expiredAt(earliestStart) && (*i)->expiredAt(cur->start())) {
 671             DEBUG(std::cerr << "\t\t\tundo changes for: " << **i << '\n');
 672             active_.push_back(*i);
 673             if (MRegisterInfo::isPhysicalRegister((*i)->reg))
 674                 prt_.addPhysRegUse((*i)->reg);
 675             else {
 676                 assert(v2pMap_.count((*i)->reg));
 677                 prt_.addPhysRegUse(v2pMap_.find((*i)->reg)->second);
 678             }
 679         }
 680     }
 681 }
 682
 683 void RA::addSpillCode(IntervalPtrs::value_type li, int slot)
 684 {
 685     // We scan the instructions corresponding to each range. We load
 686     // when we have a use and spill at end of basic blocks or end of
 687     // ranges only if the register was modified.
 688     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(li->reg);
 689
 690     for (LiveIntervals::Interval::Ranges::iterator i = li->ranges.begin(),
 691              e = li->ranges.end(); i != e; ++i) {
 692         unsigned index = i->first;
 693         unsigned end = i->second;
 694
 695         bool loaded = false;
 696
 697         // skip deleted instructions. getInstructionFromIndex returns
 698         // null if the instruction was deleted (because of coalescing
 699         // for example)
 700         while (!li_->getInstructionFromIndex(index))
 701             index += LiveIntervals::InstrSlots::NUM;
 702         MachineBasicBlock::iterator mi = li_->getInstructionFromIndex(index);
 703         MachineBasicBlock* mbb = mi->getParent();
 704         assert(mbb && "machine instruction not bound to basic block");
 705
 706         for (; index < end; index += LiveIntervals::InstrSlots::NUM) {
 707             // ignore deleted instructions
 708             while (!li_->getInstructionFromIndex(index)) index += 2;
 709             mi = li_->getInstructionFromIndex(index);
 710             DEBUG(std::cerr << "\t\t\t\texamining: \t\t\t\t\t"
 711                   << LiveIntervals::getBaseIndex(index) << '\t';
 712                   mi->print(std::cerr, *tm_));
 713
 714             // if it is used in this instruction load it
 715             for (unsigned i = 0; i < mi->getNumOperands(); ++i) {
 716                 MachineOperand& mop = mi->getOperand(i);
 717                 if (mop.isRegister() && mop.getReg() == li->reg &&
 718                     mop.isUse() && !loaded) {
 719                     loaded = true;
 720                     mri_->loadRegFromStackSlot(*mbb, mi, li->reg, slot, rc);
 721                     ++numLoads;
 722                     DEBUG(std::cerr << "\t\t\t\tadded load for reg" << li->reg
 723                           << " from ss#" << slot << " before: \t"
 724                           << LiveIntervals::getBaseIndex(index) << '\t';
 725                           mi->print(std::cerr, *tm_));
 726                 }
 727             }
 728
 729             // if it is defined in this instruction mark as dirty
 730             for (unsigned i = 0; i < mi->getNumOperands(); ++i) {
 731                 MachineOperand& mop = mi->getOperand(i);
 732                 if (mop.isRegister() && mop.getReg() == li->reg &&
 733                     mop.isDef()) {
 734                     loaded = true;
 735
 736                     mri_->storeRegToStackSlot(*mbb, next(mi), li->reg, slot,rc);
 737                     ++numStores;
 738                     DEBUG(std::cerr << "\t\t\t\tadded store for reg" << li->reg
 739                           << " to ss#" << slot << " after: \t\t"
 740                           << LiveIntervals::getBaseIndex(index) << " \t";
 741                           mi->print(std::cerr, *tm_));
 742                 }
 743             }
 744         }
 745     }
 746 }
 747
 748 unsigned RA::getFreePhysReg(IntervalPtrs::value_type cur)
 749 {
 750     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
 751
 752     for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
 753          i != rc->allocation_order_end(*mf_); ++i) {
 754         unsigned reg = *i;
 755         if (prt_.isPhysRegAvail(reg))
 756             return reg;
 757     }
 758     return 0;
 759 }
 760
 761 RA::Virt2PhysMap::iterator
 762 RA::assignVirt2PhysReg(unsigned virtReg, unsigned physReg)
 763 {
 764     bool inserted;
 765     Virt2PhysMap::iterator it;
 766     tie(it, inserted) = v2pMap_.insert(std::make_pair(virtReg, physReg));
 767     assert(inserted && "attempting to assign a virt->phys mapping to an "
 768            "already mapped register");
 769     prt_.addPhysRegUse(physReg);
 770     return it;
 771 }
 772
 773 void RA::clearVirtReg(Virt2PhysMap::iterator it)
 774 {
 775     assert(it != v2pMap_.end() &&
 776            "attempting to clear a not allocated virtual register");
 777     unsigned physReg = it->second;
 778     v2pMap_.erase(it);
 779     DEBUG(std::cerr << "\t\t\tcleared register " << mri_->getName(physReg)
 780           << "\n");
 781 }
 782
 783
 784 int RA::assignVirt2StackSlot(unsigned virtReg)
 785 {
 786     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(virtReg);
 787     int frameIndex = mf_->getFrameInfo()->CreateStackObject(rc);
 788
 789     bool inserted = v2ssMap_.insert(std::make_pair(virtReg, frameIndex)).second;
 790     assert(inserted && "attempt to assign stack slot to spilled register!");
 791     return frameIndex;
 792 }
 793
 794 int RA::getStackSlot(unsigned virtReg)
 795 {
 796     assert(v2ssMap_.count(virtReg) &&
 797            "attempt to get stack slot for a non spilled register");
 798     return v2ssMap_.find(virtReg)->second;
 799 }
 800
 801 FunctionPass* llvm::createLinearScanRegisterAllocator() {
 802     return new RA();
 803 }