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