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