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 #include "AllocationOrder.h"
16 #include "InterferenceCache.h"
17 #include "LiveDebugVariables.h"
18 #include "RegAllocBase.h"
19 #include "SpillPlacement.h"
22 #include "llvm/ADT/ArrayRef.h"
23 #include "llvm/ADT/BitVector.h"
24 #include "llvm/ADT/DenseMap.h"
25 #include "llvm/ADT/IndexedMap.h"
26 #include "llvm/ADT/SetVector.h"
27 #include "llvm/ADT/SmallPtrSet.h"
28 #include "llvm/ADT/SmallSet.h"
29 #include "llvm/ADT/SmallVector.h"
30 #include "llvm/ADT/Statistic.h"
31 #include "llvm/ADT/StringRef.h"
32 #include "llvm/Analysis/AliasAnalysis.h"
33 #include "llvm/Analysis/OptimizationDiagnosticInfo.h"
34 #include "llvm/CodeGen/CalcSpillWeights.h"
35 #include "llvm/CodeGen/EdgeBundles.h"
36 #include "llvm/CodeGen/LiveInterval.h"
37 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
38 #include "llvm/CodeGen/LiveIntervalUnion.h"
39 #include "llvm/CodeGen/LiveRangeEdit.h"
40 #include "llvm/CodeGen/LiveRegMatrix.h"
41 #include "llvm/CodeGen/LiveStackAnalysis.h"
42 #include "llvm/CodeGen/MachineBasicBlock.h"
43 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
44 #include "llvm/CodeGen/MachineDominators.h"
45 #include "llvm/CodeGen/MachineFrameInfo.h"
46 #include "llvm/CodeGen/MachineFunction.h"
47 #include "llvm/CodeGen/MachineFunctionPass.h"
48 #include "llvm/CodeGen/MachineInstr.h"
49 #include "llvm/CodeGen/MachineLoopInfo.h"
50 #include "llvm/CodeGen/MachineOperand.h"
51 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
52 #include "llvm/CodeGen/MachineRegisterInfo.h"
53 #include "llvm/CodeGen/RegAllocRegistry.h"
54 #include "llvm/CodeGen/RegisterClassInfo.h"
55 #include "llvm/CodeGen/SlotIndexes.h"
56 #include "llvm/CodeGen/VirtRegMap.h"
57 #include "llvm/IR/Function.h"
58 #include "llvm/IR/LLVMContext.h"
59 #include "llvm/MC/MCRegisterInfo.h"
60 #include "llvm/Pass.h"
61 #include "llvm/Support/BlockFrequency.h"
62 #include "llvm/Support/BranchProbability.h"
63 #include "llvm/Support/CommandLine.h"
64 #include "llvm/Support/Debug.h"
65 #include "llvm/Support/MathExtras.h"
66 #include "llvm/Support/Timer.h"
67 #include "llvm/Support/raw_ostream.h"
68 #include "llvm/Target/TargetInstrInfo.h"
69 #include "llvm/Target/TargetMachine.h"
70 #include "llvm/Target/TargetRegisterInfo.h"
71 #include "llvm/Target/TargetSubtargetInfo.h"
82 #define DEBUG_TYPE "regalloc"
84 STATISTIC(NumGlobalSplits, "Number of split global live ranges");
85 STATISTIC(NumLocalSplits, "Number of split local live ranges");
86 STATISTIC(NumEvicted, "Number of interferences evicted");
88 static cl::opt<SplitEditor::ComplementSpillMode> SplitSpillMode(
89 "split-spill-mode", cl::Hidden,
90 cl::desc("Spill mode for splitting live ranges"),
91 cl::values(clEnumValN(SplitEditor::SM_Partition, "default", "Default"),
92 clEnumValN(SplitEditor::SM_Size, "size", "Optimize for size"),
93 clEnumValN(SplitEditor::SM_Speed, "speed", "Optimize for speed")),
94 cl::init(SplitEditor::SM_Speed));
96 static cl::opt<unsigned>
97 LastChanceRecoloringMaxDepth("lcr-max-depth", cl::Hidden,
98 cl::desc("Last chance recoloring max depth"),
101 static cl::opt<unsigned> LastChanceRecoloringMaxInterference(
102 "lcr-max-interf", cl::Hidden,
103 cl::desc("Last chance recoloring maximum number of considered"
104 " interference at a time"),
108 ExhaustiveSearch("exhaustive-register-search", cl::NotHidden,
109 cl::desc("Exhaustive Search for registers bypassing the depth "
110 "and interference cutoffs of last chance recoloring"));
112 static cl::opt<bool> EnableLocalReassignment(
113 "enable-local-reassign", cl::Hidden,
114 cl::desc("Local reassignment can yield better allocation decisions, but "
115 "may be compile time intensive"),
118 static cl::opt<bool> EnableDeferredSpilling(
119 "enable-deferred-spilling", cl::Hidden,
120 cl::desc("Instead of spilling a variable right away, defer the actual "
121 "code insertion to the end of the allocation. That way the "
122 "allocator might still find a suitable coloring for this "
123 "variable because of other evicted variables."),
126 // FIXME: Find a good default for this flag and remove the flag.
127 static cl::opt<unsigned>
128 CSRFirstTimeCost("regalloc-csr-first-time-cost",
129 cl::desc("Cost for first time use of callee-saved register."),
130 cl::init(0), cl::Hidden);
132 static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator",
133 createGreedyRegisterAllocator);
137 class RAGreedy : public MachineFunctionPass,
139 private LiveRangeEdit::Delegate {
140 // Convenient shortcuts.
141 using PQueue = std::priority_queue<std::pair<unsigned, unsigned>>;
142 using SmallLISet = SmallPtrSet<LiveInterval *, 4>;
143 using SmallVirtRegSet = SmallSet<unsigned, 16>;
148 // Shortcuts to some useful interface.
149 const TargetInstrInfo *TII;
150 const TargetRegisterInfo *TRI;
151 RegisterClassInfo RCI;
154 SlotIndexes *Indexes;
155 MachineBlockFrequencyInfo *MBFI;
156 MachineDominatorTree *DomTree;
157 MachineLoopInfo *Loops;
158 MachineOptimizationRemarkEmitter *ORE;
159 EdgeBundles *Bundles;
160 SpillPlacement *SpillPlacer;
161 LiveDebugVariables *DebugVars;
165 std::unique_ptr<Spiller> SpillerInstance;
167 unsigned NextCascade;
169 // Live ranges pass through a number of stages as we try to allocate them.
170 // Some of the stages may also create new live ranges:
172 // - Region splitting.
173 // - Per-block splitting.
174 // - Local splitting.
177 // Ranges produced by one of the stages skip the previous stages when they are
178 // dequeued. This improves performance because we can skip interference checks
179 // that are unlikely to give any results. It also guarantees that the live
180 // range splitting algorithm terminates, something that is otherwise hard to
182 enum LiveRangeStage {
183 /// Newly created live range that has never been queued.
186 /// Only attempt assignment and eviction. Then requeue as RS_Split.
189 /// Attempt live range splitting if assignment is impossible.
192 /// Attempt more aggressive live range splitting that is guaranteed to make
193 /// progress. This is used for split products that may not be making
197 /// Live range will be spilled. No more splitting will be attempted.
201 /// Live range is in memory. Because of other evictions, it might get moved
202 /// in a register in the end.
205 /// There is nothing more we can do to this live range. Abort compilation
206 /// if it can't be assigned.
210 // Enum CutOffStage to keep a track whether the register allocation failed
211 // because of the cutoffs encountered in last chance recoloring.
212 // Note: This is used as bitmask. New value should be next power of 2.
214 // No cutoffs encountered
217 // lcr-max-depth cutoff encountered
220 // lcr-max-interf cutoff encountered
227 static const char *const StageName[];
230 // RegInfo - Keep additional information about each live range.
232 LiveRangeStage Stage = RS_New;
234 // Cascade - Eviction loop prevention. See canEvictInterference().
235 unsigned Cascade = 0;
240 IndexedMap<RegInfo, VirtReg2IndexFunctor> ExtraRegInfo;
242 LiveRangeStage getStage(const LiveInterval &VirtReg) const {
243 return ExtraRegInfo[VirtReg.reg].Stage;
246 void setStage(const LiveInterval &VirtReg, LiveRangeStage Stage) {
247 ExtraRegInfo.resize(MRI->getNumVirtRegs());
248 ExtraRegInfo[VirtReg.reg].Stage = Stage;
251 template<typename Iterator>
252 void setStage(Iterator Begin, Iterator End, LiveRangeStage NewStage) {
253 ExtraRegInfo.resize(MRI->getNumVirtRegs());
254 for (;Begin != End; ++Begin) {
255 unsigned Reg = *Begin;
256 if (ExtraRegInfo[Reg].Stage == RS_New)
257 ExtraRegInfo[Reg].Stage = NewStage;
261 /// Cost of evicting interference.
262 struct EvictionCost {
263 unsigned BrokenHints = 0; ///< Total number of broken hints.
264 float MaxWeight = 0; ///< Maximum spill weight evicted.
266 EvictionCost() = default;
268 bool isMax() const { return BrokenHints == ~0u; }
270 void setMax() { BrokenHints = ~0u; }
272 void setBrokenHints(unsigned NHints) { BrokenHints = NHints; }
274 bool operator<(const EvictionCost &O) const {
275 return std::tie(BrokenHints, MaxWeight) <
276 std::tie(O.BrokenHints, O.MaxWeight);
281 std::unique_ptr<SplitAnalysis> SA;
282 std::unique_ptr<SplitEditor> SE;
284 /// Cached per-block interference maps
285 InterferenceCache IntfCache;
287 /// All basic blocks where the current register has uses.
288 SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints;
290 /// Global live range splitting candidate info.
291 struct GlobalSplitCandidate {
292 // Register intended for assignment, or 0.
295 // SplitKit interval index for this candidate.
298 // Interference for PhysReg.
299 InterferenceCache::Cursor Intf;
301 // Bundles where this candidate should be live.
302 BitVector LiveBundles;
303 SmallVector<unsigned, 8> ActiveBlocks;
305 void reset(InterferenceCache &Cache, unsigned Reg) {
308 Intf.setPhysReg(Cache, Reg);
310 ActiveBlocks.clear();
313 // Set B[i] = C for every live bundle where B[i] was NoCand.
314 unsigned getBundles(SmallVectorImpl<unsigned> &B, unsigned C) {
316 for (unsigned i : LiveBundles.set_bits())
317 if (B[i] == NoCand) {
325 /// Candidate info for each PhysReg in AllocationOrder.
326 /// This vector never shrinks, but grows to the size of the largest register
328 SmallVector<GlobalSplitCandidate, 32> GlobalCand;
330 enum : unsigned { NoCand = ~0u };
332 /// Candidate map. Each edge bundle is assigned to a GlobalCand entry, or to
333 /// NoCand which indicates the stack interval.
334 SmallVector<unsigned, 32> BundleCand;
336 /// Callee-save register cost, calculated once per machine function.
337 BlockFrequency CSRCost;
339 /// Run or not the local reassignment heuristic. This information is
340 /// obtained from the TargetSubtargetInfo.
341 bool EnableLocalReassign;
343 /// Set of broken hints that may be reconciled later because of eviction.
344 SmallSetVector<LiveInterval *, 8> SetOfBrokenHints;
349 /// Return the pass name.
350 StringRef getPassName() const override { return "Greedy Register Allocator"; }
352 /// RAGreedy analysis usage.
353 void getAnalysisUsage(AnalysisUsage &AU) const override;
354 void releaseMemory() override;
355 Spiller &spiller() override { return *SpillerInstance; }
356 void enqueue(LiveInterval *LI) override;
357 LiveInterval *dequeue() override;
358 unsigned selectOrSplit(LiveInterval&, SmallVectorImpl<unsigned>&) override;
359 void aboutToRemoveInterval(LiveInterval &) override;
361 /// Perform register allocation.
362 bool runOnMachineFunction(MachineFunction &mf) override;
364 MachineFunctionProperties getRequiredProperties() const override {
365 return MachineFunctionProperties().set(
366 MachineFunctionProperties::Property::NoPHIs);
372 unsigned selectOrSplitImpl(LiveInterval &, SmallVectorImpl<unsigned> &,
373 SmallVirtRegSet &, unsigned = 0);
375 bool LRE_CanEraseVirtReg(unsigned) override;
376 void LRE_WillShrinkVirtReg(unsigned) override;
377 void LRE_DidCloneVirtReg(unsigned, unsigned) override;
378 void enqueue(PQueue &CurQueue, LiveInterval *LI);
379 LiveInterval *dequeue(PQueue &CurQueue);
381 BlockFrequency calcSpillCost();
382 bool addSplitConstraints(InterferenceCache::Cursor, BlockFrequency&);
383 void addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>);
384 void growRegion(GlobalSplitCandidate &Cand);
385 BlockFrequency calcGlobalSplitCost(GlobalSplitCandidate&);
386 bool calcCompactRegion(GlobalSplitCandidate&);
387 void splitAroundRegion(LiveRangeEdit&, ArrayRef<unsigned>);
388 void calcGapWeights(unsigned, SmallVectorImpl<float>&);
389 unsigned canReassign(LiveInterval &VirtReg, unsigned PhysReg);
390 bool shouldEvict(LiveInterval &A, bool, LiveInterval &B, bool);
391 bool canEvictInterference(LiveInterval&, unsigned, bool, EvictionCost&);
392 void evictInterference(LiveInterval&, unsigned,
393 SmallVectorImpl<unsigned>&);
394 bool mayRecolorAllInterferences(unsigned PhysReg, LiveInterval &VirtReg,
395 SmallLISet &RecoloringCandidates,
396 const SmallVirtRegSet &FixedRegisters);
398 unsigned tryAssign(LiveInterval&, AllocationOrder&,
399 SmallVectorImpl<unsigned>&);
400 unsigned tryEvict(LiveInterval&, AllocationOrder&,
401 SmallVectorImpl<unsigned>&, unsigned = ~0u);
402 unsigned tryRegionSplit(LiveInterval&, AllocationOrder&,
403 SmallVectorImpl<unsigned>&);
404 /// Calculate cost of region splitting.
405 unsigned calculateRegionSplitCost(LiveInterval &VirtReg,
406 AllocationOrder &Order,
407 BlockFrequency &BestCost,
408 unsigned &NumCands, bool IgnoreCSR);
409 /// Perform region splitting.
410 unsigned doRegionSplit(LiveInterval &VirtReg, unsigned BestCand,
412 SmallVectorImpl<unsigned> &NewVRegs);
413 /// Check other options before using a callee-saved register for the first
415 unsigned tryAssignCSRFirstTime(LiveInterval &VirtReg, AllocationOrder &Order,
416 unsigned PhysReg, unsigned &CostPerUseLimit,
417 SmallVectorImpl<unsigned> &NewVRegs);
418 void initializeCSRCost();
419 unsigned tryBlockSplit(LiveInterval&, AllocationOrder&,
420 SmallVectorImpl<unsigned>&);
421 unsigned tryInstructionSplit(LiveInterval&, AllocationOrder&,
422 SmallVectorImpl<unsigned>&);
423 unsigned tryLocalSplit(LiveInterval&, AllocationOrder&,
424 SmallVectorImpl<unsigned>&);
425 unsigned trySplit(LiveInterval&, AllocationOrder&,
426 SmallVectorImpl<unsigned>&);
427 unsigned tryLastChanceRecoloring(LiveInterval &, AllocationOrder &,
428 SmallVectorImpl<unsigned> &,
429 SmallVirtRegSet &, unsigned);
430 bool tryRecoloringCandidates(PQueue &, SmallVectorImpl<unsigned> &,
431 SmallVirtRegSet &, unsigned);
432 void tryHintRecoloring(LiveInterval &);
433 void tryHintsRecoloring();
435 /// Model the information carried by one end of a copy.
437 /// The frequency of the copy.
439 /// The virtual register or physical register.
441 /// Its currently assigned register.
442 /// In case of a physical register Reg == PhysReg.
445 HintInfo(BlockFrequency Freq, unsigned Reg, unsigned PhysReg)
446 : Freq(Freq), Reg(Reg), PhysReg(PhysReg) {}
448 using HintsInfo = SmallVector<HintInfo, 4>;
450 BlockFrequency getBrokenHintFreq(const HintsInfo &, unsigned);
451 void collectHintInfo(unsigned, HintsInfo &);
453 bool isUnusedCalleeSavedReg(unsigned PhysReg) const;
455 /// Compute and report the number of spills and reloads for a loop.
456 void reportNumberOfSplillsReloads(MachineLoop *L, unsigned &Reloads,
457 unsigned &FoldedReloads, unsigned &Spills,
458 unsigned &FoldedSpills);
460 /// Report the number of spills and reloads for each loop.
461 void reportNumberOfSplillsReloads() {
462 for (MachineLoop *L : *Loops) {
463 unsigned Reloads, FoldedReloads, Spills, FoldedSpills;
464 reportNumberOfSplillsReloads(L, Reloads, FoldedReloads, Spills,
470 } // end anonymous namespace
472 char RAGreedy::ID = 0;
473 char &llvm::RAGreedyID = RAGreedy::ID;
475 INITIALIZE_PASS_BEGIN(RAGreedy, "greedy",
476 "Greedy Register Allocator", false, false)
477 INITIALIZE_PASS_DEPENDENCY(LiveDebugVariables)
478 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
479 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
480 INITIALIZE_PASS_DEPENDENCY(RegisterCoalescer)
481 INITIALIZE_PASS_DEPENDENCY(MachineScheduler)
482 INITIALIZE_PASS_DEPENDENCY(LiveStacks)
483 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
484 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
485 INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
486 INITIALIZE_PASS_DEPENDENCY(LiveRegMatrix)
487 INITIALIZE_PASS_DEPENDENCY(EdgeBundles)
488 INITIALIZE_PASS_DEPENDENCY(SpillPlacement)
489 INITIALIZE_PASS_DEPENDENCY(MachineOptimizationRemarkEmitterPass)
490 INITIALIZE_PASS_END(RAGreedy, "greedy",
491 "Greedy Register Allocator", false, false)
494 const char *const RAGreedy::StageName[] = {
505 // Hysteresis to use when comparing floats.
506 // This helps stabilize decisions based on float comparisons.
507 const float Hysteresis = (2007 / 2048.0f); // 0.97998046875
509 FunctionPass* llvm::createGreedyRegisterAllocator() {
510 return new RAGreedy();
513 RAGreedy::RAGreedy(): MachineFunctionPass(ID) {
516 void RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const {
517 AU.setPreservesCFG();
518 AU.addRequired<MachineBlockFrequencyInfo>();
519 AU.addPreserved<MachineBlockFrequencyInfo>();
520 AU.addRequired<AAResultsWrapperPass>();
521 AU.addPreserved<AAResultsWrapperPass>();
522 AU.addRequired<LiveIntervals>();
523 AU.addPreserved<LiveIntervals>();
524 AU.addRequired<SlotIndexes>();
525 AU.addPreserved<SlotIndexes>();
526 AU.addRequired<LiveDebugVariables>();
527 AU.addPreserved<LiveDebugVariables>();
528 AU.addRequired<LiveStacks>();
529 AU.addPreserved<LiveStacks>();
530 AU.addRequired<MachineDominatorTree>();
531 AU.addPreserved<MachineDominatorTree>();
532 AU.addRequired<MachineLoopInfo>();
533 AU.addPreserved<MachineLoopInfo>();
534 AU.addRequired<VirtRegMap>();
535 AU.addPreserved<VirtRegMap>();
536 AU.addRequired<LiveRegMatrix>();
537 AU.addPreserved<LiveRegMatrix>();
538 AU.addRequired<EdgeBundles>();
539 AU.addRequired<SpillPlacement>();
540 AU.addRequired<MachineOptimizationRemarkEmitterPass>();
541 MachineFunctionPass::getAnalysisUsage(AU);
544 //===----------------------------------------------------------------------===//
545 // LiveRangeEdit delegate methods
546 //===----------------------------------------------------------------------===//
548 bool RAGreedy::LRE_CanEraseVirtReg(unsigned VirtReg) {
549 if (VRM->hasPhys(VirtReg)) {
550 LiveInterval &LI = LIS->getInterval(VirtReg);
551 Matrix->unassign(LI);
552 aboutToRemoveInterval(LI);
555 // Unassigned virtreg is probably in the priority queue.
556 // RegAllocBase will erase it after dequeueing.
560 void RAGreedy::LRE_WillShrinkVirtReg(unsigned VirtReg) {
561 if (!VRM->hasPhys(VirtReg))
564 // Register is assigned, put it back on the queue for reassignment.
565 LiveInterval &LI = LIS->getInterval(VirtReg);
566 Matrix->unassign(LI);
570 void RAGreedy::LRE_DidCloneVirtReg(unsigned New, unsigned Old) {
571 // Cloning a register we haven't even heard about yet? Just ignore it.
572 if (!ExtraRegInfo.inBounds(Old))
575 // LRE may clone a virtual register because dead code elimination causes it to
576 // be split into connected components. The new components are much smaller
577 // than the original, so they should get a new chance at being assigned.
578 // same stage as the parent.
579 ExtraRegInfo[Old].Stage = RS_Assign;
580 ExtraRegInfo.grow(New);
581 ExtraRegInfo[New] = ExtraRegInfo[Old];
584 void RAGreedy::releaseMemory() {
585 SpillerInstance.reset();
586 ExtraRegInfo.clear();
590 void RAGreedy::enqueue(LiveInterval *LI) { enqueue(Queue, LI); }
592 void RAGreedy::enqueue(PQueue &CurQueue, LiveInterval *LI) {
593 // Prioritize live ranges by size, assigning larger ranges first.
594 // The queue holds (size, reg) pairs.
595 const unsigned Size = LI->getSize();
596 const unsigned Reg = LI->reg;
597 assert(TargetRegisterInfo::isVirtualRegister(Reg) &&
598 "Can only enqueue virtual registers");
601 ExtraRegInfo.grow(Reg);
602 if (ExtraRegInfo[Reg].Stage == RS_New)
603 ExtraRegInfo[Reg].Stage = RS_Assign;
605 if (ExtraRegInfo[Reg].Stage == RS_Split) {
606 // Unsplit ranges that couldn't be allocated immediately are deferred until
607 // everything else has been allocated.
609 } else if (ExtraRegInfo[Reg].Stage == RS_Memory) {
610 // Memory operand should be considered last.
611 // Change the priority such that Memory operand are assigned in
612 // the reverse order that they came in.
613 // TODO: Make this a member variable and probably do something about hints.
614 static unsigned MemOp = 0;
617 // Giant live ranges fall back to the global assignment heuristic, which
618 // prevents excessive spilling in pathological cases.
619 bool ReverseLocal = TRI->reverseLocalAssignment();
620 const TargetRegisterClass &RC = *MRI->getRegClass(Reg);
621 bool ForceGlobal = !ReverseLocal &&
622 (Size / SlotIndex::InstrDist) > (2 * RC.getNumRegs());
624 if (ExtraRegInfo[Reg].Stage == RS_Assign && !ForceGlobal && !LI->empty() &&
625 LIS->intervalIsInOneMBB(*LI)) {
626 // Allocate original local ranges in linear instruction order. Since they
627 // are singly defined, this produces optimal coloring in the absence of
628 // global interference and other constraints.
630 Prio = LI->beginIndex().getInstrDistance(Indexes->getLastIndex());
632 // Allocating bottom up may allow many short LRGs to be assigned first
633 // to one of the cheap registers. This could be much faster for very
634 // large blocks on targets with many physical registers.
635 Prio = Indexes->getZeroIndex().getInstrDistance(LI->endIndex());
637 Prio |= RC.AllocationPriority << 24;
639 // Allocate global and split ranges in long->short order. Long ranges that
640 // don't fit should be spilled (or split) ASAP so they don't create
641 // interference. Mark a bit to prioritize global above local ranges.
642 Prio = (1u << 29) + Size;
644 // Mark a higher bit to prioritize global and local above RS_Split.
647 // Boost ranges that have a physical register hint.
648 if (VRM->hasKnownPreference(Reg))
651 // The virtual register number is a tie breaker for same-sized ranges.
652 // Give lower vreg numbers higher priority to assign them first.
653 CurQueue.push(std::make_pair(Prio, ~Reg));
656 LiveInterval *RAGreedy::dequeue() { return dequeue(Queue); }
658 LiveInterval *RAGreedy::dequeue(PQueue &CurQueue) {
659 if (CurQueue.empty())
661 LiveInterval *LI = &LIS->getInterval(~CurQueue.top().second);
666 //===----------------------------------------------------------------------===//
668 //===----------------------------------------------------------------------===//
670 /// tryAssign - Try to assign VirtReg to an available register.
671 unsigned RAGreedy::tryAssign(LiveInterval &VirtReg,
672 AllocationOrder &Order,
673 SmallVectorImpl<unsigned> &NewVRegs) {
676 while ((PhysReg = Order.next()))
677 if (!Matrix->checkInterference(VirtReg, PhysReg))
679 if (!PhysReg || Order.isHint())
682 // PhysReg is available, but there may be a better choice.
684 // If we missed a simple hint, try to cheaply evict interference from the
685 // preferred register.
686 if (unsigned Hint = MRI->getSimpleHint(VirtReg.reg))
687 if (Order.isHint(Hint)) {
688 DEBUG(dbgs() << "missed hint " << PrintReg(Hint, TRI) << '\n');
689 EvictionCost MaxCost;
690 MaxCost.setBrokenHints(1);
691 if (canEvictInterference(VirtReg, Hint, true, MaxCost)) {
692 evictInterference(VirtReg, Hint, NewVRegs);
695 // Record the missed hint, we may be able to recover
696 // at the end if the surrounding allocation changed.
697 SetOfBrokenHints.insert(&VirtReg);
700 // Try to evict interference from a cheaper alternative.
701 unsigned Cost = TRI->getCostPerUse(PhysReg);
703 // Most registers have 0 additional cost.
707 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " is available at cost " << Cost
709 unsigned CheapReg = tryEvict(VirtReg, Order, NewVRegs, Cost);
710 return CheapReg ? CheapReg : PhysReg;
713 //===----------------------------------------------------------------------===//
714 // Interference eviction
715 //===----------------------------------------------------------------------===//
717 unsigned RAGreedy::canReassign(LiveInterval &VirtReg, unsigned PrevReg) {
718 AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo, Matrix);
720 while ((PhysReg = Order.next())) {
721 if (PhysReg == PrevReg)
724 MCRegUnitIterator Units(PhysReg, TRI);
725 for (; Units.isValid(); ++Units) {
726 // Instantiate a "subquery", not to be confused with the Queries array.
727 LiveIntervalUnion::Query subQ(VirtReg, Matrix->getLiveUnions()[*Units]);
728 if (subQ.checkInterference())
731 // If no units have interference, break out with the current PhysReg.
732 if (!Units.isValid())
736 DEBUG(dbgs() << "can reassign: " << VirtReg << " from "
737 << PrintReg(PrevReg, TRI) << " to " << PrintReg(PhysReg, TRI)
742 /// shouldEvict - determine if A should evict the assigned live range B. The
743 /// eviction policy defined by this function together with the allocation order
744 /// defined by enqueue() decides which registers ultimately end up being split
747 /// Cascade numbers are used to prevent infinite loops if this function is a
750 /// @param A The live range to be assigned.
751 /// @param IsHint True when A is about to be assigned to its preferred
753 /// @param B The live range to be evicted.
754 /// @param BreaksHint True when B is already assigned to its preferred register.
755 bool RAGreedy::shouldEvict(LiveInterval &A, bool IsHint,
756 LiveInterval &B, bool BreaksHint) {
757 bool CanSplit = getStage(B) < RS_Spill;
759 // Be fairly aggressive about following hints as long as the evictee can be
761 if (CanSplit && IsHint && !BreaksHint)
764 if (A.weight > B.weight) {
765 DEBUG(dbgs() << "should evict: " << B << " w= " << B.weight << '\n');
771 /// canEvictInterference - Return true if all interferences between VirtReg and
772 /// PhysReg can be evicted.
774 /// @param VirtReg Live range that is about to be assigned.
775 /// @param PhysReg Desired register for assignment.
776 /// @param IsHint True when PhysReg is VirtReg's preferred register.
777 /// @param MaxCost Only look for cheaper candidates and update with new cost
778 /// when returning true.
779 /// @returns True when interference can be evicted cheaper than MaxCost.
780 bool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg,
781 bool IsHint, EvictionCost &MaxCost) {
782 // It is only possible to evict virtual register interference.
783 if (Matrix->checkInterference(VirtReg, PhysReg) > LiveRegMatrix::IK_VirtReg)
786 bool IsLocal = LIS->intervalIsInOneMBB(VirtReg);
788 // Find VirtReg's cascade number. This will be unassigned if VirtReg was never
789 // involved in an eviction before. If a cascade number was assigned, deny
790 // evicting anything with the same or a newer cascade number. This prevents
791 // infinite eviction loops.
793 // This works out so a register without a cascade number is allowed to evict
794 // anything, and it can be evicted by anything.
795 unsigned Cascade = ExtraRegInfo[VirtReg.reg].Cascade;
797 Cascade = NextCascade;
800 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
801 LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units);
802 // If there is 10 or more interferences, chances are one is heavier.
803 if (Q.collectInterferingVRegs(10) >= 10)
806 // Check if any interfering live range is heavier than MaxWeight.
807 for (unsigned i = Q.interferingVRegs().size(); i; --i) {
808 LiveInterval *Intf = Q.interferingVRegs()[i - 1];
809 assert(TargetRegisterInfo::isVirtualRegister(Intf->reg) &&
810 "Only expecting virtual register interference from query");
811 // Never evict spill products. They cannot split or spill.
812 if (getStage(*Intf) == RS_Done)
814 // Once a live range becomes small enough, it is urgent that we find a
815 // register for it. This is indicated by an infinite spill weight. These
816 // urgent live ranges get to evict almost anything.
818 // Also allow urgent evictions of unspillable ranges from a strictly
819 // larger allocation order.
820 bool Urgent = !VirtReg.isSpillable() &&
821 (Intf->isSpillable() ||
822 RegClassInfo.getNumAllocatableRegs(MRI->getRegClass(VirtReg.reg)) <
823 RegClassInfo.getNumAllocatableRegs(MRI->getRegClass(Intf->reg)));
824 // Only evict older cascades or live ranges without a cascade.
825 unsigned IntfCascade = ExtraRegInfo[Intf->reg].Cascade;
826 if (Cascade <= IntfCascade) {
829 // We permit breaking cascades for urgent evictions. It should be the
830 // last resort, though, so make it really expensive.
831 Cost.BrokenHints += 10;
833 // Would this break a satisfied hint?
834 bool BreaksHint = VRM->hasPreferredPhys(Intf->reg);
835 // Update eviction cost.
836 Cost.BrokenHints += BreaksHint;
837 Cost.MaxWeight = std::max(Cost.MaxWeight, Intf->weight);
838 // Abort if this would be too expensive.
839 if (!(Cost < MaxCost))
843 // Apply the eviction policy for non-urgent evictions.
844 if (!shouldEvict(VirtReg, IsHint, *Intf, BreaksHint))
846 // If !MaxCost.isMax(), then we're just looking for a cheap register.
847 // Evicting another local live range in this case could lead to suboptimal
849 if (!MaxCost.isMax() && IsLocal && LIS->intervalIsInOneMBB(*Intf) &&
850 (!EnableLocalReassign || !canReassign(*Intf, PhysReg))) {
859 /// evictInterference - Evict any interferring registers that prevent VirtReg
860 /// from being assigned to Physreg. This assumes that canEvictInterference
862 void RAGreedy::evictInterference(LiveInterval &VirtReg, unsigned PhysReg,
863 SmallVectorImpl<unsigned> &NewVRegs) {
864 // Make sure that VirtReg has a cascade number, and assign that cascade
865 // number to every evicted register. These live ranges than then only be
866 // evicted by a newer cascade, preventing infinite loops.
867 unsigned Cascade = ExtraRegInfo[VirtReg.reg].Cascade;
869 Cascade = ExtraRegInfo[VirtReg.reg].Cascade = NextCascade++;
871 DEBUG(dbgs() << "evicting " << PrintReg(PhysReg, TRI)
872 << " interference: Cascade " << Cascade << '\n');
874 // Collect all interfering virtregs first.
875 SmallVector<LiveInterval*, 8> Intfs;
876 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
877 LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units);
878 // We usually have the interfering VRegs cached so collectInterferingVRegs()
879 // should be fast, we may need to recalculate if when different physregs
880 // overlap the same register unit so we had different SubRanges queried
882 Q.collectInterferingVRegs();
883 ArrayRef<LiveInterval*> IVR = Q.interferingVRegs();
884 Intfs.append(IVR.begin(), IVR.end());
887 // Evict them second. This will invalidate the queries.
888 for (unsigned i = 0, e = Intfs.size(); i != e; ++i) {
889 LiveInterval *Intf = Intfs[i];
890 // The same VirtReg may be present in multiple RegUnits. Skip duplicates.
891 if (!VRM->hasPhys(Intf->reg))
893 Matrix->unassign(*Intf);
894 assert((ExtraRegInfo[Intf->reg].Cascade < Cascade ||
895 VirtReg.isSpillable() < Intf->isSpillable()) &&
896 "Cannot decrease cascade number, illegal eviction");
897 ExtraRegInfo[Intf->reg].Cascade = Cascade;
899 NewVRegs.push_back(Intf->reg);
903 /// Returns true if the given \p PhysReg is a callee saved register and has not
904 /// been used for allocation yet.
905 bool RAGreedy::isUnusedCalleeSavedReg(unsigned PhysReg) const {
906 unsigned CSR = RegClassInfo.getLastCalleeSavedAlias(PhysReg);
910 return !Matrix->isPhysRegUsed(PhysReg);
913 /// tryEvict - Try to evict all interferences for a physreg.
914 /// @param VirtReg Currently unassigned virtual register.
915 /// @param Order Physregs to try.
916 /// @return Physreg to assign VirtReg, or 0.
917 unsigned RAGreedy::tryEvict(LiveInterval &VirtReg,
918 AllocationOrder &Order,
919 SmallVectorImpl<unsigned> &NewVRegs,
920 unsigned CostPerUseLimit) {
921 NamedRegionTimer T("evict", "Evict", TimerGroupName, TimerGroupDescription,
922 TimePassesIsEnabled);
924 // Keep track of the cheapest interference seen so far.
925 EvictionCost BestCost;
927 unsigned BestPhys = 0;
928 unsigned OrderLimit = Order.getOrder().size();
930 // When we are just looking for a reduced cost per use, don't break any
931 // hints, and only evict smaller spill weights.
932 if (CostPerUseLimit < ~0u) {
933 BestCost.BrokenHints = 0;
934 BestCost.MaxWeight = VirtReg.weight;
936 // Check of any registers in RC are below CostPerUseLimit.
937 const TargetRegisterClass *RC = MRI->getRegClass(VirtReg.reg);
938 unsigned MinCost = RegClassInfo.getMinCost(RC);
939 if (MinCost >= CostPerUseLimit) {
940 DEBUG(dbgs() << TRI->getRegClassName(RC) << " minimum cost = " << MinCost
941 << ", no cheaper registers to be found.\n");
945 // It is normal for register classes to have a long tail of registers with
946 // the same cost. We don't need to look at them if they're too expensive.
947 if (TRI->getCostPerUse(Order.getOrder().back()) >= CostPerUseLimit) {
948 OrderLimit = RegClassInfo.getLastCostChange(RC);
949 DEBUG(dbgs() << "Only trying the first " << OrderLimit << " regs.\n");
954 while (unsigned PhysReg = Order.next(OrderLimit)) {
955 if (TRI->getCostPerUse(PhysReg) >= CostPerUseLimit)
957 // The first use of a callee-saved register in a function has cost 1.
958 // Don't start using a CSR when the CostPerUseLimit is low.
959 if (CostPerUseLimit == 1 && isUnusedCalleeSavedReg(PhysReg)) {
960 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " would clobber CSR "
961 << PrintReg(RegClassInfo.getLastCalleeSavedAlias(PhysReg), TRI)
966 if (!canEvictInterference(VirtReg, PhysReg, false, BestCost))
972 // Stop if the hint can be used.
980 evictInterference(VirtReg, BestPhys, NewVRegs);
984 //===----------------------------------------------------------------------===//
986 //===----------------------------------------------------------------------===//
988 /// addSplitConstraints - Fill out the SplitConstraints vector based on the
989 /// interference pattern in Physreg and its aliases. Add the constraints to
990 /// SpillPlacement and return the static cost of this split in Cost, assuming
991 /// that all preferences in SplitConstraints are met.
992 /// Return false if there are no bundles with positive bias.
993 bool RAGreedy::addSplitConstraints(InterferenceCache::Cursor Intf,
994 BlockFrequency &Cost) {
995 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
997 // Reset interference dependent info.
998 SplitConstraints.resize(UseBlocks.size());
999 BlockFrequency StaticCost = 0;
1000 for (unsigned i = 0; i != UseBlocks.size(); ++i) {
1001 const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
1002 SpillPlacement::BlockConstraint &BC = SplitConstraints[i];
1004 BC.Number = BI.MBB->getNumber();
1005 Intf.moveToBlock(BC.Number);
1006 BC.Entry = BI.LiveIn ? SpillPlacement::PrefReg : SpillPlacement::DontCare;
1007 BC.Exit = BI.LiveOut ? SpillPlacement::PrefReg : SpillPlacement::DontCare;
1008 BC.ChangesValue = BI.FirstDef.isValid();
1010 if (!Intf.hasInterference())
1013 // Number of spill code instructions to insert.
1016 // Interference for the live-in value.
1018 if (Intf.first() <= Indexes->getMBBStartIdx(BC.Number)) {
1019 BC.Entry = SpillPlacement::MustSpill;
1021 } else if (Intf.first() < BI.FirstInstr) {
1022 BC.Entry = SpillPlacement::PrefSpill;
1024 } else if (Intf.first() < BI.LastInstr) {
1029 // Interference for the live-out value.
1031 if (Intf.last() >= SA->getLastSplitPoint(BC.Number)) {
1032 BC.Exit = SpillPlacement::MustSpill;
1034 } else if (Intf.last() > BI.LastInstr) {
1035 BC.Exit = SpillPlacement::PrefSpill;
1037 } else if (Intf.last() > BI.FirstInstr) {
1042 // Accumulate the total frequency of inserted spill code.
1044 StaticCost += SpillPlacer->getBlockFrequency(BC.Number);
1048 // Add constraints for use-blocks. Note that these are the only constraints
1049 // that may add a positive bias, it is downhill from here.
1050 SpillPlacer->addConstraints(SplitConstraints);
1051 return SpillPlacer->scanActiveBundles();
1054 /// addThroughConstraints - Add constraints and links to SpillPlacer from the
1055 /// live-through blocks in Blocks.
1056 void RAGreedy::addThroughConstraints(InterferenceCache::Cursor Intf,
1057 ArrayRef<unsigned> Blocks) {
1058 const unsigned GroupSize = 8;
1059 SpillPlacement::BlockConstraint BCS[GroupSize];
1060 unsigned TBS[GroupSize];
1061 unsigned B = 0, T = 0;
1063 for (unsigned i = 0; i != Blocks.size(); ++i) {
1064 unsigned Number = Blocks[i];
1065 Intf.moveToBlock(Number);
1067 if (!Intf.hasInterference()) {
1068 assert(T < GroupSize && "Array overflow");
1070 if (++T == GroupSize) {
1071 SpillPlacer->addLinks(makeArrayRef(TBS, T));
1077 assert(B < GroupSize && "Array overflow");
1078 BCS[B].Number = Number;
1080 // Interference for the live-in value.
1081 if (Intf.first() <= Indexes->getMBBStartIdx(Number))
1082 BCS[B].Entry = SpillPlacement::MustSpill;
1084 BCS[B].Entry = SpillPlacement::PrefSpill;
1086 // Interference for the live-out value.
1087 if (Intf.last() >= SA->getLastSplitPoint(Number))
1088 BCS[B].Exit = SpillPlacement::MustSpill;
1090 BCS[B].Exit = SpillPlacement::PrefSpill;
1092 if (++B == GroupSize) {
1093 SpillPlacer->addConstraints(makeArrayRef(BCS, B));
1098 SpillPlacer->addConstraints(makeArrayRef(BCS, B));
1099 SpillPlacer->addLinks(makeArrayRef(TBS, T));
1102 void RAGreedy::growRegion(GlobalSplitCandidate &Cand) {
1103 // Keep track of through blocks that have not been added to SpillPlacer.
1104 BitVector Todo = SA->getThroughBlocks();
1105 SmallVectorImpl<unsigned> &ActiveBlocks = Cand.ActiveBlocks;
1106 unsigned AddedTo = 0;
1108 unsigned Visited = 0;
1112 ArrayRef<unsigned> NewBundles = SpillPlacer->getRecentPositive();
1113 // Find new through blocks in the periphery of PrefRegBundles.
1114 for (int i = 0, e = NewBundles.size(); i != e; ++i) {
1115 unsigned Bundle = NewBundles[i];
1116 // Look at all blocks connected to Bundle in the full graph.
1117 ArrayRef<unsigned> Blocks = Bundles->getBlocks(Bundle);
1118 for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end();
1120 unsigned Block = *I;
1121 if (!Todo.test(Block))
1124 // This is a new through block. Add it to SpillPlacer later.
1125 ActiveBlocks.push_back(Block);
1131 // Any new blocks to add?
1132 if (ActiveBlocks.size() == AddedTo)
1135 // Compute through constraints from the interference, or assume that all
1136 // through blocks prefer spilling when forming compact regions.
1137 auto NewBlocks = makeArrayRef(ActiveBlocks).slice(AddedTo);
1139 addThroughConstraints(Cand.Intf, NewBlocks);
1141 // Provide a strong negative bias on through blocks to prevent unwanted
1142 // liveness on loop backedges.
1143 SpillPlacer->addPrefSpill(NewBlocks, /* Strong= */ true);
1144 AddedTo = ActiveBlocks.size();
1146 // Perhaps iterating can enable more bundles?
1147 SpillPlacer->iterate();
1149 DEBUG(dbgs() << ", v=" << Visited);
1152 /// calcCompactRegion - Compute the set of edge bundles that should be live
1153 /// when splitting the current live range into compact regions. Compact
1154 /// regions can be computed without looking at interference. They are the
1155 /// regions formed by removing all the live-through blocks from the live range.
1157 /// Returns false if the current live range is already compact, or if the
1158 /// compact regions would form single block regions anyway.
1159 bool RAGreedy::calcCompactRegion(GlobalSplitCandidate &Cand) {
1160 // Without any through blocks, the live range is already compact.
1161 if (!SA->getNumThroughBlocks())
1164 // Compact regions don't correspond to any physreg.
1165 Cand.reset(IntfCache, 0);
1167 DEBUG(dbgs() << "Compact region bundles");
1169 // Use the spill placer to determine the live bundles. GrowRegion pretends
1170 // that all the through blocks have interference when PhysReg is unset.
1171 SpillPlacer->prepare(Cand.LiveBundles);
1173 // The static split cost will be zero since Cand.Intf reports no interference.
1174 BlockFrequency Cost;
1175 if (!addSplitConstraints(Cand.Intf, Cost)) {
1176 DEBUG(dbgs() << ", none.\n");
1181 SpillPlacer->finish();
1183 if (!Cand.LiveBundles.any()) {
1184 DEBUG(dbgs() << ", none.\n");
1189 for (int i : Cand.LiveBundles.set_bits())
1190 dbgs() << " EB#" << i;
1196 /// calcSpillCost - Compute how expensive it would be to split the live range in
1197 /// SA around all use blocks instead of forming bundle regions.
1198 BlockFrequency RAGreedy::calcSpillCost() {
1199 BlockFrequency Cost = 0;
1200 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
1201 for (unsigned i = 0; i != UseBlocks.size(); ++i) {
1202 const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
1203 unsigned Number = BI.MBB->getNumber();
1204 // We normally only need one spill instruction - a load or a store.
1205 Cost += SpillPlacer->getBlockFrequency(Number);
1207 // Unless the value is redefined in the block.
1208 if (BI.LiveIn && BI.LiveOut && BI.FirstDef)
1209 Cost += SpillPlacer->getBlockFrequency(Number);
1214 /// calcGlobalSplitCost - Return the global split cost of following the split
1215 /// pattern in LiveBundles. This cost should be added to the local cost of the
1216 /// interference pattern in SplitConstraints.
1218 BlockFrequency RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand) {
1219 BlockFrequency GlobalCost = 0;
1220 const BitVector &LiveBundles = Cand.LiveBundles;
1221 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
1222 for (unsigned i = 0; i != UseBlocks.size(); ++i) {
1223 const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
1224 SpillPlacement::BlockConstraint &BC = SplitConstraints[i];
1225 bool RegIn = LiveBundles[Bundles->getBundle(BC.Number, false)];
1226 bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, true)];
1230 Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg);
1232 Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg);
1234 GlobalCost += SpillPlacer->getBlockFrequency(BC.Number);
1237 for (unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) {
1238 unsigned Number = Cand.ActiveBlocks[i];
1239 bool RegIn = LiveBundles[Bundles->getBundle(Number, false)];
1240 bool RegOut = LiveBundles[Bundles->getBundle(Number, true)];
1241 if (!RegIn && !RegOut)
1243 if (RegIn && RegOut) {
1244 // We need double spill code if this block has interference.
1245 Cand.Intf.moveToBlock(Number);
1246 if (Cand.Intf.hasInterference()) {
1247 GlobalCost += SpillPlacer->getBlockFrequency(Number);
1248 GlobalCost += SpillPlacer->getBlockFrequency(Number);
1252 // live-in / stack-out or stack-in live-out.
1253 GlobalCost += SpillPlacer->getBlockFrequency(Number);
1258 /// splitAroundRegion - Split the current live range around the regions
1259 /// determined by BundleCand and GlobalCand.
1261 /// Before calling this function, GlobalCand and BundleCand must be initialized
1262 /// so each bundle is assigned to a valid candidate, or NoCand for the
1263 /// stack-bound bundles. The shared SA/SE SplitAnalysis and SplitEditor
1264 /// objects must be initialized for the current live range, and intervals
1265 /// created for the used candidates.
1267 /// @param LREdit The LiveRangeEdit object handling the current split.
1268 /// @param UsedCands List of used GlobalCand entries. Every BundleCand value
1269 /// must appear in this list.
1270 void RAGreedy::splitAroundRegion(LiveRangeEdit &LREdit,
1271 ArrayRef<unsigned> UsedCands) {
1272 // These are the intervals created for new global ranges. We may create more
1273 // intervals for local ranges.
1274 const unsigned NumGlobalIntvs = LREdit.size();
1275 DEBUG(dbgs() << "splitAroundRegion with " << NumGlobalIntvs << " globals.\n");
1276 assert(NumGlobalIntvs && "No global intervals configured");
1278 // Isolate even single instructions when dealing with a proper sub-class.
1279 // That guarantees register class inflation for the stack interval because it
1281 unsigned Reg = SA->getParent().reg;
1282 bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg));
1284 // First handle all the blocks with uses.
1285 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
1286 for (unsigned i = 0; i != UseBlocks.size(); ++i) {
1287 const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
1288 unsigned Number = BI.MBB->getNumber();
1289 unsigned IntvIn = 0, IntvOut = 0;
1290 SlotIndex IntfIn, IntfOut;
1292 unsigned CandIn = BundleCand[Bundles->getBundle(Number, false)];
1293 if (CandIn != NoCand) {
1294 GlobalSplitCandidate &Cand = GlobalCand[CandIn];
1295 IntvIn = Cand.IntvIdx;
1296 Cand.Intf.moveToBlock(Number);
1297 IntfIn = Cand.Intf.first();
1301 unsigned CandOut = BundleCand[Bundles->getBundle(Number, true)];
1302 if (CandOut != NoCand) {
1303 GlobalSplitCandidate &Cand = GlobalCand[CandOut];
1304 IntvOut = Cand.IntvIdx;
1305 Cand.Intf.moveToBlock(Number);
1306 IntfOut = Cand.Intf.last();
1310 // Create separate intervals for isolated blocks with multiple uses.
1311 if (!IntvIn && !IntvOut) {
1312 DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " isolated.\n");
1313 if (SA->shouldSplitSingleBlock(BI, SingleInstrs))
1314 SE->splitSingleBlock(BI);
1318 if (IntvIn && IntvOut)
1319 SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut);
1321 SE->splitRegInBlock(BI, IntvIn, IntfIn);
1323 SE->splitRegOutBlock(BI, IntvOut, IntfOut);
1326 // Handle live-through blocks. The relevant live-through blocks are stored in
1327 // the ActiveBlocks list with each candidate. We need to filter out
1329 BitVector Todo = SA->getThroughBlocks();
1330 for (unsigned c = 0; c != UsedCands.size(); ++c) {
1331 ArrayRef<unsigned> Blocks = GlobalCand[UsedCands[c]].ActiveBlocks;
1332 for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
1333 unsigned Number = Blocks[i];
1334 if (!Todo.test(Number))
1338 unsigned IntvIn = 0, IntvOut = 0;
1339 SlotIndex IntfIn, IntfOut;
1341 unsigned CandIn = BundleCand[Bundles->getBundle(Number, false)];
1342 if (CandIn != NoCand) {
1343 GlobalSplitCandidate &Cand = GlobalCand[CandIn];
1344 IntvIn = Cand.IntvIdx;
1345 Cand.Intf.moveToBlock(Number);
1346 IntfIn = Cand.Intf.first();
1349 unsigned CandOut = BundleCand[Bundles->getBundle(Number, true)];
1350 if (CandOut != NoCand) {
1351 GlobalSplitCandidate &Cand = GlobalCand[CandOut];
1352 IntvOut = Cand.IntvIdx;
1353 Cand.Intf.moveToBlock(Number);
1354 IntfOut = Cand.Intf.last();
1356 if (!IntvIn && !IntvOut)
1358 SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut);
1364 SmallVector<unsigned, 8> IntvMap;
1365 SE->finish(&IntvMap);
1366 DebugVars->splitRegister(Reg, LREdit.regs(), *LIS);
1368 ExtraRegInfo.resize(MRI->getNumVirtRegs());
1369 unsigned OrigBlocks = SA->getNumLiveBlocks();
1371 // Sort out the new intervals created by splitting. We get four kinds:
1372 // - Remainder intervals should not be split again.
1373 // - Candidate intervals can be assigned to Cand.PhysReg.
1374 // - Block-local splits are candidates for local splitting.
1375 // - DCE leftovers should go back on the queue.
1376 for (unsigned i = 0, e = LREdit.size(); i != e; ++i) {
1377 LiveInterval &Reg = LIS->getInterval(LREdit.get(i));
1379 // Ignore old intervals from DCE.
1380 if (getStage(Reg) != RS_New)
1383 // Remainder interval. Don't try splitting again, spill if it doesn't
1385 if (IntvMap[i] == 0) {
1386 setStage(Reg, RS_Spill);
1390 // Global intervals. Allow repeated splitting as long as the number of live
1391 // blocks is strictly decreasing.
1392 if (IntvMap[i] < NumGlobalIntvs) {
1393 if (SA->countLiveBlocks(&Reg) >= OrigBlocks) {
1394 DEBUG(dbgs() << "Main interval covers the same " << OrigBlocks
1395 << " blocks as original.\n");
1396 // Don't allow repeated splitting as a safe guard against looping.
1397 setStage(Reg, RS_Split2);
1402 // Other intervals are treated as new. This includes local intervals created
1403 // for blocks with multiple uses, and anything created by DCE.
1407 MF->verify(this, "After splitting live range around region");
1410 unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
1411 SmallVectorImpl<unsigned> &NewVRegs) {
1412 unsigned NumCands = 0;
1413 BlockFrequency BestCost;
1415 // Check if we can split this live range around a compact region.
1416 bool HasCompact = calcCompactRegion(GlobalCand.front());
1418 // Yes, keep GlobalCand[0] as the compact region candidate.
1420 BestCost = BlockFrequency::getMaxFrequency();
1422 // No benefit from the compact region, our fallback will be per-block
1423 // splitting. Make sure we find a solution that is cheaper than spilling.
1424 BestCost = calcSpillCost();
1425 DEBUG(dbgs() << "Cost of isolating all blocks = ";
1426 MBFI->printBlockFreq(dbgs(), BestCost) << '\n');
1430 calculateRegionSplitCost(VirtReg, Order, BestCost, NumCands,
1431 false/*IgnoreCSR*/);
1433 // No solutions found, fall back to single block splitting.
1434 if (!HasCompact && BestCand == NoCand)
1437 return doRegionSplit(VirtReg, BestCand, HasCompact, NewVRegs);
1440 unsigned RAGreedy::calculateRegionSplitCost(LiveInterval &VirtReg,
1441 AllocationOrder &Order,
1442 BlockFrequency &BestCost,
1445 unsigned BestCand = NoCand;
1447 while (unsigned PhysReg = Order.next()) {
1448 if (IgnoreCSR && isUnusedCalleeSavedReg(PhysReg))
1451 // Discard bad candidates before we run out of interference cache cursors.
1452 // This will only affect register classes with a lot of registers (>32).
1453 if (NumCands == IntfCache.getMaxCursors()) {
1454 unsigned WorstCount = ~0u;
1456 for (unsigned i = 0; i != NumCands; ++i) {
1457 if (i == BestCand || !GlobalCand[i].PhysReg)
1459 unsigned Count = GlobalCand[i].LiveBundles.count();
1460 if (Count < WorstCount) {
1466 GlobalCand[Worst] = GlobalCand[NumCands];
1467 if (BestCand == NumCands)
1471 if (GlobalCand.size() <= NumCands)
1472 GlobalCand.resize(NumCands+1);
1473 GlobalSplitCandidate &Cand = GlobalCand[NumCands];
1474 Cand.reset(IntfCache, PhysReg);
1476 SpillPlacer->prepare(Cand.LiveBundles);
1477 BlockFrequency Cost;
1478 if (!addSplitConstraints(Cand.Intf, Cost)) {
1479 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tno positive bundles\n");
1482 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tstatic = ";
1483 MBFI->printBlockFreq(dbgs(), Cost));
1484 if (Cost >= BestCost) {
1486 if (BestCand == NoCand)
1487 dbgs() << " worse than no bundles\n";
1489 dbgs() << " worse than "
1490 << PrintReg(GlobalCand[BestCand].PhysReg, TRI) << '\n';
1496 SpillPlacer->finish();
1498 // No live bundles, defer to splitSingleBlocks().
1499 if (!Cand.LiveBundles.any()) {
1500 DEBUG(dbgs() << " no bundles.\n");
1504 Cost += calcGlobalSplitCost(Cand);
1506 dbgs() << ", total = "; MBFI->printBlockFreq(dbgs(), Cost)
1508 for (int i : Cand.LiveBundles.set_bits())
1509 dbgs() << " EB#" << i;
1512 if (Cost < BestCost) {
1513 BestCand = NumCands;
1521 unsigned RAGreedy::doRegionSplit(LiveInterval &VirtReg, unsigned BestCand,
1523 SmallVectorImpl<unsigned> &NewVRegs) {
1524 SmallVector<unsigned, 8> UsedCands;
1525 // Prepare split editor.
1526 LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);
1527 SE->reset(LREdit, SplitSpillMode);
1529 // Assign all edge bundles to the preferred candidate, or NoCand.
1530 BundleCand.assign(Bundles->getNumBundles(), NoCand);
1532 // Assign bundles for the best candidate region.
1533 if (BestCand != NoCand) {
1534 GlobalSplitCandidate &Cand = GlobalCand[BestCand];
1535 if (unsigned B = Cand.getBundles(BundleCand, BestCand)) {
1536 UsedCands.push_back(BestCand);
1537 Cand.IntvIdx = SE->openIntv();
1538 DEBUG(dbgs() << "Split for " << PrintReg(Cand.PhysReg, TRI) << " in "
1539 << B << " bundles, intv " << Cand.IntvIdx << ".\n");
1544 // Assign bundles for the compact region.
1546 GlobalSplitCandidate &Cand = GlobalCand.front();
1547 assert(!Cand.PhysReg && "Compact region has no physreg");
1548 if (unsigned B = Cand.getBundles(BundleCand, 0)) {
1549 UsedCands.push_back(0);
1550 Cand.IntvIdx = SE->openIntv();
1551 DEBUG(dbgs() << "Split for compact region in " << B << " bundles, intv "
1552 << Cand.IntvIdx << ".\n");
1557 splitAroundRegion(LREdit, UsedCands);
1561 //===----------------------------------------------------------------------===//
1562 // Per-Block Splitting
1563 //===----------------------------------------------------------------------===//
1565 /// tryBlockSplit - Split a global live range around every block with uses. This
1566 /// creates a lot of local live ranges, that will be split by tryLocalSplit if
1567 /// they don't allocate.
1568 unsigned RAGreedy::tryBlockSplit(LiveInterval &VirtReg, AllocationOrder &Order,
1569 SmallVectorImpl<unsigned> &NewVRegs) {
1570 assert(&SA->getParent() == &VirtReg && "Live range wasn't analyzed");
1571 unsigned Reg = VirtReg.reg;
1572 bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg));
1573 LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);
1574 SE->reset(LREdit, SplitSpillMode);
1575 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
1576 for (unsigned i = 0; i != UseBlocks.size(); ++i) {
1577 const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
1578 if (SA->shouldSplitSingleBlock(BI, SingleInstrs))
1579 SE->splitSingleBlock(BI);
1581 // No blocks were split.
1585 // We did split for some blocks.
1586 SmallVector<unsigned, 8> IntvMap;
1587 SE->finish(&IntvMap);
1589 // Tell LiveDebugVariables about the new ranges.
1590 DebugVars->splitRegister(Reg, LREdit.regs(), *LIS);
1592 ExtraRegInfo.resize(MRI->getNumVirtRegs());
1594 // Sort out the new intervals created by splitting. The remainder interval
1595 // goes straight to spilling, the new local ranges get to stay RS_New.
1596 for (unsigned i = 0, e = LREdit.size(); i != e; ++i) {
1597 LiveInterval &LI = LIS->getInterval(LREdit.get(i));
1598 if (getStage(LI) == RS_New && IntvMap[i] == 0)
1599 setStage(LI, RS_Spill);
1603 MF->verify(this, "After splitting live range around basic blocks");
1607 //===----------------------------------------------------------------------===//
1608 // Per-Instruction Splitting
1609 //===----------------------------------------------------------------------===//
1611 /// Get the number of allocatable registers that match the constraints of \p Reg
1612 /// on \p MI and that are also in \p SuperRC.
1613 static unsigned getNumAllocatableRegsForConstraints(
1614 const MachineInstr *MI, unsigned Reg, const TargetRegisterClass *SuperRC,
1615 const TargetInstrInfo *TII, const TargetRegisterInfo *TRI,
1616 const RegisterClassInfo &RCI) {
1617 assert(SuperRC && "Invalid register class");
1619 const TargetRegisterClass *ConstrainedRC =
1620 MI->getRegClassConstraintEffectForVReg(Reg, SuperRC, TII, TRI,
1621 /* ExploreBundle */ true);
1624 return RCI.getNumAllocatableRegs(ConstrainedRC);
1627 /// tryInstructionSplit - Split a live range around individual instructions.
1628 /// This is normally not worthwhile since the spiller is doing essentially the
1629 /// same thing. However, when the live range is in a constrained register
1630 /// class, it may help to insert copies such that parts of the live range can
1631 /// be moved to a larger register class.
1633 /// This is similar to spilling to a larger register class.
1635 RAGreedy::tryInstructionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
1636 SmallVectorImpl<unsigned> &NewVRegs) {
1637 const TargetRegisterClass *CurRC = MRI->getRegClass(VirtReg.reg);
1638 // There is no point to this if there are no larger sub-classes.
1639 if (!RegClassInfo.isProperSubClass(CurRC))
1642 // Always enable split spill mode, since we're effectively spilling to a
1644 LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);
1645 SE->reset(LREdit, SplitEditor::SM_Size);
1647 ArrayRef<SlotIndex> Uses = SA->getUseSlots();
1648 if (Uses.size() <= 1)
1651 DEBUG(dbgs() << "Split around " << Uses.size() << " individual instrs.\n");
1653 const TargetRegisterClass *SuperRC =
1654 TRI->getLargestLegalSuperClass(CurRC, *MF);
1655 unsigned SuperRCNumAllocatableRegs = RCI.getNumAllocatableRegs(SuperRC);
1656 // Split around every non-copy instruction if this split will relax
1657 // the constraints on the virtual register.
1658 // Otherwise, splitting just inserts uncoalescable copies that do not help
1660 for (unsigned i = 0; i != Uses.size(); ++i) {
1661 if (const MachineInstr *MI = Indexes->getInstructionFromIndex(Uses[i]))
1662 if (MI->isFullCopy() ||
1663 SuperRCNumAllocatableRegs ==
1664 getNumAllocatableRegsForConstraints(MI, VirtReg.reg, SuperRC, TII,
1666 DEBUG(dbgs() << " skip:\t" << Uses[i] << '\t' << *MI);
1670 SlotIndex SegStart = SE->enterIntvBefore(Uses[i]);
1671 SlotIndex SegStop = SE->leaveIntvAfter(Uses[i]);
1672 SE->useIntv(SegStart, SegStop);
1675 if (LREdit.empty()) {
1676 DEBUG(dbgs() << "All uses were copies.\n");
1680 SmallVector<unsigned, 8> IntvMap;
1681 SE->finish(&IntvMap);
1682 DebugVars->splitRegister(VirtReg.reg, LREdit.regs(), *LIS);
1683 ExtraRegInfo.resize(MRI->getNumVirtRegs());
1685 // Assign all new registers to RS_Spill. This was the last chance.
1686 setStage(LREdit.begin(), LREdit.end(), RS_Spill);
1690 //===----------------------------------------------------------------------===//
1692 //===----------------------------------------------------------------------===//
1694 /// calcGapWeights - Compute the maximum spill weight that needs to be evicted
1695 /// in order to use PhysReg between two entries in SA->UseSlots.
1697 /// GapWeight[i] represents the gap between UseSlots[i] and UseSlots[i+1].
1699 void RAGreedy::calcGapWeights(unsigned PhysReg,
1700 SmallVectorImpl<float> &GapWeight) {
1701 assert(SA->getUseBlocks().size() == 1 && "Not a local interval");
1702 const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front();
1703 ArrayRef<SlotIndex> Uses = SA->getUseSlots();
1704 const unsigned NumGaps = Uses.size()-1;
1706 // Start and end points for the interference check.
1707 SlotIndex StartIdx =
1708 BI.LiveIn ? BI.FirstInstr.getBaseIndex() : BI.FirstInstr;
1710 BI.LiveOut ? BI.LastInstr.getBoundaryIndex() : BI.LastInstr;
1712 GapWeight.assign(NumGaps, 0.0f);
1714 // Add interference from each overlapping register.
1715 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
1716 if (!Matrix->query(const_cast<LiveInterval&>(SA->getParent()), *Units)
1717 .checkInterference())
1720 // We know that VirtReg is a continuous interval from FirstInstr to
1721 // LastInstr, so we don't need InterferenceQuery.
1723 // Interference that overlaps an instruction is counted in both gaps
1724 // surrounding the instruction. The exception is interference before
1725 // StartIdx and after StopIdx.
1727 LiveIntervalUnion::SegmentIter IntI =
1728 Matrix->getLiveUnions()[*Units] .find(StartIdx);
1729 for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) {
1730 // Skip the gaps before IntI.
1731 while (Uses[Gap+1].getBoundaryIndex() < IntI.start())
1732 if (++Gap == NumGaps)
1737 // Update the gaps covered by IntI.
1738 const float weight = IntI.value()->weight;
1739 for (; Gap != NumGaps; ++Gap) {
1740 GapWeight[Gap] = std::max(GapWeight[Gap], weight);
1741 if (Uses[Gap+1].getBaseIndex() >= IntI.stop())
1749 // Add fixed interference.
1750 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
1751 const LiveRange &LR = LIS->getRegUnit(*Units);
1752 LiveRange::const_iterator I = LR.find(StartIdx);
1753 LiveRange::const_iterator E = LR.end();
1755 // Same loop as above. Mark any overlapped gaps as HUGE_VALF.
1756 for (unsigned Gap = 0; I != E && I->start < StopIdx; ++I) {
1757 while (Uses[Gap+1].getBoundaryIndex() < I->start)
1758 if (++Gap == NumGaps)
1763 for (; Gap != NumGaps; ++Gap) {
1764 GapWeight[Gap] = huge_valf;
1765 if (Uses[Gap+1].getBaseIndex() >= I->end)
1774 /// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only
1777 unsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order,
1778 SmallVectorImpl<unsigned> &NewVRegs) {
1779 assert(SA->getUseBlocks().size() == 1 && "Not a local interval");
1780 const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front();
1782 // Note that it is possible to have an interval that is live-in or live-out
1783 // while only covering a single block - A phi-def can use undef values from
1784 // predecessors, and the block could be a single-block loop.
1785 // We don't bother doing anything clever about such a case, we simply assume
1786 // that the interval is continuous from FirstInstr to LastInstr. We should
1787 // make sure that we don't do anything illegal to such an interval, though.
1789 ArrayRef<SlotIndex> Uses = SA->getUseSlots();
1790 if (Uses.size() <= 2)
1792 const unsigned NumGaps = Uses.size()-1;
1795 dbgs() << "tryLocalSplit: ";
1796 for (unsigned i = 0, e = Uses.size(); i != e; ++i)
1797 dbgs() << ' ' << Uses[i];
1801 // If VirtReg is live across any register mask operands, compute a list of
1802 // gaps with register masks.
1803 SmallVector<unsigned, 8> RegMaskGaps;
1804 if (Matrix->checkRegMaskInterference(VirtReg)) {
1805 // Get regmask slots for the whole block.
1806 ArrayRef<SlotIndex> RMS = LIS->getRegMaskSlotsInBlock(BI.MBB->getNumber());
1807 DEBUG(dbgs() << RMS.size() << " regmasks in block:");
1808 // Constrain to VirtReg's live range.
1809 unsigned ri = std::lower_bound(RMS.begin(), RMS.end(),
1810 Uses.front().getRegSlot()) - RMS.begin();
1811 unsigned re = RMS.size();
1812 for (unsigned i = 0; i != NumGaps && ri != re; ++i) {
1813 // Look for Uses[i] <= RMS <= Uses[i+1].
1814 assert(!SlotIndex::isEarlierInstr(RMS[ri], Uses[i]));
1815 if (SlotIndex::isEarlierInstr(Uses[i+1], RMS[ri]))
1817 // Skip a regmask on the same instruction as the last use. It doesn't
1818 // overlap the live range.
1819 if (SlotIndex::isSameInstr(Uses[i+1], RMS[ri]) && i+1 == NumGaps)
1821 DEBUG(dbgs() << ' ' << RMS[ri] << ':' << Uses[i] << '-' << Uses[i+1]);
1822 RegMaskGaps.push_back(i);
1823 // Advance ri to the next gap. A regmask on one of the uses counts in
1825 while (ri != re && SlotIndex::isEarlierInstr(RMS[ri], Uses[i+1]))
1828 DEBUG(dbgs() << '\n');
1831 // Since we allow local split results to be split again, there is a risk of
1832 // creating infinite loops. It is tempting to require that the new live
1833 // ranges have less instructions than the original. That would guarantee
1834 // convergence, but it is too strict. A live range with 3 instructions can be
1835 // split 2+3 (including the COPY), and we want to allow that.
1837 // Instead we use these rules:
1839 // 1. Allow any split for ranges with getStage() < RS_Split2. (Except for the
1840 // noop split, of course).
1841 // 2. Require progress be made for ranges with getStage() == RS_Split2. All
1842 // the new ranges must have fewer instructions than before the split.
1843 // 3. New ranges with the same number of instructions are marked RS_Split2,
1844 // smaller ranges are marked RS_New.
1846 // These rules allow a 3 -> 2+3 split once, which we need. They also prevent
1847 // excessive splitting and infinite loops.
1849 bool ProgressRequired = getStage(VirtReg) >= RS_Split2;
1851 // Best split candidate.
1852 unsigned BestBefore = NumGaps;
1853 unsigned BestAfter = 0;
1856 const float blockFreq =
1857 SpillPlacer->getBlockFrequency(BI.MBB->getNumber()).getFrequency() *
1858 (1.0f / MBFI->getEntryFreq());
1859 SmallVector<float, 8> GapWeight;
1862 while (unsigned PhysReg = Order.next()) {
1863 // Keep track of the largest spill weight that would need to be evicted in
1864 // order to make use of PhysReg between UseSlots[i] and UseSlots[i+1].
1865 calcGapWeights(PhysReg, GapWeight);
1867 // Remove any gaps with regmask clobbers.
1868 if (Matrix->checkRegMaskInterference(VirtReg, PhysReg))
1869 for (unsigned i = 0, e = RegMaskGaps.size(); i != e; ++i)
1870 GapWeight[RegMaskGaps[i]] = huge_valf;
1872 // Try to find the best sequence of gaps to close.
1873 // The new spill weight must be larger than any gap interference.
1875 // We will split before Uses[SplitBefore] and after Uses[SplitAfter].
1876 unsigned SplitBefore = 0, SplitAfter = 1;
1878 // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]).
1879 // It is the spill weight that needs to be evicted.
1880 float MaxGap = GapWeight[0];
1883 // Live before/after split?
1884 const bool LiveBefore = SplitBefore != 0 || BI.LiveIn;
1885 const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut;
1887 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << ' '
1888 << Uses[SplitBefore] << '-' << Uses[SplitAfter]
1889 << " i=" << MaxGap);
1891 // Stop before the interval gets so big we wouldn't be making progress.
1892 if (!LiveBefore && !LiveAfter) {
1893 DEBUG(dbgs() << " all\n");
1896 // Should the interval be extended or shrunk?
1899 // How many gaps would the new range have?
1900 unsigned NewGaps = LiveBefore + SplitAfter - SplitBefore + LiveAfter;
1902 // Legally, without causing looping?
1903 bool Legal = !ProgressRequired || NewGaps < NumGaps;
1905 if (Legal && MaxGap < huge_valf) {
1906 // Estimate the new spill weight. Each instruction reads or writes the
1907 // register. Conservatively assume there are no read-modify-write
1910 // Try to guess the size of the new interval.
1911 const float EstWeight = normalizeSpillWeight(
1912 blockFreq * (NewGaps + 1),
1913 Uses[SplitBefore].distance(Uses[SplitAfter]) +
1914 (LiveBefore + LiveAfter) * SlotIndex::InstrDist,
1916 // Would this split be possible to allocate?
1917 // Never allocate all gaps, we wouldn't be making progress.
1918 DEBUG(dbgs() << " w=" << EstWeight);
1919 if (EstWeight * Hysteresis >= MaxGap) {
1921 float Diff = EstWeight - MaxGap;
1922 if (Diff > BestDiff) {
1923 DEBUG(dbgs() << " (best)");
1924 BestDiff = Hysteresis * Diff;
1925 BestBefore = SplitBefore;
1926 BestAfter = SplitAfter;
1933 if (++SplitBefore < SplitAfter) {
1934 DEBUG(dbgs() << " shrink\n");
1935 // Recompute the max when necessary.
1936 if (GapWeight[SplitBefore - 1] >= MaxGap) {
1937 MaxGap = GapWeight[SplitBefore];
1938 for (unsigned i = SplitBefore + 1; i != SplitAfter; ++i)
1939 MaxGap = std::max(MaxGap, GapWeight[i]);
1946 // Try to extend the interval.
1947 if (SplitAfter >= NumGaps) {
1948 DEBUG(dbgs() << " end\n");
1952 DEBUG(dbgs() << " extend\n");
1953 MaxGap = std::max(MaxGap, GapWeight[SplitAfter++]);
1957 // Didn't find any candidates?
1958 if (BestBefore == NumGaps)
1961 DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore]
1962 << '-' << Uses[BestAfter] << ", " << BestDiff
1963 << ", " << (BestAfter - BestBefore + 1) << " instrs\n");
1965 LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);
1969 SlotIndex SegStart = SE->enterIntvBefore(Uses[BestBefore]);
1970 SlotIndex SegStop = SE->leaveIntvAfter(Uses[BestAfter]);
1971 SE->useIntv(SegStart, SegStop);
1972 SmallVector<unsigned, 8> IntvMap;
1973 SE->finish(&IntvMap);
1974 DebugVars->splitRegister(VirtReg.reg, LREdit.regs(), *LIS);
1976 // If the new range has the same number of instructions as before, mark it as
1977 // RS_Split2 so the next split will be forced to make progress. Otherwise,
1978 // leave the new intervals as RS_New so they can compete.
1979 bool LiveBefore = BestBefore != 0 || BI.LiveIn;
1980 bool LiveAfter = BestAfter != NumGaps || BI.LiveOut;
1981 unsigned NewGaps = LiveBefore + BestAfter - BestBefore + LiveAfter;
1982 if (NewGaps >= NumGaps) {
1983 DEBUG(dbgs() << "Tagging non-progress ranges: ");
1984 assert(!ProgressRequired && "Didn't make progress when it was required.");
1985 for (unsigned i = 0, e = IntvMap.size(); i != e; ++i)
1986 if (IntvMap[i] == 1) {
1987 setStage(LIS->getInterval(LREdit.get(i)), RS_Split2);
1988 DEBUG(dbgs() << PrintReg(LREdit.get(i)));
1990 DEBUG(dbgs() << '\n');
1997 //===----------------------------------------------------------------------===//
1998 // Live Range Splitting
1999 //===----------------------------------------------------------------------===//
2001 /// trySplit - Try to split VirtReg or one of its interferences, making it
2003 /// @return Physreg when VirtReg may be assigned and/or new NewVRegs.
2004 unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order,
2005 SmallVectorImpl<unsigned>&NewVRegs) {
2006 // Ranges must be Split2 or less.
2007 if (getStage(VirtReg) >= RS_Spill)
2010 // Local intervals are handled separately.
2011 if (LIS->intervalIsInOneMBB(VirtReg)) {
2012 NamedRegionTimer T("local_split", "Local Splitting", TimerGroupName,
2013 TimerGroupDescription, TimePassesIsEnabled);
2014 SA->analyze(&VirtReg);
2015 unsigned PhysReg = tryLocalSplit(VirtReg, Order, NewVRegs);
2016 if (PhysReg || !NewVRegs.empty())
2018 return tryInstructionSplit(VirtReg, Order, NewVRegs);
2021 NamedRegionTimer T("global_split", "Global Splitting", TimerGroupName,
2022 TimerGroupDescription, TimePassesIsEnabled);
2024 SA->analyze(&VirtReg);
2026 // FIXME: SplitAnalysis may repair broken live ranges coming from the
2027 // coalescer. That may cause the range to become allocatable which means that
2028 // tryRegionSplit won't be making progress. This check should be replaced with
2029 // an assertion when the coalescer is fixed.
2030 if (SA->didRepairRange()) {
2031 // VirtReg has changed, so all cached queries are invalid.
2032 Matrix->invalidateVirtRegs();
2033 if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs))
2037 // First try to split around a region spanning multiple blocks. RS_Split2
2038 // ranges already made dubious progress with region splitting, so they go
2039 // straight to single block splitting.
2040 if (getStage(VirtReg) < RS_Split2) {
2041 unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs);
2042 if (PhysReg || !NewVRegs.empty())
2046 // Then isolate blocks.
2047 return tryBlockSplit(VirtReg, Order, NewVRegs);
2050 //===----------------------------------------------------------------------===//
2051 // Last Chance Recoloring
2052 //===----------------------------------------------------------------------===//
2054 /// mayRecolorAllInterferences - Check if the virtual registers that
2055 /// interfere with \p VirtReg on \p PhysReg (or one of its aliases) may be
2056 /// recolored to free \p PhysReg.
2057 /// When true is returned, \p RecoloringCandidates has been augmented with all
2058 /// the live intervals that need to be recolored in order to free \p PhysReg
2060 /// \p FixedRegisters contains all the virtual registers that cannot be
2063 RAGreedy::mayRecolorAllInterferences(unsigned PhysReg, LiveInterval &VirtReg,
2064 SmallLISet &RecoloringCandidates,
2065 const SmallVirtRegSet &FixedRegisters) {
2066 const TargetRegisterClass *CurRC = MRI->getRegClass(VirtReg.reg);
2068 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
2069 LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units);
2070 // If there is LastChanceRecoloringMaxInterference or more interferences,
2071 // chances are one would not be recolorable.
2072 if (Q.collectInterferingVRegs(LastChanceRecoloringMaxInterference) >=
2073 LastChanceRecoloringMaxInterference && !ExhaustiveSearch) {
2074 DEBUG(dbgs() << "Early abort: too many interferences.\n");
2075 CutOffInfo |= CO_Interf;
2078 for (unsigned i = Q.interferingVRegs().size(); i; --i) {
2079 LiveInterval *Intf = Q.interferingVRegs()[i - 1];
2080 // If Intf is done and sit on the same register class as VirtReg,
2081 // it would not be recolorable as it is in the same state as VirtReg.
2082 if ((getStage(*Intf) == RS_Done &&
2083 MRI->getRegClass(Intf->reg) == CurRC) ||
2084 FixedRegisters.count(Intf->reg)) {
2085 DEBUG(dbgs() << "Early abort: the inteference is not recolorable.\n");
2088 RecoloringCandidates.insert(Intf);
2094 /// tryLastChanceRecoloring - Try to assign a color to \p VirtReg by recoloring
2095 /// its interferences.
2096 /// Last chance recoloring chooses a color for \p VirtReg and recolors every
2097 /// virtual register that was using it. The recoloring process may recursively
2098 /// use the last chance recoloring. Therefore, when a virtual register has been
2099 /// assigned a color by this mechanism, it is marked as Fixed, i.e., it cannot
2100 /// be last-chance-recolored again during this recoloring "session".
2103 /// vA can use {R1, R2 }
2104 /// vB can use { R2, R3}
2105 /// vC can use {R1 }
2106 /// Where vA, vB, and vC cannot be split anymore (they are reloads for
2107 /// instance) and they all interfere.
2109 /// vA is assigned R1
2110 /// vB is assigned R2
2111 /// vC tries to evict vA but vA is already done.
2112 /// Regular register allocation fails.
2114 /// Last chance recoloring kicks in:
2115 /// vC does as if vA was evicted => vC uses R1.
2116 /// vC is marked as fixed.
2117 /// vA needs to find a color.
2118 /// None are available.
2119 /// vA cannot evict vC: vC is a fixed virtual register now.
2120 /// vA does as if vB was evicted => vA uses R2.
2121 /// vB needs to find a color.
2122 /// R3 is available.
2123 /// Recoloring => vC = R1, vA = R2, vB = R3
2125 /// \p Order defines the preferred allocation order for \p VirtReg.
2126 /// \p NewRegs will contain any new virtual register that have been created
2127 /// (split, spill) during the process and that must be assigned.
2128 /// \p FixedRegisters contains all the virtual registers that cannot be
2130 /// \p Depth gives the current depth of the last chance recoloring.
2131 /// \return a physical register that can be used for VirtReg or ~0u if none
2133 unsigned RAGreedy::tryLastChanceRecoloring(LiveInterval &VirtReg,
2134 AllocationOrder &Order,
2135 SmallVectorImpl<unsigned> &NewVRegs,
2136 SmallVirtRegSet &FixedRegisters,
2138 DEBUG(dbgs() << "Try last chance recoloring for " << VirtReg << '\n');
2139 // Ranges must be Done.
2140 assert((getStage(VirtReg) >= RS_Done || !VirtReg.isSpillable()) &&
2141 "Last chance recoloring should really be last chance");
2142 // Set the max depth to LastChanceRecoloringMaxDepth.
2143 // We may want to reconsider that if we end up with a too large search space
2144 // for target with hundreds of registers.
2145 // Indeed, in that case we may want to cut the search space earlier.
2146 if (Depth >= LastChanceRecoloringMaxDepth && !ExhaustiveSearch) {
2147 DEBUG(dbgs() << "Abort because max depth has been reached.\n");
2148 CutOffInfo |= CO_Depth;
2152 // Set of Live intervals that will need to be recolored.
2153 SmallLISet RecoloringCandidates;
2154 // Record the original mapping virtual register to physical register in case
2155 // the recoloring fails.
2156 DenseMap<unsigned, unsigned> VirtRegToPhysReg;
2157 // Mark VirtReg as fixed, i.e., it will not be recolored pass this point in
2158 // this recoloring "session".
2159 FixedRegisters.insert(VirtReg.reg);
2160 SmallVector<unsigned, 4> CurrentNewVRegs;
2163 while (unsigned PhysReg = Order.next()) {
2164 DEBUG(dbgs() << "Try to assign: " << VirtReg << " to "
2165 << PrintReg(PhysReg, TRI) << '\n');
2166 RecoloringCandidates.clear();
2167 VirtRegToPhysReg.clear();
2168 CurrentNewVRegs.clear();
2170 // It is only possible to recolor virtual register interference.
2171 if (Matrix->checkInterference(VirtReg, PhysReg) >
2172 LiveRegMatrix::IK_VirtReg) {
2173 DEBUG(dbgs() << "Some inteferences are not with virtual registers.\n");
2178 // Early give up on this PhysReg if it is obvious we cannot recolor all
2179 // the interferences.
2180 if (!mayRecolorAllInterferences(PhysReg, VirtReg, RecoloringCandidates,
2182 DEBUG(dbgs() << "Some inteferences cannot be recolored.\n");
2186 // RecoloringCandidates contains all the virtual registers that interfer
2187 // with VirtReg on PhysReg (or one of its aliases).
2188 // Enqueue them for recoloring and perform the actual recoloring.
2189 PQueue RecoloringQueue;
2190 for (SmallLISet::iterator It = RecoloringCandidates.begin(),
2191 EndIt = RecoloringCandidates.end();
2192 It != EndIt; ++It) {
2193 unsigned ItVirtReg = (*It)->reg;
2194 enqueue(RecoloringQueue, *It);
2195 assert(VRM->hasPhys(ItVirtReg) &&
2196 "Interferences are supposed to be with allocated vairables");
2198 // Record the current allocation.
2199 VirtRegToPhysReg[ItVirtReg] = VRM->getPhys(ItVirtReg);
2200 // unset the related struct.
2201 Matrix->unassign(**It);
2204 // Do as if VirtReg was assigned to PhysReg so that the underlying
2205 // recoloring has the right information about the interferes and
2206 // available colors.
2207 Matrix->assign(VirtReg, PhysReg);
2209 // Save the current recoloring state.
2210 // If we cannot recolor all the interferences, we will have to start again
2211 // at this point for the next physical register.
2212 SmallVirtRegSet SaveFixedRegisters(FixedRegisters);
2213 if (tryRecoloringCandidates(RecoloringQueue, CurrentNewVRegs,
2214 FixedRegisters, Depth)) {
2215 // Push the queued vregs into the main queue.
2216 for (unsigned NewVReg : CurrentNewVRegs)
2217 NewVRegs.push_back(NewVReg);
2218 // Do not mess up with the global assignment process.
2219 // I.e., VirtReg must be unassigned.
2220 Matrix->unassign(VirtReg);
2224 DEBUG(dbgs() << "Fail to assign: " << VirtReg << " to "
2225 << PrintReg(PhysReg, TRI) << '\n');
2227 // The recoloring attempt failed, undo the changes.
2228 FixedRegisters = SaveFixedRegisters;
2229 Matrix->unassign(VirtReg);
2231 // For a newly created vreg which is also in RecoloringCandidates,
2232 // don't add it to NewVRegs because its physical register will be restored
2233 // below. Other vregs in CurrentNewVRegs are created by calling
2234 // selectOrSplit and should be added into NewVRegs.
2235 for (SmallVectorImpl<unsigned>::iterator Next = CurrentNewVRegs.begin(),
2236 End = CurrentNewVRegs.end();
2237 Next != End; ++Next) {
2238 if (RecoloringCandidates.count(&LIS->getInterval(*Next)))
2240 NewVRegs.push_back(*Next);
2243 for (SmallLISet::iterator It = RecoloringCandidates.begin(),
2244 EndIt = RecoloringCandidates.end();
2245 It != EndIt; ++It) {
2246 unsigned ItVirtReg = (*It)->reg;
2247 if (VRM->hasPhys(ItVirtReg))
2248 Matrix->unassign(**It);
2249 unsigned ItPhysReg = VirtRegToPhysReg[ItVirtReg];
2250 Matrix->assign(**It, ItPhysReg);
2254 // Last chance recoloring did not worked either, give up.
2258 /// tryRecoloringCandidates - Try to assign a new color to every register
2259 /// in \RecoloringQueue.
2260 /// \p NewRegs will contain any new virtual register created during the
2261 /// recoloring process.
2262 /// \p FixedRegisters[in/out] contains all the registers that have been
2264 /// \return true if all virtual registers in RecoloringQueue were successfully
2265 /// recolored, false otherwise.
2266 bool RAGreedy::tryRecoloringCandidates(PQueue &RecoloringQueue,
2267 SmallVectorImpl<unsigned> &NewVRegs,
2268 SmallVirtRegSet &FixedRegisters,
2270 while (!RecoloringQueue.empty()) {
2271 LiveInterval *LI = dequeue(RecoloringQueue);
2272 DEBUG(dbgs() << "Try to recolor: " << *LI << '\n');
2274 PhysReg = selectOrSplitImpl(*LI, NewVRegs, FixedRegisters, Depth + 1);
2275 // When splitting happens, the live-range may actually be empty.
2276 // In that case, this is okay to continue the recoloring even
2277 // if we did not find an alternative color for it. Indeed,
2278 // there will not be anything to color for LI in the end.
2279 if (PhysReg == ~0u || (!PhysReg && !LI->empty()))
2283 assert(LI->empty() && "Only empty live-range do not require a register");
2284 DEBUG(dbgs() << "Recoloring of " << *LI << " succeeded. Empty LI.\n");
2287 DEBUG(dbgs() << "Recoloring of " << *LI
2288 << " succeeded with: " << PrintReg(PhysReg, TRI) << '\n');
2290 Matrix->assign(*LI, PhysReg);
2291 FixedRegisters.insert(LI->reg);
2296 //===----------------------------------------------------------------------===//
2298 //===----------------------------------------------------------------------===//
2300 unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg,
2301 SmallVectorImpl<unsigned> &NewVRegs) {
2302 CutOffInfo = CO_None;
2303 LLVMContext &Ctx = MF->getFunction()->getContext();
2304 SmallVirtRegSet FixedRegisters;
2305 unsigned Reg = selectOrSplitImpl(VirtReg, NewVRegs, FixedRegisters);
2306 if (Reg == ~0U && (CutOffInfo != CO_None)) {
2307 uint8_t CutOffEncountered = CutOffInfo & (CO_Depth | CO_Interf);
2308 if (CutOffEncountered == CO_Depth)
2309 Ctx.emitError("register allocation failed: maximum depth for recoloring "
2310 "reached. Use -fexhaustive-register-search to skip "
2312 else if (CutOffEncountered == CO_Interf)
2313 Ctx.emitError("register allocation failed: maximum interference for "
2314 "recoloring reached. Use -fexhaustive-register-search "
2316 else if (CutOffEncountered == (CO_Depth | CO_Interf))
2317 Ctx.emitError("register allocation failed: maximum interference and "
2318 "depth for recoloring reached. Use "
2319 "-fexhaustive-register-search to skip cutoffs");
2324 /// Using a CSR for the first time has a cost because it causes push|pop
2325 /// to be added to prologue|epilogue. Splitting a cold section of the live
2326 /// range can have lower cost than using the CSR for the first time;
2327 /// Spilling a live range in the cold path can have lower cost than using
2328 /// the CSR for the first time. Returns the physical register if we decide
2329 /// to use the CSR; otherwise return 0.
2330 unsigned RAGreedy::tryAssignCSRFirstTime(LiveInterval &VirtReg,
2331 AllocationOrder &Order,
2333 unsigned &CostPerUseLimit,
2334 SmallVectorImpl<unsigned> &NewVRegs) {
2335 if (getStage(VirtReg) == RS_Spill && VirtReg.isSpillable()) {
2336 // We choose spill over using the CSR for the first time if the spill cost
2337 // is lower than CSRCost.
2338 SA->analyze(&VirtReg);
2339 if (calcSpillCost() >= CSRCost)
2342 // We are going to spill, set CostPerUseLimit to 1 to make sure that
2343 // we will not use a callee-saved register in tryEvict.
2344 CostPerUseLimit = 1;
2347 if (getStage(VirtReg) < RS_Split) {
2348 // We choose pre-splitting over using the CSR for the first time if
2349 // the cost of splitting is lower than CSRCost.
2350 SA->analyze(&VirtReg);
2351 unsigned NumCands = 0;
2352 BlockFrequency BestCost = CSRCost; // Don't modify CSRCost.
2353 unsigned BestCand = calculateRegionSplitCost(VirtReg, Order, BestCost,
2354 NumCands, true /*IgnoreCSR*/);
2355 if (BestCand == NoCand)
2356 // Use the CSR if we can't find a region split below CSRCost.
2359 // Perform the actual pre-splitting.
2360 doRegionSplit(VirtReg, BestCand, false/*HasCompact*/, NewVRegs);
2366 void RAGreedy::aboutToRemoveInterval(LiveInterval &LI) {
2367 // Do not keep invalid information around.
2368 SetOfBrokenHints.remove(&LI);
2371 void RAGreedy::initializeCSRCost() {
2372 // We use the larger one out of the command-line option and the value report
2374 CSRCost = BlockFrequency(
2375 std::max((unsigned)CSRFirstTimeCost, TRI->getCSRFirstUseCost()));
2376 if (!CSRCost.getFrequency())
2379 // Raw cost is relative to Entry == 2^14; scale it appropriately.
2380 uint64_t ActualEntry = MBFI->getEntryFreq();
2385 uint64_t FixedEntry = 1 << 14;
2386 if (ActualEntry < FixedEntry)
2387 CSRCost *= BranchProbability(ActualEntry, FixedEntry);
2388 else if (ActualEntry <= UINT32_MAX)
2389 // Invert the fraction and divide.
2390 CSRCost /= BranchProbability(FixedEntry, ActualEntry);
2392 // Can't use BranchProbability in general, since it takes 32-bit numbers.
2393 CSRCost = CSRCost.getFrequency() * (ActualEntry / FixedEntry);
2396 /// \brief Collect the hint info for \p Reg.
2397 /// The results are stored into \p Out.
2398 /// \p Out is not cleared before being populated.
2399 void RAGreedy::collectHintInfo(unsigned Reg, HintsInfo &Out) {
2400 for (const MachineInstr &Instr : MRI->reg_nodbg_instructions(Reg)) {
2401 if (!Instr.isFullCopy())
2403 // Look for the other end of the copy.
2404 unsigned OtherReg = Instr.getOperand(0).getReg();
2405 if (OtherReg == Reg) {
2406 OtherReg = Instr.getOperand(1).getReg();
2407 if (OtherReg == Reg)
2410 // Get the current assignment.
2411 unsigned OtherPhysReg = TargetRegisterInfo::isPhysicalRegister(OtherReg)
2413 : VRM->getPhys(OtherReg);
2414 // Push the collected information.
2415 Out.push_back(HintInfo(MBFI->getBlockFreq(Instr.getParent()), OtherReg,
2420 /// \brief Using the given \p List, compute the cost of the broken hints if
2421 /// \p PhysReg was used.
2422 /// \return The cost of \p List for \p PhysReg.
2423 BlockFrequency RAGreedy::getBrokenHintFreq(const HintsInfo &List,
2425 BlockFrequency Cost = 0;
2426 for (const HintInfo &Info : List) {
2427 if (Info.PhysReg != PhysReg)
2433 /// \brief Using the register assigned to \p VirtReg, try to recolor
2434 /// all the live ranges that are copy-related with \p VirtReg.
2435 /// The recoloring is then propagated to all the live-ranges that have
2436 /// been recolored and so on, until no more copies can be coalesced or
2437 /// it is not profitable.
2438 /// For a given live range, profitability is determined by the sum of the
2439 /// frequencies of the non-identity copies it would introduce with the old
2440 /// and new register.
2441 void RAGreedy::tryHintRecoloring(LiveInterval &VirtReg) {
2442 // We have a broken hint, check if it is possible to fix it by
2443 // reusing PhysReg for the copy-related live-ranges. Indeed, we evicted
2444 // some register and PhysReg may be available for the other live-ranges.
2445 SmallSet<unsigned, 4> Visited;
2446 SmallVector<unsigned, 2> RecoloringCandidates;
2448 unsigned Reg = VirtReg.reg;
2449 unsigned PhysReg = VRM->getPhys(Reg);
2450 // Start the recoloring algorithm from the input live-interval, then
2451 // it will propagate to the ones that are copy-related with it.
2452 Visited.insert(Reg);
2453 RecoloringCandidates.push_back(Reg);
2455 DEBUG(dbgs() << "Trying to reconcile hints for: " << PrintReg(Reg, TRI) << '('
2456 << PrintReg(PhysReg, TRI) << ")\n");
2459 Reg = RecoloringCandidates.pop_back_val();
2461 // We cannot recolor physical register.
2462 if (TargetRegisterInfo::isPhysicalRegister(Reg))
2465 assert(VRM->hasPhys(Reg) && "We have unallocated variable!!");
2467 // Get the live interval mapped with this virtual register to be able
2468 // to check for the interference with the new color.
2469 LiveInterval &LI = LIS->getInterval(Reg);
2470 unsigned CurrPhys = VRM->getPhys(Reg);
2471 // Check that the new color matches the register class constraints and
2472 // that it is free for this live range.
2473 if (CurrPhys != PhysReg && (!MRI->getRegClass(Reg)->contains(PhysReg) ||
2474 Matrix->checkInterference(LI, PhysReg)))
2477 DEBUG(dbgs() << PrintReg(Reg, TRI) << '(' << PrintReg(CurrPhys, TRI)
2478 << ") is recolorable.\n");
2480 // Gather the hint info.
2482 collectHintInfo(Reg, Info);
2483 // Check if recoloring the live-range will increase the cost of the
2484 // non-identity copies.
2485 if (CurrPhys != PhysReg) {
2486 DEBUG(dbgs() << "Checking profitability:\n");
2487 BlockFrequency OldCopiesCost = getBrokenHintFreq(Info, CurrPhys);
2488 BlockFrequency NewCopiesCost = getBrokenHintFreq(Info, PhysReg);
2489 DEBUG(dbgs() << "Old Cost: " << OldCopiesCost.getFrequency()
2490 << "\nNew Cost: " << NewCopiesCost.getFrequency() << '\n');
2491 if (OldCopiesCost < NewCopiesCost) {
2492 DEBUG(dbgs() << "=> Not profitable.\n");
2495 // At this point, the cost is either cheaper or equal. If it is
2496 // equal, we consider this is profitable because it may expose
2497 // more recoloring opportunities.
2498 DEBUG(dbgs() << "=> Profitable.\n");
2499 // Recolor the live-range.
2500 Matrix->unassign(LI);
2501 Matrix->assign(LI, PhysReg);
2503 // Push all copy-related live-ranges to keep reconciling the broken
2505 for (const HintInfo &HI : Info) {
2506 if (Visited.insert(HI.Reg).second)
2507 RecoloringCandidates.push_back(HI.Reg);
2509 } while (!RecoloringCandidates.empty());
2512 /// \brief Try to recolor broken hints.
2513 /// Broken hints may be repaired by recoloring when an evicted variable
2514 /// freed up a register for a larger live-range.
2515 /// Consider the following example:
2523 /// Let us assume b gets split:
2533 /// Because of how the allocation work, b, c, and d may be assigned different
2534 /// colors. Now, if a gets evicted later:
2544 /// e = ld SpillSlot
2546 /// This is likely that we can assign the same register for b, c, and d,
2547 /// getting rid of 2 copies.
2548 void RAGreedy::tryHintsRecoloring() {
2549 for (LiveInterval *LI : SetOfBrokenHints) {
2550 assert(TargetRegisterInfo::isVirtualRegister(LI->reg) &&
2551 "Recoloring is possible only for virtual registers");
2552 // Some dead defs may be around (e.g., because of debug uses).
2554 if (!VRM->hasPhys(LI->reg))
2556 tryHintRecoloring(*LI);
2560 unsigned RAGreedy::selectOrSplitImpl(LiveInterval &VirtReg,
2561 SmallVectorImpl<unsigned> &NewVRegs,
2562 SmallVirtRegSet &FixedRegisters,
2564 unsigned CostPerUseLimit = ~0u;
2565 // First try assigning a free register.
2566 AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo, Matrix);
2567 if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) {
2568 // When NewVRegs is not empty, we may have made decisions such as evicting
2569 // a virtual register, go with the earlier decisions and use the physical
2571 if (CSRCost.getFrequency() && isUnusedCalleeSavedReg(PhysReg) &&
2573 unsigned CSRReg = tryAssignCSRFirstTime(VirtReg, Order, PhysReg,
2574 CostPerUseLimit, NewVRegs);
2575 if (CSRReg || !NewVRegs.empty())
2576 // Return now if we decide to use a CSR or create new vregs due to
2583 LiveRangeStage Stage = getStage(VirtReg);
2584 DEBUG(dbgs() << StageName[Stage]
2585 << " Cascade " << ExtraRegInfo[VirtReg.reg].Cascade << '\n');
2587 // Try to evict a less worthy live range, but only for ranges from the primary
2588 // queue. The RS_Split ranges already failed to do this, and they should not
2589 // get a second chance until they have been split.
2590 if (Stage != RS_Split)
2591 if (unsigned PhysReg =
2592 tryEvict(VirtReg, Order, NewVRegs, CostPerUseLimit)) {
2593 unsigned Hint = MRI->getSimpleHint(VirtReg.reg);
2594 // If VirtReg has a hint and that hint is broken record this
2595 // virtual register as a recoloring candidate for broken hint.
2596 // Indeed, since we evicted a variable in its neighborhood it is
2597 // likely we can at least partially recolor some of the
2598 // copy-related live-ranges.
2599 if (Hint && Hint != PhysReg)
2600 SetOfBrokenHints.insert(&VirtReg);
2604 assert((NewVRegs.empty() || Depth) && "Cannot append to existing NewVRegs");
2606 // The first time we see a live range, don't try to split or spill.
2607 // Wait until the second time, when all smaller ranges have been allocated.
2608 // This gives a better picture of the interference to split around.
2609 if (Stage < RS_Split) {
2610 setStage(VirtReg, RS_Split);
2611 DEBUG(dbgs() << "wait for second round\n");
2612 NewVRegs.push_back(VirtReg.reg);
2616 if (Stage < RS_Spill) {
2617 // Try splitting VirtReg or interferences.
2618 unsigned NewVRegSizeBefore = NewVRegs.size();
2619 unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs);
2620 if (PhysReg || (NewVRegs.size() - NewVRegSizeBefore))
2624 // If we couldn't allocate a register from spilling, there is probably some
2625 // invalid inline assembly. The base class will report it.
2626 if (Stage >= RS_Done || !VirtReg.isSpillable())
2627 return tryLastChanceRecoloring(VirtReg, Order, NewVRegs, FixedRegisters,
2630 // Finally spill VirtReg itself.
2631 if (EnableDeferredSpilling && getStage(VirtReg) < RS_Memory) {
2632 // TODO: This is experimental and in particular, we do not model
2633 // the live range splitting done by spilling correctly.
2634 // We would need a deep integration with the spiller to do the
2635 // right thing here. Anyway, that is still good for early testing.
2636 setStage(VirtReg, RS_Memory);
2637 DEBUG(dbgs() << "Do as if this register is in memory\n");
2638 NewVRegs.push_back(VirtReg.reg);
2640 NamedRegionTimer T("spill", "Spiller", TimerGroupName,
2641 TimerGroupDescription, TimePassesIsEnabled);
2642 LiveRangeEdit LRE(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);
2643 spiller().spill(LRE);
2644 setStage(NewVRegs.begin(), NewVRegs.end(), RS_Done);
2647 MF->verify(this, "After spilling");
2650 // The live virtual register requesting allocation was spilled, so tell
2651 // the caller not to allocate anything during this round.
2655 void RAGreedy::reportNumberOfSplillsReloads(MachineLoop *L, unsigned &Reloads,
2656 unsigned &FoldedReloads,
2658 unsigned &FoldedSpills) {
2664 // Sum up the spill and reloads in subloops.
2665 for (MachineLoop *SubLoop : *L) {
2666 unsigned SubReloads;
2667 unsigned SubFoldedReloads;
2669 unsigned SubFoldedSpills;
2671 reportNumberOfSplillsReloads(SubLoop, SubReloads, SubFoldedReloads,
2672 SubSpills, SubFoldedSpills);
2673 Reloads += SubReloads;
2674 FoldedReloads += SubFoldedReloads;
2675 Spills += SubSpills;
2676 FoldedSpills += SubFoldedSpills;
2679 const MachineFrameInfo &MFI = MF->getFrameInfo();
2680 const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
2683 for (MachineBasicBlock *MBB : L->getBlocks())
2684 // Handle blocks that were not included in subloops.
2685 if (Loops->getLoopFor(MBB) == L)
2686 for (MachineInstr &MI : *MBB) {
2687 const MachineMemOperand *MMO;
2689 if (TII->isLoadFromStackSlot(MI, FI) && MFI.isSpillSlotObjectIndex(FI))
2691 else if (TII->hasLoadFromStackSlot(MI, MMO, FI) &&
2692 MFI.isSpillSlotObjectIndex(FI))
2694 else if (TII->isStoreToStackSlot(MI, FI) &&
2695 MFI.isSpillSlotObjectIndex(FI))
2697 else if (TII->hasStoreToStackSlot(MI, MMO, FI) &&
2698 MFI.isSpillSlotObjectIndex(FI))
2702 if (Reloads || FoldedReloads || Spills || FoldedSpills) {
2703 using namespace ore;
2705 MachineOptimizationRemarkMissed R(DEBUG_TYPE, "LoopSpillReload",
2706 L->getStartLoc(), L->getHeader());
2708 R << NV("NumSpills", Spills) << " spills ";
2710 R << NV("NumFoldedSpills", FoldedSpills) << " folded spills ";
2712 R << NV("NumReloads", Reloads) << " reloads ";
2714 R << NV("NumFoldedReloads", FoldedReloads) << " folded reloads ";
2715 ORE->emit(R << "generated in loop");
2719 bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
2720 DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n"
2721 << "********** Function: " << mf.getName() << '\n');
2724 TRI = MF->getSubtarget().getRegisterInfo();
2725 TII = MF->getSubtarget().getInstrInfo();
2726 RCI.runOnMachineFunction(mf);
2728 EnableLocalReassign = EnableLocalReassignment ||
2729 MF->getSubtarget().enableRALocalReassignment(
2730 MF->getTarget().getOptLevel());
2733 MF->verify(this, "Before greedy register allocator");
2735 RegAllocBase::init(getAnalysis<VirtRegMap>(),
2736 getAnalysis<LiveIntervals>(),
2737 getAnalysis<LiveRegMatrix>());
2738 Indexes = &getAnalysis<SlotIndexes>();
2739 MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
2740 DomTree = &getAnalysis<MachineDominatorTree>();
2741 ORE = &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();
2742 SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
2743 Loops = &getAnalysis<MachineLoopInfo>();
2744 Bundles = &getAnalysis<EdgeBundles>();
2745 SpillPlacer = &getAnalysis<SpillPlacement>();
2746 DebugVars = &getAnalysis<LiveDebugVariables>();
2747 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
2749 initializeCSRCost();
2751 calculateSpillWeightsAndHints(*LIS, mf, VRM, *Loops, *MBFI);
2755 SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops));
2756 SE.reset(new SplitEditor(*SA, *AA, *LIS, *VRM, *DomTree, *MBFI));
2757 ExtraRegInfo.clear();
2758 ExtraRegInfo.resize(MRI->getNumVirtRegs());
2760 IntfCache.init(MF, Matrix->getLiveUnions(), Indexes, LIS, TRI);
2761 GlobalCand.resize(32); // This will grow as needed.
2762 SetOfBrokenHints.clear();
2765 tryHintsRecoloring();
2767 reportNumberOfSplillsReloads();