1//===- RegAllocGreedy.cpp - greedy register allocator ---------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines the RAGreedy function pass for register allocation in
10// optimized builds.
11//
12//===----------------------------------------------------------------------===//
13
14#include "RegAllocGreedy.h"
15#include "AllocationOrder.h"
16#include "InlineSpiller.h"
17#include "InterferenceCache.h"
18#include "RegAllocBase.h"
19#include "SplitKit.h"
20#include "llvm/ADT/ArrayRef.h"
21#include "llvm/ADT/BitVector.h"
22#include "llvm/ADT/IndexedMap.h"
23#include "llvm/ADT/SmallSet.h"
24#include "llvm/ADT/SmallVector.h"
25#include "llvm/ADT/Statistic.h"
26#include "llvm/ADT/StringRef.h"
27#include "llvm/Analysis/OptimizationRemarkEmitter.h"
28#include "llvm/CodeGen/CalcSpillWeights.h"
29#include "llvm/CodeGen/EdgeBundles.h"
30#include "llvm/CodeGen/LiveDebugVariables.h"
31#include "llvm/CodeGen/LiveInterval.h"
32#include "llvm/CodeGen/LiveIntervalUnion.h"
33#include "llvm/CodeGen/LiveIntervals.h"
34#include "llvm/CodeGen/LiveRangeEdit.h"
35#include "llvm/CodeGen/LiveRegMatrix.h"
36#include "llvm/CodeGen/LiveStacks.h"
37#include "llvm/CodeGen/MachineBasicBlock.h"
38#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
39#include "llvm/CodeGen/MachineDominators.h"
40#include "llvm/CodeGen/MachineFrameInfo.h"
41#include "llvm/CodeGen/MachineFunction.h"
42#include "llvm/CodeGen/MachineFunctionPass.h"
43#include "llvm/CodeGen/MachineInstr.h"
44#include "llvm/CodeGen/MachineLoopInfo.h"
45#include "llvm/CodeGen/MachineOperand.h"
46#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
47#include "llvm/CodeGen/MachinePassManager.h"
48#include "llvm/CodeGen/MachineRegisterInfo.h"
49#include "llvm/CodeGen/RegAllocEvictionAdvisor.h"
50#include "llvm/CodeGen/RegAllocGreedyPass.h"
51#include "llvm/CodeGen/RegAllocPriorityAdvisor.h"
52#include "llvm/CodeGen/RegAllocRegistry.h"
53#include "llvm/CodeGen/RegisterClassInfo.h"
54#include "llvm/CodeGen/SlotIndexes.h"
55#include "llvm/CodeGen/SpillPlacement.h"
56#include "llvm/CodeGen/Spiller.h"
57#include "llvm/CodeGen/TargetInstrInfo.h"
58#include "llvm/CodeGen/TargetRegisterInfo.h"
59#include "llvm/CodeGen/TargetSubtargetInfo.h"
60#include "llvm/CodeGen/VirtRegMap.h"
61#include "llvm/IR/Analysis.h"
62#include "llvm/IR/DebugInfoMetadata.h"
63#include "llvm/IR/Function.h"
64#include "llvm/IR/LLVMContext.h"
65#include "llvm/IR/PassTimingInfo.h"
66#include "llvm/Pass.h"
67#include "llvm/Support/BlockFrequency.h"
68#include "llvm/Support/BranchProbability.h"
69#include "llvm/Support/CommandLine.h"
70#include "llvm/Support/Debug.h"
71#include "llvm/Support/MathExtras.h"
72#include "llvm/Support/Timer.h"
73#include "llvm/Support/raw_ostream.h"
74#include <algorithm>
75#include <cassert>
76#include <cstdint>
77#include <utility>
78
79using namespace llvm;
80
81#define DEBUG_TYPE "regalloc"
82
83STATISTIC(NumGlobalSplits, "Number of split global live ranges");
84STATISTIC(NumLocalSplits, "Number of split local live ranges");
85STATISTIC(NumEvicted, "Number of interferences evicted");
86
87static cl::opt<SplitEditor::ComplementSpillMode> SplitSpillMode(
88 "split-spill-mode", cl::Hidden,
89 cl::desc("Spill mode for splitting live ranges"),
90 cl::values(clEnumValN(SplitEditor::SM_Partition, "default", "Default"),
91 clEnumValN(SplitEditor::SM_Size, "size", "Optimize for size"),
92 clEnumValN(SplitEditor::SM_Speed, "speed", "Optimize for speed")),
93 cl::init(Val: SplitEditor::SM_Speed));
94
95static cl::opt<unsigned>
96LastChanceRecoloringMaxDepth("lcr-max-depth", cl::Hidden,
97 cl::desc("Last chance recoloring max depth"),
98 cl::init(Val: 5));
99
100static cl::opt<unsigned> LastChanceRecoloringMaxInterference(
101 "lcr-max-interf", cl::Hidden,
102 cl::desc("Last chance recoloring maximum number of considered"
103 " interference at a time"),
104 cl::init(Val: 8));
105
106static cl::opt<bool> ExhaustiveSearch(
107 "exhaustive-register-search", cl::NotHidden,
108 cl::desc("Exhaustive Search for registers bypassing the depth "
109 "and interference cutoffs of last chance recoloring"),
110 cl::Hidden);
111
112static cl::opt<bool> CompactSlotIndexes(
113 "greedy-compact-slot-indexes", cl::Hidden, cl::init(Val: false),
114 cl::desc("Drop SlotIndexes entries for erased instructions before "
115 "allocating, so live range sizes reflect real code distance"));
116
117// This option should be deprecated!
118// FIXME: Find a good default for this flag and remove the flag.
119static cl::opt<unsigned>
120CSRFirstTimeCost("regalloc-csr-first-time-cost",
121 cl::desc("Cost for first time use of callee-saved register."),
122 cl::init(Val: 0), cl::Hidden);
123
124static cl::opt<unsigned> CSRCostScale(
125 "regalloc-csr-cost-scale",
126 cl::desc("Scale for the callee-saved register cost, in percentage."),
127 cl::init(Val: 80), cl::Hidden);
128
129static cl::opt<unsigned long> GrowRegionComplexityBudget(
130 "grow-region-complexity-budget",
131 cl::desc("growRegion() does not scale with the number of BB edges, so "
132 "limit its budget and bail out once we reach the limit."),
133 cl::init(Val: 10000), cl::Hidden);
134
135static cl::opt<bool> GreedyRegClassPriorityTrumpsGlobalness(
136 "greedy-regclass-priority-trumps-globalness",
137 cl::desc("Change the greedy register allocator's live range priority "
138 "calculation to make the AllocationPriority of the register class "
139 "more important then whether the range is global"),
140 cl::Hidden);
141
142static cl::opt<bool> GreedyReverseLocalAssignment(
143 "greedy-reverse-local-assignment",
144 cl::desc("Reverse allocation order of local live ranges, such that "
145 "shorter local live ranges will tend to be allocated first"),
146 cl::Hidden);
147
148static cl::opt<unsigned> SplitThresholdForRegWithHint(
149 "split-threshold-for-reg-with-hint",
150 cl::desc("The threshold for splitting a virtual register with a hint, in "
151 "percentage"),
152 cl::init(Val: 75), cl::Hidden);
153
154static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator",
155 createGreedyRegisterAllocator);
156
157namespace {
158class RAGreedyLegacy : public MachineFunctionPass {
159 RegAllocFilterFunc F;
160
161public:
162 RAGreedyLegacy(const RegAllocFilterFunc F = nullptr);
163
164 static char ID;
165 /// Return the pass name.
166 StringRef getPassName() const override { return "Greedy Register Allocator"; }
167
168 /// RAGreedy analysis usage.
169 void getAnalysisUsage(AnalysisUsage &AU) const override;
170 /// Perform register allocation.
171 bool runOnMachineFunction(MachineFunction &mf) override;
172
173 MachineFunctionProperties getRequiredProperties() const override {
174 return MachineFunctionProperties().setNoPHIs();
175 }
176
177 MachineFunctionProperties getClearedProperties() const override {
178 return MachineFunctionProperties().setIsSSA();
179 }
180};
181
182} // end anonymous namespace
183
184RAGreedyLegacy::RAGreedyLegacy(const RegAllocFilterFunc F)
185 : MachineFunctionPass(ID), F(std::move(F)) {}
186
187struct RAGreedy::RequiredAnalyses {
188 VirtRegMap *VRM = nullptr;
189 LiveIntervals *LIS = nullptr;
190 LiveRegMatrix *LRM = nullptr;
191 SlotIndexes *Indexes = nullptr;
192 MachineBlockFrequencyInfo *MBFI = nullptr;
193 MachineDominatorTree *DomTree = nullptr;
194 MachineLoopInfo *Loops = nullptr;
195 MachineOptimizationRemarkEmitter *ORE = nullptr;
196 EdgeBundles *Bundles = nullptr;
197 SpillPlacement *SpillPlacer = nullptr;
198 LiveDebugVariables *DebugVars = nullptr;
199 RegisterClassInfo *RCI = nullptr;
200
201 // Used by InlineSpiller
202 LiveStacks *LSS;
203 // Proxies for eviction and priority advisors
204 RegAllocEvictionAdvisorProvider *EvictProvider;
205 RegAllocPriorityAdvisorProvider *PriorityProvider;
206
207 RequiredAnalyses() = delete;
208 RequiredAnalyses(Pass &P);
209 RequiredAnalyses(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM);
210};
211
212RAGreedy::RAGreedy(RequiredAnalyses &Analyses, const RegAllocFilterFunc F)
213 : RegAllocBase(F) {
214 VRM = Analyses.VRM;
215 LIS = Analyses.LIS;
216 Matrix = Analyses.LRM;
217 Indexes = Analyses.Indexes;
218 MBFI = Analyses.MBFI;
219 DomTree = Analyses.DomTree;
220 Loops = Analyses.Loops;
221 ORE = Analyses.ORE;
222 Bundles = Analyses.Bundles;
223 SpillPlacer = Analyses.SpillPlacer;
224 DebugVars = Analyses.DebugVars;
225 LSS = Analyses.LSS;
226 EvictProvider = Analyses.EvictProvider;
227 PriorityProvider = Analyses.PriorityProvider;
228 RegClassInfo = Analyses.RCI;
229}
230
231void RAGreedyPass::printPipeline(
232 raw_ostream &OS,
233 function_ref<StringRef(StringRef)> MapClassName2PassName) const {
234 StringRef FilterName = Opts.FilterName.empty() ? "all" : Opts.FilterName;
235 OS << "greedy<" << FilterName << '>';
236}
237
238RAGreedy::RequiredAnalyses::RequiredAnalyses(
239 MachineFunction &MF, MachineFunctionAnalysisManager &MFAM) {
240 LIS = &MFAM.getResult<LiveIntervalsAnalysis>(IR&: MF);
241 LRM = &MFAM.getResult<LiveRegMatrixAnalysis>(IR&: MF);
242 LSS = &MFAM.getResult<LiveStacksAnalysis>(IR&: MF);
243 Indexes = &MFAM.getResult<SlotIndexesAnalysis>(IR&: MF);
244 MBFI = &MFAM.getResult<MachineBlockFrequencyAnalysis>(IR&: MF);
245 DomTree = &MFAM.getResult<MachineDominatorTreeAnalysis>(IR&: MF);
246 ORE = &MFAM.getResult<MachineOptimizationRemarkEmitterAnalysis>(IR&: MF);
247 Loops = &MFAM.getResult<MachineLoopAnalysis>(IR&: MF);
248 Bundles = &MFAM.getResult<EdgeBundlesAnalysis>(IR&: MF);
249 SpillPlacer = &MFAM.getResult<SpillPlacementAnalysis>(IR&: MF);
250 DebugVars = &MFAM.getResult<LiveDebugVariablesAnalysis>(IR&: MF);
251 EvictProvider = MFAM.getResult<RegAllocEvictionAdvisorAnalysis>(IR&: MF).Provider;
252 PriorityProvider =
253 MFAM.getResult<RegAllocPriorityAdvisorAnalysis>(IR&: MF).Provider;
254 VRM = &MFAM.getResult<VirtRegMapAnalysis>(IR&: MF);
255 RCI = &MFAM.getResult<MachineRegisterClassAnalysis>(IR&: MF);
256}
257
258PreservedAnalyses RAGreedyPass::run(MachineFunction &MF,
259 MachineFunctionAnalysisManager &MFAM) {
260 MFPropsModifier _(*this, MF);
261
262 RAGreedy::RequiredAnalyses Analyses(MF, MFAM);
263 RAGreedy Impl(Analyses, Opts.Filter);
264
265 bool Changed = Impl.run(mf&: MF);
266 if (!Changed)
267 return PreservedAnalyses::all();
268 auto PA = getMachineFunctionPassPreservedAnalyses();
269 PA.preserveSet<CFGAnalyses>();
270 PA.preserve<LiveIntervalsAnalysis>();
271 PA.preserve<SlotIndexesAnalysis>();
272 PA.preserve<LiveDebugVariablesAnalysis>();
273 PA.preserve<LiveStacksAnalysis>();
274 PA.preserve<VirtRegMapAnalysis>();
275 PA.preserve<LiveRegMatrixAnalysis>();
276 return PA;
277}
278
279RAGreedy::RequiredAnalyses::RequiredAnalyses(Pass &P) {
280 VRM = &P.getAnalysis<VirtRegMapWrapperLegacy>().getVRM();
281 LIS = &P.getAnalysis<LiveIntervalsWrapperPass>().getLIS();
282 LSS = &P.getAnalysis<LiveStacksWrapperLegacy>().getLS();
283 LRM = &P.getAnalysis<LiveRegMatrixWrapperLegacy>().getLRM();
284 Indexes = &P.getAnalysis<SlotIndexesWrapperPass>().getSI();
285 MBFI = &P.getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI();
286 DomTree = &P.getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
287 ORE = &P.getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();
288 Loops = &P.getAnalysis<MachineLoopInfoWrapperPass>().getLI();
289 Bundles = &P.getAnalysis<EdgeBundlesWrapperLegacy>().getEdgeBundles();
290 SpillPlacer = &P.getAnalysis<SpillPlacementWrapperLegacy>().getResult();
291 DebugVars = &P.getAnalysis<LiveDebugVariablesWrapperLegacy>().getLDV();
292 EvictProvider =
293 &P.getAnalysis<RegAllocEvictionAdvisorAnalysisLegacy>().getProvider();
294 PriorityProvider =
295 &P.getAnalysis<RegAllocPriorityAdvisorAnalysisLegacy>().getProvider();
296 RCI = &P.getAnalysis<MachineRegisterClassInfoWrapperPass>().getRCI();
297}
298
299bool RAGreedyLegacy::runOnMachineFunction(MachineFunction &MF) {
300 RAGreedy::RequiredAnalyses Analyses(*this);
301 RAGreedy Impl(Analyses, F);
302 return Impl.run(mf&: MF);
303}
304
305char RAGreedyLegacy::ID = 0;
306char &llvm::RAGreedyLegacyID = RAGreedyLegacy::ID;
307
308INITIALIZE_PASS_BEGIN(RAGreedyLegacy, "greedy", "Greedy Register Allocator",
309 false, false)
310INITIALIZE_PASS_DEPENDENCY(LiveDebugVariablesWrapperLegacy)
311INITIALIZE_PASS_DEPENDENCY(SlotIndexesWrapperPass)
312INITIALIZE_PASS_DEPENDENCY(LiveIntervalsWrapperPass)
313INITIALIZE_PASS_DEPENDENCY(RegisterCoalescerLegacy)
314INITIALIZE_PASS_DEPENDENCY(MachineSchedulerLegacy)
315INITIALIZE_PASS_DEPENDENCY(LiveStacksWrapperLegacy)
316INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
317INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
318INITIALIZE_PASS_DEPENDENCY(VirtRegMapWrapperLegacy)
319INITIALIZE_PASS_DEPENDENCY(LiveRegMatrixWrapperLegacy)
320INITIALIZE_PASS_DEPENDENCY(EdgeBundlesWrapperLegacy)
321INITIALIZE_PASS_DEPENDENCY(SpillPlacementWrapperLegacy)
322INITIALIZE_PASS_DEPENDENCY(MachineOptimizationRemarkEmitterPass)
323INITIALIZE_PASS_DEPENDENCY(MachineRegisterClassInfoWrapperPass)
324INITIALIZE_PASS_DEPENDENCY(RegAllocEvictionAdvisorAnalysisLegacy)
325INITIALIZE_PASS_DEPENDENCY(RegAllocPriorityAdvisorAnalysisLegacy)
326INITIALIZE_PASS_END(RAGreedyLegacy, "greedy", "Greedy Register Allocator",
327 false, false)
328
329#ifndef NDEBUG
330const char *const RAGreedy::StageName[] = {
331 "RS_New",
332 "RS_Assign",
333 "RS_Split",
334 "RS_Split2",
335 "RS_Spill",
336 "RS_Done"
337};
338#endif
339
340// Hysteresis to use when comparing floats.
341// This helps stabilize decisions based on float comparisons.
342const float Hysteresis = (2007 / 2048.0f); // 0.97998046875
343
344FunctionPass* llvm::createGreedyRegisterAllocator() {
345 return new RAGreedyLegacy();
346}
347
348FunctionPass *llvm::createGreedyRegisterAllocator(RegAllocFilterFunc Ftor) {
349 return new RAGreedyLegacy(Ftor);
350}
351
352void RAGreedyLegacy::getAnalysisUsage(AnalysisUsage &AU) const {
353 AU.setPreservesCFG();
354 AU.addRequired<MachineBlockFrequencyInfoWrapperPass>();
355 AU.addRequired<LiveIntervalsWrapperPass>();
356 AU.addPreserved<LiveIntervalsWrapperPass>();
357 AU.addRequired<SlotIndexesWrapperPass>();
358 AU.addPreserved<SlotIndexesWrapperPass>();
359 AU.addRequired<LiveDebugVariablesWrapperLegacy>();
360 AU.addPreserved<LiveDebugVariablesWrapperLegacy>();
361 AU.addRequired<LiveStacksWrapperLegacy>();
362 AU.addPreserved<LiveStacksWrapperLegacy>();
363 AU.addRequired<MachineDominatorTreeWrapperPass>();
364 AU.addRequired<MachineLoopInfoWrapperPass>();
365 AU.addRequired<VirtRegMapWrapperLegacy>();
366 AU.addPreserved<VirtRegMapWrapperLegacy>();
367 AU.addRequired<LiveRegMatrixWrapperLegacy>();
368 AU.addPreserved<LiveRegMatrixWrapperLegacy>();
369 AU.addRequired<EdgeBundlesWrapperLegacy>();
370 AU.addRequired<SpillPlacementWrapperLegacy>();
371 AU.addRequired<MachineOptimizationRemarkEmitterPass>();
372 AU.addRequired<MachineRegisterClassInfoWrapperPass>();
373 AU.addRequired<RegAllocEvictionAdvisorAnalysisLegacy>();
374 AU.addRequired<RegAllocPriorityAdvisorAnalysisLegacy>();
375 MachineFunctionPass::getAnalysisUsage(AU);
376}
377
378//===----------------------------------------------------------------------===//
379// LiveRangeEdit delegate methods
380//===----------------------------------------------------------------------===//
381
382bool RAGreedy::LRE_CanEraseVirtReg(Register VirtReg) {
383 LiveInterval &LI = LIS->getInterval(Reg: VirtReg);
384 if (VRM->hasPhys(virtReg: VirtReg)) {
385 Matrix->unassign(VirtReg: LI);
386 aboutToRemoveInterval(LI);
387 return true;
388 }
389 // Unassigned virtreg is probably in the priority queue.
390 // RegAllocBase will erase it after dequeueing.
391 // Nonetheless, clear the live-range so that the debug
392 // dump will show the right state for that VirtReg.
393 LI.clear();
394 return false;
395}
396
397void RAGreedy::LRE_WillShrinkVirtReg(Register VirtReg) {
398 if (!VRM->hasPhys(virtReg: VirtReg))
399 return;
400
401 // Register is assigned, put it back on the queue for reassignment.
402 LiveInterval &LI = LIS->getInterval(Reg: VirtReg);
403 Matrix->unassign(VirtReg: LI);
404 RegAllocBase::enqueue(LI: &LI);
405}
406
407void RAGreedy::LRE_DidCloneVirtReg(Register New, Register Old) {
408 ExtraInfo->LRE_DidCloneVirtReg(New, Old);
409}
410
411void RAGreedy::ExtraRegInfo::LRE_DidCloneVirtReg(Register New, Register Old) {
412 // Cloning a register we haven't even heard about yet? Just ignore it.
413 if (!Info.inBounds(N: Old))
414 return;
415
416 // LRE may clone a virtual register because dead code elimination causes it to
417 // be split into connected components. The new components are much smaller
418 // than the original, so they should get a new chance at being assigned.
419 // same stage as the parent.
420 Info[Old].Stage = RS_Assign;
421 Info.grow(N: New.id());
422 Info[New] = Info[Old];
423}
424
425void RAGreedy::releaseMemory() {
426 SpillerInstance.reset();
427 GlobalCand.clear();
428}
429
430void RAGreedy::enqueueImpl(const LiveInterval *LI) { enqueue(CurQueue&: Queue, LI); }
431
432void RAGreedy::enqueue(PQueue &CurQueue, const LiveInterval *LI) {
433 // Prioritize live ranges by size, assigning larger ranges first.
434 // The queue holds (size, reg) pairs.
435 const Register Reg = LI->reg();
436 assert(Reg.isVirtual() && "Can only enqueue virtual registers");
437
438 auto Stage = ExtraInfo->getOrInitStage(Reg);
439 if (Stage == RS_New) {
440 Stage = RS_Assign;
441 ExtraInfo->setStage(Reg, Stage);
442 }
443
444 unsigned Ret = PriorityAdvisor->getPriority(LI: *LI);
445
446 // The virtual register number is a tie breaker for same-sized ranges.
447 // Give lower vreg numbers higher priority to assign them first.
448 CurQueue.push(x: std::make_pair(x&: Ret, y: ~Reg.id()));
449}
450
451unsigned DefaultPriorityAdvisor::getPriority(const LiveInterval &LI) const {
452 const unsigned Size = LI.getSize();
453 const Register Reg = LI.reg();
454 unsigned Prio;
455 LiveRangeStage Stage = RA.getExtraInfo().getStage(VirtReg: LI);
456
457 if (Stage == RS_Split) {
458 // Unsplit ranges that couldn't be allocated immediately are deferred until
459 // everything else has been allocated.
460 Prio = Size;
461 } else {
462 // Giant live ranges fall back to the global assignment heuristic, which
463 // prevents excessive spilling in pathological cases.
464 const TargetRegisterClass &RC = *MRI->getRegClass(Reg);
465 bool ForceGlobal = RC.GlobalPriority ||
466 (!ReverseLocalAssignment &&
467 (Size / SlotIndex::InstrDist) >
468 (2 * RegClassInfo.getNumAllocatableRegs(RC: &RC)));
469 unsigned GlobalBit = 0;
470
471 if (Stage == RS_Assign && !ForceGlobal && !LI.empty() &&
472 LIS->intervalIsInOneMBB(LI)) {
473 // Allocate original local ranges in linear instruction order. Since they
474 // are singly defined, this produces optimal coloring in the absence of
475 // global interference and other constraints.
476 if (!ReverseLocalAssignment)
477 Prio = LI.beginIndex().getApproxInstrDistance(other: Indexes->getLastIndex());
478 else {
479 // Allocating bottom up may allow many short LRGs to be assigned first
480 // to one of the cheap registers. This could be much faster for very
481 // large blocks on targets with many physical registers.
482 Prio = Indexes->getZeroIndex().getApproxInstrDistance(other: LI.endIndex());
483 }
484 } else {
485 // Allocate global and split ranges in long->short order. Long ranges that
486 // don't fit should be spilled (or split) ASAP so they don't create
487 // interference. Mark a bit to prioritize global above local ranges.
488 Prio = Size;
489 GlobalBit = 1;
490 }
491
492 // Priority bit layout:
493 // 31 RS_Assign priority
494 // 30 Preference priority
495 // if (RegClassPriorityTrumpsGlobalness)
496 // 29-25 AllocPriority
497 // 24 GlobalBit
498 // else
499 // 29 Global bit
500 // 28-24 AllocPriority
501 // 0-23 Size/Instr distance
502
503 // Clamp the size to fit with the priority masking scheme
504 Prio = std::min(a: Prio, b: (unsigned)maxUIntN(N: 24));
505 assert(isUInt<5>(RC.AllocationPriority) && "allocation priority overflow");
506
507 if (RegClassPriorityTrumpsGlobalness)
508 Prio |= RC.AllocationPriority << 25 | GlobalBit << 24;
509 else
510 Prio |= GlobalBit << 29 | RC.AllocationPriority << 24;
511
512 // Mark a higher bit to prioritize global and local above RS_Split.
513 Prio |= (1u << 31);
514
515 // Boost ranges that have a physical register hint.
516 if (VRM->hasKnownPreference(VirtReg: Reg))
517 Prio |= (1u << 30);
518 }
519
520 return Prio;
521}
522
523unsigned DummyPriorityAdvisor::getPriority(const LiveInterval &LI) const {
524 // Prioritize by virtual register number, lowest first.
525 Register Reg = LI.reg();
526 return ~Reg.virtRegIndex();
527}
528
529const LiveInterval *RAGreedy::dequeue() { return dequeue(CurQueue&: Queue); }
530
531const LiveInterval *RAGreedy::dequeue(PQueue &CurQueue) {
532 if (CurQueue.empty())
533 return nullptr;
534 LiveInterval *LI = &LIS->getInterval(Reg: ~CurQueue.top().second);
535 CurQueue.pop();
536 return LI;
537}
538
539//===----------------------------------------------------------------------===//
540// Direct Assignment
541//===----------------------------------------------------------------------===//
542
543/// tryAssign - Try to assign VirtReg to an available register.
544MCRegister RAGreedy::tryAssign(const LiveInterval &VirtReg,
545 AllocationOrder &Order,
546 SmallVectorImpl<Register> &NewVRegs,
547 const SmallVirtRegSet &FixedRegisters) {
548 MCRegister PhysReg;
549 for (auto I = Order.begin(), E = Order.end(); I != E && !PhysReg; ++I) {
550 assert(*I);
551 if (!Matrix->checkInterference(VirtReg, PhysReg: *I)) {
552 if (I.isHint())
553 return *I;
554 else
555 PhysReg = *I;
556 }
557 }
558 if (!PhysReg.isValid())
559 return PhysReg;
560
561 // PhysReg is available, but there may be a better choice.
562
563 // If we missed a simple hint, try to cheaply evict interference from the
564 // preferred register.
565 if (Register Hint = MRI->getSimpleHint(VReg: VirtReg.reg()))
566 if (Order.isHint(Reg: Hint)) {
567 MCRegister PhysHint = Hint.asMCReg();
568 LLVM_DEBUG(dbgs() << "missed hint " << printReg(PhysHint, TRI) << '\n');
569
570 if (EvictAdvisor->canEvictHintInterference(VirtReg, PhysReg: PhysHint,
571 FixedRegisters)) {
572 evictInterference(VirtReg, PhysHint, NewVRegs);
573 return PhysHint;
574 }
575
576 // We can also split the virtual register in cold blocks.
577 if (trySplitAroundHintReg(Hint: PhysHint, VirtReg, NewVRegs, Order))
578 return MCRegister();
579
580 // Record the missed hint, we may be able to recover
581 // at the end if the surrounding allocation changed.
582 SetOfBrokenHints.insert(X: &VirtReg);
583 }
584
585 // Try to evict interference from a cheaper alternative.
586 uint8_t Cost = RegCosts[PhysReg.id()];
587
588 // Most registers have 0 additional cost.
589 if (!Cost)
590 return PhysReg;
591
592 LLVM_DEBUG(dbgs() << printReg(PhysReg, TRI) << " is available at cost "
593 << (unsigned)Cost << '\n');
594 MCRegister CheapReg = tryEvict(VirtReg, Order, NewVRegs, Cost, FixedRegisters);
595 return CheapReg ? CheapReg : PhysReg;
596}
597
598//===----------------------------------------------------------------------===//
599// Interference eviction
600//===----------------------------------------------------------------------===//
601
602bool RegAllocEvictionAdvisor::canReassign(const LiveInterval &VirtReg,
603 MCRegister FromReg) const {
604 auto HasRegUnitInterference = [&](MCRegUnit Unit) {
605 // Instantiate a "subquery", not to be confused with the Queries array.
606 LiveIntervalUnion::Query SubQ(
607 VirtReg, Matrix->getLiveUnions()[static_cast<unsigned>(Unit)]);
608 return SubQ.checkInterference();
609 };
610
611 for (MCRegister Reg :
612 AllocationOrder::create(VirtReg: VirtReg.reg(), VRM: *VRM, RegClassInfo, Matrix)) {
613 if (Reg == FromReg)
614 continue;
615 // If no units have interference, reassignment is possible.
616 if (none_of(Range: TRI->regunits(Reg), P: HasRegUnitInterference)) {
617 LLVM_DEBUG(dbgs() << "can reassign: " << VirtReg << " from "
618 << printReg(FromReg, TRI) << " to "
619 << printReg(Reg, TRI) << '\n');
620 return true;
621 }
622 }
623 return false;
624}
625
626/// evictInterference - Evict any interferring registers that prevent VirtReg
627/// from being assigned to Physreg. This assumes that canEvictInterference
628/// returned true.
629void RAGreedy::evictInterference(const LiveInterval &VirtReg,
630 MCRegister PhysReg,
631 SmallVectorImpl<Register> &NewVRegs) {
632 // Make sure that VirtReg has a cascade number, and assign that cascade
633 // number to every evicted register. These live ranges than then only be
634 // evicted by a newer cascade, preventing infinite loops.
635 unsigned Cascade = ExtraInfo->getOrAssignNewCascade(Reg: VirtReg.reg());
636
637 LLVM_DEBUG(dbgs() << "evicting " << printReg(PhysReg, TRI)
638 << " interference: Cascade " << Cascade << '\n');
639
640 // Collect all interfering virtregs first.
641 SmallVector<const LiveInterval *, 8> Intfs;
642 for (MCRegUnit Unit : TRI->regunits(Reg: PhysReg)) {
643 LiveIntervalUnion::Query &Q = Matrix->query(LR: VirtReg, RegUnit: Unit);
644 // We usually have the interfering VRegs cached so collectInterferingVRegs()
645 // should be fast, we may need to recalculate if when different physregs
646 // overlap the same register unit so we had different SubRanges queried
647 // against it.
648 ArrayRef<const LiveInterval *> IVR = Q.interferingVRegs();
649 Intfs.append(in_start: IVR.begin(), in_end: IVR.end());
650 }
651
652 // Evict them second. This will invalidate the queries.
653 for (const LiveInterval *Intf : Intfs) {
654 // The same VirtReg may be present in multiple RegUnits. Skip duplicates.
655 if (!VRM->hasPhys(virtReg: Intf->reg()))
656 continue;
657
658 Matrix->unassign(VirtReg: *Intf);
659 assert((ExtraInfo->getCascade(Intf->reg()) < Cascade ||
660 (Cascade < ExtraInfo->getCascade(Intf->reg()) &&
661 EvictAdvisor->isUrgentEviction(VirtReg, *Intf)) ||
662 VirtReg.isSpillable() < Intf->isSpillable()) &&
663 "Cannot decrease cascade number, illegal eviction");
664 ExtraInfo->setCascade(Reg: Intf->reg(), Cascade);
665 ++NumEvicted;
666 NewVRegs.push_back(Elt: Intf->reg());
667 }
668}
669
670MCRegister
671RegAllocEvictionAdvisor::getUnusedCalleeSavedReg(const LiveInterval &VirtReg,
672 MCRegister PhysReg) const {
673 auto IsUnusedCSR = [&](MCRegUnit Unit) {
674 MCRegister CSR = RegClassInfo.getCalleeSavedAlias(Unit);
675 if (CSR && !Matrix->isPhysRegUsed(PhysReg: CSR))
676 return CSR;
677 return MCRegister();
678 };
679
680 for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
681 MCRegUnit Unit = (*Units).first;
682 LaneBitmask Mask = (*Units).second;
683 if (VirtReg.hasSubRanges() &&
684 llvm::none_of(Range: VirtReg.subranges(),
685 P: [&](const LiveInterval::SubRange &S) {
686 return (S.LaneMask & Mask).any();
687 }))
688 continue;
689 if (MCRegister CSR = IsUnusedCSR(Unit))
690 return CSR;
691 }
692 return MCRegister();
693}
694
695std::optional<unsigned>
696RegAllocEvictionAdvisor::getOrderLimit(const LiveInterval &VirtReg,
697 const AllocationOrder &Order,
698 unsigned CostPerUseLimit) const {
699 unsigned OrderLimit = Order.getOrder().size();
700
701 if (CostPerUseLimit < uint8_t(~0u)) {
702 // Check of any registers in RC are below CostPerUseLimit.
703 const TargetRegisterClass *RC = MRI->getRegClass(Reg: VirtReg.reg());
704 uint8_t MinCost = RegClassInfo.getMinCost(RC);
705 if (MinCost >= CostPerUseLimit) {
706 LLVM_DEBUG(dbgs() << TRI->getRegClassName(RC) << " minimum cost = "
707 << MinCost << ", no cheaper registers to be found.\n");
708 return std::nullopt;
709 }
710
711 // It is normal for register classes to have a long tail of registers with
712 // the same cost. We don't need to look at them if they're too expensive.
713 // LastCostChange is an index into the original RegisterClassInfo order, so
714 // it cannot be used to shorten a custom order.
715 if (!Order.hasCustomOrder() &&
716 RegCosts[Order.getOrder().back()] >= CostPerUseLimit) {
717 OrderLimit = RegClassInfo.getLastCostChange(RC);
718 LLVM_DEBUG(dbgs() << "Only trying the first " << OrderLimit
719 << " regs.\n");
720 }
721 }
722 return OrderLimit;
723}
724
725bool RegAllocEvictionAdvisor::canAllocatePhysReg(const LiveInterval &VirtReg,
726 unsigned CostPerUseLimit,
727 MCRegister PhysReg) const {
728 if (RegCosts[PhysReg.id()] >= CostPerUseLimit)
729 return false;
730 // The first use of a callee-saved register in a function has cost 1.
731 // Don't start using a CSR when the CostPerUseLimit is low.
732 if (CostPerUseLimit == 1) {
733 if (MCRegister CSR = getUnusedCalleeSavedReg(VirtReg, PhysReg)) {
734 LLVM_DEBUG(dbgs() << printReg(PhysReg, TRI) << " would clobber CSR "
735 << printReg(CSR, TRI) << '\n');
736 return false;
737 }
738 }
739 return true;
740}
741
742/// tryEvict - Try to evict all interferences for a physreg.
743/// @param VirtReg Currently unassigned virtual register.
744/// @param Order Physregs to try.
745/// @return Physreg to assign VirtReg, or 0.
746MCRegister RAGreedy::tryEvict(const LiveInterval &VirtReg,
747 AllocationOrder &Order,
748 SmallVectorImpl<Register> &NewVRegs,
749 uint8_t CostPerUseLimit,
750 const SmallVirtRegSet &FixedRegisters) {
751 NamedRegionTimer T("evict", "Evict", TimerGroupName, TimerGroupDescription,
752 TimePassesIsEnabled);
753
754 MCRegister BestPhys = EvictAdvisor->tryFindEvictionCandidate(
755 VirtReg, Order, CostPerUseLimit, FixedRegisters);
756 if (BestPhys.isValid())
757 evictInterference(VirtReg, PhysReg: BestPhys, NewVRegs);
758 return BestPhys;
759}
760
761//===----------------------------------------------------------------------===//
762// Region Splitting
763//===----------------------------------------------------------------------===//
764
765/// addSplitConstraints - Fill out the SplitConstraints vector based on the
766/// interference pattern in Physreg and its aliases. Add the constraints to
767/// SpillPlacement and return the static cost of this split in Cost, assuming
768/// that all preferences in SplitConstraints are met.
769/// Return false if there are no bundles with positive bias, or if the static
770/// cost reaches MaxCost.
771bool RAGreedy::addSplitConstraints(InterferenceCache::Cursor Intf,
772 BlockFrequency &Cost,
773 BlockFrequency MaxCost) {
774 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
775
776 // Reset interference dependent info.
777 SplitConstraints.resize(N: UseBlocks.size());
778 BlockFrequency StaticCost = BlockFrequency(0);
779 for (unsigned I = 0; I != UseBlocks.size(); ++I) {
780 const SplitAnalysis::BlockInfo &BI = UseBlocks[I];
781 SpillPlacement::BlockConstraint &BC = SplitConstraints[I];
782
783 BC.Number = BI.MBB->getNumber();
784 Intf.moveToBlock(MBBNum: BC.Number);
785 BC.Entry = BI.LiveIn ? SpillPlacement::PrefReg : SpillPlacement::DontCare;
786 BC.Exit = (BI.LiveOut &&
787 !LIS->getInstructionFromIndex(index: BI.LastInstr)->isImplicitDef())
788 ? SpillPlacement::PrefReg
789 : SpillPlacement::DontCare;
790 BC.ChangesValue = BI.FirstDef.isValid();
791
792 if (!Intf.hasInterference())
793 continue;
794
795 // Number of spill code instructions to insert.
796 unsigned Ins = 0;
797
798 // Interference for the live-in value.
799 if (BI.LiveIn) {
800 if (Intf.first() <= Indexes->getMBBStartIdx(mbb: BI.MBB)) {
801 BC.Entry = SpillPlacement::MustSpill;
802 ++Ins;
803 } else if (Intf.first() < BI.FirstInstr) {
804 BC.Entry = SpillPlacement::PrefSpill;
805 ++Ins;
806 } else if (Intf.first() < BI.LastInstr) {
807 ++Ins;
808 }
809
810 // Abort if the spill cannot be inserted at the MBB' start
811 if (((BC.Entry == SpillPlacement::MustSpill) ||
812 (BC.Entry == SpillPlacement::PrefSpill)) &&
813 SlotIndex::isEarlierInstr(A: BI.FirstInstr,
814 B: SA->getFirstSplitPoint(Num: BC.Number)))
815 return false;
816 }
817
818 // Interference for the live-out value.
819 if (BI.LiveOut) {
820 if (Intf.last() >= SA->getLastSplitPoint(Num: BC.Number)) {
821 BC.Exit = SpillPlacement::MustSpill;
822 ++Ins;
823 } else if (Intf.last() > BI.LastInstr) {
824 BC.Exit = SpillPlacement::PrefSpill;
825 ++Ins;
826 } else if (Intf.last() > BI.FirstInstr) {
827 ++Ins;
828 }
829 }
830
831 // Accumulate the total frequency of inserted spill code.
832 while (Ins--)
833 StaticCost += SpillPlacer->getBlockFrequency(Number: BC.Number);
834
835 if (StaticCost >= MaxCost)
836 return false;
837 }
838 Cost = StaticCost;
839
840 // Add constraints for use-blocks. Note that these are the only constraints
841 // that may add a positive bias, it is downhill from here.
842 SpillPlacer->addConstraints(LiveBlocks: SplitConstraints);
843 return SpillPlacer->scanActiveBundles();
844}
845
846/// addThroughConstraints - Add constraints and links to SpillPlacer from the
847/// live-through blocks in Blocks.
848bool RAGreedy::addThroughConstraints(InterferenceCache::Cursor Intf,
849 ArrayRef<unsigned> Blocks) {
850 const unsigned GroupSize = 8;
851 SpillPlacement::BlockConstraint BCS[GroupSize];
852 unsigned TBS[GroupSize];
853 unsigned B = 0, T = 0;
854
855 for (unsigned Number : Blocks) {
856 Intf.moveToBlock(MBBNum: Number);
857
858 if (!Intf.hasInterference()) {
859 assert(T < GroupSize && "Array overflow");
860 TBS[T] = Number;
861 if (++T == GroupSize) {
862 SpillPlacer->addLinks(Links: ArrayRef(TBS, T));
863 T = 0;
864 }
865 continue;
866 }
867
868 assert(B < GroupSize && "Array overflow");
869 BCS[B].Number = Number;
870
871 // Abort if the spill cannot be inserted at the MBB' start
872 MachineBasicBlock *MBB = MF->getBlockNumbered(N: Number);
873 auto FirstNonDebugInstr = MBB->getFirstNonDebugInstr();
874 if (FirstNonDebugInstr != MBB->end() &&
875 SlotIndex::isEarlierInstr(A: LIS->getInstructionIndex(Instr: *FirstNonDebugInstr),
876 B: SA->getFirstSplitPoint(Num: Number)))
877 return false;
878
879 // Interference for the live-in value.
880 Register Reg = SA->getParent().reg();
881 auto InsertPt = MBB->SkipPHIsLabelsAndDebug(I: MBB->begin(), Reg);
882 SlotIndex InsertIdx = InsertPt == MBB->end()
883 ? Indexes->getMBBEndIdx(mbb: MBB)
884 : LIS->getInstructionIndex(Instr: *InsertPt);
885 if (Intf.first() <= Indexes->getMBBStartIdx(mbb: MBB) ||
886 SlotIndex::isEarlierInstr(A: Intf.first(), B: InsertIdx))
887 BCS[B].Entry = SpillPlacement::MustSpill;
888 else
889 BCS[B].Entry = SpillPlacement::PrefSpill;
890
891 // Interference for the live-out value.
892 if (Intf.last() >= SA->getLastSplitPoint(Num: Number))
893 BCS[B].Exit = SpillPlacement::MustSpill;
894 else
895 BCS[B].Exit = SpillPlacement::PrefSpill;
896
897 if (++B == GroupSize) {
898 SpillPlacer->addConstraints(LiveBlocks: ArrayRef(BCS, B));
899 B = 0;
900 }
901 }
902
903 SpillPlacer->addConstraints(LiveBlocks: ArrayRef(BCS, B));
904 SpillPlacer->addLinks(Links: ArrayRef(TBS, T));
905 return true;
906}
907
908bool RAGreedy::growRegion(GlobalSplitCandidate &Cand) {
909 // Keep track of through blocks that have not been added to SpillPlacer.
910 BitVector Todo = SA->getThroughBlocks();
911 SmallVectorImpl<unsigned> &ActiveBlocks = Cand.ActiveBlocks;
912 unsigned AddedTo = 0;
913#ifndef NDEBUG
914 unsigned Visited = 0;
915#endif
916
917 unsigned long Budget = GrowRegionComplexityBudget;
918 while (true) {
919 ArrayRef<unsigned> NewBundles = SpillPlacer->getRecentPositive();
920 // Find new through blocks in the periphery of PrefRegBundles.
921 for (unsigned Bundle : NewBundles) {
922 // Look at all blocks connected to Bundle in the full graph.
923 ArrayRef<unsigned> Blocks = Bundles->getBlocks(Bundle);
924 // Limit compilation time by bailing out after we use all our budget.
925 if (Blocks.size() >= Budget)
926 return false;
927 Budget -= Blocks.size();
928 for (unsigned Block : Blocks) {
929 if (!Todo.test(Idx: Block))
930 continue;
931 Todo.reset(Idx: Block);
932 // This is a new through block. Add it to SpillPlacer later.
933 ActiveBlocks.push_back(Elt: Block);
934#ifndef NDEBUG
935 ++Visited;
936#endif
937 }
938 }
939 // Any new blocks to add?
940 if (ActiveBlocks.size() == AddedTo)
941 break;
942
943 // Compute through constraints from the interference, or assume that all
944 // through blocks prefer spilling when forming compact regions.
945 auto NewBlocks = ArrayRef(ActiveBlocks).slice(N: AddedTo);
946 if (Cand.PhysReg) {
947 if (!addThroughConstraints(Intf: Cand.Intf, Blocks: NewBlocks))
948 return false;
949 } else {
950 // Providing that the variable being spilled does not look like a loop
951 // induction variable, which is expensive to spill around and better
952 // pushed into a condition inside the loop if possible, provide a strong
953 // negative bias on through blocks to prevent unwanted liveness on loop
954 // backedges.
955 bool PrefSpill = true;
956 if (SA->looksLikeLoopIV() && NewBlocks.size() >= 2) {
957 // Check that the current bundle is adding a Header + start+end of
958 // loop-internal blocks. If the block is indeed a header, don't make
959 // the NewBlocks as PrefSpill to allow the variable to be live in
960 // Header<->Latch.
961 MachineLoop *L = Loops->getLoopFor(BB: MF->getBlockNumbered(N: NewBlocks[0]));
962 if (L && L->getHeader()->getNumber() == (int)NewBlocks[0] &&
963 all_of(Range: NewBlocks.drop_front(), P: [&](unsigned Block) {
964 return L == Loops->getLoopFor(BB: MF->getBlockNumbered(N: Block));
965 }))
966 PrefSpill = false;
967 }
968 if (PrefSpill)
969 SpillPlacer->addPrefSpill(Blocks: NewBlocks, /* Strong= */ true);
970 }
971 AddedTo = ActiveBlocks.size();
972
973 // Perhaps iterating can enable more bundles?
974 SpillPlacer->iterate();
975 }
976 LLVM_DEBUG(dbgs() << ", v=" << Visited);
977 return true;
978}
979
980/// calcCompactRegion - Compute the set of edge bundles that should be live
981/// when splitting the current live range into compact regions. Compact
982/// regions can be computed without looking at interference. They are the
983/// regions formed by removing all the live-through blocks from the live range.
984///
985/// Returns false if the current live range is already compact, or if the
986/// compact regions would form single block regions anyway.
987bool RAGreedy::calcCompactRegion(GlobalSplitCandidate &Cand) {
988 // Without any through blocks, the live range is already compact.
989 if (!SA->getNumThroughBlocks())
990 return false;
991
992 // Compact regions don't correspond to any physreg.
993 Cand.reset(Cache&: IntfCache, Reg: MCRegister::NoRegister);
994
995 LLVM_DEBUG(dbgs() << "Compact region bundles");
996
997 // Use the spill placer to determine the live bundles. GrowRegion pretends
998 // that all the through blocks have interference when PhysReg is unset.
999 SpillPlacer->prepare(RegBundles&: Cand.LiveBundles);
1000
1001 // The static split cost will be zero since Cand.Intf reports no interference.
1002 BlockFrequency Cost;
1003 if (!addSplitConstraints(Intf: Cand.Intf, Cost, MaxCost: BlockFrequency::max())) {
1004 LLVM_DEBUG(dbgs() << ", none.\n");
1005 return false;
1006 }
1007
1008 if (!growRegion(Cand)) {
1009 LLVM_DEBUG(dbgs() << ", cannot spill all interferences.\n");
1010 return false;
1011 }
1012
1013 SpillPlacer->finish();
1014
1015 if (!Cand.LiveBundles.any()) {
1016 LLVM_DEBUG(dbgs() << ", none.\n");
1017 return false;
1018 }
1019
1020 LLVM_DEBUG({
1021 for (int I : Cand.LiveBundles.set_bits())
1022 dbgs() << " EB#" << I;
1023 dbgs() << ".\n";
1024 });
1025 return true;
1026}
1027
1028/// calcBlockSplitCost - Compute how expensive it would be to split the live
1029/// range in SA around all use blocks instead of forming bundle regions.
1030BlockFrequency RAGreedy::calcBlockSplitCost() {
1031 BlockFrequency Cost = BlockFrequency(0);
1032 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
1033 for (const SplitAnalysis::BlockInfo &BI : UseBlocks) {
1034 unsigned Number = BI.MBB->getNumber();
1035 // We normally only need one spill instruction - a load or a store.
1036 Cost += SpillPlacer->getBlockFrequency(Number);
1037
1038 // Unless the value is redefined in the block.
1039 if (BI.LiveIn && BI.LiveOut && BI.FirstDef)
1040 Cost += SpillPlacer->getBlockFrequency(Number);
1041 }
1042 return Cost;
1043}
1044
1045/// calcGlobalSplitCost - Return the global split cost of following the split
1046/// pattern in LiveBundles. This cost should be added to the local cost of the
1047/// interference pattern in SplitConstraints.
1048///
1049BlockFrequency RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand,
1050 const AllocationOrder &Order) {
1051 BlockFrequency GlobalCost = BlockFrequency(0);
1052 const BitVector &LiveBundles = Cand.LiveBundles;
1053 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
1054 for (unsigned I = 0; I != UseBlocks.size(); ++I) {
1055 const SplitAnalysis::BlockInfo &BI = UseBlocks[I];
1056 SpillPlacement::BlockConstraint &BC = SplitConstraints[I];
1057 bool RegIn = LiveBundles[Bundles->getBundle(N: BC.Number, Out: false)];
1058 bool RegOut = LiveBundles[Bundles->getBundle(N: BC.Number, Out: true)];
1059 unsigned Ins = 0;
1060
1061 Cand.Intf.moveToBlock(MBBNum: BC.Number);
1062
1063 if (BI.LiveIn)
1064 Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg);
1065 if (BI.LiveOut)
1066 Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg);
1067 while (Ins--)
1068 GlobalCost += SpillPlacer->getBlockFrequency(Number: BC.Number);
1069 }
1070
1071 for (unsigned Number : Cand.ActiveBlocks) {
1072 bool RegIn = LiveBundles[Bundles->getBundle(N: Number, Out: false)];
1073 bool RegOut = LiveBundles[Bundles->getBundle(N: Number, Out: true)];
1074 if (!RegIn && !RegOut)
1075 continue;
1076 if (RegIn && RegOut) {
1077 // We need double spill code if this block has interference.
1078 Cand.Intf.moveToBlock(MBBNum: Number);
1079 if (Cand.Intf.hasInterference()) {
1080 GlobalCost += SpillPlacer->getBlockFrequency(Number);
1081 GlobalCost += SpillPlacer->getBlockFrequency(Number);
1082 }
1083 continue;
1084 }
1085 // live-in / stack-out or stack-in live-out.
1086 GlobalCost += SpillPlacer->getBlockFrequency(Number);
1087 }
1088 return GlobalCost;
1089}
1090
1091/// splitAroundRegion - Split the current live range around the regions
1092/// determined by BundleCand and GlobalCand.
1093///
1094/// Before calling this function, GlobalCand and BundleCand must be initialized
1095/// so each bundle is assigned to a valid candidate, or NoCand for the
1096/// stack-bound bundles. The shared SA/SE SplitAnalysis and SplitEditor
1097/// objects must be initialized for the current live range, and intervals
1098/// created for the used candidates.
1099///
1100/// @param LREdit The LiveRangeEdit object handling the current split.
1101/// @param UsedCands List of used GlobalCand entries. Every BundleCand value
1102/// must appear in this list.
1103void RAGreedy::splitAroundRegion(LiveRangeEdit &LREdit,
1104 ArrayRef<unsigned> UsedCands) {
1105 // These are the intervals created for new global ranges. We may create more
1106 // intervals for local ranges.
1107 const unsigned NumGlobalIntvs = LREdit.size();
1108 LLVM_DEBUG(dbgs() << "splitAroundRegion with " << NumGlobalIntvs
1109 << " globals.\n");
1110 assert(NumGlobalIntvs && "No global intervals configured");
1111
1112 // Isolate even single instructions when dealing with a proper sub-class.
1113 // That guarantees register class inflation for the stack interval because it
1114 // is all copies.
1115 Register Reg = SA->getParent().reg();
1116 bool SingleInstrs = RegClassInfo->isProperSubClass(RC: MRI->getRegClass(Reg));
1117
1118 // First handle all the blocks with uses.
1119 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
1120 for (const SplitAnalysis::BlockInfo &BI : UseBlocks) {
1121 unsigned Number = BI.MBB->getNumber();
1122 unsigned IntvIn = 0, IntvOut = 0;
1123 SlotIndex IntfIn, IntfOut;
1124 if (BI.LiveIn) {
1125 unsigned CandIn = BundleCand[Bundles->getBundle(N: Number, Out: false)];
1126 if (CandIn != NoCand) {
1127 GlobalSplitCandidate &Cand = GlobalCand[CandIn];
1128 IntvIn = Cand.IntvIdx;
1129 Cand.Intf.moveToBlock(MBBNum: Number);
1130 IntfIn = Cand.Intf.first();
1131 }
1132 }
1133 if (BI.LiveOut) {
1134 unsigned CandOut = BundleCand[Bundles->getBundle(N: Number, Out: true)];
1135 if (CandOut != NoCand) {
1136 GlobalSplitCandidate &Cand = GlobalCand[CandOut];
1137 IntvOut = Cand.IntvIdx;
1138 Cand.Intf.moveToBlock(MBBNum: Number);
1139 IntfOut = Cand.Intf.last();
1140 }
1141 }
1142
1143 // Create separate intervals for isolated blocks with multiple uses.
1144 if (!IntvIn && !IntvOut) {
1145 LLVM_DEBUG(dbgs() << printMBBReference(*BI.MBB) << " isolated.\n");
1146 if (SA->shouldSplitSingleBlock(BI, SingleInstrs))
1147 SE->splitSingleBlock(BI);
1148 continue;
1149 }
1150
1151 if (IntvIn && IntvOut)
1152 SE->splitLiveThroughBlock(MBBNum: Number, IntvIn, LeaveBefore: IntfIn, IntvOut, EnterAfter: IntfOut);
1153 else if (IntvIn)
1154 SE->splitRegInBlock(BI, IntvIn, LeaveBefore: IntfIn);
1155 else
1156 SE->splitRegOutBlock(BI, IntvOut, EnterAfter: IntfOut);
1157 }
1158
1159 // Handle live-through blocks. The relevant live-through blocks are stored in
1160 // the ActiveBlocks list with each candidate. We need to filter out
1161 // duplicates.
1162 BitVector Todo = SA->getThroughBlocks();
1163 for (unsigned UsedCand : UsedCands) {
1164 ArrayRef<unsigned> Blocks = GlobalCand[UsedCand].ActiveBlocks;
1165 for (unsigned Number : Blocks) {
1166 if (!Todo.test(Idx: Number))
1167 continue;
1168 Todo.reset(Idx: Number);
1169
1170 unsigned IntvIn = 0, IntvOut = 0;
1171 SlotIndex IntfIn, IntfOut;
1172
1173 unsigned CandIn = BundleCand[Bundles->getBundle(N: Number, Out: false)];
1174 if (CandIn != NoCand) {
1175 GlobalSplitCandidate &Cand = GlobalCand[CandIn];
1176 IntvIn = Cand.IntvIdx;
1177 Cand.Intf.moveToBlock(MBBNum: Number);
1178 IntfIn = Cand.Intf.first();
1179 }
1180
1181 unsigned CandOut = BundleCand[Bundles->getBundle(N: Number, Out: true)];
1182 if (CandOut != NoCand) {
1183 GlobalSplitCandidate &Cand = GlobalCand[CandOut];
1184 IntvOut = Cand.IntvIdx;
1185 Cand.Intf.moveToBlock(MBBNum: Number);
1186 IntfOut = Cand.Intf.last();
1187 }
1188 if (!IntvIn && !IntvOut)
1189 continue;
1190 SE->splitLiveThroughBlock(MBBNum: Number, IntvIn, LeaveBefore: IntfIn, IntvOut, EnterAfter: IntfOut);
1191 }
1192 }
1193
1194 ++NumGlobalSplits;
1195
1196 SmallVector<unsigned, 8> IntvMap;
1197 SE->finish(LRMap: &IntvMap);
1198 DebugVars->splitRegister(OldReg: Reg, NewRegs: LREdit.regs(), LIS&: *LIS);
1199
1200 unsigned OrigBlocks = SA->getNumLiveBlocks();
1201
1202 // Sort out the new intervals created by splitting. We get four kinds:
1203 // - Remainder intervals should not be split again.
1204 // - Candidate intervals can be assigned to Cand.PhysReg.
1205 // - Block-local splits are candidates for local splitting.
1206 // - DCE leftovers should go back on the queue.
1207 for (unsigned I = 0, E = LREdit.size(); I != E; ++I) {
1208 const LiveInterval &Reg = LIS->getInterval(Reg: LREdit.get(idx: I));
1209
1210 // Ignore old intervals from DCE.
1211 if (ExtraInfo->getOrInitStage(Reg: Reg.reg()) != RS_New)
1212 continue;
1213
1214 // Remainder interval. Don't try splitting again, spill if it doesn't
1215 // allocate.
1216 if (IntvMap[I] == 0) {
1217 ExtraInfo->setStage(VirtReg: Reg, Stage: RS_Spill);
1218 continue;
1219 }
1220
1221 // Global intervals. Allow repeated splitting as long as the number of live
1222 // blocks is strictly decreasing.
1223 if (IntvMap[I] < NumGlobalIntvs) {
1224 if (SA->countLiveBlocks(li: &Reg) >= OrigBlocks) {
1225 LLVM_DEBUG(dbgs() << "Main interval covers the same " << OrigBlocks
1226 << " blocks as original.\n");
1227 // Don't allow repeated splitting as a safe guard against looping.
1228 ExtraInfo->setStage(VirtReg: Reg, Stage: RS_Split2);
1229 }
1230 continue;
1231 }
1232
1233 // Other intervals are treated as new. This includes local intervals created
1234 // for blocks with multiple uses, and anything created by DCE.
1235 }
1236
1237 if (VerifyEnabled)
1238 MF->verify(LiveInts: LIS, Indexes, Banner: "After splitting live range around region",
1239 OS: &errs());
1240}
1241
1242MCRegister RAGreedy::tryRegionSplit(const LiveInterval &VirtReg,
1243 AllocationOrder &Order,
1244 SmallVectorImpl<Register> &NewVRegs) {
1245 if (!TRI->shouldRegionSplitForVirtReg(MF: *MF, VirtReg))
1246 return MCRegister::NoRegister;
1247 unsigned NumCands = 0;
1248 BlockFrequency SpillCost = calcBlockSplitCost();
1249 BlockFrequency BestCost;
1250
1251 // Check if we can split this live range around a compact region.
1252 bool HasCompact = calcCompactRegion(Cand&: GlobalCand.front());
1253 if (HasCompact) {
1254 // Yes, keep GlobalCand[0] as the compact region candidate.
1255 NumCands = 1;
1256 BestCost = BlockFrequency::max();
1257 } else {
1258 // No benefit from the compact region, our fallback will be per-block
1259 // splitting. Make sure we find a solution that is cheaper than spilling.
1260 BestCost = SpillCost;
1261 LLVM_DEBUG(dbgs() << "Cost of isolating all blocks = "
1262 << printBlockFreq(*MBFI, BestCost) << '\n');
1263 }
1264
1265 unsigned BestCand = calculateRegionSplitCost(VirtReg, Order, BestCost,
1266 NumCands, IgnoreCSR: false /*IgnoreCSR*/);
1267
1268 // No solutions found, fall back to single block splitting.
1269 if (!HasCompact && BestCand == NoCand)
1270 return MCRegister::NoRegister;
1271
1272 return doRegionSplit(VirtReg, BestCand, HasCompact, NewVRegs);
1273}
1274
1275unsigned RAGreedy::calculateRegionSplitCostAroundReg(MCRegister PhysReg,
1276 AllocationOrder &Order,
1277 BlockFrequency &BestCost,
1278 unsigned &NumCands,
1279 unsigned &BestCand) {
1280 // Discard bad candidates before we run out of interference cache cursors.
1281 // This will only affect register classes with a lot of registers (>32).
1282 if (NumCands == IntfCache.getMaxCursors()) {
1283 unsigned WorstCount = ~0u;
1284 unsigned Worst = 0;
1285 for (unsigned CandIndex = 0; CandIndex != NumCands; ++CandIndex) {
1286 if (CandIndex == BestCand || !GlobalCand[CandIndex].PhysReg)
1287 continue;
1288 unsigned Count = GlobalCand[CandIndex].LiveBundles.count();
1289 if (Count < WorstCount) {
1290 Worst = CandIndex;
1291 WorstCount = Count;
1292 }
1293 }
1294 --NumCands;
1295 GlobalCand[Worst] = GlobalCand[NumCands];
1296 if (BestCand == NumCands)
1297 BestCand = Worst;
1298 }
1299
1300 if (GlobalCand.size() <= NumCands)
1301 GlobalCand.resize(N: NumCands+1);
1302 GlobalSplitCandidate &Cand = GlobalCand[NumCands];
1303 Cand.reset(Cache&: IntfCache, Reg: PhysReg);
1304
1305 SpillPlacer->prepare(RegBundles&: Cand.LiveBundles);
1306 BlockFrequency Cost;
1307 if (!addSplitConstraints(Intf: Cand.Intf, Cost, MaxCost: BestCost)) {
1308 LLVM_DEBUG(dbgs() << printReg(PhysReg, TRI)
1309 << "\tno positive bundles or too expensive\n");
1310 return BestCand;
1311 }
1312 LLVM_DEBUG(dbgs() << printReg(PhysReg, TRI)
1313 << "\tstatic = " << printBlockFreq(*MBFI, Cost));
1314 if (Cost >= BestCost) {
1315 LLVM_DEBUG({
1316 if (BestCand == NoCand)
1317 dbgs() << " worse than no bundles\n";
1318 else
1319 dbgs() << " worse than "
1320 << printReg(GlobalCand[BestCand].PhysReg, TRI) << '\n';
1321 });
1322 return BestCand;
1323 }
1324 if (!growRegion(Cand)) {
1325 LLVM_DEBUG(dbgs() << ", cannot spill all interferences.\n");
1326 return BestCand;
1327 }
1328
1329 SpillPlacer->finish();
1330
1331 // No live bundles, defer to splitSingleBlocks().
1332 if (!Cand.LiveBundles.any()) {
1333 LLVM_DEBUG(dbgs() << " no bundles.\n");
1334 return BestCand;
1335 }
1336
1337 Cost += calcGlobalSplitCost(Cand, Order);
1338 LLVM_DEBUG({
1339 dbgs() << ", total = " << printBlockFreq(*MBFI, Cost) << " with bundles";
1340 for (int I : Cand.LiveBundles.set_bits())
1341 dbgs() << " EB#" << I;
1342 dbgs() << ".\n";
1343 });
1344 if (Cost < BestCost) {
1345 BestCand = NumCands;
1346 BestCost = Cost;
1347 }
1348 ++NumCands;
1349
1350 return BestCand;
1351}
1352
1353unsigned RAGreedy::calculateRegionSplitCost(const LiveInterval &VirtReg,
1354 AllocationOrder &Order,
1355 BlockFrequency &BestCost,
1356 unsigned &NumCands,
1357 bool IgnoreCSR) {
1358 unsigned BestCand = NoCand;
1359 for (MCRegister PhysReg : Order) {
1360 assert(PhysReg);
1361 if (IgnoreCSR && EvictAdvisor->getUnusedCalleeSavedReg(VirtReg, PhysReg))
1362 continue;
1363
1364 calculateRegionSplitCostAroundReg(PhysReg, Order, BestCost, NumCands,
1365 BestCand);
1366 }
1367
1368 return BestCand;
1369}
1370
1371MCRegister RAGreedy::doRegionSplit(const LiveInterval &VirtReg,
1372 unsigned BestCand, bool HasCompact,
1373 SmallVectorImpl<Register> &NewVRegs) {
1374 SmallVector<unsigned, 8> UsedCands;
1375 // Prepare split editor.
1376 LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);
1377 SE->reset(LREdit, SplitSpillMode);
1378
1379 // Assign all edge bundles to the preferred candidate, or NoCand.
1380 BundleCand.assign(NumElts: Bundles->getNumBundles(), Elt: NoCand);
1381
1382 // Assign bundles for the best candidate region.
1383 if (BestCand != NoCand) {
1384 GlobalSplitCandidate &Cand = GlobalCand[BestCand];
1385 if (unsigned B = Cand.getBundles(B&: BundleCand, C: BestCand)) {
1386 UsedCands.push_back(Elt: BestCand);
1387 Cand.IntvIdx = SE->openIntv();
1388 LLVM_DEBUG(dbgs() << "Split for " << printReg(Cand.PhysReg, TRI) << " in "
1389 << B << " bundles, intv " << Cand.IntvIdx << ".\n");
1390 (void)B;
1391 }
1392 }
1393
1394 // Assign bundles for the compact region.
1395 if (HasCompact) {
1396 GlobalSplitCandidate &Cand = GlobalCand.front();
1397 assert(!Cand.PhysReg && "Compact region has no physreg");
1398 if (unsigned B = Cand.getBundles(B&: BundleCand, C: 0)) {
1399 UsedCands.push_back(Elt: 0);
1400 Cand.IntvIdx = SE->openIntv();
1401 LLVM_DEBUG(dbgs() << "Split for compact region in " << B
1402 << " bundles, intv " << Cand.IntvIdx << ".\n");
1403 (void)B;
1404 }
1405 }
1406
1407 splitAroundRegion(LREdit, UsedCands);
1408 return MCRegister();
1409}
1410
1411// VirtReg has a physical Hint, this function tries to split VirtReg around
1412// Hint if we can place new COPY instructions in cold blocks.
1413bool RAGreedy::trySplitAroundHintReg(MCRegister Hint,
1414 const LiveInterval &VirtReg,
1415 SmallVectorImpl<Register> &NewVRegs,
1416 AllocationOrder &Order) {
1417 // Split the VirtReg may generate COPY instructions in multiple cold basic
1418 // blocks, and increase code size. So we avoid it when the function is
1419 // optimized for size.
1420 if (MF->getFunction().hasOptSize())
1421 return false;
1422
1423 // Don't allow repeated splitting as a safe guard against looping.
1424 if (ExtraInfo->getStage(VirtReg) >= RS_Split2)
1425 return false;
1426
1427 BlockFrequency Cost = BlockFrequency(0);
1428 Register Reg = VirtReg.reg();
1429
1430 // Compute the cost of assigning a non Hint physical register to VirtReg.
1431 // We define it as the total frequency of broken COPY instructions to/from
1432 // Hint register, and after split, they can be deleted.
1433
1434 // FIXME: This is miscounting the costs with subregisters. In particular, this
1435 // should support recognizing SplitKit formed copy bundles instead of direct
1436 // copy instructions, which will appear in the same block.
1437 for (const MachineOperand &Opnd : MRI->reg_nodbg_operands(Reg)) {
1438 const MachineInstr &Instr = *Opnd.getParent();
1439 if (!Instr.isCopy() || Opnd.isImplicit())
1440 continue;
1441
1442 // Look for the other end of the copy.
1443 const bool IsDef = Opnd.isDef();
1444 const MachineOperand &OtherOpnd = Instr.getOperand(i: IsDef);
1445 Register OtherReg = OtherOpnd.getReg();
1446 assert(Reg == Opnd.getReg());
1447 if (OtherReg == Reg)
1448 continue;
1449
1450 unsigned SubReg = Opnd.getSubReg();
1451 unsigned OtherSubReg = OtherOpnd.getSubReg();
1452 if (SubReg && OtherSubReg && SubReg != OtherSubReg)
1453 continue;
1454
1455 // Check if VirtReg interferes with OtherReg after this COPY instruction.
1456 if (Opnd.readsReg()) {
1457 SlotIndex Index = LIS->getInstructionIndex(Instr).getRegSlot();
1458
1459 if (SubReg) {
1460 LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubIdx: SubReg);
1461 if (IsDef)
1462 Mask = ~Mask;
1463
1464 if (any_of(Range: VirtReg.subranges(), P: [=](const LiveInterval::SubRange &S) {
1465 return (S.LaneMask & Mask).any() && S.liveAt(index: Index);
1466 })) {
1467 continue;
1468 }
1469 } else {
1470 if (VirtReg.liveAt(index: Index))
1471 continue;
1472 }
1473 }
1474
1475 MCRegister OtherPhysReg =
1476 OtherReg.isPhysical() ? OtherReg.asMCReg() : VRM->getPhys(virtReg: OtherReg);
1477 MCRegister ThisHint = SubReg ? TRI->getSubReg(Reg: Hint, Idx: SubReg) : Hint;
1478 if (OtherPhysReg == ThisHint)
1479 Cost += MBFI->getBlockFreq(MBB: Instr.getParent());
1480 }
1481
1482 // Decrease the cost so it will be split in colder blocks.
1483 BranchProbability Threshold(SplitThresholdForRegWithHint, 100);
1484 Cost *= Threshold;
1485 if (Cost == BlockFrequency(0))
1486 return false;
1487
1488 unsigned NumCands = 0;
1489 unsigned BestCand = NoCand;
1490 SA->analyze(li: &VirtReg);
1491 calculateRegionSplitCostAroundReg(PhysReg: Hint, Order, BestCost&: Cost, NumCands, BestCand);
1492 if (BestCand == NoCand)
1493 return false;
1494
1495 doRegionSplit(VirtReg, BestCand, HasCompact: false/*HasCompact*/, NewVRegs);
1496 return true;
1497}
1498
1499//===----------------------------------------------------------------------===//
1500// Per-Block Splitting
1501//===----------------------------------------------------------------------===//
1502
1503/// tryBlockSplit - Split a global live range around every block with uses. This
1504/// creates a lot of local live ranges, that will be split by tryLocalSplit if
1505/// they don't allocate.
1506MCRegister RAGreedy::tryBlockSplit(const LiveInterval &VirtReg,
1507 AllocationOrder &Order,
1508 SmallVectorImpl<Register> &NewVRegs) {
1509 assert(&SA->getParent() == &VirtReg && "Live range wasn't analyzed");
1510 Register Reg = VirtReg.reg();
1511 bool SingleInstrs = RegClassInfo->isProperSubClass(RC: MRI->getRegClass(Reg));
1512 LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);
1513 SE->reset(LREdit, SplitSpillMode);
1514 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
1515 for (const SplitAnalysis::BlockInfo &BI : UseBlocks) {
1516 if (SA->shouldSplitSingleBlock(BI, SingleInstrs))
1517 SE->splitSingleBlock(BI);
1518 }
1519 // No blocks were split.
1520 if (LREdit.empty())
1521 return MCRegister();
1522
1523 // We did split for some blocks.
1524 SmallVector<unsigned, 8> IntvMap;
1525 SE->finish(LRMap: &IntvMap);
1526
1527 // Tell LiveDebugVariables about the new ranges.
1528 DebugVars->splitRegister(OldReg: Reg, NewRegs: LREdit.regs(), LIS&: *LIS);
1529
1530 // Sort out the new intervals created by splitting. The remainder interval
1531 // goes straight to spilling, the new local ranges get to stay RS_New.
1532 for (unsigned I = 0, E = LREdit.size(); I != E; ++I) {
1533 const LiveInterval &LI = LIS->getInterval(Reg: LREdit.get(idx: I));
1534 if (ExtraInfo->getOrInitStage(Reg: LI.reg()) == RS_New && IntvMap[I] == 0)
1535 ExtraInfo->setStage(VirtReg: LI, Stage: RS_Spill);
1536 }
1537
1538 if (VerifyEnabled)
1539 MF->verify(LiveInts: LIS, Indexes, Banner: "After splitting live range around basic blocks",
1540 OS: &errs());
1541 return MCRegister();
1542}
1543
1544//===----------------------------------------------------------------------===//
1545// Per-Instruction Splitting
1546//===----------------------------------------------------------------------===//
1547
1548/// Get the number of allocatable registers that match the constraints of \p Reg
1549/// on \p MI and that are also in \p SuperRC.
1550static unsigned getNumAllocatableRegsForConstraints(
1551 const MachineInstr *MI, Register Reg, const TargetRegisterClass *SuperRC,
1552 const TargetInstrInfo *TII, const TargetRegisterInfo *TRI,
1553 const RegisterClassInfo &RCI) {
1554 assert(SuperRC && "Invalid register class");
1555
1556 const TargetRegisterClass *ConstrainedRC =
1557 MI->getRegClassConstraintEffectForVReg(Reg, CurRC: SuperRC, TII, TRI,
1558 /* ExploreBundle */ true);
1559 if (!ConstrainedRC)
1560 return 0;
1561 return RCI.getNumAllocatableRegs(RC: ConstrainedRC);
1562}
1563
1564static LaneBitmask getInstReadLaneMask(const MachineRegisterInfo &MRI,
1565 const TargetRegisterInfo &TRI,
1566 const MachineInstr &FirstMI,
1567 Register Reg) {
1568 LaneBitmask Mask;
1569 SmallVector<std::pair<MachineInstr *, unsigned>, 8> Ops;
1570 (void)AnalyzeVirtRegInBundle(MI&: const_cast<MachineInstr &>(FirstMI), Reg, Ops: &Ops);
1571
1572 for (auto [MI, OpIdx] : Ops) {
1573 const MachineOperand &MO = MI->getOperand(i: OpIdx);
1574 assert(MO.isReg() && MO.getReg() == Reg);
1575 unsigned SubReg = MO.getSubReg();
1576 if (SubReg == 0 && MO.isUse()) {
1577 if (MO.isUndef())
1578 continue;
1579 return MRI.getMaxLaneMaskForVReg(Reg);
1580 }
1581
1582 LaneBitmask SubRegMask = TRI.getSubRegIndexLaneMask(SubIdx: SubReg);
1583 if (MO.isDef()) {
1584 if (!MO.isUndef())
1585 Mask |= ~SubRegMask;
1586 } else
1587 Mask |= SubRegMask;
1588 }
1589
1590 return Mask;
1591}
1592
1593/// Return true if \p MI at \P Use reads a subset of the lanes live in \p
1594/// VirtReg.
1595static bool readsLaneSubset(const MachineRegisterInfo &MRI,
1596 const MachineInstr *MI, const LiveInterval &VirtReg,
1597 const TargetRegisterInfo *TRI, SlotIndex Use,
1598 const TargetInstrInfo *TII) {
1599 // Early check the common case. Beware of the semi-formed bundles SplitKit
1600 // creates by setting the bundle flag on copies without a matching BUNDLE.
1601
1602 auto DestSrc = TII->isCopyInstr(MI: *MI);
1603 if (DestSrc && !MI->isBundled() &&
1604 DestSrc->Destination->getSubReg() == DestSrc->Source->getSubReg())
1605 return false;
1606
1607 // FIXME: We're only considering uses, but should be consider defs too?
1608 LaneBitmask ReadMask = getInstReadLaneMask(MRI, TRI: *TRI, FirstMI: *MI, Reg: VirtReg.reg());
1609
1610 LaneBitmask LiveAtMask;
1611 for (const LiveInterval::SubRange &S : VirtReg.subranges()) {
1612 if (S.liveAt(index: Use))
1613 LiveAtMask |= S.LaneMask;
1614 }
1615
1616 // If the live lanes aren't different from the lanes used by the instruction,
1617 // this doesn't help.
1618 return (ReadMask & ~(LiveAtMask & TRI->getCoveringLanes())).any();
1619}
1620
1621/// tryInstructionSplit - Split a live range around individual instructions.
1622/// This is normally not worthwhile since the spiller is doing essentially the
1623/// same thing. However, when the live range is in a constrained register
1624/// class, it may help to insert copies such that parts of the live range can
1625/// be moved to a larger register class.
1626///
1627/// This is similar to spilling to a larger register class.
1628MCRegister RAGreedy::tryInstructionSplit(const LiveInterval &VirtReg,
1629 AllocationOrder &Order,
1630 SmallVectorImpl<Register> &NewVRegs) {
1631 const TargetRegisterClass *CurRC = MRI->getRegClass(Reg: VirtReg.reg());
1632 // There is no point to this if there are no larger sub-classes.
1633
1634 bool SplitSubClass = true;
1635 if (!RegClassInfo->isProperSubClass(RC: CurRC)) {
1636 if (!VirtReg.hasSubRanges())
1637 return MCRegister();
1638 SplitSubClass = false;
1639 }
1640
1641 // Always enable split spill mode, since we're effectively spilling to a
1642 // register.
1643 LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);
1644 SE->reset(LREdit, SplitEditor::SM_Size);
1645
1646 ArrayRef<SlotIndex> Uses = SA->getUseSlots();
1647 if (Uses.size() <= 1)
1648 return MCRegister();
1649
1650 LLVM_DEBUG(dbgs() << "Split around " << Uses.size()
1651 << " individual instrs.\n");
1652
1653 const TargetRegisterClass *SuperRC =
1654 TRI->getLargestLegalSuperClass(RC: CurRC, *MF);
1655 unsigned SuperRCNumAllocatableRegs =
1656 RegClassInfo->getNumAllocatableRegs(RC: SuperRC);
1657 // Split around every non-copy instruction if this split will relax
1658 // the constraints on the virtual register.
1659 // Otherwise, splitting just inserts uncoalescable copies that do not help
1660 // the allocation.
1661 for (const SlotIndex Use : Uses) {
1662 if (const MachineInstr *MI = Indexes->getInstructionFromIndex(index: Use)) {
1663 if (TII->isFullCopyInstr(MI: *MI) ||
1664 (SplitSubClass &&
1665 SuperRCNumAllocatableRegs ==
1666 getNumAllocatableRegsForConstraints(MI, Reg: VirtReg.reg(), SuperRC,
1667 TII, TRI, RCI: *RegClassInfo)) ||
1668 // TODO: Handle split for subranges with subclass constraints?
1669 (!SplitSubClass && VirtReg.hasSubRanges() &&
1670 !readsLaneSubset(MRI: *MRI, MI, VirtReg, TRI, Use, TII))) {
1671 LLVM_DEBUG(dbgs() << " skip:\t" << Use << '\t' << *MI);
1672 continue;
1673 }
1674 }
1675 SE->openIntv();
1676 SlotIndex SegStart = SE->enterIntvBefore(Idx: Use);
1677 SlotIndex SegStop = SE->leaveIntvAfter(Idx: Use);
1678 SE->useIntv(Start: SegStart, End: SegStop);
1679 }
1680
1681 if (LREdit.empty()) {
1682 LLVM_DEBUG(dbgs() << "All uses were copies.\n");
1683 return MCRegister();
1684 }
1685
1686 SmallVector<unsigned, 8> IntvMap;
1687 SE->finish(LRMap: &IntvMap);
1688 DebugVars->splitRegister(OldReg: VirtReg.reg(), NewRegs: LREdit.regs(), LIS&: *LIS);
1689 // Assign all new registers to RS_Spill. This was the last chance.
1690 ExtraInfo->setStage(Begin: LREdit.begin(), End: LREdit.end(), NewStage: RS_Spill);
1691 return MCRegister();
1692}
1693
1694//===----------------------------------------------------------------------===//
1695// Local Splitting
1696//===----------------------------------------------------------------------===//
1697
1698/// calcGapWeights - Compute the maximum spill weight that needs to be evicted
1699/// in order to use PhysReg between two entries in SA->UseSlots.
1700///
1701/// GapWeight[I] represents the gap between UseSlots[I] and UseSlots[I + 1].
1702///
1703void RAGreedy::calcGapWeights(MCRegister PhysReg,
1704 SmallVectorImpl<float> &GapWeight) {
1705 assert(SA->getUseBlocks().size() == 1 && "Not a local interval");
1706 const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front();
1707 ArrayRef<SlotIndex> Uses = SA->getUseSlots();
1708 const unsigned NumGaps = Uses.size()-1;
1709
1710 // Start and end points for the interference check.
1711 SlotIndex StartIdx =
1712 BI.LiveIn ? BI.FirstInstr.getBaseIndex() : BI.FirstInstr;
1713 SlotIndex StopIdx =
1714 BI.LiveOut ? BI.LastInstr.getBoundaryIndex() : BI.LastInstr;
1715
1716 GapWeight.assign(NumElts: NumGaps, Elt: 0.0f);
1717
1718 // Add interference from each overlapping register.
1719 for (MCRegUnit Unit : TRI->regunits(Reg: PhysReg)) {
1720 if (!Matrix->query(LR: const_cast<LiveInterval &>(SA->getParent()), RegUnit: Unit)
1721 .checkInterference())
1722 continue;
1723
1724 // We know that VirtReg is a continuous interval from FirstInstr to
1725 // LastInstr, so we don't need InterferenceQuery.
1726 //
1727 // Interference that overlaps an instruction is counted in both gaps
1728 // surrounding the instruction. The exception is interference before
1729 // StartIdx and after StopIdx.
1730 //
1731 LiveIntervalUnion::SegmentIter IntI =
1732 Matrix->getLiveUnions()[static_cast<unsigned>(Unit)].find(x: StartIdx);
1733 for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) {
1734 // Skip the gaps before IntI.
1735 while (Uses[Gap+1].getBoundaryIndex() < IntI.start())
1736 if (++Gap == NumGaps)
1737 break;
1738 if (Gap == NumGaps)
1739 break;
1740
1741 // Update the gaps covered by IntI.
1742 const float weight = IntI.value()->weight();
1743 for (; Gap != NumGaps; ++Gap) {
1744 GapWeight[Gap] = std::max(a: GapWeight[Gap], b: weight);
1745 if (Uses[Gap+1].getBaseIndex() >= IntI.stop())
1746 break;
1747 }
1748 if (Gap == NumGaps)
1749 break;
1750 }
1751 }
1752
1753 // Add fixed interference.
1754 for (MCRegUnit Unit : TRI->regunits(Reg: PhysReg)) {
1755 const LiveRange &LR = LIS->getRegUnit(Unit);
1756 LiveRange::const_iterator I = LR.find(Pos: StartIdx);
1757 LiveRange::const_iterator E = LR.end();
1758
1759 // Same loop as above. Mark any overlapped gaps as HUGE_VALF.
1760 for (unsigned Gap = 0; I != E && I->start < StopIdx; ++I) {
1761 while (Uses[Gap+1].getBoundaryIndex() < I->start)
1762 if (++Gap == NumGaps)
1763 break;
1764 if (Gap == NumGaps)
1765 break;
1766
1767 for (; Gap != NumGaps; ++Gap) {
1768 GapWeight[Gap] = huge_valf;
1769 if (Uses[Gap+1].getBaseIndex() >= I->end)
1770 break;
1771 }
1772 if (Gap == NumGaps)
1773 break;
1774 }
1775 }
1776}
1777
1778/// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only
1779/// basic block.
1780///
1781MCRegister RAGreedy::tryLocalSplit(const LiveInterval &VirtReg,
1782 AllocationOrder &Order,
1783 SmallVectorImpl<Register> &NewVRegs) {
1784 // TODO: the function currently only handles a single UseBlock; it should be
1785 // possible to generalize.
1786 if (SA->getUseBlocks().size() != 1)
1787 return MCRegister();
1788
1789 const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front();
1790
1791 // Note that it is possible to have an interval that is live-in or live-out
1792 // while only covering a single block - A phi-def can use undef values from
1793 // predecessors, and the block could be a single-block loop.
1794 // We don't bother doing anything clever about such a case, we simply assume
1795 // that the interval is continuous from FirstInstr to LastInstr. We should
1796 // make sure that we don't do anything illegal to such an interval, though.
1797
1798 ArrayRef<SlotIndex> Uses = SA->getUseSlots();
1799 if (Uses.size() <= 2)
1800 return MCRegister();
1801 const unsigned NumGaps = Uses.size()-1;
1802
1803 LLVM_DEBUG({
1804 dbgs() << "tryLocalSplit: ";
1805 for (const auto &Use : Uses)
1806 dbgs() << ' ' << Use;
1807 dbgs() << '\n';
1808 });
1809
1810 // If VirtReg is live across any register mask operands, compute a list of
1811 // gaps with register masks.
1812 SmallVector<unsigned, 8> RegMaskGaps;
1813 if (Matrix->checkRegMaskInterference(VirtReg)) {
1814 // Get regmask slots for the whole block.
1815 ArrayRef<SlotIndex> RMS = LIS->getRegMaskSlotsInBlock(MBBNum: BI.MBB->getNumber());
1816 LLVM_DEBUG(dbgs() << RMS.size() << " regmasks in block:");
1817 // Constrain to VirtReg's live range.
1818 unsigned RI =
1819 llvm::lower_bound(Range&: RMS, Value: Uses.front().getRegSlot()) - RMS.begin();
1820 unsigned RE = RMS.size();
1821 for (unsigned I = 0; I != NumGaps && RI != RE; ++I) {
1822 // Look for Uses[I] <= RMS <= Uses[I + 1].
1823 assert(!SlotIndex::isEarlierInstr(RMS[RI], Uses[I]));
1824 if (SlotIndex::isEarlierInstr(A: Uses[I + 1], B: RMS[RI]))
1825 continue;
1826 // Skip a regmask on the same instruction as the last use. It doesn't
1827 // overlap the live range.
1828 if (SlotIndex::isSameInstr(A: Uses[I + 1], B: RMS[RI]) && I + 1 == NumGaps)
1829 break;
1830 LLVM_DEBUG(dbgs() << ' ' << RMS[RI] << ':' << Uses[I] << '-'
1831 << Uses[I + 1]);
1832 RegMaskGaps.push_back(Elt: I);
1833 // Advance ri to the next gap. A regmask on one of the uses counts in
1834 // both gaps.
1835 while (RI != RE && SlotIndex::isEarlierInstr(A: RMS[RI], B: Uses[I + 1]))
1836 ++RI;
1837 }
1838 LLVM_DEBUG(dbgs() << '\n');
1839 }
1840
1841 // Since we allow local split results to be split again, there is a risk of
1842 // creating infinite loops. It is tempting to require that the new live
1843 // ranges have less instructions than the original. That would guarantee
1844 // convergence, but it is too strict. A live range with 3 instructions can be
1845 // split 2+3 (including the COPY), and we want to allow that.
1846 //
1847 // Instead we use these rules:
1848 //
1849 // 1. Allow any split for ranges with getStage() < RS_Split2. (Except for the
1850 // noop split, of course).
1851 // 2. Require progress be made for ranges with getStage() == RS_Split2. All
1852 // the new ranges must have fewer instructions than before the split.
1853 // 3. New ranges with the same number of instructions are marked RS_Split2,
1854 // smaller ranges are marked RS_New.
1855 //
1856 // These rules allow a 3 -> 2+3 split once, which we need. They also prevent
1857 // excessive splitting and infinite loops.
1858 //
1859 bool ProgressRequired = ExtraInfo->getStage(VirtReg) >= RS_Split2;
1860
1861 // Best split candidate.
1862 unsigned BestBefore = NumGaps;
1863 unsigned BestAfter = 0;
1864 float BestDiff = 0;
1865
1866 const float blockFreq =
1867 SpillPlacer->getBlockFrequency(Number: BI.MBB->getNumber()).getFrequency() *
1868 (1.0f / MBFI->getEntryFreq().getFrequency());
1869 SmallVector<float, 8> GapWeight;
1870
1871 for (MCRegister PhysReg : Order) {
1872 assert(PhysReg);
1873 // Keep track of the largest spill weight that would need to be evicted in
1874 // order to make use of PhysReg between UseSlots[I] and UseSlots[I + 1].
1875 calcGapWeights(PhysReg, GapWeight);
1876
1877 // Remove any gaps with regmask clobbers.
1878 if (Matrix->checkRegMaskInterference(VirtReg, PhysReg))
1879 for (unsigned Gap : RegMaskGaps)
1880 GapWeight[Gap] = huge_valf;
1881
1882 // Try to find the best sequence of gaps to close.
1883 // The new spill weight must be larger than any gap interference.
1884
1885 // We will split before Uses[SplitBefore] and after Uses[SplitAfter].
1886 unsigned SplitBefore = 0, SplitAfter = 1;
1887
1888 // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]).
1889 // It is the spill weight that needs to be evicted.
1890 float MaxGap = GapWeight[0];
1891
1892 while (true) {
1893 // Live before/after split?
1894 const bool LiveBefore = SplitBefore != 0 || BI.LiveIn;
1895 const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut;
1896
1897 LLVM_DEBUG(dbgs() << printReg(PhysReg, TRI) << ' ' << Uses[SplitBefore]
1898 << '-' << Uses[SplitAfter] << " I=" << MaxGap);
1899
1900 // Stop before the interval gets so big we wouldn't be making progress.
1901 if (!LiveBefore && !LiveAfter) {
1902 LLVM_DEBUG(dbgs() << " all\n");
1903 break;
1904 }
1905 // Should the interval be extended or shrunk?
1906 bool Shrink = true;
1907
1908 // How many gaps would the new range have?
1909 unsigned NewGaps = LiveBefore + SplitAfter - SplitBefore + LiveAfter;
1910
1911 // Legally, without causing looping?
1912 bool Legal = !ProgressRequired || NewGaps < NumGaps;
1913
1914 if (Legal && MaxGap < huge_valf) {
1915 // Estimate the new spill weight. Each instruction reads or writes the
1916 // register. Conservatively assume there are no read-modify-write
1917 // instructions.
1918 //
1919 // Try to guess the size of the new interval.
1920 const float EstWeight = normalizeSpillWeight(
1921 UseDefFreq: blockFreq * (NewGaps + 1),
1922 Size: Uses[SplitBefore].distance(other: Uses[SplitAfter]) +
1923 (LiveBefore + LiveAfter) * SlotIndex::InstrDist,
1924 NumInstr: 1);
1925 // Would this split be possible to allocate?
1926 // Never allocate all gaps, we wouldn't be making progress.
1927 LLVM_DEBUG(dbgs() << " w=" << EstWeight);
1928 if (EstWeight * Hysteresis >= MaxGap) {
1929 Shrink = false;
1930 float Diff = EstWeight - MaxGap;
1931 if (Diff > BestDiff) {
1932 LLVM_DEBUG(dbgs() << " (best)");
1933 BestDiff = Hysteresis * Diff;
1934 BestBefore = SplitBefore;
1935 BestAfter = SplitAfter;
1936 }
1937 }
1938 }
1939
1940 // Try to shrink.
1941 if (Shrink) {
1942 if (++SplitBefore < SplitAfter) {
1943 LLVM_DEBUG(dbgs() << " shrink\n");
1944 // Recompute the max when necessary.
1945 if (GapWeight[SplitBefore - 1] >= MaxGap) {
1946 MaxGap = GapWeight[SplitBefore];
1947 for (unsigned I = SplitBefore + 1; I != SplitAfter; ++I)
1948 MaxGap = std::max(a: MaxGap, b: GapWeight[I]);
1949 }
1950 continue;
1951 }
1952 MaxGap = 0;
1953 }
1954
1955 // Try to extend the interval.
1956 if (SplitAfter >= NumGaps) {
1957 LLVM_DEBUG(dbgs() << " end\n");
1958 break;
1959 }
1960
1961 LLVM_DEBUG(dbgs() << " extend\n");
1962 MaxGap = std::max(a: MaxGap, b: GapWeight[SplitAfter++]);
1963 }
1964 }
1965
1966 // Didn't find any candidates?
1967 if (BestBefore == NumGaps)
1968 return MCRegister();
1969
1970 LLVM_DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore] << '-'
1971 << Uses[BestAfter] << ", " << BestDiff << ", "
1972 << (BestAfter - BestBefore + 1) << " instrs\n");
1973
1974 LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);
1975 SE->reset(LREdit);
1976
1977 SE->openIntv();
1978 SlotIndex SegStart = SE->enterIntvBefore(Idx: Uses[BestBefore]);
1979 SlotIndex SegStop = SE->leaveIntvAfter(Idx: Uses[BestAfter]);
1980 SE->useIntv(Start: SegStart, End: SegStop);
1981 SmallVector<unsigned, 8> IntvMap;
1982 SE->finish(LRMap: &IntvMap);
1983 DebugVars->splitRegister(OldReg: VirtReg.reg(), NewRegs: LREdit.regs(), LIS&: *LIS);
1984 // If the new range has the same number of instructions as before, mark it as
1985 // RS_Split2 so the next split will be forced to make progress. Otherwise,
1986 // leave the new intervals as RS_New so they can compete.
1987 bool LiveBefore = BestBefore != 0 || BI.LiveIn;
1988 bool LiveAfter = BestAfter != NumGaps || BI.LiveOut;
1989 unsigned NewGaps = LiveBefore + BestAfter - BestBefore + LiveAfter;
1990 if (NewGaps >= NumGaps) {
1991 LLVM_DEBUG(dbgs() << "Tagging non-progress ranges:");
1992 assert(!ProgressRequired && "Didn't make progress when it was required.");
1993 for (unsigned I = 0, E = IntvMap.size(); I != E; ++I)
1994 if (IntvMap[I] == 1) {
1995 ExtraInfo->setStage(VirtReg: LIS->getInterval(Reg: LREdit.get(idx: I)), Stage: RS_Split2);
1996 LLVM_DEBUG(dbgs() << ' ' << printReg(LREdit.get(I)));
1997 }
1998 LLVM_DEBUG(dbgs() << '\n');
1999 }
2000 ++NumLocalSplits;
2001
2002 return MCRegister();
2003}
2004
2005//===----------------------------------------------------------------------===//
2006// Live Range Splitting
2007//===----------------------------------------------------------------------===//
2008
2009/// trySplit - Try to split VirtReg or one of its interferences, making it
2010/// assignable.
2011/// @return Physreg when VirtReg may be assigned and/or new NewVRegs.
2012MCRegister RAGreedy::trySplit(const LiveInterval &VirtReg,
2013 AllocationOrder &Order,
2014 SmallVectorImpl<Register> &NewVRegs,
2015 const SmallVirtRegSet &FixedRegisters) {
2016 // Ranges must be Split2 or less.
2017 if (ExtraInfo->getStage(VirtReg) >= RS_Spill)
2018 return MCRegister();
2019
2020 // Local intervals are handled separately.
2021 if (LIS->intervalIsInOneMBB(LI: VirtReg)) {
2022 NamedRegionTimer T("local_split", "Local Splitting", TimerGroupName,
2023 TimerGroupDescription, TimePassesIsEnabled);
2024 SA->analyze(li: &VirtReg);
2025 MCRegister PhysReg = tryLocalSplit(VirtReg, Order, NewVRegs);
2026 if (PhysReg || !NewVRegs.empty())
2027 return PhysReg;
2028 return tryInstructionSplit(VirtReg, Order, NewVRegs);
2029 }
2030
2031 NamedRegionTimer T("global_split", "Global Splitting", TimerGroupName,
2032 TimerGroupDescription, TimePassesIsEnabled);
2033
2034 SA->analyze(li: &VirtReg);
2035
2036 // First try to split around a region spanning multiple blocks. RS_Split2
2037 // ranges already made dubious progress with region splitting, so they go
2038 // straight to single block splitting.
2039 if (ExtraInfo->getStage(VirtReg) < RS_Split2) {
2040 MCRegister PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs);
2041 if (PhysReg || !NewVRegs.empty())
2042 return PhysReg;
2043 }
2044
2045 // Then isolate blocks.
2046 return tryBlockSplit(VirtReg, Order, NewVRegs);
2047}
2048
2049//===----------------------------------------------------------------------===//
2050// Last Chance Recoloring
2051//===----------------------------------------------------------------------===//
2052
2053/// Return true if \p reg has any tied def operand.
2054static bool hasTiedDef(MachineRegisterInfo *MRI, Register reg) {
2055 for (const MachineOperand &MO : MRI->def_operands(Reg: reg))
2056 if (MO.isTied())
2057 return true;
2058
2059 return false;
2060}
2061
2062/// Return true if the existing assignment of \p Intf overlaps, but is not the
2063/// same, as \p PhysReg.
2064static bool assignedRegPartiallyOverlaps(const TargetRegisterInfo &TRI,
2065 const VirtRegMap &VRM,
2066 MCRegister PhysReg,
2067 const LiveInterval &Intf) {
2068 MCRegister AssignedReg = VRM.getPhys(virtReg: Intf.reg());
2069 if (PhysReg == AssignedReg)
2070 return false;
2071 return TRI.regsOverlap(RegA: PhysReg, RegB: AssignedReg);
2072}
2073
2074/// mayRecolorAllInterferences - Check if the virtual registers that
2075/// interfere with \p VirtReg on \p PhysReg (or one of its aliases) may be
2076/// recolored to free \p PhysReg.
2077/// When true is returned, \p RecoloringCandidates has been augmented with all
2078/// the live intervals that need to be recolored in order to free \p PhysReg
2079/// for \p VirtReg.
2080/// \p FixedRegisters contains all the virtual registers that cannot be
2081/// recolored.
2082bool RAGreedy::mayRecolorAllInterferences(
2083 MCRegister PhysReg, const LiveInterval &VirtReg,
2084 SmallLISet &RecoloringCandidates, const SmallVirtRegSet &FixedRegisters) {
2085 const TargetRegisterClass *CurRC = MRI->getRegClass(Reg: VirtReg.reg());
2086
2087 for (MCRegUnit Unit : TRI->regunits(Reg: PhysReg)) {
2088 LiveIntervalUnion::Query &Q = Matrix->query(LR: VirtReg, RegUnit: Unit);
2089 // If there is LastChanceRecoloringMaxInterference or more interferences,
2090 // chances are one would not be recolorable.
2091 if (Q.interferingVRegs(MaxInterferingRegs: LastChanceRecoloringMaxInterference).size() >=
2092 LastChanceRecoloringMaxInterference &&
2093 !ExhaustiveSearch) {
2094 LLVM_DEBUG(dbgs() << "Early abort: too many interferences.\n");
2095 CutOffInfo |= CO_Interf;
2096 return false;
2097 }
2098 for (const LiveInterval *Intf : reverse(C: Q.interferingVRegs())) {
2099 // If Intf is done and sits on the same register class as VirtReg, it
2100 // would not be recolorable as it is in the same state as
2101 // VirtReg. However there are at least two exceptions.
2102 //
2103 // If VirtReg has tied defs and Intf doesn't, then
2104 // there is still a point in examining if it can be recolorable.
2105 //
2106 // Additionally, if the register class has overlapping tuple members, it
2107 // may still be recolorable using a different tuple. This is more likely
2108 // if the existing assignment aliases with the candidate.
2109 //
2110 if (((ExtraInfo->getStage(VirtReg: *Intf) == RS_Done &&
2111 MRI->getRegClass(Reg: Intf->reg()) == CurRC &&
2112 !assignedRegPartiallyOverlaps(TRI: *TRI, VRM: *VRM, PhysReg, Intf: *Intf)) &&
2113 !(hasTiedDef(MRI, reg: VirtReg.reg()) &&
2114 !hasTiedDef(MRI, reg: Intf->reg()))) ||
2115 FixedRegisters.count(V: Intf->reg())) {
2116 LLVM_DEBUG(
2117 dbgs() << "Early abort: the interference is not recolorable.\n");
2118 return false;
2119 }
2120 RecoloringCandidates.insert(X: Intf);
2121 }
2122 }
2123 return true;
2124}
2125
2126/// tryLastChanceRecoloring - Try to assign a color to \p VirtReg by recoloring
2127/// its interferences.
2128/// Last chance recoloring chooses a color for \p VirtReg and recolors every
2129/// virtual register that was using it. The recoloring process may recursively
2130/// use the last chance recoloring. Therefore, when a virtual register has been
2131/// assigned a color by this mechanism, it is marked as Fixed, i.e., it cannot
2132/// be last-chance-recolored again during this recoloring "session".
2133/// E.g.,
2134/// Let
2135/// vA can use {R1, R2 }
2136/// vB can use { R2, R3}
2137/// vC can use {R1 }
2138/// Where vA, vB, and vC cannot be split anymore (they are reloads for
2139/// instance) and they all interfere.
2140///
2141/// vA is assigned R1
2142/// vB is assigned R2
2143/// vC tries to evict vA but vA is already done.
2144/// Regular register allocation fails.
2145///
2146/// Last chance recoloring kicks in:
2147/// vC does as if vA was evicted => vC uses R1.
2148/// vC is marked as fixed.
2149/// vA needs to find a color.
2150/// None are available.
2151/// vA cannot evict vC: vC is a fixed virtual register now.
2152/// vA does as if vB was evicted => vA uses R2.
2153/// vB needs to find a color.
2154/// R3 is available.
2155/// Recoloring => vC = R1, vA = R2, vB = R3
2156///
2157/// \p Order defines the preferred allocation order for \p VirtReg.
2158/// \p NewRegs will contain any new virtual register that have been created
2159/// (split, spill) during the process and that must be assigned.
2160/// \p FixedRegisters contains all the virtual registers that cannot be
2161/// recolored.
2162///
2163/// \p RecolorStack tracks the original assignments of successfully recolored
2164/// registers.
2165///
2166/// \p Depth gives the current depth of the last chance recoloring.
2167/// \return a physical register that can be used for VirtReg or ~0u if none
2168/// exists.
2169MCRegister RAGreedy::tryLastChanceRecoloring(
2170 const LiveInterval &VirtReg, AllocationOrder &Order,
2171 SmallVectorImpl<Register> &NewVRegs, SmallVirtRegSet &FixedRegisters,
2172 RecoloringStack &RecolorStack, unsigned Depth) {
2173 if (!TRI->shouldUseLastChanceRecoloringForVirtReg(MF: *MF, VirtReg))
2174 return ~0u;
2175
2176 LLVM_DEBUG(dbgs() << "Try last chance recoloring for " << VirtReg << '\n');
2177
2178 const ssize_t EntryStackSize = RecolorStack.size();
2179
2180 // Ranges must be Done.
2181 assert((ExtraInfo->getStage(VirtReg) >= RS_Done || !VirtReg.isSpillable()) &&
2182 "Last chance recoloring should really be last chance");
2183 // Set the max depth to LastChanceRecoloringMaxDepth.
2184 // We may want to reconsider that if we end up with a too large search space
2185 // for target with hundreds of registers.
2186 // Indeed, in that case we may want to cut the search space earlier.
2187 if (Depth >= LastChanceRecoloringMaxDepth && !ExhaustiveSearch) {
2188 LLVM_DEBUG(dbgs() << "Abort because max depth has been reached.\n");
2189 CutOffInfo |= CO_Depth;
2190 return ~0u;
2191 }
2192
2193 // Set of Live intervals that will need to be recolored.
2194 SmallLISet RecoloringCandidates;
2195
2196 // Mark VirtReg as fixed, i.e., it will not be recolored pass this point in
2197 // this recoloring "session".
2198 assert(!FixedRegisters.count(VirtReg.reg()));
2199 FixedRegisters.insert(V: VirtReg.reg());
2200 SmallVector<Register, 4> CurrentNewVRegs;
2201
2202 for (MCRegister PhysReg : Order) {
2203 assert(PhysReg.isValid());
2204 LLVM_DEBUG(dbgs() << "Try to assign: " << VirtReg << " to "
2205 << printReg(PhysReg, TRI) << '\n');
2206 RecoloringCandidates.clear();
2207 CurrentNewVRegs.clear();
2208
2209 // It is only possible to recolor virtual register interference.
2210 if (Matrix->checkInterference(VirtReg, PhysReg) >
2211 LiveRegMatrix::IK_VirtReg) {
2212 LLVM_DEBUG(
2213 dbgs() << "Some interferences are not with virtual registers.\n");
2214
2215 continue;
2216 }
2217
2218 // Early give up on this PhysReg if it is obvious we cannot recolor all
2219 // the interferences.
2220 if (!mayRecolorAllInterferences(PhysReg, VirtReg, RecoloringCandidates,
2221 FixedRegisters)) {
2222 LLVM_DEBUG(dbgs() << "Some interferences cannot be recolored.\n");
2223 continue;
2224 }
2225
2226 // RecoloringCandidates contains all the virtual registers that interfere
2227 // with VirtReg on PhysReg (or one of its aliases). Enqueue them for
2228 // recoloring and perform the actual recoloring.
2229 PQueue RecoloringQueue;
2230 for (const LiveInterval *RC : RecoloringCandidates) {
2231 Register ItVirtReg = RC->reg();
2232 enqueue(CurQueue&: RecoloringQueue, LI: RC);
2233 assert(VRM->hasPhys(ItVirtReg) &&
2234 "Interferences are supposed to be with allocated variables");
2235
2236 // Record the current allocation.
2237 RecolorStack.push_back(Elt: std::make_pair(x&: RC, y: VRM->getPhys(virtReg: ItVirtReg)));
2238
2239 // unset the related struct.
2240 Matrix->unassign(VirtReg: *RC);
2241 }
2242
2243 // Do as if VirtReg was assigned to PhysReg so that the underlying
2244 // recoloring has the right information about the interferes and
2245 // available colors.
2246 Matrix->assign(VirtReg, PhysReg);
2247
2248 // VirtReg may be deleted during tryRecoloringCandidates, save a copy.
2249 Register ThisVirtReg = VirtReg.reg();
2250
2251 // Save the current recoloring state.
2252 // If we cannot recolor all the interferences, we will have to start again
2253 // at this point for the next physical register.
2254 SmallVirtRegSet SaveFixedRegisters(FixedRegisters);
2255 if (tryRecoloringCandidates(RecoloringQueue, CurrentNewVRegs,
2256 FixedRegisters, RecolorStack, Depth)) {
2257 // Push the queued vregs into the main queue.
2258 llvm::append_range(C&: NewVRegs, R&: CurrentNewVRegs);
2259 // Do not mess up with the global assignment process.
2260 // I.e., VirtReg must be unassigned.
2261 if (VRM->hasPhys(virtReg: ThisVirtReg)) {
2262 Matrix->unassign(VirtReg);
2263 return PhysReg;
2264 }
2265
2266 // It is possible VirtReg will be deleted during tryRecoloringCandidates.
2267 LLVM_DEBUG(dbgs() << "tryRecoloringCandidates deleted a fixed register "
2268 << printReg(ThisVirtReg) << '\n');
2269 FixedRegisters.erase(V: ThisVirtReg);
2270 return MCRegister();
2271 }
2272
2273 LLVM_DEBUG(dbgs() << "Fail to assign: " << VirtReg << " to "
2274 << printReg(PhysReg, TRI) << '\n');
2275
2276 // The recoloring attempt failed, undo the changes.
2277 FixedRegisters = SaveFixedRegisters;
2278 Matrix->unassign(VirtReg);
2279
2280 // For a newly created vreg which is also in RecoloringCandidates,
2281 // don't add it to NewVRegs because its physical register will be restored
2282 // below. Other vregs in CurrentNewVRegs are created by calling
2283 // selectOrSplit and should be added into NewVRegs.
2284 for (Register R : CurrentNewVRegs) {
2285 if (RecoloringCandidates.count(key: &LIS->getInterval(Reg: R)))
2286 continue;
2287 NewVRegs.push_back(Elt: R);
2288 }
2289
2290 // Roll back our unsuccessful recoloring. Also roll back any successful
2291 // recolorings in any recursive recoloring attempts, since it's possible
2292 // they would have introduced conflicts with assignments we will be
2293 // restoring further up the stack. Perform all unassignments prior to
2294 // reassigning, since sub-recolorings may have conflicted with the registers
2295 // we are going to restore to their original assignments.
2296 for (ssize_t I = RecolorStack.size() - 1; I >= EntryStackSize; --I) {
2297 const LiveInterval *LI;
2298 MCRegister PhysReg;
2299 std::tie(args&: LI, args&: PhysReg) = RecolorStack[I];
2300
2301 if (VRM->hasPhys(virtReg: LI->reg()))
2302 Matrix->unassign(VirtReg: *LI);
2303 }
2304
2305 for (size_t I = EntryStackSize; I != RecolorStack.size(); ++I) {
2306 const LiveInterval *LI;
2307 MCRegister PhysReg;
2308 std::tie(args&: LI, args&: PhysReg) = RecolorStack[I];
2309 if (!LI->empty() && !MRI->reg_nodbg_empty(RegNo: LI->reg()))
2310 Matrix->assign(VirtReg: *LI, PhysReg);
2311 }
2312
2313 // Pop the stack of recoloring attempts.
2314 RecolorStack.resize(N: EntryStackSize);
2315 }
2316
2317 // Last chance recoloring did not worked either, give up.
2318 return ~0u;
2319}
2320
2321/// tryRecoloringCandidates - Try to assign a new color to every register
2322/// in \RecoloringQueue.
2323/// \p NewRegs will contain any new virtual register created during the
2324/// recoloring process.
2325/// \p FixedRegisters[in/out] contains all the registers that have been
2326/// recolored.
2327/// \return true if all virtual registers in RecoloringQueue were successfully
2328/// recolored, false otherwise.
2329bool RAGreedy::tryRecoloringCandidates(PQueue &RecoloringQueue,
2330 SmallVectorImpl<Register> &NewVRegs,
2331 SmallVirtRegSet &FixedRegisters,
2332 RecoloringStack &RecolorStack,
2333 unsigned Depth) {
2334 while (!RecoloringQueue.empty()) {
2335 const LiveInterval *LI = dequeue(CurQueue&: RecoloringQueue);
2336 LLVM_DEBUG(dbgs() << "Try to recolor: " << *LI << '\n');
2337 MCRegister PhysReg = selectOrSplitImpl(*LI, NewVRegs, FixedRegisters,
2338 RecolorStack, Depth + 1);
2339 // When splitting happens, the live-range may actually be empty.
2340 // In that case, this is okay to continue the recoloring even
2341 // if we did not find an alternative color for it. Indeed,
2342 // there will not be anything to color for LI in the end.
2343 if (PhysReg == ~0u || (!PhysReg && !LI->empty()))
2344 return false;
2345
2346 if (!PhysReg) {
2347 assert(LI->empty() && "Only empty live-range do not require a register");
2348 LLVM_DEBUG(dbgs() << "Recoloring of " << *LI
2349 << " succeeded. Empty LI.\n");
2350 continue;
2351 }
2352 LLVM_DEBUG(dbgs() << "Recoloring of " << *LI
2353 << " succeeded with: " << printReg(PhysReg, TRI) << '\n');
2354
2355 Matrix->assign(VirtReg: *LI, PhysReg);
2356 FixedRegisters.insert(V: LI->reg());
2357 }
2358 return true;
2359}
2360
2361//===----------------------------------------------------------------------===//
2362// Main Entry Point
2363//===----------------------------------------------------------------------===//
2364
2365MCRegister RAGreedy::selectOrSplit(const LiveInterval &VirtReg,
2366 SmallVectorImpl<Register> &NewVRegs) {
2367 CutOffInfo = CO_None;
2368 LLVMContext &Ctx = MF->getFunction().getContext();
2369 SmallVirtRegSet FixedRegisters;
2370 RecoloringStack RecolorStack;
2371 MCRegister Reg =
2372 selectOrSplitImpl(VirtReg, NewVRegs, FixedRegisters, RecolorStack);
2373 if (Reg == ~0U && (CutOffInfo != CO_None)) {
2374 uint8_t CutOffEncountered = CutOffInfo & (CO_Depth | CO_Interf);
2375 if (CutOffEncountered == CO_Depth)
2376 Ctx.emitError(ErrorStr: "register allocation failed: maximum depth for recoloring "
2377 "reached. Use -fexhaustive-register-search to skip "
2378 "cutoffs");
2379 else if (CutOffEncountered == CO_Interf)
2380 Ctx.emitError(ErrorStr: "register allocation failed: maximum interference for "
2381 "recoloring reached. Use -fexhaustive-register-search "
2382 "to skip cutoffs");
2383 else if (CutOffEncountered == (CO_Depth | CO_Interf))
2384 Ctx.emitError(ErrorStr: "register allocation failed: maximum interference and "
2385 "depth for recoloring reached. Use "
2386 "-fexhaustive-register-search to skip cutoffs");
2387 }
2388 return Reg;
2389}
2390
2391/// calcSpillCost - Compute how expensive it would be to spill the live range in
2392/// LI into memory.
2393BlockFrequency RAGreedy::calcSpillCost(const LiveInterval &LI) {
2394 uint64_t SpillCost = 0;
2395 SmallPtrSet<MachineInstr *, 8> Visited;
2396
2397 for (MachineRegisterInfo::reg_instr_nodbg_iterator
2398 I = MRI->reg_instr_nodbg_begin(RegNo: LI.reg()),
2399 E = MRI->reg_instr_nodbg_end();
2400 I != E;) {
2401 MachineInstr *MI = &*(I++);
2402 if (MI->isMetaInstruction())
2403 continue;
2404 if (!Visited.insert(Ptr: MI).second)
2405 continue;
2406
2407 auto [Reads, Writes] = MI->readsWritesVirtualRegister(Reg: LI.reg());
2408 auto MBBFreq = SpillPlacer->getBlockFrequency(Number: MI->getParent()->getNumber());
2409 SpillCost += (Reads + Writes) * MBBFreq.getFrequency();
2410 }
2411
2412 return BlockFrequency(SpillCost);
2413}
2414
2415BlockFrequency RAGreedy::calcRematCost(const LiveInterval &VirtReg,
2416 AllocationOrder &Order) const {
2417 if (!VirtReg.isSpillable())
2418 return BlockFrequency::max();
2419
2420 // This logic is intentionally narrow: handle a single concrete value
2421 // whose def can be cheaply rematerialized at every use.
2422 if (!VirtReg.containsOneValue())
2423 return BlockFrequency::max();
2424 const VNInfo *OnlyVNI = VirtReg.getValNumInfo(ValNo: 0);
2425 if (OnlyVNI->isUnused() || OnlyVNI->isPHIDef())
2426 return BlockFrequency::max();
2427
2428 MachineInstr *DefMI = LIS->getInstructionFromIndex(index: OnlyVNI->def);
2429 if (!DefMI || !TII->isReMaterializable(MI: *DefMI) ||
2430 !TII->isAsCheapAsAMove(MI: *DefMI))
2431 return BlockFrequency::max();
2432
2433 // Only consider live ranges with register-mask interference. This limits the
2434 // heuristic to avoiding a first-use CSR required by a call rather than by
2435 // register pressure.
2436 if (!Matrix->checkRegMaskInterference(VirtReg))
2437 return BlockFrequency::max();
2438
2439 BlockFrequency RematCost;
2440 bool HasUse = false;
2441 for (MachineInstr &UseMI : MRI->use_nodbg_instructions(Reg: VirtReg.reg())) {
2442 if (!UseMI.readsVirtualRegister(Reg: VirtReg.reg()))
2443 continue;
2444
2445 if (!canGuaranteeAssignmentAfterRemat(VReg: VirtReg.reg(), MI: UseMI))
2446 return BlockFrequency::max();
2447
2448 SlotIndex UseIdx = LIS->getInstructionIndex(Instr: UseMI).getRegSlot(EC: true);
2449 if (!VirtRegAuxInfo::allUsesAvailableAt(MI: DefMI, UseIdx, LIS: *LIS, MRI: *MRI, TII: *TII))
2450 return BlockFrequency::max();
2451
2452 // Check if any register that is not a first-use CSR is available as
2453 // destination for the rematerialization.
2454 SlotIndex PrevIdx = UseIdx.getPrevSlot();
2455 bool HasNoFirstCSRReg = false;
2456 for (MCRegister RematPhysReg : Order) {
2457 if (EvictAdvisor->getUnusedCalleeSavedReg(VirtReg, PhysReg: RematPhysReg))
2458 continue;
2459 if (!Matrix->checkInterference(Start: PrevIdx, End: UseIdx, PhysReg: RematPhysReg)) {
2460 HasNoFirstCSRReg = true;
2461 break;
2462 }
2463 }
2464 if (!HasNoFirstCSRReg)
2465 return BlockFrequency::max();
2466
2467 RematCost += SpillPlacer->getBlockFrequency(Number: UseMI.getParent()->getNumber());
2468 HasUse = true;
2469 }
2470
2471 return HasUse ? RematCost : BlockFrequency::max();
2472}
2473
2474/// Using a CSR for the first time has a cost because it causes push|pop
2475/// to be added to prologue|epilogue. Splitting a cold section of the live
2476/// range can have lower cost than using the CSR for the first time;
2477/// Spilling a live range in the cold path can have lower cost than using
2478/// the CSR for the first time. Returns the physical register if we decide
2479/// to use the CSR; otherwise return MCRegister().
2480MCRegister RAGreedy::tryAssignCSRFirstTime(
2481 const LiveInterval &VirtReg, AllocationOrder &Order, MCRegister PhysReg,
2482 uint8_t &CostPerUseLimit, SmallVectorImpl<Register> &NewVRegs) {
2483 LiveRangeStage Stage = ExtraInfo->getStage(VirtReg);
2484
2485 if (Stage == RS_Spill && VirtReg.isSpillable()) {
2486 // We choose spill or rematerialize over using the CSR for the first time if
2487 // the spill cost is lower than CSRCost.
2488 SA->analyze(li: &VirtReg);
2489 if (calcSpillCost(LI: VirtReg) >= CSRCost &&
2490 calcRematCost(VirtReg, Order) >= CSRCost) {
2491 return PhysReg;
2492 }
2493
2494 // We are going to spill or rematerialize, set CostPerUseLimit to 1 to make
2495 // sure that we will not use a callee-saved register in tryEvict.
2496 CostPerUseLimit = 1;
2497 return MCRegister();
2498 }
2499 if (Stage < RS_Split) {
2500 // We choose pre-splitting over using the CSR for the first time if
2501 // the cost of splitting is lower than CSRCost.
2502 SA->analyze(li: &VirtReg);
2503 unsigned NumCands = 0;
2504 BlockFrequency BestCost = CSRCost; // Don't modify CSRCost.
2505 unsigned BestCand = calculateRegionSplitCost(VirtReg, Order, BestCost,
2506 NumCands, IgnoreCSR: true /*IgnoreCSR*/);
2507 if (BestCand == NoCand) {
2508 if (calcRematCost(VirtReg, Order) < CSRCost) {
2509 CostPerUseLimit = 1;
2510 return MCRegister();
2511 }
2512 // Use the CSR if we can't find a region split below CSRCost.
2513 return PhysReg;
2514 }
2515
2516 // Perform the actual pre-splitting.
2517 doRegionSplit(VirtReg, BestCand, HasCompact: false/*HasCompact*/, NewVRegs);
2518 return MCRegister();
2519 }
2520 if (calcRematCost(VirtReg, Order) < CSRCost) {
2521 CostPerUseLimit = 1;
2522 return MCRegister();
2523 }
2524 return PhysReg;
2525}
2526
2527void RAGreedy::aboutToRemoveInterval(const LiveInterval &LI) {
2528 // Do not keep invalid information around.
2529 SetOfBrokenHints.remove(X: &LI);
2530}
2531
2532void RAGreedy::initializeCSRCost() {
2533 if (!CSRCostScale.getNumOccurrences() &&
2534 (CSRFirstTimeCost.getNumOccurrences() || TRI->getCSRCost())) {
2535 // We should deprecate the usage of CSRFirstTimeCost!
2536 // We use the command-line option if it is explicitly set, otherwise use the
2537 // larger one out of the command-line option and the value reported by TRI.
2538 CSRCost = BlockFrequency(
2539 CSRFirstTimeCost.getNumOccurrences()
2540 ? CSRFirstTimeCost
2541 : std::max(a: (unsigned)CSRFirstTimeCost, b: TRI->getCSRCost()));
2542 if (!CSRCost.getFrequency())
2543 return;
2544
2545 // Raw cost is relative to Entry == 2^14; scale it appropriately.
2546 uint64_t ActualEntry = MBFI->getEntryFreq().getFrequency();
2547 if (!ActualEntry) {
2548 CSRCost = BlockFrequency(0);
2549 return;
2550 }
2551 uint64_t FixedEntry = 1 << 14;
2552 if (ActualEntry < FixedEntry) {
2553 CSRCost *= BranchProbability(ActualEntry, FixedEntry);
2554 } else if (ActualEntry <= UINT32_MAX) {
2555 // Invert the fraction and divide.
2556 CSRCost /= BranchProbability(FixedEntry, ActualEntry);
2557 } else {
2558 // Can't use BranchProbability in general, since it takes 32-bit numbers.
2559 CSRCost =
2560 BlockFrequency(CSRCost.getFrequency() * (ActualEntry / FixedEntry));
2561 }
2562 } else {
2563 uint64_t EntryFreq = MBFI->getEntryFreq().getFrequency();
2564 CSRCost = BlockFrequency(TRI->getCSRFirstUseCost(MF: *MF) * EntryFreq);
2565 unsigned Scale = TRI->getCSRCostScale(MF: *MF);
2566 // Command line specified CSRCostScale can override target's default value.
2567 if (CSRCostScale.getNumOccurrences())
2568 Scale = CSRCostScale;
2569
2570 if (Scale < 100)
2571 CSRCost *= BranchProbability(Scale, 100);
2572 else
2573 CSRCost /= BranchProbability(100, Scale);
2574 }
2575}
2576
2577/// Collect the hint info for \p Reg.
2578/// The results are stored into \p Out.
2579/// \p Out is not cleared before being populated.
2580void RAGreedy::collectHintInfo(Register Reg, HintsInfo &Out) {
2581 const TargetRegisterClass *RC = MRI->getRegClass(Reg);
2582
2583 for (const MachineOperand &Opnd : MRI->reg_nodbg_operands(Reg)) {
2584 const MachineInstr &Instr = *Opnd.getParent();
2585 if (!Instr.isCopy() || Opnd.isImplicit())
2586 continue;
2587
2588 // Look for the other end of the copy.
2589 const MachineOperand &OtherOpnd = Instr.getOperand(i: Opnd.isDef());
2590 Register OtherReg = OtherOpnd.getReg();
2591 if (OtherReg == Reg)
2592 continue;
2593 unsigned OtherSubReg = OtherOpnd.getSubReg();
2594 unsigned SubReg = Opnd.getSubReg();
2595
2596 // Get the current assignment.
2597 MCRegister OtherPhysReg;
2598 if (OtherReg.isPhysical()) {
2599 if (OtherSubReg)
2600 OtherPhysReg = TRI->getMatchingSuperReg(Reg: OtherReg, SubIdx: OtherSubReg, RC);
2601 else if (SubReg)
2602 OtherPhysReg = TRI->getMatchingSuperReg(Reg: OtherReg, SubIdx: SubReg, RC);
2603 else
2604 OtherPhysReg = OtherReg;
2605 } else {
2606 OtherPhysReg = VRM->getPhys(virtReg: OtherReg);
2607 // TODO: Should find matching superregister, but applying this in the
2608 // non-hint case currently causes regressions
2609
2610 if (SubReg && OtherSubReg && SubReg != OtherSubReg)
2611 continue;
2612 }
2613
2614 // Push the collected information.
2615 if (OtherPhysReg) {
2616 Out.push_back(Elt: HintInfo(Instr.getParent(), OtherReg, OtherPhysReg));
2617 }
2618 }
2619}
2620
2621/// Using the given \p List, compute the cost of the broken hints if
2622/// \p PhysReg was used.
2623/// \return The cost of \p List for \p PhysReg.
2624BlockFrequency RAGreedy::getBrokenHintFreq(const HintsInfo &List,
2625 MCRegister PhysReg) {
2626 BlockFrequency Cost = BlockFrequency(0);
2627 for (const HintInfo &Info : List) {
2628 if (Info.PhysReg != PhysReg)
2629 Cost += MBFI->getBlockFreq(MBB: Info.MBB);
2630 }
2631 return Cost;
2632}
2633
2634/// Using the register assigned to \p VirtReg, try to recolor
2635/// all the live ranges that are copy-related with \p VirtReg.
2636/// The recoloring is then propagated to all the live-ranges that have
2637/// been recolored and so on, until no more copies can be coalesced or
2638/// it is not profitable.
2639/// For a given live range, profitability is determined by the sum of the
2640/// frequencies of the non-identity copies it would introduce with the old
2641/// and new register.
2642/// \p NoRecolorRegs holds registers whose walk is known to recolor nothing.
2643/// It is cleared whenever a recoloring happens.
2644void RAGreedy::tryHintRecoloring(const LiveInterval &VirtReg,
2645 DenseSet<Register> &NoRecolorRegs) {
2646 // We have a broken hint, check if it is possible to fix it by
2647 // reusing PhysReg for the copy-related live-ranges. Indeed, we evicted
2648 // some register and PhysReg may be available for the other live-ranges.
2649 HintsInfo Info;
2650 Register Reg = VirtReg.reg();
2651 MCRegister PhysReg = VRM->getPhys(virtReg: Reg);
2652 // Start the recoloring algorithm from the input live-interval, then
2653 // it will propagate to the ones that are copy-related with it.
2654 SmallDenseSet<Register, 8> Visited = {Reg};
2655 SmallVector<Register, 2> RecoloringCandidates = {Reg};
2656 SmallVector<Register, 8> Reached;
2657 bool Changed = false;
2658
2659 LLVM_DEBUG(dbgs() << "Trying to reconcile hints for: " << printReg(Reg, TRI)
2660 << '(' << printReg(PhysReg, TRI) << ")\n");
2661
2662 do {
2663 Reg = RecoloringCandidates.pop_back_val();
2664
2665 MCRegister CurrPhys = VRM->getPhys(virtReg: Reg);
2666
2667 // This may be a skipped register.
2668 if (!CurrPhys) {
2669 assert(!shouldAllocateRegister(Reg) &&
2670 "We have an unallocated variable which should have been handled");
2671 continue;
2672 }
2673
2674 // Get the live interval mapped with this virtual register to be able
2675 // to check for the interference with the new color.
2676 LiveInterval &LI = LIS->getInterval(Reg);
2677 // Check that the new color matches the register class constraints and
2678 // that it is free for this live range.
2679 if (CurrPhys != PhysReg && (!MRI->getRegClass(Reg)->contains(Reg: PhysReg) ||
2680 Matrix->checkInterference(VirtReg: LI, PhysReg)))
2681 continue;
2682
2683 LLVM_DEBUG(dbgs() << printReg(Reg, TRI) << '(' << printReg(CurrPhys, TRI)
2684 << ") is recolorable.\n");
2685
2686 // Gather the hint info.
2687 Info.clear();
2688 collectHintInfo(Reg, Out&: Info);
2689 // Check if recoloring the live-range will increase the cost of the
2690 // non-identity copies.
2691 if (CurrPhys != PhysReg) {
2692 LLVM_DEBUG(dbgs() << "Checking profitability:\n");
2693 BlockFrequency OldCopiesCost = getBrokenHintFreq(List: Info, PhysReg: CurrPhys);
2694 BlockFrequency NewCopiesCost = getBrokenHintFreq(List: Info, PhysReg);
2695 LLVM_DEBUG(dbgs() << "Old Cost: " << printBlockFreq(*MBFI, OldCopiesCost)
2696 << "\nNew Cost: "
2697 << printBlockFreq(*MBFI, NewCopiesCost) << '\n');
2698 if (OldCopiesCost < NewCopiesCost) {
2699 LLVM_DEBUG(dbgs() << "=> Not profitable.\n");
2700 continue;
2701 }
2702 // At this point, the cost is either cheaper or equal. If it is
2703 // equal, we consider this is profitable because it may expose
2704 // more recoloring opportunities.
2705 LLVM_DEBUG(dbgs() << "=> Profitable.\n");
2706 // Recolor the live-range.
2707 Matrix->unassign(VirtReg: LI);
2708 Matrix->assign(VirtReg: LI, PhysReg);
2709 Changed = true;
2710 } else {
2711 Reached.push_back(Elt: Reg);
2712 }
2713 // Push all copy-related live-ranges to keep reconciling the broken
2714 // hints.
2715 for (const HintInfo &HI : Info) {
2716 // We cannot recolor physical register.
2717 if (HI.Reg.isVirtual() && Visited.insert(V: HI.Reg).second)
2718 RecoloringCandidates.push_back(Elt: HI.Reg);
2719 }
2720 } while (!RecoloringCandidates.empty());
2721
2722 if (Changed)
2723 NoRecolorRegs.clear();
2724 else
2725 NoRecolorRegs.insert_range(R&: Reached);
2726}
2727
2728/// Try to recolor broken hints.
2729/// Broken hints may be repaired by recoloring when an evicted variable
2730/// freed up a register for a larger live-range.
2731/// Consider the following example:
2732/// BB1:
2733/// a =
2734/// b =
2735/// BB2:
2736/// ...
2737/// = b
2738/// = a
2739/// Let us assume b gets split:
2740/// BB1:
2741/// a =
2742/// b =
2743/// BB2:
2744/// c = b
2745/// ...
2746/// d = c
2747/// = d
2748/// = a
2749/// Because of how the allocation work, b, c, and d may be assigned different
2750/// colors. Now, if a gets evicted later:
2751/// BB1:
2752/// a =
2753/// st a, SpillSlot
2754/// b =
2755/// BB2:
2756/// c = b
2757/// ...
2758/// d = c
2759/// = d
2760/// e = ld SpillSlot
2761/// = e
2762/// This is likely that we can assign the same register for b, c, and d,
2763/// getting rid of 2 copies.
2764void RAGreedy::tryHintsRecoloring() {
2765 DenseSet<Register> NoRecolorRegs;
2766 for (const LiveInterval *LI : SetOfBrokenHints) {
2767 assert(LI->reg().isVirtual() &&
2768 "Recoloring is possible only for virtual registers");
2769 // Some dead defs may be around (e.g., because of debug uses).
2770 // Ignore those.
2771 if (!VRM->hasPhys(virtReg: LI->reg()) || NoRecolorRegs.contains(V: LI->reg()))
2772 continue;
2773 tryHintRecoloring(VirtReg: *LI, NoRecolorRegs);
2774 }
2775}
2776
2777MCRegister RAGreedy::selectOrSplitImpl(const LiveInterval &VirtReg,
2778 SmallVectorImpl<Register> &NewVRegs,
2779 SmallVirtRegSet &FixedRegisters,
2780 RecoloringStack &RecolorStack,
2781 unsigned Depth) {
2782 uint8_t CostPerUseLimit = uint8_t(~0u);
2783 // First try assigning a free register.
2784 auto Order =
2785 AllocationOrder::create(VirtReg: VirtReg.reg(), VRM: *VRM, RegClassInfo: *RegClassInfo, Matrix);
2786 if (MCRegister PhysReg =
2787 tryAssign(VirtReg, Order, NewVRegs, FixedRegisters)) {
2788 // When NewVRegs is not empty, we may have made decisions such as evicting
2789 // a virtual register, go with the earlier decisions and use the physical
2790 // register.
2791 if (CSRCost.getFrequency() &&
2792 EvictAdvisor->getUnusedCalleeSavedReg(VirtReg, PhysReg) &&
2793 NewVRegs.empty()) {
2794 MCRegister CSRReg = tryAssignCSRFirstTime(VirtReg, Order, PhysReg,
2795 CostPerUseLimit, NewVRegs);
2796 if (CSRReg || !NewVRegs.empty())
2797 // Return now if we decide to use a CSR or create new vregs due to
2798 // pre-splitting.
2799 return CSRReg;
2800 } else
2801 return PhysReg;
2802 }
2803 // Non empty NewVRegs means VirtReg has been split.
2804 if (!NewVRegs.empty())
2805 return MCRegister();
2806
2807 LiveRangeStage Stage = ExtraInfo->getStage(VirtReg);
2808 LLVM_DEBUG(dbgs() << StageName[Stage] << " Cascade "
2809 << ExtraInfo->getCascade(VirtReg.reg()) << '\n');
2810
2811 // Try to evict a less worthy live range, but only for ranges from the primary
2812 // queue. The RS_Split ranges already failed to do this, and they should not
2813 // get a second chance until they have been split.
2814 if (Stage != RS_Split) {
2815 if (MCRegister PhysReg =
2816 tryEvict(VirtReg, Order, NewVRegs, CostPerUseLimit,
2817 FixedRegisters)) {
2818 Register Hint = MRI->getSimpleHint(VReg: VirtReg.reg());
2819 // If VirtReg has a hint and that hint is broken record this
2820 // virtual register as a recoloring candidate for broken hint.
2821 // Indeed, since we evicted a variable in its neighborhood it is
2822 // likely we can at least partially recolor some of the
2823 // copy-related live-ranges.
2824 if (Hint && Hint != PhysReg)
2825 SetOfBrokenHints.insert(X: &VirtReg);
2826 return PhysReg;
2827 }
2828 }
2829
2830 assert((NewVRegs.empty() || Depth) && "Cannot append to existing NewVRegs");
2831
2832 // The first time we see a live range, don't try to split or spill.
2833 // Wait until the second time, when all smaller ranges have been allocated.
2834 // This gives a better picture of the interference to split around.
2835 if (Stage < RS_Split) {
2836 ExtraInfo->setStage(VirtReg, Stage: RS_Split);
2837 LLVM_DEBUG(dbgs() << "wait for second round\n");
2838 NewVRegs.push_back(Elt: VirtReg.reg());
2839 return MCRegister();
2840 }
2841
2842 if (Stage < RS_Spill && !VirtReg.empty()) {
2843 // Try splitting VirtReg or interferences.
2844 unsigned NewVRegSizeBefore = NewVRegs.size();
2845 MCRegister PhysReg = trySplit(VirtReg, Order, NewVRegs, FixedRegisters);
2846 if (PhysReg || (NewVRegs.size() - NewVRegSizeBefore))
2847 return PhysReg;
2848 }
2849
2850 // If we couldn't allocate a register from spilling, there is probably some
2851 // invalid inline assembly. The base class will report it.
2852 if (Stage >= RS_Done || !VirtReg.isSpillable()) {
2853 return tryLastChanceRecoloring(VirtReg, Order, NewVRegs, FixedRegisters,
2854 RecolorStack, Depth);
2855 }
2856
2857 // Finally spill VirtReg itself.
2858 NamedRegionTimer T("spill", "Spiller", TimerGroupName,
2859 TimerGroupDescription, TimePassesIsEnabled);
2860 LiveRangeEdit LRE(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);
2861 spiller().spill(LRE, Order: &Order);
2862 ExtraInfo->setStage(Begin: NewVRegs.begin(), End: NewVRegs.end(), NewStage: RS_Done);
2863
2864 // Tell LiveDebugVariables about the new ranges. Ranges not being covered by
2865 // the new regs are kept in LDV (still mapping to the old register), until
2866 // we rewrite spilled locations in LDV at a later stage.
2867 for (Register r : spiller().getSpilledRegs())
2868 DebugVars->splitRegister(OldReg: r, NewRegs: LRE.regs(), LIS&: *LIS);
2869 for (Register r : spiller().getReplacedRegs())
2870 DebugVars->splitRegister(OldReg: r, NewRegs: LRE.regs(), LIS&: *LIS);
2871
2872 if (VerifyEnabled)
2873 MF->verify(LiveInts: LIS, Indexes, Banner: "After spilling", OS: &errs());
2874
2875 // The live virtual register requesting allocation was spilled, so tell
2876 // the caller not to allocate anything during this round.
2877 return MCRegister();
2878}
2879
2880void RAGreedy::RAGreedyStats::report(MachineOptimizationRemarkMissed &R) {
2881 using namespace ore;
2882 if (Spills) {
2883 R << NV("NumSpills", Spills) << " spills ";
2884 R << NV("TotalSpillsCost", SpillsCost) << " total spills cost ";
2885 }
2886 if (FoldedSpills) {
2887 R << NV("NumFoldedSpills", FoldedSpills) << " folded spills ";
2888 R << NV("TotalFoldedSpillsCost", FoldedSpillsCost)
2889 << " total folded spills cost ";
2890 }
2891 if (Reloads) {
2892 R << NV("NumReloads", Reloads) << " reloads ";
2893 R << NV("TotalReloadsCost", ReloadsCost) << " total reloads cost ";
2894 }
2895 if (FoldedReloads) {
2896 R << NV("NumFoldedReloads", FoldedReloads) << " folded reloads ";
2897 R << NV("TotalFoldedReloadsCost", FoldedReloadsCost)
2898 << " total folded reloads cost ";
2899 }
2900 if (ZeroCostFoldedReloads)
2901 R << NV("NumZeroCostFoldedReloads", ZeroCostFoldedReloads)
2902 << " zero cost folded reloads ";
2903 if (Copies) {
2904 R << NV("NumVRCopies", Copies) << " virtual registers copies ";
2905 R << NV("TotalCopiesCost", CopiesCost) << " total copies cost ";
2906 }
2907}
2908
2909RAGreedy::RAGreedyStats RAGreedy::computeStats(MachineBasicBlock &MBB) {
2910 RAGreedyStats Stats;
2911 const MachineFrameInfo &MFI = MF->getFrameInfo();
2912 int FI;
2913
2914 auto isSpillSlotAccess = [&MFI](const MachineMemOperand *A) {
2915 return MFI.isSpillSlotObjectIndex(ObjectIdx: cast<FixedStackPseudoSourceValue>(
2916 Val: A->getPseudoValue())->getFrameIndex());
2917 };
2918 auto isPatchpointInstr = [](const MachineInstr &MI) {
2919 return MI.getOpcode() == TargetOpcode::PATCHPOINT ||
2920 MI.getOpcode() == TargetOpcode::STACKMAP ||
2921 MI.getOpcode() == TargetOpcode::STATEPOINT;
2922 };
2923 for (MachineInstr &MI : MBB) {
2924 auto DestSrc = TII->isCopyInstr(MI);
2925 if (DestSrc) {
2926 const MachineOperand &Dest = *DestSrc->Destination;
2927 const MachineOperand &Src = *DestSrc->Source;
2928 Register SrcReg = Src.getReg();
2929 Register DestReg = Dest.getReg();
2930 // Only count `COPY`s with a virtual register as source or destination.
2931 if (SrcReg.isVirtual() || DestReg.isVirtual()) {
2932 if (SrcReg.isVirtual()) {
2933 SrcReg = VRM->getPhys(virtReg: SrcReg);
2934 if (SrcReg && Src.getSubReg())
2935 SrcReg = TRI->getSubReg(Reg: SrcReg, Idx: Src.getSubReg());
2936 }
2937 if (DestReg.isVirtual()) {
2938 DestReg = VRM->getPhys(virtReg: DestReg);
2939 if (DestReg && Dest.getSubReg())
2940 DestReg = TRI->getSubReg(Reg: DestReg, Idx: Dest.getSubReg());
2941 }
2942 if (SrcReg != DestReg)
2943 ++Stats.Copies;
2944 }
2945 continue;
2946 }
2947
2948 SmallVector<const MachineMemOperand *, 2> Accesses;
2949 if (TII->isLoadFromStackSlot(MI, FrameIndex&: FI) && MFI.isSpillSlotObjectIndex(ObjectIdx: FI)) {
2950 ++Stats.Reloads;
2951 continue;
2952 }
2953 if (TII->isStoreToStackSlot(MI, FrameIndex&: FI) && MFI.isSpillSlotObjectIndex(ObjectIdx: FI)) {
2954 ++Stats.Spills;
2955 continue;
2956 }
2957 if (TII->hasLoadFromStackSlot(MI, Accesses) &&
2958 llvm::any_of(Range&: Accesses, P: isSpillSlotAccess)) {
2959 if (!isPatchpointInstr(MI)) {
2960 Stats.FoldedReloads += Accesses.size();
2961 continue;
2962 }
2963 // For statepoint there may be folded and zero cost folded stack reloads.
2964 std::pair<unsigned, unsigned> NonZeroCostRange =
2965 TII->getPatchpointUnfoldableRange(MI);
2966 SmallSet<unsigned, 16> FoldedReloads;
2967 SmallSet<unsigned, 16> ZeroCostFoldedReloads;
2968 for (unsigned Idx = 0, E = MI.getNumOperands(); Idx < E; ++Idx) {
2969 MachineOperand &MO = MI.getOperand(i: Idx);
2970 if (!MO.isFI() || !MFI.isSpillSlotObjectIndex(ObjectIdx: MO.getIndex()))
2971 continue;
2972 if (Idx >= NonZeroCostRange.first && Idx < NonZeroCostRange.second)
2973 FoldedReloads.insert(V: MO.getIndex());
2974 else
2975 ZeroCostFoldedReloads.insert(V: MO.getIndex());
2976 }
2977 // If stack slot is used in folded reload it is not zero cost then.
2978 for (unsigned Slot : FoldedReloads)
2979 ZeroCostFoldedReloads.erase(V: Slot);
2980 Stats.FoldedReloads += FoldedReloads.size();
2981 Stats.ZeroCostFoldedReloads += ZeroCostFoldedReloads.size();
2982 continue;
2983 }
2984 Accesses.clear();
2985 if (TII->hasStoreToStackSlot(MI, Accesses) &&
2986 llvm::any_of(Range&: Accesses, P: isSpillSlotAccess)) {
2987 Stats.FoldedSpills += Accesses.size();
2988 }
2989 }
2990 // Set cost of collected statistic by multiplication to relative frequency of
2991 // this basic block.
2992 float RelFreq = MBFI->getBlockFreqRelativeToEntryBlock(MBB: &MBB);
2993 Stats.ReloadsCost = RelFreq * Stats.Reloads;
2994 Stats.FoldedReloadsCost = RelFreq * Stats.FoldedReloads;
2995 Stats.SpillsCost = RelFreq * Stats.Spills;
2996 Stats.FoldedSpillsCost = RelFreq * Stats.FoldedSpills;
2997 Stats.CopiesCost = RelFreq * Stats.Copies;
2998 return Stats;
2999}
3000
3001RAGreedy::RAGreedyStats RAGreedy::reportStats(MachineLoop *L) {
3002 RAGreedyStats Stats;
3003
3004 // Sum up the spill and reloads in subloops.
3005 for (MachineLoop *SubLoop : *L)
3006 Stats.add(other: reportStats(L: SubLoop));
3007
3008 for (MachineBasicBlock *MBB : L->getBlocks())
3009 // Handle blocks that were not included in subloops.
3010 if (Loops->getLoopFor(BB: MBB) == L)
3011 Stats.add(other: computeStats(MBB&: *MBB));
3012
3013 if (!Stats.isEmpty()) {
3014 using namespace ore;
3015
3016 ORE->emit(RemarkBuilder: [&]() {
3017 MachineOptimizationRemarkMissed R(DEBUG_TYPE, "LoopSpillReloadCopies",
3018 L->getStartLoc(), L->getHeader());
3019 Stats.report(R);
3020 R << "generated in loop";
3021 return R;
3022 });
3023 }
3024 return Stats;
3025}
3026
3027void RAGreedy::reportStats() {
3028 if (!ORE->allowExtraAnalysis(DEBUG_TYPE))
3029 return;
3030 RAGreedyStats Stats;
3031 for (MachineLoop *L : *Loops)
3032 Stats.add(other: reportStats(L));
3033 // Process non-loop blocks.
3034 for (MachineBasicBlock &MBB : *MF)
3035 if (!Loops->getLoopFor(BB: &MBB))
3036 Stats.add(other: computeStats(MBB));
3037 if (!Stats.isEmpty()) {
3038 using namespace ore;
3039
3040 ORE->emit(RemarkBuilder: [&]() {
3041 DebugLoc Loc;
3042 if (auto *SP = MF->getFunction().getSubprogram())
3043 Loc = DILocation::get(Context&: SP->getContext(), Line: SP->getLine(), Column: 1, Scope: SP);
3044 MachineOptimizationRemarkMissed R(DEBUG_TYPE, "SpillReloadCopies", Loc,
3045 &MF->front());
3046 Stats.report(R);
3047 R << "generated in function";
3048 return R;
3049 });
3050 }
3051}
3052
3053bool RAGreedy::hasVirtRegAlloc() {
3054 for (unsigned I = 0, E = MRI->getNumVirtRegs(); I != E; ++I) {
3055 Register Reg = Register::index2VirtReg(Index: I);
3056 if (MRI->reg_nodbg_empty(RegNo: Reg))
3057 continue;
3058 if (shouldAllocateRegister(Reg))
3059 return true;
3060 }
3061
3062 return false;
3063}
3064
3065bool RAGreedy::run(MachineFunction &mf) {
3066 LLVM_DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n"
3067 << "********** Function: " << mf.getName() << '\n');
3068
3069 MF = &mf;
3070 TII = MF->getSubtarget().getInstrInfo();
3071
3072 if (VerifyEnabled)
3073 MF->verify(LiveInts: LIS, Indexes, Banner: "Before greedy register allocator", OS: &errs());
3074
3075 RegAllocBase::init(vrm&: *this->VRM, lis&: *this->LIS, mat&: *this->Matrix,
3076 rci&: *this->RegClassInfo);
3077
3078 // Early return if there is no virtual register to be allocated to a
3079 // physical register.
3080 if (!hasVirtRegAlloc())
3081 return false;
3082
3083 // Canonicalize LiveDebugVariables' indexes here and again in
3084 // emitDebugValues(); those are the only two points where it is clean, as
3085 // splitting stales indexes again mid-run. Reclaiming erased entries needs
3086 // its own entry point called from both, not a hook in packIndexes(), which
3087 // renumberIndexes() also reaches.
3088 DebugVars->canonicalizeIndexes(SI: *Indexes);
3089
3090 // Renumber to get accurate and consistent results from
3091 // SlotIndexes::getApproxInstrDistance.
3092 bool Compact = CompactSlotIndexes.getNumOccurrences()
3093 ? CompactSlotIndexes
3094 : TRI->shouldCompactSlotIndexes(MF: *MF);
3095 if (Compact) {
3096 // Compaction unlinks what it erases; this is what makes that safe.
3097 LIS->removeUnreferencedIntervals();
3098 Indexes->compactIndexes();
3099 } else {
3100 Indexes->packIndexes();
3101 }
3102
3103 initializeCSRCost();
3104
3105 RegCosts = TRI->getRegisterCosts(MF: *MF);
3106 RegClassPriorityTrumpsGlobalness =
3107 GreedyRegClassPriorityTrumpsGlobalness.getNumOccurrences()
3108 ? GreedyRegClassPriorityTrumpsGlobalness
3109 : TRI->regClassPriorityTrumpsGlobalness(MF: *MF);
3110
3111 ReverseLocalAssignment = GreedyReverseLocalAssignment.getNumOccurrences()
3112 ? GreedyReverseLocalAssignment
3113 : TRI->reverseLocalAssignment();
3114
3115 ExtraInfo.emplace();
3116
3117 EvictAdvisor = EvictProvider->getAdvisor(MF: *MF, RA: *this, MBFI, Loops);
3118 PriorityAdvisor = PriorityProvider->getAdvisor(MF: *MF, RA: *this, SI&: *Indexes);
3119
3120 VRAI = std::make_unique<VirtRegAuxInfo>(args&: *MF, args&: *LIS, args&: *VRM, args&: *Loops, args&: *MBFI);
3121 SpillerInstance.reset(p: createInlineSpiller(Analyses: {.LIS: *LIS, .LSS: *LSS, .MDT: *DomTree, .MBFI: *MBFI}, MF&: *MF,
3122 VRM&: *VRM, VRAI&: *VRAI, Matrix));
3123
3124 VRAI->calculateSpillWeightsAndHints();
3125
3126 LLVM_DEBUG(LIS->dump());
3127
3128 SA.reset(p: new SplitAnalysis(*VRM, *LIS, *Loops));
3129 SE.reset(p: new SplitEditor(*SA, *LIS, *VRM, *DomTree, *MBFI, *VRAI));
3130
3131 IntfCache.init(mf: MF, liuarray: Matrix->getLiveUnions(), indexes: Indexes, lis: LIS, tri: TRI);
3132 GlobalCand.resize(N: 32); // This will grow as needed.
3133 SetOfBrokenHints.clear();
3134
3135 allocatePhysRegs();
3136 tryHintsRecoloring();
3137
3138 if (VerifyEnabled)
3139 MF->verify(LiveInts: LIS, Indexes, Banner: "Before post optimization", OS: &errs());
3140 postOptimization();
3141 reportStats();
3142
3143 releaseMemory();
3144 return true;
3145}
3146