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