lib/CodeGen/RegAllocGreedy.cpp

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