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