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     fixed_.clear();
 139     active_.clear();
 140     inactive_.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()) {
 175         // pick the interval with the earliest start point
 176         IntervalPtrs::value_type cur = unhandled_.front();
 177         unhandled_.pop_front();
 178
 179         DEBUG(std::cerr << "\n*** CURRENT ***: " << *cur << '\n');
 180
 181         processActiveIntervals(cur);
 182         processInactiveIntervals(cur);
 183
 184         // if this register is fixed we are done
 185         if (MRegisterInfo::isPhysicalRegister(cur->reg)) {
 186             prt_->addRegUse(cur->reg);
 187             active_.push_back(cur);
 188             handled_.push_back(cur);
 189         }
 190         // otherwise we are allocating a virtual register. try to find
 191         // a free physical register or spill an interval in order to
 192         // assign it one (we could spill the current though).
 193         else {
 194             assignRegOrStackSlotAtInterval(cur);
 195         }
 196
 197         DEBUG(printIntervals("active", active_.begin(), active_.end()));
 198         DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
 199         // DEBUG(verifyAssignment());
 200     }
 201
 202     // expire any remaining active intervals
 203     for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
 204         unsigned reg = (*i)->reg;
 205         DEBUG(std::cerr << "\tinterval " << **i << " expired\n");
 206         if (MRegisterInfo::isVirtualRegister(reg))
 207             reg = vrm_->getPhys(reg);
 208         prt_->delRegUse(reg);
 209     }
 210
 211     DEBUG(std::cerr << *vrm_);
 212 }
 213
 214 void RA::initIntervalSets(LiveIntervals::Intervals& li)
 215 {
 216     assert(unhandled_.empty() && fixed_.empty() &&
 217            active_.empty() && inactive_.empty() &&
 218            "interval sets should be empty on initialization");
 219
 220     for (LiveIntervals::Intervals::iterator i = li.begin(), e = li.end();
 221          i != e; ++i) {
 222         unhandled_.push_back(&*i);
 223         if (MRegisterInfo::isPhysicalRegister(i->reg))
 224             fixed_.push_back(&*i);
 225     }
 226 }
 227
 228 void RA::processActiveIntervals(IntervalPtrs::value_type cur)
 229 {
 230     DEBUG(std::cerr << "\tprocessing active intervals:\n");
 231     for (IntervalPtrs::iterator i = active_.begin(); i != active_.end();) {
 232         unsigned reg = (*i)->reg;
 233         // remove expired intervals
 234         if ((*i)->expiredAt(cur->start())) {
 235             DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n");
 236             if (MRegisterInfo::isVirtualRegister(reg))
 237                 reg = vrm_->getPhys(reg);
 238             prt_->delRegUse(reg);
 239             // remove from active
 240             i = active_.erase(i);
 241         }
 242         // move inactive intervals to inactive list
 243         else if (!(*i)->liveAt(cur->start())) {
 244             DEBUG(std::cerr << "\t\tinterval " << **i << " inactive\n");
 245             if (MRegisterInfo::isVirtualRegister(reg))
 246                 reg = vrm_->getPhys(reg);
 247             prt_->delRegUse(reg);
 248             // add to inactive
 249             inactive_.push_back(*i);
 250             // remove from active
 251             i = active_.erase(i);
 252         }
 253         else {
 254             ++i;
 255         }
 256     }
 257 }
 258
 259 void RA::processInactiveIntervals(IntervalPtrs::value_type cur)
 260 {
 261     DEBUG(std::cerr << "\tprocessing inactive intervals:\n");
 262     for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end();) {
 263         unsigned reg = (*i)->reg;
 264
 265         // remove expired intervals
 266         if ((*i)->expiredAt(cur->start())) {
 267             DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n");
 268             // remove from inactive
 269             i = inactive_.erase(i);
 270         }
 271         // move re-activated intervals in active list
 272         else if ((*i)->liveAt(cur->start())) {
 273             DEBUG(std::cerr << "\t\tinterval " << **i << " active\n");
 274             if (MRegisterInfo::isVirtualRegister(reg))
 275                 reg = vrm_->getPhys(reg);
 276             prt_->addRegUse(reg);
 277             // add to active
 278             active_.push_back(*i);
 279             // remove from inactive
 280             i = inactive_.erase(i);
 281         }
 282         else {
 283             ++i;
 284         }
 285     }
 286 }
 287
 288 void RA::updateSpillWeights(unsigned reg, SpillWeights::value_type weight)
 289 {
 290     spillWeights_[reg] += weight;
 291     for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as)
 292         spillWeights_[*as] += weight;
 293 }
 294
 295 void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur)
 296 {
 297     DEBUG(std::cerr << "\tallocating current interval: ");
 298
 299     PhysRegTracker backupPrt = *prt_;
 300
 301     spillWeights_.assign(mri_->getNumRegs(), 0.0);
 302
 303     // for each interval in active update spill weights
 304     for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
 305          i != e; ++i) {
 306         unsigned reg = (*i)->reg;
 307         if (MRegisterInfo::isVirtualRegister(reg))
 308             reg = vrm_->getPhys(reg);
 309         updateSpillWeights(reg, (*i)->weight);
 310     }
 311
 312     // for every interval in inactive we overlap with, mark the
 313     // register as not free and update spill weights
 314     for (IntervalPtrs::const_iterator i = inactive_.begin(),
 315              e = inactive_.end(); i != e; ++i) {
 316         if (cur->overlaps(**i)) {
 317             unsigned reg = (*i)->reg;
 318             if (MRegisterInfo::isVirtualRegister(reg))
 319                 reg = vrm_->getPhys(reg);
 320             prt_->addRegUse(reg);
 321             updateSpillWeights(reg, (*i)->weight);
 322         }
 323     }
 324
 325     // for every interval in fixed we overlap with,
 326     // mark the register as not free and update spill weights
 327     for (IntervalPtrs::const_iterator i = fixed_.begin(),
 328              e = fixed_.end(); i != e; ++i) {
 329         if (cur->overlaps(**i)) {
 330             unsigned reg = (*i)->reg;
 331             prt_->addRegUse(reg);
 332             updateSpillWeights(reg, (*i)->weight);
 333         }
 334     }
 335
 336     unsigned physReg = getFreePhysReg(cur);
 337     // restore the physical register tracker
 338     *prt_ = backupPrt;
 339     // if we find a free register, we are done: assign this virtual to
 340     // the free physical register and add this interval to the active
 341     // list.
 342     if (physReg) {
 343         DEBUG(std::cerr <<  mri_->getName(physReg) << '\n');
 344         vrm_->assignVirt2Phys(cur->reg, physReg);
 345         prt_->addRegUse(physReg);
 346         active_.push_back(cur);
 347         handled_.push_back(cur);
 348         return;
 349     }
 350     DEBUG(std::cerr << "no free registers\n");
 351
 352     DEBUG(std::cerr << "\tassigning stack slot at interval "<< *cur << ":\n");
 353
 354     float minWeight = std::numeric_limits<float>::infinity();
 355     unsigned minReg = 0;
 356     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
 357     for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
 358          i != rc->allocation_order_end(*mf_); ++i) {
 359         unsigned reg = *i;
 360         if (minWeight > spillWeights_[reg]) {
 361             minWeight = spillWeights_[reg];
 362             minReg = reg;
 363         }
 364     }
 365     DEBUG(std::cerr << "\t\tregister with min weight: "
 366           << mri_->getName(minReg) << " (" << minWeight << ")\n");
 367
 368     // if the current has the minimum weight, we need to modify it,
 369     // push it back in unhandled and let the linear scan algorithm run
 370     // again
 371     if (cur->weight <= minWeight) {
 372         DEBUG(std::cerr << "\t\t\tspilling(c): " << *cur << '\n';);
 373         int slot = vrm_->assignVirt2StackSlot(cur->reg);
 374         li_->updateSpilledInterval(*cur, *vrm_, slot);
 375
 376         // if we didn't eliminate the interval find where to add it
 377         // back to unhandled. We need to scan since unhandled are
 378         // sorted on earliest start point and we may have changed our
 379         // start point.
 380         if (!cur->empty()) {
 381             IntervalPtrs::iterator it = unhandled_.begin();
 382             while (it != unhandled_.end() && (*it)->start() < cur->start())
 383                 ++it;
 384             unhandled_.insert(it, cur);
 385         }
 386         return;
 387     }
 388
 389     // push the current interval back to unhandled since we are going
 390     // to re-run at least this iteration. Since we didn't modify it it
 391     // should go back right in the front of the list
 392     unhandled_.push_front(cur);
 393
 394     // otherwise we spill all intervals aliasing the register with
 395     // minimum weight, rollback to the interval with the earliest
 396     // start point and let the linear scan algorithm run again
 397     assert(MRegisterInfo::isPhysicalRegister(minReg) &&
 398            "did not choose a register to spill?");
 399     std::vector<bool> toSpill(mri_->getNumRegs(), false);
 400     toSpill[minReg] = true;
 401     for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as)
 402         toSpill[*as] = true;
 403     unsigned earliestStart = cur->start();
 404
 405     for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
 406         unsigned reg = (*i)->reg;
 407         if (MRegisterInfo::isVirtualRegister(reg) &&
 408             toSpill[vrm_->getPhys(reg)] &&
 409             cur->overlaps(**i)) {
 410             DEBUG(std::cerr << "\t\t\tspilling(a): " << **i << '\n');
 411             earliestStart = std::min(earliestStart, (*i)->start());
 412             int slot = vrm_->assignVirt2StackSlot((*i)->reg);
 413             li_->updateSpilledInterval(**i, *vrm_, slot);
 414         }
 415     }
 416     for (IntervalPtrs::iterator i = inactive_.begin();
 417          i != inactive_.end(); ++i) {
 418         unsigned reg = (*i)->reg;
 419         if (MRegisterInfo::isVirtualRegister(reg) &&
 420             toSpill[vrm_->getPhys(reg)] &&
 421             cur->overlaps(**i)) {
 422             DEBUG(std::cerr << "\t\t\tspilling(i): " << **i << '\n');
 423             earliestStart = std::min(earliestStart, (*i)->start());
 424             int slot = vrm_->assignVirt2StackSlot((*i)->reg);
 425             li_->updateSpilledInterval(**i, *vrm_, slot);
 426         }
 427     }
 428
 429     DEBUG(std::cerr << "\t\trolling back to: " << earliestStart << '\n');
 430     // scan handled in reverse order and undo each one, restoring the
 431     // state of unhandled
 432     while (!handled_.empty()) {
 433         IntervalPtrs::value_type i = handled_.back();
 434         // if this interval starts before t we are done
 435         if (!i->empty() && i->start() < earliestStart)
 436             break;
 437         DEBUG(std::cerr << "\t\t\tundo changes for: " << *i << '\n');
 438         handled_.pop_back();
 439         IntervalPtrs::iterator it;
 440         if ((it = find(active_.begin(), active_.end(), i)) != active_.end()) {
 441             active_.erase(it);
 442             if (MRegisterInfo::isPhysicalRegister(i->reg)) {
 443                 prt_->delRegUse(i->reg);
 444                 unhandled_.push_front(i);
 445             }
 446             else {
 447                 prt_->delRegUse(vrm_->getPhys(i->reg));
 448                 vrm_->clearVirt(i->reg);
 449                 if (i->spilled()) {
 450                     if (!i->empty()) {
 451                         IntervalPtrs::iterator it = unhandled_.begin();
 452                         while (it != unhandled_.end() &&
 453                                (*it)->start() < i->start())
 454                             ++it;
 455                         unhandled_.insert(it, i);
 456                     }
 457                 }
 458                 else
 459                     unhandled_.push_front(i);
 460
 461             }
 462         }
 463         else if ((it = find(inactive_.begin(), inactive_.end(), i)) != inactive_.end()) {
 464             inactive_.erase(it);
 465             if (MRegisterInfo::isPhysicalRegister(i->reg))
 466                 unhandled_.push_front(i);
 467             else {
 468                 vrm_->clearVirt(i->reg);
 469                 if (i->spilled()) {
 470                     if (!i->empty()) {
 471                         IntervalPtrs::iterator it = unhandled_.begin();
 472                         while (it != unhandled_.end() &&
 473                                (*it)->start() < i->start())
 474                             ++it;
 475                         unhandled_.insert(it, i);
 476                     }
 477                 }
 478                 else
 479                     unhandled_.push_front(i);
 480             }
 481         }
 482         else {
 483             if (MRegisterInfo::isVirtualRegister(i->reg))
 484                 vrm_->clearVirt(i->reg);
 485             unhandled_.push_front(i);
 486         }
 487     }
 488
 489     // scan the rest and undo each interval that expired after t and
 490     // insert it in active (the next iteration of the algorithm will
 491     // put it in inactive if required)
 492     IntervalPtrs::iterator i = handled_.begin(), e = handled_.end();
 493     for (; i != e; ++i) {
 494         if (!(*i)->expiredAt(earliestStart) && (*i)->expiredAt(cur->start())) {
 495             DEBUG(std::cerr << "\t\t\tundo changes for: " << **i << '\n');
 496             active_.push_back(*i);
 497             if (MRegisterInfo::isPhysicalRegister((*i)->reg))
 498                 prt_->addRegUse((*i)->reg);
 499             else
 500                 prt_->addRegUse(vrm_->getPhys((*i)->reg));
 501         }
 502     }
 503 }
 504
 505 unsigned RA::getFreePhysReg(IntervalPtrs::value_type cur)
 506 {
 507     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
 508
 509     for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
 510          i != rc->allocation_order_end(*mf_); ++i) {
 511         unsigned reg = *i;
 512         if (prt_->isRegAvail(reg))
 513             return reg;
 514     }
 515     return 0;
 516 }
 517
 518 FunctionPass* llvm::createLinearScanRegisterAllocator() {
 519     return new RA();
 520 }