LLVM 20.0.0git
RegAllocEvictionAdvisor.h
Go to the documentation of this file.
1//===- RegAllocEvictionAdvisor.h - Interference resolution ------*- C++ -*-===//
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#ifndef LLVM_CODEGEN_REGALLOCEVICTIONADVISOR_H
10#define LLVM_CODEGEN_REGALLOCEVICTIONADVISOR_H
11
12#include "llvm/ADT/ArrayRef.h"
13#include "llvm/ADT/SmallSet.h"
14#include "llvm/ADT/StringRef.h"
16#include "llvm/Config/llvm-config.h"
17#include "llvm/MC/MCRegister.h"
18#include "llvm/Pass.h"
19
20namespace llvm {
21class AllocationOrder;
22class LiveInterval;
23class LiveIntervals;
24class LiveRegMatrix;
25class MachineFunction;
26class MachineRegisterInfo;
27class RegisterClassInfo;
28class TargetRegisterInfo;
29class VirtRegMap;
30
32
33// Live ranges pass through a number of stages as we try to allocate them.
34// Some of the stages may also create new live ranges:
35//
36// - Region splitting.
37// - Per-block splitting.
38// - Local splitting.
39// - Spilling.
40//
41// Ranges produced by one of the stages skip the previous stages when they are
42// dequeued. This improves performance because we can skip interference checks
43// that are unlikely to give any results. It also guarantees that the live
44// range splitting algorithm terminates, something that is otherwise hard to
45// ensure.
47 /// Newly created live range that has never been queued.
49
50 /// Only attempt assignment and eviction. Then requeue as RS_Split.
52
53 /// Attempt live range splitting if assignment is impossible.
55
56 /// Attempt more aggressive live range splitting that is guaranteed to make
57 /// progress. This is used for split products that may not be making
58 /// progress.
60
61 /// Live range will be spilled. No more splitting will be attempted.
63
64 /// Live range is in memory. Because of other evictions, it might get moved
65 /// in a register in the end.
67
68 /// There is nothing more we can do to this live range. Abort compilation
69 /// if it can't be assigned.
71};
72
73/// Cost of evicting interference - used by default advisor, and the eviction
74/// chain heuristic in RegAllocGreedy.
75// FIXME: this can be probably made an implementation detail of the default
76// advisor, if the eviction chain logic can be refactored.
78 unsigned BrokenHints = 0; ///< Total number of broken hints.
79 float MaxWeight = 0; ///< Maximum spill weight evicted.
80
81 EvictionCost() = default;
82
83 bool isMax() const { return BrokenHints == ~0u; }
84
85 void setMax() { BrokenHints = ~0u; }
86
87 void setBrokenHints(unsigned NHints) { BrokenHints = NHints; }
88
89 bool operator<(const EvictionCost &O) const {
90 return std::tie(BrokenHints, MaxWeight) <
91 std::tie(O.BrokenHints, O.MaxWeight);
92 }
93};
94
95/// Interface to the eviction advisor, which is responsible for making a
96/// decision as to which live ranges should be evicted (if any).
97class RAGreedy;
99public:
102 virtual ~RegAllocEvictionAdvisor() = default;
103
104 /// Find a physical register that can be freed by evicting the FixedRegisters,
105 /// or return NoRegister. The eviction decision is assumed to be correct (i.e.
106 /// no fixed live ranges are evicted) and profitable.
108 const LiveInterval &VirtReg, const AllocationOrder &Order,
109 uint8_t CostPerUseLimit, const SmallVirtRegSet &FixedRegisters) const = 0;
110
111 /// Find out if we can evict the live ranges occupying the given PhysReg,
112 /// which is a hint (preferred register) for VirtReg.
113 virtual bool
115 const SmallVirtRegSet &FixedRegisters) const = 0;
116
117 /// Returns true if the given \p PhysReg is a callee saved register and has
118 /// not been used for allocation yet.
119 bool isUnusedCalleeSavedReg(MCRegister PhysReg) const;
120
121protected:
123
124 bool canReassign(const LiveInterval &VirtReg, MCRegister FromReg) const;
125
126 // Get the upper limit of elements in the given Order we need to analize.
127 // TODO: is this heuristic, we could consider learning it.
128 std::optional<unsigned> getOrderLimit(const LiveInterval &VirtReg,
129 const AllocationOrder &Order,
130 unsigned CostPerUseLimit) const;
131
132 // Determine if it's worth trying to allocate this reg, given the
133 // CostPerUseLimit
134 // TODO: this is a heuristic component we could consider learning, too.
135 bool canAllocatePhysReg(unsigned CostPerUseLimit, MCRegister PhysReg) const;
136
138 const RAGreedy &RA;
146
147 /// Run or not the local reassignment heuristic. This information is
148 /// obtained from the TargetSubtargetInfo.
150};
151
152/// ImmutableAnalysis abstraction for fetching the Eviction Advisor. We model it
153/// as an analysis to decouple the user from the implementation insofar as
154/// dependencies on other analyses goes. The motivation for it being an
155/// immutable pass is twofold:
156/// - in the ML implementation case, the evaluator is stateless but (especially
157/// in the development mode) expensive to set up. With an immutable pass, we set
158/// it up once.
159/// - in the 'development' mode ML case, we want to capture the training log
160/// during allocation (this is a log of features encountered and decisions
161/// made), and then measure a score, potentially a few steps after allocation
162/// completes. So we need the properties of an immutable pass to keep the logger
163/// state around until we can make that measurement.
164///
165/// Because we need to offer additional services in 'development' mode, the
166/// implementations of this analysis need to implement RTTI support.
168public:
169 enum class AdvisorMode : int { Default, Release, Development };
170
172 : ImmutablePass(ID), Mode(Mode){};
173 static char ID;
174
175 /// Get an advisor for the given context (i.e. machine function, etc)
176 virtual std::unique_ptr<RegAllocEvictionAdvisor>
177 getAdvisor(const MachineFunction &MF, const RAGreedy &RA) = 0;
178 AdvisorMode getAdvisorMode() const { return Mode; }
179 virtual void logRewardIfNeeded(const MachineFunction &MF,
180 llvm::function_ref<float()> GetReward){};
181
182protected:
183 // This analysis preserves everything, and subclasses may have additional
184 // requirements.
185 void getAnalysisUsage(AnalysisUsage &AU) const override {
186 AU.setPreservesAll();
187 }
188
189private:
190 StringRef getPassName() const override;
191 const AdvisorMode Mode;
192};
193
194/// Specialization for the API used by the analysis infrastructure to create
195/// an instance of the eviction advisor.
197
198RegAllocEvictionAdvisorAnalysis *createReleaseModeAdvisor();
199
201
202// TODO: move to RegAllocEvictionAdvisor.cpp when we move implementation
203// out of RegAllocGreedy.cpp
205public:
208
209private:
210 MCRegister tryFindEvictionCandidate(const LiveInterval &,
211 const AllocationOrder &, uint8_t,
212 const SmallVirtRegSet &) const override;
213 bool canEvictHintInterference(const LiveInterval &, MCRegister,
214 const SmallVirtRegSet &) const override;
215 bool canEvictInterferenceBasedOnCost(const LiveInterval &, MCRegister, bool,
216 EvictionCost &,
217 const SmallVirtRegSet &) const;
218 bool shouldEvict(const LiveInterval &A, bool, const LiveInterval &B,
219 bool) const;
220};
221} // namespace llvm
222
223#endif // LLVM_CODEGEN_REGALLOCEVICTIONADVISOR_H
aarch64 AArch64 CCMP Pass
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
SI optimize exec mask operations pre RA
This file defines the SmallSet class.
Represent the analysis usage information of a pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
DefaultEvictionAdvisor(const MachineFunction &MF, const RAGreedy &RA)
ImmutablePass class - This class is used to provide information that does not need to be run.
Definition: Pass.h:281
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:687
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:33
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
ImmutableAnalysis abstraction for fetching the Eviction Advisor.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
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)
virtual void logRewardIfNeeded(const MachineFunction &MF, llvm::function_ref< float()> GetReward)
const TargetRegisterInfo *const TRI
virtual bool canEvictHintInterference(const LiveInterval &VirtReg, MCRegister PhysReg, const SmallVirtRegSet &FixedRegisters) const =0
Find out if we can evict the live ranges occupying the given PhysReg, which is a hint (preferred regi...
RegAllocEvictionAdvisor(RegAllocEvictionAdvisor &&)=delete
std::optional< unsigned > getOrderLimit(const LiveInterval &VirtReg, const AllocationOrder &Order, unsigned CostPerUseLimit) const
virtual MCRegister tryFindEvictionCandidate(const LiveInterval &VirtReg, const AllocationOrder &Order, uint8_t CostPerUseLimit, const SmallVirtRegSet &FixedRegisters) const =0
Find a physical register that can be freed by evicting the FixedRegisters, or return NoRegister.
const ArrayRef< uint8_t > RegCosts
MachineRegisterInfo *const MRI
const RegisterClassInfo & RegClassInfo
bool isUnusedCalleeSavedReg(MCRegister PhysReg) const
Returns true if the given PhysReg is a callee saved register and has not been used for allocation yet...
RegAllocEvictionAdvisor(const RegAllocEvictionAdvisor &)=delete
bool canReassign(const LiveInterval &VirtReg, MCRegister FromReg) const
const bool EnableLocalReassign
Run or not the local reassignment heuristic.
virtual ~RegAllocEvictionAdvisor()=default
bool canAllocatePhysReg(unsigned CostPerUseLimit, MCRegister PhysReg) const
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:132
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:51
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
An efficient, type-erasing, non-owning reference to a callable.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ RS_Split2
Attempt more aggressive live range splitting that is guaranteed to make progress.
@ RS_Spill
Live range will be spilled. No more splitting will be attempted.
@ RS_Split
Attempt live range splitting if assignment is impossible.
@ RS_New
Newly created live range that has never been queued.
@ RS_Done
There is nothing more we can do to this live range.
@ RS_Assign
Only attempt assignment and eviction. Then requeue as RS_Split.
@ RS_Memory
Live range is in memory.
Pass * callDefaultCtor< RegAllocEvictionAdvisorAnalysis >()
Specialization for the API used by the analysis infrastructure to create an instance of the eviction ...
RegAllocEvictionAdvisorAnalysis * createReleaseModeAdvisor()
RegAllocEvictionAdvisorAnalysis * createDevelopmentModeAdvisor()
Cost of evicting interference - used by default advisor, and the eviction chain heuristic in RegAlloc...
EvictionCost()=default
unsigned BrokenHints
Total number of broken hints.
bool operator<(const EvictionCost &O) const
float MaxWeight
Maximum spill weight evicted.
void setBrokenHints(unsigned NHints)