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