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 using namespace llvm;
  31
  32 namespace {
  33     Statistic<> numSpilled ("ra-linearscan", "Number of registers spilled");
  34     Statistic<> numReloaded("ra-linearscan", "Number of registers reloaded");
  35
  36     class RA : public MachineFunctionPass {
  37     private:
  38         MachineFunction* mf_;
  39         const TargetMachine* tm_;
  40         const MRegisterInfo* mri_;
  41         MachineFunction::iterator currentMbb_;
  42         MachineBasicBlock::iterator currentInstr_;
  43         typedef std::vector<const LiveIntervals::Interval*> IntervalPtrs;
  44         IntervalPtrs unhandled_, fixed_, active_, inactive_;
  45
  46         typedef std::vector<unsigned> Regs;
  47         Regs tempUseOperands_;
  48         Regs tempDefOperands_;
  49
  50         typedef std::vector<bool> RegMask;
  51         RegMask reserved_;
  52
  53         unsigned regUse_[MRegisterInfo::FirstVirtualRegister];
  54         unsigned regUseBackup_[MRegisterInfo::FirstVirtualRegister];
  55
  56         typedef std::map<unsigned, unsigned> Virt2PhysMap;
  57         Virt2PhysMap v2pMap_;
  58
  59         typedef std::map<unsigned, int> Virt2StackSlotMap;
  60         Virt2StackSlotMap v2ssMap_;
  61
  62         int instrAdded_;
  63
  64     public:
  65         virtual const char* getPassName() const {
  66             return "Linear Scan Register Allocator";
  67         }
  68
  69         virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  70             AU.addRequired<LiveVariables>();
  71             AU.addRequired<LiveIntervals>();
  72             MachineFunctionPass::getAnalysisUsage(AU);
  73         }
  74
  75     private:
  76         /// runOnMachineFunction - register allocate the whole function
  77         bool runOnMachineFunction(MachineFunction&);
  78
  79         /// initIntervalSets - initializa the four interval sets:
  80         /// unhandled, fixed, active and inactive
  81         void initIntervalSets(const LiveIntervals::Intervals& li);
  82
  83         /// processActiveIntervals - expire old intervals and move
  84         /// non-overlapping ones to the incative list
  85         void processActiveIntervals(IntervalPtrs::value_type cur);
  86
  87         /// processInactiveIntervals - expire old intervals and move
  88         /// overlapping ones to the active list
  89         void processInactiveIntervals(IntervalPtrs::value_type cur);
  90
  91         /// assignStackSlotAtInterval - choose and spill
  92         /// interval. Currently we spill the interval with the last
  93         /// end point in the active and inactive lists and the current
  94         /// interval
  95         void assignStackSlotAtInterval(IntervalPtrs::value_type cur);
  96
  97         ///
  98         /// register handling helpers
  99         ///
 100
 101         /// getFreePhysReg - return a free physical register for this
 102         /// virtual register interval if we have one, otherwise return
 103         /// 0
 104         unsigned getFreePhysReg(IntervalPtrs::value_type cur);
 105
 106         /// physRegAvailable - returns true if the specifed physical
 107         /// register is available
 108         bool physRegAvailable(unsigned physReg);
 109
 110         /// tempPhysRegAvailable - returns true if the specifed
 111         /// temporary physical register is available
 112         bool tempPhysRegAvailable(unsigned physReg);
 113
 114         /// getFreeTempPhysReg - return a free temprorary physical
 115         /// register for this virtual register if we have one (should
 116         /// never return 0)
 117         unsigned getFreeTempPhysReg(unsigned virtReg);
 118
 119         /// assignVirt2PhysReg - assigns the free physical register to
 120         /// the virtual register passed as arguments
 121         void assignVirt2PhysReg(unsigned virtReg, unsigned physReg);
 122
 123         /// clearVirtReg - free the physical register associated with this
 124         /// virtual register and disassociate virtual->physical and
 125         /// physical->virtual mappings
 126         void clearVirtReg(unsigned virtReg);
 127
 128         /// assignVirt2StackSlot - assigns this virtual register to a
 129         /// stack slot
 130         void assignVirt2StackSlot(unsigned virtReg);
 131
 132         /// getStackSlot - returns the offset of the specified
 133         /// register on the stack
 134         int getStackSlot(unsigned virtReg);
 135
 136         /// spillVirtReg - spills the virtual register
 137         void spillVirtReg(unsigned virtReg);
 138
 139         /// loadPhysReg - loads to the physical register the value of
 140         /// the virtual register specifed. Virtual register must have
 141         /// an assigned stack slot
 142         void loadVirt2PhysReg(unsigned virtReg, unsigned physReg);
 143
 144         void markPhysRegFree(unsigned physReg);
 145         void markPhysRegNotFree(unsigned physReg);
 146
 147         void backupRegUse() {
 148             memcpy(regUseBackup_, regUse_, sizeof(regUseBackup_));
 149         }
 150
 151         void restoreRegUse() {
 152             memcpy(regUse_, regUseBackup_, sizeof(regUseBackup_));
 153         }
 154
 155         void printVirt2PhysMap() const {
 156             std::cerr << "allocated registers:\n";
 157             for (Virt2PhysMap::const_iterator
 158                      i = v2pMap_.begin(), e = v2pMap_.end(); i != e; ++i) {
 159                 std::cerr << '[' << i->first << ','
 160                           << mri_->getName(i->second) << "]\n";
 161             }
 162             std::cerr << '\n';
 163         }
 164         void printIntervals(const char* const str,
 165                             RA::IntervalPtrs::const_iterator i,
 166                             RA::IntervalPtrs::const_iterator e) const {
 167             if (str) std::cerr << str << " intervals:\n";
 168             for (; i != e; ++i) {
 169                 std::cerr << "\t\t" << **i << " -> ";
 170                 if ((*i)->reg < MRegisterInfo::FirstVirtualRegister) {
 171                     std::cerr << mri_->getName((*i)->reg);
 172                 }
 173                 else {
 174                     std::cerr << mri_->getName(v2pMap_.find((*i)->reg)->second);
 175                 }
 176                 std::cerr << '\n';
 177             }
 178         }
 179         void printFreeRegs(const char* const str,
 180                            const TargetRegisterClass* rc) const {
 181             if (str) std::cerr << str << ':';
 182             for (TargetRegisterClass::iterator i =
 183                      rc->allocation_order_begin(*mf_);
 184                 i != rc->allocation_order_end(*mf_); ++i) {
 185                 unsigned reg = *i;
 186                 if (!regUse_[reg]) {
 187                     std::cerr << ' ' << mri_->getName(reg);
 188                     if (reserved_[reg]) std::cerr << "*";
 189                 }
 190             }
 191             std::cerr << '\n';
 192         }
 193     };
 194 }
 195
 196 bool RA::runOnMachineFunction(MachineFunction &fn) {
 197     mf_ = &fn;
 198     tm_ = &fn.getTarget();
 199     mri_ = tm_->getRegisterInfo();
 200
 201     initIntervalSets(getAnalysis<LiveIntervals>().getIntervals());
 202
 203     v2pMap_.clear();
 204     v2ssMap_.clear();
 205     memset(regUse_, 0, sizeof(regUse_));
 206     memset(regUseBackup_, 0, sizeof(regUseBackup_));
 207
 208     // FIXME: this will work only for the X86 backend. I need to
 209     // device an algorthm to select the minimal (considering register
 210     // aliasing) number of temp registers to reserve so that we have 2
 211     // registers for each register class available.
 212
 213     // reserve R8:   CH,  CL
 214     //         R16:  CX,  DI,
 215     //         R32: ECX, EDI,
 216     //         RFP: FP5, FP6
 217     reserved_.assign(MRegisterInfo::FirstVirtualRegister, false);
 218     reserved_[ 8] = true; /*  CH */
 219     reserved_[ 9] = true; /*  CL */
 220     reserved_[10] = true; /*  CX */
 221     reserved_[12] = true; /*  DI */
 222     reserved_[18] = true; /* ECX */
 223     reserved_[19] = true; /* EDI */
 224     reserved_[28] = true; /* FP5 */
 225     reserved_[29] = true; /* FP6 */
 226
 227     // linear scan algorithm
 228
 229     DEBUG(printIntervals("\tunhandled", unhandled_.begin(), unhandled_.end()));
 230     DEBUG(printIntervals("\tfixed", fixed_.begin(), fixed_.end()));
 231     DEBUG(printIntervals("\tactive", active_.begin(), active_.end()));
 232     DEBUG(printIntervals("\tinactive", inactive_.begin(), inactive_.end()));
 233
 234     while (!unhandled_.empty() || !fixed_.empty()) {
 235         // pick the interval with the earliest start point
 236         IntervalPtrs::value_type cur;
 237         if (fixed_.empty()) {
 238             cur = unhandled_.front();
 239             unhandled_.erase(unhandled_.begin());
 240         }
 241         else if (unhandled_.empty()) {
 242             cur = fixed_.front();
 243             fixed_.erase(fixed_.begin());
 244         }
 245         else if (unhandled_.front()->start() < fixed_.front()->start()) {
 246             cur = unhandled_.front();
 247             unhandled_.erase(unhandled_.begin());
 248         }
 249         else {
 250             cur = fixed_.front();
 251             fixed_.erase(fixed_.begin());
 252         }
 253
 254         DEBUG(std::cerr << "processing current interval: " << *cur << '\n');
 255
 256         processActiveIntervals(cur);
 257         processInactiveIntervals(cur);
 258
 259         // if this register is fixed we are done
 260         if (cur->reg < MRegisterInfo::FirstVirtualRegister) {
 261             markPhysRegNotFree(cur->reg);
 262             active_.push_back(cur);
 263         }
 264         // otherwise we are allocating a virtual register. try to find
 265         // a free physical register or spill an interval in order to
 266         // assign it one (we could spill the current though).
 267         else {
 268             backupRegUse();
 269
 270             // for every interval in inactive we overlap with, mark the
 271             // register as not free
 272             for (IntervalPtrs::const_iterator i = inactive_.begin(),
 273                      e = inactive_.end(); i != e; ++i) {
 274                 unsigned reg = (*i)->reg;
 275                 if (reg >= MRegisterInfo::FirstVirtualRegister)
 276                     reg = v2pMap_[reg];
 277
 278                 if (cur->overlaps(**i)) {
 279                     markPhysRegNotFree(reg);
 280                 }
 281             }
 282
 283             // for every interval in fixed we overlap with,
 284             // mark the register as not free
 285             for (IntervalPtrs::const_iterator i = fixed_.begin(),
 286                      e = fixed_.end(); i != e; ++i) {
 287                 assert((*i)->reg < MRegisterInfo::FirstVirtualRegister &&
 288                        "virtual register interval in fixed set?");
 289                 if (cur->overlaps(**i))
 290                     markPhysRegNotFree((*i)->reg);
 291             }
 292
 293             DEBUG(std::cerr << "\tallocating current interval:\n");
 294
 295             unsigned physReg = getFreePhysReg(cur);
 296             if (!physReg) {
 297                 assignStackSlotAtInterval(cur);
 298             }
 299             else {
 300                 restoreRegUse();
 301                 assignVirt2PhysReg(cur->reg, physReg);
 302                 active_.push_back(cur);
 303             }
 304         }
 305
 306         DEBUG(printIntervals("\tactive", active_.begin(), active_.end()));
 307         DEBUG(printIntervals("\tinactive", inactive_.begin(), inactive_.end()));    }
 308
 309     // expire any remaining active intervals
 310     for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
 311         unsigned reg = (*i)->reg;
 312         DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n");
 313         if (reg >= MRegisterInfo::FirstVirtualRegister) {
 314             reg = v2pMap_[reg];
 315         }
 316         markPhysRegFree(reg);
 317     }
 318     active_.clear();
 319     inactive_.clear();
 320
 321     DEBUG(std::cerr << "finished register allocation\n");
 322     DEBUG(printVirt2PhysMap());
 323
 324     DEBUG(std::cerr << "Rewrite machine code:\n");
 325     for (currentMbb_ = mf_->begin(); currentMbb_ != mf_->end(); ++currentMbb_) {
 326         instrAdded_ = 0;
 327
 328         for (currentInstr_ = currentMbb_->begin();
 329              currentInstr_ != currentMbb_->end(); ++currentInstr_) {
 330
 331             DEBUG(std::cerr << "\tinstruction: ";
 332                   (*currentInstr_)->print(std::cerr, *tm_););
 333
 334             // use our current mapping and actually replace and
 335             // virtual register with its allocated physical registers
 336             DEBUG(std::cerr << "\t\treplacing virtual registers with mapped "
 337                   "physical registers:\n");
 338             for (unsigned i = 0, e = (*currentInstr_)->getNumOperands();
 339                  i != e; ++i) {
 340                 MachineOperand& op = (*currentInstr_)->getOperand(i);
 341                 if (op.isVirtualRegister()) {
 342                     unsigned virtReg = op.getAllocatedRegNum();
 343                     unsigned physReg = v2pMap_[virtReg];
 344                     if (physReg) {
 345                         DEBUG(std::cerr << "\t\t\t%reg" << virtReg
 346                               << " -> " << mri_->getName(physReg) << '\n');
 347                         (*currentInstr_)->SetMachineOperandReg(i, physReg);
 348                     }
 349                 }
 350             }
 351
 352             DEBUG(std::cerr << "\t\tloading temporarily used operands to "
 353                   "registers:\n");
 354             for (unsigned i = 0, e = (*currentInstr_)->getNumOperands();
 355                  i != e; ++i) {
 356                 MachineOperand& op = (*currentInstr_)->getOperand(i);
 357                 if (op.isVirtualRegister() && op.isUse() && !op.isDef()) {
 358                     unsigned virtReg = op.getAllocatedRegNum();
 359                     unsigned physReg = v2pMap_[virtReg];
 360                     if (!physReg) {
 361                         physReg = getFreeTempPhysReg(virtReg);
 362                         loadVirt2PhysReg(virtReg, physReg);
 363                         tempUseOperands_.push_back(virtReg);
 364                     }
 365                     (*currentInstr_)->SetMachineOperandReg(i, physReg);
 366                 }
 367             }
 368
 369             DEBUG(std::cerr << "\t\tclearing temporarily used operands:\n");
 370             for (unsigned i = 0, e = tempUseOperands_.size(); i != e; ++i) {
 371                 clearVirtReg(tempUseOperands_[i]);
 372             }
 373             tempUseOperands_.clear();
 374
 375             DEBUG(std::cerr << "\t\tassigning temporarily defined operands to "
 376                   "registers:\n");
 377             for (unsigned i = 0, e = (*currentInstr_)->getNumOperands();
 378                  i != e; ++i) {
 379                 MachineOperand& op = (*currentInstr_)->getOperand(i);
 380                 if (op.isVirtualRegister() && op.isDef()) {
 381                     unsigned virtReg = op.getAllocatedRegNum();
 382                     unsigned physReg = v2pMap_[virtReg];
 383                     if (!physReg) {
 384                         physReg = getFreeTempPhysReg(virtReg);
 385                     }
 386                     if (op.isUse()) { // def and use
 387                         loadVirt2PhysReg(virtReg, physReg);
 388                     }
 389                     else {
 390                         assignVirt2PhysReg(virtReg, physReg);
 391                     }
 392                     tempDefOperands_.push_back(virtReg);
 393                     (*currentInstr_)->SetMachineOperandReg(i, physReg);
 394                 }
 395             }
 396
 397             DEBUG(std::cerr << "\t\tspilling temporarily defined operands "
 398                   "of this instruction:\n");
 399             ++currentInstr_; // we want to insert after this instruction
 400             for (unsigned i = 0, e = tempDefOperands_.size(); i != e; ++i) {
 401                 spillVirtReg(tempDefOperands_[i]);
 402             }
 403             --currentInstr_; // restore currentInstr_ iterator
 404             tempDefOperands_.clear();
 405         }
 406     }
 407
 408     return true;
 409 }
 410
 411 void RA::initIntervalSets(const LiveIntervals::Intervals& li)
 412 {
 413     assert(unhandled_.empty() && fixed_.empty() &&
 414            active_.empty() && inactive_.empty() &&
 415            "interval sets should be empty on initialization");
 416
 417     for (LiveIntervals::Intervals::const_iterator i = li.begin(), e = li.end();
 418          i != e; ++i) {
 419         if (i->reg < MRegisterInfo::FirstVirtualRegister)
 420             fixed_.push_back(&*i);
 421         else
 422             unhandled_.push_back(&*i);
 423     }
 424 }
 425
 426 void RA::processActiveIntervals(IntervalPtrs::value_type cur)
 427 {
 428     DEBUG(std::cerr << "\tprocessing active intervals:\n");
 429     for (IntervalPtrs::iterator i = active_.begin(); i != active_.end();) {
 430         unsigned reg = (*i)->reg;
 431         // remove expired intervals. we expire earlier because this if
 432         // an interval expires this is going to be the last use. in
 433         // this case we can reuse the register for a def in the same
 434         // instruction
 435         if ((*i)->expiredAt(cur->start() + 1)) {
 436             DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n");
 437             if (reg >= MRegisterInfo::FirstVirtualRegister) {
 438                 reg = v2pMap_[reg];
 439             }
 440             markPhysRegFree(reg);
 441             // remove from active
 442             i = active_.erase(i);
 443         }
 444         // move inactive intervals to inactive list
 445         else if (!(*i)->liveAt(cur->start())) {
 446             DEBUG(std::cerr << "\t\t\tinterval " << **i << " inactive\n");
 447             if (reg >= MRegisterInfo::FirstVirtualRegister) {
 448                 reg = v2pMap_[reg];
 449             }
 450             markPhysRegFree(reg);
 451             // add to inactive
 452             inactive_.push_back(*i);
 453             // remove from active
 454             i = active_.erase(i);
 455         }
 456         else {
 457             ++i;
 458         }
 459     }
 460 }
 461
 462 void RA::processInactiveIntervals(IntervalPtrs::value_type cur)
 463 {
 464     DEBUG(std::cerr << "\tprocessing inactive intervals:\n");
 465     for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end();) {
 466         unsigned reg = (*i)->reg;
 467
 468         // remove expired intervals. we expire earlier because this if
 469         // an interval expires this is going to be the last use. in
 470         // this case we can reuse the register for a def in the same
 471         // instruction
 472         if ((*i)->expiredAt(cur->start() + 1)) {
 473             DEBUG(std::cerr << "\t\t\tinterval " << **i << " expired\n");
 474             // remove from inactive
 475             i = inactive_.erase(i);
 476         }
 477         // move re-activated intervals in active list
 478         else if ((*i)->liveAt(cur->start())) {
 479             DEBUG(std::cerr << "\t\t\tinterval " << **i << " active\n");
 480             if (reg >= MRegisterInfo::FirstVirtualRegister) {
 481                 reg = v2pMap_[reg];
 482             }
 483             markPhysRegNotFree(reg);
 484             // add to active
 485             active_.push_back(*i);
 486             // remove from inactive
 487             i = inactive_.erase(i);
 488         }
 489         else {
 490             ++i;
 491         }
 492     }
 493 }
 494
 495 namespace {
 496     template <typename T>
 497     void updateWeight(T rw[], int reg, T w)
 498     {
 499         if (rw[reg] == std::numeric_limits<T>::max() ||
 500             w == std::numeric_limits<T>::max())
 501             rw[reg] = std::numeric_limits<T>::max();
 502         else
 503             rw[reg] += w;
 504     }
 505 }
 506
 507 void RA::assignStackSlotAtInterval(IntervalPtrs::value_type cur)
 508 {
 509     DEBUG(std::cerr << "\t\tassigning stack slot at interval "
 510           << *cur << ":\n");
 511
 512     // set all weights to zero
 513     float regWeight[MRegisterInfo::FirstVirtualRegister];
 514     for (unsigned i = 0; i < MRegisterInfo::FirstVirtualRegister; ++i)
 515         regWeight[i] = 0.0F;
 516
 517     // for each interval in active that overlaps
 518     for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
 519          i != e; ++i) {
 520          if (!cur->overlaps(**i))
 521              continue;
 522
 523         unsigned reg = (*i)->reg;
 524         if (reg >= MRegisterInfo::FirstVirtualRegister) {
 525             reg = v2pMap_[reg];
 526         }
 527         updateWeight(regWeight, reg, (*i)->weight);
 528         for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as)
 529             updateWeight(regWeight, *as, (*i)->weight);
 530     }
 531
 532     // for each interval in inactive that overlaps
 533     for (IntervalPtrs::const_iterator i = inactive_.begin(),
 534              e = inactive_.end(); i != e; ++i) {
 535          if (!cur->overlaps(**i))
 536              continue;
 537
 538         unsigned reg = (*i)->reg;
 539         if (reg >= MRegisterInfo::FirstVirtualRegister) {
 540             reg = v2pMap_[reg];
 541         }
 542         updateWeight(regWeight, reg, (*i)->weight);
 543         for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as)
 544             updateWeight(regWeight, *as, (*i)->weight);
 545     }
 546
 547     // for each fixed interval that overlaps
 548     for (IntervalPtrs::const_iterator i = fixed_.begin(), e = fixed_.end();
 549          i != e; ++i) {
 550         assert((*i)->reg < MRegisterInfo::FirstVirtualRegister &&
 551                "virtual register interval in fixed set?");
 552         updateWeight(regWeight, (*i)->reg, (*i)->weight);
 553         for (const unsigned* as = mri_->getAliasSet((*i)->reg); *as; ++as)
 554             updateWeight(regWeight, *as, (*i)->weight);
 555     }
 556
 557     float minWeight = std::numeric_limits<float>::max();
 558     unsigned minReg = 0;
 559     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
 560     for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
 561          i != rc->allocation_order_end(*mf_); ++i) {
 562         unsigned reg = *i;
 563         if (!reserved_[reg] && minWeight > regWeight[reg]) {
 564             minWeight = regWeight[reg];
 565             minReg = reg;
 566         }
 567     }
 568
 569     if (cur->weight < minWeight) {
 570         restoreRegUse();
 571         DEBUG(std::cerr << "\t\t\t\tspilling : " << *cur << '\n');
 572         assignVirt2StackSlot(cur->reg);
 573     }
 574     else {
 575         std::set<unsigned> toSpill;
 576         toSpill.insert(minReg);
 577         for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as)
 578             toSpill.insert(*as);
 579
 580         std::vector<unsigned> spilled;
 581         for (IntervalPtrs::iterator i = active_.begin();
 582              i != active_.end(); ) {
 583             unsigned reg = (*i)->reg;
 584             if (reg >= MRegisterInfo::FirstVirtualRegister &&
 585                 toSpill.find(v2pMap_[reg]) != toSpill.end() &&
 586                 cur->overlaps(**i)) {
 587                 spilled.push_back(v2pMap_[reg]);
 588                 DEBUG(std::cerr << "\t\t\t\tspilling : " << **i << '\n');
 589                 assignVirt2StackSlot(reg);
 590                 i = active_.erase(i);
 591             }
 592             else {
 593                 ++i;
 594             }
 595         }
 596         for (IntervalPtrs::iterator i = inactive_.begin();
 597              i != inactive_.end(); ) {
 598             unsigned reg = (*i)->reg;
 599             if (reg >= MRegisterInfo::FirstVirtualRegister &&
 600                 toSpill.find(v2pMap_[reg]) != toSpill.end() &&
 601                 cur->overlaps(**i)) {
 602                 DEBUG(std::cerr << "\t\t\t\tspilling : " << **i << '\n');
 603                 assignVirt2StackSlot(reg);
 604                 i = inactive_.erase(i);
 605             }
 606             else {
 607                 ++i;
 608             }
 609         }
 610
 611         unsigned physReg = getFreePhysReg(cur);
 612         assert(physReg && "no free physical register after spill?");
 613
 614         restoreRegUse();
 615         for (unsigned i = 0; i < spilled.size(); ++i)
 616             markPhysRegFree(spilled[i]);
 617
 618         assignVirt2PhysReg(cur->reg, physReg);
 619         active_.push_back(cur);
 620     }
 621 }
 622
 623 bool RA::physRegAvailable(unsigned physReg)
 624 {
 625     assert(!reserved_[physReg] &&
 626            "cannot call this method with a reserved register");
 627
 628     return !regUse_[physReg];
 629 }
 630
 631 unsigned RA::getFreePhysReg(IntervalPtrs::value_type cur)
 632 {
 633     DEBUG(std::cerr << "\t\tgetting free physical register: ");
 634     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
 635
 636     for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
 637          i != rc->allocation_order_end(*mf_); ++i) {
 638         unsigned reg = *i;
 639         if (!reserved_[reg] && !regUse_[reg]) {
 640             DEBUG(std::cerr << mri_->getName(reg) << '\n');
 641             return reg;
 642         }
 643     }
 644
 645     DEBUG(std::cerr << "no free register\n");
 646     return 0;
 647 }
 648
 649 bool RA::tempPhysRegAvailable(unsigned physReg)
 650 {
 651     assert(reserved_[physReg] &&
 652            "cannot call this method with a not reserved temp register");
 653
 654     return !regUse_[physReg];
 655 }
 656
 657 unsigned RA::getFreeTempPhysReg(unsigned virtReg)
 658 {
 659     DEBUG(std::cerr << "\t\tgetting free temporary physical register: ");
 660
 661     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(virtReg);
 662     // go in reverse allocation order for the temp registers
 663     for (TargetRegisterClass::iterator i = rc->allocation_order_end(*mf_) - 1;
 664          i != rc->allocation_order_begin(*mf_) - 1; --i) {
 665         unsigned reg = *i;
 666         if (reserved_[reg] && !regUse_[reg]) {
 667             DEBUG(std::cerr << mri_->getName(reg) << '\n');
 668             return reg;
 669         }
 670     }
 671
 672     assert(0 && "no free temporary physical register?");
 673     return 0;
 674 }
 675
 676 void RA::assignVirt2PhysReg(unsigned virtReg, unsigned physReg)
 677 {
 678     v2pMap_[virtReg] = physReg;
 679     markPhysRegNotFree(physReg);
 680 }
 681
 682 void RA::clearVirtReg(unsigned virtReg)
 683 {
 684     Virt2PhysMap::iterator it = v2pMap_.find(virtReg);
 685     assert(it != v2pMap_.end() &&
 686            "attempting to clear a not allocated virtual register");
 687     unsigned physReg = it->second;
 688     markPhysRegFree(physReg);
 689     v2pMap_[virtReg] = 0; // this marks that this virtual register
 690                           // lives on the stack
 691     DEBUG(std::cerr << "\t\t\tcleared register " << mri_->getName(physReg)
 692           << "\n");
 693 }
 694
 695 void RA::assignVirt2StackSlot(unsigned virtReg)
 696 {
 697     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(virtReg);
 698     int frameIndex = mf_->getFrameInfo()->CreateStackObject(rc);
 699
 700     bool inserted = v2ssMap_.insert(std::make_pair(virtReg, frameIndex)).second;
 701     assert(inserted &&
 702            "attempt to assign stack slot to already assigned register?");
 703     // if the virtual register was previously assigned clear the mapping
 704     // and free the virtual register
 705     if (v2pMap_.find(virtReg) != v2pMap_.end()) {
 706         clearVirtReg(virtReg);
 707     }
 708     else {
 709         v2pMap_[virtReg] = 0; // this marks that this virtual register
 710                               // lives on the stack
 711     }
 712 }
 713
 714 int RA::getStackSlot(unsigned virtReg)
 715 {
 716     // use lower_bound so that we can do a possibly O(1) insert later
 717     // if necessary
 718     Virt2StackSlotMap::iterator it = v2ssMap_.find(virtReg);
 719     assert(it != v2ssMap_.end() &&
 720            "attempt to get stack slot on register that does not live on the stack");
 721     return it->second;
 722 }
 723
 724 void RA::spillVirtReg(unsigned virtReg)
 725 {
 726     DEBUG(std::cerr << "\t\t\tspilling register: " << virtReg);
 727     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(virtReg);
 728     int frameIndex = getStackSlot(virtReg);
 729     DEBUG(std::cerr << " to stack slot #" << frameIndex << '\n');
 730     ++numSpilled;
 731     instrAdded_ += mri_->storeRegToStackSlot(*currentMbb_, currentInstr_,
 732                                              v2pMap_[virtReg], frameIndex, rc);
 733     clearVirtReg(virtReg);
 734 }
 735
 736 void RA::loadVirt2PhysReg(unsigned virtReg, unsigned physReg)
 737 {
 738     DEBUG(std::cerr << "\t\t\tloading register: " << virtReg);
 739     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(virtReg);
 740     int frameIndex = getStackSlot(virtReg);
 741     DEBUG(std::cerr << " from stack slot #" << frameIndex << '\n');
 742     ++numReloaded;
 743     instrAdded_ += mri_->loadRegFromStackSlot(*currentMbb_, currentInstr_,
 744                                               physReg, frameIndex, rc);
 745     assignVirt2PhysReg(virtReg, physReg);
 746 }
 747
 748 void RA::markPhysRegFree(unsigned physReg)
 749 {
 750     assert(regUse_[physReg] != 0);
 751     --regUse_[physReg];
 752     for (const unsigned* as = mri_->getAliasSet(physReg); *as; ++as) {
 753         physReg = *as;
 754         assert(regUse_[physReg] != 0);
 755         --regUse_[physReg];
 756     }
 757 }
 758
 759 void RA::markPhysRegNotFree(unsigned physReg)
 760 {
 761     ++regUse_[physReg];
 762     for (const unsigned* as = mri_->getAliasSet(physReg); *as; ++as) {
 763         physReg = *as;
 764         ++regUse_[physReg];
 765     }
 766 }
 767
 768 FunctionPass* llvm::createLinearScanRegisterAllocator() {
 769     return new RA();
 770 }