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 "llvm/ADT/Statistic.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 #include <queue>
  47
  48 using namespace llvm;
  49
  50 STATISTIC(NumGlobalSplits, "Number of split global live ranges");
  51 STATISTIC(NumLocalSplits,  "Number of split local live ranges");
  52 STATISTIC(NumEvicted,      "Number of interferences evicted");
  53
  54 static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator",
  55                                        createGreedyRegisterAllocator);
  56
  57 namespace {
  58 class RAGreedy : public MachineFunctionPass,
  59                  public RegAllocBase,
  60                  private LiveRangeEdit::Delegate {
  61
  62   // context
  63   MachineFunction *MF;
  64   BitVector ReservedRegs;
  65
  66   // analyses
  67   SlotIndexes *Indexes;
  68   LiveStacks *LS;
  69   MachineDominatorTree *DomTree;
  70   MachineLoopInfo *Loops;
  71   MachineLoopRanges *LoopRanges;
  72   EdgeBundles *Bundles;
  73   SpillPlacement *SpillPlacer;
  74
  75   // state
  76   std::auto_ptr<Spiller> SpillerInstance;
  77   std::priority_queue<std::pair<unsigned, unsigned> > Queue;
  78
  79   // Live ranges pass through a number of stages as we try to allocate them.
  80   // Some of the stages may also create new live ranges:
  81   //
  82   // - Region splitting.
  83   // - Per-block splitting.
  84   // - Local splitting.
  85   // - Spilling.
  86   //
  87   // Ranges produced by one of the stages skip the previous stages when they are
  88   // dequeued. This improves performance because we can skip interference checks
  89   // that are unlikely to give any results. It also guarantees that the live
  90   // range splitting algorithm terminates, something that is otherwise hard to
  91   // ensure.
  92   enum LiveRangeStage {
  93     RS_Original, ///< Never seen before, never split.
  94     RS_Second,   ///< Second time in the queue.
  95     RS_Region,   ///< Produced by region splitting.
  96     RS_Block,    ///< Produced by per-block splitting.
  97     RS_Local,    ///< Produced by local splitting.
  98     RS_Spill     ///< Produced by spilling.
  99   };
 100
 101   IndexedMap<unsigned char, VirtReg2IndexFunctor> LRStage;
 102
 103   LiveRangeStage getStage(const LiveInterval &VirtReg) const {
 104     return LiveRangeStage(LRStage[VirtReg.reg]);
 105   }
 106
 107   template<typename Iterator>
 108   void setStage(Iterator Begin, Iterator End, LiveRangeStage NewStage) {
 109     LRStage.resize(MRI->getNumVirtRegs());
 110     for (;Begin != End; ++Begin)
 111       LRStage[(*Begin)->reg] = NewStage;
 112   }
 113
 114   // splitting state.
 115   std::auto_ptr<SplitAnalysis> SA;
 116   std::auto_ptr<SplitEditor> SE;
 117
 118   /// All basic blocks where the current register is live.
 119   SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints;
 120
 121   typedef std::pair<SlotIndex, SlotIndex> IndexPair;
 122
 123   /// Global live range splitting candidate info.
 124   struct GlobalSplitCandidate {
 125     unsigned PhysReg;
 126     SmallVector<IndexPair, 8> Interference;
 127     BitVector LiveBundles;
 128   };
 129
 130   /// Candidate info for for each PhysReg in AllocationOrder.
 131   /// This vector never shrinks, but grows to the size of the largest register
 132   /// class.
 133   SmallVector<GlobalSplitCandidate, 32> GlobalCand;
 134
 135   /// For every instruction in SA->UseSlots, store the previous non-copy
 136   /// instruction.
 137   SmallVector<SlotIndex, 8> PrevSlot;
 138
 139 public:
 140   RAGreedy();
 141
 142   /// Return the pass name.
 143   virtual const char* getPassName() const {
 144     return "Greedy Register Allocator";
 145   }
 146
 147   /// RAGreedy analysis usage.
 148   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 149   virtual void releaseMemory();
 150   virtual Spiller &spiller() { return *SpillerInstance; }
 151   virtual void enqueue(LiveInterval *LI);
 152   virtual LiveInterval *dequeue();
 153   virtual unsigned selectOrSplit(LiveInterval&,
 154                                  SmallVectorImpl<LiveInterval*>&);
 155
 156   /// Perform register allocation.
 157   virtual bool runOnMachineFunction(MachineFunction &mf);
 158
 159   static char ID;
 160
 161 private:
 162   void LRE_WillEraseInstruction(MachineInstr*);
 163   bool LRE_CanEraseVirtReg(unsigned);
 164   void LRE_WillShrinkVirtReg(unsigned);
 165
 166   void mapGlobalInterference(unsigned, SmallVectorImpl<IndexPair>&);
 167   float calcSplitConstraints(const SmallVectorImpl<IndexPair>&);
 168
 169   float calcGlobalSplitCost(const BitVector&);
 170   void splitAroundRegion(LiveInterval&, unsigned, const BitVector&,
 171                          SmallVectorImpl<LiveInterval*>&);
 172   void calcGapWeights(unsigned, SmallVectorImpl<float>&);
 173   SlotIndex getPrevMappedIndex(const MachineInstr*);
 174   void calcPrevSlots();
 175   unsigned nextSplitPoint(unsigned);
 176   bool canEvictInterference(LiveInterval&, unsigned, float&);
 177
 178   unsigned tryEvict(LiveInterval&, AllocationOrder&,
 179                     SmallVectorImpl<LiveInterval*>&);
 180   unsigned tryRegionSplit(LiveInterval&, AllocationOrder&,
 181                           SmallVectorImpl<LiveInterval*>&);
 182   unsigned tryLocalSplit(LiveInterval&, AllocationOrder&,
 183     SmallVectorImpl<LiveInterval*>&);
 184   unsigned trySplit(LiveInterval&, AllocationOrder&,
 185                     SmallVectorImpl<LiveInterval*>&);
 186 };
 187 } // end anonymous namespace
 188
 189 char RAGreedy::ID = 0;
 190
 191 FunctionPass* llvm::createGreedyRegisterAllocator() {
 192   return new RAGreedy();
 193 }
 194
 195 RAGreedy::RAGreedy(): MachineFunctionPass(ID), LRStage(RS_Original) {
 196   initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
 197   initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
 198   initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
 199   initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
 200   initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry());
 201   initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
 202   initializeLiveStacksPass(*PassRegistry::getPassRegistry());
 203   initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
 204   initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
 205   initializeMachineLoopRangesPass(*PassRegistry::getPassRegistry());
 206   initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
 207   initializeEdgeBundlesPass(*PassRegistry::getPassRegistry());
 208   initializeSpillPlacementPass(*PassRegistry::getPassRegistry());
 209 }
 210
 211 void RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const {
 212   AU.setPreservesCFG();
 213   AU.addRequired<AliasAnalysis>();
 214   AU.addPreserved<AliasAnalysis>();
 215   AU.addRequired<LiveIntervals>();
 216   AU.addRequired<SlotIndexes>();
 217   AU.addPreserved<SlotIndexes>();
 218   if (StrongPHIElim)
 219     AU.addRequiredID(StrongPHIEliminationID);
 220   AU.addRequiredTransitive<RegisterCoalescer>();
 221   AU.addRequired<CalculateSpillWeights>();
 222   AU.addRequired<LiveStacks>();
 223   AU.addPreserved<LiveStacks>();
 224   AU.addRequired<MachineDominatorTree>();
 225   AU.addPreserved<MachineDominatorTree>();
 226   AU.addRequired<MachineLoopInfo>();
 227   AU.addPreserved<MachineLoopInfo>();
 228   AU.addRequired<MachineLoopRanges>();
 229   AU.addPreserved<MachineLoopRanges>();
 230   AU.addRequired<VirtRegMap>();
 231   AU.addPreserved<VirtRegMap>();
 232   AU.addRequired<EdgeBundles>();
 233   AU.addRequired<SpillPlacement>();
 234   MachineFunctionPass::getAnalysisUsage(AU);
 235 }
 236
 237
 238 //===----------------------------------------------------------------------===//
 239 //                     LiveRangeEdit delegate methods
 240 //===----------------------------------------------------------------------===//
 241
 242 void RAGreedy::LRE_WillEraseInstruction(MachineInstr *MI) {
 243   // LRE itself will remove from SlotIndexes and parent basic block.
 244   VRM->RemoveMachineInstrFromMaps(MI);
 245 }
 246
 247 bool RAGreedy::LRE_CanEraseVirtReg(unsigned VirtReg) {
 248   if (unsigned PhysReg = VRM->getPhys(VirtReg)) {
 249     unassign(LIS->getInterval(VirtReg), PhysReg);
 250     return true;
 251   }
 252   // Unassigned virtreg is probably in the priority queue.
 253   // RegAllocBase will erase it after dequeueing.
 254   return false;
 255 }
 256
 257 void RAGreedy::LRE_WillShrinkVirtReg(unsigned VirtReg) {
 258   unsigned PhysReg = VRM->getPhys(VirtReg);
 259   if (!PhysReg)
 260     return;
 261
 262   // Register is assigned, put it back on the queue for reassignment.
 263   LiveInterval &LI = LIS->getInterval(VirtReg);
 264   unassign(LI, PhysReg);
 265   enqueue(&LI);
 266 }
 267
 268 void RAGreedy::releaseMemory() {
 269   SpillerInstance.reset(0);
 270   LRStage.clear();
 271   RegAllocBase::releaseMemory();
 272 }
 273
 274 void RAGreedy::enqueue(LiveInterval *LI) {
 275   // Prioritize live ranges by size, assigning larger ranges first.
 276   // The queue holds (size, reg) pairs.
 277   const unsigned Size = LI->getSize();
 278   const unsigned Reg = LI->reg;
 279   assert(TargetRegisterInfo::isVirtualRegister(Reg) &&
 280          "Can only enqueue virtual registers");
 281   unsigned Prio;
 282
 283   LRStage.grow(Reg);
 284   if (LRStage[Reg] == RS_Second)
 285     // Unsplit ranges that couldn't be allocated immediately are deferred until
 286     // everything else has been allocated. Long ranges are allocated last so
 287     // they are split against realistic interference.
 288     Prio = (1u << 31) - Size;
 289   else {
 290     // Everything else is allocated in long->short order. Long ranges that don't
 291     // fit should be spilled ASAP so they don't create interference.
 292     Prio = (1u << 31) + Size;
 293
 294     // Boost ranges that have a physical register hint.
 295     if (TargetRegisterInfo::isPhysicalRegister(VRM->getRegAllocPref(Reg)))
 296       Prio |= (1u << 30);
 297   }
 298
 299   Queue.push(std::make_pair(Prio, Reg));
 300 }
 301
 302 LiveInterval *RAGreedy::dequeue() {
 303   if (Queue.empty())
 304     return 0;
 305   LiveInterval *LI = &LIS->getInterval(Queue.top().second);
 306   Queue.pop();
 307   return LI;
 308 }
 309
 310 //===----------------------------------------------------------------------===//
 311 //                         Interference eviction
 312 //===----------------------------------------------------------------------===//
 313
 314 /// canEvict - Return true if all interferences between VirtReg and PhysReg can
 315 /// be evicted. Set maxWeight to the maximal spill weight of an interference.
 316 bool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg,
 317                                     float &MaxWeight) {
 318   float Weight = 0;
 319   for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) {
 320     LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI);
 321     // If there is 10 or more interferences, chances are one is smaller.
 322     if (Q.collectInterferingVRegs(10) >= 10)
 323       return false;
 324
 325     // Check if any interfering live range is heavier than VirtReg.
 326     for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) {
 327       LiveInterval *Intf = Q.interferingVRegs()[i];
 328       if (TargetRegisterInfo::isPhysicalRegister(Intf->reg))
 329         return false;
 330       if (Intf->weight >= VirtReg.weight)
 331         return false;
 332       Weight = std::max(Weight, Intf->weight);
 333     }
 334   }
 335   MaxWeight = Weight;
 336   return true;
 337 }
 338
 339 /// tryEvict - Try to evict all interferences for a physreg.
 340 /// @param  VirtReg Currently unassigned virtual register.
 341 /// @param  Order   Physregs to try.
 342 /// @return         Physreg to assign VirtReg, or 0.
 343 unsigned RAGreedy::tryEvict(LiveInterval &VirtReg,
 344                             AllocationOrder &Order,
 345                             SmallVectorImpl<LiveInterval*> &NewVRegs){
 346   NamedRegionTimer T("Evict", TimerGroupName, TimePassesIsEnabled);
 347
 348   // Keep track of the lightest single interference seen so far.
 349   float BestWeight = 0;
 350   unsigned BestPhys = 0;
 351
 352   Order.rewind();
 353   while (unsigned PhysReg = Order.next()) {
 354     float Weight = 0;
 355     if (!canEvictInterference(VirtReg, PhysReg, Weight))
 356       continue;
 357
 358     // This is an eviction candidate.
 359     DEBUG(dbgs() << "max " << PrintReg(PhysReg, TRI) << " interference = "
 360                  << Weight << '\n');
 361     if (BestPhys && Weight >= BestWeight)
 362       continue;
 363
 364     // Best so far.
 365     BestPhys = PhysReg;
 366     BestWeight = Weight;
 367     // Stop if the hint can be used.
 368     if (Order.isHint(PhysReg))
 369       break;
 370   }
 371
 372   if (!BestPhys)
 373     return 0;
 374
 375   DEBUG(dbgs() << "evicting " << PrintReg(BestPhys, TRI) << " interference\n");
 376   for (const unsigned *AliasI = TRI->getOverlaps(BestPhys); *AliasI; ++AliasI) {
 377     LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI);
 378     assert(Q.seenAllInterferences() && "Didn't check all interfererences.");
 379     for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) {
 380       LiveInterval *Intf = Q.interferingVRegs()[i];
 381       unassign(*Intf, VRM->getPhys(Intf->reg));
 382       ++NumEvicted;
 383       NewVRegs.push_back(Intf);
 384     }
 385   }
 386   return BestPhys;
 387 }
 388
 389
 390 //===----------------------------------------------------------------------===//
 391 //                              Region Splitting
 392 //===----------------------------------------------------------------------===//
 393
 394 /// mapGlobalInterference - Compute a map of the interference from PhysReg and
 395 /// its aliases in each block in SA->LiveBlocks.
 396 /// If LiveBlocks[i] is live-in, Ranges[i].first is the first interference.
 397 /// If LiveBlocks[i] is live-out, Ranges[i].second is the last interference.
 398 void RAGreedy::mapGlobalInterference(unsigned PhysReg,
 399                                      SmallVectorImpl<IndexPair> &Ranges) {
 400   Ranges.assign(SA->LiveBlocks.size(), IndexPair());
 401   LiveInterval &VirtReg = const_cast<LiveInterval&>(SA->getParent());
 402   for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
 403     if (!query(VirtReg, *AI).checkInterference())
 404       continue;
 405     LiveIntervalUnion::SegmentIter IntI =
 406       PhysReg2LiveUnion[*AI].find(VirtReg.beginIndex());
 407     if (!IntI.valid())
 408       continue;
 409     for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) {
 410       const SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i];
 411       IndexPair &IP = Ranges[i];
 412
 413       // Skip interference-free blocks.
 414       if (IntI.start() >= BI.Stop)
 415         continue;
 416
 417       // First interference in block.
 418       if (BI.LiveIn) {
 419         IntI.advanceTo(BI.Start);
 420         if (!IntI.valid())
 421           break;
 422         if (IntI.start() >= BI.Stop)
 423           continue;
 424         if (!IP.first.isValid() || IntI.start() < IP.first)
 425           IP.first = IntI.start();
 426       }
 427
 428       // Last interference in block.
 429       if (BI.LiveOut) {
 430         IntI.advanceTo(BI.Stop);
 431         if (!IntI.valid() || IntI.start() >= BI.Stop)
 432           --IntI;
 433         if (IntI.stop() <= BI.Start)
 434           continue;
 435         if (!IP.second.isValid() || IntI.stop() > IP.second)
 436           IP.second = IntI.stop();
 437       }
 438     }
 439   }
 440 }
 441
 442 /// calcSplitConstraints - Fill out the SplitConstraints vector based on the
 443 /// interference pattern in Intf. Return the static cost of this split,
 444 /// assuming that all preferences in SplitConstraints are met.
 445 float RAGreedy::calcSplitConstraints(const SmallVectorImpl<IndexPair> &Intf) {
 446   // Reset interference dependent info.
 447   SplitConstraints.resize(SA->LiveBlocks.size());
 448   float StaticCost = 0;
 449   for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) {
 450     SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i];
 451     SpillPlacement::BlockConstraint &BC = SplitConstraints[i];
 452     IndexPair IP = Intf[i];
 453
 454     BC.Number = BI.MBB->getNumber();
 455     BC.Entry = (BI.Uses && BI.LiveIn) ?
 456       SpillPlacement::PrefReg : SpillPlacement::DontCare;
 457     BC.Exit = (BI.Uses && BI.LiveOut) ?
 458       SpillPlacement::PrefReg : SpillPlacement::DontCare;
 459
 460     // Number of spill code instructions to insert.
 461     unsigned Ins = 0;
 462
 463     // Interference for the live-in value.
 464     if (IP.first.isValid()) {
 465       if (IP.first <= BI.Start)
 466         BC.Entry = SpillPlacement::MustSpill, Ins += BI.Uses;
 467       else if (!BI.Uses)
 468         BC.Entry = SpillPlacement::PrefSpill;
 469       else if (IP.first < BI.FirstUse)
 470         BC.Entry = SpillPlacement::PrefSpill, ++Ins;
 471       else if (IP.first < (BI.LiveThrough ? BI.LastUse : BI.Kill))
 472         ++Ins;
 473     }
 474
 475     // Interference for the live-out value.
 476     if (IP.second.isValid()) {
 477       if (IP.second >= BI.LastSplitPoint)
 478         BC.Exit = SpillPlacement::MustSpill, Ins += BI.Uses;
 479       else if (!BI.Uses)
 480         BC.Exit = SpillPlacement::PrefSpill;
 481       else if (IP.second > BI.LastUse)
 482         BC.Exit = SpillPlacement::PrefSpill, ++Ins;
 483       else if (IP.second > (BI.LiveThrough ? BI.FirstUse : BI.Def))
 484         ++Ins;
 485     }
 486
 487     // Accumulate the total frequency of inserted spill code.
 488     if (Ins)
 489       StaticCost += Ins * SpillPlacer->getBlockFrequency(BC.Number);
 490   }
 491   return StaticCost;
 492 }
 493
 494
 495 /// calcGlobalSplitCost - Return the global split cost of following the split
 496 /// pattern in LiveBundles. This cost should be added to the local cost of the
 497 /// interference pattern in SplitConstraints.
 498 ///
 499 float RAGreedy::calcGlobalSplitCost(const BitVector &LiveBundles) {
 500   float GlobalCost = 0;
 501   for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) {
 502     SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i];
 503     SpillPlacement::BlockConstraint &BC = SplitConstraints[i];
 504     bool RegIn  = LiveBundles[Bundles->getBundle(BC.Number, 0)];
 505     bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, 1)];
 506     unsigned Ins = 0;
 507
 508     if (!BI.Uses)
 509       Ins += RegIn != RegOut;
 510     else {
 511       if (BI.LiveIn)
 512         Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg);
 513       if (BI.LiveOut)
 514         Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg);
 515     }
 516     if (Ins)
 517       GlobalCost += Ins * SpillPlacer->getBlockFrequency(BC.Number);
 518   }
 519   return GlobalCost;
 520 }
 521
 522 /// splitAroundRegion - Split VirtReg around the region determined by
 523 /// LiveBundles. Make an effort to avoid interference from PhysReg.
 524 ///
 525 /// The 'register' interval is going to contain as many uses as possible while
 526 /// avoiding interference. The 'stack' interval is the complement constructed by
 527 /// SplitEditor. It will contain the rest.
 528 ///
 529 void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
 530                                  const BitVector &LiveBundles,
 531                                  SmallVectorImpl<LiveInterval*> &NewVRegs) {
 532   DEBUG({
 533     dbgs() << "Splitting around region for " << PrintReg(PhysReg, TRI)
 534            << " with bundles";
 535     for (int i = LiveBundles.find_first(); i>=0; i = LiveBundles.find_next(i))
 536       dbgs() << " EB#" << i;
 537     dbgs() << ".\n";
 538   });
 539
 540   // First compute interference ranges in the live blocks.
 541   SmallVector<IndexPair, 8> InterferenceRanges;
 542   mapGlobalInterference(PhysReg, InterferenceRanges);
 543
 544   LiveRangeEdit LREdit(VirtReg, NewVRegs, this);
 545   SE->reset(LREdit);
 546
 547   // Create the main cross-block interval.
 548   SE->openIntv();
 549
 550   // First add all defs that are live out of a block.
 551   for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) {
 552     SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i];
 553     bool RegIn  = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)];
 554     bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)];
 555
 556     // Should the register be live out?
 557     if (!BI.LiveOut || !RegOut)
 558       continue;
 559
 560     IndexPair &IP = InterferenceRanges[i];
 561     DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " -> EB#"
 562                  << Bundles->getBundle(BI.MBB->getNumber(), 1)
 563                  << " [" << BI.Start << ';' << BI.LastSplitPoint << '-'
 564                  << BI.Stop << ") intf [" << IP.first << ';' << IP.second
 565                  << ')');
 566
 567     // The interference interval should either be invalid or overlap MBB.
 568     assert((!IP.first.isValid() || IP.first < BI.Stop) && "Bad interference");
 569     assert((!IP.second.isValid() || IP.second > BI.Start)
 570            && "Bad interference");
 571
 572     // Check interference leaving the block.
 573     if (!IP.second.isValid()) {
 574       // Block is interference-free.
 575       DEBUG(dbgs() << ", no interference");
 576       if (!BI.Uses) {
 577         assert(BI.LiveThrough && "No uses, but not live through block?");
 578         // Block is live-through without interference.
 579         DEBUG(dbgs() << ", no uses"
 580                      << (RegIn ? ", live-through.\n" : ", stack in.\n"));
 581         if (!RegIn)
 582           SE->enterIntvAtEnd(*BI.MBB);
 583         continue;
 584       }
 585       if (!BI.LiveThrough) {
 586         DEBUG(dbgs() << ", not live-through.\n");
 587         SE->useIntv(SE->enterIntvBefore(BI.Def), BI.Stop);
 588         continue;
 589       }
 590       if (!RegIn) {
 591         // Block is live-through, but entry bundle is on the stack.
 592         // Reload just before the first use.
 593         DEBUG(dbgs() << ", not live-in, enter before first use.\n");
 594         SE->useIntv(SE->enterIntvBefore(BI.FirstUse), BI.Stop);
 595         continue;
 596       }
 597       DEBUG(dbgs() << ", live-through.\n");
 598       continue;
 599     }
 600
 601     // Block has interference.
 602     DEBUG(dbgs() << ", interference to " << IP.second);
 603
 604     if (!BI.LiveThrough && IP.second <= BI.Def) {
 605       // The interference doesn't reach the outgoing segment.
 606       DEBUG(dbgs() << " doesn't affect def from " << BI.Def << '\n');
 607       SE->useIntv(BI.Def, BI.Stop);
 608       continue;
 609     }
 610
 611
 612     if (!BI.Uses) {
 613       // No uses in block, avoid interference by reloading as late as possible.
 614       DEBUG(dbgs() << ", no uses.\n");
 615       SlotIndex SegStart = SE->enterIntvAtEnd(*BI.MBB);
 616       assert(SegStart >= IP.second && "Couldn't avoid interference");
 617       continue;
 618     }
 619
 620     if (IP.second.getBoundaryIndex() < BI.LastUse) {
 621       // There are interference-free uses at the end of the block.
 622       // Find the first use that can get the live-out register.
 623       SmallVectorImpl<SlotIndex>::const_iterator UI =
 624         std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(),
 625                          IP.second.getBoundaryIndex());
 626       assert(UI != SA->UseSlots.end() && "Couldn't find last use");
 627       SlotIndex Use = *UI;
 628       assert(Use <= BI.LastUse && "Couldn't find last use");
 629       // Only attempt a split befroe the last split point.
 630       if (Use.getBaseIndex() <= BI.LastSplitPoint) {
 631         DEBUG(dbgs() << ", free use at " << Use << ".\n");
 632         SlotIndex SegStart = SE->enterIntvBefore(Use);
 633         assert(SegStart >= IP.second && "Couldn't avoid interference");
 634         assert(SegStart < BI.LastSplitPoint && "Impossible split point");
 635         SE->useIntv(SegStart, BI.Stop);
 636         continue;
 637       }
 638     }
 639
 640     // Interference is after the last use.
 641     DEBUG(dbgs() << " after last use.\n");
 642     SlotIndex SegStart = SE->enterIntvAtEnd(*BI.MBB);
 643     assert(SegStart >= IP.second && "Couldn't avoid interference");
 644   }
 645
 646   // Now all defs leading to live bundles are handled, do everything else.
 647   for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) {
 648     SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i];
 649     bool RegIn  = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)];
 650     bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)];
 651
 652     // Is the register live-in?
 653     if (!BI.LiveIn || !RegIn)
 654       continue;
 655
 656     // We have an incoming register. Check for interference.
 657     IndexPair &IP = InterferenceRanges[i];
 658
 659     DEBUG(dbgs() << "EB#" << Bundles->getBundle(BI.MBB->getNumber(), 0)
 660                  << " -> BB#" << BI.MBB->getNumber() << " [" << BI.Start << ';'
 661                  << BI.LastSplitPoint << '-' << BI.Stop << ')');
 662
 663     // Check interference entering the block.
 664     if (!IP.first.isValid()) {
 665       // Block is interference-free.
 666       DEBUG(dbgs() << ", no interference");
 667       if (!BI.Uses) {
 668         assert(BI.LiveThrough && "No uses, but not live through block?");
 669         // Block is live-through without interference.
 670         if (RegOut) {
 671           DEBUG(dbgs() << ", no uses, live-through.\n");
 672           SE->useIntv(BI.Start, BI.Stop);
 673         } else {
 674           DEBUG(dbgs() << ", no uses, stack-out.\n");
 675           SE->leaveIntvAtTop(*BI.MBB);
 676         }
 677         continue;
 678       }
 679       if (!BI.LiveThrough) {
 680         DEBUG(dbgs() << ", killed in block.\n");
 681         SE->useIntv(BI.Start, SE->leaveIntvAfter(BI.Kill));
 682         continue;
 683       }
 684       if (!RegOut) {
 685         // Block is live-through, but exit bundle is on the stack.
 686         // Spill immediately after the last use.
 687         if (BI.LastUse < BI.LastSplitPoint) {
 688           DEBUG(dbgs() << ", uses, stack-out.\n");
 689           SE->useIntv(BI.Start, SE->leaveIntvAfter(BI.LastUse));
 690           continue;
 691         }
 692         // The last use is after the last split point, it is probably an
 693         // indirect jump.
 694         DEBUG(dbgs() << ", uses at " << BI.LastUse << " after split point "
 695                      << BI.LastSplitPoint << ", stack-out.\n");
 696         SlotIndex SegEnd = SE->leaveIntvBefore(BI.LastSplitPoint);
 697         SE->useIntv(BI.Start, SegEnd);
 698         // Run a double interval from the split to the last use.
 699         // This makes it possible to spill the complement without affecting the
 700         // indirect branch.
 701         SE->overlapIntv(SegEnd, BI.LastUse);
 702         continue;
 703       }
 704       // Register is live-through.
 705       DEBUG(dbgs() << ", uses, live-through.\n");
 706       SE->useIntv(BI.Start, BI.Stop);
 707       continue;
 708     }
 709
 710     // Block has interference.
 711     DEBUG(dbgs() << ", interference from " << IP.first);
 712
 713     if (!BI.LiveThrough && IP.first >= BI.Kill) {
 714       // The interference doesn't reach the outgoing segment.
 715       DEBUG(dbgs() << " doesn't affect kill at " << BI.Kill << '\n');
 716       SE->useIntv(BI.Start, BI.Kill);
 717       continue;
 718     }
 719
 720     if (!BI.Uses) {
 721       // No uses in block, avoid interference by spilling as soon as possible.
 722       DEBUG(dbgs() << ", no uses.\n");
 723       SlotIndex SegEnd = SE->leaveIntvAtTop(*BI.MBB);
 724       assert(SegEnd <= IP.first && "Couldn't avoid interference");
 725       continue;
 726     }
 727     if (IP.first.getBaseIndex() > BI.FirstUse) {
 728       // There are interference-free uses at the beginning of the block.
 729       // Find the last use that can get the register.
 730       SmallVectorImpl<SlotIndex>::const_iterator UI =
 731         std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(),
 732                          IP.first.getBaseIndex());
 733       assert(UI != SA->UseSlots.begin() && "Couldn't find first use");
 734       SlotIndex Use = (--UI)->getBoundaryIndex();
 735       DEBUG(dbgs() << ", free use at " << *UI << ".\n");
 736       SlotIndex SegEnd = SE->leaveIntvAfter(Use);
 737       assert(SegEnd <= IP.first && "Couldn't avoid interference");
 738       SE->useIntv(BI.Start, SegEnd);
 739       continue;
 740     }
 741
 742     // Interference is before the first use.
 743     DEBUG(dbgs() << " before first use.\n");
 744     SlotIndex SegEnd = SE->leaveIntvAtTop(*BI.MBB);
 745     assert(SegEnd <= IP.first && "Couldn't avoid interference");
 746   }
 747
 748   SE->closeIntv();
 749
 750   // FIXME: Should we be more aggressive about splitting the stack region into
 751   // per-block segments? The current approach allows the stack region to
 752   // separate into connected components. Some components may be allocatable.
 753   SE->finish();
 754   ++NumGlobalSplits;
 755
 756   if (VerifyEnabled)
 757     MF->verify(this, "After splitting live range around region");
 758 }
 759
 760 unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
 761                                   SmallVectorImpl<LiveInterval*> &NewVRegs) {
 762   BitVector LiveBundles, BestBundles;
 763   float BestCost = 0;
 764   unsigned BestReg = 0;
 765
 766   Order.rewind();
 767   for (unsigned Cand = 0; unsigned PhysReg = Order.next(); ++Cand) {
 768     if (GlobalCand.size() <= Cand)
 769       GlobalCand.resize(Cand+1);
 770     GlobalCand[Cand].PhysReg = PhysReg;
 771
 772     mapGlobalInterference(PhysReg, GlobalCand[Cand].Interference);
 773     float Cost = calcSplitConstraints(GlobalCand[Cand].Interference);
 774     DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tstatic = " << Cost);
 775     if (BestReg && Cost >= BestCost) {
 776       DEBUG(dbgs() << " higher.\n");
 777       continue;
 778     }
 779
 780     SpillPlacer->placeSpills(SplitConstraints, LiveBundles);
 781     // No live bundles, defer to splitSingleBlocks().
 782     if (!LiveBundles.any()) {
 783       DEBUG(dbgs() << " no bundles.\n");
 784       continue;
 785     }
 786
 787     Cost += calcGlobalSplitCost(LiveBundles);
 788     DEBUG({
 789       dbgs() << ", total = " << Cost << " with bundles";
 790       for (int i = LiveBundles.find_first(); i>=0; i = LiveBundles.find_next(i))
 791         dbgs() << " EB#" << i;
 792       dbgs() << ".\n";
 793     });
 794     if (!BestReg || Cost < BestCost) {
 795       BestReg = PhysReg;
 796       BestCost = 0.98f * Cost; // Prevent rounding effects.
 797       BestBundles.swap(LiveBundles);
 798     }
 799   }
 800
 801   if (!BestReg)
 802     return 0;
 803
 804   splitAroundRegion(VirtReg, BestReg, BestBundles, NewVRegs);
 805   setStage(NewVRegs.begin(), NewVRegs.end(), RS_Region);
 806   return 0;
 807 }
 808
 809
 810 //===----------------------------------------------------------------------===//
 811 //                             Local Splitting
 812 //===----------------------------------------------------------------------===//
 813
 814
 815 /// calcGapWeights - Compute the maximum spill weight that needs to be evicted
 816 /// in order to use PhysReg between two entries in SA->UseSlots.
 817 ///
 818 /// GapWeight[i] represents the gap between UseSlots[i] and UseSlots[i+1].
 819 ///
 820 void RAGreedy::calcGapWeights(unsigned PhysReg,
 821                               SmallVectorImpl<float> &GapWeight) {
 822   assert(SA->LiveBlocks.size() == 1 && "Not a local interval");
 823   const SplitAnalysis::BlockInfo &BI = SA->LiveBlocks.front();
 824   const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots;
 825   const unsigned NumGaps = Uses.size()-1;
 826
 827   // Start and end points for the interference check.
 828   SlotIndex StartIdx = BI.LiveIn ? BI.FirstUse.getBaseIndex() : BI.FirstUse;
 829   SlotIndex StopIdx = BI.LiveOut ? BI.LastUse.getBoundaryIndex() : BI.LastUse;
 830
 831   GapWeight.assign(NumGaps, 0.0f);
 832
 833   // Add interference from each overlapping register.
 834   for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
 835     if (!query(const_cast<LiveInterval&>(SA->getParent()), *AI)
 836            .checkInterference())
 837       continue;
 838
 839     // We know that VirtReg is a continuous interval from FirstUse to LastUse,
 840     // so we don't need InterferenceQuery.
 841     //
 842     // Interference that overlaps an instruction is counted in both gaps
 843     // surrounding the instruction. The exception is interference before
 844     // StartIdx and after StopIdx.
 845     //
 846     LiveIntervalUnion::SegmentIter IntI = PhysReg2LiveUnion[*AI].find(StartIdx);
 847     for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) {
 848       // Skip the gaps before IntI.
 849       while (Uses[Gap+1].getBoundaryIndex() < IntI.start())
 850         if (++Gap == NumGaps)
 851           break;
 852       if (Gap == NumGaps)
 853         break;
 854
 855       // Update the gaps covered by IntI.
 856       const float weight = IntI.value()->weight;
 857       for (; Gap != NumGaps; ++Gap) {
 858         GapWeight[Gap] = std::max(GapWeight[Gap], weight);
 859         if (Uses[Gap+1].getBaseIndex() >= IntI.stop())
 860           break;
 861       }
 862       if (Gap == NumGaps)
 863         break;
 864     }
 865   }
 866 }
 867
 868 /// getPrevMappedIndex - Return the slot index of the last non-copy instruction
 869 /// before MI that has a slot index. If MI is the first mapped instruction in
 870 /// its block, return the block start index instead.
 871 ///
 872 SlotIndex RAGreedy::getPrevMappedIndex(const MachineInstr *MI) {
 873   assert(MI && "Missing MachineInstr");
 874   const MachineBasicBlock *MBB = MI->getParent();
 875   MachineBasicBlock::const_iterator B = MBB->begin(), I = MI;
 876   while (I != B)
 877     if (!(--I)->isDebugValue() && !I->isCopy())
 878       return Indexes->getInstructionIndex(I);
 879   return Indexes->getMBBStartIdx(MBB);
 880 }
 881
 882 /// calcPrevSlots - Fill in the PrevSlot array with the index of the previous
 883 /// real non-copy instruction for each instruction in SA->UseSlots.
 884 ///
 885 void RAGreedy::calcPrevSlots() {
 886   const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots;
 887   PrevSlot.clear();
 888   PrevSlot.reserve(Uses.size());
 889   for (unsigned i = 0, e = Uses.size(); i != e; ++i) {
 890     const MachineInstr *MI = Indexes->getInstructionFromIndex(Uses[i]);
 891     PrevSlot.push_back(getPrevMappedIndex(MI).getDefIndex());
 892   }
 893 }
 894
 895 /// nextSplitPoint - Find the next index into SA->UseSlots > i such that it may
 896 /// be beneficial to split before UseSlots[i].
 897 ///
 898 /// 0 is always a valid split point
 899 unsigned RAGreedy::nextSplitPoint(unsigned i) {
 900   const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots;
 901   const unsigned Size = Uses.size();
 902   assert(i != Size && "No split points after the end");
 903   // Allow split before i when Uses[i] is not adjacent to the previous use.
 904   while (++i != Size && PrevSlot[i].getBaseIndex() <= Uses[i-1].getBaseIndex())
 905     ;
 906   return i;
 907 }
 908
 909 /// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only
 910 /// basic block.
 911 ///
 912 unsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order,
 913                                  SmallVectorImpl<LiveInterval*> &NewVRegs) {
 914   assert(SA->LiveBlocks.size() == 1 && "Not a local interval");
 915   const SplitAnalysis::BlockInfo &BI = SA->LiveBlocks.front();
 916
 917   // Note that it is possible to have an interval that is live-in or live-out
 918   // while only covering a single block - A phi-def can use undef values from
 919   // predecessors, and the block could be a single-block loop.
 920   // We don't bother doing anything clever about such a case, we simply assume
 921   // that the interval is continuous from FirstUse to LastUse. We should make
 922   // sure that we don't do anything illegal to such an interval, though.
 923
 924   const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots;
 925   if (Uses.size() <= 2)
 926     return 0;
 927   const unsigned NumGaps = Uses.size()-1;
 928
 929   DEBUG({
 930     dbgs() << "tryLocalSplit: ";
 931     for (unsigned i = 0, e = Uses.size(); i != e; ++i)
 932       dbgs() << ' ' << SA->UseSlots[i];
 933     dbgs() << '\n';
 934   });
 935
 936   // For every use, find the previous mapped non-copy instruction.
 937   // We use this to detect valid split points, and to estimate new interval
 938   // sizes.
 939   calcPrevSlots();
 940
 941   unsigned BestBefore = NumGaps;
 942   unsigned BestAfter = 0;
 943   float BestDiff = 0;
 944
 945   const float blockFreq = SpillPlacer->getBlockFrequency(BI.MBB->getNumber());
 946   SmallVector<float, 8> GapWeight;
 947
 948   Order.rewind();
 949   while (unsigned PhysReg = Order.next()) {
 950     // Keep track of the largest spill weight that would need to be evicted in
 951     // order to make use of PhysReg between UseSlots[i] and UseSlots[i+1].
 952     calcGapWeights(PhysReg, GapWeight);
 953
 954     // Try to find the best sequence of gaps to close.
 955     // The new spill weight must be larger than any gap interference.
 956
 957     // We will split before Uses[SplitBefore] and after Uses[SplitAfter].
 958     unsigned SplitBefore = 0, SplitAfter = nextSplitPoint(1) - 1;
 959
 960     // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]).
 961     // It is the spill weight that needs to be evicted.
 962     float MaxGap = GapWeight[0];
 963     for (unsigned i = 1; i != SplitAfter; ++i)
 964       MaxGap = std::max(MaxGap, GapWeight[i]);
 965
 966     for (;;) {
 967       // Live before/after split?
 968       const bool LiveBefore = SplitBefore != 0 || BI.LiveIn;
 969       const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut;
 970
 971       DEBUG(dbgs() << PrintReg(PhysReg, TRI) << ' '
 972                    << Uses[SplitBefore] << '-' << Uses[SplitAfter]
 973                    << " i=" << MaxGap);
 974
 975       // Stop before the interval gets so big we wouldn't be making progress.
 976       if (!LiveBefore && !LiveAfter) {
 977         DEBUG(dbgs() << " all\n");
 978         break;
 979       }
 980       // Should the interval be extended or shrunk?
 981       bool Shrink = true;
 982       if (MaxGap < HUGE_VALF) {
 983         // Estimate the new spill weight.
 984         //
 985         // Each instruction reads and writes the register, except the first
 986         // instr doesn't read when !FirstLive, and the last instr doesn't write
 987         // when !LastLive.
 988         //
 989         // We will be inserting copies before and after, so the total number of
 990         // reads and writes is 2 * EstUses.
 991         //
 992         const unsigned EstUses = 2*(SplitAfter - SplitBefore) +
 993                                  2*(LiveBefore + LiveAfter);
 994
 995         // Try to guess the size of the new interval. This should be trivial,
 996         // but the slot index of an inserted copy can be a lot smaller than the
 997         // instruction it is inserted before if there are many dead indexes
 998         // between them.
 999         //
1000         // We measure the distance from the instruction before SplitBefore to
1001         // get a conservative estimate.
1002         //
1003         // The final distance can still be different if inserting copies
1004         // triggers a slot index renumbering.
1005         //
1006         const float EstWeight = normalizeSpillWeight(blockFreq * EstUses,
1007                               PrevSlot[SplitBefore].distance(Uses[SplitAfter]));
1008         // Would this split be possible to allocate?
1009         // Never allocate all gaps, we wouldn't be making progress.
1010         float Diff = EstWeight - MaxGap;
1011         DEBUG(dbgs() << " w=" << EstWeight << " d=" << Diff);
1012         if (Diff > 0) {
1013           Shrink = false;
1014           if (Diff > BestDiff) {
1015             DEBUG(dbgs() << " (best)");
1016             BestDiff = Diff;
1017             BestBefore = SplitBefore;
1018             BestAfter = SplitAfter;
1019           }
1020         }
1021       }
1022
1023       // Try to shrink.
1024       if (Shrink) {
1025         SplitBefore = nextSplitPoint(SplitBefore);
1026         if (SplitBefore < SplitAfter) {
1027           DEBUG(dbgs() << " shrink\n");
1028           // Recompute the max when necessary.
1029           if (GapWeight[SplitBefore - 1] >= MaxGap) {
1030             MaxGap = GapWeight[SplitBefore];
1031             for (unsigned i = SplitBefore + 1; i != SplitAfter; ++i)
1032               MaxGap = std::max(MaxGap, GapWeight[i]);
1033           }
1034           continue;
1035         }
1036         MaxGap = 0;
1037       }
1038
1039       // Try to extend the interval.
1040       if (SplitAfter >= NumGaps) {
1041         DEBUG(dbgs() << " end\n");
1042         break;
1043       }
1044
1045       DEBUG(dbgs() << " extend\n");
1046       for (unsigned e = nextSplitPoint(SplitAfter + 1) - 1;
1047            SplitAfter != e; ++SplitAfter)
1048         MaxGap = std::max(MaxGap, GapWeight[SplitAfter]);
1049           continue;
1050     }
1051   }
1052
1053   // Didn't find any candidates?
1054   if (BestBefore == NumGaps)
1055     return 0;
1056
1057   DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore]
1058                << '-' << Uses[BestAfter] << ", " << BestDiff
1059                << ", " << (BestAfter - BestBefore + 1) << " instrs\n");
1060
1061   LiveRangeEdit LREdit(VirtReg, NewVRegs, this);
1062   SE->reset(LREdit);
1063
1064   SE->openIntv();
1065   SlotIndex SegStart = SE->enterIntvBefore(Uses[BestBefore]);
1066   SlotIndex SegStop  = SE->leaveIntvAfter(Uses[BestAfter]);
1067   SE->useIntv(SegStart, SegStop);
1068   SE->closeIntv();
1069   SE->finish();
1070   setStage(NewVRegs.begin(), NewVRegs.end(), RS_Local);
1071   ++NumLocalSplits;
1072
1073   return 0;
1074 }
1075
1076 //===----------------------------------------------------------------------===//
1077 //                          Live Range Splitting
1078 //===----------------------------------------------------------------------===//
1079
1080 /// trySplit - Try to split VirtReg or one of its interferences, making it
1081 /// assignable.
1082 /// @return Physreg when VirtReg may be assigned and/or new NewVRegs.
1083 unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order,
1084                             SmallVectorImpl<LiveInterval*>&NewVRegs) {
1085   // Local intervals are handled separately.
1086   if (LIS->intervalIsInOneMBB(VirtReg)) {
1087     NamedRegionTimer T("Local Splitting", TimerGroupName, TimePassesIsEnabled);
1088     SA->analyze(&VirtReg);
1089     return tryLocalSplit(VirtReg, Order, NewVRegs);
1090   }
1091
1092   NamedRegionTimer T("Global Splitting", TimerGroupName, TimePassesIsEnabled);
1093
1094   // Don't iterate global splitting.
1095   // Move straight to spilling if this range was produced by a global split.
1096   LiveRangeStage Stage = getStage(VirtReg);
1097   if (Stage >= RS_Block)
1098     return 0;
1099
1100   SA->analyze(&VirtReg);
1101
1102   // First try to split around a region spanning multiple blocks.
1103   if (Stage < RS_Region) {
1104     unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs);
1105     if (PhysReg || !NewVRegs.empty())
1106       return PhysReg;
1107   }
1108
1109   // Then isolate blocks with multiple uses.
1110   if (Stage < RS_Block) {
1111     SplitAnalysis::BlockPtrSet Blocks;
1112     if (SA->getMultiUseBlocks(Blocks)) {
1113       LiveRangeEdit LREdit(VirtReg, NewVRegs, this);
1114       SE->reset(LREdit);
1115       SE->splitSingleBlocks(Blocks);
1116       setStage(NewVRegs.begin(), NewVRegs.end(), RS_Block);
1117       if (VerifyEnabled)
1118         MF->verify(this, "After splitting live range around basic blocks");
1119     }
1120   }
1121
1122   // Don't assign any physregs.
1123   return 0;
1124 }
1125
1126
1127 //===----------------------------------------------------------------------===//
1128 //                            Main Entry Point
1129 //===----------------------------------------------------------------------===//
1130
1131 unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg,
1132                                  SmallVectorImpl<LiveInterval*> &NewVRegs) {
1133   // First try assigning a free register.
1134   AllocationOrder Order(VirtReg.reg, *VRM, ReservedRegs);
1135   while (unsigned PhysReg = Order.next()) {
1136     if (!checkPhysRegInterference(VirtReg, PhysReg))
1137       return PhysReg;
1138   }
1139
1140   if (unsigned PhysReg = tryEvict(VirtReg, Order, NewVRegs))
1141     return PhysReg;
1142
1143   assert(NewVRegs.empty() && "Cannot append to existing NewVRegs");
1144
1145   // The first time we see a live range, don't try to split or spill.
1146   // Wait until the second time, when all smaller ranges have been allocated.
1147   // This gives a better picture of the interference to split around.
1148   LiveRangeStage Stage = getStage(VirtReg);
1149   if (Stage == RS_Original) {
1150     LRStage[VirtReg.reg] = RS_Second;
1151     DEBUG(dbgs() << "wait for second round\n");
1152     NewVRegs.push_back(&VirtReg);
1153     return 0;
1154   }
1155
1156   assert(Stage < RS_Spill && "Cannot allocate after spilling");
1157
1158   // Try splitting VirtReg or interferences.
1159   unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs);
1160   if (PhysReg || !NewVRegs.empty())
1161     return PhysReg;
1162
1163   // Finally spill VirtReg itself.
1164   NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled);
1165   LiveRangeEdit LRE(VirtReg, NewVRegs, this);
1166   spiller().spill(LRE);
1167
1168   if (VerifyEnabled)
1169     MF->verify(this, "After spilling");
1170
1171   // The live virtual register requesting allocation was spilled, so tell
1172   // the caller not to allocate anything during this round.
1173   return 0;
1174 }
1175
1176 bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
1177   DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n"
1178                << "********** Function: "
1179                << ((Value*)mf.getFunction())->getName() << '\n');
1180
1181   MF = &mf;
1182   if (VerifyEnabled)
1183     MF->verify(this, "Before greedy register allocator");
1184
1185   RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>());
1186   Indexes = &getAnalysis<SlotIndexes>();
1187   DomTree = &getAnalysis<MachineDominatorTree>();
1188   ReservedRegs = TRI->getReservedRegs(*MF);
1189   SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
1190   Loops = &getAnalysis<MachineLoopInfo>();
1191   LoopRanges = &getAnalysis<MachineLoopRanges>();
1192   Bundles = &getAnalysis<EdgeBundles>();
1193   SpillPlacer = &getAnalysis<SpillPlacement>();
1194
1195   SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops));
1196   SE.reset(new SplitEditor(*SA, *LIS, *VRM, *DomTree));
1197   LRStage.clear();
1198   LRStage.resize(MRI->getNumVirtRegs());
1199
1200   allocatePhysRegs();
1201   addMBBLiveIns(MF);
1202   LIS->addKillFlags();
1203
1204   // Run rewriter
1205   {
1206     NamedRegionTimer T("Rewriter", TimerGroupName, TimePassesIsEnabled);
1207     VRM->rewrite(Indexes);
1208   }
1209
1210   // The pass output is in VirtRegMap. Release all the transient data.
1211   releaseMemory();
1212
1213   return true;
1214 }