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