1 //===-- RegAllocGreedy.cpp - greedy register allocator --------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the RAGreedy function pass for register allocation in
13 //===----------------------------------------------------------------------===//
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"
22 #include "SpillPlacement.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/MachineLoopRanges.h"
37 #include "llvm/CodeGen/MachineRegisterInfo.h"
38 #include "llvm/CodeGen/Passes.h"
39 #include "llvm/CodeGen/RegAllocRegistry.h"
40 #include "llvm/CodeGen/RegisterCoalescer.h"
41 #include "llvm/Target/TargetOptions.h"
42 #include "llvm/Support/Debug.h"
43 #include "llvm/Support/ErrorHandling.h"
44 #include "llvm/Support/raw_ostream.h"
45 #include "llvm/Support/Timer.h"
51 STATISTIC(NumGlobalSplits, "Number of split global live ranges");
52 STATISTIC(NumLocalSplits, "Number of split local live ranges");
53 STATISTIC(NumEvicted, "Number of interferences evicted");
55 static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator",
56 createGreedyRegisterAllocator);
59 class RAGreedy : public MachineFunctionPass,
61 private LiveRangeEdit::Delegate {
65 BitVector ReservedRegs;
70 MachineDominatorTree *DomTree;
71 MachineLoopInfo *Loops;
72 MachineLoopRanges *LoopRanges;
74 SpillPlacement *SpillPlacer;
75 LiveDebugVariables *DebugVars;
78 std::auto_ptr<Spiller> SpillerInstance;
79 std::priority_queue<std::pair<unsigned, unsigned> > Queue;
81 // Live ranges pass through a number of stages as we try to allocate them.
82 // Some of the stages may also create new live ranges:
84 // - Region splitting.
85 // - Per-block splitting.
89 // Ranges produced by one of the stages skip the previous stages when they are
90 // dequeued. This improves performance because we can skip interference checks
91 // that are unlikely to give any results. It also guarantees that the live
92 // range splitting algorithm terminates, something that is otherwise hard to
95 RS_New, ///< Never seen before.
96 RS_First, ///< First time in the queue.
97 RS_Second, ///< Second time in the queue.
98 RS_Global, ///< Produced by global splitting.
99 RS_Local, ///< Produced by local splitting.
100 RS_Spill ///< Produced by spilling.
103 IndexedMap<unsigned char, VirtReg2IndexFunctor> LRStage;
105 LiveRangeStage getStage(const LiveInterval &VirtReg) const {
106 return LiveRangeStage(LRStage[VirtReg.reg]);
109 template<typename Iterator>
110 void setStage(Iterator Begin, Iterator End, LiveRangeStage NewStage) {
111 LRStage.resize(MRI->getNumVirtRegs());
112 for (;Begin != End; ++Begin) {
113 unsigned Reg = (*Begin)->reg;
114 if (LRStage[Reg] == RS_New)
115 LRStage[Reg] = NewStage;
120 std::auto_ptr<SplitAnalysis> SA;
121 std::auto_ptr<SplitEditor> SE;
123 /// Cached per-block interference maps
124 InterferenceCache IntfCache;
126 /// All basic blocks where the current register has uses.
127 SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints;
129 /// Global live range splitting candidate info.
130 struct GlobalSplitCandidate {
132 BitVector LiveBundles;
133 SmallVector<unsigned, 8> ActiveBlocks;
135 void reset(unsigned Reg) {
138 ActiveBlocks.clear();
142 /// Candidate info for for each PhysReg in AllocationOrder.
143 /// This vector never shrinks, but grows to the size of the largest register
145 SmallVector<GlobalSplitCandidate, 32> GlobalCand;
147 /// For every instruction in SA->UseSlots, store the previous non-copy
149 SmallVector<SlotIndex, 8> PrevSlot;
154 /// Return the pass name.
155 virtual const char* getPassName() const {
156 return "Greedy Register Allocator";
159 /// RAGreedy analysis usage.
160 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
161 virtual void releaseMemory();
162 virtual Spiller &spiller() { return *SpillerInstance; }
163 virtual void enqueue(LiveInterval *LI);
164 virtual LiveInterval *dequeue();
165 virtual unsigned selectOrSplit(LiveInterval&,
166 SmallVectorImpl<LiveInterval*>&);
168 /// Perform register allocation.
169 virtual bool runOnMachineFunction(MachineFunction &mf);
174 void LRE_WillEraseInstruction(MachineInstr*);
175 bool LRE_CanEraseVirtReg(unsigned);
176 void LRE_WillShrinkVirtReg(unsigned);
177 void LRE_DidCloneVirtReg(unsigned, unsigned);
179 float calcSpillCost();
180 bool addSplitConstraints(InterferenceCache::Cursor, float&);
181 void addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>);
182 void growRegion(GlobalSplitCandidate &Cand, InterferenceCache::Cursor);
183 float calcGlobalSplitCost(GlobalSplitCandidate&, InterferenceCache::Cursor);
184 void splitAroundRegion(LiveInterval&, GlobalSplitCandidate&,
185 SmallVectorImpl<LiveInterval*>&);
186 void calcGapWeights(unsigned, SmallVectorImpl<float>&);
187 SlotIndex getPrevMappedIndex(const MachineInstr*);
188 void calcPrevSlots();
189 unsigned nextSplitPoint(unsigned);
190 bool canEvictInterference(LiveInterval&, unsigned, float&);
192 unsigned tryAssign(LiveInterval&, AllocationOrder&,
193 SmallVectorImpl<LiveInterval*>&);
194 unsigned tryEvict(LiveInterval&, AllocationOrder&,
195 SmallVectorImpl<LiveInterval*>&, unsigned = ~0u);
196 unsigned tryRegionSplit(LiveInterval&, AllocationOrder&,
197 SmallVectorImpl<LiveInterval*>&);
198 unsigned tryLocalSplit(LiveInterval&, AllocationOrder&,
199 SmallVectorImpl<LiveInterval*>&);
200 unsigned trySplit(LiveInterval&, AllocationOrder&,
201 SmallVectorImpl<LiveInterval*>&);
203 } // end anonymous namespace
205 char RAGreedy::ID = 0;
207 // Hysteresis to use when comparing floats.
208 // This helps stabilize decisions based on float comparisons.
209 const float Hysteresis = 0.98f;
212 FunctionPass* llvm::createGreedyRegisterAllocator() {
213 return new RAGreedy();
216 RAGreedy::RAGreedy(): MachineFunctionPass(ID), LRStage(RS_New) {
217 initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry());
218 initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
219 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
220 initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
221 initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
222 initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry());
223 initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
224 initializeLiveStacksPass(*PassRegistry::getPassRegistry());
225 initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
226 initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
227 initializeMachineLoopRangesPass(*PassRegistry::getPassRegistry());
228 initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
229 initializeEdgeBundlesPass(*PassRegistry::getPassRegistry());
230 initializeSpillPlacementPass(*PassRegistry::getPassRegistry());
233 void RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const {
234 AU.setPreservesCFG();
235 AU.addRequired<AliasAnalysis>();
236 AU.addPreserved<AliasAnalysis>();
237 AU.addRequired<LiveIntervals>();
238 AU.addRequired<SlotIndexes>();
239 AU.addPreserved<SlotIndexes>();
240 AU.addRequired<LiveDebugVariables>();
241 AU.addPreserved<LiveDebugVariables>();
243 AU.addRequiredID(StrongPHIEliminationID);
244 AU.addRequiredTransitive<RegisterCoalescer>();
245 AU.addRequired<CalculateSpillWeights>();
246 AU.addRequired<LiveStacks>();
247 AU.addPreserved<LiveStacks>();
248 AU.addRequired<MachineDominatorTree>();
249 AU.addPreserved<MachineDominatorTree>();
250 AU.addRequired<MachineLoopInfo>();
251 AU.addPreserved<MachineLoopInfo>();
252 AU.addRequired<MachineLoopRanges>();
253 AU.addPreserved<MachineLoopRanges>();
254 AU.addRequired<VirtRegMap>();
255 AU.addPreserved<VirtRegMap>();
256 AU.addRequired<EdgeBundles>();
257 AU.addRequired<SpillPlacement>();
258 MachineFunctionPass::getAnalysisUsage(AU);
262 //===----------------------------------------------------------------------===//
263 // LiveRangeEdit delegate methods
264 //===----------------------------------------------------------------------===//
266 void RAGreedy::LRE_WillEraseInstruction(MachineInstr *MI) {
267 // LRE itself will remove from SlotIndexes and parent basic block.
268 VRM->RemoveMachineInstrFromMaps(MI);
271 bool RAGreedy::LRE_CanEraseVirtReg(unsigned VirtReg) {
272 if (unsigned PhysReg = VRM->getPhys(VirtReg)) {
273 unassign(LIS->getInterval(VirtReg), PhysReg);
276 // Unassigned virtreg is probably in the priority queue.
277 // RegAllocBase will erase it after dequeueing.
281 void RAGreedy::LRE_WillShrinkVirtReg(unsigned VirtReg) {
282 unsigned PhysReg = VRM->getPhys(VirtReg);
286 // Register is assigned, put it back on the queue for reassignment.
287 LiveInterval &LI = LIS->getInterval(VirtReg);
288 unassign(LI, PhysReg);
292 void RAGreedy::LRE_DidCloneVirtReg(unsigned New, unsigned Old) {
293 // LRE may clone a virtual register because dead code elimination causes it to
294 // be split into connected components. Ensure that the new register gets the
295 // same stage as the parent.
297 LRStage[New] = LRStage[Old];
300 void RAGreedy::releaseMemory() {
301 SpillerInstance.reset(0);
304 RegAllocBase::releaseMemory();
307 void RAGreedy::enqueue(LiveInterval *LI) {
308 // Prioritize live ranges by size, assigning larger ranges first.
309 // The queue holds (size, reg) pairs.
310 const unsigned Size = LI->getSize();
311 const unsigned Reg = LI->reg;
312 assert(TargetRegisterInfo::isVirtualRegister(Reg) &&
313 "Can only enqueue virtual registers");
317 if (LRStage[Reg] == RS_New)
318 LRStage[Reg] = RS_First;
320 if (LRStage[Reg] == RS_Second)
321 // Unsplit ranges that couldn't be allocated immediately are deferred until
322 // everything else has been allocated. Long ranges are allocated last so
323 // they are split against realistic interference.
324 Prio = (1u << 31) - Size;
326 // Everything else is allocated in long->short order. Long ranges that don't
327 // fit should be spilled ASAP so they don't create interference.
328 Prio = (1u << 31) + Size;
330 // Boost ranges that have a physical register hint.
331 if (TargetRegisterInfo::isPhysicalRegister(VRM->getRegAllocPref(Reg)))
335 Queue.push(std::make_pair(Prio, Reg));
338 LiveInterval *RAGreedy::dequeue() {
341 LiveInterval *LI = &LIS->getInterval(Queue.top().second);
347 //===----------------------------------------------------------------------===//
349 //===----------------------------------------------------------------------===//
351 /// tryAssign - Try to assign VirtReg to an available register.
352 unsigned RAGreedy::tryAssign(LiveInterval &VirtReg,
353 AllocationOrder &Order,
354 SmallVectorImpl<LiveInterval*> &NewVRegs) {
357 while ((PhysReg = Order.next()))
358 if (!checkPhysRegInterference(VirtReg, PhysReg))
360 if (!PhysReg || Order.isHint(PhysReg))
363 // PhysReg is available. Try to evict interference from a cheaper alternative.
364 unsigned Cost = TRI->getCostPerUse(PhysReg);
366 // Most registers have 0 additional cost.
370 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " is available at cost " << Cost
372 unsigned CheapReg = tryEvict(VirtReg, Order, NewVRegs, Cost);
373 return CheapReg ? CheapReg : PhysReg;
377 //===----------------------------------------------------------------------===//
378 // Interference eviction
379 //===----------------------------------------------------------------------===//
381 /// canEvict - Return true if all interferences between VirtReg and PhysReg can
383 /// Return false if any interference is heavier than MaxWeight.
384 /// On return, set MaxWeight to the maximal spill weight of an interference.
385 bool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg,
388 for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) {
389 LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI);
390 // If there is 10 or more interferences, chances are one is heavier.
391 if (Q.collectInterferingVRegs(10, MaxWeight) >= 10)
394 // Check if any interfering live range is heavier than MaxWeight.
395 for (unsigned i = Q.interferingVRegs().size(); i; --i) {
396 LiveInterval *Intf = Q.interferingVRegs()[i - 1];
397 if (TargetRegisterInfo::isPhysicalRegister(Intf->reg))
399 if (Intf->weight >= MaxWeight)
401 Weight = std::max(Weight, Intf->weight);
408 /// tryEvict - Try to evict all interferences for a physreg.
409 /// @param VirtReg Currently unassigned virtual register.
410 /// @param Order Physregs to try.
411 /// @return Physreg to assign VirtReg, or 0.
412 unsigned RAGreedy::tryEvict(LiveInterval &VirtReg,
413 AllocationOrder &Order,
414 SmallVectorImpl<LiveInterval*> &NewVRegs,
415 unsigned CostPerUseLimit) {
416 NamedRegionTimer T("Evict", TimerGroupName, TimePassesIsEnabled);
418 // Keep track of the lightest single interference seen so far.
419 float BestWeight = VirtReg.weight;
420 unsigned BestPhys = 0;
423 while (unsigned PhysReg = Order.next()) {
424 if (TRI->getCostPerUse(PhysReg) >= CostPerUseLimit)
426 // The first use of a register in a function has cost 1.
427 if (CostPerUseLimit == 1 && !MRI->isPhysRegUsed(PhysReg))
430 float Weight = BestWeight;
431 if (!canEvictInterference(VirtReg, PhysReg, Weight))
434 // This is an eviction candidate.
435 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " interference = "
437 if (BestPhys && Weight >= BestWeight)
443 // Stop if the hint can be used.
444 if (Order.isHint(PhysReg))
451 DEBUG(dbgs() << "evicting " << PrintReg(BestPhys, TRI) << " interference\n");
452 for (const unsigned *AliasI = TRI->getOverlaps(BestPhys); *AliasI; ++AliasI) {
453 LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI);
454 assert(Q.seenAllInterferences() && "Didn't check all interfererences.");
455 for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) {
456 LiveInterval *Intf = Q.interferingVRegs()[i];
457 unassign(*Intf, VRM->getPhys(Intf->reg));
459 NewVRegs.push_back(Intf);
466 //===----------------------------------------------------------------------===//
468 //===----------------------------------------------------------------------===//
470 /// addSplitConstraints - Fill out the SplitConstraints vector based on the
471 /// interference pattern in Physreg and its aliases. Add the constraints to
472 /// SpillPlacement and return the static cost of this split in Cost, assuming
473 /// that all preferences in SplitConstraints are met.
474 /// Return false if there are no bundles with positive bias.
475 bool RAGreedy::addSplitConstraints(InterferenceCache::Cursor Intf,
477 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
479 // Reset interference dependent info.
480 SplitConstraints.resize(UseBlocks.size());
481 float StaticCost = 0;
482 for (unsigned i = 0; i != UseBlocks.size(); ++i) {
483 const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
484 SpillPlacement::BlockConstraint &BC = SplitConstraints[i];
486 BC.Number = BI.MBB->getNumber();
487 Intf.moveToBlock(BC.Number);
488 BC.Entry = BI.LiveIn ? SpillPlacement::PrefReg : SpillPlacement::DontCare;
489 BC.Exit = BI.LiveOut ? SpillPlacement::PrefReg : SpillPlacement::DontCare;
491 if (!Intf.hasInterference())
494 // Number of spill code instructions to insert.
497 // Interference for the live-in value.
499 if (Intf.first() <= Indexes->getMBBStartIdx(BC.Number))
500 BC.Entry = SpillPlacement::MustSpill, ++Ins;
501 else if (Intf.first() < BI.FirstUse)
502 BC.Entry = SpillPlacement::PrefSpill, ++Ins;
503 else if (Intf.first() < (BI.LiveThrough ? BI.LastUse : BI.Kill))
507 // Interference for the live-out value.
509 if (Intf.last() >= SA->getLastSplitPoint(BC.Number))
510 BC.Exit = SpillPlacement::MustSpill, ++Ins;
511 else if (Intf.last() > BI.LastUse)
512 BC.Exit = SpillPlacement::PrefSpill, ++Ins;
513 else if (Intf.last() > (BI.LiveThrough ? BI.FirstUse : BI.Def))
517 // Accumulate the total frequency of inserted spill code.
519 StaticCost += Ins * SpillPlacer->getBlockFrequency(BC.Number);
523 // Add constraints for use-blocks. Note that these are the only constraints
524 // that may add a positive bias, it is downhill from here.
525 SpillPlacer->addConstraints(SplitConstraints);
526 return SpillPlacer->scanActiveBundles();
530 /// addThroughConstraints - Add constraints and links to SpillPlacer from the
531 /// live-through blocks in Blocks.
532 void RAGreedy::addThroughConstraints(InterferenceCache::Cursor Intf,
533 ArrayRef<unsigned> Blocks) {
534 const unsigned GroupSize = 8;
535 SpillPlacement::BlockConstraint BCS[GroupSize];
536 unsigned TBS[GroupSize];
537 unsigned B = 0, T = 0;
539 for (unsigned i = 0; i != Blocks.size(); ++i) {
540 unsigned Number = Blocks[i];
541 Intf.moveToBlock(Number);
543 if (!Intf.hasInterference()) {
544 assert(T < GroupSize && "Array overflow");
546 if (++T == GroupSize) {
547 SpillPlacer->addLinks(ArrayRef<unsigned>(TBS, T));
553 assert(B < GroupSize && "Array overflow");
554 BCS[B].Number = Number;
556 // Interference for the live-in value.
557 if (Intf.first() <= Indexes->getMBBStartIdx(Number))
558 BCS[B].Entry = SpillPlacement::MustSpill;
560 BCS[B].Entry = SpillPlacement::PrefSpill;
562 // Interference for the live-out value.
563 if (Intf.last() >= SA->getLastSplitPoint(Number))
564 BCS[B].Exit = SpillPlacement::MustSpill;
566 BCS[B].Exit = SpillPlacement::PrefSpill;
568 if (++B == GroupSize) {
569 ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B);
570 SpillPlacer->addConstraints(Array);
575 ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B);
576 SpillPlacer->addConstraints(Array);
577 SpillPlacer->addLinks(ArrayRef<unsigned>(TBS, T));
580 void RAGreedy::growRegion(GlobalSplitCandidate &Cand,
581 InterferenceCache::Cursor Intf) {
582 // Keep track of through blocks that have not been added to SpillPlacer.
583 BitVector Todo = SA->getThroughBlocks();
584 SmallVectorImpl<unsigned> &ActiveBlocks = Cand.ActiveBlocks;
585 unsigned AddedTo = 0;
587 unsigned Visited = 0;
591 ArrayRef<unsigned> NewBundles = SpillPlacer->getRecentPositive();
592 if (NewBundles.empty())
594 // Find new through blocks in the periphery of PrefRegBundles.
595 for (int i = 0, e = NewBundles.size(); i != e; ++i) {
596 unsigned Bundle = NewBundles[i];
597 // Look at all blocks connected to Bundle in the full graph.
598 ArrayRef<unsigned> Blocks = Bundles->getBlocks(Bundle);
599 for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end();
602 if (!Todo.test(Block))
605 // This is a new through block. Add it to SpillPlacer later.
606 ActiveBlocks.push_back(Block);
612 // Any new blocks to add?
613 if (ActiveBlocks.size() > AddedTo) {
614 ArrayRef<unsigned> Add(&ActiveBlocks[AddedTo],
615 ActiveBlocks.size() - AddedTo);
616 addThroughConstraints(Intf, Add);
617 AddedTo = ActiveBlocks.size();
619 // Perhaps iterating can enable more bundles?
620 SpillPlacer->iterate();
622 DEBUG(dbgs() << ", v=" << Visited);
625 /// calcSpillCost - Compute how expensive it would be to split the live range in
626 /// SA around all use blocks instead of forming bundle regions.
627 float RAGreedy::calcSpillCost() {
629 const LiveInterval &LI = SA->getParent();
630 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
631 for (unsigned i = 0; i != UseBlocks.size(); ++i) {
632 const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
633 unsigned Number = BI.MBB->getNumber();
634 // We normally only need one spill instruction - a load or a store.
635 Cost += SpillPlacer->getBlockFrequency(Number);
637 // Unless the value is redefined in the block.
638 if (BI.LiveIn && BI.LiveOut) {
639 SlotIndex Start, Stop;
640 tie(Start, Stop) = Indexes->getMBBRange(Number);
641 LiveInterval::const_iterator I = LI.find(Start);
642 assert(I != LI.end() && "Expected live-in value");
643 // Is there a different live-out value? If so, we need an extra spill
646 Cost += SpillPlacer->getBlockFrequency(Number);
652 /// calcGlobalSplitCost - Return the global split cost of following the split
653 /// pattern in LiveBundles. This cost should be added to the local cost of the
654 /// interference pattern in SplitConstraints.
656 float RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand,
657 InterferenceCache::Cursor Intf) {
658 float GlobalCost = 0;
659 const BitVector &LiveBundles = Cand.LiveBundles;
660 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
661 for (unsigned i = 0; i != UseBlocks.size(); ++i) {
662 const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
663 SpillPlacement::BlockConstraint &BC = SplitConstraints[i];
664 bool RegIn = LiveBundles[Bundles->getBundle(BC.Number, 0)];
665 bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, 1)];
669 Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg);
671 Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg);
673 GlobalCost += Ins * SpillPlacer->getBlockFrequency(BC.Number);
676 for (unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) {
677 unsigned Number = Cand.ActiveBlocks[i];
678 bool RegIn = LiveBundles[Bundles->getBundle(Number, 0)];
679 bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)];
680 if (!RegIn && !RegOut)
682 if (RegIn && RegOut) {
683 // We need double spill code if this block has interference.
684 Intf.moveToBlock(Number);
685 if (Intf.hasInterference())
686 GlobalCost += 2*SpillPlacer->getBlockFrequency(Number);
689 // live-in / stack-out or stack-in live-out.
690 GlobalCost += SpillPlacer->getBlockFrequency(Number);
695 /// splitAroundRegion - Split VirtReg around the region determined by
696 /// LiveBundles. Make an effort to avoid interference from PhysReg.
698 /// The 'register' interval is going to contain as many uses as possible while
699 /// avoiding interference. The 'stack' interval is the complement constructed by
700 /// SplitEditor. It will contain the rest.
702 void RAGreedy::splitAroundRegion(LiveInterval &VirtReg,
703 GlobalSplitCandidate &Cand,
704 SmallVectorImpl<LiveInterval*> &NewVRegs) {
705 const BitVector &LiveBundles = Cand.LiveBundles;
708 dbgs() << "Splitting around region for " << PrintReg(Cand.PhysReg, TRI)
710 for (int i = LiveBundles.find_first(); i>=0; i = LiveBundles.find_next(i))
711 dbgs() << " EB#" << i;
715 InterferenceCache::Cursor Intf(IntfCache, Cand.PhysReg);
716 LiveRangeEdit LREdit(VirtReg, NewVRegs, this);
719 // Create the main cross-block interval.
720 const unsigned MainIntv = SE->openIntv();
722 // First add all defs that are live out of a block.
723 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
724 for (unsigned i = 0; i != UseBlocks.size(); ++i) {
725 const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
726 bool RegIn = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)];
727 bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)];
729 // Create separate intervals for isolated blocks with multiple uses.
730 if (!RegIn && !RegOut && BI.FirstUse != BI.LastUse) {
731 DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " isolated.\n");
732 SE->splitSingleBlock(BI);
733 SE->selectIntv(MainIntv);
737 // Should the register be live out?
738 if (!BI.LiveOut || !RegOut)
741 SlotIndex Start, Stop;
742 tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
743 Intf.moveToBlock(BI.MBB->getNumber());
744 DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " -> EB#"
745 << Bundles->getBundle(BI.MBB->getNumber(), 1)
746 << " [" << Start << ';'
747 << SA->getLastSplitPoint(BI.MBB->getNumber()) << '-' << Stop
748 << ") intf [" << Intf.first() << ';' << Intf.last() << ')');
750 // The interference interval should either be invalid or overlap MBB.
751 assert((!Intf.hasInterference() || Intf.first() < Stop)
752 && "Bad interference");
753 assert((!Intf.hasInterference() || Intf.last() > Start)
754 && "Bad interference");
756 // Check interference leaving the block.
757 if (!Intf.hasInterference()) {
758 // Block is interference-free.
759 DEBUG(dbgs() << ", no interference");
760 if (!BI.LiveThrough) {
761 DEBUG(dbgs() << ", not live-through.\n");
762 SE->useIntv(SE->enterIntvBefore(BI.Def), Stop);
766 // Block is live-through, but entry bundle is on the stack.
767 // Reload just before the first use.
768 DEBUG(dbgs() << ", not live-in, enter before first use.\n");
769 SE->useIntv(SE->enterIntvBefore(BI.FirstUse), Stop);
772 DEBUG(dbgs() << ", live-through.\n");
776 // Block has interference.
777 DEBUG(dbgs() << ", interference to " << Intf.last());
779 if (!BI.LiveThrough && Intf.last() <= BI.Def) {
780 // The interference doesn't reach the outgoing segment.
781 DEBUG(dbgs() << " doesn't affect def from " << BI.Def << '\n');
782 SE->useIntv(BI.Def, Stop);
786 SlotIndex LastSplitPoint = SA->getLastSplitPoint(BI.MBB->getNumber());
787 if (Intf.last().getBoundaryIndex() < BI.LastUse) {
788 // There are interference-free uses at the end of the block.
789 // Find the first use that can get the live-out register.
790 SmallVectorImpl<SlotIndex>::const_iterator UI =
791 std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(),
792 Intf.last().getBoundaryIndex());
793 assert(UI != SA->UseSlots.end() && "Couldn't find last use");
795 assert(Use <= BI.LastUse && "Couldn't find last use");
796 // Only attempt a split befroe the last split point.
797 if (Use.getBaseIndex() <= LastSplitPoint) {
798 DEBUG(dbgs() << ", free use at " << Use << ".\n");
799 SlotIndex SegStart = SE->enterIntvBefore(Use);
800 assert(SegStart >= Intf.last() && "Couldn't avoid interference");
801 assert(SegStart < LastSplitPoint && "Impossible split point");
802 SE->useIntv(SegStart, Stop);
807 // Interference is after the last use.
808 DEBUG(dbgs() << " after last use.\n");
809 SlotIndex SegStart = SE->enterIntvAtEnd(*BI.MBB);
810 assert(SegStart >= Intf.last() && "Couldn't avoid interference");
813 // Now all defs leading to live bundles are handled, do everything else.
814 for (unsigned i = 0; i != UseBlocks.size(); ++i) {
815 const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
816 bool RegIn = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)];
817 bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)];
819 // Is the register live-in?
820 if (!BI.LiveIn || !RegIn)
823 // We have an incoming register. Check for interference.
824 SlotIndex Start, Stop;
825 tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
826 Intf.moveToBlock(BI.MBB->getNumber());
827 DEBUG(dbgs() << "EB#" << Bundles->getBundle(BI.MBB->getNumber(), 0)
828 << " -> BB#" << BI.MBB->getNumber() << " [" << Start << ';'
829 << SA->getLastSplitPoint(BI.MBB->getNumber()) << '-' << Stop
832 // Check interference entering the block.
833 if (!Intf.hasInterference()) {
834 // Block is interference-free.
835 DEBUG(dbgs() << ", no interference");
836 if (!BI.LiveThrough) {
837 DEBUG(dbgs() << ", killed in block.\n");
838 SE->useIntv(Start, SE->leaveIntvAfter(BI.Kill));
842 SlotIndex LastSplitPoint = SA->getLastSplitPoint(BI.MBB->getNumber());
843 // Block is live-through, but exit bundle is on the stack.
844 // Spill immediately after the last use.
845 if (BI.LastUse < LastSplitPoint) {
846 DEBUG(dbgs() << ", uses, stack-out.\n");
847 SE->useIntv(Start, SE->leaveIntvAfter(BI.LastUse));
850 // The last use is after the last split point, it is probably an
852 DEBUG(dbgs() << ", uses at " << BI.LastUse << " after split point "
853 << LastSplitPoint << ", stack-out.\n");
854 SlotIndex SegEnd = SE->leaveIntvBefore(LastSplitPoint);
855 SE->useIntv(Start, SegEnd);
856 // Run a double interval from the split to the last use.
857 // This makes it possible to spill the complement without affecting the
859 SE->overlapIntv(SegEnd, BI.LastUse);
862 // Register is live-through.
863 DEBUG(dbgs() << ", uses, live-through.\n");
864 SE->useIntv(Start, Stop);
868 // Block has interference.
869 DEBUG(dbgs() << ", interference from " << Intf.first());
871 if (!BI.LiveThrough && Intf.first() >= BI.Kill) {
872 // The interference doesn't reach the outgoing segment.
873 DEBUG(dbgs() << " doesn't affect kill at " << BI.Kill << '\n');
874 SE->useIntv(Start, BI.Kill);
878 if (Intf.first().getBaseIndex() > BI.FirstUse) {
879 // There are interference-free uses at the beginning of the block.
880 // Find the last use that can get the register.
881 SmallVectorImpl<SlotIndex>::const_iterator UI =
882 std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(),
883 Intf.first().getBaseIndex());
884 assert(UI != SA->UseSlots.begin() && "Couldn't find first use");
885 SlotIndex Use = (--UI)->getBoundaryIndex();
886 DEBUG(dbgs() << ", free use at " << *UI << ".\n");
887 SlotIndex SegEnd = SE->leaveIntvAfter(Use);
888 assert(SegEnd <= Intf.first() && "Couldn't avoid interference");
889 SE->useIntv(Start, SegEnd);
893 // Interference is before the first use.
894 DEBUG(dbgs() << " before first use.\n");
895 SlotIndex SegEnd = SE->leaveIntvAtTop(*BI.MBB);
896 assert(SegEnd <= Intf.first() && "Couldn't avoid interference");
899 // Handle live-through blocks.
900 for (unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) {
901 unsigned Number = Cand.ActiveBlocks[i];
902 bool RegIn = LiveBundles[Bundles->getBundle(Number, 0)];
903 bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)];
904 DEBUG(dbgs() << "Live through BB#" << Number << '\n');
905 if (RegIn && RegOut) {
906 Intf.moveToBlock(Number);
907 if (!Intf.hasInterference()) {
908 SE->useIntv(Indexes->getMBBStartIdx(Number),
909 Indexes->getMBBEndIdx(Number));
913 MachineBasicBlock *MBB = MF->getBlockNumbered(Number);
915 SE->leaveIntvAtTop(*MBB);
917 SE->enterIntvAtEnd(*MBB);
922 SmallVector<unsigned, 8> IntvMap;
923 SE->finish(&IntvMap);
924 DebugVars->splitRegister(VirtReg.reg, LREdit.regs());
926 LRStage.resize(MRI->getNumVirtRegs());
927 unsigned OrigBlocks = SA->getNumThroughBlocks() + SA->getUseBlocks().size();
929 // Sort out the new intervals created by splitting. We get four kinds:
930 // - Remainder intervals should not be split again.
931 // - Candidate intervals can be assigned to Cand.PhysReg.
932 // - Block-local splits are candidates for local splitting.
933 // - DCE leftovers should go back on the queue.
934 for (unsigned i = 0, e = LREdit.size(); i != e; ++i) {
935 unsigned Reg = LREdit.get(i)->reg;
937 // Ignore old intervals from DCE.
938 if (LRStage[Reg] != RS_New)
941 // Remainder interval. Don't try splitting again, spill if it doesn't
943 if (IntvMap[i] == 0) {
944 LRStage[Reg] = RS_Global;
948 // Main interval. Allow repeated splitting as long as the number of live
949 // blocks is strictly decreasing.
950 if (IntvMap[i] == MainIntv) {
951 if (SA->countLiveBlocks(LREdit.get(i)) >= OrigBlocks) {
952 DEBUG(dbgs() << "Main interval covers the same " << OrigBlocks
953 << " blocks as original.\n");
954 // Don't allow repeated splitting as a safe guard against looping.
955 LRStage[Reg] = RS_Global;
960 // Other intervals are treated as new. This includes local intervals created
961 // for blocks with multiple uses, and anything created by DCE.
965 MF->verify(this, "After splitting live range around region");
968 unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
969 SmallVectorImpl<LiveInterval*> &NewVRegs) {
970 float BestCost = Hysteresis * calcSpillCost();
971 DEBUG(dbgs() << "Cost of isolating all blocks = " << BestCost << '\n');
972 const unsigned NoCand = ~0u;
973 unsigned BestCand = NoCand;
976 for (unsigned Cand = 0; unsigned PhysReg = Order.next(); ++Cand) {
977 if (GlobalCand.size() <= Cand)
978 GlobalCand.resize(Cand+1);
979 GlobalCand[Cand].reset(PhysReg);
981 SpillPlacer->prepare(GlobalCand[Cand].LiveBundles);
983 InterferenceCache::Cursor Intf(IntfCache, PhysReg);
984 if (!addSplitConstraints(Intf, Cost)) {
985 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tno positive bundles\n");
988 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tstatic = " << Cost);
989 if (Cost >= BestCost) {
991 if (BestCand == NoCand)
992 dbgs() << " worse than no bundles\n";
994 dbgs() << " worse than "
995 << PrintReg(GlobalCand[BestCand].PhysReg, TRI) << '\n';
999 growRegion(GlobalCand[Cand], Intf);
1001 SpillPlacer->finish();
1003 // No live bundles, defer to splitSingleBlocks().
1004 if (!GlobalCand[Cand].LiveBundles.any()) {
1005 DEBUG(dbgs() << " no bundles.\n");
1009 Cost += calcGlobalSplitCost(GlobalCand[Cand], Intf);
1011 dbgs() << ", total = " << Cost << " with bundles";
1012 for (int i = GlobalCand[Cand].LiveBundles.find_first(); i>=0;
1013 i = GlobalCand[Cand].LiveBundles.find_next(i))
1014 dbgs() << " EB#" << i;
1017 if (Cost < BestCost) {
1019 BestCost = Hysteresis * Cost; // Prevent rounding effects.
1023 if (BestCand == NoCand)
1026 splitAroundRegion(VirtReg, GlobalCand[BestCand], NewVRegs);
1031 //===----------------------------------------------------------------------===//
1033 //===----------------------------------------------------------------------===//
1036 /// calcGapWeights - Compute the maximum spill weight that needs to be evicted
1037 /// in order to use PhysReg between two entries in SA->UseSlots.
1039 /// GapWeight[i] represents the gap between UseSlots[i] and UseSlots[i+1].
1041 void RAGreedy::calcGapWeights(unsigned PhysReg,
1042 SmallVectorImpl<float> &GapWeight) {
1043 assert(SA->getUseBlocks().size() == 1 && "Not a local interval");
1044 const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front();
1045 const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots;
1046 const unsigned NumGaps = Uses.size()-1;
1048 // Start and end points for the interference check.
1049 SlotIndex StartIdx = BI.LiveIn ? BI.FirstUse.getBaseIndex() : BI.FirstUse;
1050 SlotIndex StopIdx = BI.LiveOut ? BI.LastUse.getBoundaryIndex() : BI.LastUse;
1052 GapWeight.assign(NumGaps, 0.0f);
1054 // Add interference from each overlapping register.
1055 for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
1056 if (!query(const_cast<LiveInterval&>(SA->getParent()), *AI)
1057 .checkInterference())
1060 // We know that VirtReg is a continuous interval from FirstUse to LastUse,
1061 // so we don't need InterferenceQuery.
1063 // Interference that overlaps an instruction is counted in both gaps
1064 // surrounding the instruction. The exception is interference before
1065 // StartIdx and after StopIdx.
1067 LiveIntervalUnion::SegmentIter IntI = PhysReg2LiveUnion[*AI].find(StartIdx);
1068 for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) {
1069 // Skip the gaps before IntI.
1070 while (Uses[Gap+1].getBoundaryIndex() < IntI.start())
1071 if (++Gap == NumGaps)
1076 // Update the gaps covered by IntI.
1077 const float weight = IntI.value()->weight;
1078 for (; Gap != NumGaps; ++Gap) {
1079 GapWeight[Gap] = std::max(GapWeight[Gap], weight);
1080 if (Uses[Gap+1].getBaseIndex() >= IntI.stop())
1089 /// getPrevMappedIndex - Return the slot index of the last non-copy instruction
1090 /// before MI that has a slot index. If MI is the first mapped instruction in
1091 /// its block, return the block start index instead.
1093 SlotIndex RAGreedy::getPrevMappedIndex(const MachineInstr *MI) {
1094 assert(MI && "Missing MachineInstr");
1095 const MachineBasicBlock *MBB = MI->getParent();
1096 MachineBasicBlock::const_iterator B = MBB->begin(), I = MI;
1098 if (!(--I)->isDebugValue() && !I->isCopy())
1099 return Indexes->getInstructionIndex(I);
1100 return Indexes->getMBBStartIdx(MBB);
1103 /// calcPrevSlots - Fill in the PrevSlot array with the index of the previous
1104 /// real non-copy instruction for each instruction in SA->UseSlots.
1106 void RAGreedy::calcPrevSlots() {
1107 const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots;
1109 PrevSlot.reserve(Uses.size());
1110 for (unsigned i = 0, e = Uses.size(); i != e; ++i) {
1111 const MachineInstr *MI = Indexes->getInstructionFromIndex(Uses[i]);
1112 PrevSlot.push_back(getPrevMappedIndex(MI).getDefIndex());
1116 /// nextSplitPoint - Find the next index into SA->UseSlots > i such that it may
1117 /// be beneficial to split before UseSlots[i].
1119 /// 0 is always a valid split point
1120 unsigned RAGreedy::nextSplitPoint(unsigned i) {
1121 const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots;
1122 const unsigned Size = Uses.size();
1123 assert(i != Size && "No split points after the end");
1124 // Allow split before i when Uses[i] is not adjacent to the previous use.
1125 while (++i != Size && PrevSlot[i].getBaseIndex() <= Uses[i-1].getBaseIndex())
1130 /// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only
1133 unsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order,
1134 SmallVectorImpl<LiveInterval*> &NewVRegs) {
1135 assert(SA->getUseBlocks().size() == 1 && "Not a local interval");
1136 const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front();
1138 // Note that it is possible to have an interval that is live-in or live-out
1139 // while only covering a single block - A phi-def can use undef values from
1140 // predecessors, and the block could be a single-block loop.
1141 // We don't bother doing anything clever about such a case, we simply assume
1142 // that the interval is continuous from FirstUse to LastUse. We should make
1143 // sure that we don't do anything illegal to such an interval, though.
1145 const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots;
1146 if (Uses.size() <= 2)
1148 const unsigned NumGaps = Uses.size()-1;
1151 dbgs() << "tryLocalSplit: ";
1152 for (unsigned i = 0, e = Uses.size(); i != e; ++i)
1153 dbgs() << ' ' << SA->UseSlots[i];
1157 // For every use, find the previous mapped non-copy instruction.
1158 // We use this to detect valid split points, and to estimate new interval
1162 unsigned BestBefore = NumGaps;
1163 unsigned BestAfter = 0;
1166 const float blockFreq = SpillPlacer->getBlockFrequency(BI.MBB->getNumber());
1167 SmallVector<float, 8> GapWeight;
1170 while (unsigned PhysReg = Order.next()) {
1171 // Keep track of the largest spill weight that would need to be evicted in
1172 // order to make use of PhysReg between UseSlots[i] and UseSlots[i+1].
1173 calcGapWeights(PhysReg, GapWeight);
1175 // Try to find the best sequence of gaps to close.
1176 // The new spill weight must be larger than any gap interference.
1178 // We will split before Uses[SplitBefore] and after Uses[SplitAfter].
1179 unsigned SplitBefore = 0, SplitAfter = nextSplitPoint(1) - 1;
1181 // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]).
1182 // It is the spill weight that needs to be evicted.
1183 float MaxGap = GapWeight[0];
1184 for (unsigned i = 1; i != SplitAfter; ++i)
1185 MaxGap = std::max(MaxGap, GapWeight[i]);
1188 // Live before/after split?
1189 const bool LiveBefore = SplitBefore != 0 || BI.LiveIn;
1190 const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut;
1192 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << ' '
1193 << Uses[SplitBefore] << '-' << Uses[SplitAfter]
1194 << " i=" << MaxGap);
1196 // Stop before the interval gets so big we wouldn't be making progress.
1197 if (!LiveBefore && !LiveAfter) {
1198 DEBUG(dbgs() << " all\n");
1201 // Should the interval be extended or shrunk?
1203 if (MaxGap < HUGE_VALF) {
1204 // Estimate the new spill weight.
1206 // Each instruction reads and writes the register, except the first
1207 // instr doesn't read when !FirstLive, and the last instr doesn't write
1210 // We will be inserting copies before and after, so the total number of
1211 // reads and writes is 2 * EstUses.
1213 const unsigned EstUses = 2*(SplitAfter - SplitBefore) +
1214 2*(LiveBefore + LiveAfter);
1216 // Try to guess the size of the new interval. This should be trivial,
1217 // but the slot index of an inserted copy can be a lot smaller than the
1218 // instruction it is inserted before if there are many dead indexes
1221 // We measure the distance from the instruction before SplitBefore to
1222 // get a conservative estimate.
1224 // The final distance can still be different if inserting copies
1225 // triggers a slot index renumbering.
1227 const float EstWeight = normalizeSpillWeight(blockFreq * EstUses,
1228 PrevSlot[SplitBefore].distance(Uses[SplitAfter]));
1229 // Would this split be possible to allocate?
1230 // Never allocate all gaps, we wouldn't be making progress.
1231 DEBUG(dbgs() << " w=" << EstWeight);
1232 if (EstWeight * Hysteresis >= MaxGap) {
1234 float Diff = EstWeight - MaxGap;
1235 if (Diff > BestDiff) {
1236 DEBUG(dbgs() << " (best)");
1237 BestDiff = Hysteresis * Diff;
1238 BestBefore = SplitBefore;
1239 BestAfter = SplitAfter;
1246 SplitBefore = nextSplitPoint(SplitBefore);
1247 if (SplitBefore < SplitAfter) {
1248 DEBUG(dbgs() << " shrink\n");
1249 // Recompute the max when necessary.
1250 if (GapWeight[SplitBefore - 1] >= MaxGap) {
1251 MaxGap = GapWeight[SplitBefore];
1252 for (unsigned i = SplitBefore + 1; i != SplitAfter; ++i)
1253 MaxGap = std::max(MaxGap, GapWeight[i]);
1260 // Try to extend the interval.
1261 if (SplitAfter >= NumGaps) {
1262 DEBUG(dbgs() << " end\n");
1266 DEBUG(dbgs() << " extend\n");
1267 for (unsigned e = nextSplitPoint(SplitAfter + 1) - 1;
1268 SplitAfter != e; ++SplitAfter)
1269 MaxGap = std::max(MaxGap, GapWeight[SplitAfter]);
1274 // Didn't find any candidates?
1275 if (BestBefore == NumGaps)
1278 DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore]
1279 << '-' << Uses[BestAfter] << ", " << BestDiff
1280 << ", " << (BestAfter - BestBefore + 1) << " instrs\n");
1282 LiveRangeEdit LREdit(VirtReg, NewVRegs, this);
1286 SlotIndex SegStart = SE->enterIntvBefore(Uses[BestBefore]);
1287 SlotIndex SegStop = SE->leaveIntvAfter(Uses[BestAfter]);
1288 SE->useIntv(SegStart, SegStop);
1290 DebugVars->splitRegister(VirtReg.reg, LREdit.regs());
1291 setStage(NewVRegs.begin(), NewVRegs.end(), RS_Local);
1297 //===----------------------------------------------------------------------===//
1298 // Live Range Splitting
1299 //===----------------------------------------------------------------------===//
1301 /// trySplit - Try to split VirtReg or one of its interferences, making it
1303 /// @return Physreg when VirtReg may be assigned and/or new NewVRegs.
1304 unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order,
1305 SmallVectorImpl<LiveInterval*>&NewVRegs) {
1306 // Local intervals are handled separately.
1307 if (LIS->intervalIsInOneMBB(VirtReg)) {
1308 NamedRegionTimer T("Local Splitting", TimerGroupName, TimePassesIsEnabled);
1309 SA->analyze(&VirtReg);
1310 return tryLocalSplit(VirtReg, Order, NewVRegs);
1313 NamedRegionTimer T("Global Splitting", TimerGroupName, TimePassesIsEnabled);
1315 // Don't iterate global splitting.
1316 // Move straight to spilling if this range was produced by a global split.
1317 if (getStage(VirtReg) >= RS_Global)
1320 SA->analyze(&VirtReg);
1322 // FIXME: SplitAnalysis may repair broken live ranges coming from the
1323 // coalescer. That may cause the range to become allocatable which means that
1324 // tryRegionSplit won't be making progress. This check should be replaced with
1325 // an assertion when the coalescer is fixed.
1326 if (SA->didRepairRange()) {
1327 // VirtReg has changed, so all cached queries are invalid.
1328 invalidateVirtRegs();
1329 if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs))
1333 // First try to split around a region spanning multiple blocks.
1334 unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs);
1335 if (PhysReg || !NewVRegs.empty())
1338 // Then isolate blocks with multiple uses.
1339 SplitAnalysis::BlockPtrSet Blocks;
1340 if (SA->getMultiUseBlocks(Blocks)) {
1341 LiveRangeEdit LREdit(VirtReg, NewVRegs, this);
1343 SE->splitSingleBlocks(Blocks);
1344 setStage(NewVRegs.begin(), NewVRegs.end(), RS_Global);
1346 MF->verify(this, "After splitting live range around basic blocks");
1349 // Don't assign any physregs.
1354 //===----------------------------------------------------------------------===//
1356 //===----------------------------------------------------------------------===//
1358 unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg,
1359 SmallVectorImpl<LiveInterval*> &NewVRegs) {
1360 // First try assigning a free register.
1361 AllocationOrder Order(VirtReg.reg, *VRM, ReservedRegs);
1362 if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs))
1365 if (unsigned PhysReg = tryEvict(VirtReg, Order, NewVRegs))
1368 assert(NewVRegs.empty() && "Cannot append to existing NewVRegs");
1370 // The first time we see a live range, don't try to split or spill.
1371 // Wait until the second time, when all smaller ranges have been allocated.
1372 // This gives a better picture of the interference to split around.
1373 LiveRangeStage Stage = getStage(VirtReg);
1374 if (Stage == RS_First) {
1375 LRStage[VirtReg.reg] = RS_Second;
1376 DEBUG(dbgs() << "wait for second round\n");
1377 NewVRegs.push_back(&VirtReg);
1381 // If we couldn't allocate a register from spilling, there is probably some
1382 // invalid inline assembly. The base class wil report it.
1383 if (Stage >= RS_Spill)
1386 // Try splitting VirtReg or interferences.
1387 unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs);
1388 if (PhysReg || !NewVRegs.empty())
1391 // Finally spill VirtReg itself.
1392 NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled);
1393 LiveRangeEdit LRE(VirtReg, NewVRegs, this);
1394 spiller().spill(LRE);
1395 setStage(NewVRegs.begin(), NewVRegs.end(), RS_Spill);
1398 MF->verify(this, "After spilling");
1400 // The live virtual register requesting allocation was spilled, so tell
1401 // the caller not to allocate anything during this round.
1405 bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
1406 DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n"
1407 << "********** Function: "
1408 << ((Value*)mf.getFunction())->getName() << '\n');
1412 MF->verify(this, "Before greedy register allocator");
1414 RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>());
1415 Indexes = &getAnalysis<SlotIndexes>();
1416 DomTree = &getAnalysis<MachineDominatorTree>();
1417 ReservedRegs = TRI->getReservedRegs(*MF);
1418 SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
1419 Loops = &getAnalysis<MachineLoopInfo>();
1420 LoopRanges = &getAnalysis<MachineLoopRanges>();
1421 Bundles = &getAnalysis<EdgeBundles>();
1422 SpillPlacer = &getAnalysis<SpillPlacement>();
1423 DebugVars = &getAnalysis<LiveDebugVariables>();
1425 SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops));
1426 SE.reset(new SplitEditor(*SA, *LIS, *VRM, *DomTree));
1428 LRStage.resize(MRI->getNumVirtRegs());
1429 IntfCache.init(MF, &PhysReg2LiveUnion[0], Indexes, TRI);
1433 LIS->addKillFlags();
1437 NamedRegionTimer T("Rewriter", TimerGroupName, TimePassesIsEnabled);
1438 VRM->rewrite(Indexes);
1441 // Write out new DBG_VALUE instructions.
1442 DebugVars->emitDebugValues(VRM);
1444 // The pass output is in VirtRegMap. Release all the transient data.