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