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 "LiveDebugVariables.h"
  16 #include "LiveRangeEdit.h"
  17 #include "VirtRegMap.h"
  18 #include "VirtRegRewriter.h"
  19 #include "Spiller.h"
  20 #include "llvm/Analysis/AliasAnalysis.h"
  21 #include "llvm/Function.h"
  22 #include "llvm/CodeGen/CalcSpillWeights.h"
  23 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  24 #include "llvm/CodeGen/MachineFunctionPass.h"
  25 #include "llvm/CodeGen/MachineInstr.h"
  26 #include "llvm/CodeGen/MachineLoopInfo.h"
  27 #include "llvm/CodeGen/MachineRegisterInfo.h"
  28 #include "llvm/CodeGen/Passes.h"
  29 #include "llvm/CodeGen/RegAllocRegistry.h"
  30 #include "llvm/CodeGen/RegisterCoalescer.h"
  31 #include "llvm/Target/TargetRegisterInfo.h"
  32 #include "llvm/Target/TargetMachine.h"
  33 #include "llvm/Target/TargetOptions.h"
  34 #include "llvm/Target/TargetInstrInfo.h"
  35 #include "llvm/ADT/EquivalenceClasses.h"
  36 #include "llvm/ADT/SmallSet.h"
  37 #include "llvm/ADT/Statistic.h"
  38 #include "llvm/ADT/STLExtras.h"
  39 #include "llvm/Support/Debug.h"
  40 #include "llvm/Support/ErrorHandling.h"
  41 #include "llvm/Support/raw_ostream.h"
  42 #include <algorithm>
  43 #include <set>
  44 #include <queue>
  45 #include <memory>
  46 #include <cmath>
  47
  48 using namespace llvm;
  49
  50 STATISTIC(NumIters     , "Number of iterations performed");
  51 STATISTIC(NumBacktracks, "Number of times we had to backtrack");
  52 STATISTIC(NumCoalesce,   "Number of copies coalesced");
  53 STATISTIC(NumDowngrade,  "Number of registers downgraded");
  54
  55 static cl::opt<bool>
  56 NewHeuristic("new-spilling-heuristic",
  57              cl::desc("Use new spilling heuristic"),
  58              cl::init(false), cl::Hidden);
  59
  60 static cl::opt<bool>
  61 PreSplitIntervals("pre-alloc-split",
  62                   cl::desc("Pre-register allocation live interval splitting"),
  63                   cl::init(false), cl::Hidden);
  64
  65 static cl::opt<bool>
  66 TrivCoalesceEnds("trivial-coalesce-ends",
  67                   cl::desc("Attempt trivial coalescing of interval ends"),
  68                   cl::init(false), cl::Hidden);
  69
  70 static cl::opt<bool>
  71 AvoidWAWHazard("avoid-waw-hazard",
  72                cl::desc("Avoid write-write hazards for some register classes"),
  73                cl::init(false), cl::Hidden);
  74
  75 static RegisterRegAlloc
  76 linearscanRegAlloc("linearscan", "linear scan register allocator",
  77                    createLinearScanRegisterAllocator);
  78
  79 namespace {
  80   // When we allocate a register, add it to a fixed-size queue of
  81   // registers to skip in subsequent allocations. This trades a small
  82   // amount of register pressure and increased spills for flexibility in
  83   // the post-pass scheduler.
  84   //
  85   // Note that in a the number of registers used for reloading spills
  86   // will be one greater than the value of this option.
  87   //
  88   // One big limitation of this is that it doesn't differentiate between
  89   // different register classes. So on x86-64, if there is xmm register
  90   // pressure, it can caused fewer GPRs to be held in the queue.
  91   static cl::opt<unsigned>
  92   NumRecentlyUsedRegs("linearscan-skip-count",
  93                       cl::desc("Number of registers for linearscan to remember"
  94                                "to skip."),
  95                       cl::init(0),
  96                       cl::Hidden);
  97
  98   struct RALinScan : public MachineFunctionPass {
  99     static char ID;
 100     RALinScan() : MachineFunctionPass(ID) {
 101       initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry());
 102       initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
 103       initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
 104       initializeRegisterCoalescerAnalysisGroup(
 105         *PassRegistry::getPassRegistry());
 106       initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
 107       initializePreAllocSplittingPass(*PassRegistry::getPassRegistry());
 108       initializeLiveStacksPass(*PassRegistry::getPassRegistry());
 109       initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
 110       initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
 111       initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
 112       initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
 113
 114       // Initialize the queue to record recently-used registers.
 115       if (NumRecentlyUsedRegs > 0)
 116         RecentRegs.resize(NumRecentlyUsedRegs, 0);
 117       RecentNext = RecentRegs.begin();
 118       avoidWAW_ = 0;
 119     }
 120
 121     typedef std::pair<LiveInterval*, LiveInterval::iterator> IntervalPtr;
 122     typedef SmallVector<IntervalPtr, 32> IntervalPtrs;
 123   private:
 124     /// RelatedRegClasses - This structure is built the first time a function is
 125     /// compiled, and keeps track of which register classes have registers that
 126     /// belong to multiple classes or have aliases that are in other classes.
 127     EquivalenceClasses<const TargetRegisterClass*> RelatedRegClasses;
 128     DenseMap<unsigned, const TargetRegisterClass*> OneClassForEachPhysReg;
 129
 130     // NextReloadMap - For each register in the map, it maps to the another
 131     // register which is defined by a reload from the same stack slot and
 132     // both reloads are in the same basic block.
 133     DenseMap<unsigned, unsigned> NextReloadMap;
 134
 135     // DowngradedRegs - A set of registers which are being "downgraded", i.e.
 136     // un-favored for allocation.
 137     SmallSet<unsigned, 8> DowngradedRegs;
 138
 139     // DowngradeMap - A map from virtual registers to physical registers being
 140     // downgraded for the virtual registers.
 141     DenseMap<unsigned, unsigned> DowngradeMap;
 142
 143     MachineFunction* mf_;
 144     MachineRegisterInfo* mri_;
 145     const TargetMachine* tm_;
 146     const TargetRegisterInfo* tri_;
 147     const TargetInstrInfo* tii_;
 148     BitVector allocatableRegs_;
 149     BitVector reservedRegs_;
 150     LiveIntervals* li_;
 151     MachineLoopInfo *loopInfo;
 152
 153     /// handled_ - Intervals are added to the handled_ set in the order of their
 154     /// start value.  This is uses for backtracking.
 155     std::vector<LiveInterval*> handled_;
 156
 157     /// fixed_ - Intervals that correspond to machine registers.
 158     ///
 159     IntervalPtrs fixed_;
 160
 161     /// active_ - Intervals that are currently being processed, and which have a
 162     /// live range active for the current point.
 163     IntervalPtrs active_;
 164
 165     /// inactive_ - Intervals that are currently being processed, but which have
 166     /// a hold at the current point.
 167     IntervalPtrs inactive_;
 168
 169     typedef std::priority_queue<LiveInterval*,
 170                                 SmallVector<LiveInterval*, 64>,
 171                                 greater_ptr<LiveInterval> > IntervalHeap;
 172     IntervalHeap unhandled_;
 173
 174     /// regUse_ - Tracks register usage.
 175     SmallVector<unsigned, 32> regUse_;
 176     SmallVector<unsigned, 32> regUseBackUp_;
 177
 178     /// vrm_ - Tracks register assignments.
 179     VirtRegMap* vrm_;
 180
 181     std::auto_ptr<VirtRegRewriter> rewriter_;
 182
 183     std::auto_ptr<Spiller> spiller_;
 184
 185     // The queue of recently-used registers.
 186     SmallVector<unsigned, 4> RecentRegs;
 187     SmallVector<unsigned, 4>::iterator RecentNext;
 188
 189     // Last write-after-write register written.
 190     unsigned avoidWAW_;
 191
 192     // Record that we just picked this register.
 193     void recordRecentlyUsed(unsigned reg) {
 194       assert(reg != 0 && "Recently used register is NOREG!");
 195       if (!RecentRegs.empty()) {
 196         *RecentNext++ = reg;
 197         if (RecentNext == RecentRegs.end())
 198           RecentNext = RecentRegs.begin();
 199       }
 200     }
 201
 202   public:
 203     virtual const char* getPassName() const {
 204       return "Linear Scan Register Allocator";
 205     }
 206
 207     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 208       AU.setPreservesCFG();
 209       AU.addRequired<AliasAnalysis>();
 210       AU.addPreserved<AliasAnalysis>();
 211       AU.addRequired<LiveIntervals>();
 212       AU.addPreserved<SlotIndexes>();
 213       if (StrongPHIElim)
 214         AU.addRequiredID(StrongPHIEliminationID);
 215       // Make sure PassManager knows which analyses to make available
 216       // to coalescing and which analyses coalescing invalidates.
 217       AU.addRequiredTransitive<RegisterCoalescer>();
 218       AU.addRequired<CalculateSpillWeights>();
 219       if (PreSplitIntervals)
 220         AU.addRequiredID(PreAllocSplittingID);
 221       AU.addRequiredID(LiveStacksID);
 222       AU.addPreservedID(LiveStacksID);
 223       AU.addRequired<MachineLoopInfo>();
 224       AU.addPreserved<MachineLoopInfo>();
 225       AU.addRequired<VirtRegMap>();
 226       AU.addPreserved<VirtRegMap>();
 227       AU.addRequired<LiveDebugVariables>();
 228       AU.addPreserved<LiveDebugVariables>();
 229       AU.addRequiredID(MachineDominatorsID);
 230       AU.addPreservedID(MachineDominatorsID);
 231       MachineFunctionPass::getAnalysisUsage(AU);
 232     }
 233
 234     /// runOnMachineFunction - register allocate the whole function
 235     bool runOnMachineFunction(MachineFunction&);
 236
 237     // Determine if we skip this register due to its being recently used.
 238     bool isRecentlyUsed(unsigned reg) const {
 239       return reg == avoidWAW_ ||
 240        std::find(RecentRegs.begin(), RecentRegs.end(), reg) != RecentRegs.end();
 241     }
 242
 243   private:
 244     /// linearScan - the linear scan algorithm
 245     void linearScan();
 246
 247     /// initIntervalSets - initialize the interval sets.
 248     ///
 249     void initIntervalSets();
 250
 251     /// processActiveIntervals - expire old intervals and move non-overlapping
 252     /// ones to the inactive list.
 253     void processActiveIntervals(SlotIndex CurPoint);
 254
 255     /// processInactiveIntervals - expire old intervals and move overlapping
 256     /// ones to the active list.
 257     void processInactiveIntervals(SlotIndex CurPoint);
 258
 259     /// hasNextReloadInterval - Return the next liveinterval that's being
 260     /// defined by a reload from the same SS as the specified one.
 261     LiveInterval *hasNextReloadInterval(LiveInterval *cur);
 262
 263     /// DowngradeRegister - Downgrade a register for allocation.
 264     void DowngradeRegister(LiveInterval *li, unsigned Reg);
 265
 266     /// UpgradeRegister - Upgrade a register for allocation.
 267     void UpgradeRegister(unsigned Reg);
 268
 269     /// assignRegOrStackSlotAtInterval - assign a register if one
 270     /// is available, or spill.
 271     void assignRegOrStackSlotAtInterval(LiveInterval* cur);
 272
 273     void updateSpillWeights(std::vector<float> &Weights,
 274                             unsigned reg, float weight,
 275                             const TargetRegisterClass *RC);
 276
 277     /// findIntervalsToSpill - Determine the intervals to spill for the
 278     /// specified interval. It's passed the physical registers whose spill
 279     /// weight is the lowest among all the registers whose live intervals
 280     /// conflict with the interval.
 281     void findIntervalsToSpill(LiveInterval *cur,
 282                             std::vector<std::pair<unsigned,float> > &Candidates,
 283                             unsigned NumCands,
 284                             SmallVector<LiveInterval*, 8> &SpillIntervals);
 285
 286     /// attemptTrivialCoalescing - If a simple interval is defined by a copy,
 287     /// try to allocate the definition to the same register as the source,
 288     /// if the register is not defined during the life time of the interval.
 289     /// This eliminates a copy, and is used to coalesce copies which were not
 290     /// coalesced away before allocation either due to dest and src being in
 291     /// different register classes or because the coalescer was overly
 292     /// conservative.
 293     unsigned attemptTrivialCoalescing(LiveInterval &cur, unsigned Reg);
 294
 295     ///
 296     /// Register usage / availability tracking helpers.
 297     ///
 298
 299     void initRegUses() {
 300       regUse_.resize(tri_->getNumRegs(), 0);
 301       regUseBackUp_.resize(tri_->getNumRegs(), 0);
 302     }
 303
 304     void finalizeRegUses() {
 305 #ifndef NDEBUG
 306       // Verify all the registers are "freed".
 307       bool Error = false;
 308       for (unsigned i = 0, e = tri_->getNumRegs(); i != e; ++i) {
 309         if (regUse_[i] != 0) {
 310           dbgs() << tri_->getName(i) << " is still in use!\n";
 311           Error = true;
 312         }
 313       }
 314       if (Error)
 315         llvm_unreachable(0);
 316 #endif
 317       regUse_.clear();
 318       regUseBackUp_.clear();
 319     }
 320
 321     void addRegUse(unsigned physReg) {
 322       assert(TargetRegisterInfo::isPhysicalRegister(physReg) &&
 323              "should be physical register!");
 324       ++regUse_[physReg];
 325       for (const unsigned* as = tri_->getAliasSet(physReg); *as; ++as)
 326         ++regUse_[*as];
 327     }
 328
 329     void delRegUse(unsigned physReg) {
 330       assert(TargetRegisterInfo::isPhysicalRegister(physReg) &&
 331              "should be physical register!");
 332       assert(regUse_[physReg] != 0);
 333       --regUse_[physReg];
 334       for (const unsigned* as = tri_->getAliasSet(physReg); *as; ++as) {
 335         assert(regUse_[*as] != 0);
 336         --regUse_[*as];
 337       }
 338     }
 339
 340     bool isRegAvail(unsigned physReg) const {
 341       assert(TargetRegisterInfo::isPhysicalRegister(physReg) &&
 342              "should be physical register!");
 343       return regUse_[physReg] == 0;
 344     }
 345
 346     void backUpRegUses() {
 347       regUseBackUp_ = regUse_;
 348     }
 349
 350     void restoreRegUses() {
 351       regUse_ = regUseBackUp_;
 352     }
 353
 354     ///
 355     /// Register handling helpers.
 356     ///
 357
 358     /// getFreePhysReg - return a free physical register for this virtual
 359     /// register interval if we have one, otherwise return 0.
 360     unsigned getFreePhysReg(LiveInterval* cur);
 361     unsigned getFreePhysReg(LiveInterval* cur,
 362                             const TargetRegisterClass *RC,
 363                             unsigned MaxInactiveCount,
 364                             SmallVector<unsigned, 256> &inactiveCounts,
 365                             bool SkipDGRegs);
 366
 367     /// getFirstNonReservedPhysReg - return the first non-reserved physical
 368     /// register in the register class.
 369     unsigned getFirstNonReservedPhysReg(const TargetRegisterClass *RC) {
 370         TargetRegisterClass::iterator aoe = RC->allocation_order_end(*mf_);
 371         TargetRegisterClass::iterator i = RC->allocation_order_begin(*mf_);
 372         while (i != aoe && reservedRegs_.test(*i))
 373           ++i;
 374         assert(i != aoe && "All registers reserved?!");
 375         return *i;
 376       }
 377
 378     void ComputeRelatedRegClasses();
 379
 380     template <typename ItTy>
 381     void printIntervals(const char* const str, ItTy i, ItTy e) const {
 382       DEBUG({
 383           if (str)
 384             dbgs() << str << " intervals:\n";
 385
 386           for (; i != e; ++i) {
 387             dbgs() << '\t' << *i->first << " -> ";
 388
 389             unsigned reg = i->first->reg;
 390             if (TargetRegisterInfo::isVirtualRegister(reg))
 391               reg = vrm_->getPhys(reg);
 392
 393             dbgs() << tri_->getName(reg) << '\n';
 394           }
 395         });
 396     }
 397   };
 398   char RALinScan::ID = 0;
 399 }
 400
 401 INITIALIZE_PASS_BEGIN(RALinScan, "linearscan-regalloc",
 402                       "Linear Scan Register Allocator", false, false)
 403 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
 404 INITIALIZE_PASS_DEPENDENCY(StrongPHIElimination)
 405 INITIALIZE_PASS_DEPENDENCY(CalculateSpillWeights)
 406 INITIALIZE_PASS_DEPENDENCY(PreAllocSplitting)
 407 INITIALIZE_PASS_DEPENDENCY(LiveStacks)
 408 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
 409 INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
 410 INITIALIZE_AG_DEPENDENCY(RegisterCoalescer)
 411 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
 412 INITIALIZE_PASS_END(RALinScan, "linearscan-regalloc",
 413                     "Linear Scan Register Allocator", false, false)
 414
 415 void RALinScan::ComputeRelatedRegClasses() {
 416   // First pass, add all reg classes to the union, and determine at least one
 417   // reg class that each register is in.
 418   bool HasAliases = false;
 419   for (TargetRegisterInfo::regclass_iterator RCI = tri_->regclass_begin(),
 420        E = tri_->regclass_end(); RCI != E; ++RCI) {
 421     RelatedRegClasses.insert(*RCI);
 422     for (TargetRegisterClass::iterator I = (*RCI)->begin(), E = (*RCI)->end();
 423          I != E; ++I) {
 424       HasAliases = HasAliases || *tri_->getAliasSet(*I) != 0;
 425
 426       const TargetRegisterClass *&PRC = OneClassForEachPhysReg[*I];
 427       if (PRC) {
 428         // Already processed this register.  Just make sure we know that
 429         // multiple register classes share a register.
 430         RelatedRegClasses.unionSets(PRC, *RCI);
 431       } else {
 432         PRC = *RCI;
 433       }
 434     }
 435   }
 436
 437   // Second pass, now that we know conservatively what register classes each reg
 438   // belongs to, add info about aliases.  We don't need to do this for targets
 439   // without register aliases.
 440   if (HasAliases)
 441     for (DenseMap<unsigned, const TargetRegisterClass*>::iterator
 442          I = OneClassForEachPhysReg.begin(), E = OneClassForEachPhysReg.end();
 443          I != E; ++I)
 444       for (const unsigned *AS = tri_->getAliasSet(I->first); *AS; ++AS) {
 445         const TargetRegisterClass *AliasClass =
 446           OneClassForEachPhysReg.lookup(*AS);
 447         if (AliasClass)
 448           RelatedRegClasses.unionSets(I->second, AliasClass);
 449       }
 450 }
 451
 452 /// attemptTrivialCoalescing - If a simple interval is defined by a copy, try
 453 /// allocate the definition the same register as the source register if the
 454 /// register is not defined during live time of the interval. If the interval is
 455 /// killed by a copy, try to use the destination register. This eliminates a
 456 /// copy. This is used to coalesce copies which were not coalesced away before
 457 /// allocation either due to dest and src being in different register classes or
 458 /// because the coalescer was overly conservative.
 459 unsigned RALinScan::attemptTrivialCoalescing(LiveInterval &cur, unsigned Reg) {
 460   unsigned Preference = vrm_->getRegAllocPref(cur.reg);
 461   if ((Preference && Preference == Reg) || !cur.containsOneValue())
 462     return Reg;
 463
 464   // We cannot handle complicated live ranges. Simple linear stuff only.
 465   if (cur.ranges.size() != 1)
 466     return Reg;
 467
 468   const LiveRange &range = cur.ranges.front();
 469
 470   VNInfo *vni = range.valno;
 471   if (vni->isUnused() || !vni->def.isValid())
 472     return Reg;
 473
 474   unsigned CandReg;
 475   {
 476     MachineInstr *CopyMI;
 477     if ((CopyMI = li_->getInstructionFromIndex(vni->def)) && CopyMI->isCopy())
 478       // Defined by a copy, try to extend SrcReg forward
 479       CandReg = CopyMI->getOperand(1).getReg();
 480     else if (TrivCoalesceEnds &&
 481             (CopyMI = li_->getInstructionFromIndex(range.end.getBaseIndex())) &&
 482              CopyMI->isCopy() && cur.reg == CopyMI->getOperand(1).getReg())
 483       // Only used by a copy, try to extend DstReg backwards
 484       CandReg = CopyMI->getOperand(0).getReg();
 485     else
 486       return Reg;
 487
 488     // If the target of the copy is a sub-register then don't coalesce.
 489     if(CopyMI->getOperand(0).getSubReg())
 490       return Reg;
 491   }
 492
 493   if (TargetRegisterInfo::isVirtualRegister(CandReg)) {
 494     if (!vrm_->isAssignedReg(CandReg))
 495       return Reg;
 496     CandReg = vrm_->getPhys(CandReg);
 497   }
 498   if (Reg == CandReg)
 499     return Reg;
 500
 501   const TargetRegisterClass *RC = mri_->getRegClass(cur.reg);
 502   if (!RC->contains(CandReg))
 503     return Reg;
 504
 505   if (li_->conflictsWithPhysReg(cur, *vrm_, CandReg))
 506     return Reg;
 507
 508   // Try to coalesce.
 509   DEBUG(dbgs() << "Coalescing: " << cur << " -> " << tri_->getName(CandReg)
 510         << '\n');
 511   vrm_->clearVirt(cur.reg);
 512   vrm_->assignVirt2Phys(cur.reg, CandReg);
 513
 514   ++NumCoalesce;
 515   return CandReg;
 516 }
 517
 518 bool RALinScan::runOnMachineFunction(MachineFunction &fn) {
 519   mf_ = &fn;
 520   mri_ = &fn.getRegInfo();
 521   tm_ = &fn.getTarget();
 522   tri_ = tm_->getRegisterInfo();
 523   tii_ = tm_->getInstrInfo();
 524   allocatableRegs_ = tri_->getAllocatableSet(fn);
 525   reservedRegs_ = tri_->getReservedRegs(fn);
 526   li_ = &getAnalysis<LiveIntervals>();
 527   loopInfo = &getAnalysis<MachineLoopInfo>();
 528
 529   // We don't run the coalescer here because we have no reason to
 530   // interact with it.  If the coalescer requires interaction, it
 531   // won't do anything.  If it doesn't require interaction, we assume
 532   // it was run as a separate pass.
 533
 534   // If this is the first function compiled, compute the related reg classes.
 535   if (RelatedRegClasses.empty())
 536     ComputeRelatedRegClasses();
 537
 538   // Also resize register usage trackers.
 539   initRegUses();
 540
 541   vrm_ = &getAnalysis<VirtRegMap>();
 542   if (!rewriter_.get()) rewriter_.reset(createVirtRegRewriter());
 543
 544   spiller_.reset(createSpiller(*this, *mf_, *vrm_));
 545
 546   initIntervalSets();
 547
 548   linearScan();
 549
 550   // Rewrite spill code and update the PhysRegsUsed set.
 551   rewriter_->runOnMachineFunction(*mf_, *vrm_, li_);
 552
 553   // Write out new DBG_VALUE instructions.
 554   getAnalysis<LiveDebugVariables>().emitDebugValues(vrm_);
 555
 556   assert(unhandled_.empty() && "Unhandled live intervals remain!");
 557
 558   finalizeRegUses();
 559
 560   fixed_.clear();
 561   active_.clear();
 562   inactive_.clear();
 563   handled_.clear();
 564   NextReloadMap.clear();
 565   DowngradedRegs.clear();
 566   DowngradeMap.clear();
 567   spiller_.reset(0);
 568
 569   return true;
 570 }
 571
 572 /// initIntervalSets - initialize the interval sets.
 573 ///
 574 void RALinScan::initIntervalSets()
 575 {
 576   assert(unhandled_.empty() && fixed_.empty() &&
 577          active_.empty() && inactive_.empty() &&
 578          "interval sets should be empty on initialization");
 579
 580   handled_.reserve(li_->getNumIntervals());
 581
 582   for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) {
 583     if (TargetRegisterInfo::isPhysicalRegister(i->second->reg)) {
 584       if (!i->second->empty() && allocatableRegs_.test(i->second->reg)) {
 585         mri_->setPhysRegUsed(i->second->reg);
 586         fixed_.push_back(std::make_pair(i->second, i->second->begin()));
 587       }
 588     } else {
 589       if (i->second->empty()) {
 590         assignRegOrStackSlotAtInterval(i->second);
 591       }
 592       else
 593         unhandled_.push(i->second);
 594     }
 595   }
 596 }
 597
 598 void RALinScan::linearScan() {
 599   // linear scan algorithm
 600   DEBUG({
 601       dbgs() << "********** LINEAR SCAN **********\n"
 602              << "********** Function: "
 603              << mf_->getFunction()->getName() << '\n';
 604       printIntervals("fixed", fixed_.begin(), fixed_.end());
 605     });
 606
 607   while (!unhandled_.empty()) {
 608     // pick the interval with the earliest start point
 609     LiveInterval* cur = unhandled_.top();
 610     unhandled_.pop();
 611     ++NumIters;
 612     DEBUG(dbgs() << "\n*** CURRENT ***: " << *cur << '\n');
 613
 614     assert(!cur->empty() && "Empty interval in unhandled set.");
 615
 616     processActiveIntervals(cur->beginIndex());
 617     processInactiveIntervals(cur->beginIndex());
 618
 619     assert(TargetRegisterInfo::isVirtualRegister(cur->reg) &&
 620            "Can only allocate virtual registers!");
 621
 622     // Allocating a virtual register. try to find a free
 623     // physical register or spill an interval (possibly this one) in order to
 624     // assign it one.
 625     assignRegOrStackSlotAtInterval(cur);
 626
 627     DEBUG({
 628         printIntervals("active", active_.begin(), active_.end());
 629         printIntervals("inactive", inactive_.begin(), inactive_.end());
 630       });
 631   }
 632
 633   // Expire any remaining active intervals
 634   while (!active_.empty()) {
 635     IntervalPtr &IP = active_.back();
 636     unsigned reg = IP.first->reg;
 637     DEBUG(dbgs() << "\tinterval " << *IP.first << " expired\n");
 638     assert(TargetRegisterInfo::isVirtualRegister(reg) &&
 639            "Can only allocate virtual registers!");
 640     reg = vrm_->getPhys(reg);
 641     delRegUse(reg);
 642     active_.pop_back();
 643   }
 644
 645   // Expire any remaining inactive intervals
 646   DEBUG({
 647       for (IntervalPtrs::reverse_iterator
 648              i = inactive_.rbegin(); i != inactive_.rend(); ++i)
 649         dbgs() << "\tinterval " << *i->first << " expired\n";
 650     });
 651   inactive_.clear();
 652
 653   // Add live-ins to every BB except for entry. Also perform trivial coalescing.
 654   MachineFunction::iterator EntryMBB = mf_->begin();
 655   SmallVector<MachineBasicBlock*, 8> LiveInMBBs;
 656   for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) {
 657     LiveInterval &cur = *i->second;
 658     unsigned Reg = 0;
 659     bool isPhys = TargetRegisterInfo::isPhysicalRegister(cur.reg);
 660     if (isPhys)
 661       Reg = cur.reg;
 662     else if (vrm_->isAssignedReg(cur.reg))
 663       Reg = attemptTrivialCoalescing(cur, vrm_->getPhys(cur.reg));
 664     if (!Reg)
 665       continue;
 666     // Ignore splited live intervals.
 667     if (!isPhys && vrm_->getPreSplitReg(cur.reg))
 668       continue;
 669
 670     for (LiveInterval::Ranges::const_iterator I = cur.begin(), E = cur.end();
 671          I != E; ++I) {
 672       const LiveRange &LR = *I;
 673       if (li_->findLiveInMBBs(LR.start, LR.end, LiveInMBBs)) {
 674         for (unsigned i = 0, e = LiveInMBBs.size(); i != e; ++i)
 675           if (LiveInMBBs[i] != EntryMBB) {
 676             assert(TargetRegisterInfo::isPhysicalRegister(Reg) &&
 677                    "Adding a virtual register to livein set?");
 678             LiveInMBBs[i]->addLiveIn(Reg);
 679           }
 680         LiveInMBBs.clear();
 681       }
 682     }
 683   }
 684
 685   DEBUG(dbgs() << *vrm_);
 686
 687   // Look for physical registers that end up not being allocated even though
 688   // register allocator had to spill other registers in its register class.
 689   if (!vrm_->FindUnusedRegisters(li_))
 690     return;
 691 }
 692
 693 /// processActiveIntervals - expire old intervals and move non-overlapping ones
 694 /// to the inactive list.
 695 void RALinScan::processActiveIntervals(SlotIndex CurPoint)
 696 {
 697   DEBUG(dbgs() << "\tprocessing active intervals:\n");
 698
 699   for (unsigned i = 0, e = active_.size(); i != e; ++i) {
 700     LiveInterval *Interval = active_[i].first;
 701     LiveInterval::iterator IntervalPos = active_[i].second;
 702     unsigned reg = Interval->reg;
 703
 704     IntervalPos = Interval->advanceTo(IntervalPos, CurPoint);
 705
 706     if (IntervalPos == Interval->end()) {     // Remove expired intervals.
 707       DEBUG(dbgs() << "\t\tinterval " << *Interval << " expired\n");
 708       assert(TargetRegisterInfo::isVirtualRegister(reg) &&
 709              "Can only allocate virtual registers!");
 710       reg = vrm_->getPhys(reg);
 711       delRegUse(reg);
 712
 713       // Pop off the end of the list.
 714       active_[i] = active_.back();
 715       active_.pop_back();
 716       --i; --e;
 717
 718     } else if (IntervalPos->start > CurPoint) {
 719       // Move inactive intervals to inactive list.
 720       DEBUG(dbgs() << "\t\tinterval " << *Interval << " inactive\n");
 721       assert(TargetRegisterInfo::isVirtualRegister(reg) &&
 722              "Can only allocate virtual registers!");
 723       reg = vrm_->getPhys(reg);
 724       delRegUse(reg);
 725       // add to inactive.
 726       inactive_.push_back(std::make_pair(Interval, IntervalPos));
 727
 728       // Pop off the end of the list.
 729       active_[i] = active_.back();
 730       active_.pop_back();
 731       --i; --e;
 732     } else {
 733       // Otherwise, just update the iterator position.
 734       active_[i].second = IntervalPos;
 735     }
 736   }
 737 }
 738
 739 /// processInactiveIntervals - expire old intervals and move overlapping
 740 /// ones to the active list.
 741 void RALinScan::processInactiveIntervals(SlotIndex CurPoint)
 742 {
 743   DEBUG(dbgs() << "\tprocessing inactive intervals:\n");
 744
 745   for (unsigned i = 0, e = inactive_.size(); i != e; ++i) {
 746     LiveInterval *Interval = inactive_[i].first;
 747     LiveInterval::iterator IntervalPos = inactive_[i].second;
 748     unsigned reg = Interval->reg;
 749
 750     IntervalPos = Interval->advanceTo(IntervalPos, CurPoint);
 751
 752     if (IntervalPos == Interval->end()) {       // remove expired intervals.
 753       DEBUG(dbgs() << "\t\tinterval " << *Interval << " expired\n");
 754
 755       // Pop off the end of the list.
 756       inactive_[i] = inactive_.back();
 757       inactive_.pop_back();
 758       --i; --e;
 759     } else if (IntervalPos->start <= CurPoint) {
 760       // move re-activated intervals in active list
 761       DEBUG(dbgs() << "\t\tinterval " << *Interval << " active\n");
 762       assert(TargetRegisterInfo::isVirtualRegister(reg) &&
 763              "Can only allocate virtual registers!");
 764       reg = vrm_->getPhys(reg);
 765       addRegUse(reg);
 766       // add to active
 767       active_.push_back(std::make_pair(Interval, IntervalPos));
 768
 769       // Pop off the end of the list.
 770       inactive_[i] = inactive_.back();
 771       inactive_.pop_back();
 772       --i; --e;
 773     } else {
 774       // Otherwise, just update the iterator position.
 775       inactive_[i].second = IntervalPos;
 776     }
 777   }
 778 }
 779
 780 /// updateSpillWeights - updates the spill weights of the specifed physical
 781 /// register and its weight.
 782 void RALinScan::updateSpillWeights(std::vector<float> &Weights,
 783                                    unsigned reg, float weight,
 784                                    const TargetRegisterClass *RC) {
 785   SmallSet<unsigned, 4> Processed;
 786   SmallSet<unsigned, 4> SuperAdded;
 787   SmallVector<unsigned, 4> Supers;
 788   Weights[reg] += weight;
 789   Processed.insert(reg);
 790   for (const unsigned* as = tri_->getAliasSet(reg); *as; ++as) {
 791     Weights[*as] += weight;
 792     Processed.insert(*as);
 793     if (tri_->isSubRegister(*as, reg) &&
 794         SuperAdded.insert(*as) &&
 795         RC->contains(*as)) {
 796       Supers.push_back(*as);
 797     }
 798   }
 799
 800   // If the alias is a super-register, and the super-register is in the
 801   // register class we are trying to allocate. Then add the weight to all
 802   // sub-registers of the super-register even if they are not aliases.
 803   // e.g. allocating for GR32, bh is not used, updating bl spill weight.
 804   //      bl should get the same spill weight otherwise it will be chosen
 805   //      as a spill candidate since spilling bh doesn't make ebx available.
 806   for (unsigned i = 0, e = Supers.size(); i != e; ++i) {
 807     for (const unsigned *sr = tri_->getSubRegisters(Supers[i]); *sr; ++sr)
 808       if (!Processed.count(*sr))
 809         Weights[*sr] += weight;
 810   }
 811 }
 812
 813 static
 814 RALinScan::IntervalPtrs::iterator
 815 FindIntervalInVector(RALinScan::IntervalPtrs &IP, LiveInterval *LI) {
 816   for (RALinScan::IntervalPtrs::iterator I = IP.begin(), E = IP.end();
 817        I != E; ++I)
 818     if (I->first == LI) return I;
 819   return IP.end();
 820 }
 821
 822 static void RevertVectorIteratorsTo(RALinScan::IntervalPtrs &V,
 823                                     SlotIndex Point){
 824   for (unsigned i = 0, e = V.size(); i != e; ++i) {
 825     RALinScan::IntervalPtr &IP = V[i];
 826     LiveInterval::iterator I = std::upper_bound(IP.first->begin(),
 827                                                 IP.second, Point);
 828     if (I != IP.first->begin()) --I;
 829     IP.second = I;
 830   }
 831 }
 832
 833 /// getConflictWeight - Return the number of conflicts between cur
 834 /// live interval and defs and uses of Reg weighted by loop depthes.
 835 static
 836 float getConflictWeight(LiveInterval *cur, unsigned Reg, LiveIntervals *li_,
 837                         MachineRegisterInfo *mri_,
 838                         MachineLoopInfo *loopInfo) {
 839   float Conflicts = 0;
 840   for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(Reg),
 841          E = mri_->reg_end(); I != E; ++I) {
 842     MachineInstr *MI = &*I;
 843     if (cur->liveAt(li_->getInstructionIndex(MI))) {
 844       unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent());
 845       Conflicts += std::pow(10.0f, (float)loopDepth);
 846     }
 847   }
 848   return Conflicts;
 849 }
 850
 851 /// findIntervalsToSpill - Determine the intervals to spill for the
 852 /// specified interval. It's passed the physical registers whose spill
 853 /// weight is the lowest among all the registers whose live intervals
 854 /// conflict with the interval.
 855 void RALinScan::findIntervalsToSpill(LiveInterval *cur,
 856                             std::vector<std::pair<unsigned,float> > &Candidates,
 857                             unsigned NumCands,
 858                             SmallVector<LiveInterval*, 8> &SpillIntervals) {
 859   // We have figured out the *best* register to spill. But there are other
 860   // registers that are pretty good as well (spill weight within 3%). Spill
 861   // the one that has fewest defs and uses that conflict with cur.
 862   float Conflicts[3] = { 0.0f, 0.0f, 0.0f };
 863   SmallVector<LiveInterval*, 8> SLIs[3];
 864
 865   DEBUG({
 866       dbgs() << "\tConsidering " << NumCands << " candidates: ";
 867       for (unsigned i = 0; i != NumCands; ++i)
 868         dbgs() << tri_->getName(Candidates[i].first) << " ";
 869       dbgs() << "\n";
 870     });
 871
 872   // Calculate the number of conflicts of each candidate.
 873   for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
 874     unsigned Reg = i->first->reg;
 875     unsigned PhysReg = vrm_->getPhys(Reg);
 876     if (!cur->overlapsFrom(*i->first, i->second))
 877       continue;
 878     for (unsigned j = 0; j < NumCands; ++j) {
 879       unsigned Candidate = Candidates[j].first;
 880       if (tri_->regsOverlap(PhysReg, Candidate)) {
 881         if (NumCands > 1)
 882           Conflicts[j] += getConflictWeight(cur, Reg, li_, mri_, loopInfo);
 883         SLIs[j].push_back(i->first);
 884       }
 885     }
 886   }
 887
 888   for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end(); ++i){
 889     unsigned Reg = i->first->reg;
 890     unsigned PhysReg = vrm_->getPhys(Reg);
 891     if (!cur->overlapsFrom(*i->first, i->second-1))
 892       continue;
 893     for (unsigned j = 0; j < NumCands; ++j) {
 894       unsigned Candidate = Candidates[j].first;
 895       if (tri_->regsOverlap(PhysReg, Candidate)) {
 896         if (NumCands > 1)
 897           Conflicts[j] += getConflictWeight(cur, Reg, li_, mri_, loopInfo);
 898         SLIs[j].push_back(i->first);
 899       }
 900     }
 901   }
 902
 903   // Which is the best candidate?
 904   unsigned BestCandidate = 0;
 905   float MinConflicts = Conflicts[0];
 906   for (unsigned i = 1; i != NumCands; ++i) {
 907     if (Conflicts[i] < MinConflicts) {
 908       BestCandidate = i;
 909       MinConflicts = Conflicts[i];
 910     }
 911   }
 912
 913   std::copy(SLIs[BestCandidate].begin(), SLIs[BestCandidate].end(),
 914             std::back_inserter(SpillIntervals));
 915 }
 916
 917 namespace {
 918   struct WeightCompare {
 919   private:
 920     const RALinScan &Allocator;
 921
 922   public:
 923     WeightCompare(const RALinScan &Alloc) : Allocator(Alloc) {}
 924
 925     typedef std::pair<unsigned, float> RegWeightPair;
 926     bool operator()(const RegWeightPair &LHS, const RegWeightPair &RHS) const {
 927       return LHS.second < RHS.second && !Allocator.isRecentlyUsed(LHS.first);
 928     }
 929   };
 930 }
 931
 932 static bool weightsAreClose(float w1, float w2) {
 933   if (!NewHeuristic)
 934     return false;
 935
 936   float diff = w1 - w2;
 937   if (diff <= 0.02f)  // Within 0.02f
 938     return true;
 939   return (diff / w2) <= 0.05f;  // Within 5%.
 940 }
 941
 942 LiveInterval *RALinScan::hasNextReloadInterval(LiveInterval *cur) {
 943   DenseMap<unsigned, unsigned>::iterator I = NextReloadMap.find(cur->reg);
 944   if (I == NextReloadMap.end())
 945     return 0;
 946   return &li_->getInterval(I->second);
 947 }
 948
 949 void RALinScan::DowngradeRegister(LiveInterval *li, unsigned Reg) {
 950   for (const unsigned *AS = tri_->getOverlaps(Reg); *AS; ++AS) {
 951     bool isNew = DowngradedRegs.insert(*AS);
 952     (void)isNew; // Silence compiler warning.
 953     assert(isNew && "Multiple reloads holding the same register?");
 954     DowngradeMap.insert(std::make_pair(li->reg, *AS));
 955   }
 956   ++NumDowngrade;
 957 }
 958
 959 void RALinScan::UpgradeRegister(unsigned Reg) {
 960   if (Reg) {
 961     DowngradedRegs.erase(Reg);
 962     for (const unsigned *AS = tri_->getAliasSet(Reg); *AS; ++AS)
 963       DowngradedRegs.erase(*AS);
 964   }
 965 }
 966
 967 namespace {
 968   struct LISorter {
 969     bool operator()(LiveInterval* A, LiveInterval* B) {
 970       return A->beginIndex() < B->beginIndex();
 971     }
 972   };
 973 }
 974
 975 /// assignRegOrStackSlotAtInterval - assign a register if one is available, or
 976 /// spill.
 977 void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) {
 978   const TargetRegisterClass *RC = mri_->getRegClass(cur->reg);
 979   DEBUG(dbgs() << "\tallocating current interval from "
 980                << RC->getName() << ": ");
 981
 982   // This is an implicitly defined live interval, just assign any register.
 983   if (cur->empty()) {
 984     unsigned physReg = vrm_->getRegAllocPref(cur->reg);
 985     if (!physReg)
 986       physReg = getFirstNonReservedPhysReg(RC);
 987     DEBUG(dbgs() <<  tri_->getName(physReg) << '\n');
 988     // Note the register is not really in use.
 989     vrm_->assignVirt2Phys(cur->reg, physReg);
 990     return;
 991   }
 992
 993   backUpRegUses();
 994
 995   std::vector<std::pair<unsigned, float> > SpillWeightsToAdd;
 996   SlotIndex StartPosition = cur->beginIndex();
 997   const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC);
 998
 999   // If start of this live interval is defined by a move instruction and its
