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