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