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