lib/CodeGen/RegAllocGreedy.cpp

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