lib/CodeGen/RegAllocLinearScan.cpp

   1 //===-- RegAllocLinearScan.cpp - Linear Scan register allocator -----------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // 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 "PhysRegTracker.h"
  16 #include "VirtRegMap.h"
  17 #include "llvm/Function.h"
  18 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  19 #include "llvm/CodeGen/LiveStackAnalysis.h"
  20 #include "llvm/CodeGen/MachineFunctionPass.h"
  21 #include "llvm/CodeGen/MachineInstr.h"
  22 #include "llvm/CodeGen/MachineLoopInfo.h"
  23 #include "llvm/CodeGen/MachineRegisterInfo.h"
  24 #include "llvm/CodeGen/Passes.h"
  25 #include "llvm/CodeGen/RegAllocRegistry.h"
  26 #include "llvm/CodeGen/RegisterCoalescer.h"
  27 #include "llvm/Target/TargetRegisterInfo.h"
  28 #include "llvm/Target/TargetMachine.h"
  29 #include "llvm/Target/TargetOptions.h"
  30 #include "llvm/Target/TargetInstrInfo.h"
  31 #include "llvm/ADT/EquivalenceClasses.h"
  32 #include "llvm/ADT/Statistic.h"
  33 #include "llvm/ADT/STLExtras.h"
  34 #include "llvm/Support/Debug.h"
  35 #include "llvm/Support/Compiler.h"
  36 #include <algorithm>
  37 #include <set>
  38 #include <queue>
  39 #include <memory>
  40 #include <cmath>
  41 using namespace llvm;
  42
  43 STATISTIC(NumIters     , "Number of iterations performed");
  44 STATISTIC(NumBacktracks, "Number of times we had to backtrack");
  45 STATISTIC(NumCoalesce,   "Number of copies coalesced");
  46
  47 static cl::opt<bool>
  48 NewHeuristic("new-spilling-heuristic",
  49              cl::desc("Use new spilling heuristic"),
  50              cl::init(false), cl::Hidden);
  51
  52 static RegisterRegAlloc
  53 linearscanRegAlloc("linearscan", "linear scan register allocator",
  54                    createLinearScanRegisterAllocator);
  55
  56 namespace {
  57   struct VISIBILITY_HIDDEN RALinScan : public MachineFunctionPass {
  58     static char ID;
  59     RALinScan() : MachineFunctionPass(&ID) {}
  60
  61     typedef std::pair<LiveInterval*, LiveInterval::iterator> IntervalPtr;
  62     typedef SmallVector<IntervalPtr, 32> IntervalPtrs;
  63   private:
  64     /// RelatedRegClasses - This structure is built the first time a function is
  65     /// compiled, and keeps track of which register classes have registers that
  66     /// belong to multiple classes or have aliases that are in other classes.
  67     EquivalenceClasses<const TargetRegisterClass*> RelatedRegClasses;
  68     DenseMap<unsigned, const TargetRegisterClass*> OneClassForEachPhysReg;
  69
  70     MachineFunction* mf_;
  71     MachineRegisterInfo* mri_;
  72     const TargetMachine* tm_;
  73     const TargetRegisterInfo* tri_;
  74     const TargetInstrInfo* tii_;
  75     BitVector allocatableRegs_;
  76     LiveIntervals* li_;
  77     LiveStacks* ls_;
  78     const MachineLoopInfo *loopInfo;
  79
  80     /// handled_ - Intervals are added to the handled_ set in the order of their
  81     /// start value.  This is uses for backtracking.
  82     std::vector<LiveInterval*> handled_;
  83
  84     /// fixed_ - Intervals that correspond to machine registers.
  85     ///
  86     IntervalPtrs fixed_;
  87
  88     /// active_ - Intervals that are currently being processed, and which have a
  89     /// live range active for the current point.
  90     IntervalPtrs active_;
  91
  92     /// inactive_ - Intervals that are currently being processed, but which have
  93     /// a hold at the current point.
  94     IntervalPtrs inactive_;
  95
  96     typedef std::priority_queue<LiveInterval*,
  97                                 SmallVector<LiveInterval*, 64>,
  98                                 greater_ptr<LiveInterval> > IntervalHeap;
  99     IntervalHeap unhandled_;
 100     std::auto_ptr<PhysRegTracker> prt_;
 101     std::auto_ptr<VirtRegMap> vrm_;
 102     std::auto_ptr<Spiller> spiller_;
 103
 104   public:
 105     virtual const char* getPassName() const {
 106       return "Linear Scan Register Allocator";
 107     }
 108
 109     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 110       AU.addRequired<LiveIntervals>();
 111       if (StrongPHIElim)
 112         AU.addRequiredID(StrongPHIEliminationID);
 113       // Make sure PassManager knows which analyses to make available
 114       // to coalescing and which analyses coalescing invalidates.
 115       AU.addRequiredTransitive<RegisterCoalescer>();
 116       AU.addRequired<LiveStacks>();
 117       AU.addPreserved<LiveStacks>();
 118       AU.addRequired<MachineLoopInfo>();
 119       AU.addPreserved<MachineLoopInfo>();
 120       AU.addPreservedID(MachineDominatorsID);
 121       MachineFunctionPass::getAnalysisUsage(AU);
 122     }
 123
 124     /// runOnMachineFunction - register allocate the whole function
 125     bool runOnMachineFunction(MachineFunction&);
 126
 127   private:
 128     /// linearScan - the linear scan algorithm
 129     void linearScan();
 130
 131     /// initIntervalSets - initialize the interval sets.
 132     ///
 133     void initIntervalSets();
 134
 135     /// processActiveIntervals - expire old intervals and move non-overlapping
 136     /// ones to the inactive list.
 137     void processActiveIntervals(unsigned CurPoint);
 138
 139     /// processInactiveIntervals - expire old intervals and move overlapping
 140     /// ones to the active list.
 141     void processInactiveIntervals(unsigned CurPoint);
 142
 143     /// assignRegOrStackSlotAtInterval - assign a register if one
 144     /// is available, or spill.
 145     void assignRegOrStackSlotAtInterval(LiveInterval* cur);
 146
 147     /// findIntervalsToSpill - Determine the intervals to spill for the
 148     /// specified interval. It's passed the physical registers whose spill
 149     /// weight is the lowest among all the registers whose live intervals
 150     /// conflict with the interval.
 151     void findIntervalsToSpill(LiveInterval *cur,
 152                             std::vector<std::pair<unsigned,float> > &Candidates,
 153                             unsigned NumCands,
 154                             SmallVector<LiveInterval*, 8> &SpillIntervals);
 155
 156     /// attemptTrivialCoalescing - If a simple interval is defined by a copy,
 157     /// try allocate the definition the same register as the source register
 158     /// if the register is not defined during live time of the interval. This
 159     /// eliminate a copy. This is used to coalesce copies which were not
 160     /// coalesced away before allocation either due to dest and src being in
 161     /// different register classes or because the coalescer was overly
 162     /// conservative.
 163     unsigned attemptTrivialCoalescing(LiveInterval &cur, unsigned Reg);
 164
 165     ///
 166     /// register handling helpers
 167     ///
 168
 169     /// getFreePhysReg - return a free physical register for this virtual
 170     /// register interval if we have one, otherwise return 0.
 171     unsigned getFreePhysReg(LiveInterval* cur);
 172
 173     /// assignVirt2StackSlot - assigns this virtual register to a
 174     /// stack slot. returns the stack slot
 175     int assignVirt2StackSlot(unsigned virtReg);
 176
 177     void ComputeRelatedRegClasses();
 178
 179     template <typename ItTy>
 180     void printIntervals(const char* const str, ItTy i, ItTy e) const {
 181       if (str) DOUT << str << " intervals:\n";
 182       for (; i != e; ++i) {
 183         DOUT << "\t" << *i->first << " -> ";
 184         unsigned reg = i->first->reg;
 185         if (TargetRegisterInfo::isVirtualRegister(reg)) {
 186           reg = vrm_->getPhys(reg);
 187         }
 188         DOUT << tri_->getName(reg) << '\n';
 189       }
 190     }
 191   };
 192   char RALinScan::ID = 0;
 193 }
 194
 195 static RegisterPass<RALinScan>
 196 X("linearscan-regalloc", "Linear Scan Register Allocator");
 197
 198 void RALinScan::ComputeRelatedRegClasses() {
 199   const TargetRegisterInfo &TRI = *tri_;
 200
 201   // First pass, add all reg classes to the union, and determine at least one
 202   // reg class that each register is in.
 203   bool HasAliases = false;
 204   for (TargetRegisterInfo::regclass_iterator RCI = TRI.regclass_begin(),
 205        E = TRI.regclass_end(); RCI != E; ++RCI) {
 206     RelatedRegClasses.insert(*RCI);
 207     for (TargetRegisterClass::iterator I = (*RCI)->begin(), E = (*RCI)->end();
 208          I != E; ++I) {
 209       HasAliases = HasAliases || *TRI.getAliasSet(*I) != 0;
 210
 211       const TargetRegisterClass *&PRC = OneClassForEachPhysReg[*I];
 212       if (PRC) {
 213         // Already processed this register.  Just make sure we know that
 214         // multiple register classes share a register.
 215         RelatedRegClasses.unionSets(PRC, *RCI);
 216       } else {
 217         PRC = *RCI;
 218       }
 219     }
 220   }
 221
 222   // Second pass, now that we know conservatively what register classes each reg
 223   // belongs to, add info about aliases.  We don't need to do this for targets
 224   // without register aliases.
 225   if (HasAliases)
 226     for (DenseMap<unsigned, const TargetRegisterClass*>::iterator
 227          I = OneClassForEachPhysReg.begin(), E = OneClassForEachPhysReg.end();
 228          I != E; ++I)
 229       for (const unsigned *AS = TRI.getAliasSet(I->first); *AS; ++AS)
 230         RelatedRegClasses.unionSets(I->second, OneClassForEachPhysReg[*AS]);
 231 }
 232
 233 /// attemptTrivialCoalescing - If a simple interval is defined by a copy,
 234 /// try allocate the definition the same register as the source register
 235 /// if the register is not defined during live time of the interval. This
 236 /// eliminate a copy. This is used to coalesce copies which were not
 237 /// coalesced away before allocation either due to dest and src being in
 238 /// different register classes or because the coalescer was overly
 239 /// conservative.
 240 unsigned RALinScan::attemptTrivialCoalescing(LiveInterval &cur, unsigned Reg) {
 241   if ((cur.preference && cur.preference == Reg) || !cur.containsOneValue())
 242     return Reg;
 243
 244   VNInfo *vni = cur.getValNumInfo(0);
 245   if (!vni->def || vni->def == ~1U || vni->def == ~0U)
 246     return Reg;
 247   MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def);
 248   unsigned SrcReg, DstReg;
 249   if (!CopyMI || !tii_->isMoveInstr(*CopyMI, SrcReg, DstReg))
 250     return Reg;
 251   if (TargetRegisterInfo::isVirtualRegister(SrcReg)) {
 252     if (!vrm_->isAssignedReg(SrcReg))
 253       return Reg;
 254     else
 255       SrcReg = vrm_->getPhys(SrcReg);
 256   }
 257   if (Reg == SrcReg)
 258     return Reg;
 259
 260   const TargetRegisterClass *RC = mri_->getRegClass(cur.reg);
 261   if (!RC->contains(SrcReg))
 262     return Reg;
 263
 264   // Try to coalesce.
 265   if (!li_->conflictsWithPhysRegDef(cur, *vrm_, SrcReg)) {
 266     DOUT << "Coalescing: " << cur << " -> " << tri_->getName(SrcReg)
 267          << '\n';
 268     vrm_->clearVirt(cur.reg);
 269     vrm_->assignVirt2Phys(cur.reg, SrcReg);
 270     ++NumCoalesce;
 271     return SrcReg;
 272   }
 273
 274   return Reg;
 275 }
 276
 277 bool RALinScan::runOnMachineFunction(MachineFunction &fn) {
 278   mf_ = &fn;
 279   mri_ = &fn.getRegInfo();
 280   tm_ = &fn.getTarget();
 281   tri_ = tm_->getRegisterInfo();
 282   tii_ = tm_->getInstrInfo();
 283   allocatableRegs_ = tri_->getAllocatableSet(fn);
 284   li_ = &getAnalysis<LiveIntervals>();
 285   ls_ = &getAnalysis<LiveStacks>();
 286   loopInfo = &getAnalysis<MachineLoopInfo>();
 287
 288   // We don't run the coalescer here because we have no reason to
 289   // interact with it.  If the coalescer requires interaction, it
 290   // won't do anything.  If it doesn't require interaction, we assume
 291   // it was run as a separate pass.
 292
 293   // If this is the first function compiled, compute the related reg classes.
 294   if (RelatedRegClasses.empty())
 295     ComputeRelatedRegClasses();
 296
 297   if (!prt_.get()) prt_.reset(new PhysRegTracker(*tri_));
 298   vrm_.reset(new VirtRegMap(*mf_));
 299   if (!spiller_.get()) spiller_.reset(createSpiller());
 300
 301   initIntervalSets();
 302
 303   linearScan();
 304
 305   // Rewrite spill code and update the PhysRegsUsed set.
 306   spiller_->runOnMachineFunction(*mf_, *vrm_);
 307   vrm_.reset();  // Free the VirtRegMap
 308
 309   assert(unhandled_.empty() && "Unhandled live intervals remain!");
 310   fixed_.clear();
 311   active_.clear();
 312   inactive_.clear();
 313   handled_.clear();
 314
 315   return true;
 316 }
 317
 318 /// initIntervalSets - initialize the interval sets.
 319 ///
 320 void RALinScan::initIntervalSets()
 321 {
 322   assert(unhandled_.empty() && fixed_.empty() &&
 323          active_.empty() && inactive_.empty() &&
 324          "interval sets should be empty on initialization");
 325
 326   handled_.reserve(li_->getNumIntervals());
 327
 328   for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) {
 329     if (TargetRegisterInfo::isPhysicalRegister(i->second->reg)) {
 330       mri_->setPhysRegUsed(i->second->reg);
 331       fixed_.push_back(std::make_pair(i->second, i->second->begin()));
 332     } else
 333       unhandled_.push(i->second);
 334   }
 335 }
 336
 337 void RALinScan::linearScan()
 338 {
 339   // linear scan algorithm
 340   DOUT << "********** LINEAR SCAN **********\n";
 341   DOUT << "********** Function: " << mf_->getFunction()->getName() << '\n';
 342
 343   DEBUG(printIntervals("fixed", fixed_.begin(), fixed_.end()));
 344
 345   while (!unhandled_.empty()) {
 346     // pick the interval with the earliest start point
 347     LiveInterval* cur = unhandled_.top();
 348     unhandled_.pop();
 349     ++NumIters;
 350     DOUT << "\n*** CURRENT ***: " << *cur << '\n';
 351
 352     if (!cur->empty()) {
 353       processActiveIntervals(cur->beginNumber());
 354       processInactiveIntervals(cur->beginNumber());
 355
 356       assert(TargetRegisterInfo::isVirtualRegister(cur->reg) &&
 357              "Can only allocate virtual registers!");
 358     }
 359
 360     // Allocating a virtual register. try to find a free
 361     // physical register or spill an interval (possibly this one) in order to
 362     // assign it one.
 363     assignRegOrStackSlotAtInterval(cur);
 364
 365     DEBUG(printIntervals("active", active_.begin(), active_.end()));
 366     DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
 367   }
 368
 369   // expire any remaining active intervals
 370   while (!active_.empty()) {
 371     IntervalPtr &IP = active_.back();
 372     unsigned reg = IP.first->reg;
 373     DOUT << "\tinterval " << *IP.first << " expired\n";
 374     assert(TargetRegisterInfo::isVirtualRegister(reg) &&
 375            "Can only allocate virtual registers!");
 376     reg = vrm_->getPhys(reg);
 377     prt_->delRegUse(reg);
 378     active_.pop_back();
 379   }
 380
 381   // expire any remaining inactive intervals
 382   DEBUG(for (IntervalPtrs::reverse_iterator
 383                i = inactive_.rbegin(); i != inactive_.rend(); ++i)
 384         DOUT << "\tinterval " << *i->first << " expired\n");
 385   inactive_.clear();
 386
 387   // Add live-ins to every BB except for entry. Also perform trivial coalescing.
 388   MachineFunction::iterator EntryMBB = mf_->begin();
 389   SmallVector<MachineBasicBlock*, 8> LiveInMBBs;
 390   for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) {
 391     LiveInterval &cur = *i->second;
 392     unsigned Reg = 0;
 393     bool isPhys = TargetRegisterInfo::isPhysicalRegister(cur.reg);
 394     if (isPhys)
 395       Reg = cur.reg;
 396     else if (vrm_->isAssignedReg(cur.reg))
 397       Reg = attemptTrivialCoalescing(cur, vrm_->getPhys(cur.reg));
 398     if (!Reg)
 399       continue;
 400     // Ignore splited live intervals.
 401     if (!isPhys && vrm_->getPreSplitReg(cur.reg))
 402       continue;
 403     for (LiveInterval::Ranges::const_iterator I = cur.begin(), E = cur.end();
 404          I != E; ++I) {
 405       const LiveRange &LR = *I;
 406       if (li_->findLiveInMBBs(LR, LiveInMBBs)) {
 407         for (unsigned i = 0, e = LiveInMBBs.size(); i != e; ++i)
 408           if (LiveInMBBs[i] != EntryMBB)
 409             LiveInMBBs[i]->addLiveIn(Reg);
 410         LiveInMBBs.clear();
 411       }
 412     }
 413   }
 414
 415   DOUT << *vrm_;
 416 }
 417
 418 /// processActiveIntervals - expire old intervals and move non-overlapping ones
 419 /// to the inactive list.
 420 void RALinScan::processActiveIntervals(unsigned CurPoint)
 421 {
 422   DOUT << "\tprocessing active intervals:\n";
 423
 424   for (unsigned i = 0, e = active_.size(); i != e; ++i) {
 425     LiveInterval *Interval = active_[i].first;
 426     LiveInterval::iterator IntervalPos = active_[i].second;
 427     unsigned reg = Interval->reg;
 428
 429     IntervalPos = Interval->advanceTo(IntervalPos, CurPoint);
 430
 431     if (IntervalPos == Interval->end()) {     // Remove expired intervals.
 432       DOUT << "\t\tinterval " << *Interval << " expired\n";
 433       assert(TargetRegisterInfo::isVirtualRegister(reg) &&
 434              "Can only allocate virtual registers!");
 435       reg = vrm_->getPhys(reg);
 436       prt_->delRegUse(reg);
 437
 438       // Pop off the end of the list.
 439       active_[i] = active_.back();
 440       active_.pop_back();
 441       --i; --e;
 442
 443     } else if (IntervalPos->start > CurPoint) {
 444       // Move inactive intervals to inactive list.
 445       DOUT << "\t\tinterval " << *Interval << " inactive\n";
 446       assert(TargetRegisterInfo::isVirtualRegister(reg) &&
 447              "Can only allocate virtual registers!");
 448       reg = vrm_->getPhys(reg);
 449       prt_->delRegUse(reg);
 450       // add to inactive.
 451       inactive_.push_back(std::make_pair(Interval, IntervalPos));
 452
 453       // Pop off the end of the list.
 454       active_[i] = active_.back();
 455       active_.pop_back();
 456       --i; --e;
 457     } else {
 458       // Otherwise, just update the iterator position.
 459       active_[i].second = IntervalPos;
 460     }
 461   }
 462 }
 463
 464 /// processInactiveIntervals - expire old intervals and move overlapping
 465 /// ones to the active list.
 466 void RALinScan::processInactiveIntervals(unsigned CurPoint)
 467 {
 468   DOUT << "\tprocessing inactive intervals:\n";
 469
 470   for (unsigned i = 0, e = inactive_.size(); i != e; ++i) {
 471     LiveInterval *Interval = inactive_[i].first;
 472     LiveInterval::iterator IntervalPos = inactive_[i].second;
 473     unsigned reg = Interval->reg;
 474
 475     IntervalPos = Interval->advanceTo(IntervalPos, CurPoint);
 476
 477     if (IntervalPos == Interval->end()) {       // remove expired intervals.
 478       DOUT << "\t\tinterval " << *Interval << " expired\n";
 479
 480       // Pop off the end of the list.
 481       inactive_[i] = inactive_.back();
 482       inactive_.pop_back();
 483       --i; --e;
 484     } else if (IntervalPos->start <= CurPoint) {
 485       // move re-activated intervals in active list
 486       DOUT << "\t\tinterval " << *Interval << " active\n";
 487       assert(TargetRegisterInfo::isVirtualRegister(reg) &&
 488              "Can only allocate virtual registers!");
 489       reg = vrm_->getPhys(reg);
 490       prt_->addRegUse(reg);
 491       // add to active
 492       active_.push_back(std::make_pair(Interval, IntervalPos));
 493
 494       // Pop off the end of the list.
 495       inactive_[i] = inactive_.back();
 496       inactive_.pop_back();
 497       --i; --e;
 498     } else {
 499       // Otherwise, just update the iterator position.
 500       inactive_[i].second = IntervalPos;
 501     }
 502   }
 503 }
 504
 505 /// updateSpillWeights - updates the spill weights of the specifed physical
 506 /// register and its weight.
 507 static void updateSpillWeights(std::vector<float> &Weights,
 508                                unsigned reg, float weight,
 509                                const TargetRegisterInfo *TRI) {
 510   Weights[reg] += weight;
 511   for (const unsigned* as = TRI->getAliasSet(reg); *as; ++as)
 512     Weights[*as] += weight;
 513 }
 514
 515 static
 516 RALinScan::IntervalPtrs::iterator
 517 FindIntervalInVector(RALinScan::IntervalPtrs &IP, LiveInterval *LI) {
 518   for (RALinScan::IntervalPtrs::iterator I = IP.begin(), E = IP.end();
 519        I != E; ++I)
 520     if (I->first == LI) return I;
 521   return IP.end();
 522 }
 523
 524 static void RevertVectorIteratorsTo(RALinScan::IntervalPtrs &V, unsigned Point){
 525   for (unsigned i = 0, e = V.size(); i != e; ++i) {
 526     RALinScan::IntervalPtr &IP = V[i];
 527     LiveInterval::iterator I = std::upper_bound(IP.first->begin(),
 528                                                 IP.second, Point);
 529     if (I != IP.first->begin()) --I;
 530     IP.second = I;
 531   }
 532 }
 533
 534 /// addStackInterval - Create a LiveInterval for stack if the specified live
 535 /// interval has been spilled.
 536 static void addStackInterval(LiveInterval *cur, LiveStacks *ls_,
 537                              LiveIntervals *li_, float &Weight,
 538                              VirtRegMap &vrm_) {
 539   int SS = vrm_.getStackSlot(cur->reg);
 540   if (SS == VirtRegMap::NO_STACK_SLOT)
 541     return;
 542   LiveInterval &SI = ls_->getOrCreateInterval(SS);
 543   SI.weight += Weight;
 544
 545   VNInfo *VNI;
 546   if (SI.getNumValNums())
 547     VNI = SI.getValNumInfo(0);
 548   else
 549     VNI = SI.getNextValue(~0U, 0, ls_->getVNInfoAllocator());
 550
 551   LiveInterval &RI = li_->getInterval(cur->reg);
 552   // FIXME: This may be overly conservative.
 553   SI.MergeRangesInAsValue(RI, VNI);
 554 }
 555
 556 /// getConflictWeight - Return the number of conflicts between cur
 557 /// live interval and defs and uses of Reg weighted by loop depthes.
 558 static float getConflictWeight(LiveInterval *cur, unsigned Reg,
 559                                   LiveIntervals *li_,
 560                                   MachineRegisterInfo *mri_,
 561                                   const MachineLoopInfo *loopInfo) {
 562   float Conflicts = 0;
 563   for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(Reg),
 564          E = mri_->reg_end(); I != E; ++I) {
 565     MachineInstr *MI = &*I;
 566     if (cur->liveAt(li_->getInstructionIndex(MI))) {
 567       unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent());
 568       Conflicts += powf(10.0f, (float)loopDepth);
 569     }
 570   }
 571   return Conflicts;
 572 }
 573
 574 /// findIntervalsToSpill - Determine the intervals to spill for the
 575 /// specified interval. It's passed the physical registers whose spill
 576 /// weight is the lowest among all the registers whose live intervals
 577 /// conflict with the interval.
 578 void RALinScan::findIntervalsToSpill(LiveInterval *cur,
 579                             std::vector<std::pair<unsigned,float> > &Candidates,
 580                             unsigned NumCands,
 581                             SmallVector<LiveInterval*, 8> &SpillIntervals) {
 582   // We have figured out the *best* register to spill. But there are other
 583   // registers that are pretty good as well (spill weight within 3%). Spill
 584   // the one that has fewest defs and uses that conflict with cur.
 585   float Conflicts[3] = { 0.0f, 0.0f, 0.0f };
 586   SmallVector<LiveInterval*, 8> SLIs[3];
 587
 588   DOUT << "\tConsidering " << NumCands << " candidates: ";
 589   DEBUG(for (unsigned i = 0; i != NumCands; ++i)
 590           DOUT << tri_->getName(Candidates[i].first) << " ";
 591         DOUT << "\n";);
 592
 593   // Calculate the number of conflicts of each candidate.
 594   for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
 595     unsigned Reg = i->first->reg;
 596     unsigned PhysReg = vrm_->getPhys(Reg);
 597     if (!cur->overlapsFrom(*i->first, i->second))
 598       continue;
 599     for (unsigned j = 0; j < NumCands; ++j) {
 600       unsigned Candidate = Candidates[j].first;
 601       if (tri_->regsOverlap(PhysReg, Candidate)) {
 602         if (NumCands > 1)
 603           Conflicts[j] += getConflictWeight(cur, Reg, li_, mri_, loopInfo);
 604         SLIs[j].push_back(i->first);
 605       }
 606     }
 607   }
 608
 609   for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end(); ++i){
 610     unsigned Reg = i->first->reg;
 611     unsigned PhysReg = vrm_->getPhys(Reg);
 612     if (!cur->overlapsFrom(*i->first, i->second-1))
 613       continue;
 614     for (unsigned j = 0; j < NumCands; ++j) {
 615       unsigned Candidate = Candidates[j].first;
 616       if (tri_->regsOverlap(PhysReg, Candidate)) {
 617         if (NumCands > 1)
 618           Conflicts[j] += getConflictWeight(cur, Reg, li_, mri_, loopInfo);
 619         SLIs[j].push_back(i->first);
 620       }
 621     }
 622   }
 623
 624   // Which is the best candidate?
 625   unsigned BestCandidate = 0;
 626   float MinConflicts = Conflicts[0];
 627   for (unsigned i = 1; i != NumCands; ++i) {
 628     if (Conflicts[i] < MinConflicts) {
 629       BestCandidate = i;
 630       MinConflicts = Conflicts[i];
 631     }
 632   }
 633
 634   std::copy(SLIs[BestCandidate].begin(), SLIs[BestCandidate].end(),
 635             std::back_inserter(SpillIntervals));
 636 }
 637
 638 namespace {
 639   struct WeightCompare {
 640     typedef std::pair<unsigned, float> RegWeightPair;
 641     bool operator()(const RegWeightPair &LHS, const RegWeightPair &RHS) const {
 642       return LHS.second < RHS.second;
 643     }
 644   };
 645 }
 646
 647 static bool weightsAreClose(float w1, float w2) {
 648   if (!NewHeuristic)
 649     return false;
 650
 651   float diff = w1 - w2;
 652   if (diff <= 0.02f)  // Within 0.02f
 653     return true;
 654   return (diff / w2) <= 0.05f;  // Within 5%.
 655 }
 656
 657 /// assignRegOrStackSlotAtInterval - assign a register if one is available, or
 658 /// spill.
 659 void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur)
 660 {
 661   DOUT << "\tallocating current interval: ";
 662
 663   // This is an implicitly defined live interval, just assign any register.
 664   const TargetRegisterClass *RC = mri_->getRegClass(cur->reg);
 665   if (cur->empty()) {
 666     unsigned physReg = cur->preference;
 667     if (!physReg)
 668       physReg = *RC->allocation_order_begin(*mf_);
 669     DOUT <<  tri_->getName(physReg) << '\n';
 670     // Note the register is not really in use.
 671     vrm_->assignVirt2Phys(cur->reg, physReg);
 672     return;
 673   }
 674
 675   PhysRegTracker backupPrt = *prt_;
 676
 677   std::vector<std::pair<unsigned, float> > SpillWeightsToAdd;
 678   unsigned StartPosition = cur->beginNumber();
 679   const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC);
 680
 681   // If this live interval is defined by a move instruction and its source is
 682   // assigned a physical register that is compatible with the target register
 683   // class, then we should try to assign it the same register.
 684   // This can happen when the move is from a larger register class to a smaller
 685   // one, e.g. X86::mov32to32_. These move instructions are not coalescable.
 686   if (!cur->preference && cur->containsOneValue()) {
 687     VNInfo *vni = cur->getValNumInfo(0);
 688     if (vni->def && vni->def != ~1U && vni->def != ~0U) {
 689       MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def);
 690       unsigned SrcReg, DstReg;
 691       if (CopyMI && tii_->isMoveInstr(*CopyMI, SrcReg, DstReg)) {
 692         unsigned Reg = 0;
 693         if (TargetRegisterInfo::isPhysicalRegister(SrcReg))
 694           Reg = SrcReg;
 695         else if (vrm_->isAssignedReg(SrcReg))
 696           Reg = vrm_->getPhys(SrcReg);
 697         if (Reg && allocatableRegs_[Reg] && RC->contains(Reg))
 698           cur->preference = Reg;
 699       }
 700     }
 701   }
 702
 703   // for every interval in inactive we overlap with, mark the
 704   // register as not free and update spill weights.
 705   for (IntervalPtrs::const_iterator i = inactive_.begin(),
 706          e = inactive_.end(); i != e; ++i) {
 707     unsigned Reg = i->first->reg;
 708     assert(TargetRegisterInfo::isVirtualRegister(Reg) &&
 709            "Can only allocate virtual registers!");
 710     const TargetRegisterClass *RegRC = mri_->getRegClass(Reg);
 711     // If this is not in a related reg class to the register we're allocating,
 712     // don't check it.
 713     if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader &&
 714         cur->overlapsFrom(*i->first, i->second-1)) {
 715       Reg = vrm_->getPhys(Reg);
 716       prt_->addRegUse(Reg);
 717       SpillWeightsToAdd.push_back(std::make_pair(Reg, i->first->weight));
 718     }
 719   }
 720
 721   // Speculatively check to see if we can get a register right now.  If not,
 722   // we know we won't be able to by adding more constraints.  If so, we can
 723   // check to see if it is valid.  Doing an exhaustive search of the fixed_ list
 724   // is very bad (it contains all callee clobbered registers for any functions
 725   // with a call), so we want to avoid doing that if possible.
 726   unsigned physReg = getFreePhysReg(cur);
 727   unsigned BestPhysReg = physReg;
 728   if (physReg) {
 729     // We got a register.  However, if it's in the fixed_ list, we might
 730     // conflict with it.  Check to see if we conflict with it or any of its
 731     // aliases.
 732     SmallSet<unsigned, 8> RegAliases;
 733     for (const unsigned *AS = tri_->getAliasSet(physReg); *AS; ++AS)
 734       RegAliases.insert(*AS);
 735
 736     bool ConflictsWithFixed = false;
 737     for (unsigned i = 0, e = fixed_.size(); i != e; ++i) {
 738       IntervalPtr &IP = fixed_[i];
 739       if (physReg == IP.first->reg || RegAliases.count(IP.first->reg)) {
 740         // Okay, this reg is on the fixed list.  Check to see if we actually
 741         // conflict.
 742         LiveInterval *I = IP.first;
 743         if (I->endNumber() > StartPosition) {
 744           LiveInterval::iterator II = I->advanceTo(IP.second, StartPosition);
 745           IP.second = II;
 746           if (II != I->begin() && II->start > StartPosition)
 747             --II;
 748           if (cur->overlapsFrom(*I, II)) {
 749             ConflictsWithFixed = true;
 750             break;
 751           }
 752         }
 753       }
 754     }
 755
 756     // Okay, the register picked by our speculative getFreePhysReg call turned
 757     // out to be in use.  Actually add all of the conflicting fixed registers to
 758     // prt so we can do an accurate query.
 759     if (ConflictsWithFixed) {
 760       // For every interval in fixed we overlap with, mark the register as not
 761       // free and update spill weights.
 762       for (unsigned i = 0, e = fixed_.size(); i != e; ++i) {
 763         IntervalPtr &IP = fixed_[i];
 764         LiveInterval *I = IP.first;
 765
 766         const TargetRegisterClass *RegRC = OneClassForEachPhysReg[I->reg];
 767         if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader &&
 768             I->endNumber() > StartPosition) {
 769           LiveInterval::iterator II = I->advanceTo(IP.second, StartPosition);
 770           IP.second = II;
 771           if (II != I->begin() && II->start > StartPosition)
 772             --II;
 773           if (cur->overlapsFrom(*I, II)) {
 774             unsigned reg = I->reg;
 775             prt_->addRegUse(reg);
 776             SpillWeightsToAdd.push_back(std::make_pair(reg, I->weight));
 777           }
 778         }
 779       }
 780
 781       // Using the newly updated prt_ object, which includes conflicts in the
 782       // future, see if there are any registers available.
 783       physReg = getFreePhysReg(cur);
 784     }
 785   }
 786
 787   // Restore the physical register tracker, removing information about the
 788   // future.
 789   *prt_ = backupPrt;
 790
 791   // if we find a free register, we are done: assign this virtual to
 792   // the free physical register and add this interval to the active
 793   // list.
 794   if (physReg) {
 795     DOUT <<  tri_->getName(physReg) << '\n';
 796     vrm_->assignVirt2Phys(cur->reg, physReg);
 797     prt_->addRegUse(physReg);
 798     active_.push_back(std::make_pair(cur, cur->begin()));
 799     handled_.push_back(cur);
 800     return;
 801   }
 802   DOUT << "no free registers\n";
 803
 804   // Compile the spill weights into an array that is better for scanning.
 805   std::vector<float> SpillWeights(tri_->getNumRegs(), 0.0f);
 806   for (std::vector<std::pair<unsigned, float> >::iterator
 807        I = SpillWeightsToAdd.begin(), E = SpillWeightsToAdd.end(); I != E; ++I)
 808     updateSpillWeights(SpillWeights, I->first, I->second, tri_);
 809
 810   // for each interval in active, update spill weights.
 811   for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
 812        i != e; ++i) {
 813     unsigned reg = i->first->reg;
 814     assert(TargetRegisterInfo::isVirtualRegister(reg) &&
 815            "Can only allocate virtual registers!");
 816     reg = vrm_->getPhys(reg);
 817     updateSpillWeights(SpillWeights, reg, i->first->weight, tri_);
 818   }
 819
 820   DOUT << "\tassigning stack slot at interval "<< *cur << ":\n";
 821
 822   // Find a register to spill.
 823   float minWeight = HUGE_VALF;
 824   unsigned minReg = 0; /*cur->preference*/;  // Try the preferred register first.
 825
 826   bool Found = false;
 827   std::vector<std::pair<unsigned,float> > RegsWeights;
 828   if (!minReg || SpillWeights[minReg] == HUGE_VALF)
 829     for (TargetRegisterClass::iterator i = RC->allocation_order_begin(*mf_),
 830            e = RC->allocation_order_end(*mf_); i != e; ++i) {
 831       unsigned reg = *i;
 832       float regWeight = SpillWeights[reg];
 833       if (minWeight > regWeight)
 834         Found = true;
 835       RegsWeights.push_back(std::make_pair(reg, regWeight));
 836     }
 837
 838   // If we didn't find a register that is spillable, try aliases?
 839   if (!Found) {
 840     for (TargetRegisterClass::iterator i = RC->allocation_order_begin(*mf_),
 841            e = RC->allocation_order_end(*mf_); i != e; ++i) {
 842       unsigned reg = *i;
 843       // No need to worry about if the alias register size < regsize of RC.
 844       // We are going to spill all registers that alias it anyway.
 845       for (const unsigned* as = tri_->getAliasSet(reg); *as; ++as)
 846         RegsWeights.push_back(std::make_pair(*as, SpillWeights[*as]));
 847     }
 848   }
 849
 850   // Sort all potential spill candidates by weight.
 851   std::sort(RegsWeights.begin(), RegsWeights.end(), WeightCompare());
 852   minReg = RegsWeights[0].first;
 853   minWeight = RegsWeights[0].second;
 854   if (minWeight == HUGE_VALF) {
 855     // All registers must have inf weight. Just grab one!
 856     minReg = BestPhysReg ? BestPhysReg : *RC->allocation_order_begin(*mf_);
 857     if (cur->weight == HUGE_VALF ||
 858         li_->getApproximateInstructionCount(*cur) == 0) {
 859       // Spill a physical register around defs and uses.
 860       li_->spillPhysRegAroundRegDefsUses(*cur, minReg, *vrm_);
 861       assignRegOrStackSlotAtInterval(cur);
 862       return;
 863     }
 864   }
 865
 866   // Find up to 3 registers to consider as spill candidates.
 867   unsigned LastCandidate = RegsWeights.size() >= 3 ? 3 : 1;
 868   while (LastCandidate > 1) {
 869     if (weightsAreClose(RegsWeights[LastCandidate-1].second, minWeight))
 870       break;
 871     --LastCandidate;
 872   }
 873
 874   DOUT << "\t\tregister(s) with min weight(s): ";
 875   DEBUG(for (unsigned i = 0; i != LastCandidate; ++i)
 876           DOUT << tri_->getName(RegsWeights[i].first)
 877                << " (" << RegsWeights[i].second << ")\n");
 878
 879   // if the current has the minimum weight, we need to spill it and
 880   // add any added intervals back to unhandled, and restart
 881   // linearscan.
 882   if (cur->weight != HUGE_VALF && cur->weight <= minWeight) {
 883     DOUT << "\t\t\tspilling(c): " << *cur << '\n';
 884     float SSWeight;
 885     SmallVector<LiveInterval*, 8> spillIs;
 886     std::vector<LiveInterval*> added =
 887       li_->addIntervalsForSpills(*cur, spillIs, loopInfo, *vrm_, SSWeight);
 888     addStackInterval(cur, ls_, li_, SSWeight, *vrm_);
 889     if (added.empty())
 890       return;  // Early exit if all spills were folded.
 891
 892     // Merge added with unhandled.  Note that we know that
 893     // addIntervalsForSpills returns intervals sorted by their starting
 894     // point.
 895     for (unsigned i = 0, e = added.size(); i != e; ++i)
 896       unhandled_.push(added[i]);
 897     return;
 898   }
 899
 900   ++NumBacktracks;
 901
 902   // push the current interval back to unhandled since we are going
 903   // to re-run at least this iteration. Since we didn't modify it it
 904   // should go back right in the front of the list
 905   unhandled_.push(cur);
 906
 907   assert(TargetRegisterInfo::isPhysicalRegister(minReg) &&
 908          "did not choose a register to spill?");
 909
 910   // We spill all intervals aliasing the register with
 911   // minimum weight, rollback to the interval with the earliest
 912   // start point and let the linear scan algorithm run again
 913   SmallVector<LiveInterval*, 8> spillIs;
 914
 915   // Determine which intervals have to be spilled.
 916   findIntervalsToSpill(cur, RegsWeights, LastCandidate, spillIs);
 917
 918   // Set of spilled vregs (used later to rollback properly)
 919   SmallSet<unsigned, 8> spilled;
 920
 921   // The earliest start of a Spilled interval indicates up to where
 922   // in handled we need to roll back
 923   unsigned earliestStart = cur->beginNumber();
 924
 925   // Spill live intervals of virtual regs mapped to the physical register we
 926   // want to clear (and its aliases).  We only spill those that overlap with the
 927   // current interval as the rest do not affect its allocation. we also keep
 928   // track of the earliest start of all spilled live intervals since this will
 929   // mark our rollback point.
 930   std::vector<LiveInterval*> added;
 931   while (!spillIs.empty()) {
 932     LiveInterval *sli = spillIs.back();
 933     spillIs.pop_back();
 934     DOUT << "\t\t\tspilling(a): " << *sli << '\n';
 935     earliestStart = std::min(earliestStart, sli->beginNumber());
 936     float SSWeight;
 937     std::vector<LiveInterval*> newIs =
 938       li_->addIntervalsForSpills(*sli, spillIs, loopInfo, *vrm_, SSWeight);
 939     addStackInterval(sli, ls_, li_, SSWeight, *vrm_);
 940     std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
 941     spilled.insert(sli->reg);
 942   }
 943
 944   DOUT << "\t\trolling back to: " << earliestStart << '\n';
 945
 946   // Scan handled in reverse order up to the earliest start of a
 947   // spilled live interval and undo each one, restoring the state of
 948   // unhandled.
 949   while (!handled_.empty()) {
 950     LiveInterval* i = handled_.back();
 951     // If this interval starts before t we are done.
 952     if (i->beginNumber() < earliestStart)
 953       break;
 954     DOUT << "\t\t\tundo changes for: " << *i << '\n';
 955     handled_.pop_back();
 956
 957     // When undoing a live interval allocation we must know if it is active or
 958     // inactive to properly update the PhysRegTracker and the VirtRegMap.
 959     IntervalPtrs::iterator it;
 960     if ((it = FindIntervalInVector(active_, i)) != active_.end()) {
 961       active_.erase(it);
 962       assert(!TargetRegisterInfo::isPhysicalRegister(i->reg));
 963       if (!spilled.count(i->reg))
 964         unhandled_.push(i);
 965       prt_->delRegUse(vrm_->getPhys(i->reg));
 966       vrm_->clearVirt(i->reg);
 967     } else if ((it = FindIntervalInVector(inactive_, i)) != inactive_.end()) {
 968       inactive_.erase(it);
 969       assert(!TargetRegisterInfo::isPhysicalRegister(i->reg));
 970       if (!spilled.count(i->reg))
 971         unhandled_.push(i);
 972       vrm_->clearVirt(i->reg);
 973     } else {
 974       assert(TargetRegisterInfo::isVirtualRegister(i->reg) &&
 975              "Can only allocate virtual registers!");
 976       vrm_->clearVirt(i->reg);
 977       unhandled_.push(i);
 978     }
 979
 980     // It interval has a preference, it must be defined by a copy. Clear the
 981     // preference now since the source interval allocation may have been undone
 982     // as well.
 983     i->preference = 0;
 984   }
 985
 986   // Rewind the iterators in the active, inactive, and fixed lists back to the
 987   // point we reverted to.
 988   RevertVectorIteratorsTo(active_, earliestStart);
 989   RevertVectorIteratorsTo(inactive_, earliestStart);
 990   RevertVectorIteratorsTo(fixed_, earliestStart);
 991
 992   // scan the rest and undo each interval that expired after t and
 993   // insert it in active (the next iteration of the algorithm will
 994   // put it in inactive if required)
 995   for (unsigned i = 0, e = handled_.size(); i != e; ++i) {
 996     LiveInterval *HI = handled_[i];
 997     if (!HI->expiredAt(earliestStart) &&
 998         HI->expiredAt(cur->beginNumber())) {
 999       DOUT << "\t\t\tundo changes for: " << *HI << '\n';
1000       active_.push_back(std::make_pair(HI, HI->begin()));
1001       assert(!TargetRegisterInfo::isPhysicalRegister(HI->reg));
1002       prt_->addRegUse(vrm_->getPhys(HI->reg));
1003     }
1004   }
1005
1006   // merge added with unhandled
1007   for (unsigned i = 0, e = added.size(); i != e; ++i)
1008     unhandled_.push(added[i]);
1009 }
1010
1011 /// getFreePhysReg - return a free physical register for this virtual register
1012 /// interval if we have one, otherwise return 0.
1013 unsigned RALinScan::getFreePhysReg(LiveInterval *cur) {
1014   SmallVector<unsigned, 256> inactiveCounts;
1015   unsigned MaxInactiveCount = 0;
1016
1017   const TargetRegisterClass *RC = mri_->getRegClass(cur->reg);
1018   const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC);
1019
1020   for (IntervalPtrs::iterator i = inactive_.begin(), e = inactive_.end();
1021        i != e; ++i) {
1022     unsigned reg = i->first->reg;
1023     assert(TargetRegisterInfo::isVirtualRegister(reg) &&
1024            "Can only allocate virtual registers!");
1025
1026     // If this is not in a related reg class to the register we're allocating,
1027     // don't check it.
1028     const TargetRegisterClass *RegRC = mri_->getRegClass(reg);
1029     if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader) {
1030       reg = vrm_->getPhys(reg);
1031       if (inactiveCounts.size() <= reg)
1032         inactiveCounts.resize(reg+1);
1033       ++inactiveCounts[reg];
1034       MaxInactiveCount = std::max(MaxInactiveCount, inactiveCounts[reg]);
1035     }
1036   }
1037
1038   unsigned FreeReg = 0;
1039   unsigned FreeRegInactiveCount = 0;
1040
1041   // If copy coalescer has assigned a "preferred" register, check if it's
1042   // available first.
1043   if (cur->preference) {
1044     if (prt_->isRegAvail(cur->preference) &&
1045         RC->contains(cur->preference)) {
1046       DOUT << "\t\tassigned the preferred register: "
1047            << tri_->getName(cur->preference) << "\n";
1048       return cur->preference;
1049     } else
1050       DOUT << "\t\tunable to assign the preferred register: "
1051            << tri_->getName(cur->preference) << "\n";
1052   }
1053
1054   // Scan for the first available register.
1055   TargetRegisterClass::iterator I = RC->allocation_order_begin(*mf_);
1056   TargetRegisterClass::iterator E = RC->allocation_order_end(*mf_);
1057   assert(I != E && "No allocatable register in this register class!");
1058   for (; I != E; ++I)
1059     if (prt_->isRegAvail(*I)) {
1060       FreeReg = *I;
1061       if (FreeReg < inactiveCounts.size())
1062         FreeRegInactiveCount = inactiveCounts[FreeReg];
1063       else
1064         FreeRegInactiveCount = 0;
1065       break;
1066     }
1067
1068   // If there are no free regs, or if this reg has the max inactive count,
1069   // return this register.
1070   if (FreeReg == 0 || FreeRegInactiveCount == MaxInactiveCount) return FreeReg;
1071
1072   // Continue scanning the registers, looking for the one with the highest
1073   // inactive count.  Alkis found that this reduced register pressure very
1074   // slightly on X86 (in rev 1.94 of this file), though this should probably be
1075   // reevaluated now.
1076   for (; I != E; ++I) {
1077     unsigned Reg = *I;
1078     if (prt_->isRegAvail(Reg) && Reg < inactiveCounts.size() &&
1079         FreeRegInactiveCount < inactiveCounts[Reg]) {
1080       FreeReg = Reg;
1081       FreeRegInactiveCount = inactiveCounts[Reg];
1082       if (FreeRegInactiveCount == MaxInactiveCount)
1083         break;    // We found the one with the max inactive count.
1084     }
1085   }
1086
1087   return FreeReg;
1088 }
1089
1090 FunctionPass* llvm::createLinearScanRegisterAllocator() {
1091   return new RALinScan();
1092 }