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