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 "InterferenceCache.h"
  18 #include "LiveDebugVariables.h"
  19 #include "LiveRangeEdit.h"
  20 #include "RegAllocBase.h"
  21 #include "Spiller.h"
  22 #include "SpillPlacement.h"
  23 #include "SplitKit.h"
  24 #include "VirtRegMap.h"
  25 #include "llvm/ADT/Statistic.h"
  26 #include "llvm/Analysis/AliasAnalysis.h"
  27 #include "llvm/Function.h"
  28 #include "llvm/PassAnalysisSupport.h"
  29 #include "llvm/CodeGen/CalcSpillWeights.h"
  30 #include "llvm/CodeGen/EdgeBundles.h"
  31 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  32 #include "llvm/CodeGen/LiveStackAnalysis.h"
  33 #include "llvm/CodeGen/MachineDominators.h"
  34 #include "llvm/CodeGen/MachineFunctionPass.h"
  35 #include "llvm/CodeGen/MachineLoopInfo.h"
  36 #include "llvm/CodeGen/MachineRegisterInfo.h"
  37 #include "llvm/CodeGen/Passes.h"
  38 #include "llvm/CodeGen/RegAllocRegistry.h"
  39 #include "llvm/Target/TargetOptions.h"
  40 #include "llvm/Support/CommandLine.h"
  41 #include "llvm/Support/Debug.h"
  42 #include "llvm/Support/ErrorHandling.h"
  43 #include "llvm/Support/raw_ostream.h"
  44 #include "llvm/Support/Timer.h"
  45
  46 #include <queue>
  47
  48 using namespace llvm;
  49
  50 STATISTIC(NumGlobalSplits, "Number of split global live ranges");
  51 STATISTIC(NumLocalSplits,  "Number of split local live ranges");
  52 STATISTIC(NumEvicted,      "Number of interferences evicted");
  53
  54 static cl::opt<SplitEditor::ComplementSpillMode>
  55 SplitSpillMode("split-spill-mode", cl::Hidden,
  56   cl::desc("Spill mode for splitting live ranges"),
  57   cl::values(clEnumValN(SplitEditor::SM_Partition, "default", "Default"),
  58              clEnumValN(SplitEditor::SM_Size,  "size",  "Optimize for size"),
  59              clEnumValN(SplitEditor::SM_Speed, "speed", "Optimize for speed"),
  60              clEnumValEnd),
  61   cl::init(SplitEditor::SM_Partition));
  62
  63 static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator",
  64                                        createGreedyRegisterAllocator);
  65
  66 namespace {
  67 class RAGreedy : public MachineFunctionPass,
  68                  public RegAllocBase,
  69                  private LiveRangeEdit::Delegate {
  70
  71   // context
  72   MachineFunction *MF;
  73
  74   // analyses
  75   SlotIndexes *Indexes;
  76   LiveStacks *LS;
  77   MachineDominatorTree *DomTree;
  78   MachineLoopInfo *Loops;
  79   EdgeBundles *Bundles;
  80   SpillPlacement *SpillPlacer;
  81   LiveDebugVariables *DebugVars;
  82
  83   // state
  84   std::auto_ptr<Spiller> SpillerInstance;
  85   std::priority_queue<std::pair<unsigned, unsigned> > Queue;
  86   unsigned NextCascade;
  87
  88   // Live ranges pass through a number of stages as we try to allocate them.
  89   // Some of the stages may also create new live ranges:
  90   //
  91   // - Region splitting.
  92   // - Per-block splitting.
  93   // - Local splitting.
  94   // - Spilling.
  95   //
  96   // Ranges produced by one of the stages skip the previous stages when they are
  97   // dequeued. This improves performance because we can skip interference checks
  98   // that are unlikely to give any results. It also guarantees that the live
  99   // range splitting algorithm terminates, something that is otherwise hard to
 100   // ensure.
 101   enum LiveRangeStage {
 102     /// Newly created live range that has never been queued.
 103     RS_New,
 104
 105     /// Only attempt assignment and eviction. Then requeue as RS_Split.
 106     RS_Assign,
 107
 108     /// Attempt live range splitting if assignment is impossible.
 109     RS_Split,
 110
 111     /// Attempt more aggressive live range splitting that is guaranteed to make
 112     /// progress.  This is used for split products that may not be making
 113     /// progress.
 114     RS_Split2,
 115
 116     /// Live range will be spilled.  No more splitting will be attempted.
 117     RS_Spill,
 118
 119     /// There is nothing more we can do to this live range.  Abort compilation
 120     /// if it can't be assigned.
 121     RS_Done
 122   };
 123
 124   static const char *const StageName[];
 125
 126   // RegInfo - Keep additional information about each live range.
 127   struct RegInfo {
 128     LiveRangeStage Stage;
 129
 130     // Cascade - Eviction loop prevention. See canEvictInterference().
 131     unsigned Cascade;
 132
 133     RegInfo() : Stage(RS_New), Cascade(0) {}
 134   };
 135
 136   IndexedMap<RegInfo, VirtReg2IndexFunctor> ExtraRegInfo;
 137
 138   LiveRangeStage getStage(const LiveInterval &VirtReg) const {
 139     return ExtraRegInfo[VirtReg.reg].Stage;
 140   }
 141
 142   void setStage(const LiveInterval &VirtReg, LiveRangeStage Stage) {
 143     ExtraRegInfo.resize(MRI->getNumVirtRegs());
 144     ExtraRegInfo[VirtReg.reg].Stage = Stage;
 145   }
 146
 147   template<typename Iterator>
 148   void setStage(Iterator Begin, Iterator End, LiveRangeStage NewStage) {
 149     ExtraRegInfo.resize(MRI->getNumVirtRegs());
 150     for (;Begin != End; ++Begin) {
 151       unsigned Reg = (*Begin)->reg;
 152       if (ExtraRegInfo[Reg].Stage == RS_New)
 153         ExtraRegInfo[Reg].Stage = NewStage;
 154     }
 155   }
 156
 157   /// Cost of evicting interference.
 158   struct EvictionCost {
 159     unsigned BrokenHints; ///< Total number of broken hints.
 160     float MaxWeight;      ///< Maximum spill weight evicted.
 161
 162     EvictionCost(unsigned B = 0) : BrokenHints(B), MaxWeight(0) {}
 163
 164     bool operator<(const EvictionCost &O) const {
 165       if (BrokenHints != O.BrokenHints)
 166         return BrokenHints < O.BrokenHints;
 167       return MaxWeight < O.MaxWeight;
 168     }
 169   };
 170
 171   // splitting state.
 172   std::auto_ptr<SplitAnalysis> SA;
 173   std::auto_ptr<SplitEditor> SE;
 174
 175   /// Cached per-block interference maps
 176   InterferenceCache IntfCache;
 177
 178   /// All basic blocks where the current register has uses.
 179   SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints;
 180
 181   /// Global live range splitting candidate info.
 182   struct GlobalSplitCandidate {
 183     // Register intended for assignment, or 0.
 184     unsigned PhysReg;
 185
 186     // SplitKit interval index for this candidate.
 187     unsigned IntvIdx;
 188
 189     // Interference for PhysReg.
 190     InterferenceCache::Cursor Intf;
 191
 192     // Bundles where this candidate should be live.
 193     BitVector LiveBundles;
 194     SmallVector<unsigned, 8> ActiveBlocks;
 195
 196     void reset(InterferenceCache &Cache, unsigned Reg) {
 197       PhysReg = Reg;
 198       IntvIdx = 0;
 199       Intf.setPhysReg(Cache, Reg);
 200       LiveBundles.clear();
 201       ActiveBlocks.clear();
 202     }
 203
 204     // Set B[i] = C for every live bundle where B[i] was NoCand.
 205     unsigned getBundles(SmallVectorImpl<unsigned> &B, unsigned C) {
 206       unsigned Count = 0;
 207       for (int i = LiveBundles.find_first(); i >= 0;
 208            i = LiveBundles.find_next(i))
 209         if (B[i] == NoCand) {
 210           B[i] = C;
 211           Count++;
 212         }
 213       return Count;
 214     }
 215   };
 216
 217   /// Candidate info for for each PhysReg in AllocationOrder.
 218   /// This vector never shrinks, but grows to the size of the largest register
 219   /// class.
 220   SmallVector<GlobalSplitCandidate, 32> GlobalCand;
 221
 222   enum { NoCand = ~0u };
 223
 224   /// Candidate map. Each edge bundle is assigned to a GlobalCand entry, or to
 225   /// NoCand which indicates the stack interval.
 226   SmallVector<unsigned, 32> BundleCand;
 227
 228 public:
 229   RAGreedy();
 230
 231   /// Return the pass name.
 232   virtual const char* getPassName() const {
 233     return "Greedy Register Allocator";
 234   }
 235
 236   /// RAGreedy analysis usage.
 237   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 238   virtual void releaseMemory();
 239   virtual Spiller &spiller() { return *SpillerInstance; }
 240   virtual void enqueue(LiveInterval *LI);
 241   virtual LiveInterval *dequeue();
 242   virtual unsigned selectOrSplit(LiveInterval&,
 243                                  SmallVectorImpl<LiveInterval*>&);
 244
 245   /// Perform register allocation.
 246   virtual bool runOnMachineFunction(MachineFunction &mf);
 247
 248   static char ID;
 249
 250 private:
 251   bool LRE_CanEraseVirtReg(unsigned);
 252   void LRE_WillShrinkVirtReg(unsigned);
 253   void LRE_DidCloneVirtReg(unsigned, unsigned);
 254
 255   float calcSpillCost();
 256   bool addSplitConstraints(InterferenceCache::Cursor, float&);
 257   void addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>);
 258   void growRegion(GlobalSplitCandidate &Cand);
 259   float calcGlobalSplitCost(GlobalSplitCandidate&);
 260   bool calcCompactRegion(GlobalSplitCandidate&);
 261   void splitAroundRegion(LiveRangeEdit&, ArrayRef<unsigned>);
 262   void calcGapWeights(unsigned, SmallVectorImpl<float>&);
 263   bool shouldEvict(LiveInterval &A, bool, LiveInterval &B, bool);
 264   bool canEvictInterference(LiveInterval&, unsigned, bool, EvictionCost&);
 265   void evictInterference(LiveInterval&, unsigned,
 266                          SmallVectorImpl<LiveInterval*>&);
 267
 268   unsigned tryAssign(LiveInterval&, AllocationOrder&,
 269                      SmallVectorImpl<LiveInterval*>&);
 270   unsigned tryEvict(LiveInterval&, AllocationOrder&,
 271                     SmallVectorImpl<LiveInterval*>&, unsigned = ~0u);
 272   unsigned tryRegionSplit(LiveInterval&, AllocationOrder&,
 273                           SmallVectorImpl<LiveInterval*>&);
 274   unsigned tryBlockSplit(LiveInterval&, AllocationOrder&,
 275                          SmallVectorImpl<LiveInterval*>&);
 276   unsigned tryLocalSplit(LiveInterval&, AllocationOrder&,
 277     SmallVectorImpl<LiveInterval*>&);
 278   unsigned trySplit(LiveInterval&, AllocationOrder&,
 279                     SmallVectorImpl<LiveInterval*>&);
 280 };
 281 } // end anonymous namespace
 282
 283 char RAGreedy::ID = 0;
 284
 285 #ifndef NDEBUG
 286 const char *const RAGreedy::StageName[] = {
 287     "RS_New",
 288     "RS_Assign",
 289     "RS_Split",
 290     "RS_Split2",
 291     "RS_Spill",
 292     "RS_Done"
 293 };
 294 #endif
 295
 296 // Hysteresis to use when comparing floats.
 297 // This helps stabilize decisions based on float comparisons.
 298 const float Hysteresis = 0.98f;
 299
 300
 301 FunctionPass* llvm::createGreedyRegisterAllocator() {
 302   return new RAGreedy();
 303 }
 304
 305 RAGreedy::RAGreedy(): MachineFunctionPass(ID) {
 306   initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry());
 307   initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
 308   initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
 309   initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
 310   initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
 311   initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry());
 312   initializeMachineSchedulerPassPass(*PassRegistry::getPassRegistry());
 313   initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
 314   initializeLiveStacksPass(*PassRegistry::getPassRegistry());
 315   initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
 316   initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
 317   initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
 318   initializeEdgeBundlesPass(*PassRegistry::getPassRegistry());
 319   initializeSpillPlacementPass(*PassRegistry::getPassRegistry());
 320 }
 321
 322 void RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const {
 323   AU.setPreservesCFG();
 324   AU.addRequired<AliasAnalysis>();
 325   AU.addPreserved<AliasAnalysis>();
 326   AU.addRequired<LiveIntervals>();
 327   AU.addRequired<SlotIndexes>();
 328   AU.addPreserved<SlotIndexes>();
 329   AU.addRequired<LiveDebugVariables>();
 330   AU.addPreserved<LiveDebugVariables>();
 331   if (StrongPHIElim)
 332     AU.addRequiredID(StrongPHIEliminationID);
 333   AU.addRequiredTransitiveID(RegisterCoalescerPassID);
 334   if (EnableMachineSched)
 335     AU.addRequiredID(MachineSchedulerPassID);
 336   AU.addRequired<CalculateSpillWeights>();
 337   AU.addRequired<LiveStacks>();
 338   AU.addPreserved<LiveStacks>();
 339   AU.addRequired<MachineDominatorTree>();
 340   AU.addPreserved<MachineDominatorTree>();
 341   AU.addRequired<MachineLoopInfo>();
 342   AU.addPreserved<MachineLoopInfo>();
 343   AU.addRequired<VirtRegMap>();
 344   AU.addPreserved<VirtRegMap>();
 345   AU.addRequired<EdgeBundles>();
 346   AU.addRequired<SpillPlacement>();
 347   MachineFunctionPass::getAnalysisUsage(AU);
 348 }
 349
 350
 351 //===----------------------------------------------------------------------===//
 352 //                     LiveRangeEdit delegate methods
 353 //===----------------------------------------------------------------------===//
 354
 355 bool RAGreedy::LRE_CanEraseVirtReg(unsigned VirtReg) {
 356   if (unsigned PhysReg = VRM->getPhys(VirtReg)) {
 357     unassign(LIS->getInterval(VirtReg), PhysReg);
 358     return true;
 359   }
 360   // Unassigned virtreg is probably in the priority queue.
 361   // RegAllocBase will erase it after dequeueing.
 362   return false;
 363 }
 364
 365 void RAGreedy::LRE_WillShrinkVirtReg(unsigned VirtReg) {
 366   unsigned PhysReg = VRM->getPhys(VirtReg);
 367   if (!PhysReg)
 368     return;
 369
 370   // Register is assigned, put it back on the queue for reassignment.
 371   LiveInterval &LI = LIS->getInterval(VirtReg);
 372   unassign(LI, PhysReg);
 373   enqueue(&LI);
 374 }
 375
 376 void RAGreedy::LRE_DidCloneVirtReg(unsigned New, unsigned Old) {
 377   // Cloning a register we haven't even heard about yet?  Just ignore it.
 378   if (!ExtraRegInfo.inBounds(Old))
 379     return;
 380
 381   // LRE may clone a virtual register because dead code elimination causes it to
 382   // be split into connected components. The new components are much smaller
 383   // than the original, so they should get a new chance at being assigned.
 384   // same stage as the parent.
 385   ExtraRegInfo[Old].Stage = RS_Assign;
 386   ExtraRegInfo.grow(New);
 387   ExtraRegInfo[New] = ExtraRegInfo[Old];
 388 }
 389
 390 void RAGreedy::releaseMemory() {
 391   SpillerInstance.reset(0);
 392   ExtraRegInfo.clear();
 393   GlobalCand.clear();
 394   RegAllocBase::releaseMemory();
 395 }
 396
 397 void RAGreedy::enqueue(LiveInterval *LI) {
 398   // Prioritize live ranges by size, assigning larger ranges first.
 399   // The queue holds (size, reg) pairs.
 400   const unsigned Size = LI->getSize();
 401   const unsigned Reg = LI->reg;
 402   assert(TargetRegisterInfo::isVirtualRegister(Reg) &&
 403          "Can only enqueue virtual registers");
 404   unsigned Prio;
 405
 406   ExtraRegInfo.grow(Reg);
 407   if (ExtraRegInfo[Reg].Stage == RS_New)
 408     ExtraRegInfo[Reg].Stage = RS_Assign;
 409
 410   if (ExtraRegInfo[Reg].Stage == RS_Split) {
 411     // Unsplit ranges that couldn't be allocated immediately are deferred until
 412     // everything else has been allocated.
 413     Prio = Size;
 414   } else {
 415     // Everything is allocated in long->short order. Long ranges that don't fit
 416     // should be spilled (or split) ASAP so they don't create interference.
 417     Prio = (1u << 31) + Size;
 418
 419     // Boost ranges that have a physical register hint.
 420     if (TargetRegisterInfo::isPhysicalRegister(VRM->getRegAllocPref(Reg)))
 421       Prio |= (1u << 30);
 422   }
 423
 424   Queue.push(std::make_pair(Prio, Reg));
 425 }
 426
 427 LiveInterval *RAGreedy::dequeue() {
 428   if (Queue.empty())
 429     return 0;
 430   LiveInterval *LI = &LIS->getInterval(Queue.top().second);
 431   Queue.pop();
 432   return LI;
 433 }
 434
 435
 436 //===----------------------------------------------------------------------===//
 437 //                            Direct Assignment
 438 //===----------------------------------------------------------------------===//
 439
 440 /// tryAssign - Try to assign VirtReg to an available register.
 441 unsigned RAGreedy::tryAssign(LiveInterval &VirtReg,
 442                              AllocationOrder &Order,
 443                              SmallVectorImpl<LiveInterval*> &NewVRegs) {
 444   Order.rewind();
 445   unsigned PhysReg;
 446   while ((PhysReg = Order.next()))
 447     if (!checkPhysRegInterference(VirtReg, PhysReg))
 448       break;
 449   if (!PhysReg || Order.isHint(PhysReg))
 450     return PhysReg;
 451
 452   // PhysReg is available, but there may be a better choice.
 453
 454   // If we missed a simple hint, try to cheaply evict interference from the
 455   // preferred register.
 456   if (unsigned Hint = MRI->getSimpleHint(VirtReg.reg))
 457     if (Order.isHint(Hint)) {
 458       DEBUG(dbgs() << "missed hint " << PrintReg(Hint, TRI) << '\n');
 459       EvictionCost MaxCost(1);
 460       if (canEvictInterference(VirtReg, Hint, true, MaxCost)) {
 461         evictInterference(VirtReg, Hint, NewVRegs);
 462         return Hint;
 463       }
 464     }
 465
 466   // Try to evict interference from a cheaper alternative.
 467   unsigned Cost = TRI->getCostPerUse(PhysReg);
 468
 469   // Most registers have 0 additional cost.
 470   if (!Cost)
 471     return PhysReg;
 472
 473   DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " is available at cost " << Cost
 474                << '\n');
 475   unsigned CheapReg = tryEvict(VirtReg, Order, NewVRegs, Cost);
 476   return CheapReg ? CheapReg : PhysReg;
 477 }
 478
 479
 480 //===----------------------------------------------------------------------===//
 481 //                         Interference eviction
 482 //===----------------------------------------------------------------------===//
 483
 484 /// shouldEvict - determine if A should evict the assigned live range B. The
 485 /// eviction policy defined by this function together with the allocation order
 486 /// defined by enqueue() decides which registers ultimately end up being split
 487 /// and spilled.
 488 ///
 489 /// Cascade numbers are used to prevent infinite loops if this function is a
 490 /// cyclic relation.
 491 ///
 492 /// @param A          The live range to be assigned.
 493 /// @param IsHint     True when A is about to be assigned to its preferred
 494 ///                   register.
 495 /// @param B          The live range to be evicted.
 496 /// @param BreaksHint True when B is already assigned to its preferred register.
 497 bool RAGreedy::shouldEvict(LiveInterval &A, bool IsHint,
 498                            LiveInterval &B, bool BreaksHint) {
 499   bool CanSplit = getStage(B) < RS_Spill;
 500
 501   // Be fairly aggressive about following hints as long as the evictee can be
 502   // split.
 503   if (CanSplit && IsHint && !BreaksHint)
 504     return true;
 505
 506   return A.weight > B.weight;
 507 }
 508
 509 /// canEvictInterference - Return true if all interferences between VirtReg and
 510 /// PhysReg can be evicted.  When OnlyCheap is set, don't do anything
 511 ///
 512 /// @param VirtReg Live range that is about to be assigned.
 513 /// @param PhysReg Desired register for assignment.
 514 /// @prarm IsHint  True when PhysReg is VirtReg's preferred register.
 515 /// @param MaxCost Only look for cheaper candidates and update with new cost
 516 ///                when returning true.
 517 /// @returns True when interference can be evicted cheaper than MaxCost.
 518 bool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg,
 519                                     bool IsHint, EvictionCost &MaxCost) {
 520   // Find VirtReg's cascade number. This will be unassigned if VirtReg was never
 521   // involved in an eviction before. If a cascade number was assigned, deny
 522   // evicting anything with the same or a newer cascade number. This prevents
 523   // infinite eviction loops.
 524   //
 525   // This works out so a register without a cascade number is allowed to evict
 526   // anything, and it can be evicted by anything.
 527   unsigned Cascade = ExtraRegInfo[VirtReg.reg].Cascade;
 528   if (!Cascade)
 529     Cascade = NextCascade;
 530
 531   EvictionCost Cost;
 532   for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) {
 533     LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI);
 534     // If there is 10 or more interferences, chances are one is heavier.
 535     if (Q.collectInterferingVRegs(10) >= 10)
 536       return false;
 537
 538     // Check if any interfering live range is heavier than MaxWeight.
 539     for (unsigned i = Q.interferingVRegs().size(); i; --i) {
 540       LiveInterval *Intf = Q.interferingVRegs()[i - 1];
 541       if (TargetRegisterInfo::isPhysicalRegister(Intf->reg))
 542         return false;
 543       // Never evict spill products. They cannot split or spill.
 544       if (getStage(*Intf) == RS_Done)
 545         return false;
 546       // Once a live range becomes small enough, it is urgent that we find a
 547       // register for it. This is indicated by an infinite spill weight. These
 548       // urgent live ranges get to evict almost anything.
 549       bool Urgent = !VirtReg.isSpillable() && Intf->isSpillable();
 550       // Only evict older cascades or live ranges without a cascade.
 551       unsigned IntfCascade = ExtraRegInfo[Intf->reg].Cascade;
 552       if (Cascade <= IntfCascade) {
 553         if (!Urgent)
 554           return false;
 555         // We permit breaking cascades for urgent evictions. It should be the
 556         // last resort, though, so make it really expensive.
 557         Cost.BrokenHints += 10;
 558       }
 559       // Would this break a satisfied hint?
 560       bool BreaksHint = VRM->hasPreferredPhys(Intf->reg);
 561       // Update eviction cost.
 562       Cost.BrokenHints += BreaksHint;
 563       Cost.MaxWeight = std::max(Cost.MaxWeight, Intf->weight);
 564       // Abort if this would be too expensive.
 565       if (!(Cost < MaxCost))
 566         return false;
 567       // Finally, apply the eviction policy for non-urgent evictions.
 568       if (!Urgent && !shouldEvict(VirtReg, IsHint, *Intf, BreaksHint))
 569         return false;
 570     }
 571   }
 572   MaxCost = Cost;
 573   return true;
 574 }
 575
 576 /// evictInterference - Evict any interferring registers that prevent VirtReg
 577 /// from being assigned to Physreg. This assumes that canEvictInterference
 578 /// returned true.
 579 void RAGreedy::evictInterference(LiveInterval &VirtReg, unsigned PhysReg,
 580                                  SmallVectorImpl<LiveInterval*> &NewVRegs) {
 581   // Make sure that VirtReg has a cascade number, and assign that cascade
 582   // number to every evicted register. These live ranges than then only be
 583   // evicted by a newer cascade, preventing infinite loops.
 584   unsigned Cascade = ExtraRegInfo[VirtReg.reg].Cascade;
 585   if (!Cascade)
 586     Cascade = ExtraRegInfo[VirtReg.reg].Cascade = NextCascade++;
 587
 588   DEBUG(dbgs() << "evicting " << PrintReg(PhysReg, TRI)
 589                << " interference: Cascade " << Cascade << '\n');
 590   for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) {
 591     LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI);
 592     assert(Q.seenAllInterferences() && "Didn't check all interfererences.");
 593     for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) {
 594       LiveInterval *Intf = Q.interferingVRegs()[i];
 595       unassign(*Intf, VRM->getPhys(Intf->reg));
 596       assert((ExtraRegInfo[Intf->reg].Cascade < Cascade ||
 597               VirtReg.isSpillable() < Intf->isSpillable()) &&
 598              "Cannot decrease cascade number, illegal eviction");
 599       ExtraRegInfo[Intf->reg].Cascade = Cascade;
 600       ++NumEvicted;
 601       NewVRegs.push_back(Intf);
 602     }
 603   }
 604 }
 605
 606 /// tryEvict - Try to evict all interferences for a physreg.
 607 /// @param  VirtReg Currently unassigned virtual register.
 608 /// @param  Order   Physregs to try.
 609 /// @return         Physreg to assign VirtReg, or 0.
 610 unsigned RAGreedy::tryEvict(LiveInterval &VirtReg,
 611                             AllocationOrder &Order,
 612                             SmallVectorImpl<LiveInterval*> &NewVRegs,
 613                             unsigned CostPerUseLimit) {
 614   NamedRegionTimer T("Evict", TimerGroupName, TimePassesIsEnabled);
 615
 616   // Keep track of the cheapest interference seen so far.
 617   EvictionCost BestCost(~0u);
 618   unsigned BestPhys = 0;
 619
 620   // When we are just looking for a reduced cost per use, don't break any
 621   // hints, and only evict smaller spill weights.
 622   if (CostPerUseLimit < ~0u) {
 623     BestCost.BrokenHints = 0;
 624     BestCost.MaxWeight = VirtReg.weight;
 625   }
 626
 627   Order.rewind();
 628   while (unsigned PhysReg = Order.next()) {
 629     if (TRI->getCostPerUse(PhysReg) >= CostPerUseLimit)
 630       continue;
 631     // The first use of a callee-saved register in a function has cost 1.
 632     // Don't start using a CSR when the CostPerUseLimit is low.
 633     if (CostPerUseLimit == 1)
 634      if (unsigned CSR = RegClassInfo.getLastCalleeSavedAlias(PhysReg))
 635        if (!MRI->isPhysRegUsed(CSR)) {
 636          DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " would clobber CSR "
 637                       << PrintReg(CSR, TRI) << '\n');
 638          continue;
 639        }
 640
 641     if (!canEvictInterference(VirtReg, PhysReg, false, BestCost))
 642       continue;
 643
 644     // Best so far.
 645     BestPhys = PhysReg;
 646
 647     // Stop if the hint can be used.
 648     if (Order.isHint(PhysReg))
 649       break;
 650   }
 651
 652   if (!BestPhys)
 653     return 0;
 654
 655   evictInterference(VirtReg, BestPhys, NewVRegs);
 656   return BestPhys;
 657 }
 658
 659
 660 //===----------------------------------------------------------------------===//
 661 //                              Region Splitting
 662 //===----------------------------------------------------------------------===//
 663
 664 /// addSplitConstraints - Fill out the SplitConstraints vector based on the
 665 /// interference pattern in Physreg and its aliases. Add the constraints to
 666 /// SpillPlacement and return the static cost of this split in Cost, assuming
 667 /// that all preferences in SplitConstraints are met.
 668 /// Return false if there are no bundles with positive bias.
 669 bool RAGreedy::addSplitConstraints(InterferenceCache::Cursor Intf,
 670                                    float &Cost) {
 671   ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
 672
 673   // Reset interference dependent info.
 674   SplitConstraints.resize(UseBlocks.size());
 675   float StaticCost = 0;
 676   for (unsigned i = 0; i != UseBlocks.size(); ++i) {
 677     const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
 678     SpillPlacement::BlockConstraint &BC = SplitConstraints[i];
 679
 680     BC.Number = BI.MBB->getNumber();
 681     Intf.moveToBlock(BC.Number);
 682     BC.Entry = BI.LiveIn ? SpillPlacement::PrefReg : SpillPlacement::DontCare;
 683     BC.Exit = BI.LiveOut ? SpillPlacement::PrefReg : SpillPlacement::DontCare;
 684     BC.ChangesValue = BI.FirstDef;
 685
 686     if (!Intf.hasInterference())
 687       continue;
 688
 689     // Number of spill code instructions to insert.
 690     unsigned Ins = 0;
 691
 692     // Interference for the live-in value.
 693     if (BI.LiveIn) {
 694       if (Intf.first() <= Indexes->getMBBStartIdx(BC.Number))
 695         BC.Entry = SpillPlacement::MustSpill, ++Ins;
 696       else if (Intf.first() < BI.FirstInstr)
 697         BC.Entry = SpillPlacement::PrefSpill, ++Ins;
 698       else if (Intf.first() < BI.LastInstr)
 699         ++Ins;
 700     }
 701
 702     // Interference for the live-out value.
 703     if (BI.LiveOut) {
 704       if (Intf.last() >= SA->getLastSplitPoint(BC.Number))
 705         BC.Exit = SpillPlacement::MustSpill, ++Ins;
 706       else if (Intf.last() > BI.LastInstr)
 707         BC.Exit = SpillPlacement::PrefSpill, ++Ins;
 708       else if (Intf.last() > BI.FirstInstr)
 709         ++Ins;
 710     }
 711
 712     // Accumulate the total frequency of inserted spill code.
 713     if (Ins)
 714       StaticCost += Ins * SpillPlacer->getBlockFrequency(BC.Number);
 715   }
 716   Cost = StaticCost;
 717
 718   // Add constraints for use-blocks. Note that these are the only constraints
 719   // that may add a positive bias, it is downhill from here.
 720   SpillPlacer->addConstraints(SplitConstraints);
 721   return SpillPlacer->scanActiveBundles();
 722 }
 723
 724
 725 /// addThroughConstraints - Add constraints and links to SpillPlacer from the
 726 /// live-through blocks in Blocks.
 727 void RAGreedy::addThroughConstraints(InterferenceCache::Cursor Intf,
 728                                      ArrayRef<unsigned> Blocks) {
 729   const unsigned GroupSize = 8;
 730   SpillPlacement::BlockConstraint BCS[GroupSize];
 731   unsigned TBS[GroupSize];
 732   unsigned B = 0, T = 0;
 733
 734   for (unsigned i = 0; i != Blocks.size(); ++i) {
 735     unsigned Number = Blocks[i];
 736     Intf.moveToBlock(Number);
 737
 738     if (!Intf.hasInterference()) {
 739       assert(T < GroupSize && "Array overflow");
 740       TBS[T] = Number;
 741       if (++T == GroupSize) {
 742         SpillPlacer->addLinks(makeArrayRef(TBS, T));
 743         T = 0;
 744       }
 745       continue;
 746     }
 747
 748     assert(B < GroupSize && "Array overflow");
 749     BCS[B].Number = Number;
 750
 751     // Interference for the live-in value.
 752     if (Intf.first() <= Indexes->getMBBStartIdx(Number))
 753       BCS[B].Entry = SpillPlacement::MustSpill;
 754     else
 755       BCS[B].Entry = SpillPlacement::PrefSpill;
 756
 757     // Interference for the live-out value.
 758     if (Intf.last() >= SA->getLastSplitPoint(Number))
 759       BCS[B].Exit = SpillPlacement::MustSpill;
 760     else
 761       BCS[B].Exit = SpillPlacement::PrefSpill;
 762
 763     if (++B == GroupSize) {
 764       ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B);
 765       SpillPlacer->addConstraints(Array);
 766       B = 0;
 767     }
 768   }
 769
 770   ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B);
 771   SpillPlacer->addConstraints(Array);
 772   SpillPlacer->addLinks(makeArrayRef(TBS, T));
 773 }
 774
 775 void RAGreedy::growRegion(GlobalSplitCandidate &Cand) {
 776   // Keep track of through blocks that have not been added to SpillPlacer.
 777   BitVector Todo = SA->getThroughBlocks();
 778   SmallVectorImpl<unsigned> &ActiveBlocks = Cand.ActiveBlocks;
 779   unsigned AddedTo = 0;
 780 #ifndef NDEBUG
 781   unsigned Visited = 0;
 782 #endif
 783
 784   for (;;) {
 785     ArrayRef<unsigned> NewBundles = SpillPlacer->getRecentPositive();
 786     // Find new through blocks in the periphery of PrefRegBundles.
 787     for (int i = 0, e = NewBundles.size(); i != e; ++i) {
 788       unsigned Bundle = NewBundles[i];
 789       // Look at all blocks connected to Bundle in the full graph.
 790       ArrayRef<unsigned> Blocks = Bundles->getBlocks(Bundle);
 791       for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end();
 792            I != E; ++I) {
 793         unsigned Block = *I;
 794         if (!Todo.test(Block))
 795           continue;
 796         Todo.reset(Block);
 797         // This is a new through block. Add it to SpillPlacer later.
 798         ActiveBlocks.push_back(Block);
 799 #ifndef NDEBUG
 800         ++Visited;
 801 #endif
 802       }
 803     }
 804     // Any new blocks to add?
 805     if (ActiveBlocks.size() == AddedTo)
 806       break;
 807
 808     // Compute through constraints from the interference, or assume that all
 809     // through blocks prefer spilling when forming compact regions.
 810     ArrayRef<unsigned> NewBlocks = makeArrayRef(ActiveBlocks).slice(AddedTo);
 811     if (Cand.PhysReg)
 812       addThroughConstraints(Cand.Intf, NewBlocks);
 813     else
 814       // Provide a strong negative bias on through blocks to prevent unwanted
 815       // liveness on loop backedges.
 816       SpillPlacer->addPrefSpill(NewBlocks, /* Strong= */ true);
 817     AddedTo = ActiveBlocks.size();
 818
 819     // Perhaps iterating can enable more bundles?
 820     SpillPlacer->iterate();
 821   }
 822   DEBUG(dbgs() << ", v=" << Visited);
 823 }
 824
 825 /// calcCompactRegion - Compute the set of edge bundles that should be live
 826 /// when splitting the current live range into compact regions.  Compact
 827 /// regions can be computed without looking at interference.  They are the
 828 /// regions formed by removing all the live-through blocks from the live range.
 829 ///
 830 /// Returns false if the current live range is already compact, or if the
 831 /// compact regions would form single block regions anyway.
 832 bool RAGreedy::calcCompactRegion(GlobalSplitCandidate &Cand) {
 833   // Without any through blocks, the live range is already compact.
 834   if (!SA->getNumThroughBlocks())
 835     return false;
 836
 837   // Compact regions don't correspond to any physreg.
 838   Cand.reset(IntfCache, 0);
 839
 840   DEBUG(dbgs() << "Compact region bundles");
 841
 842   // Use the spill placer to determine the live bundles. GrowRegion pretends
 843   // that all the through blocks have interference when PhysReg is unset.
 844   SpillPlacer->prepare(Cand.LiveBundles);
 845
 846   // The static split cost will be zero since Cand.Intf reports no interference.
 847   float Cost;
 848   if (!addSplitConstraints(Cand.Intf, Cost)) {
 849     DEBUG(dbgs() << ", none.\n");
 850     return false;
 851   }
 852
 853   growRegion(Cand);
 854   SpillPlacer->finish();
 855
 856   if (!Cand.LiveBundles.any()) {
 857     DEBUG(dbgs() << ", none.\n");
 858     return false;
 859   }
 860
 861   DEBUG({
 862     for (int i = Cand.LiveBundles.find_first(); i>=0;
 863          i = Cand.LiveBundles.find_next(i))
 864     dbgs() << " EB#" << i;
 865     dbgs() << ".\n";
 866   });
 867   return true;
 868 }
 869
 870 /// calcSpillCost - Compute how expensive it would be to split the live range in
 871 /// SA around all use blocks instead of forming bundle regions.
 872 float RAGreedy::calcSpillCost() {
 873   float Cost = 0;
 874   ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
 875   for (unsigned i = 0; i != UseBlocks.size(); ++i) {
 876     const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
 877     unsigned Number = BI.MBB->getNumber();
 878     // We normally only need one spill instruction - a load or a store.
 879     Cost += SpillPlacer->getBlockFrequency(Number);
 880
 881     // Unless the value is redefined in the block.
 882     if (BI.LiveIn && BI.LiveOut && BI.FirstDef)
 883       Cost += SpillPlacer->getBlockFrequency(Number);
 884   }
 885   return Cost;
 886 }
 887
 888 /// calcGlobalSplitCost - Return the global split cost of following the split
 889 /// pattern in LiveBundles. This cost should be added to the local cost of the
 890 /// interference pattern in SplitConstraints.
 891 ///
 892 float RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand) {
 893   float GlobalCost = 0;
 894   const BitVector &LiveBundles = Cand.LiveBundles;
 895   ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
 896   for (unsigned i = 0; i != UseBlocks.size(); ++i) {
 897     const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
 898     SpillPlacement::BlockConstraint &BC = SplitConstraints[i];
 899     bool RegIn  = LiveBundles[Bundles->getBundle(BC.Number, 0)];
 900     bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, 1)];
 901     unsigned Ins = 0;
 902
 903     if (BI.LiveIn)
 904       Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg);
 905     if (BI.LiveOut)
 906       Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg);
 907     if (Ins)
 908       GlobalCost += Ins * SpillPlacer->getBlockFrequency(BC.Number);
 909   }
 910
 911   for (unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) {
 912     unsigned Number = Cand.ActiveBlocks[i];
 913     bool RegIn  = LiveBundles[Bundles->getBundle(Number, 0)];
 914     bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)];
 915     if (!RegIn && !RegOut)
 916       continue;
 917     if (RegIn && RegOut) {
 918       // We need double spill code if this block has interference.
 919       Cand.Intf.moveToBlock(Number);
 920       if (Cand.Intf.hasInterference())
 921         GlobalCost += 2*SpillPlacer->getBlockFrequency(Number);
 922       continue;
 923     }
 924     // live-in / stack-out or stack-in live-out.
 925     GlobalCost += SpillPlacer->getBlockFrequency(Number);
 926   }
 927   return GlobalCost;
 928 }
 929
 930 /// splitAroundRegion - Split the current live range around the regions
 931 /// determined by BundleCand and GlobalCand.
 932 ///
 933 /// Before calling this function, GlobalCand and BundleCand must be initialized
 934 /// so each bundle is assigned to a valid candidate, or NoCand for the
 935 /// stack-bound bundles.  The shared SA/SE SplitAnalysis and SplitEditor
 936 /// objects must be initialized for the current live range, and intervals
 937 /// created for the used candidates.
 938 ///
 939 /// @param LREdit    The LiveRangeEdit object handling the current split.
 940 /// @param UsedCands List of used GlobalCand entries. Every BundleCand value
 941 ///                  must appear in this list.
 942 void RAGreedy::splitAroundRegion(LiveRangeEdit &LREdit,
 943                                  ArrayRef<unsigned> UsedCands) {
 944   // These are the intervals created for new global ranges. We may create more
 945   // intervals for local ranges.
 946   const unsigned NumGlobalIntvs = LREdit.size();
 947   DEBUG(dbgs() << "splitAroundRegion with " << NumGlobalIntvs << " globals.\n");
 948   assert(NumGlobalIntvs && "No global intervals configured");
 949
 950   // Isolate even single instructions when dealing with a proper sub-class.
 951   // That guarantees register class inflation for the stack interval because it
 952   // is all copies.
 953   unsigned Reg = SA->getParent().reg;
 954   bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg));
 955
 956   // First handle all the blocks with uses.
 957   ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
 958   for (unsigned i = 0; i != UseBlocks.size(); ++i) {
 959     const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
 960     unsigned Number = BI.MBB->getNumber();
 961     unsigned IntvIn = 0, IntvOut = 0;
 962     SlotIndex IntfIn, IntfOut;
 963     if (BI.LiveIn) {
 964       unsigned CandIn = BundleCand[Bundles->getBundle(Number, 0)];
 965       if (CandIn != NoCand) {
 966         GlobalSplitCandidate &Cand = GlobalCand[CandIn];
 967         IntvIn = Cand.IntvIdx;
 968         Cand.Intf.moveToBlock(Number);
 969         IntfIn = Cand.Intf.first();
 970       }
 971     }
 972     if (BI.LiveOut) {
 973       unsigned CandOut = BundleCand[Bundles->getBundle(Number, 1)];
 974       if (CandOut != NoCand) {
 975         GlobalSplitCandidate &Cand = GlobalCand[CandOut];
 976         IntvOut = Cand.IntvIdx;
 977         Cand.Intf.moveToBlock(Number);
 978         IntfOut = Cand.Intf.last();
 979       }
 980     }
 981
 982     // Create separate intervals for isolated blocks with multiple uses.
 983     if (!IntvIn && !IntvOut) {
 984       DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " isolated.\n");
 985       if (SA->shouldSplitSingleBlock(BI, SingleInstrs))
 986         SE->splitSingleBlock(BI);
 987       continue;
 988     }
 989
 990     if (IntvIn && IntvOut)
 991       SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut);
 992     else if (IntvIn)
 993       SE->splitRegInBlock(BI, IntvIn, IntfIn);
 994     else
 995       SE->splitRegOutBlock(BI, IntvOut, IntfOut);
 996   }
 997
 998   // Handle live-through blocks. The relevant live-through blocks are stored in
 999   // the ActiveBlocks list with each candidate. We need to filter out
