lib/CodeGen/RegAllocLinearScan.cpp

   1 //===-- RegAllocLinearScan.cpp - Linear Scan register allocator -----------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements a linear scan register allocator.
  11 //
  12 //===----------------------------------------------------------------------===//
  13 #define DEBUG_TYPE "regalloc"
  14 #include "llvm/Function.h"
  15 #include "llvm/CodeGen/LiveIntervals.h"
  16 #include "llvm/CodeGen/LiveVariables.h"
  17 #include "llvm/CodeGen/MachineFrameInfo.h"
  18 #include "llvm/CodeGen/MachineFunctionPass.h"
  19 #include "llvm/CodeGen/MachineInstr.h"
  20 #include "llvm/CodeGen/Passes.h"
  21 #include "llvm/CodeGen/SSARegMap.h"
  22 #include "llvm/Target/MRegisterInfo.h"
  23 #include "llvm/Target/TargetInstrInfo.h"
  24 #include "llvm/Target/TargetMachine.h"
  25 #include "llvm/Support/CFG.h"
  26 #include "Support/Debug.h"
  27 #include "Support/DepthFirstIterator.h"
  28 #include "Support/Statistic.h"
  29 #include "Support/STLExtras.h"
  30 using namespace llvm;
  31
  32 namespace {
  33     Statistic<> numSpilled ("ra-linearscan", "Number of registers spilled");
  34     Statistic<> numReloaded("ra-linearscan", "Number of registers reloaded");
  35     Statistic<> numPeep    ("ra-linearscan",
  36                             "Number of identity moves eliminated");
  37
  38     class PhysRegTracker {
  39     private:
  40         const MRegisterInfo* mri_;
  41         std::vector<bool> reserved_;
  42         std::vector<unsigned> regUse_;
  43
  44     public:
  45         PhysRegTracker(MachineFunction* mf)
  46             : mri_(mf ? mf->getTarget().getRegisterInfo() : NULL) {
  47             if (mri_) {
  48                 reserved_.assign(mri_->getNumRegs(), false);
  49                 regUse_.assign(mri_->getNumRegs(), 0);
  50             }
  51         }
  52
  53         PhysRegTracker(const PhysRegTracker& rhs)
  54             : mri_(rhs.mri_),
  55               reserved_(rhs.reserved_),
  56               regUse_(rhs.regUse_) {
  57         }
  58
  59         const PhysRegTracker& operator=(const PhysRegTracker& rhs) {
  60             mri_ = rhs.mri_;
  61             reserved_ = rhs.reserved_;
  62             regUse_ = rhs.regUse_;
  63             return *this;
  64         }
  65
  66         void reservePhysReg(unsigned physReg) {
  67             reserved_[physReg] = true;
  68         }
  69
  70         void addPhysRegUse(unsigned physReg) {
  71             ++regUse_[physReg];
  72             for (const unsigned* as = mri_->getAliasSet(physReg); *as; ++as) {
  73                 physReg = *as;
  74                 ++regUse_[physReg];
  75             }
  76         }
  77
  78         void delPhysRegUse(unsigned physReg) {
  79             assert(regUse_[physReg] != 0);
  80             --regUse_[physReg];
  81             for (const unsigned* as = mri_->getAliasSet(physReg); *as; ++as) {
  82                 physReg = *as;
  83                 assert(regUse_[physReg] != 0);
  84                 --regUse_[physReg];
  85             }
  86         }
  87
  88         bool isPhysRegReserved(unsigned physReg) const {
  89             return reserved_[physReg];
  90         }
  91
  92         bool isPhysRegAvail(unsigned physReg) const {
  93             return regUse_[physReg] == 0 && !isPhysRegReserved(physReg);
  94         }
  95
  96         bool isReservedPhysRegAvail(unsigned physReg) const {
  97             return regUse_[physReg] == 0 && isPhysRegReserved(physReg);
  98         }
  99     };
 100
 101     class RA : public MachineFunctionPass {
 102     private:
 103         MachineFunction* mf_;
 104         const TargetMachine* tm_;
 105         const MRegisterInfo* mri_;
 106         LiveIntervals* li_;
 107         MachineFunction::iterator currentMbb_;
 108         MachineBasicBlock::iterator currentInstr_;
 109         typedef std::vector<const LiveIntervals::Interval*> IntervalPtrs;
 110         IntervalPtrs unhandled_, fixed_, active_, inactive_;
 111
 112         PhysRegTracker prt_;
 113
 114         typedef std::map<unsigned, unsigned> Virt2PhysMap;
 115         Virt2PhysMap v2pMap_;
 116
 117         typedef std::map<unsigned, int> Virt2StackSlotMap;
 118         Virt2StackSlotMap v2ssMap_;
 119
 120         int instrAdded_;
 121
 122         typedef std::vector<float> SpillWeights;
 123         SpillWeights spillWeights_;
 124
 125     public:
 126         RA()
 127             : prt_(NULL) {
 128
 129         }
 130
 131         virtual const char* getPassName() const {
 132             return "Linear Scan Register Allocator";
 133         }
 134
 135         virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 136             AU.addRequired<LiveVariables>();
 137             AU.addRequired<LiveIntervals>();
 138             MachineFunctionPass::getAnalysisUsage(AU);
 139         }
 140
 141         /// runOnMachineFunction - register allocate the whole function
 142         bool runOnMachineFunction(MachineFunction&);
 143
 144         void releaseMemory();
 145
 146     private:
 147         /// initIntervalSets - initializa the four interval sets:
 148         /// unhandled, fixed, active and inactive
 149         void initIntervalSets(const LiveIntervals::Intervals& li);
 150
 151         /// processActiveIntervals - expire old intervals and move
 152         /// non-overlapping ones to the incative list
 153         void processActiveIntervals(IntervalPtrs::value_type cur);
 154
 155         /// processInactiveIntervals - expire old intervals and move
 156         /// overlapping ones to the active list
 157         void processInactiveIntervals(IntervalPtrs::value_type cur);
 158
 159         /// updateSpillWeights - updates the spill weights of the
 160         /// specifed physical register and its weight
 161         void updateSpillWeights(unsigned reg, SpillWeights::value_type weight);
 162
 163         /// assignRegOrStackSlotAtInterval - assign a register if one
 164         /// is available, or spill.
 165         void assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur);
 166
 167         ///
 168         /// register handling helpers
 169         ///
 170
 171         /// getFreePhysReg - return a free physical register for this
 172         /// virtual register interval if we have one, otherwise return
 173         /// 0
 174         unsigned getFreePhysReg(IntervalPtrs::value_type cur);
 175
 176         /// getFreeTempPhysReg - return a free temprorary physical
 177         /// register for this virtual register if we have one (should
 178         /// never return 0)
 179         unsigned getFreeTempPhysReg(unsigned virtReg);
 180
 181         /// assignVirt2PhysReg - assigns the free physical register to
 182         /// the virtual register passed as arguments
 183         Virt2PhysMap::iterator
 184         assignVirt2PhysReg(unsigned virtReg, unsigned physReg);
 185
 186         /// clearVirtReg - free the physical register associated with this
 187         /// virtual register and disassociate virtual->physical and
 188         /// physical->virtual mappings
 189         void clearVirtReg(Virt2PhysMap::iterator it);
 190
 191         /// assignVirt2StackSlot - assigns this virtual register to a
 192         /// stack slot
 193         void assignVirt2StackSlot(unsigned virtReg);
 194
 195         /// getStackSlot - returns the offset of the specified
 196         /// register on the stack
 197         int getStackSlot(unsigned virtReg);
 198
 199         /// spillVirtReg - spills the virtual register
 200         void spillVirtReg(Virt2PhysMap::iterator it);
 201
 202         /// loadPhysReg - loads to the physical register the value of
 203         /// the virtual register specifed. Virtual register must have
 204         /// an assigned stack slot
 205         Virt2PhysMap::iterator
 206         loadVirt2PhysReg(unsigned virtReg, unsigned physReg);
 207
 208         void printVirtRegAssignment() const {
 209             std::cerr << "register assignment:\n";
 210
 211             for (Virt2PhysMap::const_iterator
 212                      i = v2pMap_.begin(), e = v2pMap_.end(); i != e; ++i) {
 213                 assert(i->second != 0);
 214                 std::cerr << '[' << i->first << ','
 215                           << mri_->getName(i->second) << "]\n";
 216             }
 217             for (Virt2StackSlotMap::const_iterator
 218                      i = v2ssMap_.begin(), e = v2ssMap_.end(); i != e; ++i) {
 219                 std::cerr << '[' << i->first << ",ss#" << i->second << "]\n";
 220             }
 221             std::cerr << '\n';
 222         }
 223
 224         void printIntervals(const char* const str,
 225                             RA::IntervalPtrs::const_iterator i,
 226                             RA::IntervalPtrs::const_iterator e) const {
 227             if (str) std::cerr << str << " intervals:\n";
 228             for (; i != e; ++i) {
 229                 std::cerr << "\t\t" << **i << " -> ";
 230                 unsigned reg = (*i)->reg;
 231                 if (MRegisterInfo::isVirtualRegister(reg)) {
 232                     Virt2PhysMap::const_iterator it = v2pMap_.find(reg);
 233                     reg = (it == v2pMap_.end() ? 0 : it->second);
 234                 }
 235                 std::cerr << mri_->getName(reg) << '\n';
 236             }
 237         }
 238
 239 //         void printFreeRegs(const char* const str,
 240 //                            const TargetRegisterClass* rc) const {
 241 //             if (str) std::cerr << str << ':';
 242 //             for (TargetRegisterClass::iterator i =
 243 //                      rc->allocation_order_begin(*mf_);
 244 //                  i != rc->allocation_order_end(*mf_); ++i) {
 245 //                 unsigned reg = *i;
 246 //                 if (!regUse_[reg]) {
 247 //                     std::cerr << ' ' << mri_->getName(reg);
 248 //                     if (reserved_[reg]) std::cerr << "*";
 249 //                 }
 250 //             }
 251 //             std::cerr << '\n';
 252 //         }
 253     };
 254 }
 255
 256 void RA::releaseMemory()
 257 {
 258     v2pMap_.clear();
 259     v2ssMap_.clear();
 260     unhandled_.clear();
 261     active_.clear();
 262     inactive_.clear();
 263     fixed_.clear();
 264
 265 }
 266
 267 bool RA::runOnMachineFunction(MachineFunction &fn) {
 268     mf_ = &fn;
 269     tm_ = &fn.getTarget();
 270     mri_ = tm_->getRegisterInfo();
 271     li_ = &getAnalysis<LiveIntervals>();
 272     prt_ = PhysRegTracker(mf_);
 273
 274     initIntervalSets(li_->getIntervals());
 275
 276     // FIXME: this will work only for the X86 backend. I need to
 277     // device an algorthm to select the minimal (considering register
 278     // aliasing) number of temp registers to reserve so that we have 2
 279     // registers for each register class available.
 280
 281     // reserve R8:   CH,  CL
 282     //         R16:  CX,  DI,
 283     //         R32: ECX, EDI,
 284     //         RFP: FP5, FP6
 285     prt_.reservePhysReg( 8); /*  CH */
 286     prt_.reservePhysReg( 9); /*  CL */
 287     prt_.reservePhysReg(10); /*  CX */
 288     prt_.reservePhysReg(12); /*  DI */
 289     prt_.reservePhysReg(18); /* ECX */
 290     prt_.reservePhysReg(19); /* EDI */
 291     prt_.reservePhysReg(28); /* FP5 */
 292     prt_.reservePhysReg(29); /* FP6 */
 293
 294     // linear scan algorithm
 295     DEBUG(std::cerr << "Machine Function\n");
 296
 297     DEBUG(printIntervals("\tunhandled", unhandled_.begin(), unhandled_.end()));
 298     DEBUG(printIntervals("\tfixed", fixed_.begin(), fixed_.end()));
 299     DEBUG(printIntervals("\tactive", active_.begin(), active_.end()));
 300     DEBUG(printIntervals("\tinactive", inactive_.begin(), inactive_.end()));
 301
 302     while (!unhandled_.empty() || !fixed_.empty()) {
 303         // pick the interval with the earliest start point
 304         IntervalPtrs::value_type cur;
 305         if (fixed_.empty()) {
 306             cur = unhandled_.front();
 307             unhandled_.erase(unhandled_.begin());
 308         }
 309         else if (unhandled_.empty()) {
 310             cur = fixed_.front();
 311             fixed_.erase(fixed_.begin());
 312         }
 313         else if (unhandled_.front()->start() < fixed_.front()->start()) {
 314             cur = unhandled_.front();
 315             unhandled_.erase(unhandled_.begin());
 316         }
 317         else {
 318             cur = fixed_.front();
 319             fixed_.erase(fixed_.begin());
 320         }
 321
 322         DEBUG(std::cerr << *cur << '\n');
 323
 324         processActiveIntervals(cur);
 325         processInactiveIntervals(cur);
 326
 327         // if this register is fixed we are done
 328         if (MRegisterInfo::isPhysicalRegister(cur->reg)) {
 329             prt_.addPhysRegUse(cur->reg);
 330             active_.push_back(cur);
 331         }
 332         // otherwise we are allocating a virtual register. try to find
 333         // a free physical register or spill an interval in order to
 334         // assign it one (we could spill the current though).
 335         else {
 336             assignRegOrStackSlotAtInterval(cur);
 337         }
 338
 339         DEBUG(printIntervals("\tactive", active_.begin(), active_.end()));
 340         DEBUG(printIntervals("\tinactive", inactive_.begin(), inactive_.end()));    }
 341
 342     // expire any remaining active intervals
 343     for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
 344         unsigned reg = (*i)->reg;
 345         DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n");
 346         if (MRegisterInfo::isVirtualRegister(reg)) {
 347             reg = v2pMap_[reg];
 348         }
 349         prt_.delPhysRegUse(reg);
 350     }
 351
 352     typedef LiveIntervals::Reg2RegMap Reg2RegMap;
 353     const Reg2RegMap& r2rMap = li_->getJoinedRegMap();
 354
 355     DEBUG(printVirtRegAssignment());
 356     DEBUG(std::cerr << "Performing coalescing on joined intervals\n");
 357     // perform coalescing if we were passed joined intervals
 358     for(Reg2RegMap::const_iterator i = r2rMap.begin(), e = r2rMap.end();
 359         i != e; ++i) {
 360         unsigned reg = i->first;
 361         unsigned rep = li_->rep(reg);
 362
 363         assert((MRegisterInfo::isPhysicalRegister(rep) ||
 364                 v2pMap_.count(rep) || v2ssMap_.count(rep)) &&
 365                "representative register is not allocated!");
 366
 367         assert(MRegisterInfo::isVirtualRegister(reg) &&
 368                !v2pMap_.count(reg) && !v2ssMap_.count(reg) &&
 369                "coalesced register is already allocated!");
 370
 371         if (MRegisterInfo::isPhysicalRegister(rep)) {
 372             v2pMap_.insert(std::make_pair(reg, rep));
 373         }
 374         else {
 375             Virt2PhysMap::const_iterator pr = v2pMap_.find(rep);
 376             if (pr != v2pMap_.end()) {
 377                 v2pMap_.insert(std::make_pair(reg, pr->second));
 378             }
 379             else {
 380                 Virt2StackSlotMap::const_iterator ss = v2ssMap_.find(rep);
 381                 assert(ss != v2ssMap_.end());
 382                 v2ssMap_.insert(std::make_pair(reg, ss->second));
 383             }
 384         }
 385     }
 386
 387     DEBUG(printVirtRegAssignment());
 388     DEBUG(std::cerr << "finished register allocation\n");
 389
 390     const TargetInstrInfo& tii = tm_->getInstrInfo();
 391
 392     DEBUG(std::cerr << "Rewrite machine code:\n");
 393     for (currentMbb_ = mf_->begin(); currentMbb_ != mf_->end(); ++currentMbb_) {
 394         instrAdded_ = 0;
 395
 396         for (currentInstr_ = currentMbb_->begin();
 397              currentInstr_ != currentMbb_->end(); ) {
 398             DEBUG(std::cerr << "\tinstruction: ";
 399                   currentInstr_->print(std::cerr, *tm_););
 400
 401             // use our current mapping and actually replace and
 402             // virtual register with its allocated physical registers
 403             DEBUG(std::cerr << "\t\treplacing virtual registers with mapped "
 404                   "physical registers:\n");
 405             for (unsigned i = 0, e = currentInstr_->getNumOperands();
 406                  i != e; ++i) {
 407                 MachineOperand& op = currentInstr_->getOperand(i);
 408                 if (op.isRegister() &&
 409                     MRegisterInfo::isVirtualRegister(op.getReg())) {
 410                     unsigned virtReg = op.getReg();
 411                     Virt2PhysMap::const_iterator it = v2pMap_.find(virtReg);
 412                     if (it != v2pMap_.end()) {
 413                         DEBUG(std::cerr << "\t\t\t%reg" << it->first
 414                               << " -> " << mri_->getName(it->second) << '\n');
 415                         currentInstr_->SetMachineOperandReg(i, it->second);
 416                     }
 417                 }
 418             }
 419
 420             unsigned srcReg, dstReg;
 421             if (tii.isMoveInstr(*currentInstr_, srcReg, dstReg) &&
 422                 ((MRegisterInfo::isPhysicalRegister(srcReg) &&
 423                   MRegisterInfo::isPhysicalRegister(dstReg) &&
 424                   srcReg == dstReg) ||
 425                  (MRegisterInfo::isVirtualRegister(srcReg) &&
 426                   MRegisterInfo::isVirtualRegister(dstReg) &&
 427                   v2ssMap_[srcReg] == v2ssMap_[dstReg]))) {
 428                 currentInstr_ = currentMbb_->erase(currentInstr_);
 429                 ++numPeep;
 430                 DEBUG(std::cerr << "\t\tdeleting instruction\n");
 431                 continue;
 432             }
 433
 434             typedef std::vector<Virt2PhysMap::iterator> Regs;
 435             Regs toClear;
 436             Regs toSpill;
 437
 438             const unsigned numOperands = currentInstr_->getNumOperands();
 439
 440             DEBUG(std::cerr << "\t\tloading temporarily used operands to "
 441                   "registers:\n");
 442             for (unsigned i = 0; i != numOperands; ++i) {
 443                 MachineOperand& op = currentInstr_->getOperand(i);
 444                 if (op.isRegister() && op.isUse() &&
 445                     MRegisterInfo::isVirtualRegister(op.getReg())) {
 446                     unsigned virtReg = op.getAllocatedRegNum();
 447                     unsigned physReg = 0;
 448                     Virt2PhysMap::iterator it = v2pMap_.find(virtReg);
 449                     if (it != v2pMap_.end()) {
 450                         physReg = it->second;
 451                     }
 452                     else {
 453                         physReg = getFreeTempPhysReg(virtReg);
 454                         it = loadVirt2PhysReg(virtReg, physReg);
 455                         // we will clear uses that are not also defs
 456                         // before we allocate registers the defs
 457                         if (op.isDef())
 458                             toSpill.push_back(it);
 459                         else
 460                             toClear.push_back(it);
 461                     }
 462                     currentInstr_->SetMachineOperandReg(i, physReg);
 463                 }
 464             }
 465
 466             DEBUG(std::cerr << "\t\tclearing temporarily used but not defined "
 467                   "operands:\n");
 468             std::for_each(toClear.begin(), toClear.end(),
 469                           std::bind1st(std::mem_fun(&RA::clearVirtReg), this));
 470
 471             DEBUG(std::cerr << "\t\tassigning temporarily defined operands to "
 472                   "registers:\n");
 473             for (unsigned i = 0; i != numOperands; ++i) {
 474                 MachineOperand& op = currentInstr_->getOperand(i);
 475                 if (op.isRegister() &&
 476                     MRegisterInfo::isVirtualRegister(op.getReg())) {
 477                     assert(!op.isUse() && "we should not have uses here!");
 478                     unsigned virtReg = op.getReg();
 479                     unsigned physReg = 0;
 480                     Virt2PhysMap::iterator it = v2pMap_.find(virtReg);
 481                     if (it != v2pMap_.end()) {
 482                         physReg = it->second;
 483                     }
 484                     else {
 485                         physReg = getFreeTempPhysReg(virtReg);
 486                         it = assignVirt2PhysReg(virtReg, physReg);
 487                         // need to spill this after we are done with
 488                         // this instruction
 489                         toSpill.push_back(it);
 490                     }
 491                     currentInstr_->SetMachineOperandReg(i, physReg);
 492                 }
 493             }
 494             ++currentInstr_; // spills will go after this instruction
 495
 496             DEBUG(std::cerr << "\t\tspilling temporarily defined operands:\n");
 497             std::for_each(toSpill.begin(), toSpill.end(),
 498                           std::bind1st(std::mem_fun(&RA::spillVirtReg), this));
 499         }
 500     }
 501
 502     return true;
 503 }
 504
 505 void RA::initIntervalSets(const LiveIntervals::Intervals& li)
 506 {
 507     assert(unhandled_.empty() && fixed_.empty() &&
 508            active_.empty() && inactive_.empty() &&
 509            "interval sets should be empty on initialization");
 510
 511     for (LiveIntervals::Intervals::const_iterator i = li.begin(), e = li.end();
 512          i != e; ++i) {
 513         if (MRegisterInfo::isPhysicalRegister(i->reg))
 514             fixed_.push_back(&*i);
 515         else
 516             unhandled_.push_back(&*i);
 517     }
 518 }
 519
 520 void RA::processActiveIntervals(IntervalPtrs::value_type cur)
 521 {
 522     DEBUG(std::cerr << "\tprocessing active intervals:\n");
 523     for (IntervalPtrs::iterator i = active_.begin(); i != active_.end();) {
 524         unsigned reg = (*i)->reg;
 525         // remove expired intervals
 526         if ((*i)->expiredAt(cur->start())) {
 527             DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n");
 528             if (MRegisterInfo::isVirtualRegister(reg)) {
 529                 reg = v2pMap_[reg];
 530             }
 531             prt_.delPhysRegUse(reg);
 532             // remove from active
 533             i = active_.erase(i);
 534         }
 535         // move inactive intervals to inactive list
 536         else if (!(*i)->liveAt(cur->start())) {
 537             DEBUG(std::cerr << "\t\t\tinterval " << **i << " inactive\n");
 538             if (MRegisterInfo::isVirtualRegister(reg)) {
 539                 reg = v2pMap_[reg];
 540             }
 541             prt_.delPhysRegUse(reg);
 542             // add to inactive
 543             inactive_.push_back(*i);
 544             // remove from active
 545             i = active_.erase(i);
 546         }
 547         else {
 548             ++i;
 549         }
 550     }
 551 }
 552
 553 void RA::processInactiveIntervals(IntervalPtrs::value_type cur)
 554 {
 555     DEBUG(std::cerr << "\tprocessing inactive intervals:\n");
 556     for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end();) {
 557         unsigned reg = (*i)->reg;
 558
 559         // remove expired intervals
 560         if ((*i)->expiredAt(cur->start())) {
 561             DEBUG(std::cerr << "\t\t\tinterval " << **i << " expired\n");
 562             // remove from inactive
 563             i = inactive_.erase(i);
 564         }
 565         // move re-activated intervals in active list
 566         else if ((*i)->liveAt(cur->start())) {
 567             DEBUG(std::cerr << "\t\t\tinterval " << **i << " active\n");
 568             if (MRegisterInfo::isVirtualRegister(reg)) {
 569                 reg = v2pMap_[reg];
 570             }
 571             prt_.addPhysRegUse(reg);
 572             // add to active
 573             active_.push_back(*i);
 574             // remove from inactive
 575             i = inactive_.erase(i);
 576         }
 577         else {
 578             ++i;
 579         }
 580     }
 581 }
 582
 583 void RA::updateSpillWeights(unsigned reg, SpillWeights::value_type weight)
 584 {
 585     spillWeights_[reg] += weight;
 586     for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as)
 587         spillWeights_[*as] += weight;
 588 }
 589
 590 void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur)
 591 {
 592     DEBUG(std::cerr << "\tallocating current interval:\n");
 593
 594     PhysRegTracker backupPrt = prt_;
 595
 596     spillWeights_.assign(mri_->getNumRegs(), 0.0);
 597
 598     // for each interval in active update spill weights
 599     for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
 600          i != e; ++i) {
 601         unsigned reg = (*i)->reg;
 602         if (MRegisterInfo::isVirtualRegister(reg))
 603             reg = v2pMap_[reg];
 604         updateSpillWeights(reg, (*i)->weight);
 605     }
 606
 607     // for every interval in inactive we overlap with, mark the
 608     // register as not free and update spill weights
 609     for (IntervalPtrs::const_iterator i = inactive_.begin(),
 610              e = inactive_.end(); i != e; ++i) {
 611         if (cur->overlaps(**i)) {
 612             unsigned reg = (*i)->reg;
 613             if (MRegisterInfo::isVirtualRegister(reg))
 614                 reg = v2pMap_[reg];
 615             prt_.addPhysRegUse(reg);
 616             updateSpillWeights(reg, (*i)->weight);
 617         }
 618     }
 619
 620     // for every interval in fixed we overlap with,
 621     // mark the register as not free and update spill weights
 622     for (IntervalPtrs::const_iterator i = fixed_.begin(),
 623              e = fixed_.end(); i != e; ++i) {
 624         if (cur->overlaps(**i)) {
 625             unsigned reg = (*i)->reg;
 626             prt_.addPhysRegUse(reg);
 627             updateSpillWeights(reg, (*i)->weight);
 628         }
 629     }
 630
 631     unsigned physReg = getFreePhysReg(cur);
 632     // if we find a free register, we are done: restore original
 633     // register tracker, assign this virtual to the free physical
 634     // register and add this interval to the active list.
 635     if (physReg) {
 636         prt_ = backupPrt;
 637         assignVirt2PhysReg(cur->reg, physReg);
 638         active_.push_back(cur);
 639         return;
 640     }
 641
 642     DEBUG(std::cerr << "\t\tassigning stack slot at interval "<< *cur << ":\n");
 643
 644     float minWeight = std::numeric_limits<float>::max();
 645     unsigned minReg = 0;
 646     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
 647     for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
 648          i != rc->allocation_order_end(*mf_); ++i) {
 649         unsigned reg = *i;
 650         if (!prt_.isPhysRegReserved(reg) && minWeight > spillWeights_[reg]) {
 651             minWeight = spillWeights_[reg];
 652             minReg = reg;
 653         }
 654     }
 655     DEBUG(std::cerr << "\t\t\tregister with min weight: "
 656           << mri_->getName(minReg) << " (" << minWeight << ")\n");
 657
 658     // if the current has the minimum weight, we are done: restore
 659     // original register tracker and assign a stack slot to this
 660     // virtual register
 661     if (cur->weight < minWeight) {
 662         prt_ = backupPrt;
 663         DEBUG(std::cerr << "\t\t\t\tspilling: " << *cur << '\n');
 664         assignVirt2StackSlot(cur->reg);
 665         return;
 666     }
 667
 668     std::vector<bool> toSpill(mri_->getNumRegs(), false);
 669     toSpill[minReg] = true;
 670     for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as)
 671         toSpill[*as] = true;
 672
 673     std::vector<unsigned> spilled;
 674     for (IntervalPtrs::iterator i = active_.begin();
 675          i != active_.end(); ) {
 676         unsigned reg = (*i)->reg;
 677         if (MRegisterInfo::isVirtualRegister(reg) &&
 678             toSpill[v2pMap_[reg]] &&
 679             cur->overlaps(**i)) {
 680             spilled.push_back(v2pMap_[reg]);
 681             DEBUG(std::cerr << "\t\t\t\tspilling : " << **i << '\n');
 682             assignVirt2StackSlot(reg);
 683             i = active_.erase(i);
 684         }
 685         else {
 686             ++i;
 687         }
 688     }
 689     for (IntervalPtrs::iterator i = inactive_.begin();
 690          i != inactive_.end(); ) {
 691         unsigned reg = (*i)->reg;
 692         if (MRegisterInfo::isVirtualRegister(reg) &&
 693             toSpill[v2pMap_[reg]] &&
 694             cur->overlaps(**i)) {
 695             DEBUG(std::cerr << "\t\t\t\tspilling : " << **i << '\n');
 696             assignVirt2StackSlot(reg);
 697             i = inactive_.erase(i);
 698         }
 699         else {
 700             ++i;
 701         }
 702     }
 703
 704     physReg = getFreePhysReg(cur);
 705     assert(physReg && "no free physical register after spill?");
 706
 707     prt_ = backupPrt;
 708     for (unsigned i = 0; i < spilled.size(); ++i)
 709         prt_.delPhysRegUse(spilled[i]);
 710
 711     assignVirt2PhysReg(cur->reg, physReg);
 712     active_.push_back(cur);
 713 }
 714
 715 unsigned RA::getFreePhysReg(IntervalPtrs::value_type cur)
 716 {
 717     DEBUG(std::cerr << "\t\tgetting free physical register: ");
 718     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
 719
 720     for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
 721          i != rc->allocation_order_end(*mf_); ++i) {
 722         unsigned reg = *i;
 723         if (prt_.isPhysRegAvail(reg)) {
 724             DEBUG(std::cerr << mri_->getName(reg) << '\n');
 725             return reg;
 726         }
 727     }
 728
 729     DEBUG(std::cerr << "no free register\n");
 730     return 0;
 731 }
 732
 733 unsigned RA::getFreeTempPhysReg(unsigned virtReg)
 734 {
 735     DEBUG(std::cerr << "\t\tgetting free temporary physical register: ");
 736
 737     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(virtReg);
 738     // go in reverse allocation order for the temp registers
 739     typedef std::reverse_iterator<TargetRegisterClass::iterator> TRCRevIter;
 740     for (TRCRevIter
 741              i(rc->allocation_order_end(*mf_)),
 742              e(rc->allocation_order_begin(*mf_)); i != e; ++i) {
 743         unsigned reg = *i;
 744         if (prt_.isReservedPhysRegAvail(reg)) {
 745             DEBUG(std::cerr << mri_->getName(reg) << '\n');
 746             return reg;
 747         }
 748     }
 749
 750     assert(0 && "no free temporary physical register?");
 751     return 0;
 752 }
 753
 754 RA::Virt2PhysMap::iterator
 755 RA::assignVirt2PhysReg(unsigned virtReg, unsigned physReg)
 756 {
 757     bool inserted;
 758     Virt2PhysMap::iterator it;
 759     tie(it, inserted) = v2pMap_.insert(std::make_pair(virtReg, physReg));
 760     assert(inserted && "attempting to assign a virt->phys mapping to an "
 761            "already mapped register");
 762     prt_.addPhysRegUse(physReg);
 763     return it;
 764 }
 765
 766 void RA::clearVirtReg(Virt2PhysMap::iterator it)
 767 {
 768     assert(it != v2pMap_.end() &&
 769            "attempting to clear a not allocated virtual register");
 770     unsigned physReg = it->second;
 771     prt_.delPhysRegUse(physReg);
 772     v2pMap_.erase(it);
 773     DEBUG(std::cerr << "\t\t\tcleared register " << mri_->getName(physReg)
 774           << "\n");
 775 }
 776
 777 void RA::assignVirt2StackSlot(unsigned virtReg)
 778 {
 779     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(virtReg);
 780     int frameIndex = mf_->getFrameInfo()->CreateStackObject(rc);
 781
 782     bool inserted = v2ssMap_.insert(std::make_pair(virtReg, frameIndex)).second;
 783     assert(inserted &&
 784            "attempt to assign stack slot to already assigned register?");
 785     // if the virtual register was previously assigned clear the mapping
 786     // and free the virtual register
 787     Virt2PhysMap::iterator it = v2pMap_.find(virtReg);
 788     if (it != v2pMap_.end()) {
 789         clearVirtReg(it);
 790     }
 791 }
 792
 793 int RA::getStackSlot(unsigned virtReg)
 794 {
 795     Virt2StackSlotMap::iterator it = v2ssMap_.find(virtReg);
 796     assert(it != v2ssMap_.end() &&
 797            "attempt to get stack slot on register that does not live on the stack");
 798     return it->second;
 799 }
 800
 801 void RA::spillVirtReg(Virt2PhysMap::iterator it)
 802 {
 803     assert(it != v2pMap_.end() &&
 804            "attempt to spill a not allocated virtual register");
 805     unsigned virtReg = it->first;
 806     DEBUG(std::cerr << "\t\t\tspilling register: " << virtReg);
 807     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(virtReg);
 808     int frameIndex = getStackSlot(virtReg);
 809     DEBUG(std::cerr << " to stack slot #" << frameIndex << '\n');
 810     ++numSpilled;
 811     instrAdded_ += mri_->storeRegToStackSlot(*currentMbb_, currentInstr_,
 812                                              it->second, frameIndex, rc);
 813     clearVirtReg(it);
 814 }
 815
 816 RA::Virt2PhysMap::iterator
 817 RA::loadVirt2PhysReg(unsigned virtReg, unsigned physReg)
 818 {
 819     DEBUG(std::cerr << "\t\t\tloading register: " << virtReg);
 820     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(virtReg);
 821     int frameIndex = getStackSlot(virtReg);
 822     DEBUG(std::cerr << " from stack slot #" << frameIndex << '\n');
 823     ++numReloaded;
 824     instrAdded_ += mri_->loadRegFromStackSlot(*currentMbb_, currentInstr_,
 825                                               physReg, frameIndex, rc);
 826     return assignVirt2PhysReg(virtReg, physReg);
 827 }
 828
 829 FunctionPass* llvm::createLinearScanRegisterAllocator() {
 830     return new RA();
 831 }