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