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