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