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