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 "Support/Debug.h"
  29 #include "Support/Statistic.h"
  30 #include "Support/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   for (IntervalPtrs::reverse_iterator
 268          i = active_.rbegin(); i != active_.rend();) {
 269     unsigned reg = (*i)->reg;
 270     // remove expired intervals
 271     if ((*i)->expiredAt(cur->start())) {
 272       DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n");
 273       if (MRegisterInfo::isVirtualRegister(reg))
 274         reg = vrm_->getPhys(reg);
 275       prt_->delRegUse(reg);
 276       // remove from active
 277       i = IntervalPtrs::reverse_iterator(active_.erase(i.base()-1));
 278     }
 279     // move inactive intervals to inactive list
 280     else if (!(*i)->liveAt(cur->start())) {
 281       DEBUG(std::cerr << "\t\tinterval " << **i << " inactive\n");
 282       if (MRegisterInfo::isVirtualRegister(reg))
 283         reg = vrm_->getPhys(reg);
 284       prt_->delRegUse(reg);
 285       // add to inactive
 286       inactive_.push_back(*i);
 287       // remove from active
 288       i = IntervalPtrs::reverse_iterator(active_.erase(i.base()-1));
 289     }
 290     else {
 291       ++i;
 292     }
 293   }
 294 }
 295
 296 void RA::processInactiveIntervals(IntervalPtrs::value_type cur)
 297 {
 298   DEBUG(std::cerr << "\tprocessing inactive intervals:\n");
 299   for (IntervalPtrs::reverse_iterator
 300          i = inactive_.rbegin(); i != inactive_.rend();) {
 301     unsigned reg = (*i)->reg;
 302
 303     // remove expired intervals
 304     if ((*i)->expiredAt(cur->start())) {
 305       DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n");
 306       // remove from inactive
 307       i = IntervalPtrs::reverse_iterator(inactive_.erase(i.base()-1));
 308     }
 309     // move re-activated intervals in active list
 310     else if ((*i)->liveAt(cur->start())) {
 311       DEBUG(std::cerr << "\t\tinterval " << **i << " active\n");
 312       if (MRegisterInfo::isVirtualRegister(reg))
 313         reg = vrm_->getPhys(reg);
 314       prt_->addRegUse(reg);
 315       // add to active
 316       active_.push_back(*i);
 317       // remove from inactive
 318       i = IntervalPtrs::reverse_iterator(inactive_.erase(i.base()-1));
 319     }
 320     else {
 321       ++i;
 322     }
 323   }
 324 }
 325
 326 void RA::updateSpillWeights(unsigned reg, SpillWeights::value_type weight)
 327 {
 328   spillWeights_[reg] += weight;
 329   for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as)
 330     spillWeights_[*as] += weight;
 331 }
 332
 333 void RA::assignRegOrSpillAtInterval(IntervalPtrs::value_type cur)
 334 {
 335   DEBUG(std::cerr << "\tallocating current interval: ");
 336
 337   PhysRegTracker backupPrt = *prt_;
 338
 339   spillWeights_.assign(mri_->getNumRegs(), 0.0);
 340
 341   // for each interval in active update spill weights
 342   for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
 343        i != e; ++i) {
 344     unsigned reg = (*i)->reg;
 345     if (MRegisterInfo::isVirtualRegister(reg))
 346       reg = vrm_->getPhys(reg);
 347     updateSpillWeights(reg, (*i)->weight);
 348   }
 349
 350   // for every interval in inactive we overlap with, mark the
 351   // register as not free and update spill weights
 352   for (IntervalPtrs::const_iterator i = inactive_.begin(),
 353          e = inactive_.end(); i != e; ++i) {
 354     if (cur->overlaps(**i)) {
 355       unsigned reg = (*i)->reg;
 356       if (MRegisterInfo::isVirtualRegister(reg))
 357         reg = vrm_->getPhys(reg);
 358       prt_->addRegUse(reg);
 359       updateSpillWeights(reg, (*i)->weight);
 360     }
 361   }
 362
 363   // for every interval in fixed we overlap with,
 364   // mark the register as not free and update spill weights
 365   for (IntervalPtrs::const_iterator i = fixed_.begin(),
 366          e = fixed_.end(); i != e; ++i) {
 367     if (cur->overlaps(**i)) {
 368       unsigned reg = (*i)->reg;
 369       prt_->addRegUse(reg);
 370       updateSpillWeights(reg, (*i)->weight);
 371     }
 372   }
 373
 374   unsigned physReg = getFreePhysReg(cur);
 375   // restore the physical register tracker
 376   *prt_ = backupPrt;
 377   // if we find a free register, we are done: assign this virtual to
 378   // the free physical register and add this interval to the active
 379   // list.
 380   if (physReg) {
 381     DEBUG(std::cerr <<  mri_->getName(physReg) << '\n');
 382     vrm_->assignVirt2Phys(cur->reg, physReg);
 383     prt_->addRegUse(physReg);
 384     active_.push_back(cur);
 385     handled_.push_back(cur);
 386     return;
 387   }
 388   DEBUG(std::cerr << "no free registers\n");
 389
 390   DEBUG(std::cerr << "\tassigning stack slot at interval "<< *cur << ":\n");
 391
 392   float minWeight = HUGE_VAL;
 393   unsigned minReg = 0;
 394   const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
 395   for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
 396        i != rc->allocation_order_end(*mf_); ++i) {
 397     unsigned reg = *i;
 398     if (minWeight > spillWeights_[reg]) {
 399       minWeight = spillWeights_[reg];
 400       minReg = reg;
 401     }
 402   }
 403   DEBUG(std::cerr << "\t\tregister with min weight: "
 404         << mri_->getName(minReg) << " (" << minWeight << ")\n");
 405
 406   // if the current has the minimum weight, we spill it and move on
 407   if (cur->weight <= minWeight) {
 408     DEBUG(std::cerr << "\t\t\tspilling(c): " << *cur << '\n');
 409     spilled_.push_back(cur);
 410     return;
 411   }
 412
 413   // otherwise we spill all intervals aliasing the register with
 414   // minimum weight, assigned the newly cleared register to the
 415   // current interval and continue
 416   assert(MRegisterInfo::isPhysicalRegister(minReg) &&
 417          "did not choose a register to spill?");
 418   std::vector<bool> toSpill(mri_->getNumRegs(), false);
 419   toSpill[minReg] = true;
 420   for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as)
 421     toSpill[*as] = true;
 422   unsigned earliestStart = cur->start();
 423
 424   std::set<unsigned> spilled;
 425
 426   for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ) {
 427     unsigned reg = (*i)->reg;
 428     if (MRegisterInfo::isVirtualRegister(reg) &&
 429         toSpill[vrm_->getPhys(reg)] &&
 430         cur->overlaps(**i)) {
 431       DEBUG(std::cerr << "\t\t\tspilling(a): " << **i << '\n');
 432       spilled_.push_back(*i);
 433       prt_->delRegUse(vrm_->getPhys(reg));
 434       vrm_->clearVirt(reg);
 435       i = active_.erase(i);
 436     }
 437     else
 438       ++i;
 439   }
 440   for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end(); ) {
 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       spilled_.push_back(*i);
 447       vrm_->clearVirt(reg);
 448       i = inactive_.erase(i);
 449     }
 450     else
 451       ++i;
 452   }
 453
 454   vrm_->assignVirt2Phys(cur->reg, minReg);
 455   prt_->addRegUse(minReg);
 456   active_.push_back(cur);
 457   handled_.push_back(cur);
 458
 459 }
 460
 461 unsigned RA::getFreePhysReg(IntervalPtrs::value_type cur)
 462 {
 463   const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
 464
 465   for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
 466        i != rc->allocation_order_end(*mf_); ++i) {
 467     unsigned reg = *i;
 468     if (prt_->isRegAvail(reg))
 469       return reg;
 470   }
 471   return 0;
 472 }
 473
 474 FunctionPass* llvm::createIterativeScanRegisterAllocator() {
 475   return new RA();
 476 }