LLVM 20.0.0git
RegAllocEvictionAdvisor.cpp
Go to the documentation of this file.
1//===- RegAllocEvictionAdvisor.cpp - eviction advisor ---------------------===//
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// Implementation of the default eviction advisor and of the Analysis pass.
10//
11//===----------------------------------------------------------------------===//
12
14#include "AllocationOrder.h"
15#include "RegAllocGreedy.h"
20#include "llvm/IR/Module.h"
22#include "llvm/Pass.h"
26
27using namespace llvm;
28
30 "regalloc-enable-advisor", cl::Hidden,
31 cl::init(RegAllocEvictionAdvisorAnalysis::AdvisorMode::Default),
32 cl::desc("Enable regalloc advisor mode"),
34 clEnumValN(RegAllocEvictionAdvisorAnalysis::AdvisorMode::Default,
35 "default", "Default"),
36 clEnumValN(RegAllocEvictionAdvisorAnalysis::AdvisorMode::Release,
37 "release", "precompiled"),
38 clEnumValN(RegAllocEvictionAdvisorAnalysis::AdvisorMode::Development,
39 "development", "for training")));
40
42 "enable-local-reassign", cl::Hidden,
43 cl::desc("Local reassignment can yield better allocation decisions, but "
44 "may be compile time intensive"),
45 cl::init(false));
46
47namespace llvm {
49 "regalloc-eviction-max-interference-cutoff", cl::Hidden,
50 cl::desc("Number of interferences after which we declare "
51 "an interference unevictable and bail out. This "
52 "is a compilation cost-saving consideration. To "
53 "disable, pass a very large number."),
54 cl::init(10));
55}
56
57#define DEBUG_TYPE "regalloc"
58#ifdef LLVM_HAVE_TF_AOT_REGALLOCEVICTMODEL
59#define LLVM_HAVE_TF_AOT
60#endif
61
64 "Regalloc eviction policy", false, true)
65
66namespace {
67class DefaultEvictionAdvisorAnalysis final
69public:
70 DefaultEvictionAdvisorAnalysis(bool NotAsRequested)
71 : RegAllocEvictionAdvisorAnalysis(AdvisorMode::Default),
72 NotAsRequested(NotAsRequested) {}
73
74 // support for isa<> and dyn_cast.
75 static bool classof(const RegAllocEvictionAdvisorAnalysis *R) {
76 return R->getAdvisorMode() == AdvisorMode::Default;
77 }
78
79private:
80 std::unique_ptr<RegAllocEvictionAdvisor>
81 getAdvisor(const MachineFunction &MF, const RAGreedy &RA) override {
82 return std::make_unique<DefaultEvictionAdvisor>(MF, RA);
83 }
84 bool doInitialization(Module &M) override {
85 if (NotAsRequested)
86 M.getContext().emitError("Requested regalloc eviction advisor analysis "
87 "could not be created. Using default");
89 }
90 const bool NotAsRequested;
91};
92} // namespace
93
95 Pass *Ret = nullptr;
96 switch (Mode) {
97 case RegAllocEvictionAdvisorAnalysis::AdvisorMode::Default:
98 Ret = new DefaultEvictionAdvisorAnalysis(/*NotAsRequested*/ false);
99 break;
100 case RegAllocEvictionAdvisorAnalysis::AdvisorMode::Development:
101#if defined(LLVM_HAVE_TFLITE)
103#endif
104 break;
105 case RegAllocEvictionAdvisorAnalysis::AdvisorMode::Release:
107 break;
108 }
109 if (Ret)
110 return Ret;
111 return new DefaultEvictionAdvisorAnalysis(/*NotAsRequested*/ true);
112}
113
114StringRef RegAllocEvictionAdvisorAnalysis::getPassName() const {
115 switch (getAdvisorMode()) {
117 return "Default Regalloc Eviction Advisor";
119 return "Release mode Regalloc Eviction Advisor";
121 return "Development mode Regalloc Eviction Advisor";
122 }
123 llvm_unreachable("Unknown advisor kind");
124}
125
127 const RAGreedy &RA)
128 : MF(MF), RA(RA), Matrix(RA.getInterferenceMatrix()),
129 LIS(RA.getLiveIntervals()), VRM(RA.getVirtRegMap()),
130 MRI(&VRM->getRegInfo()), TRI(MF.getSubtarget().getRegisterInfo()),
131 RegClassInfo(RA.getRegClassInfo()), RegCosts(TRI->getRegisterCosts(MF)),
132 EnableLocalReassign(EnableLocalReassignment ||
133 MF.getSubtarget().enableRALocalReassignment(
134 MF.getTarget().getOptLevel())) {}
135
136/// shouldEvict - determine if A should evict the assigned live range B. The
137/// eviction policy defined by this function together with the allocation order
138/// defined by enqueue() decides which registers ultimately end up being split
139/// and spilled.
140///
141/// Cascade numbers are used to prevent infinite loops if this function is a
142/// cyclic relation.
143///
144/// @param A The live range to be assigned.
145/// @param IsHint True when A is about to be assigned to its preferred
146/// register.
147/// @param B The live range to be evicted.
148/// @param BreaksHint True when B is already assigned to its preferred register.
149bool DefaultEvictionAdvisor::shouldEvict(const LiveInterval &A, bool IsHint,
150 const LiveInterval &B,
151 bool BreaksHint) const {
152 bool CanSplit = RA.getExtraInfo().getStage(B) < RS_Spill;
153
154 // Be fairly aggressive about following hints as long as the evictee can be
155 // split.
156 if (CanSplit && IsHint && !BreaksHint)
157 return true;
158
159 if (A.weight() > B.weight()) {
160 LLVM_DEBUG(dbgs() << "should evict: " << B << " w= " << B.weight() << '\n');
161 return true;
162 }
163 return false;
164}
165
166/// canEvictHintInterference - return true if the interference for VirtReg
167/// on the PhysReg, which is VirtReg's hint, can be evicted in favor of VirtReg.
168bool DefaultEvictionAdvisor::canEvictHintInterference(
169 const LiveInterval &VirtReg, MCRegister PhysReg,
170 const SmallVirtRegSet &FixedRegisters) const {
171 EvictionCost MaxCost;
172 MaxCost.setBrokenHints(1);
173 return canEvictInterferenceBasedOnCost(VirtReg, PhysReg, true, MaxCost,
174 FixedRegisters);
175}
176
177/// canEvictInterferenceBasedOnCost - Return true if all interferences between
178/// VirtReg and PhysReg can be evicted.
179///
180/// @param VirtReg Live range that is about to be assigned.
181/// @param PhysReg Desired register for assignment.
182/// @param IsHint True when PhysReg is VirtReg's preferred register.
183/// @param MaxCost Only look for cheaper candidates and update with new cost
184/// when returning true.
185/// @returns True when interference can be evicted cheaper than MaxCost.
186bool DefaultEvictionAdvisor::canEvictInterferenceBasedOnCost(
187 const LiveInterval &VirtReg, MCRegister PhysReg, bool IsHint,
188 EvictionCost &MaxCost, const SmallVirtRegSet &FixedRegisters) const {
189 // It is only possible to evict virtual register interference.
190 if (Matrix->checkInterference(VirtReg, PhysReg) > LiveRegMatrix::IK_VirtReg)
191 return false;
192
193 bool IsLocal = VirtReg.empty() || LIS->intervalIsInOneMBB(VirtReg);
194
195 // Find VirtReg's cascade number. This will be unassigned if VirtReg was never
196 // involved in an eviction before. If a cascade number was assigned, deny
197 // evicting anything with the same or a newer cascade number. This prevents
198 // infinite eviction loops.
199 //
200 // This works out so a register without a cascade number is allowed to evict
201 // anything, and it can be evicted by anything.
202 unsigned Cascade = RA.getExtraInfo().getCascadeOrCurrentNext(VirtReg.reg());
203
205 for (MCRegUnit Unit : TRI->regunits(PhysReg)) {
206 LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, Unit);
207 // If there is 10 or more interferences, chances are one is heavier.
208 const auto &Interferences = Q.interferingVRegs(EvictInterferenceCutoff);
209 if (Interferences.size() >= EvictInterferenceCutoff)
210 return false;
211
212 // Check if any interfering live range is heavier than MaxWeight.
213 for (const LiveInterval *Intf : reverse(Interferences)) {
214 assert(Intf->reg().isVirtual() &&
215 "Only expecting virtual register interference from query");
216
217 // Do not allow eviction of a virtual register if we are in the middle
218 // of last-chance recoloring and this virtual register is one that we
219 // have scavenged a physical register for.
220 if (FixedRegisters.count(Intf->reg()))
221 return false;
222
223 // Never evict spill products. They cannot split or spill.
224 if (RA.getExtraInfo().getStage(*Intf) == RS_Done)
225 return false;
226 // Once a live range becomes small enough, it is urgent that we find a
227 // register for it. This is indicated by an infinite spill weight. These
228 // urgent live ranges get to evict almost anything.
229 //
230 // Also allow urgent evictions of unspillable ranges from a strictly
231 // larger allocation order.
232 bool Urgent =
233 !VirtReg.isSpillable() &&
234 (Intf->isSpillable() ||
237 MRI->getRegClass(Intf->reg())));
238 // Only evict older cascades or live ranges without a cascade.
239 unsigned IntfCascade = RA.getExtraInfo().getCascade(Intf->reg());
240 if (Cascade == IntfCascade)
241 return false;
242
243 if (Cascade < IntfCascade) {
244 if (!Urgent)
245 return false;
246 // We permit breaking cascades for urgent evictions. It should be the
247 // last resort, though, so make it really expensive.
248 Cost.BrokenHints += 10;
249 }
250 // Would this break a satisfied hint?
251 bool BreaksHint = VRM->hasPreferredPhys(Intf->reg());
252 // Update eviction cost.
253 Cost.BrokenHints += BreaksHint;
254 Cost.MaxWeight = std::max(Cost.MaxWeight, Intf->weight());
255 // Abort if this would be too expensive.
256 if (!(Cost < MaxCost))
257 return false;
258 if (Urgent)
259 continue;
260 // Apply the eviction policy for non-urgent evictions.
261 if (!shouldEvict(VirtReg, IsHint, *Intf, BreaksHint))
262 return false;
263 // If !MaxCost.isMax(), then we're just looking for a cheap register.
264 // Evicting another local live range in this case could lead to suboptimal
265 // coloring.
266 if (!MaxCost.isMax() && IsLocal && LIS->intervalIsInOneMBB(*Intf) &&
267 (!EnableLocalReassign || !canReassign(*Intf, PhysReg))) {
268 return false;
269 }
270 }
271 }
272 MaxCost = Cost;
273 return true;
274}
275
276MCRegister DefaultEvictionAdvisor::tryFindEvictionCandidate(
277 const LiveInterval &VirtReg, const AllocationOrder &Order,
278 uint8_t CostPerUseLimit, const SmallVirtRegSet &FixedRegisters) const {
279 // Keep track of the cheapest interference seen so far.
280 EvictionCost BestCost;
281 BestCost.setMax();
282 MCRegister BestPhys;
283 auto MaybeOrderLimit = getOrderLimit(VirtReg, Order, CostPerUseLimit);
284 if (!MaybeOrderLimit)
286 unsigned OrderLimit = *MaybeOrderLimit;
287
288 // When we are just looking for a reduced cost per use, don't break any
289 // hints, and only evict smaller spill weights.
290 if (CostPerUseLimit < uint8_t(~0u)) {
291 BestCost.BrokenHints = 0;
292 BestCost.MaxWeight = VirtReg.weight();
293 }
294
295 for (auto I = Order.begin(), E = Order.getOrderLimitEnd(OrderLimit); I != E;
296 ++I) {
297 MCRegister PhysReg = *I;
298 assert(PhysReg);
299 if (!canAllocatePhysReg(CostPerUseLimit, PhysReg) ||
300 !canEvictInterferenceBasedOnCost(VirtReg, PhysReg, false, BestCost,
301 FixedRegisters))
302 continue;
303
304 // Best so far.
305 BestPhys = PhysReg;
306
307 // Stop if the hint can be used.
308 if (I.isHint())
309 break;
310 }
311 return BestPhys;
312}
unsigned const MachineRegisterInfo * MRI
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
Definition: CommandLine.h:686
#define LLVM_DEBUG(X)
Definition: Debug.h:101
Live Register Matrix
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned const TargetRegisterInfo * TRI
Module.h This file contains the declarations for the Module class.
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
static cl::opt< bool > EnableLocalReassignment("enable-local-reassign", cl::Hidden, cl::desc("Local reassignment can yield better allocation decisions, but " "may be compile time intensive"), cl::init(false))
static cl::opt< RegAllocEvictionAdvisorAnalysis::AdvisorMode > Mode("regalloc-enable-advisor", cl::Hidden, cl::init(RegAllocEvictionAdvisorAnalysis::AdvisorMode::Default), cl::desc("Enable regalloc advisor mode"), cl::values(clEnumValN(RegAllocEvictionAdvisorAnalysis::AdvisorMode::Default, "default", "Default"), clEnumValN(RegAllocEvictionAdvisorAnalysis::AdvisorMode::Release, "release", "precompiled"), clEnumValN(RegAllocEvictionAdvisorAnalysis::AdvisorMode::Development, "development", "for training")))
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI optimize exec mask operations pre RA
Iterator getOrderLimitEnd(unsigned OrderLimit) const
Iterator begin() const
Query interferences between a single live virtual register and a live interval union.
const SmallVectorImpl< const LiveInterval * > & interferingVRegs(unsigned MaxInterferingRegs=std::numeric_limits< unsigned >::max())
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:687
float weight() const
Definition: LiveInterval.h:719
Register reg() const
Definition: LiveInterval.h:718
bool isSpillable() const
isSpillable - Can this interval be spilled?
Definition: LiveInterval.h:826
MachineBasicBlock * intervalIsInOneMBB(const LiveInterval &LI) const
If LI is confined to a single basic block, return a pointer to that block.
bool empty() const
Definition: LiveInterval.h:382
LiveIntervalUnion::Query & query(const LiveRange &LR, MCRegister RegUnit)
Query a line of the assigned virtual register matrix directly.
@ IK_VirtReg
Virtual register interference.
Definition: LiveRegMatrix.h:90
InterferenceKind checkInterference(const LiveInterval &VirtReg, MCRegister PhysReg)
Check for interference before assigning VirtReg to PhysReg.
iterator_range< MCRegUnitIterator > regunits(MCRegister Reg) const
Returns an iterator range over all regunits for Reg.
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:33
static constexpr unsigned NoRegister
Definition: MCRegister.h:52
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:94
virtual bool doInitialization(Module &)
doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...
Definition: Pass.h:119
LiveRangeStage getStage(Register Reg) const
unsigned getCascade(Register Reg) const
unsigned getCascadeOrCurrentNext(Register Reg) const
const ExtraRegInfo & getExtraInfo() const
ImmutableAnalysis abstraction for fetching the Eviction Advisor.
virtual std::unique_ptr< RegAllocEvictionAdvisor > getAdvisor(const MachineFunction &MF, const RAGreedy &RA)=0
Get an advisor for the given context (i.e. machine function, etc)
const TargetRegisterInfo *const TRI
std::optional< unsigned > getOrderLimit(const LiveInterval &VirtReg, const AllocationOrder &Order, unsigned CostPerUseLimit) const
MachineRegisterInfo *const MRI
const RegisterClassInfo & RegClassInfo
RegAllocEvictionAdvisor(const RegAllocEvictionAdvisor &)=delete
bool canReassign(const LiveInterval &VirtReg, MCRegister FromReg) const
const bool EnableLocalReassign
Run or not the local reassignment heuristic.
bool canAllocatePhysReg(unsigned CostPerUseLimit, MCRegister PhysReg) const
unsigned getNumAllocatableRegs(const TargetRegisterClass *RC) const
getNumAllocatableRegs - Returns the number of actually allocatable registers in RC in the current fun...
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:166
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
bool hasPreferredPhys(Register VirtReg) const
returns true if VirtReg is assigned to its preferred physreg.
Definition: VirtRegMap.cpp:109
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
Definition: CommandLine.h:711
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:419
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
@ RS_Spill
Live range will be spilled. No more splitting will be attempted.
@ RS_Done
There is nothing more we can do to this live range.
Pass * callDefaultCtor< RegAllocEvictionAdvisorAnalysis >()
Specialization for the API used by the analysis infrastructure to create an instance of the eviction ...
RegAllocEvictionAdvisorAnalysis * createReleaseModeAdvisor()
RegAllocEvictionAdvisorAnalysis * createDevelopmentModeAdvisor()
cl::opt< unsigned > EvictInterferenceCutoff
InstructionCost Cost
Cost of evicting interference - used by default advisor, and the eviction chain heuristic in RegAlloc...
unsigned BrokenHints
Total number of broken hints.
float MaxWeight
Maximum spill weight evicted.
void setBrokenHints(unsigned NHints)