1000   // source is assigned a physical register that is compatible with the target
1001   // register class, then we should try to assign it the same register.
1002   // This can happen when the move is from a larger register class to a smaller
1003   // one, e.g. X86::mov32to32_. These move instructions are not coalescable.
1004   if (!vrm_->getRegAllocPref(cur->reg) && cur->hasAtLeastOneValue()) {
1005     VNInfo *vni = cur->begin()->valno;
1006     if (!vni->isUnused() && vni->def.isValid()) {
1007       MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def);
1008       if (CopyMI && CopyMI->isCopy()) {
1009         unsigned DstSubReg = CopyMI->getOperand(0).getSubReg();
1010         unsigned SrcReg = CopyMI->getOperand(1).getReg();
1011         unsigned SrcSubReg = CopyMI->getOperand(1).getSubReg();
1012         unsigned Reg = 0;
1013         if (TargetRegisterInfo::isPhysicalRegister(SrcReg))
1014           Reg = SrcReg;
1015         else if (vrm_->isAssignedReg(SrcReg))
1016           Reg = vrm_->getPhys(SrcReg);
1017         if (Reg) {
1018           if (SrcSubReg)
1019             Reg = tri_->getSubReg(Reg, SrcSubReg);
1020           if (DstSubReg)
1021             Reg = tri_->getMatchingSuperReg(Reg, DstSubReg, RC);
1022           if (Reg && allocatableRegs_[Reg] && RC->contains(Reg))
1023             mri_->setRegAllocationHint(cur->reg, 0, Reg);
1024         }
1025       }
1026     }
1027   }
1028
1029   // For every interval in inactive we overlap with, mark the
1030   // register as not free and update spill weights.
1031   for (IntervalPtrs::const_iterator i = inactive_.begin(),
1032          e = inactive_.end(); i != e; ++i) {
1033     unsigned Reg = i->first->reg;
1034     assert(TargetRegisterInfo::isVirtualRegister(Reg) &&
1035            "Can only allocate virtual registers!");
1036     const TargetRegisterClass *RegRC = mri_->getRegClass(Reg);
1037     // If this is not in a related reg class to the register we're allocating,
1038     // don't check it.
1039     if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader &&
1040         cur->overlapsFrom(*i->first, i->second-1)) {
1041       Reg = vrm_->getPhys(Reg);
1042       addRegUse(Reg);
1043       SpillWeightsToAdd.push_back(std::make_pair(Reg, i->first->weight));
1044     }
1045   }
1046
1047   // Speculatively check to see if we can get a register right now.  If not,
1048   // we know we won't be able to by adding more constraints.  If so, we can
1049   // check to see if it is valid.  Doing an exhaustive search of the fixed_ list
1050   // is very bad (it contains all callee clobbered registers for any functions
1051   // with a call), so we want to avoid doing that if possible.
1052   unsigned physReg = getFreePhysReg(cur);
1053   unsigned BestPhysReg = physReg;
1054   if (physReg) {
1055     // We got a register.  However, if it's in the fixed_ list, we might
1056     // conflict with it.  Check to see if we conflict with it or any of its
1057     // aliases.
1058     SmallSet<unsigned, 8> RegAliases;
1059     for (const unsigned *AS = tri_->getAliasSet(physReg); *AS; ++AS)
1060       RegAliases.insert(*AS);
1061
1062     bool ConflictsWithFixed = false;
1063     for (unsigned i = 0, e = fixed_.size(); i != e; ++i) {
1064       IntervalPtr &IP = fixed_[i];
1065       if (physReg == IP.first->reg || RegAliases.count(IP.first->reg)) {
1066         // Okay, this reg is on the fixed list.  Check to see if we actually
1067         // conflict.
1068         LiveInterval *I = IP.first;
1069         if (I->endIndex() > StartPosition) {
1070           LiveInterval::iterator II = I->advanceTo(IP.second, StartPosition);
1071           IP.second = II;
1072           if (II != I->begin() && II->start > StartPosition)
1073             --II;
1074           if (cur->overlapsFrom(*I, II)) {
1075             ConflictsWithFixed = true;
1076             break;
1077           }
1078         }
1079       }
1080     }
1081
1082     // Okay, the register picked by our speculative getFreePhysReg call turned
1083     // out to be in use.  Actually add all of the conflicting fixed registers to
1084     // regUse_ so we can do an accurate query.
1085     if (ConflictsWithFixed) {
1086       // For every interval in fixed we overlap with, mark the register as not
1087       // free and update spill weights.
1088       for (unsigned i = 0, e = fixed_.size(); i != e; ++i) {
1089         IntervalPtr &IP = fixed_[i];
1090         LiveInterval *I = IP.first;
1091
1092         const TargetRegisterClass *RegRC = OneClassForEachPhysReg[I->reg];
1093         if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader &&
1094             I->endIndex() > StartPosition) {
1095           LiveInterval::iterator II = I->advanceTo(IP.second, StartPosition);
1096           IP.second = II;
1097           if (II != I->begin() && II->start > StartPosition)
1098             --II;
1099           if (cur->overlapsFrom(*I, II)) {
1100             unsigned reg = I->reg;
1101             addRegUse(reg);
1102             SpillWeightsToAdd.push_back(std::make_pair(reg, I->weight));
1103           }
1104         }
1105       }
1106
1107       // Using the newly updated regUse_ object, which includes conflicts in the
1108       // future, see if there are any registers available.
1109       physReg = getFreePhysReg(cur);
1110     }
1111   }
1112
1113   // Restore the physical register tracker, removing information about the
1114   // future.
1115   restoreRegUses();
1116
1117   // If we find a free register, we are done: assign this virtual to
1118   // the free physical register and add this interval to the active
1119   // list.
1120   if (physReg) {
1121     DEBUG(dbgs() <<  tri_->getName(physReg) << '\n');
1122     assert(RC->contains(physReg) && "Invalid candidate");
1123     vrm_->assignVirt2Phys(cur->reg, physReg);
1124     addRegUse(physReg);
1125     active_.push_back(std::make_pair(cur, cur->begin()));
1126     handled_.push_back(cur);
1127
1128     // Remember physReg for avoiding a write-after-write hazard in the next
1129     // instruction.
1130     if (AvoidWAWHazard &&
1131         tri_->avoidWriteAfterWrite(mri_->getRegClass(cur->reg)))
1132       avoidWAW_ = physReg;
1133
1134     // "Upgrade" the physical register since it has been allocated.
1135     UpgradeRegister(physReg);
1136     if (LiveInterval *NextReloadLI = hasNextReloadInterval(cur)) {
1137       // "Downgrade" physReg to try to keep physReg from being allocated until
1138       // the next reload from the same SS is allocated.
1139       mri_->setRegAllocationHint(NextReloadLI->reg, 0, physReg);
1140       DowngradeRegister(cur, physReg);
1141     }
1142     return;
1143   }
1144   DEBUG(dbgs() << "no free registers\n");
1145
1146   // Compile the spill weights into an array that is better for scanning.
1147   std::vector<float> SpillWeights(tri_->getNumRegs(), 0.0f);
1148   for (std::vector<std::pair<unsigned, float> >::iterator
1149        I = SpillWeightsToAdd.begin(), E = SpillWeightsToAdd.end(); I != E; ++I)
1150     updateSpillWeights(SpillWeights, I->first, I->second, RC);
1151
1152   // for each interval in active, update spill weights.
1153   for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
1154        i != e; ++i) {
1155     unsigned reg = i->first->reg;
1156     assert(TargetRegisterInfo::isVirtualRegister(reg) &&
1157            "Can only allocate virtual registers!");
1158     reg = vrm_->getPhys(reg);
1159     updateSpillWeights(SpillWeights, reg, i->first->weight, RC);
1160   }
1161
1162   DEBUG(dbgs() << "\tassigning stack slot at interval "<< *cur << ":\n");
1163
1164   // Find a register to spill.
1165   float minWeight = HUGE_VALF;
1166   unsigned minReg = 0;
1167
1168   bool Found = false;
1169   std::vector<std::pair<unsigned,float> > RegsWeights;
1170   if (!minReg || SpillWeights[minReg] == HUGE_VALF)
1171     for (TargetRegisterClass::iterator i = RC->allocation_order_begin(*mf_),
1172            e = RC->allocation_order_end(*mf_); i != e; ++i) {
1173       unsigned reg = *i;
1174       float regWeight = SpillWeights[reg];
1175       // Don't even consider reserved regs.
1176       if (reservedRegs_.test(reg))
1177         continue;
1178       // Skip recently allocated registers and reserved registers.
1179       if (minWeight > regWeight && !isRecentlyUsed(reg))
1180         Found = true;
1181       RegsWeights.push_back(std::make_pair(reg, regWeight));
1182     }
1183
1184   // If we didn't find a register that is spillable, try aliases?
1185   if (!Found) {
1186     for (TargetRegisterClass::iterator i = RC->allocation_order_begin(*mf_),
1187            e = RC->allocation_order_end(*mf_); i != e; ++i) {
1188       unsigned reg = *i;
1189       if (reservedRegs_.test(reg))
1190         continue;
1191       // No need to worry about if the alias register size < regsize of RC.
1192       // We are going to spill all registers that alias it anyway.
1193       for (const unsigned* as = tri_->getAliasSet(reg); *as; ++as)
1194         RegsWeights.push_back(std::make_pair(*as, SpillWeights[*as]));
1195     }
1196   }
1197
1198   // Sort all potential spill candidates by weight.
1199   std::sort(RegsWeights.begin(), RegsWeights.end(), WeightCompare(*this));
1200   minReg = RegsWeights[0].first;
1201   minWeight = RegsWeights[0].second;
1202   if (minWeight == HUGE_VALF) {
1203     // All registers must have inf weight. Just grab one!
1204     minReg = BestPhysReg ? BestPhysReg : getFirstNonReservedPhysReg(RC);
1205     if (cur->weight == HUGE_VALF ||
1206         li_->getApproximateInstructionCount(*cur) == 0) {
1207       // Spill a physical register around defs and uses.
1208       if (li_->spillPhysRegAroundRegDefsUses(*cur, minReg, *vrm_)) {
1209         // spillPhysRegAroundRegDefsUses may have invalidated iterator stored
1210         // in fixed_. Reset them.
1211         for (unsigned i = 0, e = fixed_.size(); i != e; ++i) {
1212           IntervalPtr &IP = fixed_[i];
1213           LiveInterval *I = IP.first;
1214           if (I->reg == minReg || tri_->isSubRegister(minReg, I->reg))
1215             IP.second = I->advanceTo(I->begin(), StartPosition);
1216         }
1217
1218         DowngradedRegs.clear();
1219         assignRegOrStackSlotAtInterval(cur);
1220       } else {
1221         assert(false && "Ran out of registers during register allocation!");
1222         report_fatal_error("Ran out of registers during register allocation!");
1223       }
1224       return;
1225     }
1226   }
1227
1228   // Find up to 3 registers to consider as spill candidates.
1229   unsigned LastCandidate = RegsWeights.size() >= 3 ? 3 : 1;
1230   while (LastCandidate > 1) {
1231     if (weightsAreClose(RegsWeights[LastCandidate-1].second, minWeight))
1232       break;
1233     --LastCandidate;
1234   }
1235
1236   DEBUG({
1237       dbgs() << "\t\tregister(s) with min weight(s): ";
1238
1239       for (unsigned i = 0; i != LastCandidate; ++i)
1240         dbgs() << tri_->getName(RegsWeights[i].first)
1241                << " (" << RegsWeights[i].second << ")\n";
1242     });
1243
1244   // If the current has the minimum weight, we need to spill it and
1245   // add any added intervals back to unhandled, and restart
1246   // linearscan.
1247   if (cur->weight != HUGE_VALF && cur->weight <= minWeight) {
1248     DEBUG(dbgs() << "\t\t\tspilling(c): " << *cur << '\n');
1249     SmallVector<LiveInterval*, 8> added;
1250     LiveRangeEdit LRE(*cur, added);
1251     spiller_->spill(LRE);
1252
1253     std::sort(added.begin(), added.end(), LISorter());
1254     if (added.empty())
1255       return;  // Early exit if all spills were folded.
1256
1257     // Merge added with unhandled.  Note that we have already sorted
1258     // intervals returned by addIntervalsForSpills by their starting
1259     // point.
1260     // This also update the NextReloadMap. That is, it adds mapping from a
1261     // register defined by a reload from SS to the next reload from SS in the
1262     // same basic block.
1263     MachineBasicBlock *LastReloadMBB = 0;
1264     LiveInterval *LastReload = 0;
1265     int LastReloadSS = VirtRegMap::NO_STACK_SLOT;
1266     for (unsigned i = 0, e = added.size(); i != e; ++i) {
1267       LiveInterval *ReloadLi = added[i];
1268       if (ReloadLi->weight == HUGE_VALF &&
1269           li_->getApproximateInstructionCount(*ReloadLi) == 0) {
1270         SlotIndex ReloadIdx = ReloadLi->beginIndex();
1271         MachineBasicBlock *ReloadMBB = li_->getMBBFromIndex(ReloadIdx);
1272         int ReloadSS = vrm_->getStackSlot(ReloadLi->reg);
1273         if (LastReloadMBB == ReloadMBB && LastReloadSS == ReloadSS) {
1274           // Last reload of same SS is in the same MBB. We want to try to
1275           // allocate both reloads the same register and make sure the reg
1276           // isn't clobbered in between if at all possible.
1277           assert(LastReload->beginIndex() < ReloadIdx);
1278           NextReloadMap.insert(std::make_pair(LastReload->reg, ReloadLi->reg));
1279         }
1280         LastReloadMBB = ReloadMBB;
1281         LastReload = ReloadLi;
1282         LastReloadSS = ReloadSS;
1283       }
1284       unhandled_.push(ReloadLi);
1285     }
1286     return;
1287   }
1288
1289   ++NumBacktracks;
1290
1291   // Push the current interval back to unhandled since we are going
1292   // to re-run at least this iteration. Since we didn't modify it it
1293   // should go back right in the front of the list
1294   unhandled_.push(cur);
1295
1296   assert(TargetRegisterInfo::isPhysicalRegister(minReg) &&
1297          "did not choose a register to spill?");
1298
1299   // We spill all intervals aliasing the register with
1300   // minimum weight, rollback to the interval with the earliest
1301   // start point and let the linear scan algorithm run again
1302   SmallVector<LiveInterval*, 8> spillIs;
1303
1304   // Determine which intervals have to be spilled.
1305   findIntervalsToSpill(cur, RegsWeights, LastCandidate, spillIs);
1306
1307   // Set of spilled vregs (used later to rollback properly)
1308   SmallSet<unsigned, 8> spilled;
1309
1310   // The earliest start of a Spilled interval indicates up to where
1311   // in handled we need to roll back
1312   assert(!spillIs.empty() && "No spill intervals?");
1313   SlotIndex earliestStart = spillIs[0]->beginIndex();
1314
1315   // Spill live intervals of virtual regs mapped to the physical register we
1316   // want to clear (and its aliases).  We only spill those that overlap with the
1317   // current interval as the rest do not affect its allocation. we also keep
1318   // track of the earliest start of all spilled live intervals since this will
1319   // mark our rollback point.
1320   SmallVector<LiveInterval*, 8> added;
1321   while (!spillIs.empty()) {
1322     LiveInterval *sli = spillIs.back();
1323     spillIs.pop_back();
1324     DEBUG(dbgs() << "\t\t\tspilling(a): " << *sli << '\n');
1325     if (sli->beginIndex() < earliestStart)
1326       earliestStart = sli->beginIndex();
1327     LiveRangeEdit LRE(*sli, added, 0, &spillIs);
1328     spiller_->spill(LRE);
1329     spilled.insert(sli->reg);
1330   }
1331
1332   // Include any added intervals in earliestStart.
1333   for (unsigned i = 0, e = added.size(); i != e; ++i) {
1334     SlotIndex SI = added[i]->beginIndex();
1335     if (SI < earliestStart)
1336       earliestStart = SI;
1337   }
1338
1339   DEBUG(dbgs() << "\t\trolling back to: " << earliestStart << '\n');
1340
1341   // Scan handled in reverse order up to the earliest start of a
1342   // spilled live interval and undo each one, restoring the state of
1343   // unhandled.
1344   while (!handled_.empty()) {
1345     LiveInterval* i = handled_.back();
1346     // If this interval starts before t we are done.
1347     if (!i->empty() && i->beginIndex() < earliestStart)
1348       break;
1349     DEBUG(dbgs() << "\t\t\tundo changes for: " << *i << '\n');
1350     handled_.pop_back();
1351
1352     // When undoing a live interval allocation we must know if it is active or
1353     // inactive to properly update regUse_ and the VirtRegMap.
1354     IntervalPtrs::iterator it;
1355     if ((it = FindIntervalInVector(active_, i)) != active_.end()) {
1356       active_.erase(it);
1357       assert(!TargetRegisterInfo::isPhysicalRegister(i->reg));
1358       if (!spilled.count(i->reg))
1359         unhandled_.push(i);
1360       delRegUse(vrm_->getPhys(i->reg));
1361       vrm_->clearVirt(i->reg);
1362     } else if ((it = FindIntervalInVector(inactive_, i)) != inactive_.end()) {
1363       inactive_.erase(it);
1364       assert(!TargetRegisterInfo::isPhysicalRegister(i->reg));
1365       if (!spilled.count(i->reg))
1366         unhandled_.push(i);
1367       vrm_->clearVirt(i->reg);
1368     } else {
1369       assert(TargetRegisterInfo::isVirtualRegister(i->reg) &&
1370              "Can only allocate virtual registers!");
1371       vrm_->clearVirt(i->reg);
1372       unhandled_.push(i);
1373     }
1374
1375     DenseMap<unsigned, unsigned>::iterator ii = DowngradeMap.find(i->reg);
1376     if (ii == DowngradeMap.end())
1377       // It interval has a preference, it must be defined by a copy. Clear the
1378       // preference now since the source interval allocation may have been
1379       // undone as well.
1380       mri_->setRegAllocationHint(i->reg, 0, 0);
1381     else {
1382       UpgradeRegister(ii->second);
1383     }
1384   }
1385
1386   // Rewind the iterators in the active, inactive, and fixed lists back to the
1387   // point we reverted to.
1388   RevertVectorIteratorsTo(active_, earliestStart);
1389   RevertVectorIteratorsTo(inactive_, earliestStart);
1390   RevertVectorIteratorsTo(fixed_, earliestStart);
1391
1392   // Scan the rest and undo each interval that expired after t and
1393   // insert it in active (the next iteration of the algorithm will
1394   // put it in inactive if required)
1395   for (unsigned i = 0, e = handled_.size(); i != e; ++i) {
1396     LiveInterval *HI = handled_[i];
1397     if (!HI->expiredAt(earliestStart) &&
1398         HI->expiredAt(cur->beginIndex())) {
1399       DEBUG(dbgs() << "\t\t\tundo changes for: " << *HI << '\n');
1400       active_.push_back(std::make_pair(HI, HI->begin()));
1401       assert(!TargetRegisterInfo::isPhysicalRegister(HI->reg));
1402       addRegUse(vrm_->getPhys(HI->reg));
1403     }
1404   }
1405
1406   // Merge added with unhandled.
1407   // This also update the NextReloadMap. That is, it adds mapping from a
1408   // register defined by a reload from SS to the next reload from SS in the
1409   // same basic block.
1410   MachineBasicBlock *LastReloadMBB = 0;
1411   LiveInterval *LastReload = 0;
1412   int LastReloadSS = VirtRegMap::NO_STACK_SLOT;
1413   std::sort(added.begin(), added.end(), LISorter());
1414   for (unsigned i = 0, e = added.size(); i != e; ++i) {
1415     LiveInterval *ReloadLi = added[i];
1416     if (ReloadLi->weight == HUGE_VALF &&
1417         li_->getApproximateInstructionCount(*ReloadLi) == 0) {
1418       SlotIndex ReloadIdx = ReloadLi->beginIndex();
1419       MachineBasicBlock *ReloadMBB = li_->getMBBFromIndex(ReloadIdx);
1420       int ReloadSS = vrm_->getStackSlot(ReloadLi->reg);
1421       if (LastReloadMBB == ReloadMBB && LastReloadSS == ReloadSS) {
1422         // Last reload of same SS is in the same MBB. We want to try to
1423         // allocate both reloads the same register and make sure the reg
1424         // isn't clobbered in between if at all possible.
1425         assert(LastReload->beginIndex() < ReloadIdx);
1426         NextReloadMap.insert(std::make_pair(LastReload->reg, ReloadLi->reg));
1427       }
1428       LastReloadMBB = ReloadMBB;
1429       LastReload = ReloadLi;
1430       LastReloadSS = ReloadSS;
1431     }
1432     unhandled_.push(ReloadLi);
1433   }
1434 }
1435
1436 unsigned RALinScan::getFreePhysReg(LiveInterval* cur,
1437                                    const TargetRegisterClass *RC,
1438                                    unsigned MaxInactiveCount,
1439                                    SmallVector<unsigned, 256> &inactiveCounts,
1440                                    bool SkipDGRegs) {
1441   unsigned FreeReg = 0;
1442   unsigned FreeRegInactiveCount = 0;
1443
1444   std::pair<unsigned, unsigned> Hint = mri_->getRegAllocationHint(cur->reg);
1445   // Resolve second part of the hint (if possible) given the current allocation.
1446   unsigned physReg = Hint.second;
1447   if (TargetRegisterInfo::isVirtualRegister(physReg) && vrm_->hasPhys(physReg))
1448     physReg = vrm_->getPhys(physReg);
1449
1450   TargetRegisterClass::iterator I, E;
1451   tie(I, E) = tri_->getAllocationOrder(RC, Hint.first, physReg, *mf_);
1452   assert(I != E && "No allocatable register in this register class!");
1453
1454   // Scan for the first available register.
1455   for (; I != E; ++I) {
1456     unsigned Reg = *I;
1457     // Ignore "downgraded" registers.
1458     if (SkipDGRegs && DowngradedRegs.count(Reg))
1459       continue;
1460     // Skip reserved registers.
1461     if (reservedRegs_.test(Reg))
1462       continue;
1463     // Skip recently allocated registers.
1464     if (isRegAvail(Reg) && (!SkipDGRegs || !isRecentlyUsed(Reg))) {
1465       FreeReg = Reg;
1466       if (FreeReg < inactiveCounts.size())
1467         FreeRegInactiveCount = inactiveCounts[FreeReg];
1468       else
1469         FreeRegInactiveCount = 0;
1470       break;
1471     }
1472   }
1473
1474   // If there are no free regs, or if this reg has the max inactive count,
1475   // return this register.
1476   if (FreeReg == 0 || FreeRegInactiveCount == MaxInactiveCount) {
1477     // Remember what register we picked so we can skip it next time.
1478     if (FreeReg != 0) recordRecentlyUsed(FreeReg);
1479     return FreeReg;
1480   }
1481
1482   // Continue scanning the registers, looking for the one with the highest
1483   // inactive count.  Alkis found that this reduced register pressure very
1484   // slightly on X86 (in rev 1.94 of this file), though this should probably be
1485   // reevaluated now.
1486   for (; I != E; ++I) {
1487     unsigned Reg = *I;
1488     // Ignore "downgraded" registers.
1489     if (SkipDGRegs && DowngradedRegs.count(Reg))
1490       continue;
1491     // Skip reserved registers.
1492     if (reservedRegs_.test(Reg))
1493       continue;
1494     if (isRegAvail(Reg) && Reg < inactiveCounts.size() &&
1495         FreeRegInactiveCount < inactiveCounts[Reg] &&
1496         (!SkipDGRegs || !isRecentlyUsed(Reg))) {
1497       FreeReg = Reg;
1498       FreeRegInactiveCount = inactiveCounts[Reg];
1499       if (FreeRegInactiveCount == MaxInactiveCount)
1500         break;    // We found the one with the max inactive count.
1501     }
1502   }
1503
1504   // Remember what register we picked so we can skip it next time.
1505   recordRecentlyUsed(FreeReg);
1506
1507   return FreeReg;
1508 }
1509
1510 /// getFreePhysReg - return a free physical register for this virtual register
1511 /// interval if we have one, otherwise return 0.
1512 unsigned RALinScan::getFreePhysReg(LiveInterval *cur) {
1513   SmallVector<unsigned, 256> inactiveCounts;
1514   unsigned MaxInactiveCount = 0;
1515
1516   const TargetRegisterClass *RC = mri_->getRegClass(cur->reg);
1517   const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC);
1518
1519   for (IntervalPtrs::iterator i = inactive_.begin(), e = inactive_.end();
1520        i != e; ++i) {
1521     unsigned reg = i->first->reg;
1522     assert(TargetRegisterInfo::isVirtualRegister(reg) &&
1523            "Can only allocate virtual registers!");
1524
1525     // If this is not in a related reg class to the register we're allocating,
1526     // don't check it.
1527     const TargetRegisterClass *RegRC = mri_->getRegClass(reg);
1528     if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader) {
1529       reg = vrm_->getPhys(reg);
1530       if (inactiveCounts.size() <= reg)
1531         inactiveCounts.resize(reg+1);
1532       ++inactiveCounts[reg];
1533       MaxInactiveCount = std::max(MaxInactiveCount, inactiveCounts[reg]);
1534     }
1535   }
1536
1537   // If copy coalescer has assigned a "preferred" register, check if it's
1538   // available first.
1539   unsigned Preference = vrm_->getRegAllocPref(cur->reg);
1540   if (Preference) {
1541     DEBUG(dbgs() << "(preferred: " << tri_->getName(Preference) << ") ");
1542     if (isRegAvail(Preference) &&
1543         RC->contains(Preference))
1544       return Preference;
1545   }
1546
1547   unsigned FreeReg = getFreePhysReg(cur, RC, MaxInactiveCount, inactiveCounts,
1548                                     true);
1549   if (FreeReg)
1550     return FreeReg;
1551   return getFreePhysReg(cur, RC, MaxInactiveCount, inactiveCounts, false);
1552 }
1553
1554 FunctionPass* llvm::createLinearScanRegisterAllocator() {
1555   return new RALinScan();
1556 }