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