lib/CodeGen/RegAllocGreedy.cpp

   1 //===-- RegAllocGreedy.cpp - greedy 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 defines the RAGreedy function pass for register allocation in
  11 // optimized builds.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #define DEBUG_TYPE "regalloc"
  16 #include "AllocationOrder.h"
  17 #include "LiveIntervalUnion.h"
  18 #include "LiveRangeEdit.h"
  19 #include "RegAllocBase.h"
  20 #include "Spiller.h"
  21 #include "SpillPlacement.h"
  22 #include "SplitKit.h"
  23 #include "VirtRegMap.h"
  24 #include "VirtRegRewriter.h"
  25 #include "llvm/Analysis/AliasAnalysis.h"
  26 #include "llvm/Function.h"
  27 #include "llvm/PassAnalysisSupport.h"
  28 #include "llvm/CodeGen/CalcSpillWeights.h"
  29 #include "llvm/CodeGen/EdgeBundles.h"
  30 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  31 #include "llvm/CodeGen/LiveStackAnalysis.h"
  32 #include "llvm/CodeGen/MachineDominators.h"
  33 #include "llvm/CodeGen/MachineFunctionPass.h"
  34 #include "llvm/CodeGen/MachineLoopInfo.h"
  35 #include "llvm/CodeGen/MachineLoopRanges.h"
  36 #include "llvm/CodeGen/MachineRegisterInfo.h"
  37 #include "llvm/CodeGen/Passes.h"
  38 #include "llvm/CodeGen/RegAllocRegistry.h"
  39 #include "llvm/CodeGen/RegisterCoalescer.h"
  40 #include "llvm/Target/TargetOptions.h"
  41 #include "llvm/Support/Debug.h"
  42 #include "llvm/Support/ErrorHandling.h"
  43 #include "llvm/Support/raw_ostream.h"
  44 #include "llvm/Support/Timer.h"
  45
  46 using namespace llvm;
  47
  48 static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator",
  49                                        createGreedyRegisterAllocator);
  50
  51 namespace {
  52 class RAGreedy : public MachineFunctionPass, public RegAllocBase {
  53   // context
  54   MachineFunction *MF;
  55   BitVector ReservedRegs;
  56
  57   // analyses
  58   SlotIndexes *Indexes;
  59   LiveStacks *LS;
  60   MachineDominatorTree *DomTree;
  61   MachineLoopInfo *Loops;
  62   MachineLoopRanges *LoopRanges;
  63   EdgeBundles *Bundles;
  64   SpillPlacement *SpillPlacer;
  65
  66   // state
  67   std::auto_ptr<Spiller> SpillerInstance;
  68   std::auto_ptr<SplitAnalysis> SA;
  69
  70   // splitting state.
  71
  72   /// All basic blocks where the current register is live.
  73   SmallVector<SpillPlacement::BlockConstraint, 8> SpillConstraints;
  74
  75   /// Additional information about basic blocks where the current variable is
  76   /// live. Such a block will look like one of these templates:
  77   ///
  78   ///  1. |   o---x   | Internal to block. Variable is only live in this block.
  79   ///  2. |---x       | Live-in, kill.
  80   ///  3. |       o---| Def, live-out.
  81   ///  4. |---x   o---| Live-in, kill, def, live-out.
  82   ///  5. |---o---o---| Live-through with uses or defs.
  83   ///  6. |-----------| Live-through without uses. Transparent.
  84   ///
  85   struct BlockInfo {
  86     MachineBasicBlock *MBB;
  87     SlotIndex FirstUse;   ///< First instr using current reg.
  88     SlotIndex LastUse;    ///< Last instr using current reg.
  89     SlotIndex Kill;       ///< Interval end point inside block.
  90     SlotIndex Def;        ///< Interval start point inside block.
  91     /// Last possible point for splitting live ranges.
  92     SlotIndex LastSplitPoint;
  93     bool Uses;            ///< Current reg has uses or defs in block.
  94     bool LiveThrough;     ///< Live in whole block (Templ 5. or 6. above).
  95     bool LiveIn;          ///< Current reg is live in.
  96     bool LiveOut;         ///< Current reg is live out.
  97
  98     // Per-interference pattern scratch data.
  99     bool OverlapEntry;    ///< Interference overlaps entering interval.
 100     bool OverlapExit;     ///< Interference overlaps exiting interval.
 101   };
 102
 103   /// Basic blocks where var is live. This array is parallel to
 104   /// SpillConstraints.
 105   SmallVector<BlockInfo, 8> LiveBlocks;
 106
 107 public:
 108   RAGreedy();
 109
 110   /// Return the pass name.
 111   virtual const char* getPassName() const {
 112     return "Greedy Register Allocator";
 113   }
 114
 115   /// RAGreedy analysis usage.
 116   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 117
 118   virtual void releaseMemory();
 119
 120   virtual Spiller &spiller() { return *SpillerInstance; }
 121
 122   virtual float getPriority(LiveInterval *LI);
 123
 124   virtual unsigned selectOrSplit(LiveInterval&,
 125                                  SmallVectorImpl<LiveInterval*>&);
 126
 127   /// Perform register allocation.
 128   virtual bool runOnMachineFunction(MachineFunction &mf);
 129
 130   static char ID;
 131
 132 private:
 133   bool checkUncachedInterference(LiveInterval&, unsigned);
 134   LiveInterval *getSingleInterference(LiveInterval&, unsigned);
 135   bool reassignVReg(LiveInterval &InterferingVReg, unsigned OldPhysReg);
 136   float calcInterferenceWeight(LiveInterval&, unsigned);
 137   void calcLiveBlockInfo(LiveInterval&);
 138   float calcInterferenceInfo(LiveInterval&, unsigned);
 139   float calcGlobalSplitCost(const BitVector&);
 140   void splitAroundRegion(LiveInterval&, unsigned, const BitVector&,
 141                          SmallVectorImpl<LiveInterval*>&);
 142
 143   unsigned tryReassignOrEvict(LiveInterval&, AllocationOrder&,
 144                               SmallVectorImpl<LiveInterval*>&);
 145   unsigned tryRegionSplit(LiveInterval&, AllocationOrder&,
 146                           SmallVectorImpl<LiveInterval*>&);
 147   unsigned trySplit(LiveInterval&, AllocationOrder&,
 148                     SmallVectorImpl<LiveInterval*>&);
 149   unsigned trySpillInterferences(LiveInterval&, AllocationOrder&,
 150                                  SmallVectorImpl<LiveInterval*>&);
 151 };
 152 } // end anonymous namespace
 153
 154 char RAGreedy::ID = 0;
 155
 156 FunctionPass* llvm::createGreedyRegisterAllocator() {
 157   return new RAGreedy();
 158 }
 159
 160 RAGreedy::RAGreedy(): MachineFunctionPass(ID) {
 161   initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
 162   initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
 163   initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
 164   initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
 165   initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry());
 166   initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
 167   initializeLiveStacksPass(*PassRegistry::getPassRegistry());
 168   initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
 169   initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
 170   initializeMachineLoopRangesPass(*PassRegistry::getPassRegistry());
 171   initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
 172   initializeEdgeBundlesPass(*PassRegistry::getPassRegistry());
 173   initializeSpillPlacementPass(*PassRegistry::getPassRegistry());
 174 }
 175
 176 void RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const {
 177   AU.setPreservesCFG();
 178   AU.addRequired<AliasAnalysis>();
 179   AU.addPreserved<AliasAnalysis>();
 180   AU.addRequired<LiveIntervals>();
 181   AU.addRequired<SlotIndexes>();
 182   AU.addPreserved<SlotIndexes>();
 183   if (StrongPHIElim)
 184     AU.addRequiredID(StrongPHIEliminationID);
 185   AU.addRequiredTransitive<RegisterCoalescer>();
 186   AU.addRequired<CalculateSpillWeights>();
 187   AU.addRequired<LiveStacks>();
 188   AU.addPreserved<LiveStacks>();
 189   AU.addRequired<MachineDominatorTree>();
 190   AU.addPreserved<MachineDominatorTree>();
 191   AU.addRequired<MachineLoopInfo>();
 192   AU.addPreserved<MachineLoopInfo>();
 193   AU.addRequired<MachineLoopRanges>();
 194   AU.addPreserved<MachineLoopRanges>();
 195   AU.addRequired<VirtRegMap>();
 196   AU.addPreserved<VirtRegMap>();
 197   AU.addRequired<EdgeBundles>();
 198   AU.addRequired<SpillPlacement>();
 199   MachineFunctionPass::getAnalysisUsage(AU);
 200 }
 201
 202 void RAGreedy::releaseMemory() {
 203   SpillerInstance.reset(0);
 204   RegAllocBase::releaseMemory();
 205 }
 206
 207 float RAGreedy::getPriority(LiveInterval *LI) {
 208   float Priority = LI->weight;
 209
 210   // Prioritize hinted registers so they are allocated first.
 211   std::pair<unsigned, unsigned> Hint;
 212   if (Hint.first || Hint.second) {
 213     // The hint can be target specific, a virtual register, or a physreg.
 214     Priority *= 2;
 215
 216     // Prefer physreg hints above anything else.
 217     if (Hint.first == 0 && TargetRegisterInfo::isPhysicalRegister(Hint.second))
 218       Priority *= 2;
 219   }
 220   return Priority;
 221 }
 222
 223
 224 //===----------------------------------------------------------------------===//
 225 //                         Register Reassignment
 226 //===----------------------------------------------------------------------===//
 227
 228 // Check interference without using the cache.
 229 bool RAGreedy::checkUncachedInterference(LiveInterval &VirtReg,
 230                                          unsigned PhysReg) {
 231   for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) {
 232     LiveIntervalUnion::Query subQ(&VirtReg, &PhysReg2LiveUnion[*AliasI]);
 233     if (subQ.checkInterference())
 234       return true;
 235   }
 236   return false;
 237 }
 238
 239 /// getSingleInterference - Return the single interfering virtual register
 240 /// assigned to PhysReg. Return 0 if more than one virtual register is
 241 /// interfering.
 242 LiveInterval *RAGreedy::getSingleInterference(LiveInterval &VirtReg,
 243                                               unsigned PhysReg) {
 244   // Check physreg and aliases.
 245   LiveInterval *Interference = 0;
 246   for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) {
 247     LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI);
 248     if (Q.checkInterference()) {
 249       if (Interference)
 250         return 0;
 251       Q.collectInterferingVRegs(1);
 252       if (!Q.seenAllInterferences())
 253         return 0;
 254       Interference = Q.interferingVRegs().front();
 255     }
 256   }
 257   return Interference;
 258 }
 259
 260 // Attempt to reassign this virtual register to a different physical register.
 261 //
 262 // FIXME: we are not yet caching these "second-level" interferences discovered
 263 // in the sub-queries. These interferences can change with each call to
 264 // selectOrSplit. However, we could implement a "may-interfere" cache that
 265 // could be conservatively dirtied when we reassign or split.
 266 //
 267 // FIXME: This may result in a lot of alias queries. We could summarize alias
 268 // live intervals in their parent register's live union, but it's messy.
 269 bool RAGreedy::reassignVReg(LiveInterval &InterferingVReg,
 270                             unsigned WantedPhysReg) {
 271   assert(TargetRegisterInfo::isVirtualRegister(InterferingVReg.reg) &&
 272          "Can only reassign virtual registers");
 273   assert(TRI->regsOverlap(WantedPhysReg, VRM->getPhys(InterferingVReg.reg)) &&
 274          "inconsistent phys reg assigment");
 275
 276   AllocationOrder Order(InterferingVReg.reg, *VRM, ReservedRegs);
 277   while (unsigned PhysReg = Order.next()) {
 278     // Don't reassign to a WantedPhysReg alias.
 279     if (TRI->regsOverlap(PhysReg, WantedPhysReg))
 280       continue;
 281
 282     if (checkUncachedInterference(InterferingVReg, PhysReg))
 283       continue;
 284
 285     // Reassign the interfering virtual reg to this physical reg.
 286     unsigned OldAssign = VRM->getPhys(InterferingVReg.reg);
 287     DEBUG(dbgs() << "reassigning: " << InterferingVReg << " from " <<
 288           TRI->getName(OldAssign) << " to " << TRI->getName(PhysReg) << '\n');
 289     unassign(InterferingVReg, OldAssign);
 290     assign(InterferingVReg, PhysReg);
 291     return true;
 292   }
 293   return false;
 294 }
 295
 296 /// tryReassignOrEvict - Try to reassign a single interferences to a different
 297 /// physreg, or evict a single interference with a lower spill weight.
 298 /// @param  VirtReg Currently unassigned virtual register.
 299 /// @param  Order   Physregs to try.
 300 /// @return         Physreg to assign VirtReg, or 0.
 301 unsigned RAGreedy::tryReassignOrEvict(LiveInterval &VirtReg,
 302                                       AllocationOrder &Order,
 303                                       SmallVectorImpl<LiveInterval*> &NewVRegs){
 304   NamedRegionTimer T("Reassign", TimerGroupName, TimePassesIsEnabled);
 305
 306   // Keep track of the lightest single interference seen so far.
 307   float BestWeight = VirtReg.weight;
 308   LiveInterval *BestVirt = 0;
 309   unsigned BestPhys = 0;
 310
 311   Order.rewind();
 312   while (unsigned PhysReg = Order.next()) {
 313     LiveInterval *InterferingVReg = getSingleInterference(VirtReg, PhysReg);
 314     if (!InterferingVReg)
 315       continue;
 316     if (TargetRegisterInfo::isPhysicalRegister(InterferingVReg->reg))
 317       continue;
 318     if (reassignVReg(*InterferingVReg, PhysReg))
 319       return PhysReg;
 320
 321     // Cannot reassign, is this an eviction candidate?
 322     if (InterferingVReg->weight < BestWeight) {
 323       BestVirt = InterferingVReg;
 324       BestPhys = PhysReg;
 325       BestWeight = InterferingVReg->weight;
 326     }
 327   }
 328
 329   // Nothing reassigned, can we evict a lighter single interference?
 330   if (BestVirt) {
 331     DEBUG(dbgs() << "evicting lighter " << *BestVirt << '\n');
 332     unassign(*BestVirt, VRM->getPhys(BestVirt->reg));
 333     NewVRegs.push_back(BestVirt);
 334     return BestPhys;
 335   }
 336
 337   return 0;
 338 }
 339
 340
 341 //===----------------------------------------------------------------------===//
 342 //                              Region Splitting
 343 //===----------------------------------------------------------------------===//
 344
 345 /// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks
 346 /// where VirtReg is live.
 347 /// The SpillConstraints array is minimally initialized with MBB->getNumber().
 348 void RAGreedy::calcLiveBlockInfo(LiveInterval &VirtReg) {
 349   LiveBlocks.clear();
 350   SpillConstraints.clear();
 351
 352   assert(!VirtReg.empty() && "Cannot allocate an empty interval");
 353   LiveInterval::const_iterator LVI = VirtReg.begin();
 354   LiveInterval::const_iterator LVE = VirtReg.end();
 355
 356   SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE;
 357   UseI = SA->UseSlots.begin();
 358   UseE = SA->UseSlots.end();
 359
 360   // Loop over basic blocks where VirtReg is live.
 361   MachineFunction::iterator MFI = Indexes->getMBBFromIndex(LVI->start);
 362   for (;;) {
 363     // Block constraints depend on the interference pattern.
 364     // Just allocate them here, don't compute anything.
 365     SpillPlacement::BlockConstraint BC;
 366     BC.Number = MFI->getNumber();
 367     SpillConstraints.push_back(BC);
 368
 369     BlockInfo BI;
 370     BI.MBB = MFI;
 371     SlotIndex Start, Stop;
 372     tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
 373
 374     // The last split point is the latest possible insertion point that dominates
 375     // all successor blocks. If interference reaches LastSplitPoint, it is not
 376     // possible to insert a split or reload that makes VirtReg live in the
 377     // outgoing bundle.
 378     MachineBasicBlock::iterator LSP = LIS->getLastSplitPoint(VirtReg, BI.MBB);
 379     if (LSP == BI.MBB->end())
 380       BI.LastSplitPoint = Stop;
 381     else
 382       BI.LastSplitPoint = Indexes->getInstructionIndex(LSP);
 383
 384     // LVI is the first live segment overlapping MBB.
 385     BI.LiveIn = LVI->start <= Start;
 386     if (!BI.LiveIn)
 387       BI.Def = LVI->start;
 388
 389     // Find the first and last uses in the block.
 390     BI.Uses = SA->hasUses(MFI);
 391     if (BI.Uses && UseI != UseE) {
 392       BI.FirstUse = *UseI;
 393       assert(BI.FirstUse >= Start);
 394       do ++UseI;
 395       while (UseI != UseE && *UseI < Stop);
 396       BI.LastUse = UseI[-1];
 397       assert(BI.LastUse < Stop);
 398     }
 399
 400     // Look for gaps in the live range.
 401     bool hasGap = false;
 402     BI.LiveOut = true;
 403     while (LVI->end < Stop) {
 404       SlotIndex LastStop = LVI->end;
 405       if (++LVI == LVE || LVI->start >= Stop) {
 406         BI.Kill = LastStop;
 407         BI.LiveOut = false;
 408         break;
 409       }
 410       if (LastStop < LVI->start) {
 411         hasGap = true;
 412         BI.Kill = LastStop;
 413         BI.Def = LVI->start;
 414       }
 415     }
 416
 417     // Don't set LiveThrough when the block has a gap.
 418     BI.LiveThrough = !hasGap && BI.LiveIn && BI.LiveOut;
 419     LiveBlocks.push_back(BI);
 420
 421     // LVI is now at LVE or LVI->end >= Stop.
 422     if (LVI == LVE)
 423       break;
 424
 425     // Live segment ends exactly at Stop. Move to the next segment.
 426     if (LVI->end == Stop && ++LVI == LVE)
 427       break;
 428
 429     // Pick the next basic block.
 430     if (LVI->start < Stop)
 431       ++MFI;
 432     else
 433       MFI = Indexes->getMBBFromIndex(LVI->start);
 434   }
 435 }
 436
 437 /// calcInterferenceInfo - Compute per-block outgoing and ingoing constraints
 438 /// when considering interference from PhysReg. Also compute an optimistic local
 439 /// cost of this interference pattern.
 440 ///
 441 /// The final cost of a split is the local cost + global cost of preferences
 442 /// broken by SpillPlacement.
 443 ///
 444 float RAGreedy::calcInterferenceInfo(LiveInterval &VirtReg, unsigned PhysReg) {
 445   // Reset interference dependent info.
 446   for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
 447     BlockInfo &BI = LiveBlocks[i];
 448     SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
 449     BC.Entry = (BI.Uses && BI.LiveIn) ?
 450       SpillPlacement::PrefReg : SpillPlacement::DontCare;
 451     BC.Exit = (BI.Uses && BI.LiveOut) ?
 452       SpillPlacement::PrefReg : SpillPlacement::DontCare;
 453     BI.OverlapEntry = BI.OverlapExit = false;
 454   }
 455
 456   // Add interference info from each PhysReg alias.
 457   for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
 458     if (!query(VirtReg, *AI).checkInterference())
 459       continue;
 460     LiveIntervalUnion::SegmentIter IntI =
 461       PhysReg2LiveUnion[*AI].find(VirtReg.beginIndex());
 462     if (!IntI.valid())
 463       continue;
 464
 465     // Determine which blocks have interference live in or after the last split
 466     // point.
 467     for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
 468       BlockInfo &BI = LiveBlocks[i];
 469       SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
 470       SlotIndex Start, Stop;
 471       tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
 472
 473       // Skip interference-free blocks.
 474       if (IntI.start() >= Stop)
 475         continue;
 476
 477       // Is the interference live-in?
 478       if (BI.LiveIn) {
 479         IntI.advanceTo(Start);
 480         if (!IntI.valid())
 481           break;
 482         if (IntI.start() <= Start)
 483           BC.Entry = SpillPlacement::MustSpill;
 484       }
 485
 486       // Is the interference overlapping the last split point?
 487       if (BI.LiveOut) {
 488         if (IntI.stop() < BI.LastSplitPoint)
 489           IntI.advanceTo(BI.LastSplitPoint.getPrevSlot());
 490         if (!IntI.valid())
 491           break;
 492         if (IntI.start() < Stop)
 493           BC.Exit = SpillPlacement::MustSpill;
 494       }
 495     }
 496
 497     // Rewind iterator and check other interferences.
 498     IntI.find(VirtReg.beginIndex());
 499     for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
 500       BlockInfo &BI = LiveBlocks[i];
 501       SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
 502       SlotIndex Start, Stop;
 503       tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
 504
 505       // Skip interference-free blocks.
 506       if (IntI.start() >= Stop)
 507         continue;
 508
 509       // Handle transparent blocks with interference separately.
 510       // Transparent blocks never incur any fixed cost.
 511       if (BI.LiveThrough && !BI.Uses) {
 512         IntI.advanceTo(Start);
 513         if (!IntI.valid())
 514           break;
 515         if (IntI.start() >= Stop)
 516           continue;
 517
 518         if (BC.Entry != SpillPlacement::MustSpill)
 519           BC.Entry = SpillPlacement::PrefSpill;
 520         if (BC.Exit != SpillPlacement::MustSpill)
 521           BC.Exit = SpillPlacement::PrefSpill;
 522         continue;
 523       }
 524
 525       // Now we only have blocks with uses left.
 526       // Check if the interference overlaps the uses.
 527       assert(BI.Uses && "Non-transparent block without any uses");
 528
 529       // Check interference on entry.
 530       if (BI.LiveIn && BC.Entry != SpillPlacement::MustSpill) {
 531         IntI.advanceTo(Start);
 532         if (!IntI.valid())
 533           break;
 534         // Not live in, but before the first use.
 535         if (IntI.start() < BI.FirstUse)
 536           BC.Entry = SpillPlacement::PrefSpill;
 537       }
 538
 539       // Does interference overlap the uses in the entry segment
 540       // [FirstUse;Kill)?
 541       if (BI.LiveIn && !BI.OverlapEntry) {
 542         IntI.advanceTo(BI.FirstUse);
 543         if (!IntI.valid())
 544           break;
 545         // A live-through interval has no kill.
 546         // Check [FirstUse;LastUse) instead.
 547         if (IntI.start() < (BI.LiveThrough ? BI.LastUse : BI.Kill))
 548           BI.OverlapEntry = true;
 549       }
 550
 551       // Does interference overlap the uses in the exit segment [Def;LastUse)?
 552       if (BI.LiveOut && !BI.LiveThrough && !BI.OverlapExit) {
 553         IntI.advanceTo(BI.Def);
 554         if (!IntI.valid())
 555           break;
 556         if (IntI.start() < BI.LastUse)
 557           BI.OverlapExit = true;
 558       }
 559
 560       // Check interference on exit.
 561       if (BI.LiveOut && BC.Exit != SpillPlacement::MustSpill) {
 562         // Check interference between LastUse and Stop.
 563         if (BC.Exit != SpillPlacement::PrefSpill) {
 564           IntI.advanceTo(BI.LastUse);
 565           if (!IntI.valid())
 566             break;
 567           if (IntI.start() < Stop)
 568             BC.Exit = SpillPlacement::PrefSpill;
 569         }
 570       }
 571     }
 572   }
 573
 574   // Accumulate a local cost of this interference pattern.
 575   float LocalCost = 0;
 576   for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
 577     BlockInfo &BI = LiveBlocks[i];
 578     if (!BI.Uses)
 579       continue;
 580     SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
 581     unsigned Inserts = 0;
 582
 583     // Do we need spill code for the entry segment?
 584     if (BI.LiveIn)
 585       Inserts += BI.OverlapEntry || BC.Entry != SpillPlacement::PrefReg;
 586
 587     // For the exit segment?
 588     if (BI.LiveOut)
 589       Inserts += BI.OverlapExit || BC.Exit != SpillPlacement::PrefReg;
 590
 591     // The local cost of spill code in this block is the block frequency times
 592     // the number of spill instructions inserted.
 593     if (Inserts)
 594       LocalCost += Inserts * SpillPlacer->getBlockFrequency(BI.MBB);
 595   }
 596   DEBUG(dbgs() << "Local cost of " << PrintReg(PhysReg, TRI) << " = "
 597                << LocalCost << '\n');
 598   return LocalCost;
 599 }
 600
 601 /// calcGlobalSplitCost - Return the global split cost of following the split
 602 /// pattern in LiveBundles. This cost should be added to the local cost of the
 603 /// interference pattern in SpillConstraints.
 604 ///
 605 float RAGreedy::calcGlobalSplitCost(const BitVector &LiveBundles) {
 606   float GlobalCost = 0;
 607   for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
 608     SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
 609     unsigned Inserts = 0;
 610     // Broken entry preference?
 611     Inserts += LiveBundles[Bundles->getBundle(BC.Number, 0)] !=
 612                  (BC.Entry == SpillPlacement::PrefReg);
 613     // Broken exit preference?
 614     Inserts += LiveBundles[Bundles->getBundle(BC.Number, 1)] !=
 615                  (BC.Exit == SpillPlacement::PrefReg);
 616     if (Inserts)
 617       GlobalCost += Inserts * SpillPlacer->getBlockFrequency(LiveBlocks[i].MBB);
 618   }
 619   DEBUG(dbgs() << "Global cost = " << GlobalCost << '\n');
 620   return GlobalCost;
 621 }
 622
 623 /// splitAroundRegion - Split VirtReg around the region determined by
 624 /// LiveBundles. Make an effort to avoid interference from PhysReg.
 625 ///
 626 /// The 'register' interval is going to contain as many uses as possible while
 627 /// avoiding interference. The 'stack' interval is the complement constructed by
 628 /// SplitEditor. It will contain the rest.
 629 ///
 630 void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
 631                                  const BitVector &LiveBundles,
 632                                  SmallVectorImpl<LiveInterval*> &NewVRegs) {
 633   DEBUG({
 634     dbgs() << "Splitting around region for " << PrintReg(PhysReg, TRI)
 635            << " with bundles";
 636     for (int i = LiveBundles.find_first(); i>=0; i = LiveBundles.find_next(i))
 637       dbgs() << " EB#" << i;
 638     dbgs() << ".\n";
 639   });
 640
 641   // First compute interference ranges in the live blocks.
 642   typedef std::pair<SlotIndex, SlotIndex> IndexPair;
 643   SmallVector<IndexPair, 8> InterferenceRanges;
 644   InterferenceRanges.resize(LiveBlocks.size());
 645   for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
 646     if (!query(VirtReg, *AI).checkInterference())
 647       continue;
 648     LiveIntervalUnion::SegmentIter IntI =
 649       PhysReg2LiveUnion[*AI].find(VirtReg.beginIndex());
 650     if (!IntI.valid())
 651       continue;
 652     for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
 653       const BlockInfo &BI = LiveBlocks[i];
 654       IndexPair &IP = InterferenceRanges[i];
 655       SlotIndex Start, Stop;
 656       tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
 657       // Skip interference-free blocks.
 658       if (IntI.start() >= Stop)
 659         continue;
 660
 661       // First interference in block.
 662       if (BI.LiveIn) {
 663         IntI.advanceTo(Start);
 664         if (!IntI.valid())
 665           break;
 666         if (IntI.start() >= Stop)
 667           continue;
 668         if (!IP.first.isValid() || IntI.start() < IP.first)
 669           IP.first = IntI.start();
 670       }
 671
 672       // Last interference in block.
 673       if (BI.LiveOut) {
 674         IntI.advanceTo(Stop);
 675         if (!IntI.valid() || IntI.start() >= Stop)
 676           --IntI;
 677         if (IntI.stop() <= Start)
 678           continue;
 679         if (!IP.second.isValid() || IntI.stop() > IP.second)
 680           IP.second = IntI.stop();
 681       }
 682     }
 683   }
 684
 685   SmallVector<LiveInterval*, 4> SpillRegs;
 686   LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs);
 687   SplitEditor SE(*SA, *LIS, *VRM, *DomTree, LREdit);
 688
 689   // Create the main cross-block interval.
 690   SE.openIntv();
 691
 692   // First add all defs that are live out of a block.
 693   for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
 694     BlockInfo &BI = LiveBlocks[i];
 695     bool RegIn  = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)];
 696     bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)];
 697
 698     // Should the register be live out?
 699     if (!BI.LiveOut || !RegOut)
 700       continue;
 701
 702     IndexPair &IP = InterferenceRanges[i];
 703     SlotIndex Start, Stop;
 704     tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
 705
 706     DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " -> EB#"
 707                  << Bundles->getBundle(BI.MBB->getNumber(), 1)
 708                  << " intf [" << IP.first << ';' << IP.second << ')');
 709
 710     // The interference interval should either be invalid or overlap MBB.
 711     assert((!IP.first.isValid() || IP.first < Stop) && "Bad interference");
 712     assert((!IP.second.isValid() || IP.second > Start) && "Bad interference");
 713
 714     // Check interference leaving the block.
 715     if (!IP.second.isValid()) {
 716       // Block is interference-free.
 717       DEBUG(dbgs() << ", no interference");
 718       if (!BI.Uses) {
 719         assert(BI.LiveThrough && "No uses, but not live through block?");
 720         // Block is live-through without interference.
 721         DEBUG(dbgs() << ", no uses"
 722                      << (RegIn ? ", live-through.\n" : ", stack in.\n"));
 723         if (!RegIn)
 724           SE.enterIntvAtEnd(*BI.MBB);
 725         continue;
 726       }
 727       if (!BI.LiveThrough) {
 728         DEBUG(dbgs() << ", not live-through.\n");
 729         SE.useIntv(SE.enterIntvBefore(BI.Def), Stop);
 730         continue;
 731       }
 732       if (!RegIn) {
 733         // Block is live-through, but entry bundle is on the stack.
 734         // Reload just before the first use.
 735         DEBUG(dbgs() << ", not live-in, enter before first use.\n");
 736         SE.useIntv(SE.enterIntvBefore(BI.FirstUse), Stop);
 737         continue;
 738       }
 739       DEBUG(dbgs() << ", live-through.\n");
 740       continue;
 741     }
 742
 743     // Block has interference.
 744     DEBUG(dbgs() << ", interference to " << IP.second);
 745
 746     if (!BI.LiveThrough && IP.second <= BI.Def) {
 747       // The interference doesn't reach the outgoing segment.
 748       DEBUG(dbgs() << " doesn't affect def from " << BI.Def << '\n');
 749       SE.useIntv(BI.Def, Stop);
 750       continue;
 751     }
 752
 753
 754     if (!BI.Uses) {
 755       // No uses in block, avoid interference by reloading as late as possible.
 756       DEBUG(dbgs() << ", no uses.\n");
 757       SlotIndex SegStart = SE.enterIntvAtEnd(*BI.MBB);
 758       assert(SegStart >= IP.second && "Couldn't avoid interference");
 759       continue;
 760     }
 761
 762     if (IP.second.getBoundaryIndex() < BI.LastUse) {
 763       // There are interference-free uses at the end of the block.
 764       // Find the first use that can get the live-out register.
 765       SmallVectorImpl<SlotIndex>::const_iterator UI =
 766         std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(),
 767                          IP.second.getBoundaryIndex());
 768       assert(UI != SA->UseSlots.end() && "Couldn't find last use");
 769       SlotIndex Use = *UI;
 770       assert(Use <= BI.LastUse && "Couldn't find last use");
 771       // Only attempt a split befroe the last split point.
 772       if (Use.getBaseIndex() <= BI.LastSplitPoint) {
 773         DEBUG(dbgs() << ", free use at " << Use << ".\n");
 774         SlotIndex SegStart = SE.enterIntvBefore(Use);
 775         assert(SegStart >= IP.second && "Couldn't avoid interference");
 776         assert(SegStart < BI.LastSplitPoint && "Impossible split point");
 777         SE.useIntv(SegStart, Stop);
 778         continue;
 779       }
 780     }
 781
 782     // Interference is after the last use.
 783     DEBUG(dbgs() << " after last use.\n");
 784     SlotIndex SegStart = SE.enterIntvAtEnd(*BI.MBB);
 785     assert(SegStart >= IP.second && "Couldn't avoid interference");
 786   }
 787
 788   // Now all defs leading to live bundles are handled, do everything else.
 789   for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
 790     BlockInfo &BI = LiveBlocks[i];
 791     bool RegIn  = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)];
 792     bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)];
 793
 794     // Is the register live-in?
 795     if (!BI.LiveIn || !RegIn)
 796       continue;
 797
 798     // We have an incoming register. Check for interference.
 799     IndexPair &IP = InterferenceRanges[i];
 800     SlotIndex Start, Stop;
 801     tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
 802
 803     DEBUG(dbgs() << "EB#" << Bundles->getBundle(BI.MBB->getNumber(), 0)
 804                  << " -> BB#" << BI.MBB->getNumber());
 805
 806     // Check interference entering the block.
 807     if (!IP.first.isValid()) {
 808       // Block is interference-free.
 809       DEBUG(dbgs() << ", no interference");
 810       if (!BI.Uses) {
 811         assert(BI.LiveThrough && "No uses, but not live through block?");
 812         // Block is live-through without interference.
 813         if (RegOut) {
 814           DEBUG(dbgs() << ", no uses, live-through.\n");
 815           SE.useIntv(Start, Stop);
 816         } else {
 817           DEBUG(dbgs() << ", no uses, stack-out.\n");
 818           SE.leaveIntvAtTop(*BI.MBB);
 819         }
 820         continue;
 821       }
 822       if (!BI.LiveThrough) {
 823         DEBUG(dbgs() << ", killed in block.\n");
 824         SE.useIntv(Start, SE.leaveIntvAfter(BI.Kill));
 825         continue;
 826       }
 827       if (!RegOut) {
 828         // Block is live-through, but exit bundle is on the stack.
 829         // Spill immediately after the last use.
 830         if (BI.LastUse < BI.LastSplitPoint) {
 831           DEBUG(dbgs() << ", uses, stack-out.\n");
 832           SE.useIntv(Start, SE.leaveIntvAfter(BI.LastUse));
 833           continue;
 834         }
 835         // The last use is after the last split point, it is probably an
 836         // indirect jump.
 837         DEBUG(dbgs() << ", uses at " << BI.LastUse << " after split point "
 838                      << BI.LastSplitPoint << ", stack-out.\n");
 839         SlotIndex SegEnd;
 840         // Find the last real instruction before the split point.
 841         MachineBasicBlock::iterator SplitI =
 842           LIS->getInstructionFromIndex(BI.LastSplitPoint);
 843         MachineBasicBlock::iterator I = SplitI, B = BI.MBB->begin();
 844         while (I != B && (--I)->isDebugValue())
 845           ;
 846         if (I == SplitI)
 847           SegEnd = SE.leaveIntvAtTop(*BI.MBB);
 848         else {
 849           SegEnd = SE.leaveIntvAfter(LIS->getInstructionIndex(I));
 850           SE.useIntv(Start, SegEnd);
 851         }
 852         // Run a double interval from the split to the last use.
 853         // This makes it possible to spill the complement without affecting the
 854         // indirect branch.
 855         SE.overlapIntv(SegEnd, BI.LastUse);
 856         continue;
 857       }
 858       // Register is live-through.
 859       DEBUG(dbgs() << ", uses, live-through.\n");
 860       SE.useIntv(Start, Stop);
 861       continue;
 862     }
 863
 864     // Block has interference.
 865     DEBUG(dbgs() << ", interference from " << IP.first);
 866
 867     if (!BI.LiveThrough && IP.first >= BI.Kill) {
 868       // The interference doesn't reach the outgoing segment.
 869       DEBUG(dbgs() << " doesn't affect kill at " << BI.Kill << '\n');
 870       SE.useIntv(Start, BI.Kill);
 871       continue;
 872     }
 873
 874     if (!BI.Uses) {
 875       // No uses in block, avoid interference by spilling as soon as possible.
 876       DEBUG(dbgs() << ", no uses.\n");
 877       SlotIndex SegEnd = SE.leaveIntvAtTop(*BI.MBB);
 878       assert(SegEnd <= IP.first && "Couldn't avoid interference");
 879       continue;
 880     }
 881     if (IP.first.getBaseIndex() > BI.FirstUse) {
 882       // There are interference-free uses at the beginning of the block.
 883       // Find the last use that can get the register.
 884       SmallVectorImpl<SlotIndex>::const_iterator UI =
 885         std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(),
 886                          IP.first.getBaseIndex());
 887       assert(UI != SA->UseSlots.begin() && "Couldn't find first use");
 888       SlotIndex Use = (--UI)->getBoundaryIndex();
 889       DEBUG(dbgs() << ", free use at " << *UI << ".\n");
 890       SlotIndex SegEnd = SE.leaveIntvAfter(Use);
 891       assert(SegEnd <= IP.first && "Couldn't avoid interference");
 892       SE.useIntv(Start, SegEnd);
 893       continue;
 894     }
 895
 896     // Interference is before the first use.
 897     DEBUG(dbgs() << " before first use.\n");
 898     SlotIndex SegEnd = SE.leaveIntvAtTop(*BI.MBB);
 899     assert(SegEnd <= IP.first && "Couldn't avoid interference");
 900   }
 901
 902   SE.closeIntv();
 903
 904   // FIXME: Should we be more aggressive about splitting the stack region into
 905   // per-block segments? The current approach allows the stack region to
 906   // separate into connected components. Some components may be allocatable.
 907   SE.finish();
 908
 909   if (VerifyEnabled) {
 910     MF->verify(this, "After splitting live range around region");
 911
 912 #ifndef NDEBUG
 913     // Make sure that at least one of the new intervals can allocate to PhysReg.
 914     // That was the whole point of splitting the live range.
 915     bool found = false;
 916     for (LiveRangeEdit::iterator I = LREdit.begin(), E = LREdit.end(); I != E;
 917          ++I)
 918       if (!checkUncachedInterference(**I, PhysReg)) {
 919         found = true;
 920         break;
 921       }
 922     assert(found && "No allocatable intervals after pointless splitting");
 923 #endif
 924   }
 925 }
 926
 927 unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
 928                                   SmallVectorImpl<LiveInterval*> &NewVRegs) {
 929   calcLiveBlockInfo(VirtReg);
 930   BitVector LiveBundles, BestBundles;
 931   float BestCost = 0;
 932   unsigned BestReg = 0;
 933   Order.rewind();
 934   while (unsigned PhysReg = Order.next()) {
 935     float Cost = calcInterferenceInfo(VirtReg, PhysReg);
 936     if (BestReg && Cost >= BestCost)
 937       continue;
 938
 939     SpillPlacer->placeSpills(SpillConstraints, LiveBundles);
 940     // No live bundles, defer to splitSingleBlocks().
 941     if (!LiveBundles.any())
 942       continue;
 943
 944     Cost += calcGlobalSplitCost(LiveBundles);
 945     if (!BestReg || Cost < BestCost) {
 946       BestReg = PhysReg;
 947       BestCost = Cost;
 948       BestBundles.swap(LiveBundles);
 949     }
 950   }
 951
 952   if (!BestReg)
 953     return 0;
 954
 955   splitAroundRegion(VirtReg, BestReg, BestBundles, NewVRegs);
 956   return 0;
 957 }
 958
 959
 960 //===----------------------------------------------------------------------===//
 961 //                          Live Range Splitting
 962 //===----------------------------------------------------------------------===//
 963
 964 /// trySplit - Try to split VirtReg or one of its interferences, making it
 965 /// assignable.
 966 /// @return Physreg when VirtReg may be assigned and/or new NewVRegs.
 967 unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order,
 968                             SmallVectorImpl<LiveInterval*>&NewVRegs) {
 969   NamedRegionTimer T("Splitter", TimerGroupName, TimePassesIsEnabled);
 970   SA->analyze(&VirtReg);
 971
 972   // Don't attempt splitting on local intervals for now. TBD.
 973   if (LIS->intervalIsInOneMBB(VirtReg))
 974     return 0;
 975
 976   // First try to split around a region spanning multiple blocks.
 977   unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs);
 978   if (PhysReg || !NewVRegs.empty())
 979     return PhysReg;
 980
 981   // Then isolate blocks with multiple uses.
 982   SplitAnalysis::BlockPtrSet Blocks;
 983   if (SA->getMultiUseBlocks(Blocks)) {
 984     SmallVector<LiveInterval*, 4> SpillRegs;
 985     LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs);
 986     SplitEditor(*SA, *LIS, *VRM, *DomTree, LREdit).splitSingleBlocks(Blocks);
 987     if (VerifyEnabled)
 988       MF->verify(this, "After splitting live range around basic blocks");
 989   }
 990
 991   // Don't assign any physregs.
 992   return 0;
 993 }
 994
 995
 996 //===----------------------------------------------------------------------===//
 997 //                                Spilling
 998 //===----------------------------------------------------------------------===//
 999
