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