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 (!IP.first.isValid() || IntI.start() < IP.first)
 630           IP.first = IntI.start();
 631       }
 632
 633       // Last interference in block.
 634       if (BI.LiveOut) {
 635         IntI.advanceTo(Stop);
 636         if (!IntI.valid() || IntI.start() >= Stop)
 637           --IntI;
 638         if (!IP.second.isValid() || IntI.stop() > IP.second)
 639           IP.second = IntI.stop();
 640       }
 641     }
 642   }
 643
 644   SmallVector<LiveInterval*, 4> SpillRegs;
 645   LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs);
 646   SplitEditor SE(*SA, *LIS, *VRM, *DomTree, LREdit);
 647
 648   // Ranges to add to the register interval after all defs are in place.
 649   SmallVector<IndexPair, 8> UseRanges;
 650
 651   // Create the main cross-block interval.
 652   SE.openIntv();
 653
 654   // First add all defs that are live out of a block.
 655   for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
 656     BlockInfo &BI = LiveBlocks[i];
 657     bool RegIn  = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)];
 658     bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)];
 659
 660     // Should the register be live out?
 661     if (!BI.LiveOut || !RegOut)
 662       continue;
 663
 664     IndexPair &IP = InterferenceRanges[i];
 665     SlotIndex Start, Stop;
 666     tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
 667
 668     DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " -> EB#"
 669                  << Bundles->getBundle(BI.MBB->getNumber(), 1));
 670
 671     // Check interference leaving the block.
 672     if (!IP.second.isValid() || IP.second < Start) {
 673       // Block is interference-free.
 674       DEBUG(dbgs() << ", no interference");
 675       if (!BI.Uses) {
 676         assert(BI.LiveThrough && "No uses, but not live through block?");
 677         // Block is live-through without interference.
 678         DEBUG(dbgs() << ", no uses"
 679                      << (RegIn ? ", live-through.\n" : ", stack in.\n"));
 680         if (!RegIn)
 681           SE.enterIntvAtEnd(*BI.MBB);
 682         continue;
 683       }
 684       if (!BI.LiveThrough) {
 685         DEBUG(dbgs() << ", not live-through.\n");
 686         SE.enterIntvBefore(BI.Def);
 687         UseRanges.push_back(IndexPair(BI.Def, Stop));
 688         continue;
 689       }
 690       if (!RegIn) {
 691         // Block is live-through, but entry bundle is on the stack.
 692         // Reload just before the first use.
 693         DEBUG(dbgs() << ", not live-in, enter before first use.\n");
 694         SE.enterIntvBefore(BI.FirstUse);
 695         UseRanges.push_back(IndexPair(BI.FirstUse, Stop));
 696         continue;
 697       }
 698       DEBUG(dbgs() << ", live-through.\n");
 699       continue;
 700     }
 701
 702     // Block has interference.
 703     DEBUG(dbgs() << ", interference to " << IP.second);
 704     if (!BI.Uses) {
 705       // No uses in block, avoid interference by reloading as late as possible.
 706       DEBUG(dbgs() << ", no uses.\n");
 707       SE.enterIntvAtEnd(*BI.MBB);
 708       continue;
 709     }
 710     if (IP.second < BI.LastUse) {
 711       // There are interference-free uses at the end of the block.
 712       // Find the first use that can get the live-out register.
 713       SmallVectorImpl<SlotIndex>::const_iterator UI =
 714         std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(), IP.second);
 715       assert(UI != SA->UseSlots.end() && "Couldn't find last use");
 716       SlotIndex Use = *UI;
 717       DEBUG(dbgs() << ", free use at " << Use << ".\n");
 718       assert(Use <= BI.LastUse && "Couldn't find last use");
 719       SE.enterIntvBefore(Use);
 720       UseRanges.push_back(IndexPair(Use, Stop));
 721       continue;
 722     }
 723
 724     // Interference is after the last use.
 725     DEBUG(dbgs() << " after last use.\n");
 726     SE.enterIntvAtEnd(*BI.MBB);
 727   }
 728
 729   // Add the live-out ranges following the defs.
 730   // We must wait until all defs have been inserted, otherwise SplitKit gets
 731   // confused about the value mapping.
 732   for (unsigned i = 0, e = UseRanges.size(); i != e; ++i)
 733     SE.useIntv(UseRanges[i].first, UseRanges[i].second);
 734
 735   // Now all defs leading to live bundles are handled, do everything else.
 736   for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
 737     BlockInfo &BI = LiveBlocks[i];
 738     bool RegIn  = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)];
 739     bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)];
 740
 741     // Is the register live-in?
 742     if (!BI.LiveIn || !RegIn)
 743       continue;
 744
 745     // We have an incoming register. Check for interference.
 746     IndexPair &IP = InterferenceRanges[i];
 747     SlotIndex Start, Stop;
 748     tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
 749
 750     DEBUG(dbgs() << "EB#" << Bundles->getBundle(BI.MBB->getNumber(), 0)
 751                  << " -> BB#" << BI.MBB->getNumber());
 752
 753     // Check interference entering the block.
 754     if (!IP.first.isValid() || IP.first > Stop) {
 755       // Block is interference-free.
 756       DEBUG(dbgs() << ", no interference");
 757       if (!BI.Uses) {
 758         assert(BI.LiveThrough && "No uses, but not live through block?");
 759         // Block is live-through without interference.
 760         if (RegOut) {
 761           DEBUG(dbgs() << ", no uses, live-through.\n");
 762           SE.useIntv(Start, Stop);
 763         } else {
 764           DEBUG(dbgs() << ", no uses, stack-out.\n");
 765           SE.leaveIntvAtTop(*BI.MBB);
 766         }
 767         continue;
 768       }
 769       if (!BI.LiveThrough) {
 770         DEBUG(dbgs() << ", killed in block.\n");
 771         SE.useIntv(Start, BI.Kill.getBoundaryIndex());
 772         SE.leaveIntvAfter(BI.Kill);
 773         continue;
 774       }
 775       if (!RegOut) {
 776         // Block is live-through, but exit bundle is on the stack.
 777         // Spill immediately after the last use.
 778         DEBUG(dbgs() << ", uses, stack-out.\n");
 779         SE.useIntv(Start, BI.LastUse.getBoundaryIndex());
 780         SE.leaveIntvAfter(BI.LastUse);
 781         continue;
 782       }
 783       // Register is live-through.
 784       DEBUG(dbgs() << ", uses, live-through.\n");
 785       SE.useIntv(Start, Stop);
 786       continue;
 787     }
 788
 789     // Block has interference.
 790     DEBUG(dbgs() << ", interference from " << IP.first);
 791     if (!BI.Uses) {
 792       // No uses in block, avoid interference by spilling as soon as possible.
 793       DEBUG(dbgs() << ", no uses.\n");
 794       SE.leaveIntvAtTop(*BI.MBB);
 795       continue;
 796     }
 797     if (IP.first > BI.FirstUse) {
 798       // There are interference-free uses at the beginning of the block.
 799       // Find the last use that can get the register.
 800       SmallVectorImpl<SlotIndex>::const_iterator UI =
 801         std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(), IP.first);
 802       assert(UI != SA->UseSlots.begin() && "Couldn't find first use");
 803       SlotIndex Use = (--UI)->getBoundaryIndex();
 804       DEBUG(dbgs() << ", free use at " << *UI << ".\n");
 805       assert(Use >= BI.FirstUse && Use < IP.first);
 806       SE.useIntv(Start, Use);
 807       SE.leaveIntvAfter(Use);
 808       continue;
 809     }
 810
 811     // Interference is before the first use.
 812     DEBUG(dbgs() << " before first use.\n");
 813     SE.leaveIntvAtTop(*BI.MBB);
 814   }
 815
 816   SE.closeIntv();
 817
 818   // FIXME: Should we be more aggressive about splitting the stack region into
 819   // per-block segments? The current approach allows the stack region to
 820   // separate into connected components. Some components may be allocatable.
 821   SE.finish();
 822
 823   if (VerifyEnabled)
 824     MF->verify(this, "After splitting live range around region");
 825 }
 826
 827 unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
 828                                   SmallVectorImpl<LiveInterval*> &NewVRegs) {
 829   calcLiveBlockInfo(VirtReg);
 830   BitVector LiveBundles, BestBundles;
 831   float BestCost = 0;
 832   unsigned BestReg = 0;
 833   Order.rewind();
 834   while (unsigned PhysReg = Order.next()) {
 835     float Cost = calcInterferenceInfo(VirtReg, PhysReg);
 836     if (BestReg && Cost >= BestCost)
 837       continue;
 838
 839     SpillPlacer->placeSpills(SpillConstraints, LiveBundles);
 840     // No live bundles, defer to splitSingleBlocks().
 841     if (!LiveBundles.any())
 842       continue;
 843
 844     Cost += calcGlobalSplitCost(LiveBundles);
 845     if (!BestReg || Cost < BestCost) {
 846       BestReg = PhysReg;
 847       BestCost = Cost;
 848       BestBundles.swap(LiveBundles);
 849     }
 850   }
 851
 852   if (!BestReg)
 853     return 0;
 854
 855   splitAroundRegion(VirtReg, BestReg, BestBundles, NewVRegs);
 856   return 0;
 857 }
 858
 859
 860 //===----------------------------------------------------------------------===//
 861 //                          Live Range Splitting
 862 //===----------------------------------------------------------------------===//
 863
 864 /// trySplit - Try to split VirtReg or one of its interferences, making it
 865 /// assignable.
 866 /// @return Physreg when VirtReg may be assigned and/or new NewVRegs.
 867 unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order,
 868                             SmallVectorImpl<LiveInterval*>&NewVRegs) {
 869   NamedRegionTimer T("Splitter", TimerGroupName, TimePassesIsEnabled);
 870   SA->analyze(&VirtReg);
 871
 872   // Don't attempt splitting on local intervals for now. TBD.
 873   if (LIS->intervalIsInOneMBB(VirtReg))
 874     return 0;
 875
 876   // First try to split around a region spanning multiple blocks.
 877   unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs);
 878   if (PhysReg || !NewVRegs.empty())
 879     return PhysReg;
 880
 881   // Then isolate blocks with multiple uses.
 882   SplitAnalysis::BlockPtrSet Blocks;
 883   if (SA->getMultiUseBlocks(Blocks)) {
 884     SmallVector<LiveInterval*, 4> SpillRegs;
 885     LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs);
 886     SplitEditor(*SA, *LIS, *VRM, *DomTree, LREdit).splitSingleBlocks(Blocks);
 887   }
 888
 889   // Don't assign any physregs.
 890   return 0;
 891 }
 892
 893
 894 //===----------------------------------------------------------------------===//
 895 //                                Spilling
 896 //===----------------------------------------------------------------------===//
 897
 898 /// calcInterferenceWeight - Calculate the combined spill weight of
 899 /// interferences when assigning VirtReg to PhysReg.
 900 float RAGreedy::calcInterferenceWeight(LiveInterval &VirtReg, unsigned PhysReg){
 901   float Sum = 0;
 902   for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
 903     LiveIntervalUnion::Query &Q = query(VirtReg, *AI);
 904     Q.collectInterferingVRegs();
 905     if (Q.seenUnspillableVReg())
 906       return HUGE_VALF;
 907     for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i)
 908       Sum += Q.interferingVRegs()[i]->weight;
 909   }
 910   return Sum;
 911 }
 912
 913 /// trySpillInterferences - Try to spill interfering registers instead of the
 914 /// current one. Only do it if the accumulated spill weight is smaller than the
 915 /// current spill weight.
 916 unsigned RAGreedy::trySpillInterferences(LiveInterval &VirtReg,
 917                                          AllocationOrder &Order,
 918                                      SmallVectorImpl<LiveInterval*> &NewVRegs) {
 919   NamedRegionTimer T("Spill Interference", TimerGroupName, TimePassesIsEnabled);
 920   unsigned BestPhys = 0;
 921   float BestWeight = 0;
 922
 923   Order.rewind();
 924   while (unsigned PhysReg = Order.next()) {
 925     float Weight = calcInterferenceWeight(VirtReg, PhysReg);
 926     if (Weight == HUGE_VALF || Weight >= VirtReg.weight)
 927       continue;
 928     if (!BestPhys || Weight < BestWeight)
 929       BestPhys = PhysReg, BestWeight = Weight;
 930   }
 931
 932   // No candidates found.
 933   if (!BestPhys)
 934     return 0;
 935
 936   // Collect all interfering registers.
 937   SmallVector<LiveInterval*, 8> Spills;
 938   for (const unsigned *AI = TRI->getOverlaps(BestPhys); *AI; ++AI) {
 939     LiveIntervalUnion::Query &Q = query(VirtReg, *AI);
 940     Spills.append(Q.interferingVRegs().begin(), Q.interferingVRegs().end());
 941     for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) {
 942       LiveInterval *VReg = Q.interferingVRegs()[i];
 943       PhysReg2LiveUnion[*AI].extract(*VReg);
 944       VRM->clearVirt(VReg->reg);
 945     }
 946   }
 947
 948   // Spill them all.
 949   DEBUG(dbgs() << "spilling " << Spills.size() << " interferences with weight "
 950                << BestWeight << '\n');
 951   for (unsigned i = 0, e = Spills.size(); i != e; ++i)
 952     spiller().spill(Spills[i], NewVRegs, Spills);
 953   return BestPhys;
 954 }
 955
 956
 957 //===----------------------------------------------------------------------===//
 958 //                            Main Entry Point
 959 //===----------------------------------------------------------------------===//
 960
 961 unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg,
 962                                  SmallVectorImpl<LiveInterval*> &NewVRegs) {
 963   // First try assigning a free register.
 964   AllocationOrder Order(VirtReg.reg, *VRM, ReservedRegs);
 965   while (unsigned PhysReg = Order.next()) {
 966     if (!checkPhysRegInterference(VirtReg, PhysReg))
 967       return PhysReg;
 968   }
 969
 970   // Try to reassign interferences.
 971   if (unsigned PhysReg = tryReassign(VirtReg, Order))
 972     return PhysReg;
 973
 974   assert(NewVRegs.empty() && "Cannot append to existing NewVRegs");
 975
 976   // Try splitting VirtReg or interferences.
 977   unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs);
 978   if (PhysReg || !NewVRegs.empty())
 979     return PhysReg;
 980
 981   // Try to spill another interfering reg with less spill weight.
 982   PhysReg = trySpillInterferences(VirtReg, Order, NewVRegs);
 983   if (PhysReg)
 984     return PhysReg;
 985
 986   // Finally spill VirtReg itself.
 987   NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled);
 988   SmallVector<LiveInterval*, 1> pendingSpills;
 989   spiller().spill(&VirtReg, NewVRegs, pendingSpills);
 990
 991   // The live virtual register requesting allocation was spilled, so tell
 992   // the caller not to allocate anything during this round.
 993   return 0;
 994 }
 995
 996 bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
 997   DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n"
 998                << "********** Function: "
 999                << ((Value*)mf.getFunction())->getName() << '\n');
1000
1001   MF = &mf;
1002   if (VerifyEnabled)
1003     MF->verify(this, "Before greedy register allocator");
1004
1005   RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>());
1006   Indexes = &getAnalysis<SlotIndexes>();
1007   DomTree = &getAnalysis<MachineDominatorTree>();
1008   ReservedRegs = TRI->getReservedRegs(*MF);
1009   SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
1010   Loops = &getAnalysis<MachineLoopInfo>();
1011   LoopRanges = &getAnalysis<MachineLoopRanges>();
1012   Bundles = &getAnalysis<EdgeBundles>();
1013   SpillPlacer = &getAnalysis<SpillPlacement>();
1014
1015   SA.reset(new SplitAnalysis(*MF, *LIS, *Loops));
1016
1017   allocatePhysRegs();
1018   addMBBLiveIns(MF);
1019
1020   // Run rewriter
1021   {
1022     NamedRegionTimer T("Rewriter", TimerGroupName, TimePassesIsEnabled);
1023     std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
1024     rewriter->runOnMachineFunction(*MF, *VRM, LIS);
1025   }
1026
1027   // The pass output is in VirtRegMap. Release all the transient data.
1028   releaseMemory();
1029
1030   return true;
1031 }