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