lib/CodeGen/RegAllocLinearScan.cpp

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