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     const 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 &VirtReg,
 123                                  SmallVectorImpl<LiveInterval*> &SplitVRegs);
 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   unsigned findInterferenceFreeReg(MachineLoopRange*,
 136                                    LiveInterval&, AllocationOrder&);
 137   float calcInterferenceWeight(LiveInterval&, unsigned);
 138   void calcLiveBlockInfo(LiveInterval&);
 139   float calcInterferenceInfo(LiveInterval&, unsigned);
 140   float calcGlobalSplitCost(const BitVector&);
 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 //                              Loop Splitting
 328 //===----------------------------------------------------------------------===//
 329
 330 /// findInterferenceFreeReg - Find a physical register in Order where Loop has
 331 /// no interferences with VirtReg.
 332 unsigned RAGreedy::findInterferenceFreeReg(MachineLoopRange *Loop,
 333                                            LiveInterval &VirtReg,
 334                                            AllocationOrder &Order) {
 335   Order.rewind();
 336   while (unsigned PhysReg = Order.next()) {
 337     bool interference = false;
 338     for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
 339       if (query(VirtReg, *AI).checkLoopInterference(Loop)) {
 340         interference = true;
 341         break;
 342       }
 343     }
 344     if (!interference)
 345       return PhysReg;
 346   }
 347   // No physreg found.
 348   return 0;
 349 }
 350
 351 /// trySplit - Try to split VirtReg or one of its interferences, making it
 352 /// assignable.
 353 /// @return Physreg when VirtReg may be assigned and/or new SplitVRegs.
 354 unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order,
 355                             SmallVectorImpl<LiveInterval*>&SplitVRegs) {
 356   // Don't attempt splitting on local intervals for now.
 357   if (LIS->intervalIsInOneMBB(VirtReg))
 358     return 0;
 359
 360   NamedRegionTimer T("Splitter", TimerGroupName, TimePassesIsEnabled);
 361   SA->analyze(&VirtReg);
 362
 363   // Get the set of loops that have VirtReg uses and are splittable.
 364   SplitAnalysis::LoopPtrSet SplitLoopSet;
 365   SA->getSplitLoops(SplitLoopSet);
 366
 367   // Order loops by descending area.
 368   SmallVector<MachineLoopRange*, 8> SplitLoops;
 369   for (SplitAnalysis::LoopPtrSet::const_iterator I = SplitLoopSet.begin(),
 370          E = SplitLoopSet.end(); I != E; ++I)
 371     SplitLoops.push_back(LoopRanges->getLoopRange(*I));
 372   array_pod_sort(SplitLoops.begin(), SplitLoops.end(),
 373                  MachineLoopRange::byAreaDesc);
 374
 375   // Find the first loop that is interference-free for some register in the
 376   // allocation order.
 377   MachineLoopRange *Loop = 0;
 378   for (unsigned i = 0, e = SplitLoops.size(); i != e; ++i) {
 379     DEBUG(dbgs() << "  Checking " << *SplitLoops[i]);
 380     if (unsigned PhysReg = findInterferenceFreeReg(SplitLoops[i],
 381                                                    VirtReg, Order)) {
 382       (void)PhysReg;
 383       Loop = SplitLoops[i];
 384       DEBUG(dbgs() << ": Use %" << TRI->getName(PhysReg) << '\n');
 385       break;
 386     } else {
 387       DEBUG(dbgs() << ": Interference.\n");
 388     }
 389   }
 390
 391   if (!Loop) {
 392     DEBUG(dbgs() << "  All candidate loops have interference.\n");
 393     return 0;
 394   }
 395
 396   // Execute the split around Loop.
 397   SmallVector<LiveInterval*, 4> SpillRegs;
 398   LiveRangeEdit LREdit(VirtReg, SplitVRegs, SpillRegs);
 399   SplitEditor(*SA, *LIS, *VRM, *DomTree, LREdit)
 400     .splitAroundLoop(Loop->getLoop());
 401
 402   if (VerifyEnabled)
 403     MF->verify(this, "After splitting live range around loop");
 404
 405   // We have new split regs, don't assign anything.
 406   return 0;
 407 }
 408
 409
 410 //===----------------------------------------------------------------------===//
 411 //                              Region Splitting
 412 //===----------------------------------------------------------------------===//
 413
 414 /// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks
 415 /// where VirtReg is live.
 416 /// The SpillConstraints array is minimally initialized with MBB->getNumber().
 417 void RAGreedy::calcLiveBlockInfo(LiveInterval &VirtReg) {
 418   LiveBlocks.clear();
 419   SpillConstraints.clear();
 420
 421   assert(!VirtReg.empty() && "Cannot allocate an empty interval");
 422   LiveInterval::const_iterator LVI = VirtReg.begin();
 423   LiveInterval::const_iterator LVE = VirtReg.end();
 424
 425   SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE;
 426   UseI = SA->UseSlots.begin();
 427   UseE = SA->UseSlots.end();
 428
 429   // Loop over basic blocks where VirtReg is live.
 430   MachineFunction::const_iterator MFI = Indexes->getMBBFromIndex(LVI->start);
 431   for (;;) {
 432     // Block constraints depend on the interference pattern.
 433     // Just allocate them here, don't compute anything.
 434     SpillPlacement::BlockConstraint BC;
 435     BC.Number = MFI->getNumber();
 436     SpillConstraints.push_back(BC);
 437
 438     BlockInfo BI;
 439     BI.MBB = MFI;
 440     SlotIndex Start, Stop;
 441     tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
 442
 443     // LVI is the first live segment overlapping MBB.
 444     BI.LiveIn = LVI->start <= Start;
 445     if (!BI.LiveIn)
 446       BI.Def = LVI->start;
 447
 448     // Find the first and last uses in the block.
 449     BI.Uses = SA->hasUses(MFI);
 450     if (BI.Uses && UseI != UseE) {
 451       BI.FirstUse = *UseI;
 452       assert(BI.FirstUse >= Start);
 453       do ++UseI;
 454       while (UseI != UseE && *UseI < Stop);
 455       BI.LastUse = UseI[-1];
 456       assert(BI.LastUse < Stop);
 457     }
 458
 459     // Look for gaps in the live range.
 460     bool hasGap = false;
 461     BI.LiveOut = true;
 462     while (LVI->end < Stop) {
 463       SlotIndex LastStop = LVI->end;
 464       if (++LVI == LVE || LVI->start >= Stop) {
 465         BI.Kill = LastStop;
 466         BI.LiveOut = false;
 467         break;
 468       }
 469       if (LastStop < LVI->start) {
 470         hasGap = true;
 471         BI.Kill = LastStop;
 472         BI.Def = LVI->start;
 473       }
 474     }
 475
 476     // Don't set LiveThrough when the block has a gap.
 477     BI.LiveThrough = !hasGap && BI.LiveIn && BI.LiveOut;
 478     LiveBlocks.push_back(BI);
 479
 480     // LVI is now at LVE or LVI->end >= Stop.
 481     if (LVI == LVE)
 482       break;
 483
 484     // Live segment ends exactly at Stop. Move to the next segment.
 485     if (LVI->end == Stop && ++LVI == LVE)
 486       break;
 487
 488     // Pick the next basic block.
 489     if (LVI->start < Stop)
 490       ++MFI;
 491     else
 492       MFI = Indexes->getMBBFromIndex(LVI->start);
 493   }
 494 }
 495
 496 /// calcInterferenceInfo - Compute per-block outgoing and ingoing constraints
 497 /// when considering interference from PhysReg. Also compute an optimistic local
 498 /// cost of this interference pattern.
 499 ///
 500 /// The final cost of a split is the local cost + global cost of preferences
 501 /// broken by SpillPlacement.
 502 ///
 503 float RAGreedy::calcInterferenceInfo(LiveInterval &VirtReg, unsigned PhysReg) {
 504   // Reset interference dependent info.
 505   for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
 506     BlockInfo &BI = LiveBlocks[i];
 507     SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
 508     BC.Entry = (BI.Uses && BI.LiveIn) ?
 509       SpillPlacement::PrefReg : SpillPlacement::DontCare;
 510     BC.Exit = (BI.Uses && BI.LiveOut) ?
 511       SpillPlacement::PrefReg : SpillPlacement::DontCare;
 512     BI.OverlapEntry = BI.OverlapExit = false;
 513   }
 514
 515   // Add interference info from each PhysReg alias.
 516   for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
 517     if (!query(VirtReg, *AI).checkInterference())
 518       continue;
 519     DEBUG(PhysReg2LiveUnion[*AI].print(dbgs(), TRI));
 520     LiveIntervalUnion::SegmentIter IntI =
 521       PhysReg2LiveUnion[*AI].find(VirtReg.beginIndex());
 522     if (!IntI.valid())
 523       continue;
 524
 525     for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
 526       BlockInfo &BI = LiveBlocks[i];
 527       SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
 528       SlotIndex Start, Stop;
 529       tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
 530
 531       // Skip interference-free blocks.
 532       if (IntI.start() >= Stop)
 533         continue;
 534
 535       // Handle transparent blocks with interference separately.
 536       // Transparent blocks never incur any fixed cost.
 537       if (BI.LiveThrough && !BI.Uses) {
 538         // Check if interference is live-in - force spill.
 539         if (BC.Entry != SpillPlacement::MustSpill) {
 540           BC.Entry = SpillPlacement::PrefSpill;
 541           IntI.advanceTo(Start);
 542           if (IntI.valid() && IntI.start() <= Start)
 543             BC.Entry = SpillPlacement::MustSpill;
 544         }
 545
 546         // Check if interference is live-out - force spill.
 547         if (BC.Exit != SpillPlacement::MustSpill) {
 548           BC.Exit = SpillPlacement::PrefSpill;
 549           IntI.advanceTo(Stop);
 550           if (IntI.valid() && IntI.start() < Stop)
 551             BC.Exit = SpillPlacement::MustSpill;
 552         }
 553
 554         // Nothing more to do for this transparent block.
 555         if (!IntI.valid())
 556           break;
 557         continue;
 558       }
 559
 560       // Now we only have blocks with uses left.
 561       // Check if the interference overlaps the uses.
 562       assert(BI.Uses && "Non-transparent block without any uses");
 563
 564       // Check interference on entry.
 565       if (BI.LiveIn && BC.Entry != SpillPlacement::MustSpill) {
 566         IntI.advanceTo(Start);
 567         if (!IntI.valid())
 568           break;
 569
 570         // Interference is live-in - force spill.
 571         if (IntI.start() <= Start)
 572           BC.Entry = SpillPlacement::MustSpill;
 573         // Not live in, but before the first use.
 574         else if (IntI.start() < BI.FirstUse)
 575           BC.Entry = SpillPlacement::PrefSpill;
 576       }
 577
 578       // Does interference overlap the uses in the entry segment
 579       // [FirstUse;Kill)?
 580       if (BI.LiveIn && !BI.OverlapEntry) {
 581         IntI.advanceTo(BI.FirstUse);
 582         if (!IntI.valid())
 583           break;
 584         // A live-through interval has no kill.
 585         // Check [FirstUse;LastUse) instead.
 586         if (IntI.start() < (BI.LiveThrough ? BI.LastUse : BI.Kill))
 587           BI.OverlapEntry = true;
 588       }
 589
 590       // Does interference overlap the uses in the exit segment [Def;LastUse)?
 591       if (BI.LiveOut && !BI.LiveThrough && !BI.OverlapExit) {
 592         IntI.advanceTo(BI.Def);
 593         if (!IntI.valid())
 594           break;
 595         if (IntI.start() < BI.LastUse)
 596           BI.OverlapExit = true;
 597       }
 598
 599       // Check interference on exit.
 600       if (BI.LiveOut && BC.Exit != SpillPlacement::MustSpill) {
 601         // Check interference between LastUse and Stop.
 602         if (BC.Exit != SpillPlacement::PrefSpill) {
 603           IntI.advanceTo(BI.LastUse);
 604           if (!IntI.valid())
 605             break;
 606           if (IntI.start() < Stop)
 607             BC.Exit = SpillPlacement::PrefSpill;
 608         }
 609         // Is the interference live-out?
 610         IntI.advanceTo(Stop);
 611         if (!IntI.valid())
 612           break;
 613         if (IntI.start() < Stop)
 614           BC.Exit = SpillPlacement::MustSpill;
 615       }
 616     }
 617   }
 618
 619   // Accumulate a local cost of this interference pattern.
 620   float LocalCost = 0;
 621   for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
 622     BlockInfo &BI = LiveBlocks[i];
 623     if (!BI.Uses)
 624       continue;
 625     SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
 626     unsigned Inserts = 0;
 627
 628     // Do we need spill code for the entry segment?
 629     if (BI.LiveIn)
 630       Inserts += BI.OverlapEntry || BC.Entry != SpillPlacement::PrefReg;
 631
 632     // For the exit segment?
 633     if (BI.LiveOut)
 634       Inserts += BI.OverlapExit || BC.Exit != SpillPlacement::PrefReg;
 635
 636     // The local cost of spill code in this block is the block frequency times
 637     // the number of spill instructions inserted.
 638     if (Inserts)
 639       LocalCost += Inserts * SpillPlacer->getBlockFrequency(BI.MBB);
 640   }
 641   DEBUG(dbgs() << "Local cost of " << PrintReg(PhysReg, TRI) << " = "
 642                << LocalCost << '\n');
 643   return LocalCost;
 644 }
 645
 646 /// calcGlobalSplitCost - Return the global split cost of following the split
 647 /// pattern in LiveBundles. This cost should be added to the local cost of the
 648 /// interference pattern in SpillConstraints.
 649 ///
 650 float RAGreedy::calcGlobalSplitCost(const BitVector &LiveBundles) {
 651   float GlobalCost = 0;
 652   for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
 653     SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
 654     unsigned Inserts = 0;
 655     // Broken entry preference?
 656     Inserts += LiveBundles[Bundles->getBundle(BC.Number, 0)] !=
 657                  (BC.Entry == SpillPlacement::PrefReg);
 658     // Broken exit preference?
 659     Inserts += LiveBundles[Bundles->getBundle(BC.Number, 1)] !=
 660                  (BC.Exit == SpillPlacement::PrefReg);
 661     if (Inserts)
 662       GlobalCost += Inserts * SpillPlacer->getBlockFrequency(LiveBlocks[i].MBB);
 663   }
 664   DEBUG(dbgs() << "Global cost = " << GlobalCost << '\n');
 665   return GlobalCost;
 666 }
 667
 668 unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
 669                                   SmallVectorImpl<LiveInterval*> &NewVRegs) {
 670   calcLiveBlockInfo(VirtReg);
 671   BitVector LiveBundles, BestBundles;
 672   float BestCost = 0;
 673   unsigned BestReg = 0;
 674   Order.rewind();
 675   while (unsigned PhysReg = Order.next()) {
 676     float Cost = calcInterferenceInfo(VirtReg, PhysReg);
 677     if (BestReg && Cost >= BestCost)
 678       continue;
 679     if (!SpillPlacer->placeSpills(SpillConstraints, LiveBundles))
 680       Cost += calcGlobalSplitCost(LiveBundles);
 681     if (!BestReg || Cost < BestCost) {
 682       BestReg = PhysReg;
 683       BestCost = Cost;
 684       BestBundles.swap(LiveBundles);
 685     }
 686   }
 687   // FIXME: Actually execute the split.
 688   return 0;
 689 }
 690
 691 //===----------------------------------------------------------------------===//
 692 //                                Spilling
 693 //===----------------------------------------------------------------------===//
 694
 695 /// calcInterferenceWeight - Calculate the combined spill weight of
 696 /// interferences when assigning VirtReg to PhysReg.
 697 float RAGreedy::calcInterferenceWeight(LiveInterval &VirtReg, unsigned PhysReg){
 698   float Sum = 0;
 699   for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
 700     LiveIntervalUnion::Query &Q = query(VirtReg, *AI);
 701     Q.collectInterferingVRegs();
 702     if (Q.seenUnspillableVReg())
 703       return HUGE_VALF;
 704     for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i)
 705       Sum += Q.interferingVRegs()[i]->weight;
 706   }
 707   return Sum;
 708 }
 709
 710 /// trySpillInterferences - Try to spill interfering registers instead of the
 711 /// current one. Only do it if the accumulated spill weight is smaller than the
 712 /// current spill weight.
 713 unsigned RAGreedy::trySpillInterferences(LiveInterval &VirtReg,
 714                                          AllocationOrder &Order,
 715                                      SmallVectorImpl<LiveInterval*> &NewVRegs) {
 716   NamedRegionTimer T("Spill Interference", TimerGroupName, TimePassesIsEnabled);
 717   unsigned BestPhys = 0;
 718   float BestWeight = 0;
 719
 720   Order.rewind();
 721   while (unsigned PhysReg = Order.next()) {
 722     float Weight = calcInterferenceWeight(VirtReg, PhysReg);
 723     if (Weight == HUGE_VALF || Weight >= VirtReg.weight)
 724       continue;
 725     if (!BestPhys || Weight < BestWeight)
 726       BestPhys = PhysReg, BestWeight = Weight;
 727   }
 728
 729   // No candidates found.
 730   if (!BestPhys)
 731     return 0;
 732
 733   // Collect all interfering registers.
 734   SmallVector<LiveInterval*, 8> Spills;
 735   for (const unsigned *AI = TRI->getOverlaps(BestPhys); *AI; ++AI) {
 736     LiveIntervalUnion::Query &Q = query(VirtReg, *AI);
 737     Spills.append(Q.interferingVRegs().begin(), Q.interferingVRegs().end());
 738     for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) {
 739       LiveInterval *VReg = Q.interferingVRegs()[i];
 740       PhysReg2LiveUnion[*AI].extract(*VReg);
 741       VRM->clearVirt(VReg->reg);
 742     }
 743   }
 744
 745   // Spill them all.
 746   DEBUG(dbgs() << "spilling " << Spills.size() << " interferences with weight "
 747                << BestWeight << '\n');
 748   for (unsigned i = 0, e = Spills.size(); i != e; ++i)
 749     spiller().spill(Spills[i], NewVRegs, Spills);
 750   return BestPhys;
 751 }
 752
 753
 754 //===----------------------------------------------------------------------===//
 755 //                            Main Entry Point
 756 //===----------------------------------------------------------------------===//
 757
 758 unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg,
 759                                  SmallVectorImpl<LiveInterval*> &SplitVRegs) {
 760   // First try assigning a free register.
 761   AllocationOrder Order(VirtReg.reg, *VRM, ReservedRegs);
 762   while (unsigned PhysReg = Order.next()) {
 763     if (!checkPhysRegInterference(VirtReg, PhysReg))
 764       return PhysReg;
 765   }
 766
 767   // Try to reassign interferences.
 768   if (unsigned PhysReg = tryReassign(VirtReg, Order))
 769     return PhysReg;
 770
 771   // Try splitting VirtReg or interferences.
 772   unsigned PhysReg = trySplit(VirtReg, Order, SplitVRegs);
 773   if (PhysReg || !SplitVRegs.empty())
 774     return PhysReg;
 775
 776   // Try to spill another interfering reg with less spill weight.
 777   PhysReg = trySpillInterferences(VirtReg, Order, SplitVRegs);
 778   if (PhysReg)
 779     return PhysReg;
 780
 781   // Finally spill VirtReg itself.
 782   NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled);
 783   SmallVector<LiveInterval*, 1> pendingSpills;
 784   spiller().spill(&VirtReg, SplitVRegs, pendingSpills);
 785
 786   // The live virtual register requesting allocation was spilled, so tell
 787   // the caller not to allocate anything during this round.
 788   return 0;
 789 }
 790
 791 bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
 792   DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n"
 793                << "********** Function: "
 794                << ((Value*)mf.getFunction())->getName() << '\n');
 795
 796   MF = &mf;
 797   if (VerifyEnabled)
 798     MF->verify(this, "Before greedy register allocator");
 799
 800   RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>());
 801   Indexes = &getAnalysis<SlotIndexes>();
 802   DomTree = &getAnalysis<MachineDominatorTree>();
 803   ReservedRegs = TRI->getReservedRegs(*MF);
 804   SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
 805   Loops = &getAnalysis<MachineLoopInfo>();
 806   LoopRanges = &getAnalysis<MachineLoopRanges>();
 807   Bundles = &getAnalysis<EdgeBundles>();
 808   SpillPlacer = &getAnalysis<SpillPlacement>();
 809
 810   SA.reset(new SplitAnalysis(*MF, *LIS, *Loops));
 811
 812   allocatePhysRegs();
 813   addMBBLiveIns(MF);
 814
 815   // Run rewriter
 816   {
 817     NamedRegionTimer T("Rewriter", TimerGroupName, TimePassesIsEnabled);
 818     std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
 819     rewriter->runOnMachineFunction(*MF, *VRM, LIS);
 820   }
 821
 822   // The pass output is in VirtRegMap. Release all the transient data.
 823   releaseMemory();
 824
 825   return true;
 826 }