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