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