1000   // duplicates.
1001   BitVector Todo = SA->getThroughBlocks();
1002   for (unsigned c = 0; c != UsedCands.size(); ++c) {
1003     ArrayRef<unsigned> Blocks = GlobalCand[UsedCands[c]].ActiveBlocks;
1004     for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
1005       unsigned Number = Blocks[i];
1006       if (!Todo.test(Number))
1007         continue;
1008       Todo.reset(Number);
1009
1010       unsigned IntvIn = 0, IntvOut = 0;
1011       SlotIndex IntfIn, IntfOut;
1012
1013       unsigned CandIn = BundleCand[Bundles->getBundle(Number, 0)];
1014       if (CandIn != NoCand) {
1015         GlobalSplitCandidate &Cand = GlobalCand[CandIn];
1016         IntvIn = Cand.IntvIdx;
1017         Cand.Intf.moveToBlock(Number);
1018         IntfIn = Cand.Intf.first();
1019       }
1020
1021       unsigned CandOut = BundleCand[Bundles->getBundle(Number, 1)];
1022       if (CandOut != NoCand) {
1023         GlobalSplitCandidate &Cand = GlobalCand[CandOut];
1024         IntvOut = Cand.IntvIdx;
1025         Cand.Intf.moveToBlock(Number);
1026         IntfOut = Cand.Intf.last();
1027       }
1028       if (!IntvIn && !IntvOut)
1029         continue;
1030       SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut);
1031     }
1032   }
1033
1034   ++NumGlobalSplits;
1035
1036   SmallVector<unsigned, 8> IntvMap;
1037   SE->finish(&IntvMap);
1038   DebugVars->splitRegister(Reg, LREdit.regs());
1039
1040   ExtraRegInfo.resize(MRI->getNumVirtRegs());
1041   unsigned OrigBlocks = SA->getNumLiveBlocks();
1042
1043   // Sort out the new intervals created by splitting. We get four kinds:
1044   // - Remainder intervals should not be split again.
1045   // - Candidate intervals can be assigned to Cand.PhysReg.
1046   // - Block-local splits are candidates for local splitting.
1047   // - DCE leftovers should go back on the queue.
1048   for (unsigned i = 0, e = LREdit.size(); i != e; ++i) {
1049     LiveInterval &Reg = *LREdit.get(i);
1050
1051     // Ignore old intervals from DCE.
1052     if (getStage(Reg) != RS_New)
1053       continue;
1054
1055     // Remainder interval. Don't try splitting again, spill if it doesn't
1056     // allocate.
1057     if (IntvMap[i] == 0) {
1058       setStage(Reg, RS_Spill);
1059       continue;
1060     }
1061
1062     // Global intervals. Allow repeated splitting as long as the number of live
1063     // blocks is strictly decreasing.
1064     if (IntvMap[i] < NumGlobalIntvs) {
1065       if (SA->countLiveBlocks(&Reg) >= OrigBlocks) {
1066         DEBUG(dbgs() << "Main interval covers the same " << OrigBlocks
1067                      << " blocks as original.\n");
1068         // Don't allow repeated splitting as a safe guard against looping.
1069         setStage(Reg, RS_Split2);
1070       }
1071       continue;
1072     }
1073
1074     // Other intervals are treated as new. This includes local intervals created
1075     // for blocks with multiple uses, and anything created by DCE.
1076   }
1077
1078   if (VerifyEnabled)
1079     MF->verify(this, "After splitting live range around region");
1080 }
1081
1082 unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
1083                                   SmallVectorImpl<LiveInterval*> &NewVRegs) {
1084   unsigned NumCands = 0;
1085   unsigned BestCand = NoCand;
1086   float BestCost;
1087   SmallVector<unsigned, 8> UsedCands;
1088
1089   // Check if we can split this live range around a compact region.
1090   bool HasCompact = calcCompactRegion(GlobalCand.front());
1091   if (HasCompact) {
1092     // Yes, keep GlobalCand[0] as the compact region candidate.
1093     NumCands = 1;
1094     BestCost = HUGE_VALF;
1095   } else {
1096     // No benefit from the compact region, our fallback will be per-block
1097     // splitting. Make sure we find a solution that is cheaper than spilling.
1098     BestCost = Hysteresis * calcSpillCost();
1099     DEBUG(dbgs() << "Cost of isolating all blocks = " << BestCost << '\n');
1100   }
1101
1102   Order.rewind();
1103   while (unsigned PhysReg = Order.next()) {
1104     // Discard bad candidates before we run out of interference cache cursors.
1105     // This will only affect register classes with a lot of registers (>32).
1106     if (NumCands == IntfCache.getMaxCursors()) {
1107       unsigned WorstCount = ~0u;
1108       unsigned Worst = 0;
1109       for (unsigned i = 0; i != NumCands; ++i) {
1110         if (i == BestCand || !GlobalCand[i].PhysReg)
1111           continue;
1112         unsigned Count = GlobalCand[i].LiveBundles.count();
1113         if (Count < WorstCount)
1114           Worst = i, WorstCount = Count;
1115       }
1116       --NumCands;
1117       GlobalCand[Worst] = GlobalCand[NumCands];
1118       if (BestCand == NumCands)
1119         BestCand = Worst;
1120     }
1121
1122     if (GlobalCand.size() <= NumCands)
1123       GlobalCand.resize(NumCands+1);
1124     GlobalSplitCandidate &Cand = GlobalCand[NumCands];
1125     Cand.reset(IntfCache, PhysReg);
1126
1127     SpillPlacer->prepare(Cand.LiveBundles);
1128     float Cost;
1129     if (!addSplitConstraints(Cand.Intf, Cost)) {
1130       DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tno positive bundles\n");
1131       continue;
1132     }
1133     DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tstatic = " << Cost);
1134     if (Cost >= BestCost) {
1135       DEBUG({
1136         if (BestCand == NoCand)
1137           dbgs() << " worse than no bundles\n";
1138         else
1139           dbgs() << " worse than "
1140                  << PrintReg(GlobalCand[BestCand].PhysReg, TRI) << '\n';
1141       });
1142       continue;
1143     }
1144     growRegion(Cand);
1145
1146     SpillPlacer->finish();
1147
1148     // No live bundles, defer to splitSingleBlocks().
1149     if (!Cand.LiveBundles.any()) {
1150       DEBUG(dbgs() << " no bundles.\n");
1151       continue;
1152     }
1153
1154     Cost += calcGlobalSplitCost(Cand);
1155     DEBUG({
1156       dbgs() << ", total = " << Cost << " with bundles";
1157       for (int i = Cand.LiveBundles.find_first(); i>=0;
1158            i = Cand.LiveBundles.find_next(i))
1159         dbgs() << " EB#" << i;
1160       dbgs() << ".\n";
1161     });
1162     if (Cost < BestCost) {
1163       BestCand = NumCands;
1164       BestCost = Hysteresis * Cost; // Prevent rounding effects.
1165     }
1166     ++NumCands;
1167   }
1168
1169   // No solutions found, fall back to single block splitting.
1170   if (!HasCompact && BestCand == NoCand)
1171     return 0;
1172
1173   // Prepare split editor.
1174   LiveRangeEdit LREdit(VirtReg, NewVRegs, this);
1175   SE->reset(LREdit, SplitSpillMode);
1176
1177   // Assign all edge bundles to the preferred candidate, or NoCand.
1178   BundleCand.assign(Bundles->getNumBundles(), NoCand);
1179
1180   // Assign bundles for the best candidate region.
1181   if (BestCand != NoCand) {
1182     GlobalSplitCandidate &Cand = GlobalCand[BestCand];
1183     if (unsigned B = Cand.getBundles(BundleCand, BestCand)) {
1184       UsedCands.push_back(BestCand);
1185       Cand.IntvIdx = SE->openIntv();
1186       DEBUG(dbgs() << "Split for " << PrintReg(Cand.PhysReg, TRI) << " in "
1187                    << B << " bundles, intv " << Cand.IntvIdx << ".\n");
1188       (void)B;
1189     }
1190   }
1191
1192   // Assign bundles for the compact region.
1193   if (HasCompact) {
1194     GlobalSplitCandidate &Cand = GlobalCand.front();
1195     assert(!Cand.PhysReg && "Compact region has no physreg");
1196     if (unsigned B = Cand.getBundles(BundleCand, 0)) {
1197       UsedCands.push_back(0);
1198       Cand.IntvIdx = SE->openIntv();
1199       DEBUG(dbgs() << "Split for compact region in " << B << " bundles, intv "
1200                    << Cand.IntvIdx << ".\n");
1201       (void)B;
1202     }
1203   }
1204
1205   splitAroundRegion(LREdit, UsedCands);
1206   return 0;
1207 }
1208
1209
1210 //===----------------------------------------------------------------------===//
1211 //                            Per-Block Splitting
1212 //===----------------------------------------------------------------------===//
1213
1214 /// tryBlockSplit - Split a global live range around every block with uses. This
1215 /// creates a lot of local live ranges, that will be split by tryLocalSplit if
1216 /// they don't allocate.
1217 unsigned RAGreedy::tryBlockSplit(LiveInterval &VirtReg, AllocationOrder &Order,
1218                                  SmallVectorImpl<LiveInterval*> &NewVRegs) {
1219   assert(&SA->getParent() == &VirtReg && "Live range wasn't analyzed");
1220   unsigned Reg = VirtReg.reg;
1221   bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg));
1222   LiveRangeEdit LREdit(VirtReg, NewVRegs, this);
1223   SE->reset(LREdit, SplitSpillMode);
1224   ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
1225   for (unsigned i = 0; i != UseBlocks.size(); ++i) {
1226     const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
1227     if (SA->shouldSplitSingleBlock(BI, SingleInstrs))
1228       SE->splitSingleBlock(BI);
1229   }
1230   // No blocks were split.
1231   if (LREdit.empty())
1232     return 0;
1233
1234   // We did split for some blocks.
1235   SmallVector<unsigned, 8> IntvMap;
1236   SE->finish(&IntvMap);
1237
1238   // Tell LiveDebugVariables about the new ranges.
1239   DebugVars->splitRegister(Reg, LREdit.regs());
1240
1241   ExtraRegInfo.resize(MRI->getNumVirtRegs());
1242
1243   // Sort out the new intervals created by splitting. The remainder interval
1244   // goes straight to spilling, the new local ranges get to stay RS_New.
1245   for (unsigned i = 0, e = LREdit.size(); i != e; ++i) {
1246     LiveInterval &LI = *LREdit.get(i);
1247     if (getStage(LI) == RS_New && IntvMap[i] == 0)
1248       setStage(LI, RS_Spill);
1249   }
1250
1251   if (VerifyEnabled)
1252     MF->verify(this, "After splitting live range around basic blocks");
1253   return 0;
1254 }
1255
1256 //===----------------------------------------------------------------------===//
1257 //                             Local Splitting
1258 //===----------------------------------------------------------------------===//
1259
1260
1261 /// calcGapWeights - Compute the maximum spill weight that needs to be evicted
1262 /// in order to use PhysReg between two entries in SA->UseSlots.
1263 ///
1264 /// GapWeight[i] represents the gap between UseSlots[i] and UseSlots[i+1].
1265 ///
1266 void RAGreedy::calcGapWeights(unsigned PhysReg,
1267                               SmallVectorImpl<float> &GapWeight) {
1268   assert(SA->getUseBlocks().size() == 1 && "Not a local interval");
1269   const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front();
1270   ArrayRef<SlotIndex> Uses = SA->getUseSlots();
1271   const unsigned NumGaps = Uses.size()-1;
1272
1273   // Start and end points for the interference check.
1274   SlotIndex StartIdx =
1275     BI.LiveIn ? BI.FirstInstr.getBaseIndex() : BI.FirstInstr;
1276   SlotIndex StopIdx =
1277     BI.LiveOut ? BI.LastInstr.getBoundaryIndex() : BI.LastInstr;
1278
1279   GapWeight.assign(NumGaps, 0.0f);
1280
1281   // Add interference from each overlapping register.
1282   for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
1283     if (!query(const_cast<LiveInterval&>(SA->getParent()), *AI)
1284            .checkInterference())
1285       continue;
1286
1287     // We know that VirtReg is a continuous interval from FirstInstr to
1288     // LastInstr, so we don't need InterferenceQuery.
1289     //
1290     // Interference that overlaps an instruction is counted in both gaps
1291     // surrounding the instruction. The exception is interference before
1292     // StartIdx and after StopIdx.
1293     //
1294     LiveIntervalUnion::SegmentIter IntI = getLiveUnion(*AI).find(StartIdx);
1295     for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) {
1296       // Skip the gaps before IntI.
1297       while (Uses[Gap+1].getBoundaryIndex() < IntI.start())
1298         if (++Gap == NumGaps)
1299           break;
1300       if (Gap == NumGaps)
1301         break;
1302
1303       // Update the gaps covered by IntI.
1304       const float weight = IntI.value()->weight;
1305       for (; Gap != NumGaps; ++Gap) {
1306         GapWeight[Gap] = std::max(GapWeight[Gap], weight);
1307         if (Uses[Gap+1].getBaseIndex() >= IntI.stop())
1308           break;
1309       }
1310       if (Gap == NumGaps)
1311         break;
1312     }
1313   }
1314 }
1315
1316 /// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only
1317 /// basic block.
1318 ///
1319 unsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order,
1320                                  SmallVectorImpl<LiveInterval*> &NewVRegs) {
1321   assert(SA->getUseBlocks().size() == 1 && "Not a local interval");
1322   const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front();
1323
1324   // Note that it is possible to have an interval that is live-in or live-out
1325   // while only covering a single block - A phi-def can use undef values from
1326   // predecessors, and the block could be a single-block loop.
1327   // We don't bother doing anything clever about such a case, we simply assume
1328   // that the interval is continuous from FirstInstr to LastInstr. We should
1329   // make sure that we don't do anything illegal to such an interval, though.
1330
1331   ArrayRef<SlotIndex> Uses = SA->getUseSlots();
1332   if (Uses.size() <= 2)
1333     return 0;
1334   const unsigned NumGaps = Uses.size()-1;
1335
1336   DEBUG({
1337     dbgs() << "tryLocalSplit: ";
1338     for (unsigned i = 0, e = Uses.size(); i != e; ++i)
1339       dbgs() << ' ' << Uses[i];
1340     dbgs() << '\n';
1341   });
1342
1343   // Since we allow local split results to be split again, there is a risk of
1344   // creating infinite loops. It is tempting to require that the new live
1345   // ranges have less instructions than the original. That would guarantee
1346   // convergence, but it is too strict. A live range with 3 instructions can be
1347   // split 2+3 (including the COPY), and we want to allow that.
1348   //
1349   // Instead we use these rules:
1350   //
1351   // 1. Allow any split for ranges with getStage() < RS_Split2. (Except for the
1352   //    noop split, of course).
1353   // 2. Require progress be made for ranges with getStage() == RS_Split2. All
1354   //    the new ranges must have fewer instructions than before the split.
1355   // 3. New ranges with the same number of instructions are marked RS_Split2,
1356   //    smaller ranges are marked RS_New.
1357   //
1358   // These rules allow a 3 -> 2+3 split once, which we need. They also prevent
1359   // excessive splitting and infinite loops.
1360   //
1361   bool ProgressRequired = getStage(VirtReg) >= RS_Split2;
1362
1363   // Best split candidate.
1364   unsigned BestBefore = NumGaps;
1365   unsigned BestAfter = 0;
1366   float BestDiff = 0;
1367
1368   const float blockFreq = SpillPlacer->getBlockFrequency(BI.MBB->getNumber());
1369   SmallVector<float, 8> GapWeight;
1370
1371   Order.rewind();
1372   while (unsigned PhysReg = Order.next()) {
1373     // Keep track of the largest spill weight that would need to be evicted in
1374     // order to make use of PhysReg between UseSlots[i] and UseSlots[i+1].
1375     calcGapWeights(PhysReg, GapWeight);
1376
1377     // Try to find the best sequence of gaps to close.
1378     // The new spill weight must be larger than any gap interference.
1379
1380     // We will split before Uses[SplitBefore] and after Uses[SplitAfter].
1381     unsigned SplitBefore = 0, SplitAfter = 1;
1382
1383     // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]).
1384     // It is the spill weight that needs to be evicted.
1385     float MaxGap = GapWeight[0];
1386
1387     for (;;) {
1388       // Live before/after split?
1389       const bool LiveBefore = SplitBefore != 0 || BI.LiveIn;
1390       const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut;
1391
1392       DEBUG(dbgs() << PrintReg(PhysReg, TRI) << ' '
1393                    << Uses[SplitBefore] << '-' << Uses[SplitAfter]
1394                    << " i=" << MaxGap);
1395
1396       // Stop before the interval gets so big we wouldn't be making progress.
1397       if (!LiveBefore && !LiveAfter) {
1398         DEBUG(dbgs() << " all\n");
1399         break;
1400       }
1401       // Should the interval be extended or shrunk?
1402       bool Shrink = true;
1403
1404       // How many gaps would the new range have?
1405       unsigned NewGaps = LiveBefore + SplitAfter - SplitBefore + LiveAfter;
1406
1407       // Legally, without causing looping?
1408       bool Legal = !ProgressRequired || NewGaps < NumGaps;
1409
1410       if (Legal && MaxGap < HUGE_VALF) {
1411         // Estimate the new spill weight. Each instruction reads or writes the
1412         // register. Conservatively assume there are no read-modify-write
1413         // instructions.
1414         //
1415         // Try to guess the size of the new interval.
1416         const float EstWeight = normalizeSpillWeight(blockFreq * (NewGaps + 1),
1417                                  Uses[SplitBefore].distance(Uses[SplitAfter]) +
1418                                  (LiveBefore + LiveAfter)*SlotIndex::InstrDist);
1419         // Would this split be possible to allocate?
1420         // Never allocate all gaps, we wouldn't be making progress.
1421         DEBUG(dbgs() << " w=" << EstWeight);
1422         if (EstWeight * Hysteresis >= MaxGap) {
1423           Shrink = false;
1424           float Diff = EstWeight - MaxGap;
1425           if (Diff > BestDiff) {
1426             DEBUG(dbgs() << " (best)");
1427             BestDiff = Hysteresis * Diff;
1428             BestBefore = SplitBefore;
1429             BestAfter = SplitAfter;
1430           }
1431         }
1432       }
1433
1434       // Try to shrink.
1435       if (Shrink) {
1436         if (++SplitBefore < SplitAfter) {
1437           DEBUG(dbgs() << " shrink\n");
1438           // Recompute the max when necessary.
1439           if (GapWeight[SplitBefore - 1] >= MaxGap) {
1440             MaxGap = GapWeight[SplitBefore];
1441             for (unsigned i = SplitBefore + 1; i != SplitAfter; ++i)
1442               MaxGap = std::max(MaxGap, GapWeight[i]);
1443           }
1444           continue;
1445         }
1446         MaxGap = 0;
1447       }
1448
1449       // Try to extend the interval.
1450       if (SplitAfter >= NumGaps) {
1451         DEBUG(dbgs() << " end\n");
1452         break;
1453       }
1454
1455       DEBUG(dbgs() << " extend\n");
1456       MaxGap = std::max(MaxGap, GapWeight[SplitAfter++]);
1457     }
1458   }
1459
1460   // Didn't find any candidates?
1461   if (BestBefore == NumGaps)
1462     return 0;
1463
1464   DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore]
1465                << '-' << Uses[BestAfter] << ", " << BestDiff
1466                << ", " << (BestAfter - BestBefore + 1) << " instrs\n");
1467
1468   LiveRangeEdit LREdit(VirtReg, NewVRegs, this);
1469   SE->reset(LREdit);
1470
1471   SE->openIntv();
1472   SlotIndex SegStart = SE->enterIntvBefore(Uses[BestBefore]);
1473   SlotIndex SegStop  = SE->leaveIntvAfter(Uses[BestAfter]);
1474   SE->useIntv(SegStart, SegStop);
1475   SmallVector<unsigned, 8> IntvMap;
1476   SE->finish(&IntvMap);
1477   DebugVars->splitRegister(VirtReg.reg, LREdit.regs());
1478
1479   // If the new range has the same number of instructions as before, mark it as
1480   // RS_Split2 so the next split will be forced to make progress. Otherwise,
1481   // leave the new intervals as RS_New so they can compete.
1482   bool LiveBefore = BestBefore != 0 || BI.LiveIn;
1483   bool LiveAfter = BestAfter != NumGaps || BI.LiveOut;
1484   unsigned NewGaps = LiveBefore + BestAfter - BestBefore + LiveAfter;
1485   if (NewGaps >= NumGaps) {
1486     DEBUG(dbgs() << "Tagging non-progress ranges: ");
1487     assert(!ProgressRequired && "Didn't make progress when it was required.");
1488     for (unsigned i = 0, e = IntvMap.size(); i != e; ++i)
1489       if (IntvMap[i] == 1) {
1490         setStage(*LREdit.get(i), RS_Split2);
1491         DEBUG(dbgs() << PrintReg(LREdit.get(i)->reg));
1492       }
1493     DEBUG(dbgs() << '\n');
1494   }
1495   ++NumLocalSplits;
1496
1497   return 0;
1498 }
1499
1500 //===----------------------------------------------------------------------===//
1501 //                          Live Range Splitting
1502 //===----------------------------------------------------------------------===//
1503
1504 /// trySplit - Try to split VirtReg or one of its interferences, making it
1505 /// assignable.
1506 /// @return Physreg when VirtReg may be assigned and/or new NewVRegs.
1507 unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order,
1508                             SmallVectorImpl<LiveInterval*>&NewVRegs) {
1509   // Ranges must be Split2 or less.
1510   if (getStage(VirtReg) >= RS_Spill)
1511     return 0;
1512
1513   // Local intervals are handled separately.
1514   if (LIS->intervalIsInOneMBB(VirtReg)) {
1515     NamedRegionTimer T("Local Splitting", TimerGroupName, TimePassesIsEnabled);
1516     SA->analyze(&VirtReg);
1517     return tryLocalSplit(VirtReg, Order, NewVRegs);
1518   }
1519
1520   NamedRegionTimer T("Global Splitting", TimerGroupName, TimePassesIsEnabled);
1521
1522   SA->analyze(&VirtReg);
1523
1524   // FIXME: SplitAnalysis may repair broken live ranges coming from the
1525   // coalescer. That may cause the range to become allocatable which means that
1526   // tryRegionSplit won't be making progress. This check should be replaced with
1527   // an assertion when the coalescer is fixed.
1528   if (SA->didRepairRange()) {
1529     // VirtReg has changed, so all cached queries are invalid.
1530     invalidateVirtRegs();
1531     if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs))
1532       return PhysReg;
1533   }
1534
1535   // First try to split around a region spanning multiple blocks. RS_Split2
1536   // ranges already made dubious progress with region splitting, so they go
1537   // straight to single block splitting.
1538   if (getStage(VirtReg) < RS_Split2) {
1539     unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs);
1540     if (PhysReg || !NewVRegs.empty())
1541       return PhysReg;
1542   }
1543
1544   // Then isolate blocks.
1545   return tryBlockSplit(VirtReg, Order, NewVRegs);
1546 }
1547
1548
1549 //===----------------------------------------------------------------------===//
1550 //                            Main Entry Point
1551 //===----------------------------------------------------------------------===//
1552
1553 unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg,
1554                                  SmallVectorImpl<LiveInterval*> &NewVRegs) {
1555   // First try assigning a free register.
1556   AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo);
1557   if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs))
1558     return PhysReg;
1559
1560   LiveRangeStage Stage = getStage(VirtReg);
1561   DEBUG(dbgs() << StageName[Stage]
1562                << " Cascade " << ExtraRegInfo[VirtReg.reg].Cascade << '\n');
1563
1564   // Try to evict a less worthy live range, but only for ranges from the primary
1565   // queue. The RS_Split ranges already failed to do this, and they should not
1566   // get a second chance until they have been split.
1567   if (Stage != RS_Split)
1568     if (unsigned PhysReg = tryEvict(VirtReg, Order, NewVRegs))
1569       return PhysReg;
1570
1571   assert(NewVRegs.empty() && "Cannot append to existing NewVRegs");
1572
1573   // The first time we see a live range, don't try to split or spill.
1574   // Wait until the second time, when all smaller ranges have been allocated.
1575   // This gives a better picture of the interference to split around.
1576   if (Stage < RS_Split) {
1577     setStage(VirtReg, RS_Split);
1578     DEBUG(dbgs() << "wait for second round\n");
1579     NewVRegs.push_back(&VirtReg);
1580     return 0;
1581   }
1582
1583   // If we couldn't allocate a register from spilling, there is probably some
1584   // invalid inline assembly. The base class wil report it.
1585   if (Stage >= RS_Done || !VirtReg.isSpillable())
1586     return ~0u;
1587
1588   // Try splitting VirtReg or interferences.
1589   unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs);
1590   if (PhysReg || !NewVRegs.empty())
1591     return PhysReg;
1592
1593   // Finally spill VirtReg itself.
1594   NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled);
1595   LiveRangeEdit LRE(VirtReg, NewVRegs, this);
1596   spiller().spill(LRE);
1597   setStage(NewVRegs.begin(), NewVRegs.end(), RS_Done);
1598
1599   if (VerifyEnabled)
1600     MF->verify(this, "After spilling");
1601
1602   // The live virtual register requesting allocation was spilled, so tell
1603   // the caller not to allocate anything during this round.
1604   return 0;
1605 }
1606
1607 bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
1608   DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n"
1609                << "********** Function: "
1610                << ((Value*)mf.getFunction())->getName() << '\n');
1611
1612   MF = &mf;
1613   if (VerifyEnabled)
1614     MF->verify(this, "Before greedy register allocator");
1615
1616   RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>());
1617   Indexes = &getAnalysis<SlotIndexes>();
1618   DomTree = &getAnalysis<MachineDominatorTree>();
1619   SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
1620   Loops = &getAnalysis<MachineLoopInfo>();
1621   Bundles = &getAnalysis<EdgeBundles>();
1622   SpillPlacer = &getAnalysis<SpillPlacement>();
1623   DebugVars = &getAnalysis<LiveDebugVariables>();
1624
1625   SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops));
1626   SE.reset(new SplitEditor(*SA, *LIS, *VRM, *DomTree));
1627   ExtraRegInfo.clear();
1628   ExtraRegInfo.resize(MRI->getNumVirtRegs());
1629   NextCascade = 1;
1630   IntfCache.init(MF, &getLiveUnion(0), Indexes, TRI);
1631   GlobalCand.resize(32);  // This will grow as needed.
1632
1633   allocatePhysRegs();
1634   addMBBLiveIns(MF);
1635   LIS->addKillFlags();
1636
1637   // Run rewriter
1638   {
1639     NamedRegionTimer T("Rewriter", TimerGroupName, TimePassesIsEnabled);
1640     VRM->rewrite(Indexes);
1641   }
1642
1643   // Write out new DBG_VALUE instructions.
1644   {
1645     NamedRegionTimer T("Emit Debug Info", TimerGroupName, TimePassesIsEnabled);
1646     DebugVars->emitDebugValues(VRM);
1647   }
1648
1649   // The pass output is in VirtRegMap. Release all the transient data.
1650   releaseMemory();
1651
1652   return true;
1653 }