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 <iostream>
  38 #include <set>
  39
  40 using namespace llvm;
  41
  42 namespace {
  43
  44     Statistic<double> efficiency
  45     ("regalloc", "Ratio of intervals processed over total intervals");
  46
  47     static unsigned numIterations = 0;
  48     static unsigned numIntervals = 0;
  49
  50     class RA : public MachineFunctionPass {
  51     private:
  52         MachineFunction* mf_;
  53         const TargetMachine* tm_;
  54         const MRegisterInfo* mri_;
  55         LiveIntervals* li_;
  56         typedef std::vector<LiveInterval*> IntervalPtrs;
  57         IntervalPtrs unhandled_, fixed_, active_, inactive_, handled_, spilled_;
  58
  59         std::auto_ptr<PhysRegTracker> prt_;
  60         std::auto_ptr<VirtRegMap> vrm_;
  61         std::auto_ptr<Spiller> spiller_;
  62
  63         typedef std::vector<float> SpillWeights;
  64         SpillWeights spillWeights_;
  65
  66     public:
  67         virtual const char* getPassName() const {
  68             return "Linear Scan Register Allocator";
  69         }
  70
  71         virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  72             AU.addRequired<LiveVariables>();
  73             AU.addRequired<LiveIntervals>();
  74             MachineFunctionPass::getAnalysisUsage(AU);
  75         }
  76
  77         /// runOnMachineFunction - register allocate the whole function
  78         bool runOnMachineFunction(MachineFunction&);
  79
  80         void releaseMemory();
  81
  82     private:
  83         /// linearScan - the linear scan algorithm. Returns a boolean
  84         /// indicating if there were any spills
  85         bool linearScan();
  86
  87         /// initIntervalSets - initializes the four interval sets:
  88         /// unhandled, fixed, active and inactive
  89         void initIntervalSets(LiveIntervals::Intervals& li);
  90
  91         /// processActiveIntervals - expire old intervals and move
  92         /// non-overlapping ones to the incative list
  93         void processActiveIntervals(IntervalPtrs::value_type cur);
  94
  95         /// processInactiveIntervals - expire old intervals and move
  96         /// overlapping ones to the active list
  97         void processInactiveIntervals(IntervalPtrs::value_type cur);
  98
  99         /// updateSpillWeights - updates the spill weights of the
 100         /// specifed physical register and its weight
 101         void updateSpillWeights(unsigned reg, SpillWeights::value_type weight);
 102
 103         /// assignRegOrStackSlotAtInterval - assign a register if one
 104         /// is available, or spill.
 105         void assignRegOrSpillAtInterval(IntervalPtrs::value_type cur);
 106
 107         ///
 108         /// register handling helpers
 109         ///
 110
 111         /// getFreePhysReg - return a free physical register for this
 112         /// virtual register interval if we have one, otherwise return
 113         /// 0
 114         unsigned getFreePhysReg(IntervalPtrs::value_type cur);
 115
 116         /// assignVirt2StackSlot - assigns this virtual register to a
 117         /// stack slot. returns the stack slot
 118         int assignVirt2StackSlot(unsigned virtReg);
 119
 120         void printIntervals(const char* const str,
 121                             RA::IntervalPtrs::const_iterator i,
 122                             RA::IntervalPtrs::const_iterator e) const {
 123             if (str) std::cerr << str << " intervals:\n";
 124             for (; i != e; ++i) {
 125                 std::cerr << "\t" << **i << " -> ";
 126                 unsigned reg = (*i)->reg;
 127                 if (MRegisterInfo::isVirtualRegister(reg)) {
 128                     reg = vrm_->getPhys(reg);
 129                 }
 130                 std::cerr << mri_->getName(reg) << '\n';
 131             }
 132         }
 133     };
 134 }
 135
 136 void RA::releaseMemory()
 137 {
 138     unhandled_.clear();
 139     fixed_.clear();
 140     active_.clear();
 141     inactive_.clear();
 142     handled_.clear();
 143     spilled_.clear();
 144 }
 145
 146 bool RA::runOnMachineFunction(MachineFunction &fn) {
 147     mf_ = &fn;
 148     tm_ = &fn.getTarget();
 149     mri_ = tm_->getRegisterInfo();
 150     li_ = &getAnalysis<LiveIntervals>();
 151     if (!prt_.get()) prt_.reset(new PhysRegTracker(*mri_));
 152     vrm_.reset(new VirtRegMap(*mf_));
 153     if (!spiller_.get()) spiller_.reset(createSpiller());
 154
 155     initIntervalSets(li_->getIntervals());
 156
 157     numIntervals += li_->getIntervals().size();
 158
 159     while (linearScan()) {
 160         // we spilled some registers, so we need to add intervals for
 161         // the spill code and restart the algorithm
 162         std::set<unsigned> spilledRegs;
 163         for (IntervalPtrs::iterator
 164                  i = spilled_.begin(); i != spilled_.end(); ) {
 165             int slot = vrm_->assignVirt2StackSlot((*i)->reg);
 166             std::vector<LiveInterval*> added =
 167                 li_->addIntervalsForSpills(**i, *vrm_, slot);
 168             std::copy(added.begin(), added.end(), std::back_inserter(handled_));
 169             spilledRegs.insert((*i)->reg);
 170             i = spilled_.erase(i);
 171         }
 172         for (IntervalPtrs::iterator
 173                  i = handled_.begin(); i != handled_.end(); )
 174             if (spilledRegs.count((*i)->reg))
 175                 i = handled_.erase(i);
 176             else
 177                 ++i;
 178         handled_.swap(unhandled_);
 179         vrm_->clearAllVirt();
 180     }
 181
 182     efficiency = double(numIterations) / double(numIntervals);
 183
 184     DEBUG(std::cerr << *vrm_);
 185
 186     spiller_->runOnMachineFunction(*mf_, *vrm_);
 187
 188     return true;
 189 }
 190
 191 bool RA::linearScan()
 192 {
 193     // linear scan algorithm
 194     DEBUG(std::cerr << "********** LINEAR SCAN **********\n");
 195     DEBUG(std::cerr << "********** Function: "
 196           << mf_->getFunction()->getName() << '\n');
 197
 198
 199     std::sort(unhandled_.begin(), unhandled_.end(),
 200               greater_ptr<LiveInterval>());
 201     DEBUG(printIntervals("unhandled", unhandled_.begin(), unhandled_.end()));
 202     DEBUG(printIntervals("fixed", fixed_.begin(), fixed_.end()));
 203     DEBUG(printIntervals("active", active_.begin(), active_.end()));
 204     DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
 205
 206     while (!unhandled_.empty()) {
 207         // pick the interval with the earliest start point
 208         IntervalPtrs::value_type cur = unhandled_.back();
 209         unhandled_.pop_back();
 210         ++numIterations;
 211         DEBUG(std::cerr << "\n*** CURRENT ***: " << *cur << '\n');
 212
 213         processActiveIntervals(cur);
 214         processInactiveIntervals(cur);
 215
 216         // if this register is fixed we are done
 217         if (MRegisterInfo::isPhysicalRegister(cur->reg)) {
 218             prt_->addRegUse(cur->reg);
 219             active_.push_back(cur);
 220             handled_.push_back(cur);
 221         }
 222         // otherwise we are allocating a virtual register. try to find
 223         // a free physical register or spill an interval in order to
 224         // assign it one (we could spill the current though).
 225         else {
 226             assignRegOrSpillAtInterval(cur);
 227         }
 228
 229         DEBUG(printIntervals("active", active_.begin(), active_.end()));
 230         DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
 231     }
 232
 233     // expire any remaining active intervals
 234     for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ) {
 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 = active_.erase(i);
 241     }
 242
 243     // expire any remaining inactive intervals
 244     for (IntervalPtrs::iterator
 245              i = inactive_.begin(); i != inactive_.end(); ) {
 246         DEBUG(std::cerr << "\tinterval " << **i << " expired\n");
 247         i = inactive_.erase(i);
 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::iterator i = active_.begin(); i != active_.end();) {
 272         unsigned reg = (*i)->reg;
 273         // remove expired intervals
 274         if ((*i)->expiredAt(cur->start())) {
 275             DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n");
 276             if (MRegisterInfo::isVirtualRegister(reg))
 277                 reg = vrm_->getPhys(reg);
 278             prt_->delRegUse(reg);
 279             // remove from active
 280             i = active_.erase(i);
 281         }
 282         // move inactive intervals to inactive list
 283         else if (!(*i)->liveAt(cur->start())) {
 284             DEBUG(std::cerr << "\t\tinterval " << **i << " inactive\n");
 285             if (MRegisterInfo::isVirtualRegister(reg))
 286                 reg = vrm_->getPhys(reg);
 287             prt_->delRegUse(reg);
 288             // add to inactive
 289             inactive_.push_back(*i);
 290             // remove from active
 291             i = active_.erase(i);
 292         }
 293         else {
 294             ++i;
 295         }
 296     }
 297 }
 298
 299 void RA::processInactiveIntervals(IntervalPtrs::value_type cur)
 300 {
 301     DEBUG(std::cerr << "\tprocessing inactive intervals:\n");
 302     for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end();) {
 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 = inactive_.erase(i);
 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 = inactive_.erase(i);
 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     std::vector<LiveInterval*> added;
 419     assert(MRegisterInfo::isPhysicalRegister(minReg) &&
 420            "did not choose a register to spill?");
 421     std::vector<bool> toSpill(mri_->getNumRegs(), false);
 422     toSpill[minReg] = true;
 423     for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as)
 424         toSpill[*as] = true;
 425     unsigned earliestStart = cur->start();
 426
 427     std::set<unsigned> spilled;
 428
 429     for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ) {
 430         unsigned reg = (*i)->reg;
 431         if (MRegisterInfo::isVirtualRegister(reg) &&
 432             toSpill[vrm_->getPhys(reg)] &&
 433             cur->overlaps(**i)) {
 434             DEBUG(std::cerr << "\t\t\tspilling(a): " << **i << '\n');
 435             spilled_.push_back(*i);
 436             prt_->delRegUse(vrm_->getPhys(reg));
 437             vrm_->clearVirt(reg);
 438             i = active_.erase(i);
 439         }
 440         else
 441             ++i;
 442     }
 443     for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end(); ) {
 444         unsigned reg = (*i)->reg;
 445         if (MRegisterInfo::isVirtualRegister(reg) &&
 446             toSpill[vrm_->getPhys(reg)] &&
 447             cur->overlaps(**i)) {
 448             DEBUG(std::cerr << "\t\t\tspilling(i): " << **i << '\n');
 449             spilled_.push_back(*i);
 450             vrm_->clearVirt(reg);
 451             i = inactive_.erase(i);
 452         }
 453         else
 454             ++i;
 455     }
 456
 457     vrm_->assignVirt2Phys(cur->reg, minReg);
 458     prt_->addRegUse(minReg);
 459     active_.push_back(cur);
 460     handled_.push_back(cur);
 461
 462 }
 463
 464 unsigned RA::getFreePhysReg(IntervalPtrs::value_type cur)
 465 {
 466     const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
 467
 468     for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
 469          i != rc->allocation_order_end(*mf_); ++i) {
 470         unsigned reg = *i;
 471         if (prt_->isRegAvail(reg))
 472             return reg;
 473     }
 474     return 0;
 475 }
 476
 477 FunctionPass* llvm::createIterativeScanRegisterAllocator() {
 478     return new RA();
 479 }