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 #include <algorithm>
  31 using namespace llvm;
  32
  33 namespace {
  34     Statistic<> numStores("ra-linearscan", "Number of stores added");
  35     Statistic<> numLoads ("ra-linearscan", "Number of loads added");
  36
  37     class PhysRegTracker {
  38     private:
  39         const MRegisterInfo* mri_;
  40         std::vector<unsigned> regUse_;
  41
  42     public:
  43         PhysRegTracker(MachineFunction* mf)
  44             : mri_(mf ? mf->getTarget().getRegisterInfo() : NULL) {
  45             if (mri_) {
  46                 regUse_.assign(mri_->getNumRegs(), 0);
  47             }
  48         }
  49
  50         PhysRegTracker(const PhysRegTracker& rhs)
  51             : mri_(rhs.mri_),
  52               regUse_(rhs.regUse_) {
  53         }
  54
  55         const PhysRegTracker& operator=(const PhysRegTracker& rhs) {
  56             mri_ = rhs.mri_;
  57             regUse_ = rhs.regUse_;
  58             return *this;
  59         }
  60
  61         void addPhysRegUse(unsigned physReg) {
  62             ++regUse_[physReg];
  63             for (const unsigned* as = mri_->getAliasSet(physReg); *as; ++as) {
  64                 physReg = *as;
  65                 ++regUse_[physReg];
  66             }
  67         }
  68
  69         void delPhysRegUse(unsigned physReg) {
  70             assert(regUse_[physReg] != 0);
  71             --regUse_[physReg];
  72             for (const unsigned* as = mri_->getAliasSet(physReg); *as; ++as) {
  73                 physReg = *as;
  74                 assert(regUse_[physReg] != 0);
  75                 --regUse_[physReg];
  76             }
  77         }
  78
  79         bool isPhysRegAvail(unsigned physReg) const {
  80             return regUse_[physReg] == 0;
  81         }
  82     };
  83
  84     class RA : public MachineFunctionPass {
  85     private:
  86         MachineFunction* mf_;
  87         const TargetMachine* tm_;
  88         const MRegisterInfo* mri_;
  89         LiveIntervals* li_;
  90         typedef std::list<LiveIntervals::Interval*> IntervalPtrs;
  91         IntervalPtrs unhandled_, fixed_, active_, inactive_, handled_;
  92
  93         PhysRegTracker prt_;
  94
  95         typedef std::map<unsigned, unsigned> Virt2PhysMap;
  96         Virt2PhysMap v2pMap_;
  97
  98         typedef std::map<unsigned, int> Virt2StackSlotMap;
  99         Virt2StackSlotMap v2ssMap_;
 100
 101         int instrAdded_;
 102
 103         typedef std::vector<float> SpillWeights;
 104         SpillWeights spillWeights_;
 105
 106     public:
 107         RA()
 108             : prt_(NULL) {
 109
 110         }
 111
 112         virtual const char* getPassName() const {
 113             return "Linear Scan Register Allocator";
 114         }
 115
 116         virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 117             AU.addRequired<LiveVariables>();
 118             AU.addRequired<LiveIntervals>();
 119             MachineFunctionPass::getAnalysisUsage(AU);
 120         }
 121
 122         /// runOnMachineFunction - register allocate the whole function
 123         bool runOnMachineFunction(MachineFunction&);
 124
 125         void releaseMemory();
 126
 127     private:
 128         /// initIntervalSets - initializa the four interval sets:
 129         /// unhandled, fixed, active and inactive
 130         void initIntervalSets(LiveIntervals::Intervals& li);
 131
 132         /// processActiveIntervals - expire old intervals and move
 133         /// non-overlapping ones to the incative list
 134         void processActiveIntervals(IntervalPtrs::value_type cur);
 135
 136         /// processInactiveIntervals - expire old intervals and move
 137         /// overlapping ones to the active list
 138         void processInactiveIntervals(IntervalPtrs::value_type cur);
 139
 140         /// updateSpillWeights - updates the spill weights of the
 141         /// specifed physical register and its weight
 142         void updateSpillWeights(unsigned reg, SpillWeights::value_type weight);
 143
 144         /// assignRegOrStackSlotAtInterval - assign a register if one
 145         /// is available, or spill.
 146         void assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur);
 147
 148         /// addSpillCode - adds spill code for interval. The interval
 149         /// must be modified by LiveIntervals::updateIntervalForSpill.
 150         void addSpillCode(IntervalPtrs::value_type li, int slot);
 151
 152         ///
 153         /// register handling helpers
 154         ///
 155
 156         /// getFreePhysReg - return a free physical register for this
 157         /// virtual register interval if we have one, otherwise return
 158         /// 0
 159         unsigned getFreePhysReg(IntervalPtrs::value_type cur);
 160
 161         /// assignVirt2PhysReg - assigns the free physical register to
 162         /// the virtual register passed as arguments
 163         Virt2PhysMap::iterator
 164         assignVirt2PhysReg(unsigned virtReg, unsigned physReg);
 165
 166         /// clearVirtReg - free the physical register associated with this
 167         /// virtual register and disassociate virtual->physical and
 168         /// physical->virtual mappings
 169         void clearVirtReg(Virt2PhysMap::iterator it);
 170
 171         /// assignVirt2StackSlot - assigns this virtual register to a
 172         /// stack slot. returns the stack slot
 173         int assignVirt2StackSlot(unsigned virtReg);
 174
 175         /// getStackSlot - returns the offset of the specified
 176         /// register on the stack
 177         int getStackSlot(unsigned virtReg);
 178
 179         void printVirtRegAssignment() const {
 180             std::cerr << "register assignment:\n";
 181
 182             for (Virt2PhysMap::const_iterator
 183                      i = v2pMap_.begin(), e = v2pMap_.end(); i != e; ++i) {
 184                 assert(i->second != 0);
 185                 std::cerr << '[' << i->first << ','
 186                           << mri_->getName(i->second) << "]\n";
 187             }
 188             for (Virt2StackSlotMap::const_iterator
 189                      i = v2ssMap_.begin(), e = v2ssMap_.end(); i != e; ++i) {
 190                 std::cerr << '[' << i->first << ",ss#" << i->second << "]\n";
 191             }
 192             std::cerr << '\n';
 193         }
 194
 195         void printIntervals(const char* const str,
 196                             RA::IntervalPtrs::const_iterator i,
 197                             RA::IntervalPtrs::const_iterator e) const {
 198             if (str) std::cerr << str << " intervals:\n";
 199             for (; i != e; ++i) {
 200                 std::cerr << "\t\t" << **i << " -> ";
 201                 unsigned reg = (*i)->reg;
 202                 if (MRegisterInfo::isVirtualRegister(reg)) {
 203                     Virt2PhysMap::const_iterator it = v2pMap_.find(reg);
 204                     reg = (it == v2pMap_.end() ? 0 : it->second);
 205                 }
 206                 std::cerr << mri_->getName(reg) << '\n';
 207             }
 208         }
 209
 210         void verifyAssignment() const {
 211             for (Virt2PhysMap::const_iterator i = v2pMap_.begin(),
 212                      e = v2pMap_.end(); i != e; ++i)
 213                 for (Virt2PhysMap::const_iterator i2 = next(i); i2 != e; ++i2)
 214                     if (MRegisterInfo::isVirtualRegister(i->second) &&
 215                         (i->second == i2->second ||
 216                          mri_->areAliases(i->second, i2->second))) {
 217                         const LiveIntervals::Interval
 218                             &in = li_->getInterval(i->second),
 219                             &in2 = li_->getInterval(i2->second);
 220                         if (in.overlaps(in2)) {
 221                             std::cerr << in << " overlaps " << in2 << '\n';
 222                             assert(0);
 223                         }
 224                     }
 225         }
 226     };
 227 }
 228
 229 void RA::releaseMemory()
 230 {
 231     v2pMap_.clear();
 232     v2ssMap_.clear();
 233     unhandled_.clear();
 234     active_.clear();
 235     inactive_.clear();
 236     fixed_.clear();
 237     handled_.clear();
 238 }
 239
 240 bool RA::runOnMachineFunction(MachineFunction &fn) {
 241     mf_ = &fn;
 242     tm_ = &fn.getTarget();
 243     mri_ = tm_->getRegisterInfo();
 244     li_ = &getAnalysis<LiveIntervals>();
 245     prt_ = PhysRegTracker(mf_);
 246
 247     initIntervalSets(li_->getIntervals());
 248
 249     // linear scan algorithm
 250     DEBUG(std::cerr << "Machine Function\n");
 251
 252     DEBUG(printIntervals("\tunhandled", unhandled_.begin(), unhandled_.end()));
 253     DEBUG(printIntervals("\tfixed", fixed_.begin(), fixed_.end()));
 254     DEBUG(printIntervals("\tactive", active_.begin(), active_.end()));
 255     DEBUG(printIntervals("\tinactive", inactive_.begin(), inactive_.end()));
 256
 257     while (!unhandled_.empty() || !fixed_.empty()) {
 258         // pick the interval with the earliest start point
 259         IntervalPtrs::value_type cur;
 260         if (fixed_.empty()) {
 261             cur = unhandled_.front();
 262             unhandled_.pop_front();
 263         }
 264         else if (unhandled_.empty()) {
 265             cur = fixed_.front();
 266             fixed_.pop_front();
 267         }
 268         else if (unhandled_.front()->start() < fixed_.front()->start()) {
 269             cur = unhandled_.front();
 270             unhandled_.pop_front();
 271         }
 272         else {
 273             cur = fixed_.front();
 274             fixed_.pop_front();
 275         }
 276
 277         DEBUG(std::cerr << *cur << '\n');
 278
 279         processActiveIntervals(cur);
 280         processInactiveIntervals(cur);
 281
 282         // if this register is fixed we are done
 283         if (MRegisterInfo::isPhysicalRegister(cur->reg)) {
 284             prt_.addPhysRegUse(cur->reg);
 285             active_.push_back(cur);
 286             handled_.push_back(cur);
 287         }
 288         // otherwise we are allocating a virtual register. try to find
 289         // a free physical register or spill an interval in order to
 290         // assign it one (we could spill the current though).
 291         else {
 292             assignRegOrStackSlotAtInterval(cur);
 293         }
 294
 295         DEBUG(printIntervals("\tactive", active_.begin(), active_.end()));
 296         DEBUG(printIntervals("\tinactive", inactive_.begin(), inactive_.end()));    }
 297
 298     // expire any remaining active intervals
 299     for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
 300         unsigned reg = (*i)->reg;
 301         DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n");
 302         if (MRegisterInfo::isVirtualRegister(reg)) {
 303             reg = v2pMap_[reg];
 304         }
 305         prt_.delPhysRegUse(reg);
 306     }
 307
 308     DEBUG(printVirtRegAssignment());
 309     DEBUG(std::cerr << "finished register allocation\n");
 310     // this is a slow operations do not uncomment
 311     // DEBUG(verifyAssignment());
 312
 313     const TargetInstrInfo& tii = tm_->getInstrInfo();
 314
 315     DEBUG(std::cerr << "Rewrite machine code:\n");
 316     for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
 317          mbbi != mbbe; ++mbbi) {
 318         instrAdded_ = 0;
 319
 320         for (MachineBasicBlock::iterator mii = mbbi->begin(), mie = mbbi->end();
 321              mii != mie; ++mii) {
 322             DEBUG(std::cerr << '\t'; mii->print(std::cerr, *tm_));
 323
 324             // use our current mapping and actually replace every
 325             // virtual register with its allocated physical registers
 326             DEBUG(std::cerr << "\t\treplacing virtual registers with mapped "
 327                   "physical registers:\n");
 328             for (unsigned i = 0, e = mii->getNumOperands();
 329                  i != e; ++i) {
 330                 MachineOperand& op = mii->getOperand(i);
 331                 if (op.isRegister() &&
 332                     MRegisterInfo::isVirtualRegister(op.getReg())) {
 333                     unsigned virtReg = op.getReg();
 334                     Virt2PhysMap::iterator it = v2pMap_.find(virtReg);
 335                     assert(it != v2pMap_.end() &&
 336                            "all virtual registers must be allocated");
 337                     unsigned physReg = it->second;
 338                     assert(MRegisterInfo::isPhysicalRegister(physReg));
 339                     DEBUG(std::cerr << "\t\t\t%reg" << virtReg
 340                           << " -> " << mri_->getName(physReg) << '\n');
 341                     mii->SetMachineOperandReg(i, physReg);
 342                 }
 343             }
 344         }
 345     }
 346
 347     return true;
 348 }
 349
 350 void RA::initIntervalSets(LiveIntervals::Intervals& li)
 351 {
 352     assert(unhandled_.empty() && fixed_.empty() &&
 353            active_.empty() && inactive_.empty() &&
 354            "interval sets should be empty on initialization");
 355
 356     for (LiveIntervals::Intervals::iterator i = li.begin(), e = li.end();
 357          i != e; ++i) {
 358         if (MRegisterInfo::isPhysicalRegister(i->reg))
 359             fixed_.push_back(&*i);
 360         else
 361             unhandled_.push_back(&*i);
 362     }
 363 }
 364
 365 void RA::processActiveIntervals(IntervalPtrs::value_type cur)
 366 {
 367     DEBUG(std::cerr << "\tprocessing active intervals:\n");
 368     for (IntervalPtrs::iterator i = active_.begin(); i != active_.end();) {
 369         unsigned reg = (*i)->reg;
 370         // remove expired intervals
 371         if ((*i)->expiredAt(cur->start())) {
 372             DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n");
 373             if (MRegisterInfo::isVirtualRegister(reg)) {
 374                 reg = v2pMap_[reg];
 375             }
 376             prt_.delPhysRegUse(reg);
 377             // remove from active
 378             i = active_.erase(i);
 379         }
 380         // move inactive intervals to inactive list
 381         else if (!(*i)->liveAt(cur->start())) {
 382             DEBUG(std::cerr << "\t\t\tinterval " << **i << " inactive\n");
 383             if (MRegisterInfo::isVirtualRegister(reg)) {
 384                 reg = v2pMap_[reg];
 385             }
 386             prt_.delPhysRegUse(reg);
 387             // add to inactive
 388             inactive_.push_back(*i);
 389             // remove from active
 390             i = active_.erase(i);
 391         }
 392         else {
 393             ++i;
 394         }
 395     }
 396 }
 397
 398 void RA::processInactiveIntervals(IntervalPtrs::value_type cur)
 399 {
 400     DEBUG(std::cerr << "\tprocessing inactive intervals:\n");
 401     for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end();) {
 402         unsigned reg = (*i)->reg;
 403
 404         // remove expired intervals
 405         if ((*i)->expiredAt(cur->start())) {
 406             DEBUG(std::cerr << "\t\t\tinterval " << **i << " expired\n");
 407             // remove from inactive
 408             i = inactive_.erase(i);
 409         }
 410         // move re-activated intervals in active list
 411         else if ((*i)->liveAt(cur->start())) {
 412             DEBUG(std::cerr << "\t\t\tinterval " << **i << " active\n");
 413             if (MRegisterInfo::isVirtualRegister(reg)) {
 414                 reg = v2pMap_[reg];
 415             }
 416             prt_.addPhysRegUse(reg);
 417             // add to active
 418             active_.push_back(*i);
 419             // remove from inactive
 420             i = inactive_.erase(i);
 421         }
 422         else {
 423             ++i;
 424         }
 425     }
 426 }
 427
 428 void RA::updateSpillWeights(unsigned reg, SpillWeights::value_type weight)
 429 {
 430     spillWeights_[reg] += weight;
 431     for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as)
 432         spillWeights_[*as] += weight;
 433 }
 434
 435 void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur)
 436 {
 437     DEBUG(std::cerr << "\tallocating current interval:\n");
 438
 439     PhysRegTracker backupPrt = prt_;
 440
 441     spillWeights_.assign(mri_->getNumRegs(), 0.0);
 442
 443     // for each interval in active update spill weights
 444     for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
 445          i != e; ++i) {
 446         unsigned reg = (*i)->reg;
 447         if (MRegisterInfo::isVirtualRegister(reg))
 448             reg = v2pMap_[reg];
 449         updateSpillWeights(reg, (*i)->weight);
 450     }
 451
 452     // for every interval in inactive we overlap with, mark the
 453     // register as not free and update spill weights
 454     for (IntervalPtrs::const_iterator i = inactive_.begin(),
 455              e = inactive_.end(); i != e; ++i) {
 456         if (cur->overlaps(**i)) {
 457             unsigned reg = (*i)->reg;
 458             if (MRegisterInfo::isVirtualRegister(reg))
 459                 reg = v2pMap_[reg];
 460             prt_.addPhysRegUse(reg);
 461             updateSpillWeights(reg, (*i)->weight);
 462         }
 463     }
 464
 465     // for every interval in fixed we overlap with,
 466     // mark the register as not free and update spill weights
 467     for (IntervalPtrs::const_iterator i = fixed_.begin(),
 468              e = fixed_.end(); i != e; ++i) {
 469         if (cur->overlaps(**i)) {
 470             unsigned reg = (*i)->reg;
 471             prt_.addPhysRegUse(reg);
 472             updateSpillWeights(reg, (*i)->weight);
 473         }
 474     }
 475
 476     unsigned physReg = getFreePhysReg(cur);
 477     // restore the physical register tracker
 478     prt_ = backupPrt;
 479     // if we find a free register, we are done: assign this virtual to
 480     // the free physical register and add this interval to the active
 481     // list.
 482     if (physReg) {
 483         assignVirt2PhysReg(cur->reg, physReg);
 484         active_.push_back(cur);
 485         handled_.push_back(cur);
 486         return;
 487     }
 488
 489     DEBUG(std::cerr << "\t\tassigning stack slot at interval "<< *cur << ":\n");
 490     // push the current interval back to unhandled since we are going
 491     // to re-run at least this iteration
 492     unhandled_.push_front(cur);
 493
 494     float minWeight = std::numeric_limits<float>::infinity();
 495     unsigned minReg = 0;
 496     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
 497     for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
 498          i != rc->allocation_order_end(*mf_); ++i) {
 499         unsigned reg = *i;
 500         if (minWeight > spillWeights_[reg]) {
 501             minWeight = spillWeights_[reg];
 502             minReg = reg;
 503         }
 504     }
 505     DEBUG(std::cerr << "\t\t\tregister with min weight: "
 506           << mri_->getName(minReg) << " (" << minWeight << ")\n");
 507
 508     // if the current has the minimum weight, we need to modify it,
 509     // push it back in unhandled and let the linear scan algorithm run
 510     // again
 511     if (cur->weight < minWeight) {
 512         DEBUG(std::cerr << "\t\t\t\tspilling(c): " << *cur;);
 513         int slot = assignVirt2StackSlot(cur->reg);
 514         li_->updateSpilledInterval(*cur);
 515         addSpillCode(cur, slot);
 516         DEBUG(std::cerr << "[ " << *cur << " ]\n");
 517         return;
 518     }
 519
 520     // otherwise we spill all intervals aliasing the register with
 521     // minimum weight, rollback to the interval with the earliest
 522     // start point and let the linear scan algorithm run again
 523     std::vector<bool> toSpill(mri_->getNumRegs(), false);
 524     toSpill[minReg] = true;
 525     for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as)
 526         toSpill[*as] = true;
 527     unsigned earliestStart = cur->start();
 528
 529     for (IntervalPtrs::iterator i = active_.begin();
 530          i != active_.end(); ++i) {
 531         unsigned reg = (*i)->reg;
 532         if (MRegisterInfo::isVirtualRegister(reg) &&
 533             toSpill[v2pMap_[reg]] &&
 534             cur->overlaps(**i)) {
 535             DEBUG(std::cerr << "\t\t\t\tspilling(a): " << **i);
 536             int slot = assignVirt2StackSlot((*i)->reg);
 537             li_->updateSpilledInterval(**i);
 538             addSpillCode(*i, slot);
 539             DEBUG(std::cerr << "[ " << **i << " ]\n");
 540             earliestStart = std::min(earliestStart, (*i)->start());
 541         }
 542     }
 543     for (IntervalPtrs::iterator i = inactive_.begin();
 544          i != inactive_.end(); ++i) {
 545         unsigned reg = (*i)->reg;
 546         if (MRegisterInfo::isVirtualRegister(reg) &&
 547             toSpill[v2pMap_[reg]] &&
 548             cur->overlaps(**i)) {
 549             DEBUG(std::cerr << "\t\t\t\tspilling(i): " << **i << '\n');
 550             int slot = assignVirt2StackSlot((*i)->reg);
 551             li_->updateSpilledInterval(**i);
 552             addSpillCode(*i, slot);
 553             DEBUG(std::cerr << "[ " << **i << " ]\n");
 554             earliestStart = std::min(earliestStart, (*i)->start());
 555         }
 556     }
 557
 558     DEBUG(std::cerr << "\t\t\t\trolling back to: " << earliestStart << '\n');
 559     // scan handled in reverse order and undo each one, restoring the
 560     // state of unhandled and fixed
 561     while (!handled_.empty()) {
 562         IntervalPtrs::value_type i = handled_.back();
 563         // if this interval starts before t we are done
 564         if (i->start() < earliestStart)
 565             break;
 566         DEBUG(std::cerr << "\t\t\t\t\tundo changes for: " << *i << '\n');
 567         handled_.pop_back();
 568         IntervalPtrs::iterator it;
 569         if ((it = find(active_.begin(), active_.end(), i)) != active_.end()) {
 570             active_.erase(it);
 571             if (MRegisterInfo::isPhysicalRegister(i->reg)) {
 572                 fixed_.push_front(i);
 573                 prt_.delPhysRegUse(i->reg);
 574             }
 575             else {
 576                 Virt2PhysMap::iterator v2pIt = v2pMap_.find(i->reg);
 577                 clearVirtReg(v2pIt);
 578                 unhandled_.push_front(i);
 579                 prt_.delPhysRegUse(v2pIt->second);
 580             }
 581         }
 582         else if ((it = find(inactive_.begin(), inactive_.end(), i)) != inactive_.end()) {
 583             inactive_.erase(it);
 584             if (MRegisterInfo::isPhysicalRegister(i->reg))
 585                 fixed_.push_front(i);
 586             else {
 587                 Virt2PhysMap::iterator v2pIt = v2pMap_.find(i->reg);
 588                 clearVirtReg(v2pIt);
 589                 unhandled_.push_front(i);
 590             }
 591         }
 592         else {
 593             if (MRegisterInfo::isPhysicalRegister(i->reg))
 594                 fixed_.push_front(i);
 595             else {
 596                 Virt2PhysMap::iterator v2pIt = v2pMap_.find(i->reg);
 597                 clearVirtReg(v2pIt);
 598                 unhandled_.push_front(i);
 599             }
 600         }
 601     }
 602
 603     // scan the rest and undo each interval that expired after t and
 604     // insert it in active (the next iteration of the algorithm will
 605     // put it in inactive if required)
 606     IntervalPtrs::iterator i = handled_.begin(), e = handled_.end();
 607     for (; i != e; ++i) {
 608         if (!(*i)->expiredAt(earliestStart) && (*i)->expiredAt(cur->start())) {
 609             DEBUG(std::cerr << "\t\t\t\t\tundo changes for: " << **i << '\n');
 610             active_.push_back(*i);
 611             if (MRegisterInfo::isPhysicalRegister((*i)->reg))
 612                 prt_.addPhysRegUse((*i)->reg);
 613             else {
 614                 assert(v2pMap_.count((*i)->reg));
 615                 prt_.addPhysRegUse(v2pMap_.find((*i)->reg)->second);
 616             }
 617         }
 618     }
 619 }
 620
 621 void RA::addSpillCode(IntervalPtrs::value_type li, int slot)
 622 {
 623     // We scan the instructions corresponding to each range. We load
 624     // when we have a use and spill at end of basic blocks or end of
 625     // ranges only if the register was modified.
 626     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(li->reg);
 627
 628     for (LiveIntervals::Interval::Ranges::iterator i = li->ranges.begin(),
 629              e = li->ranges.end(); i != e; ++i) {
 630         unsigned index = i->first & ~1;
 631         unsigned end = i->second;
 632
 633     entry:
 634         bool dirty = false, loaded = false;
 635
 636         // skip deleted instructions. getInstructionFromIndex returns
 637         // null if the instruction was deleted (because of coalescing
 638         // for example)
 639         while (!li_->getInstructionFromIndex(index)) index += 2;
 640         MachineBasicBlock::iterator mi = li_->getInstructionFromIndex(index);
 641         MachineBasicBlock* mbb = mi->getParent();
 642
 643         for (; index < end; index += 2) {
 644             // ignore deleted instructions
 645             while (!li_->getInstructionFromIndex(index)) index += 2;
 646
 647             // if we changed basic block we need to start over
 648             mi = li_->getInstructionFromIndex(index);
 649             if (mbb != mi->getParent()) {
 650                 if (dirty) {
 651                     mi = li_->getInstructionFromIndex(index-2);
 652                     assert(mbb == mi->getParent() &&
 653                            "rewound to wrong instruction?");
 654                     DEBUG(std::cerr << "add store for reg" << li->reg << " to "
 655                           "stack slot " << slot << " after: ";
 656                           mi->print(std::cerr, *tm_));
 657                     ++numStores;
 658                     mri_->storeRegToStackSlot(*mi->getParent(),
 659                                               next(mi), li->reg, slot, rc);
 660                 }
 661                 goto entry;
 662             }
 663
 664             // if it is used in this instruction load it
 665             for (unsigned i = 0; i < mi->getNumOperands(); ++i) {
 666                 MachineOperand& mop = mi->getOperand(i);
 667                 if (mop.isRegister() && mop.getReg() == li->reg &&
 668                     mop.isUse() && !loaded) {
 669                     loaded = true;
 670                     DEBUG(std::cerr << "add load for reg" << li->reg
 671                           << " from stack slot " << slot << " before: ";
 672                           mi->print(std::cerr, *tm_));
 673                     ++numLoads;
 674                     mri_->loadRegFromStackSlot(*mi->getParent(),
 675                                                mi, li->reg, slot, rc);
 676                 }
 677             }
 678
 679             // if it is defined in this instruction mark as dirty
 680             for (unsigned i = 0; i < mi->getNumOperands(); ++i) {
 681                 MachineOperand& mop = mi->getOperand(i);
 682                 if (mop.isRegister() && mop.getReg() == li->reg &&
 683                     mop.isDef())
 684                     dirty = loaded = true;
 685             }
 686         }
 687         if (dirty) {
 688             mi = li_->getInstructionFromIndex(index-2);
 689             assert(mbb == mi->getParent() &&
 690                    "rewound to wrong instruction?");
 691             DEBUG(std::cerr << "add store for reg" << li->reg << " to "
 692                   "stack slot " << slot << " after: ";
 693                   mi->print(std::cerr, *tm_));
 694             ++numStores;
 695             mri_->storeRegToStackSlot(*mi->getParent(),
 696                                       next(mi), li->reg, slot, rc);
 697         }
 698     }
 699 }
 700
 701 unsigned RA::getFreePhysReg(IntervalPtrs::value_type cur)
 702 {
 703     DEBUG(std::cerr << "\t\tgetting free physical register: ");
 704     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
 705
 706     for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
 707          i != rc->allocation_order_end(*mf_); ++i) {
 708         unsigned reg = *i;
 709         if (prt_.isPhysRegAvail(reg)) {
 710             DEBUG(std::cerr << mri_->getName(reg) << '\n');
 711             return reg;
 712         }
 713     }
 714
 715     DEBUG(std::cerr << "no free register\n");
 716     return 0;
 717 }
 718
 719 RA::Virt2PhysMap::iterator
 720 RA::assignVirt2PhysReg(unsigned virtReg, unsigned physReg)
 721 {
 722     bool inserted;
 723     Virt2PhysMap::iterator it;
 724     tie(it, inserted) = v2pMap_.insert(std::make_pair(virtReg, physReg));
 725     assert(inserted && "attempting to assign a virt->phys mapping to an "
 726            "already mapped register");
 727     prt_.addPhysRegUse(physReg);
 728     return it;
 729 }
 730
 731 void RA::clearVirtReg(Virt2PhysMap::iterator it)
 732 {
 733     assert(it != v2pMap_.end() &&
 734            "attempting to clear a not allocated virtual register");
 735     unsigned physReg = it->second;
 736     v2pMap_.erase(it);
 737     DEBUG(std::cerr << "\t\t\tcleared register " << mri_->getName(physReg)
 738           << "\n");
 739 }
 740
 741
 742 int RA::assignVirt2StackSlot(unsigned virtReg)
 743 {
 744     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(virtReg);
 745     int frameIndex = mf_->getFrameInfo()->CreateStackObject(rc);
 746
 747     bool inserted = v2ssMap_.insert(std::make_pair(virtReg, frameIndex)).second;
 748     assert(inserted && "attempt to assign stack slot to spilled register!");
 749     return frameIndex;
 750 }
 751
 752 int RA::getStackSlot(unsigned virtReg)
 753 {
 754     assert(v2ssMap_.count(virtReg) &&
 755            "attempt to get stack slot for a non spilled register");
 756     return v2ssMap_.find(virtReg)->second;
 757 }
 758
 759 FunctionPass* llvm::createLinearScanRegisterAllocator() {
 760     return new RA();
 761 }