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