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