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