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.isVirtualRegister()) {
 409                     unsigned virtReg = op.getAllocatedRegNum();
 410                     Virt2PhysMap::const_iterator it = v2pMap_.find(virtReg);
 411                     if (it != v2pMap_.end()) {
 412                         DEBUG(std::cerr << "\t\t\t%reg" << it->first
 413                               << " -> " << mri_->getName(it->second) << '\n');
 414                         (*currentInstr_)->SetMachineOperandReg(i, it->second);
 415                     }
 416                 }
 417             }
 418
 419             unsigned srcReg, dstReg;
 420             if (tii.isMoveInstr(**currentInstr_, srcReg, dstReg) &&
 421                 ((MRegisterInfo::isPhysicalRegister(srcReg) &&
 422                   MRegisterInfo::isPhysicalRegister(dstReg) &&
 423                   srcReg == dstReg) ||
 424                  (MRegisterInfo::isVirtualRegister(srcReg) &&
 425                   MRegisterInfo::isVirtualRegister(dstReg) &&
 426                   v2ssMap_[srcReg] == v2ssMap_[dstReg]))) {
 427                 delete *currentInstr_;
 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.isVirtualRegister() && op.isUse()) {
 445                     unsigned virtReg = op.getAllocatedRegNum();
 446                     unsigned physReg = 0;
 447                     Virt2PhysMap::iterator it = v2pMap_.find(virtReg);
 448                     if (it != v2pMap_.end()) {
 449                         physReg = it->second;
 450                     }
 451                     else {
 452                         physReg = getFreeTempPhysReg(virtReg);
 453                         it = loadVirt2PhysReg(virtReg, physReg);
 454                         // we will clear uses that are not also defs
 455                         // before we allocate registers the defs
 456                         if (op.isDef())
 457                             toSpill.push_back(it);
 458                         else
 459                             toClear.push_back(it);
 460                     }
 461                     (*currentInstr_)->SetMachineOperandReg(i, physReg);
 462                 }
 463             }
 464
 465             DEBUG(std::cerr << "\t\tclearing temporarily used but not defined "
 466                   "operands:\n");
 467             std::for_each(toClear.begin(), toClear.end(),
 468                           std::bind1st(std::mem_fun(&RA::clearVirtReg), this));
 469
 470             DEBUG(std::cerr << "\t\tassigning temporarily defined operands to "
 471                   "registers:\n");
 472             for (unsigned i = 0; i != numOperands; ++i) {
 473                 MachineOperand& op = (*currentInstr_)->getOperand(i);
 474                 if (op.isVirtualRegister()) {
 475                     assert(!op.isUse() && "we should not have uses here!");
 476                     unsigned virtReg = op.getAllocatedRegNum();
 477                     unsigned physReg = 0;
 478                     Virt2PhysMap::iterator it = v2pMap_.find(virtReg);
 479                     if (it != v2pMap_.end()) {
 480                         physReg = it->second;
 481                     }
 482                     else {
 483                         physReg = getFreeTempPhysReg(virtReg);
 484                         it = assignVirt2PhysReg(virtReg, physReg);
 485                         // need to spill this after we are done with
 486                         // this instruction
 487                         toSpill.push_back(it);
 488                     }
 489                     (*currentInstr_)->SetMachineOperandReg(i, physReg);
 490                 }
 491             }
 492             ++currentInstr_; // spills will go after this instruction
 493
 494             DEBUG(std::cerr << "\t\tspilling temporarily defined operands:\n");
 495             std::for_each(toSpill.begin(), toSpill.end(),
 496                           std::bind1st(std::mem_fun(&RA::spillVirtReg), this));
 497         }
 498     }
 499
 500     return true;
 501 }
 502
 503 void RA::initIntervalSets(const LiveIntervals::Intervals& li)
 504 {
 505     assert(unhandled_.empty() && fixed_.empty() &&
 506            active_.empty() && inactive_.empty() &&
 507            "interval sets should be empty on initialization");
 508
 509     for (LiveIntervals::Intervals::const_iterator i = li.begin(), e = li.end();
 510          i != e; ++i) {
 511         if (MRegisterInfo::isPhysicalRegister(i->reg))
 512             fixed_.push_back(&*i);
 513         else
 514             unhandled_.push_back(&*i);
 515     }
 516 }
 517
 518 void RA::processActiveIntervals(IntervalPtrs::value_type cur)
 519 {
 520     DEBUG(std::cerr << "\tprocessing active intervals:\n");
 521     for (IntervalPtrs::iterator i = active_.begin(); i != active_.end();) {
 522         unsigned reg = (*i)->reg;
 523         // remove expired intervals
 524         if ((*i)->expiredAt(cur->start())) {
 525             DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n");
 526             if (MRegisterInfo::isVirtualRegister(reg)) {
 527                 reg = v2pMap_[reg];
 528             }
 529             prt_.delPhysRegUse(reg);
 530             // remove from active
 531             i = active_.erase(i);
 532         }
 533         // move inactive intervals to inactive list
 534         else if (!(*i)->liveAt(cur->start())) {
 535             DEBUG(std::cerr << "\t\t\tinterval " << **i << " inactive\n");
 536             if (MRegisterInfo::isVirtualRegister(reg)) {
 537                 reg = v2pMap_[reg];
 538             }
 539             prt_.delPhysRegUse(reg);
 540             // add to inactive
 541             inactive_.push_back(*i);
 542             // remove from active
 543             i = active_.erase(i);
 544         }
 545         else {
 546             ++i;
 547         }
 548     }
 549 }
 550
 551 void RA::processInactiveIntervals(IntervalPtrs::value_type cur)
 552 {
 553     DEBUG(std::cerr << "\tprocessing inactive intervals:\n");
 554     for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end();) {
 555         unsigned reg = (*i)->reg;
 556
 557         // remove expired intervals
 558         if ((*i)->expiredAt(cur->start())) {
 559             DEBUG(std::cerr << "\t\t\tinterval " << **i << " expired\n");
 560             // remove from inactive
 561             i = inactive_.erase(i);
 562         }
 563         // move re-activated intervals in active list
 564         else if ((*i)->liveAt(cur->start())) {
 565             DEBUG(std::cerr << "\t\t\tinterval " << **i << " active\n");
 566             if (MRegisterInfo::isVirtualRegister(reg)) {
 567                 reg = v2pMap_[reg];
 568             }
 569             prt_.addPhysRegUse(reg);
 570             // add to active
 571             active_.push_back(*i);
 572             // remove from inactive
 573             i = inactive_.erase(i);
 574         }
 575         else {
 576             ++i;
 577         }
 578     }
 579 }
 580
 581 void RA::updateSpillWeights(unsigned reg, SpillWeights::value_type weight)
 582 {
 583     spillWeights_[reg] += weight;
 584     for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as)
 585         spillWeights_[*as] += weight;
 586 }
 587
 588 void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur)
 589 {
 590     DEBUG(std::cerr << "\tallocating current interval:\n");
 591
 592     PhysRegTracker backupPrt = prt_;
 593
 594     spillWeights_.assign(mri_->getNumRegs(), 0.0);
 595
 596     // for each interval in active update spill weights
 597     for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
 598          i != e; ++i) {
 599         unsigned reg = (*i)->reg;
 600         if (MRegisterInfo::isVirtualRegister(reg))
 601             reg = v2pMap_[reg];
 602         updateSpillWeights(reg, (*i)->weight);
 603     }
 604
 605     // for every interval in inactive we overlap with, mark the
 606     // register as not free and update spill weights
 607     for (IntervalPtrs::const_iterator i = inactive_.begin(),
 608              e = inactive_.end(); i != e; ++i) {
 609         if (cur->overlaps(**i)) {
 610             unsigned reg = (*i)->reg;
 611             if (MRegisterInfo::isVirtualRegister(reg))
 612                 reg = v2pMap_[reg];
 613             prt_.addPhysRegUse(reg);
 614             updateSpillWeights(reg, (*i)->weight);
 615         }
 616     }
 617
 618     // for every interval in fixed we overlap with,
 619     // mark the register as not free and update spill weights
 620     for (IntervalPtrs::const_iterator i = fixed_.begin(),
 621              e = fixed_.end(); i != e; ++i) {
 622         if (cur->overlaps(**i)) {
 623             unsigned reg = (*i)->reg;
 624             prt_.addPhysRegUse(reg);
 625             updateSpillWeights(reg, (*i)->weight);
 626         }
 627     }
 628
 629     unsigned physReg = getFreePhysReg(cur);
 630     // if we find a free register, we are done: restore original
 631     // register tracker, assign this virtual to the free physical
 632     // register and add this interval to the active list.
 633     if (physReg) {
 634         prt_ = backupPrt;
 635         assignVirt2PhysReg(cur->reg, physReg);
 636         active_.push_back(cur);
 637         return;
 638     }
 639
 640     DEBUG(std::cerr << "\t\tassigning stack slot at interval "<< *cur << ":\n");
 641
 642     float minWeight = std::numeric_limits<float>::max();
 643     unsigned minReg = 0;
 644     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
 645     for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
 646          i != rc->allocation_order_end(*mf_); ++i) {
 647         unsigned reg = *i;
 648         if (!prt_.isPhysRegReserved(reg) && minWeight > spillWeights_[reg]) {
 649             minWeight = spillWeights_[reg];
 650             minReg = reg;
 651         }
 652     }
 653     DEBUG(std::cerr << "\t\t\tregister with min weight: "
 654           << mri_->getName(minReg) << " (" << minWeight << ")\n");
 655
 656     // if the current has the minimum weight, we are done: restore
 657     // original register tracker and assign a stack slot to this
 658     // virtual register
 659     if (cur->weight < minWeight) {
 660         prt_ = backupPrt;
 661         DEBUG(std::cerr << "\t\t\t\tspilling: " << *cur << '\n');
 662         assignVirt2StackSlot(cur->reg);
 663         return;
 664     }
 665
 666     std::vector<bool> toSpill(mri_->getNumRegs(), false);
 667     toSpill[minReg] = true;
 668     for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as)
 669         toSpill[*as] = true;
 670
 671     std::vector<unsigned> spilled;
 672     for (IntervalPtrs::iterator i = active_.begin();
 673          i != active_.end(); ) {
 674         unsigned reg = (*i)->reg;
 675         if (MRegisterInfo::isVirtualRegister(reg) &&
 676             toSpill[v2pMap_[reg]] &&
 677             cur->overlaps(**i)) {
 678             spilled.push_back(v2pMap_[reg]);
 679             DEBUG(std::cerr << "\t\t\t\tspilling : " << **i << '\n');
 680             assignVirt2StackSlot(reg);
 681             i = active_.erase(i);
 682         }
 683         else {
 684             ++i;
 685         }
 686     }
 687     for (IntervalPtrs::iterator i = inactive_.begin();
 688          i != inactive_.end(); ) {
 689         unsigned reg = (*i)->reg;
 690         if (MRegisterInfo::isVirtualRegister(reg) &&
 691             toSpill[v2pMap_[reg]] &&
 692             cur->overlaps(**i)) {
 693             DEBUG(std::cerr << "\t\t\t\tspilling : " << **i << '\n');
 694             assignVirt2StackSlot(reg);
 695             i = inactive_.erase(i);
 696         }
 697         else {
 698             ++i;
 699         }
 700     }
 701
 702     physReg = getFreePhysReg(cur);
 703     assert(physReg && "no free physical register after spill?");
 704
 705     prt_ = backupPrt;
 706     for (unsigned i = 0; i < spilled.size(); ++i)
 707         prt_.delPhysRegUse(spilled[i]);
 708
 709     assignVirt2PhysReg(cur->reg, physReg);
 710     active_.push_back(cur);
 711 }
 712
 713 unsigned RA::getFreePhysReg(IntervalPtrs::value_type cur)
 714 {
 715     DEBUG(std::cerr << "\t\tgetting free physical register: ");
 716     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
 717
 718     for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
 719          i != rc->allocation_order_end(*mf_); ++i) {
 720         unsigned reg = *i;
 721         if (prt_.isPhysRegAvail(reg)) {
 722             DEBUG(std::cerr << mri_->getName(reg) << '\n');
 723             return reg;
 724         }
 725     }
 726
 727     DEBUG(std::cerr << "no free register\n");
 728     return 0;
 729 }
 730
 731 unsigned RA::getFreeTempPhysReg(unsigned virtReg)
 732 {
 733     DEBUG(std::cerr << "\t\tgetting free temporary physical register: ");
 734
 735     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(virtReg);
 736     // go in reverse allocation order for the temp registers
 737     typedef std::reverse_iterator<TargetRegisterClass::iterator> TRCRevIter;
 738     for (TRCRevIter
 739              i(rc->allocation_order_end(*mf_)),
 740              e(rc->allocation_order_begin(*mf_)); i != e; ++i) {
 741         unsigned reg = *i;
 742         if (prt_.isReservedPhysRegAvail(reg)) {
 743             DEBUG(std::cerr << mri_->getName(reg) << '\n');
 744             return reg;
 745         }
 746     }
 747
 748     assert(0 && "no free temporary physical register?");
 749     return 0;
 750 }
 751
 752 RA::Virt2PhysMap::iterator
 753 RA::assignVirt2PhysReg(unsigned virtReg, unsigned physReg)
 754 {
 755     bool inserted;
 756     Virt2PhysMap::iterator it;
 757     tie(it, inserted) = v2pMap_.insert(std::make_pair(virtReg, physReg));
 758     assert(inserted && "attempting to assign a virt->phys mapping to an "
 759            "already mapped register");
 760     prt_.addPhysRegUse(physReg);
 761     return it;
 762 }
 763
 764 void RA::clearVirtReg(Virt2PhysMap::iterator it)
 765 {
 766     assert(it != v2pMap_.end() &&
 767            "attempting to clear a not allocated virtual register");
 768     unsigned physReg = it->second;
 769     prt_.delPhysRegUse(physReg);
 770     v2pMap_.erase(it);
 771     DEBUG(std::cerr << "\t\t\tcleared register " << mri_->getName(physReg)
 772           << "\n");
 773 }
 774
 775 void RA::assignVirt2StackSlot(unsigned virtReg)
 776 {
 777     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(virtReg);
 778     int frameIndex = mf_->getFrameInfo()->CreateStackObject(rc);
 779
 780     bool inserted = v2ssMap_.insert(std::make_pair(virtReg, frameIndex)).second;
 781     assert(inserted &&
 782            "attempt to assign stack slot to already assigned register?");
 783     // if the virtual register was previously assigned clear the mapping
 784     // and free the virtual register
 785     Virt2PhysMap::iterator it = v2pMap_.find(virtReg);
 786     if (it != v2pMap_.end()) {
 787         clearVirtReg(it);
 788     }
 789 }
 790
 791 int RA::getStackSlot(unsigned virtReg)
 792 {
 793     Virt2StackSlotMap::iterator it = v2ssMap_.find(virtReg);
 794     assert(it != v2ssMap_.end() &&
 795            "attempt to get stack slot on register that does not live on the stack");
 796     return it->second;
 797 }
 798
 799 void RA::spillVirtReg(Virt2PhysMap::iterator it)
 800 {
 801     assert(it != v2pMap_.end() &&
 802            "attempt to spill a not allocated virtual register");
 803     unsigned virtReg = it->first;
 804     DEBUG(std::cerr << "\t\t\tspilling register: " << virtReg);
 805     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(virtReg);
 806     int frameIndex = getStackSlot(virtReg);
 807     DEBUG(std::cerr << " to stack slot #" << frameIndex << '\n');
 808     ++numSpilled;
 809     instrAdded_ += mri_->storeRegToStackSlot(*currentMbb_, currentInstr_,
 810                                              it->second, frameIndex, rc);
 811     clearVirtReg(it);
 812 }
 813
 814 RA::Virt2PhysMap::iterator
 815 RA::loadVirt2PhysReg(unsigned virtReg, unsigned physReg)
 816 {
 817     DEBUG(std::cerr << "\t\t\tloading register: " << virtReg);
 818     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(virtReg);
 819     int frameIndex = getStackSlot(virtReg);
 820     DEBUG(std::cerr << " from stack slot #" << frameIndex << '\n');
 821     ++numReloaded;
 822     instrAdded_ += mri_->loadRegFromStackSlot(*currentMbb_, currentInstr_,
 823                                               physReg, frameIndex, rc);
 824     return assignVirt2PhysReg(virtReg, physReg);
 825 }
 826
 827 FunctionPass* llvm::createLinearScanRegisterAllocator() {
 828     return new RA();
 829 }