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