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