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