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