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. we expire earlier because this if
 432         // an interval expires this is going to be the last use. in
 433         // this case we can reuse the register for a def in the same
 434         // instruction
 435         if ((*i)->expiredAt(cur->start() + 1)) {
 436             DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n");
 437             if (reg >= MRegisterInfo::FirstVirtualRegister) {
 438                 reg = v2pMap_[reg];
 439             }
 440             markPhysRegFree(reg);
 441             // remove from active
 442             i = active_.erase(i);
 443         }
 444         // move inactive intervals to inactive list
 445         else if (!(*i)->liveAt(cur->start())) {
 446             DEBUG(std::cerr << "\t\t\tinterval " << **i << " inactive\n");
 447             if (reg >= MRegisterInfo::FirstVirtualRegister) {
 448                 reg = v2pMap_[reg];
 449             }
 450             markPhysRegFree(reg);
 451             // add to inactive
 452             inactive_.push_back(*i);
 453             // remove from active
 454             i = active_.erase(i);
 455         }
 456         else {
 457             ++i;
 458         }
 459     }
 460 }
 461
 462 void RA::processInactiveIntervals(IntervalPtrs::value_type cur)
 463 {
 464     DEBUG(std::cerr << "\tprocessing inactive intervals:\n");
 465     for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end();) {
 466         unsigned reg = (*i)->reg;
 467
 468         // remove expired intervals. we expire earlier because this if
 469         // an interval expires this is going to be the last use. in
 470         // this case we can reuse the register for a def in the same
 471         // instruction
 472         if ((*i)->expiredAt(cur->start() + 1)) {
 473             DEBUG(std::cerr << "\t\t\tinterval " << **i << " expired\n");
 474             // remove from inactive
 475             i = inactive_.erase(i);
 476         }
 477         // move re-activated intervals in active list
 478         else if ((*i)->liveAt(cur->start())) {
 479             DEBUG(std::cerr << "\t\t\tinterval " << **i << " active\n");
 480             if (reg >= MRegisterInfo::FirstVirtualRegister) {
 481                 reg = v2pMap_[reg];
 482             }
 483             markPhysRegNotFree(reg);
 484             // add to active
 485             active_.push_back(*i);
 486             // remove from inactive
 487             i = inactive_.erase(i);
 488         }
 489         else {
 490             ++i;
 491         }
 492     }
 493 }
 494
 495 namespace {
 496     template <typename T>
 497     void updateWeight(T rw[], int reg, T w)
 498     {
 499         if (rw[reg] == std::numeric_limits<T>::max() ||
 500             w == std::numeric_limits<T>::max())
 501             rw[reg] = std::numeric_limits<T>::max();
 502         else
 503             rw[reg] += w;
 504     }
 505 }
 506
 507 void RA::assignStackSlotAtInterval(IntervalPtrs::value_type cur)
 508 {
 509     DEBUG(std::cerr << "\t\tassigning stack slot at interval "
 510           << *cur << ":\n");
 511
 512     // set all weights to zero
 513     float regWeight[MRegisterInfo::FirstVirtualRegister];
 514     for (unsigned i = 0; i < MRegisterInfo::FirstVirtualRegister; ++i)
 515         regWeight[i] = 0.0F;
 516
 517     // for each interval in active that overlaps
 518     for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
 519          i != e; ++i) {
 520         if (!cur->overlaps(**i))
 521             continue;
 522
 523         unsigned reg = (*i)->reg;
 524         if (reg >= MRegisterInfo::FirstVirtualRegister) {
 525             reg = v2pMap_[reg];
 526         }
 527         updateWeight(regWeight, reg, (*i)->weight);
 528         for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as)
 529             updateWeight(regWeight, *as, (*i)->weight);
 530     }
 531
 532     // for each interval in inactive that overlaps
 533     for (IntervalPtrs::const_iterator i = inactive_.begin(),
 534              e = inactive_.end(); i != e; ++i) {
 535         if (!cur->overlaps(**i))
 536             continue;
 537
 538         unsigned reg = (*i)->reg;
 539         if (reg >= MRegisterInfo::FirstVirtualRegister) {
 540             reg = v2pMap_[reg];
 541         }
 542         updateWeight(regWeight, reg, (*i)->weight);
 543         for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as)
 544             updateWeight(regWeight, *as, (*i)->weight);
 545     }
 546
 547     // for each fixed interval that overlaps
 548     for (IntervalPtrs::const_iterator i = fixed_.begin(), e = fixed_.end();
 549          i != e; ++i) {
 550         if (!cur->overlaps(**i))
 551             continue;
 552
 553         assert((*i)->reg < MRegisterInfo::FirstVirtualRegister &&
 554                "virtual register interval in fixed set?");
 555         updateWeight(regWeight, (*i)->reg, (*i)->weight);
 556         for (const unsigned* as = mri_->getAliasSet((*i)->reg); *as; ++as)
 557             updateWeight(regWeight, *as, (*i)->weight);
 558     }
 559
 560     float minWeight = std::numeric_limits<float>::max();
 561     unsigned minReg = 0;
 562     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
 563     for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
 564          i != rc->allocation_order_end(*mf_); ++i) {
 565         unsigned reg = *i;
 566         if (!reserved_[reg] && minWeight > regWeight[reg]) {
 567             minWeight = regWeight[reg];
 568             minReg = reg;
 569         }
 570     }
 571
 572     if (cur->weight < minWeight) {
 573         restoreRegUse();
 574         DEBUG(std::cerr << "\t\t\t\tspilling: " << *cur << '\n');
 575         assignVirt2StackSlot(cur->reg);
 576     }
 577     else {
 578         DEBUG(std::cerr << "\t\t\t\tfreeing: " << mri_->getName(minReg) << '\n');
 579         std::set<unsigned> toSpill;
 580         toSpill.insert(minReg);
 581         for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as)
 582             toSpill.insert(*as);
 583
 584         std::vector<unsigned> spilled;
 585         for (IntervalPtrs::iterator i = active_.begin();
 586              i != active_.end(); ) {
 587             unsigned reg = (*i)->reg;
 588             if (reg >= MRegisterInfo::FirstVirtualRegister &&
 589                 toSpill.find(v2pMap_[reg]) != toSpill.end() &&
 590                 cur->overlaps(**i)) {
 591                 spilled.push_back(v2pMap_[reg]);
 592                 DEBUG(std::cerr << "\t\t\t\tspilling : " << **i << '\n');
 593                 assignVirt2StackSlot(reg);
 594                 i = active_.erase(i);
 595             }
 596             else {
 597                 ++i;
 598             }
 599         }
 600         for (IntervalPtrs::iterator i = inactive_.begin();
 601              i != inactive_.end(); ) {
 602             unsigned reg = (*i)->reg;
 603             if (reg >= MRegisterInfo::FirstVirtualRegister &&
 604                 toSpill.find(v2pMap_[reg]) != toSpill.end() &&
 605                 cur->overlaps(**i)) {
 606                 DEBUG(std::cerr << "\t\t\t\tspilling : " << **i << '\n');
 607                 assignVirt2StackSlot(reg);
 608                 i = inactive_.erase(i);
 609             }
 610             else {
 611                 ++i;
 612             }
 613         }
 614
 615         unsigned physReg = getFreePhysReg(cur);
 616         assert(physReg && "no free physical register after spill?");
 617
 618         restoreRegUse();
 619         for (unsigned i = 0; i < spilled.size(); ++i)
 620             markPhysRegFree(spilled[i]);
 621
 622         assignVirt2PhysReg(cur->reg, physReg);
 623         active_.push_back(cur);
 624     }
 625 }
 626
 627 bool RA::physRegAvailable(unsigned physReg)
 628 {
 629     assert(!reserved_[physReg] &&
 630            "cannot call this method with a reserved register");
 631
 632     return !regUse_[physReg];
 633 }
 634
 635 unsigned RA::getFreePhysReg(IntervalPtrs::value_type cur)
 636 {
 637     DEBUG(std::cerr << "\t\tgetting free physical register: ");
 638     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
 639
 640     for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
 641          i != rc->allocation_order_end(*mf_); ++i) {
 642         unsigned reg = *i;
 643         if (!reserved_[reg] && !regUse_[reg]) {
 644             DEBUG(std::cerr << mri_->getName(reg) << '\n');
 645             return reg;
 646         }
 647     }
 648
 649     DEBUG(std::cerr << "no free register\n");
 650     return 0;
 651 }
 652
 653 bool RA::tempPhysRegAvailable(unsigned physReg)
 654 {
 655     assert(reserved_[physReg] &&
 656            "cannot call this method with a not reserved temp register");
 657
 658     return !regUse_[physReg];
 659 }
 660
 661 unsigned RA::getFreeTempPhysReg(unsigned virtReg)
 662 {
 663     DEBUG(std::cerr << "\t\tgetting free temporary physical register: ");
 664
 665     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(virtReg);
 666     // go in reverse allocation order for the temp registers
 667     for (TargetRegisterClass::iterator i = rc->allocation_order_end(*mf_) - 1;
 668          i != rc->allocation_order_begin(*mf_) - 1; --i) {
 669         unsigned reg = *i;
 670         if (reserved_[reg] && !regUse_[reg]) {
 671             DEBUG(std::cerr << mri_->getName(reg) << '\n');
 672             return reg;
 673         }
 674     }
 675
 676     assert(0 && "no free temporary physical register?");
 677     return 0;
 678 }
 679
 680 void RA::assignVirt2PhysReg(unsigned virtReg, unsigned physReg)
 681 {
 682     v2pMap_[virtReg] = physReg;
 683     markPhysRegNotFree(physReg);
 684 }
 685
 686 void RA::clearVirtReg(unsigned virtReg)
 687 {
 688     Virt2PhysMap::iterator it = v2pMap_.find(virtReg);
 689     assert(it != v2pMap_.end() &&
 690            "attempting to clear a not allocated virtual register");
 691     unsigned physReg = it->second;
 692     markPhysRegFree(physReg);
 693     v2pMap_[virtReg] = 0; // this marks that this virtual register
 694                           // lives on the stack
 695     DEBUG(std::cerr << "\t\t\tcleared register " << mri_->getName(physReg)
 696           << "\n");
 697 }
 698
 699 void RA::assignVirt2StackSlot(unsigned virtReg)
 700 {
 701     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(virtReg);
 702     int frameIndex = mf_->getFrameInfo()->CreateStackObject(rc);
 703
 704     bool inserted = v2ssMap_.insert(std::make_pair(virtReg, frameIndex)).second;
 705     assert(inserted &&
 706            "attempt to assign stack slot to already assigned register?");
 707     // if the virtual register was previously assigned clear the mapping
 708     // and free the virtual register
 709     if (v2pMap_.find(virtReg) != v2pMap_.end()) {
 710         clearVirtReg(virtReg);
 711     }
 712     else {
 713         v2pMap_[virtReg] = 0; // this marks that this virtual register
 714                               // lives on the stack
 715     }
 716 }
 717
 718 int RA::getStackSlot(unsigned virtReg)
 719 {
 720     // use lower_bound so that we can do a possibly O(1) insert later
 721     // if necessary
 722     Virt2StackSlotMap::iterator it = v2ssMap_.find(virtReg);
 723     assert(it != v2ssMap_.end() &&
 724            "attempt to get stack slot on register that does not live on the stack");
 725     return it->second;
 726 }
 727
 728 void RA::spillVirtReg(unsigned virtReg)
 729 {
 730     DEBUG(std::cerr << "\t\t\tspilling register: " << virtReg);
 731     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(virtReg);
 732     int frameIndex = getStackSlot(virtReg);
 733     DEBUG(std::cerr << " to stack slot #" << frameIndex << '\n');
 734     ++numSpilled;
 735     instrAdded_ += mri_->storeRegToStackSlot(*currentMbb_, currentInstr_,
 736                                              v2pMap_[virtReg], frameIndex, rc);
 737     clearVirtReg(virtReg);
 738 }
 739
 740 void RA::loadVirt2PhysReg(unsigned virtReg, unsigned physReg)
 741 {
 742     DEBUG(std::cerr << "\t\t\tloading register: " << virtReg);
 743     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(virtReg);
 744     int frameIndex = getStackSlot(virtReg);
 745     DEBUG(std::cerr << " from stack slot #" << frameIndex << '\n');
 746     ++numReloaded;
 747     instrAdded_ += mri_->loadRegFromStackSlot(*currentMbb_, currentInstr_,
 748                                               physReg, frameIndex, rc);
 749     assignVirt2PhysReg(virtReg, physReg);
 750 }
 751
 752 void RA::markPhysRegFree(unsigned physReg)
 753 {
 754     assert(regUse_[physReg] != 0);
 755     --regUse_[physReg];
 756     for (const unsigned* as = mri_->getAliasSet(physReg); *as; ++as) {
 757         physReg = *as;
 758         assert(regUse_[physReg] != 0);
 759         --regUse_[physReg];
 760     }
 761 }
 762
 763 void RA::markPhysRegNotFree(unsigned physReg)
 764 {
 765     ++regUse_[physReg];
 766     for (const unsigned* as = mri_->getAliasSet(physReg); *as; ++as) {
 767         physReg = *as;
 768         ++regUse_[physReg];
 769     }
 770 }
 771
 772 FunctionPass* llvm::createLinearScanRegisterAllocator() {
 773     return new RA();
 774 }