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
  14 #define DEBUG_TYPE "regalloc"
  15 #include "llvm/Function.h"
  16 #include "llvm/CodeGen/LiveVariables.h"
  17 #include "llvm/CodeGen/MachineFunctionPass.h"
  18 #include "llvm/CodeGen/MachineInstr.h"
  19 #include "llvm/CodeGen/Passes.h"
  20 #include "llvm/CodeGen/SSARegMap.h"
  21 #include "llvm/Target/MRegisterInfo.h"
  22 #include "llvm/Target/TargetMachine.h"
  23 #include "Support/Debug.h"
  24 #include "Support/Statistic.h"
  25 #include "Support/STLExtras.h"
  26 #include "LiveIntervals.h"
  27 #include "PhysRegTracker.h"
  28 #include "VirtRegMap.h"
  29 #include <algorithm>
  30 #include <cmath>
  31 #include <iostream>
  32 #include <set>
  33
  34 using namespace llvm;
  35
  36 namespace {
  37
  38     Statistic<double> efficiency
  39     ("regalloc", "Ratio of intervals processed over total intervals");
  40
  41     static unsigned numIterations = 0;
  42     static unsigned numIntervals = 0;
  43
  44     class RA : public MachineFunctionPass {
  45     private:
  46         MachineFunction* mf_;
  47         const TargetMachine* tm_;
  48         const MRegisterInfo* mri_;
  49         LiveIntervals* li_;
  50         typedef std::list<LiveInterval*> IntervalPtrs;
  51         IntervalPtrs unhandled_, fixed_, active_, inactive_, handled_;
  52
  53         std::auto_ptr<PhysRegTracker> prt_;
  54         std::auto_ptr<VirtRegMap> vrm_;
  55         std::auto_ptr<Spiller> spiller_;
  56
  57         typedef std::vector<float> SpillWeights;
  58         SpillWeights spillWeights_;
  59
  60     public:
  61         virtual const char* getPassName() const {
  62             return "Linear Scan Register Allocator";
  63         }
  64
  65         virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  66             AU.addRequired<LiveVariables>();
  67             AU.addRequired<LiveIntervals>();
  68             MachineFunctionPass::getAnalysisUsage(AU);
  69         }
  70
  71         /// runOnMachineFunction - register allocate the whole function
  72         bool runOnMachineFunction(MachineFunction&);
  73
  74         void releaseMemory();
  75
  76     private:
  77         /// linearScan - the linear scan algorithm
  78         void linearScan();
  79
  80         /// initIntervalSets - initializa the four interval sets:
  81         /// unhandled, fixed, active and inactive
  82         void initIntervalSets(LiveIntervals::Intervals& li);
  83
  84         /// processActiveIntervals - expire old intervals and move
  85         /// non-overlapping ones to the incative list
  86         void processActiveIntervals(IntervalPtrs::value_type cur);
  87
  88         /// processInactiveIntervals - expire old intervals and move
  89         /// overlapping ones to the active list
  90         void processInactiveIntervals(IntervalPtrs::value_type cur);
  91
  92         /// updateSpillWeights - updates the spill weights of the
  93         /// specifed physical register and its weight
  94         void updateSpillWeights(unsigned reg, SpillWeights::value_type weight);
  95
  96         /// assignRegOrStackSlotAtInterval - assign a register if one
  97         /// is available, or spill.
  98         void assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur);
  99
 100         ///
 101         /// register handling helpers
 102         ///
 103
 104         /// getFreePhysReg - return a free physical register for this
 105         /// virtual register interval if we have one, otherwise return
 106         /// 0
 107         unsigned getFreePhysReg(IntervalPtrs::value_type cur);
 108
 109         /// assignVirt2StackSlot - assigns this virtual register to a
 110         /// stack slot. returns the stack slot
 111         int assignVirt2StackSlot(unsigned virtReg);
 112
 113         void printIntervals(const char* const str,
 114                             RA::IntervalPtrs::const_iterator i,
 115                             RA::IntervalPtrs::const_iterator e) const {
 116             if (str) std::cerr << str << " intervals:\n";
 117             for (; i != e; ++i) {
 118                 std::cerr << "\t" << **i << " -> ";
 119                 unsigned reg = (*i)->reg;
 120                 if (MRegisterInfo::isVirtualRegister(reg)) {
 121                     reg = vrm_->getPhys(reg);
 122                 }
 123                 std::cerr << mri_->getName(reg) << '\n';
 124             }
 125         }
 126
 127 //         void verifyAssignment() const {
 128 //             for (Virt2PhysMap::const_iterator i = v2pMap_.begin(),
 129 //                      e = v2pMap_.end(); i != e; ++i)
 130 //                 for (Virt2PhysMap::const_iterator i2 = next(i); i2 != e; ++i2)
 131 //                     if (MRegisterInfo::isVirtualRegister(i->second) &&
 132 //                         (i->second == i2->second ||
 133 //                          mri_->areAliases(i->second, i2->second))) {
 134 //                         const Interval
 135 //                             &in = li_->getInterval(i->second),
 136 //                             &in2 = li_->getInterval(i2->second);
 137 //                         if (in.overlaps(in2)) {
 138 //                             std::cerr << in << " overlaps " << in2 << '\n';
 139 //                             assert(0);
 140 //                         }
 141 //                     }
 142 //         }
 143     };
 144 }
 145
 146 void RA::releaseMemory()
 147 {
 148     unhandled_.clear();
 149     fixed_.clear();
 150     active_.clear();
 151     inactive_.clear();
 152     handled_.clear();
 153 }
 154
 155 bool RA::runOnMachineFunction(MachineFunction &fn) {
 156     mf_ = &fn;
 157     tm_ = &fn.getTarget();
 158     mri_ = tm_->getRegisterInfo();
 159     li_ = &getAnalysis<LiveIntervals>();
 160     if (!prt_.get()) prt_.reset(new PhysRegTracker(*mri_));
 161     vrm_.reset(new VirtRegMap(*mf_));
 162     if (!spiller_.get()) spiller_.reset(createSpiller());
 163
 164     initIntervalSets(li_->getIntervals());
 165
 166     linearScan();
 167
 168     spiller_->runOnMachineFunction(*mf_, *vrm_);
 169
 170     return true;
 171 }
 172
 173 void RA::linearScan()
 174 {
 175     // linear scan algorithm
 176     DEBUG(std::cerr << "********** LINEAR SCAN **********\n");
 177     DEBUG(std::cerr << "********** Function: "
 178           << mf_->getFunction()->getName() << '\n');
 179
 180     DEBUG(printIntervals("unhandled", unhandled_.begin(), unhandled_.end()));
 181     DEBUG(printIntervals("fixed", fixed_.begin(), fixed_.end()));
 182     DEBUG(printIntervals("active", active_.begin(), active_.end()));
 183     DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
 184
 185     while (!unhandled_.empty()) {
 186         // pick the interval with the earliest start point
 187         IntervalPtrs::value_type cur = unhandled_.front();
 188         unhandled_.pop_front();
 189         ++numIterations;
 190         DEBUG(std::cerr << "\n*** CURRENT ***: " << *cur << '\n');
 191
 192         processActiveIntervals(cur);
 193         processInactiveIntervals(cur);
 194
 195         // if this register is fixed we are done
 196         if (MRegisterInfo::isPhysicalRegister(cur->reg)) {
 197             prt_->addRegUse(cur->reg);
 198             active_.push_back(cur);
 199             handled_.push_back(cur);
 200         }
 201         // otherwise we are allocating a virtual register. try to find
 202         // a free physical register or spill an interval in order to
 203         // assign it one (we could spill the current though).
 204         else {
 205             assignRegOrStackSlotAtInterval(cur);
 206         }
 207
 208         DEBUG(printIntervals("active", active_.begin(), active_.end()));
 209         DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
 210         // DEBUG(verifyAssignment());
 211     }
 212     numIntervals += li_->getIntervals().size();
 213     efficiency = double(numIterations) / double(numIntervals);
 214
 215     // expire any remaining active intervals
 216     for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
 217         unsigned reg = (*i)->reg;
 218         DEBUG(std::cerr << "\tinterval " << **i << " expired\n");
 219         if (MRegisterInfo::isVirtualRegister(reg))
 220             reg = vrm_->getPhys(reg);
 221         prt_->delRegUse(reg);
 222     }
 223
 224     DEBUG(std::cerr << *vrm_);
 225 }
 226
 227 void RA::initIntervalSets(LiveIntervals::Intervals& li)
 228 {
 229     assert(unhandled_.empty() && fixed_.empty() &&
 230            active_.empty() && inactive_.empty() &&
 231            "interval sets should be empty on initialization");
 232
 233     for (LiveIntervals::Intervals::iterator i = li.begin(), e = li.end();
 234          i != e; ++i) {
 235         unhandled_.push_back(&*i);
 236         if (MRegisterInfo::isPhysicalRegister(i->reg))
 237             fixed_.push_back(&*i);
 238     }
 239 }
 240
 241 void RA::processActiveIntervals(IntervalPtrs::value_type cur)
 242 {
 243     DEBUG(std::cerr << "\tprocessing active intervals:\n");
 244     for (IntervalPtrs::iterator i = active_.begin(); i != active_.end();) {
 245         unsigned reg = (*i)->reg;
 246         // remove expired intervals
 247         if ((*i)->expiredAt(cur->start())) {
 248             DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n");
 249             if (MRegisterInfo::isVirtualRegister(reg))
 250                 reg = vrm_->getPhys(reg);
 251             prt_->delRegUse(reg);
 252             // remove from active
 253             i = active_.erase(i);
 254         }
 255         // move inactive intervals to inactive list
 256         else if (!(*i)->liveAt(cur->start())) {
 257             DEBUG(std::cerr << "\t\tinterval " << **i << " inactive\n");
 258             if (MRegisterInfo::isVirtualRegister(reg))
 259                 reg = vrm_->getPhys(reg);
 260             prt_->delRegUse(reg);
 261             // add to inactive
 262             inactive_.push_back(*i);
 263             // remove from active
 264             i = active_.erase(i);
 265         }
 266         else {
 267             ++i;
 268         }
 269     }
 270 }
 271
 272 void RA::processInactiveIntervals(IntervalPtrs::value_type cur)
 273 {
 274     DEBUG(std::cerr << "\tprocessing inactive intervals:\n");
 275     for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end();) {
 276         unsigned reg = (*i)->reg;
 277
 278         // remove expired intervals
 279         if ((*i)->expiredAt(cur->start())) {
 280             DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n");
 281             // remove from inactive
 282             i = inactive_.erase(i);
 283         }
 284         // move re-activated intervals in active list
 285         else if ((*i)->liveAt(cur->start())) {
 286             DEBUG(std::cerr << "\t\tinterval " << **i << " active\n");
 287             if (MRegisterInfo::isVirtualRegister(reg))
 288                 reg = vrm_->getPhys(reg);
 289             prt_->addRegUse(reg);
 290             // add to active
 291             active_.push_back(*i);
 292             // remove from inactive
 293             i = inactive_.erase(i);
 294         }
 295         else {
 296             ++i;
 297         }
 298     }
 299 }
 300
 301 void RA::updateSpillWeights(unsigned reg, SpillWeights::value_type weight)
 302 {
 303     spillWeights_[reg] += weight;
 304     for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as)
 305         spillWeights_[*as] += weight;
 306 }
 307
 308 void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur)
 309 {
 310     DEBUG(std::cerr << "\tallocating current interval: ");
 311
 312     PhysRegTracker backupPrt = *prt_;
 313
 314     spillWeights_.assign(mri_->getNumRegs(), 0.0);
 315
 316     // for each interval in active update spill weights
 317     for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
 318          i != e; ++i) {
 319         unsigned reg = (*i)->reg;
 320         if (MRegisterInfo::isVirtualRegister(reg))
 321             reg = vrm_->getPhys(reg);
 322         updateSpillWeights(reg, (*i)->weight);
 323     }
 324
 325     // for every interval in inactive we overlap with, mark the
 326     // register as not free and update spill weights
 327     for (IntervalPtrs::const_iterator i = inactive_.begin(),
 328              e = inactive_.end(); i != e; ++i) {
 329         if (cur->overlaps(**i)) {
 330             unsigned reg = (*i)->reg;
 331             if (MRegisterInfo::isVirtualRegister(reg))
 332                 reg = vrm_->getPhys(reg);
 333             prt_->addRegUse(reg);
 334             updateSpillWeights(reg, (*i)->weight);
 335         }
 336     }
 337
 338     // for every interval in fixed we overlap with,
 339     // mark the register as not free and update spill weights
 340     for (IntervalPtrs::const_iterator i = fixed_.begin(),
 341              e = fixed_.end(); i != e; ++i) {
 342         if (cur->overlaps(**i)) {
 343             unsigned reg = (*i)->reg;
 344             prt_->addRegUse(reg);
 345             updateSpillWeights(reg, (*i)->weight);
 346         }
 347     }
 348
 349     unsigned physReg = getFreePhysReg(cur);
 350     // restore the physical register tracker
 351     *prt_ = backupPrt;
 352     // if we find a free register, we are done: assign this virtual to
 353     // the free physical register and add this interval to the active
 354     // list.
 355     if (physReg) {
 356         DEBUG(std::cerr <<  mri_->getName(physReg) << '\n');
 357         vrm_->assignVirt2Phys(cur->reg, physReg);
 358         prt_->addRegUse(physReg);
 359         active_.push_back(cur);
 360         handled_.push_back(cur);
 361         return;
 362     }
 363     DEBUG(std::cerr << "no free registers\n");
 364
 365     DEBUG(std::cerr << "\tassigning stack slot at interval "<< *cur << ":\n");
 366
 367     float minWeight = HUGE_VAL;
 368     unsigned minReg = 0;
 369     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
 370     for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
 371          i != rc->allocation_order_end(*mf_); ++i) {
 372         unsigned reg = *i;
 373         if (minWeight > spillWeights_[reg]) {
 374             minWeight = spillWeights_[reg];
 375             minReg = reg;
 376         }
 377     }
 378     DEBUG(std::cerr << "\t\tregister with min weight: "
 379           << mri_->getName(minReg) << " (" << minWeight << ")\n");
 380
 381     // if the current has the minimum weight, we need to spill it and
 382     // add any added intervals back to unhandled, and restart
 383     // linearscan.
 384     if (cur->weight <= minWeight) {
 385         DEBUG(std::cerr << "\t\t\tspilling(c): " << *cur << '\n';);
 386         int slot = vrm_->assignVirt2StackSlot(cur->reg);
 387         std::vector<LiveInterval*> added =
 388             li_->addIntervalsForSpills(*cur, *vrm_, slot);
 389         if (added.empty())
 390           return;  // Early exit if all spills were folded.
 391 #ifndef NDEBUG
 392         int OldStart = -1;
 393 #endif
 394
 395         // Merge added with unhandled.  Note that we know that
 396         // addIntervalsForSpills returns intervals sorted by their starting
 397         // point.
 398         std::vector<LiveInterval*>::iterator addedIt = added.begin();
 399         std::vector<LiveInterval*>::iterator addedItEnd = added.end();
 400         for (IntervalPtrs::iterator i = unhandled_.begin(), e =unhandled_.end();
 401              i != e && addedIt != addedItEnd; ++i) {
 402             while ((*i)->start() > (*addedIt)->start() &&
 403                    addedIt != addedItEnd) {
 404 #ifndef NDEBUG
 405                 // This code only works if addIntervalsForSpills retursn a
 406                 // sorted interval list.  Assert this is the case now.
 407                 assert(OldStart <= (int)(*addedIt)->start() &&
 408                    "addIntervalsForSpills didn't return sorted interval list!");
 409                 OldStart = (*addedIt)->start();
 410 #endif
 411                 i = unhandled_.insert(i, *(addedIt++));
 412             }
 413         }
 414
 415         while (addedIt != addedItEnd) {
 416 #ifndef NDEBUG
 417                 // This code only works if addIntervalsForSpills retursn a
 418                 // sorted interval list.  Assert this is the case now.
 419                 assert(OldStart <= (int)(*addedIt)->start() &&
 420                    "addIntervalsForSpills didn't return sorted interval list!");
 421                 OldStart = (*addedIt)->start();
 422 #endif
 423             unhandled_.push_back(*(addedIt++));
 424         }
 425         return;
 426     }
 427
 428     // push the current interval back to unhandled since we are going
 429     // to re-run at least this iteration. Since we didn't modify it it
 430     // should go back right in the front of the list
 431     unhandled_.push_front(cur);
 432
 433     // otherwise we spill all intervals aliasing the register with
 434     // minimum weight, rollback to the interval with the earliest
 435     // start point and let the linear scan algorithm run again
 436     std::vector<LiveInterval*> added;
 437     assert(MRegisterInfo::isPhysicalRegister(minReg) &&
 438            "did not choose a register to spill?");
 439     std::vector<bool> toSpill(mri_->getNumRegs(), false);
 440     toSpill[minReg] = true;
 441     for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as)
 442         toSpill[*as] = true;
 443     unsigned earliestStart = cur->start();
 444
 445     std::set<unsigned> spilled;
 446
 447     for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
 448         unsigned reg = (*i)->reg;
 449         if (MRegisterInfo::isVirtualRegister(reg) &&
 450             toSpill[vrm_->getPhys(reg)] &&
 451             cur->overlaps(**i)) {
 452             DEBUG(std::cerr << "\t\t\tspilling(a): " << **i << '\n');
 453             earliestStart = std::min(earliestStart, (*i)->start());
 454             int slot = vrm_->assignVirt2StackSlot((*i)->reg);
 455             std::vector<LiveInterval*> newIs =
 456                 li_->addIntervalsForSpills(**i, *vrm_, slot);
 457             std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
 458             spilled.insert(reg);
 459         }
 460     }
 461     for (IntervalPtrs::iterator i = inactive_.begin();
 462          i != inactive_.end(); ++i) {
 463         unsigned reg = (*i)->reg;
 464         if (MRegisterInfo::isVirtualRegister(reg) &&
 465             toSpill[vrm_->getPhys(reg)] &&
 466             cur->overlaps(**i)) {
 467             DEBUG(std::cerr << "\t\t\tspilling(i): " << **i << '\n');
 468             earliestStart = std::min(earliestStart, (*i)->start());
 469             int slot = vrm_->assignVirt2StackSlot((*i)->reg);
 470             std::vector<LiveInterval*> newIs =
 471                 li_->addIntervalsForSpills(**i, *vrm_, slot);
 472             std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
 473             spilled.insert(reg);
 474         }
 475     }
 476
 477     DEBUG(std::cerr << "\t\trolling back to: " << earliestStart << '\n');
 478     // scan handled in reverse order and undo each one, restoring the
 479     // state of unhandled
 480     while (!handled_.empty()) {
 481         IntervalPtrs::value_type i = handled_.back();
 482         // if this interval starts before t we are done
 483         if (i->start() < earliestStart)
 484             break;
 485         DEBUG(std::cerr << "\t\t\tundo changes for: " << *i << '\n');
 486         handled_.pop_back();
 487         IntervalPtrs::iterator it;
 488         if ((it = find(active_.begin(), active_.end(), i)) != active_.end()) {
 489             active_.erase(it);
 490             if (MRegisterInfo::isPhysicalRegister(i->reg)) {
 491                 prt_->delRegUse(i->reg);
 492                 unhandled_.push_front(i);
 493             }
 494             else {
 495                 if (!spilled.count(i->reg))
 496                     unhandled_.push_front(i);
 497                 prt_->delRegUse(vrm_->getPhys(i->reg));
 498                 vrm_->clearVirt(i->reg);
 499             }
 500         }
 501         else if ((it = find(inactive_.begin(), inactive_.end(), i)) != inactive_.end()) {
 502             inactive_.erase(it);
 503             if (MRegisterInfo::isPhysicalRegister(i->reg))
 504                 unhandled_.push_front(i);
 505             else {
 506                 if (!spilled.count(i->reg))
 507                     unhandled_.push_front(i);
 508                 vrm_->clearVirt(i->reg);
 509             }
 510         }
 511         else {
 512             if (MRegisterInfo::isVirtualRegister(i->reg))
 513                 vrm_->clearVirt(i->reg);
 514             unhandled_.push_front(i);
 515         }
 516     }
 517
 518     // scan the rest and undo each interval that expired after t and
 519     // insert it in active (the next iteration of the algorithm will
 520     // put it in inactive if required)
 521     IntervalPtrs::iterator i = handled_.begin(), e = handled_.end();
 522     for (; i != e; ++i) {
 523         if (!(*i)->expiredAt(earliestStart) && (*i)->expiredAt(cur->start())) {
 524             DEBUG(std::cerr << "\t\t\tundo changes for: " << **i << '\n');
 525             active_.push_back(*i);
 526             if (MRegisterInfo::isPhysicalRegister((*i)->reg))
 527                 prt_->addRegUse((*i)->reg);
 528             else
 529                 prt_->addRegUse(vrm_->getPhys((*i)->reg));
 530         }
 531     }
 532
 533     std::sort(added.begin(), added.end(), less_ptr<LiveInterval>());
 534     // merge added with unhandled
 535     std::vector<LiveInterval*>::iterator addedIt = added.begin();
 536     std::vector<LiveInterval*>::iterator addedItEnd = added.end();
 537     for (IntervalPtrs::iterator i = unhandled_.begin(), e = unhandled_.end();
 538          i != e && addedIt != addedItEnd; ++i) {
 539         if ((*i)->start() > (*addedIt)->start())
 540             i = unhandled_.insert(i, *(addedIt++));
 541     }
 542     while (addedIt != addedItEnd)
 543         unhandled_.push_back(*(addedIt++));
 544
 545 }
 546
 547 unsigned RA::getFreePhysReg(IntervalPtrs::value_type cur)
 548 {
 549     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
 550
 551     for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
 552          i != rc->allocation_order_end(*mf_); ++i) {
 553         unsigned reg = *i;
 554         if (prt_->isRegAvail(reg))
 555             return reg;
 556     }
 557     return 0;
 558 }
 559
 560 FunctionPass* llvm::createLinearScanRegisterAllocator() {
 561     return new RA();
 562 }