lib/CodeGen/RegAllocIterativeScan.cpp

   1 //===-- RegAllocIterativeScan.cpp - Iterative 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 an iterative scan register
  11 // allocator. Iterative scan is a linear scan variant with the
  12 // following difference:
  13 //
  14 // It performs linear scan and keeps a list of the registers it cannot
  15 // allocate. It then spills all those registers and repeats the
  16 // process until allocation succeeds.
  17 //
  18 //===----------------------------------------------------------------------===//
  19
  20 #define DEBUG_TYPE "regalloc"
  21 #include "llvm/Function.h"
  22 #include "llvm/CodeGen/MachineFunctionPass.h"
  23 #include "llvm/CodeGen/MachineInstr.h"
  24 #include "llvm/CodeGen/Passes.h"
  25 #include "llvm/CodeGen/SSARegMap.h"
  26 #include "llvm/Target/MRegisterInfo.h"
  27 #include "llvm/Target/TargetMachine.h"
  28 #include "llvm/Support/Debug.h"
  29 #include "llvm/ADT/Statistic.h"
  30 #include "llvm/ADT/STLExtras.h"
  31 #include "LiveIntervalAnalysis.h"
  32 #include "PhysRegTracker.h"
  33 #include "VirtRegMap.h"
  34 #include <algorithm>
  35 #include <cmath>
  36 #include <set>
  37
  38 using namespace llvm;
  39
  40 namespace {
  41
  42   Statistic<double> efficiency
  43   ("regalloc", "Ratio of intervals processed over total intervals");
  44
  45   static unsigned numIterations = 0;
  46   static unsigned numIntervals = 0;
  47
  48   class RA : public MachineFunctionPass {
  49   private:
  50     MachineFunction* mf_;
  51     const TargetMachine* tm_;
  52     const MRegisterInfo* mri_;
  53     LiveIntervals* li_;
  54     typedef std::vector<LiveInterval*> IntervalPtrs;
  55     IntervalPtrs unhandled_, fixed_, active_, inactive_, handled_, spilled_;
  56
  57     std::auto_ptr<PhysRegTracker> prt_;
  58     std::auto_ptr<VirtRegMap> vrm_;
  59     std::auto_ptr<Spiller> spiller_;
  60
  61     typedef std::vector<float> SpillWeights;
  62     SpillWeights spillWeights_;
  63
  64   public:
  65     virtual const char* getPassName() const {
  66       return "Iterative Scan Register Allocator";
  67     }
  68
  69     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  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. Returns a boolean
  81     /// indicating if there were any spills
  82     bool linearScan();
  83
  84     /// initIntervalSets - initializes the four interval sets:
  85     /// unhandled, fixed, active and inactive
  86     void initIntervalSets();
  87
  88     /// processActiveIntervals - expire old intervals and move
  89     /// non-overlapping ones to the incative list
  90     void processActiveIntervals(IntervalPtrs::value_type cur);
  91
  92     /// processInactiveIntervals - expire old intervals and move
  93     /// overlapping ones to the active list
  94     void processInactiveIntervals(IntervalPtrs::value_type cur);
  95
  96     /// updateSpillWeights - updates the spill weights of the
  97     /// specifed physical register and its weight
  98     void updateSpillWeights(unsigned reg, SpillWeights::value_type weight);
  99
 100     /// assignRegOrStackSlotAtInterval - assign a register if one
 101     /// is available, or spill.
 102     void assignRegOrSpillAtInterval(IntervalPtrs::value_type cur);
 103
 104     ///
 105     /// register handling helpers
 106     ///
 107
 108     /// getFreePhysReg - return a free physical register for this
 109     /// virtual register interval if we have one, otherwise return
 110     /// 0
 111     unsigned getFreePhysReg(IntervalPtrs::value_type cur);
 112
 113     /// assignVirt2StackSlot - assigns this virtual register to a
 114     /// stack slot. returns the stack slot
 115     int assignVirt2StackSlot(unsigned virtReg);
 116
 117     void printIntervals(const char* const str,
 118                         RA::IntervalPtrs::const_iterator i,
 119                         RA::IntervalPtrs::const_iterator e) const {
 120       if (str) std::cerr << str << " intervals:\n";
 121       for (; i != e; ++i) {
 122         std::cerr << "\t" << **i << " -> ";
 123         unsigned reg = (*i)->reg;
 124         if (MRegisterInfo::isVirtualRegister(reg)) {
 125           reg = vrm_->getPhys(reg);
 126         }
 127         std::cerr << mri_->getName(reg) << '\n';
 128       }
 129     }
 130   };
 131 }
 132
 133 void RA::releaseMemory()
 134 {
 135   unhandled_.clear();
 136   fixed_.clear();
 137   active_.clear();
 138   inactive_.clear();
 139   handled_.clear();
 140   spilled_.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   if (!spiller_.get()) spiller_.reset(createSpiller());
 151
 152   initIntervalSets();
 153
 154   numIntervals += li_->getNumIntervals();
 155
 156   while (linearScan()) {
 157     // we spilled some registers, so we need to add intervals for
 158     // the spill code and restart the algorithm
 159     std::set<unsigned> spilledRegs;
 160     for (IntervalPtrs::iterator
 161            i = spilled_.begin(); i != spilled_.end(); ++i) {
 162       int slot = vrm_->assignVirt2StackSlot((*i)->reg);
 163       std::vector<LiveInterval*> added =
 164         li_->addIntervalsForSpills(**i, *vrm_, slot);
 165       std::copy(added.begin(), added.end(), std::back_inserter(handled_));
 166       spilledRegs.insert((*i)->reg);
 167     }
 168     spilled_.clear();
 169     for (IntervalPtrs::iterator
 170            i = handled_.begin(); i != handled_.end(); )
 171       if (spilledRegs.count((*i)->reg))
 172         i = handled_.erase(i);
 173       else
 174         ++i;
 175     handled_.swap(unhandled_);
 176     vrm_->clearAllVirt();
 177   }
 178
 179   efficiency = double(numIterations) / double(numIntervals);
 180
 181   DEBUG(std::cerr << *vrm_);
 182
 183   spiller_->runOnMachineFunction(*mf_, *vrm_);
 184
 185   return true;
 186 }
 187
 188 bool RA::linearScan()
 189 {
 190   // linear scan algorithm
 191   DEBUG(std::cerr << "********** LINEAR SCAN **********\n");
 192   DEBUG(std::cerr << "********** Function: "
 193         << mf_->getFunction()->getName() << '\n');
 194
 195
 196   std::sort(unhandled_.begin(), unhandled_.end(),
 197             greater_ptr<LiveInterval>());
 198   DEBUG(printIntervals("unhandled", unhandled_.begin(), unhandled_.end()));
 199   DEBUG(printIntervals("fixed", fixed_.begin(), fixed_.end()));
 200   DEBUG(printIntervals("active", active_.begin(), active_.end()));
 201   DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
 202
 203   while (!unhandled_.empty()) {
 204     // pick the interval with the earliest start point
 205     IntervalPtrs::value_type cur = unhandled_.back();
 206     unhandled_.pop_back();
 207     ++numIterations;
 208     DEBUG(std::cerr << "\n*** CURRENT ***: " << *cur << '\n');
 209
 210     processActiveIntervals(cur);
 211     processInactiveIntervals(cur);
 212
 213     // if this register is fixed we are done
 214     if (MRegisterInfo::isPhysicalRegister(cur->reg)) {
 215       prt_->addRegUse(cur->reg);
 216       active_.push_back(cur);
 217       handled_.push_back(cur);
 218     }
 219     // otherwise we are allocating a virtual register. try to find
 220     // a free physical register or spill an interval in order to
 221     // assign it one (we could spill the current though).
 222     else {
 223       assignRegOrSpillAtInterval(cur);
 224     }
 225
 226     DEBUG(printIntervals("active", active_.begin(), active_.end()));
 227     DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
 228   }
 229
 230   // expire any remaining active intervals
 231   for (IntervalPtrs::reverse_iterator
 232          i = active_.rbegin(); i != active_.rend(); ) {
 233     unsigned reg = (*i)->reg;
 234     DEBUG(std::cerr << "\tinterval " << **i << " expired\n");
 235     if (MRegisterInfo::isVirtualRegister(reg))
 236       reg = vrm_->getPhys(reg);
 237     prt_->delRegUse(reg);
 238     i = IntervalPtrs::reverse_iterator(active_.erase(i.base()-1));
 239   }
 240
 241   // expire any remaining inactive intervals
 242   for (IntervalPtrs::reverse_iterator
 243          i = inactive_.rbegin(); i != inactive_.rend(); ) {
 244     DEBUG(std::cerr << "\tinterval " << **i << " expired\n");
 245     i = IntervalPtrs::reverse_iterator(inactive_.erase(i.base()-1));
 246   }
 247
 248   // return true if we spilled anything
 249   return !spilled_.empty();
 250 }
 251
 252 void RA::initIntervalSets() {
 253   assert(unhandled_.empty() && fixed_.empty() &&
 254          active_.empty() && inactive_.empty() &&
 255          "interval sets should be empty on initialization");
 256
 257   for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i){
 258     unhandled_.push_back(&i->second);
 259     if (MRegisterInfo::isPhysicalRegister(i->second.reg))
 260       fixed_.push_back(&i->second);
 261   }
 262 }
 263
 264 void RA::processActiveIntervals(IntervalPtrs::value_type cur)
 265 {
 266   DEBUG(std::cerr << "\tprocessing active intervals:\n");
 267   IntervalPtrs::iterator ii = active_.begin(), ie = active_.end();
 268   while (ii != ie) {
 269     LiveInterval* i = *ii;
 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       if (MRegisterInfo::isVirtualRegister(reg))
 276         reg = vrm_->getPhys(reg);
 277       prt_->delRegUse(reg);
 278       // swap with last element and move end iterator back one position
 279       std::iter_swap(ii, --ie);
 280     }
 281     // move inactive intervals to inactive list
 282     else if (!i->liveAt(cur->start())) {
 283       DEBUG(std::cerr << "\t\tinterval " << *i << " inactive\n");
 284       if (MRegisterInfo::isVirtualRegister(reg))
 285         reg = vrm_->getPhys(reg);
 286       prt_->delRegUse(reg);
 287       // add to inactive
 288       inactive_.push_back(i);
 289       // swap with last element and move end iterator back one postion
 290       std::iter_swap(ii, --ie);
 291     }
 292     else {
 293       ++ii;
 294     }
 295   }
 296   active_.erase(ie, active_.end());
 297 }
 298
 299 void RA::processInactiveIntervals(IntervalPtrs::value_type cur)
 300 {
 301   DEBUG(std::cerr << "\tprocessing inactive intervals:\n");
 302   IntervalPtrs::iterator ii = inactive_.begin(), ie = inactive_.end();
 303   while (ii != ie) {
 304     LiveInterval* i = *ii;
 305     unsigned reg = i->reg;
 306
 307     // remove expired intervals
 308     if (i->expiredAt(cur->start())) {
 309       DEBUG(std::cerr << "\t\tinterval " << *i << " expired\n");
 310       // swap with last element and move end iterator back one position
 311       std::iter_swap(ii, --ie);
 312     }
 313     // move re-activated intervals in active list
 314     else if (i->liveAt(cur->start())) {
 315       DEBUG(std::cerr << "\t\tinterval " << *i << " active\n");
 316       if (MRegisterInfo::isVirtualRegister(reg))
 317         reg = vrm_->getPhys(reg);
 318       prt_->addRegUse(reg);
 319       // add to active
 320       active_.push_back(i);
 321       // swap with last element and move end iterator back one position
 322       std::iter_swap(ii, --ie);
 323     }
 324     else {
 325       ++ii;
 326     }
 327   }
 328   inactive_.erase(ie, inactive_.end());
 329 }
 330
 331 void RA::updateSpillWeights(unsigned reg, SpillWeights::value_type weight)
 332 {
 333   spillWeights_[reg] += weight;
 334   for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as)
 335     spillWeights_[*as] += weight;
 336 }
 337
 338 void RA::assignRegOrSpillAtInterval(IntervalPtrs::value_type cur)
 339 {
 340   DEBUG(std::cerr << "\tallocating current interval: ");
 341
 342   PhysRegTracker backupPrt = *prt_;
 343
 344   spillWeights_.assign(mri_->getNumRegs(), 0.0);
 345
 346   // for each interval in active update spill weights
 347   for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
 348        i != e; ++i) {
 349     unsigned reg = (*i)->reg;
 350     if (MRegisterInfo::isVirtualRegister(reg))
 351       reg = vrm_->getPhys(reg);
 352     updateSpillWeights(reg, (*i)->weight);
 353   }
 354
 355   // for every interval in inactive we overlap with, mark the
 356   // register as not free and update spill weights
 357   for (IntervalPtrs::const_iterator i = inactive_.begin(),
 358          e = inactive_.end(); i != e; ++i) {
 359     if (cur->overlaps(**i)) {
 360       unsigned reg = (*i)->reg;
 361       if (MRegisterInfo::isVirtualRegister(reg))
 362         reg = vrm_->getPhys(reg);
 363       prt_->addRegUse(reg);
 364       updateSpillWeights(reg, (*i)->weight);
 365     }
 366   }
 367
 368   // for every interval in fixed we overlap with,
 369   // mark the register as not free and update spill weights
 370   for (IntervalPtrs::const_iterator i = fixed_.begin(),
 371          e = fixed_.end(); i != e; ++i) {
 372     if (cur->overlaps(**i)) {
 373       unsigned reg = (*i)->reg;
 374       prt_->addRegUse(reg);
 375       updateSpillWeights(reg, (*i)->weight);
 376     }
 377   }
 378
 379   unsigned physReg = getFreePhysReg(cur);
 380   // restore the physical register tracker
 381   *prt_ = backupPrt;
 382   // if we find a free register, we are done: assign this virtual to
 383   // the free physical register and add this interval to the active
 384   // list.
 385   if (physReg) {
 386     DEBUG(std::cerr <<  mri_->getName(physReg) << '\n');
 387     vrm_->assignVirt2Phys(cur->reg, physReg);
 388     prt_->addRegUse(physReg);
 389     active_.push_back(cur);
 390     handled_.push_back(cur);
 391     return;
 392   }
 393   DEBUG(std::cerr << "no free registers\n");
 394
 395   DEBUG(std::cerr << "\tassigning stack slot at interval "<< *cur << ":\n");
 396
 397   float minWeight = HUGE_VAL;
 398   unsigned minReg = 0;
 399   const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
 400   for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
 401        i != rc->allocation_order_end(*mf_); ++i) {
 402     unsigned reg = *i;
 403     if (minWeight > spillWeights_[reg]) {
 404       minWeight = spillWeights_[reg];
 405       minReg = reg;
 406     }
 407   }
 408   DEBUG(std::cerr << "\t\tregister with min weight: "
 409         << mri_->getName(minReg) << " (" << minWeight << ")\n");
 410
 411   // if the current has the minimum weight, we spill it and move on
 412   if (cur->weight <= minWeight) {
 413     DEBUG(std::cerr << "\t\t\tspilling(c): " << *cur << '\n');
 414     spilled_.push_back(cur);
 415     return;
 416   }
 417
 418   // otherwise we spill all intervals aliasing the register with
 419   // minimum weight, assigned the newly cleared register to the
 420   // current interval and continue
 421   assert(MRegisterInfo::isPhysicalRegister(minReg) &&
 422          "did not choose a register to spill?");
 423   std::vector<bool> toSpill(mri_->getNumRegs(), false);
 424   toSpill[minReg] = true;
 425   for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as)
 426     toSpill[*as] = true;
 427   unsigned earliestStart = cur->start();
 428
 429   std::set<unsigned> spilled;
 430
 431   for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ) {
 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(a): " << **i << '\n');
 437       spilled_.push_back(*i);
 438       prt_->delRegUse(vrm_->getPhys(reg));
 439       vrm_->clearVirt(reg);
 440       i = active_.erase(i);
 441     }
 442     else
 443       ++i;
 444   }
 445   for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end(); ) {
 446     unsigned reg = (*i)->reg;
 447     if (MRegisterInfo::isVirtualRegister(reg) &&
 448         toSpill[vrm_->getPhys(reg)] &&
 449         cur->overlaps(**i)) {
 450       DEBUG(std::cerr << "\t\t\tspilling(i): " << **i << '\n');
 451       spilled_.push_back(*i);
 452       vrm_->clearVirt(reg);
 453       i = inactive_.erase(i);
 454     }
 455     else
 456       ++i;
 457   }
 458
 459   vrm_->assignVirt2Phys(cur->reg, minReg);
 460   prt_->addRegUse(minReg);
 461   active_.push_back(cur);
 462   handled_.push_back(cur);
 463
 464 }
 465
 466 unsigned RA::getFreePhysReg(IntervalPtrs::value_type cur)
 467 {
 468   const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
 469
 470   for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
 471        i != rc->allocation_order_end(*mf_); ++i) {
 472     unsigned reg = *i;
 473     if (prt_->isRegAvail(reg))
 474       return reg;
 475   }
 476   return 0;
 477 }
 478
 479 FunctionPass* llvm::createIterativeScanRegisterAllocator() {
 480   return new RA();
 481 }