1000 /// calcInterferenceWeight - Calculate the combined spill weight of
1001 /// interferences when assigning VirtReg to PhysReg.
1002 float RAGreedy::calcInterferenceWeight(LiveInterval &VirtReg, unsigned PhysReg){
1003   float Sum = 0;
1004   for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
1005     LiveIntervalUnion::Query &Q = query(VirtReg, *AI);
1006     Q.collectInterferingVRegs();
1007     if (Q.seenUnspillableVReg())
1008       return HUGE_VALF;
1009     for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i)
1010       Sum += Q.interferingVRegs()[i]->weight;
1011   }
1012   return Sum;
1013 }
1014
1015 /// trySpillInterferences - Try to spill interfering registers instead of the
1016 /// current one. Only do it if the accumulated spill weight is smaller than the
1017 /// current spill weight.
1018 unsigned RAGreedy::trySpillInterferences(LiveInterval &VirtReg,
1019                                          AllocationOrder &Order,
1020                                      SmallVectorImpl<LiveInterval*> &NewVRegs) {
1021   NamedRegionTimer T("Spill Interference", TimerGroupName, TimePassesIsEnabled);
1022   unsigned BestPhys = 0;
1023   float BestWeight = 0;
1024
1025   Order.rewind();
1026   while (unsigned PhysReg = Order.next()) {
1027     float Weight = calcInterferenceWeight(VirtReg, PhysReg);
1028     if (Weight == HUGE_VALF || Weight >= VirtReg.weight)
1029       continue;
1030     if (!BestPhys || Weight < BestWeight)
1031       BestPhys = PhysReg, BestWeight = Weight;
1032   }
1033
1034   // No candidates found.
1035   if (!BestPhys)
1036     return 0;
1037
1038   // Collect all interfering registers.
1039   SmallVector<LiveInterval*, 8> Spills;
1040   for (const unsigned *AI = TRI->getOverlaps(BestPhys); *AI; ++AI) {
1041     LiveIntervalUnion::Query &Q = query(VirtReg, *AI);
1042     Spills.append(Q.interferingVRegs().begin(), Q.interferingVRegs().end());
1043     for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) {
1044       LiveInterval *VReg = Q.interferingVRegs()[i];
1045       unassign(*VReg, *AI);
1046     }
1047   }
1048
1049   // Spill them all.
1050   DEBUG(dbgs() << "spilling " << Spills.size() << " interferences with weight "
1051                << BestWeight << '\n');
1052   for (unsigned i = 0, e = Spills.size(); i != e; ++i)
1053     spiller().spill(Spills[i], NewVRegs, Spills);
1054   return BestPhys;
1055 }
1056
1057
1058 //===----------------------------------------------------------------------===//
1059 //                            Main Entry Point
1060 //===----------------------------------------------------------------------===//
1061
1062 unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg,
1063                                  SmallVectorImpl<LiveInterval*> &NewVRegs) {
1064   // First try assigning a free register.
1065   AllocationOrder Order(VirtReg.reg, *VRM, ReservedRegs);
1066   while (unsigned PhysReg = Order.next()) {
1067     if (!checkPhysRegInterference(VirtReg, PhysReg))
1068       return PhysReg;
1069   }
1070
1071   // Try to reassign interferences.
1072   if (unsigned PhysReg = tryReassignOrEvict(VirtReg, Order, NewVRegs))
1073     return PhysReg;
1074
1075   assert(NewVRegs.empty() && "Cannot append to existing NewVRegs");
1076
1077   // Try splitting VirtReg or interferences.
1078   unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs);
1079   if (PhysReg || !NewVRegs.empty())
1080     return PhysReg;
1081
1082   // Try to spill another interfering reg with less spill weight.
1083   PhysReg = trySpillInterferences(VirtReg, Order, NewVRegs);
1084   if (PhysReg)
1085     return PhysReg;
1086
1087   // Finally spill VirtReg itself.
1088   NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled);
1089   SmallVector<LiveInterval*, 1> pendingSpills;
1090   spiller().spill(&VirtReg, NewVRegs, pendingSpills);
1091
1092   // The live virtual register requesting allocation was spilled, so tell
1093   // the caller not to allocate anything during this round.
1094   return 0;
1095 }
1096
1097 bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
1098   DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n"
1099                << "********** Function: "
1100                << ((Value*)mf.getFunction())->getName() << '\n');
1101
1102   MF = &mf;
1103   if (VerifyEnabled)
1104     MF->verify(this, "Before greedy register allocator");
1105
1106   RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>());
1107   Indexes = &getAnalysis<SlotIndexes>();
1108   DomTree = &getAnalysis<MachineDominatorTree>();
1109   ReservedRegs = TRI->getReservedRegs(*MF);
1110   SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
1111   Loops = &getAnalysis<MachineLoopInfo>();
1112   LoopRanges = &getAnalysis<MachineLoopRanges>();
1113   Bundles = &getAnalysis<EdgeBundles>();
1114   SpillPlacer = &getAnalysis<SpillPlacement>();
1115
1116   SA.reset(new SplitAnalysis(*MF, *LIS, *Loops));
1117
1118   allocatePhysRegs();
1119   addMBBLiveIns(MF);
1120   LIS->addKillFlags();
1121
1122   // Run rewriter
1123   {
1124     NamedRegionTimer T("Rewriter", TimerGroupName, TimePassesIsEnabled);
1125     std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
1126     rewriter->runOnMachineFunction(*MF, *VRM, LIS);
1127   }
1128
1129   // The pass output is in VirtRegMap. Release all the transient data.
1130   releaseMemory();
1131
1132   return true;
1133 }