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