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 "VirtRegRewriter.h"
  25 #include "llvm/Analysis/AliasAnalysis.h"
  26 #include "llvm/Function.h"
  27 #include "llvm/PassAnalysisSupport.h"
  28 #include "llvm/CodeGen/CalcSpillWeights.h"
  29 #include "llvm/CodeGen/EdgeBundles.h"
  30 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  31 #include "llvm/CodeGen/LiveStackAnalysis.h"
  32 #include "llvm/CodeGen/MachineDominators.h"
  33 #include "llvm/CodeGen/MachineFunctionPass.h"
  34 #include "llvm/CodeGen/MachineLoopInfo.h"
  35 #include "llvm/CodeGen/MachineLoopRanges.h"
  36 #include "llvm/CodeGen/MachineRegisterInfo.h"
  37 #include "llvm/CodeGen/Passes.h"
  38 #include "llvm/CodeGen/RegAllocRegistry.h"
  39 #include "llvm/CodeGen/RegisterCoalescer.h"
  40 #include "llvm/Target/TargetOptions.h"
  41 #include "llvm/Support/Debug.h"
  42 #include "llvm/Support/ErrorHandling.h"
  43 #include "llvm/Support/raw_ostream.h"
  44 #include "llvm/Support/Timer.h"
  45
  46 using namespace llvm;
  47
  48 static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator",
  49                                        createGreedyRegisterAllocator);
  50
  51 namespace {
  52 class RAGreedy : public MachineFunctionPass, public RegAllocBase {
  53   // context
  54   MachineFunction *MF;
  55   BitVector ReservedRegs;
  56
  57   // analyses
  58   SlotIndexes *Indexes;
  59   LiveStacks *LS;
  60   MachineDominatorTree *DomTree;
  61   MachineLoopInfo *Loops;
  62   MachineLoopRanges *LoopRanges;
  63   EdgeBundles *Bundles;
  64   SpillPlacement *SpillPlacer;
  65
  66   // state
  67   std::auto_ptr<Spiller> SpillerInstance;
  68   std::auto_ptr<SplitAnalysis> SA;
  69
  70   // splitting state.
  71
  72   /// All basic blocks where the current register is live.
  73   SmallVector<SpillPlacement::BlockConstraint, 8> SpillConstraints;
  74
  75   /// Additional information about basic blocks where the current variable is
  76   /// live. Such a block will look like one of these templates:
  77   ///
  78   ///  1. |   o---x   | Internal to block. Variable is only live in this block.
  79   ///  2. |---x       | Live-in, kill.
  80   ///  3. |       o---| Def, live-out.
  81   ///  4. |---x   o---| Live-in, kill, def, live-out.
  82   ///  5. |---o---o---| Live-through with uses or defs.
  83   ///  6. |-----------| Live-through without uses. Transparent.
  84   ///
  85   struct BlockInfo {
  86     MachineBasicBlock *MBB;
  87     SlotIndex FirstUse;   ///< First instr using current reg.
  88     SlotIndex LastUse;    ///< Last instr using current reg.
  89     SlotIndex Kill;       ///< Interval end point inside block.
  90     SlotIndex Def;        ///< Interval start point inside block.
  91     bool Uses;            ///< Current reg has uses or defs in block.
  92     bool LiveThrough;     ///< Live in whole block (Templ 5. or 6. above).
  93     bool LiveIn;          ///< Current reg is live in.
  94     bool LiveOut;         ///< Current reg is live out.
  95
  96     // Per-interference pattern scratch data.
  97     bool OverlapEntry;    ///< Interference overlaps entering interval.
  98     bool OverlapExit;     ///< Interference overlaps exiting interval.
  99   };
 100
 101   /// Basic blocks where var is live. This array is parallel to
 102   /// SpillConstraints.
 103   SmallVector<BlockInfo, 8> LiveBlocks;
 104
 105 public:
 106   RAGreedy();
 107
 108   /// Return the pass name.
 109   virtual const char* getPassName() const {
 110     return "Greedy Register Allocator";
 111   }
 112
 113   /// RAGreedy analysis usage.
 114   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 115
 116   virtual void releaseMemory();
 117
 118   virtual Spiller &spiller() { return *SpillerInstance; }
 119
 120   virtual float getPriority(LiveInterval *LI);
 121
 122   virtual unsigned selectOrSplit(LiveInterval&,
 123                                  SmallVectorImpl<LiveInterval*>&);
 124
 125   /// Perform register allocation.
 126   virtual bool runOnMachineFunction(MachineFunction &mf);
 127
 128   static char ID;
 129
 130 private:
 131   bool checkUncachedInterference(LiveInterval&, unsigned);
 132   LiveInterval *getSingleInterference(LiveInterval&, unsigned);
 133   bool reassignVReg(LiveInterval &InterferingVReg, unsigned OldPhysReg);
 134   bool reassignInterferences(LiveInterval &VirtReg, unsigned PhysReg);
 135   float calcInterferenceWeight(LiveInterval&, unsigned);
 136   void calcLiveBlockInfo(LiveInterval&);
 137   float calcInterferenceInfo(LiveInterval&, unsigned);
 138   float calcGlobalSplitCost(const BitVector&);
 139   void splitAroundRegion(LiveInterval&, unsigned, const BitVector&,
 140                          SmallVectorImpl<LiveInterval*>&);
 141
 142   unsigned tryReassign(LiveInterval&, AllocationOrder&);
 143   unsigned tryRegionSplit(LiveInterval&, AllocationOrder&,
 144                           SmallVectorImpl<LiveInterval*>&);
 145   unsigned trySplit(LiveInterval&, AllocationOrder&,
 146                     SmallVectorImpl<LiveInterval*>&);
 147   unsigned trySpillInterferences(LiveInterval&, AllocationOrder&,
 148                                  SmallVectorImpl<LiveInterval*>&);
 149 };
 150 } // end anonymous namespace
 151
 152 char RAGreedy::ID = 0;
 153
 154 FunctionPass* llvm::createGreedyRegisterAllocator() {
 155   return new RAGreedy();
 156 }
 157
 158 RAGreedy::RAGreedy(): MachineFunctionPass(ID) {
 159   initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
 160   initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
 161   initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
 162   initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
 163   initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry());
 164   initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
 165   initializeLiveStacksPass(*PassRegistry::getPassRegistry());
 166   initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
 167   initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
 168   initializeMachineLoopRangesPass(*PassRegistry::getPassRegistry());
 169   initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
 170   initializeEdgeBundlesPass(*PassRegistry::getPassRegistry());
 171   initializeSpillPlacementPass(*PassRegistry::getPassRegistry());
 172 }
 173
 174 void RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const {
 175   AU.setPreservesCFG();
 176   AU.addRequired<AliasAnalysis>();
 177   AU.addPreserved<AliasAnalysis>();
 178   AU.addRequired<LiveIntervals>();
 179   AU.addRequired<SlotIndexes>();
 180   AU.addPreserved<SlotIndexes>();
 181   if (StrongPHIElim)
 182     AU.addRequiredID(StrongPHIEliminationID);
 183   AU.addRequiredTransitive<RegisterCoalescer>();
 184   AU.addRequired<CalculateSpillWeights>();
 185   AU.addRequired<LiveStacks>();
 186   AU.addPreserved<LiveStacks>();
 187   AU.addRequired<MachineDominatorTree>();
 188   AU.addPreserved<MachineDominatorTree>();
 189   AU.addRequired<MachineLoopInfo>();
 190   AU.addPreserved<MachineLoopInfo>();
 191   AU.addRequired<MachineLoopRanges>();
 192   AU.addPreserved<MachineLoopRanges>();
 193   AU.addRequired<VirtRegMap>();
 194   AU.addPreserved<VirtRegMap>();
 195   AU.addRequired<EdgeBundles>();
 196   AU.addRequired<SpillPlacement>();
 197   MachineFunctionPass::getAnalysisUsage(AU);
 198 }
 199
 200 void RAGreedy::releaseMemory() {
 201   SpillerInstance.reset(0);
 202   RegAllocBase::releaseMemory();
 203 }
 204
 205 float RAGreedy::getPriority(LiveInterval *LI) {
 206   float Priority = LI->weight;
 207
 208   // Prioritize hinted registers so they are allocated first.
 209   std::pair<unsigned, unsigned> Hint;
 210   if (Hint.first || Hint.second) {
 211     // The hint can be target specific, a virtual register, or a physreg.
 212     Priority *= 2;
 213
 214     // Prefer physreg hints above anything else.
 215     if (Hint.first == 0 && TargetRegisterInfo::isPhysicalRegister(Hint.second))
 216       Priority *= 2;
 217   }
 218   return Priority;
 219 }
 220
 221
 222 //===----------------------------------------------------------------------===//
 223 //                         Register Reassignment
 224 //===----------------------------------------------------------------------===//
 225
 226 // Check interference without using the cache.
 227 bool RAGreedy::checkUncachedInterference(LiveInterval &VirtReg,
 228                                          unsigned PhysReg) {
 229   for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) {
 230     LiveIntervalUnion::Query subQ(&VirtReg, &PhysReg2LiveUnion[*AliasI]);
 231     if (subQ.checkInterference())
 232       return true;
 233   }
 234   return false;
 235 }
 236
 237 /// getSingleInterference - Return the single interfering virtual register
 238 /// assigned to PhysReg. Return 0 if more than one virtual register is
 239 /// interfering.
 240 LiveInterval *RAGreedy::getSingleInterference(LiveInterval &VirtReg,
 241                                               unsigned PhysReg) {
 242   // Check physreg and aliases.
 243   LiveInterval *Interference = 0;
 244   for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) {
 245     LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI);
 246     if (Q.checkInterference()) {
 247       if (Interference)
 248         return 0;
 249       Q.collectInterferingVRegs(1);
 250       if (!Q.seenAllInterferences())
 251         return 0;
 252       Interference = Q.interferingVRegs().front();
 253     }
 254   }
 255   return Interference;
 256 }
 257
 258 // Attempt to reassign this virtual register to a different physical register.
 259 //
 260 // FIXME: we are not yet caching these "second-level" interferences discovered
 261 // in the sub-queries. These interferences can change with each call to
 262 // selectOrSplit. However, we could implement a "may-interfere" cache that
 263 // could be conservatively dirtied when we reassign or split.
 264 //
 265 // FIXME: This may result in a lot of alias queries. We could summarize alias
 266 // live intervals in their parent register's live union, but it's messy.
 267 bool RAGreedy::reassignVReg(LiveInterval &InterferingVReg,
 268                             unsigned WantedPhysReg) {
 269   assert(TargetRegisterInfo::isVirtualRegister(InterferingVReg.reg) &&
 270          "Can only reassign virtual registers");
 271   assert(TRI->regsOverlap(WantedPhysReg, VRM->getPhys(InterferingVReg.reg)) &&
 272          "inconsistent phys reg assigment");
 273
 274   AllocationOrder Order(InterferingVReg.reg, *VRM, ReservedRegs);
 275   while (unsigned PhysReg = Order.next()) {
 276     // Don't reassign to a WantedPhysReg alias.
 277     if (TRI->regsOverlap(PhysReg, WantedPhysReg))
 278       continue;
 279
 280     if (checkUncachedInterference(InterferingVReg, PhysReg))
 281       continue;
 282
 283     // Reassign the interfering virtual reg to this physical reg.
 284     unsigned OldAssign = VRM->getPhys(InterferingVReg.reg);
 285     DEBUG(dbgs() << "reassigning: " << InterferingVReg << " from " <<
 286           TRI->getName(OldAssign) << " to " << TRI->getName(PhysReg) << '\n');
 287     PhysReg2LiveUnion[OldAssign].extract(InterferingVReg);
 288     VRM->clearVirt(InterferingVReg.reg);
 289     VRM->assignVirt2Phys(InterferingVReg.reg, PhysReg);
 290     PhysReg2LiveUnion[PhysReg].unify(InterferingVReg);
 291
 292     return true;
 293   }
 294   return false;
 295 }
 296
 297 /// reassignInterferences - Reassign all interferences to different physical
 298 /// registers such that Virtreg can be assigned to PhysReg.
 299 /// Currently this only works with a single interference.
 300 /// @param  VirtReg Currently unassigned virtual register.
 301 /// @param  PhysReg Physical register to be cleared.
 302 /// @return True on success, false if nothing was changed.
 303 bool RAGreedy::reassignInterferences(LiveInterval &VirtReg, unsigned PhysReg) {
 304   LiveInterval *InterferingVReg = getSingleInterference(VirtReg, PhysReg);
 305   if (!InterferingVReg)
 306     return false;
 307   if (TargetRegisterInfo::isPhysicalRegister(InterferingVReg->reg))
 308     return false;
 309   return reassignVReg(*InterferingVReg, PhysReg);
 310 }
 311
 312 /// tryReassign - Try to reassign interferences to different physregs.
 313 /// @param  VirtReg Currently unassigned virtual register.
 314 /// @param  Order   Physregs to try.
 315 /// @return         Physreg to assign VirtReg, or 0.
 316 unsigned RAGreedy::tryReassign(LiveInterval &VirtReg, AllocationOrder &Order) {
 317   NamedRegionTimer T("Reassign", TimerGroupName, TimePassesIsEnabled);
 318   Order.rewind();
 319   while (unsigned PhysReg = Order.next())
 320     if (reassignInterferences(VirtReg, PhysReg))
 321       return PhysReg;
 322   return 0;
 323 }
 324
 325
 326 //===----------------------------------------------------------------------===//
 327 //                              Region Splitting
 328 //===----------------------------------------------------------------------===//
 329
 330 /// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks
 331 /// where VirtReg is live.
 332 /// The SpillConstraints array is minimally initialized with MBB->getNumber().
 333 void RAGreedy::calcLiveBlockInfo(LiveInterval &VirtReg) {
 334   LiveBlocks.clear();
 335   SpillConstraints.clear();
 336
 337   assert(!VirtReg.empty() && "Cannot allocate an empty interval");
 338   LiveInterval::const_iterator LVI = VirtReg.begin();
 339   LiveInterval::const_iterator LVE = VirtReg.end();
 340
 341   SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE;
 342   UseI = SA->UseSlots.begin();
 343   UseE = SA->UseSlots.end();
 344
 345   // Loop over basic blocks where VirtReg is live.
 346   MachineFunction::iterator MFI = Indexes->getMBBFromIndex(LVI->start);
 347   for (;;) {
 348     // Block constraints depend on the interference pattern.
 349     // Just allocate them here, don't compute anything.
 350     SpillPlacement::BlockConstraint BC;
 351     BC.Number = MFI->getNumber();
 352     SpillConstraints.push_back(BC);
 353
 354     BlockInfo BI;
 355     BI.MBB = MFI;
 356     SlotIndex Start, Stop;
 357     tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
 358
 359     // LVI is the first live segment overlapping MBB.
 360     BI.LiveIn = LVI->start <= Start;
 361     if (!BI.LiveIn)
 362       BI.Def = LVI->start;
 363
 364     // Find the first and last uses in the block.
 365     BI.Uses = SA->hasUses(MFI);
 366     if (BI.Uses && UseI != UseE) {
 367       BI.FirstUse = *UseI;
 368       assert(BI.FirstUse >= Start);
 369       do ++UseI;
 370       while (UseI != UseE && *UseI < Stop);
 371       BI.LastUse = UseI[-1];
 372       assert(BI.LastUse < Stop);
 373     }
 374
 375     // Look for gaps in the live range.
 376     bool hasGap = false;
 377     BI.LiveOut = true;
 378     while (LVI->end < Stop) {
 379       SlotIndex LastStop = LVI->end;
 380       if (++LVI == LVE || LVI->start >= Stop) {
 381         BI.Kill = LastStop;
 382         BI.LiveOut = false;
 383         break;
 384       }
 385       if (LastStop < LVI->start) {
 386         hasGap = true;
 387         BI.Kill = LastStop;
 388         BI.Def = LVI->start;
 389       }
 390     }
 391
 392     // Don't set LiveThrough when the block has a gap.
 393     BI.LiveThrough = !hasGap && BI.LiveIn && BI.LiveOut;
 394     LiveBlocks.push_back(BI);
 395
 396     // LVI is now at LVE or LVI->end >= Stop.
 397     if (LVI == LVE)
 398       break;
 399
 400     // Live segment ends exactly at Stop. Move to the next segment.
 401     if (LVI->end == Stop && ++LVI == LVE)
 402       break;
 403
 404     // Pick the next basic block.
 405     if (LVI->start < Stop)
 406       ++MFI;
 407     else
 408       MFI = Indexes->getMBBFromIndex(LVI->start);
 409   }
 410 }
 411
 412 /// calcInterferenceInfo - Compute per-block outgoing and ingoing constraints
 413 /// when considering interference from PhysReg. Also compute an optimistic local
 414 /// cost of this interference pattern.
 415 ///
 416 /// The final cost of a split is the local cost + global cost of preferences
 417 /// broken by SpillPlacement.
 418 ///
 419 float RAGreedy::calcInterferenceInfo(LiveInterval &VirtReg, unsigned PhysReg) {
 420   // Reset interference dependent info.
 421   for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
 422     BlockInfo &BI = LiveBlocks[i];
 423     SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
 424     BC.Entry = (BI.Uses && BI.LiveIn) ?
 425       SpillPlacement::PrefReg : SpillPlacement::DontCare;
 426     BC.Exit = (BI.Uses && BI.LiveOut) ?
 427       SpillPlacement::PrefReg : SpillPlacement::DontCare;
 428     BI.OverlapEntry = BI.OverlapExit = false;
 429   }
 430
 431   // Add interference info from each PhysReg alias.
 432   for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
 433     if (!query(VirtReg, *AI).checkInterference())
 434       continue;
 435     DEBUG(PhysReg2LiveUnion[*AI].print(dbgs(), TRI));
 436     LiveIntervalUnion::SegmentIter IntI =
 437       PhysReg2LiveUnion[*AI].find(VirtReg.beginIndex());
 438     if (!IntI.valid())
 439       continue;
 440
 441     for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
 442       BlockInfo &BI = 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       // Handle transparent blocks with interference separately.
 452       // Transparent blocks never incur any fixed cost.
 453       if (BI.LiveThrough && !BI.Uses) {
 454         // Check if interference is live-in - force spill.
 455         if (BC.Entry != SpillPlacement::MustSpill) {
 456           BC.Entry = SpillPlacement::PrefSpill;
 457           IntI.advanceTo(Start);
 458           if (IntI.valid() && IntI.start() <= Start)
 459             BC.Entry = SpillPlacement::MustSpill;
 460         }
 461
 462         // Check if interference is live-out - force spill.
 463         if (BC.Exit != SpillPlacement::MustSpill) {
 464           BC.Exit = SpillPlacement::PrefSpill;
 465           IntI.advanceTo(Stop);
 466           if (IntI.valid() && IntI.start() < Stop)
 467             BC.Exit = SpillPlacement::MustSpill;
 468         }
 469
 470         // Nothing more to do for this transparent block.
 471         if (!IntI.valid())
 472           break;
 473         continue;
 474       }
 475
 476       // Now we only have blocks with uses left.
 477       // Check if the interference overlaps the uses.
 478       assert(BI.Uses && "Non-transparent block without any uses");
 479
 480       // Check interference on entry.
 481       if (BI.LiveIn && BC.Entry != SpillPlacement::MustSpill) {
 482         IntI.advanceTo(Start);
 483         if (!IntI.valid())
 484           break;
 485
 486         // Interference is live-in - force spill.
 487         if (IntI.start() <= Start)
 488           BC.Entry = SpillPlacement::MustSpill;
 489         // Not live in, but before the first use.
 490         else if (IntI.start() < BI.FirstUse)
 491           BC.Entry = SpillPlacement::PrefSpill;
 492       }
 493
 494       // Does interference overlap the uses in the entry segment
 495       // [FirstUse;Kill)?
 496       if (BI.LiveIn && !BI.OverlapEntry) {
 497         IntI.advanceTo(BI.FirstUse);
 498         if (!IntI.valid())
 499           break;
 500         // A live-through interval has no kill.
 501         // Check [FirstUse;LastUse) instead.
 502         if (IntI.start() < (BI.LiveThrough ? BI.LastUse : BI.Kill))
 503           BI.OverlapEntry = true;
 504       }
 505
 506       // Does interference overlap the uses in the exit segment [Def;LastUse)?
 507       if (BI.LiveOut && !BI.LiveThrough && !BI.OverlapExit) {
 508         IntI.advanceTo(BI.Def);
 509         if (!IntI.valid())
 510           break;
 511         if (IntI.start() < BI.LastUse)
 512           BI.OverlapExit = true;
 513       }
 514
 515       // Check interference on exit.
 516       if (BI.LiveOut && BC.Exit != SpillPlacement::MustSpill) {
 517         // Check interference between LastUse and Stop.
 518         if (BC.Exit != SpillPlacement::PrefSpill) {
 519           IntI.advanceTo(BI.LastUse);
 520           if (!IntI.valid())
 521             break;
 522           if (IntI.start() < Stop)
 523             BC.Exit = SpillPlacement::PrefSpill;
 524         }
 525         // Is the interference live-out?
 526         IntI.advanceTo(Stop);
 527         if (!IntI.valid())
 528           break;
 529         if (IntI.start() < Stop)
 530           BC.Exit = SpillPlacement::MustSpill;
 531       }
 532     }
 533   }
 534
 535   // Accumulate a local cost of this interference pattern.
 536   float LocalCost = 0;
 537   for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
 538     BlockInfo &BI = LiveBlocks[i];
 539     if (!BI.Uses)
 540       continue;
 541     SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
 542     unsigned Inserts = 0;
 543
 544     // Do we need spill code for the entry segment?
 545     if (BI.LiveIn)
 546       Inserts += BI.OverlapEntry || BC.Entry != SpillPlacement::PrefReg;
 547
 548     // For the exit segment?
 549     if (BI.LiveOut)
 550       Inserts += BI.OverlapExit || BC.Exit != SpillPlacement::PrefReg;
 551
 552     // The local cost of spill code in this block is the block frequency times
 553     // the number of spill instructions inserted.
 554     if (Inserts)
 555       LocalCost += Inserts * SpillPlacer->getBlockFrequency(BI.MBB);
 556   }
 557   DEBUG(dbgs() << "Local cost of " << PrintReg(PhysReg, TRI) << " = "
 558                << LocalCost << '\n');
 559   return LocalCost;
 560 }
 561
 562 /// calcGlobalSplitCost - Return the global split cost of following the split
 563 /// pattern in LiveBundles. This cost should be added to the local cost of the
 564 /// interference pattern in SpillConstraints.
 565 ///
 566 float RAGreedy::calcGlobalSplitCost(const BitVector &LiveBundles) {
 567   float GlobalCost = 0;
 568   for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
 569     SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
 570     unsigned Inserts = 0;
 571     // Broken entry preference?
 572     Inserts += LiveBundles[Bundles->getBundle(BC.Number, 0)] !=
 573                  (BC.Entry == SpillPlacement::PrefReg);
 574     // Broken exit preference?
 575     Inserts += LiveBundles[Bundles->getBundle(BC.Number, 1)] !=
 576                  (BC.Exit == SpillPlacement::PrefReg);
 577     if (Inserts)
 578       GlobalCost += Inserts * SpillPlacer->getBlockFrequency(LiveBlocks[i].MBB);
 579   }
 580   DEBUG(dbgs() << "Global cost = " << GlobalCost << '\n');
 581   return GlobalCost;
 582 }
 583
 584 /// splitAroundRegion - Split VirtReg around the region determined by
 585 /// LiveBundles. Make an effort to avoid interference from PhysReg.
 586 ///
 587 /// The 'register' interval is going to contain as many uses as possible while
 588 /// avoiding interference. The 'stack' interval is the complement constructed by
 589 /// SplitEditor. It will contain the rest.
 590 ///
 591 void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
 592                                  const BitVector &LiveBundles,
 593                                  SmallVectorImpl<LiveInterval*> &NewVRegs) {
 594   DEBUG({
 595     dbgs() << "Splitting around region for " << PrintReg(PhysReg, TRI)
 596            << " with bundles";
 597     for (int i = LiveBundles.find_first(); i>=0; i = LiveBundles.find_next(i))
 598       dbgs() << " EB#" << i;
 599     dbgs() << ".\n";
 600   });
 601
 602   // First compute interference ranges in the live blocks.
 603   typedef std::pair<SlotIndex, SlotIndex> IndexPair;
 604   SmallVector<IndexPair, 8> InterferenceRanges;
 605   InterferenceRanges.resize(LiveBlocks.size());
 606   for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
 607     if (!query(VirtReg, *AI).checkInterference())
 608       continue;
 609     LiveIntervalUnion::SegmentIter IntI =
 610       PhysReg2LiveUnion[*AI].find(VirtReg.beginIndex());
 611     if (!IntI.valid())
 612       continue;
 613     for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
 614       BlockInfo &BI = LiveBlocks[i];
 615       if (!BI.Uses)
 616         continue;
 617       IndexPair &IP = InterferenceRanges[i];
 618       SlotIndex Start, Stop;
 619       tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
 620       // Skip interference-free blocks.
 621       if (IntI.start() >= Stop)
 622         continue;
 623
 624       // First interference in block.
 625       if (BI.LiveIn) {
 626         IntI.advanceTo(Start);
 627         if (!IntI.valid())
 628           break;
 629         if (IntI.start() >= Stop)
 630           continue;
 631         if (!IP.first.isValid() || IntI.start() < IP.first)
 632           IP.first = IntI.start();
 633       }
 634
 635       // Last interference in block.
 636       if (BI.LiveOut) {
 637         IntI.advanceTo(Stop);
 638         if (!IntI.valid() || IntI.start() >= Stop)
 639           --IntI;
 640         if (IntI.stop() <= Start)
 641           continue;
 642         if (!IP.second.isValid() || IntI.stop() > IP.second)
 643           IP.second = IntI.stop();
 644       }
 645     }
 646   }
 647
 648   SmallVector<LiveInterval*, 4> SpillRegs;
 649   LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs);
 650   SplitEditor SE(*SA, *LIS, *VRM, *DomTree, LREdit);
 651
 652   // Create the main cross-block interval.
 653   SE.openIntv();
 654
 655   // First add all defs that are live out of a block.
 656   for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
 657     BlockInfo &BI = LiveBlocks[i];
 658     bool RegIn  = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)];
 659     bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)];
 660
 661     // Should the register be live out?
 662     if (!BI.LiveOut || !RegOut)
 663       continue;
 664
 665     IndexPair &IP = InterferenceRanges[i];
 666     SlotIndex Start, Stop;
 667     tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
 668
 669     DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " -> EB#"
 670                  << Bundles->getBundle(BI.MBB->getNumber(), 1)
 671                  << " intf [" << IP.first << ';' << IP.second << ')');
 672
 673     // The interference interval should either be invalid or overlap MBB.
 674     assert((!IP.first.isValid() || IP.first < Stop) && "Bad interference");
 675     assert((!IP.second.isValid() || IP.second > Start) && "Bad interference");
 676
 677     // Check interference leaving the block.
 678     if (!IP.second.isValid()) {
 679       // Block is interference-free.
 680       DEBUG(dbgs() << ", no interference");
 681       if (!BI.Uses) {
 682         assert(BI.LiveThrough && "No uses, but not live through block?");
 683         // Block is live-through without interference.
 684         DEBUG(dbgs() << ", no uses"
 685                      << (RegIn ? ", live-through.\n" : ", stack in.\n"));
 686         if (!RegIn)
 687           SE.enterIntvAtEnd(*BI.MBB);
 688         continue;
 689       }
 690       if (!BI.LiveThrough) {
 691         DEBUG(dbgs() << ", not live-through.\n");
 692         SE.useIntv(SE.enterIntvBefore(BI.Def), Stop);
 693         continue;
 694       }
 695       if (!RegIn) {
 696         // Block is live-through, but entry bundle is on the stack.
 697         // Reload just before the first use.
 698         DEBUG(dbgs() << ", not live-in, enter before first use.\n");
 699         SE.useIntv(SE.enterIntvBefore(BI.FirstUse), Stop);
 700         continue;
 701       }
 702       DEBUG(dbgs() << ", live-through.\n");
 703       continue;
 704     }
 705
 706     // Block has interference.
 707     DEBUG(dbgs() << ", interference to " << IP.second);
 708     if (!BI.Uses) {
 709       // No uses in block, avoid interference by reloading as late as possible.
 710       DEBUG(dbgs() << ", no uses.\n");
 711       SE.enterIntvAtEnd(*BI.MBB);
 712       continue;
 713     }
 714     if (IP.second < BI.LastUse) {
 715       // There are interference-free uses at the end of the block.
 716       // Find the first use that can get the live-out register.
 717       SmallVectorImpl<SlotIndex>::const_iterator UI =
 718         std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(), IP.second);
 719       assert(UI != SA->UseSlots.end() && "Couldn't find last use");
 720       SlotIndex Use = *UI;
 721       DEBUG(dbgs() << ", free use at " << Use << ".\n");
 722       assert(Use <= BI.LastUse && "Couldn't find last use");
 723       SE.useIntv(SE.enterIntvBefore(Use), Stop);
 724       continue;
 725     }
 726
 727     // Interference is after the last use.
 728     DEBUG(dbgs() << " after last use.\n");
 729     SE.enterIntvAtEnd(*BI.MBB);
 730   }
 731
 732   // Now all defs leading to live bundles are handled, do everything else.
 733   for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
 734     BlockInfo &BI = LiveBlocks[i];
 735     bool RegIn  = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)];
 736     bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)];
 737
 738     // Is the register live-in?
 739     if (!BI.LiveIn || !RegIn)
 740       continue;
 741
 742     // We have an incoming register. Check for interference.
 743     IndexPair &IP = InterferenceRanges[i];
 744     SlotIndex Start, Stop;
 745     tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
 746
 747     DEBUG(dbgs() << "EB#" << Bundles->getBundle(BI.MBB->getNumber(), 0)
 748                  << " -> BB#" << BI.MBB->getNumber());
 749
 750     // Check interference entering the block.
 751     if (!IP.first.isValid()) {
 752       // Block is interference-free.
 753       DEBUG(dbgs() << ", no interference");
 754       if (!BI.Uses) {
 755         assert(BI.LiveThrough && "No uses, but not live through block?");
 756         // Block is live-through without interference.
 757         if (RegOut) {
 758           DEBUG(dbgs() << ", no uses, live-through.\n");
 759           SE.useIntv(Start, Stop);
 760         } else {
 761           DEBUG(dbgs() << ", no uses, stack-out.\n");
 762           SE.leaveIntvAtTop(*BI.MBB);
 763         }
 764         continue;
 765       }
 766       if (!BI.LiveThrough) {
 767         DEBUG(dbgs() << ", killed in block.\n");
 768         SE.useIntv(Start, SE.leaveIntvAfter(BI.Kill));
 769         continue;
 770       }
 771       if (!RegOut) {
 772         // Block is live-through, but exit bundle is on the stack.
 773         // Spill immediately after the last use.
 774         DEBUG(dbgs() << ", uses, stack-out.\n");
 775         SE.useIntv(Start, SE.leaveIntvAfter(BI.LastUse));
 776         continue;
 777       }
 778       // Register is live-through.
 779       DEBUG(dbgs() << ", uses, live-through.\n");
 780       SE.useIntv(Start, Stop);
 781       continue;
 782     }
 783
 784     // Block has interference.
 785     DEBUG(dbgs() << ", interference from " << IP.first);
 786     if (!BI.Uses) {
 787       // No uses in block, avoid interference by spilling as soon as possible.
 788       DEBUG(dbgs() << ", no uses.\n");
 789       SE.leaveIntvAtTop(*BI.MBB);
 790       continue;
 791     }
 792     if (IP.first > BI.FirstUse) {
 793       // There are interference-free uses at the beginning of the block.
 794       // Find the last use that can get the register.
 795       SmallVectorImpl<SlotIndex>::const_iterator UI =
 796         std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(), IP.first);
 797       assert(UI != SA->UseSlots.begin() && "Couldn't find first use");
 798       SlotIndex Use = (--UI)->getBoundaryIndex();
 799       DEBUG(dbgs() << ", free use at " << *UI << ".\n");
 800       assert(Use >= BI.FirstUse && Use < IP.first);
 801       SE.useIntv(Start, SE.leaveIntvAfter(Use));
 802       continue;
 803     }
 804
 805     // Interference is before the first use.
 806     DEBUG(dbgs() << " before first use.\n");
 807     SE.leaveIntvAtTop(*BI.MBB);
 808   }
 809
 810   SE.closeIntv();
 811
 812   // FIXME: Should we be more aggressive about splitting the stack region into
 813   // per-block segments? The current approach allows the stack region to
 814   // separate into connected components. Some components may be allocatable.
 815   SE.finish();
 816
 817   if (VerifyEnabled)
 818     MF->verify(this, "After splitting live range around region");
 819 }
 820
 821 unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
 822                                   SmallVectorImpl<LiveInterval*> &NewVRegs) {
 823   calcLiveBlockInfo(VirtReg);
 824   BitVector LiveBundles, BestBundles;
 825   float BestCost = 0;
 826   unsigned BestReg = 0;
 827   Order.rewind();
 828   while (unsigned PhysReg = Order.next()) {
 829     float Cost = calcInterferenceInfo(VirtReg, PhysReg);
 830     if (BestReg && Cost >= BestCost)
 831       continue;
 832
 833     SpillPlacer->placeSpills(SpillConstraints, LiveBundles);
 834     // No live bundles, defer to splitSingleBlocks().
 835     if (!LiveBundles.any())
 836       continue;
 837
 838     Cost += calcGlobalSplitCost(LiveBundles);
 839     if (!BestReg || Cost < BestCost) {
 840       BestReg = PhysReg;
 841       BestCost = Cost;
 842       BestBundles.swap(LiveBundles);
 843     }
 844   }
 845
 846   if (!BestReg)
 847     return 0;
 848
 849   splitAroundRegion(VirtReg, BestReg, BestBundles, NewVRegs);
 850   return 0;
 851 }
 852
 853
 854 //===----------------------------------------------------------------------===//
 855 //                          Live Range Splitting
 856 //===----------------------------------------------------------------------===//
 857
 858 /// trySplit - Try to split VirtReg or one of its interferences, making it
 859 /// assignable.
 860 /// @return Physreg when VirtReg may be assigned and/or new NewVRegs.
 861 unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order,
 862                             SmallVectorImpl<LiveInterval*>&NewVRegs) {
 863   NamedRegionTimer T("Splitter", TimerGroupName, TimePassesIsEnabled);
 864   SA->analyze(&VirtReg);
 865
 866   // Don't attempt splitting on local intervals for now. TBD.
 867   if (LIS->intervalIsInOneMBB(VirtReg))
 868     return 0;
 869
 870   // First try to split around a region spanning multiple blocks.
 871   unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs);
 872   if (PhysReg || !NewVRegs.empty())
 873     return PhysReg;
 874
 875   // Then isolate blocks with multiple uses.
 876   SplitAnalysis::BlockPtrSet Blocks;
 877   if (SA->getMultiUseBlocks(Blocks)) {
 878     SmallVector<LiveInterval*, 4> SpillRegs;
 879     LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs);
 880     SplitEditor(*SA, *LIS, *VRM, *DomTree, LREdit).splitSingleBlocks(Blocks);
 881     if (VerifyEnabled)
 882       MF->verify(this, "After splitting live range around basic blocks");
 883   }
 884
 885   // Don't assign any physregs.
 886   return 0;
 887 }
 888
 889
 890 //===----------------------------------------------------------------------===//
 891 //                                Spilling
 892 //===----------------------------------------------------------------------===//
 893
 894 /// calcInterferenceWeight - Calculate the combined spill weight of
 895 /// interferences when assigning VirtReg to PhysReg.
 896 float RAGreedy::calcInterferenceWeight(LiveInterval &VirtReg, unsigned PhysReg){
 897   float Sum = 0;
 898   for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
 899     LiveIntervalUnion::Query &Q = query(VirtReg, *AI);
 900     Q.collectInterferingVRegs();
 901     if (Q.seenUnspillableVReg())
 902       return HUGE_VALF;
 903     for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i)
 904       Sum += Q.interferingVRegs()[i]->weight;
 905   }
 906   return Sum;
 907 }
 908
 909 /// trySpillInterferences - Try to spill interfering registers instead of the
 910 /// current one. Only do it if the accumulated spill weight is smaller than the
 911 /// current spill weight.
 912 unsigned RAGreedy::trySpillInterferences(LiveInterval &VirtReg,
 913                                          AllocationOrder &Order,
 914                                      SmallVectorImpl<LiveInterval*> &NewVRegs) {
 915   NamedRegionTimer T("Spill Interference", TimerGroupName, TimePassesIsEnabled);
 916   unsigned BestPhys = 0;
 917   float BestWeight = 0;
 918
 919   Order.rewind();
 920   while (unsigned PhysReg = Order.next()) {
 921     float Weight = calcInterferenceWeight(VirtReg, PhysReg);
 922     if (Weight == HUGE_VALF || Weight >= VirtReg.weight)
 923       continue;
 924     if (!BestPhys || Weight < BestWeight)
 925       BestPhys = PhysReg, BestWeight = Weight;
 926   }
 927
 928   // No candidates found.
 929   if (!BestPhys)
 930     return 0;
 931
 932   // Collect all interfering registers.
 933   SmallVector<LiveInterval*, 8> Spills;
 934   for (const unsigned *AI = TRI->getOverlaps(BestPhys); *AI; ++AI) {
 935     LiveIntervalUnion::Query &Q = query(VirtReg, *AI);
 936     Spills.append(Q.interferingVRegs().begin(), Q.interferingVRegs().end());
 937     for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) {
 938       LiveInterval *VReg = Q.interferingVRegs()[i];
 939       PhysReg2LiveUnion[*AI].extract(*VReg);
 940       VRM->clearVirt(VReg->reg);
 941     }
 942   }
 943
 944   // Spill them all.
 945   DEBUG(dbgs() << "spilling " << Spills.size() << " interferences with weight "
 946                << BestWeight << '\n');
 947   for (unsigned i = 0, e = Spills.size(); i != e; ++i)
 948     spiller().spill(Spills[i], NewVRegs, Spills);
 949   return BestPhys;
 950 }
 951
 952
 953 //===----------------------------------------------------------------------===//
 954 //                            Main Entry Point
 955 //===----------------------------------------------------------------------===//
 956
 957 unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg,
 958                                  SmallVectorImpl<LiveInterval*> &NewVRegs) {
 959   // First try assigning a free register.
 960   AllocationOrder Order(VirtReg.reg, *VRM, ReservedRegs);
 961   while (unsigned PhysReg = Order.next()) {
 962     if (!checkPhysRegInterference(VirtReg, PhysReg))
 963       return PhysReg;
 964   }
 965
 966   // Try to reassign interferences.
 967   if (unsigned PhysReg = tryReassign(VirtReg, Order))
 968     return PhysReg;
 969
 970   assert(NewVRegs.empty() && "Cannot append to existing NewVRegs");
 971
 972   // Try splitting VirtReg or interferences.
 973   unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs);
 974   if (PhysReg || !NewVRegs.empty())
 975     return PhysReg;
 976
 977   // Try to spill another interfering reg with less spill weight.
 978   PhysReg = trySpillInterferences(VirtReg, Order, NewVRegs);
 979   if (PhysReg)
 980     return PhysReg;
 981
 982   // Finally spill VirtReg itself.
 983   NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled);
 984   SmallVector<LiveInterval*, 1> pendingSpills;
 985   spiller().spill(&VirtReg, NewVRegs, pendingSpills);
 986
 987   // The live virtual register requesting allocation was spilled, so tell
 988   // the caller not to allocate anything during this round.
 989   return 0;
 990 }
 991
 992 bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
 993   DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n"
 994                << "********** Function: "
 995                << ((Value*)mf.getFunction())->getName() << '\n');
 996
 997   MF = &mf;
 998   if (VerifyEnabled)
 999     MF->verify(this, "Before greedy register allocator");
1000
1001   RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>());
1002   Indexes = &getAnalysis<SlotIndexes>();
1003   DomTree = &getAnalysis<MachineDominatorTree>();
1004   ReservedRegs = TRI->getReservedRegs(*MF);
1005   SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
1006   Loops = &getAnalysis<MachineLoopInfo>();
1007   LoopRanges = &getAnalysis<MachineLoopRanges>();
1008   Bundles = &getAnalysis<EdgeBundles>();
1009   SpillPlacer = &getAnalysis<SpillPlacement>();
1010
1011   SA.reset(new SplitAnalysis(*MF, *LIS, *Loops));
1012
1013   allocatePhysRegs();
1014   addMBBLiveIns(MF);
1015
1016   // Run rewriter
1017   {
1018     NamedRegionTimer T("Rewriter", TimerGroupName, TimePassesIsEnabled);
1019     std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
1020     rewriter->runOnMachineFunction(*MF, *VRM, LIS);
1021   }
1022
1023   // The pass output is in VirtRegMap. Release all the transient data.
1024   releaseMemory();
1025
1026   return true;
1027 }