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