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