1//===---------------------- AMDGPUNextUseAnalysis.h ----------------------===//
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 implements Next Use Analysis.
10//
11// For each register it goes over all uses and returns the estimated distance of
12// the nearest use. This will be used for selecting which registers to spill
13// before register allocation.
14//
15// This is based on ideas from the paper:
16// "Register Spilling and Live-Range Splitting for SSA-Form Programs"
17// Matthias Braun and Sebastian Hack, CC'09
18//
19//===----------------------------------------------------------------------===//
20
21#ifndef LLVM_LIB_TARGET_AMDGPU_AMDGPUNEXTUSEANALYSIS_H
22#define LLVM_LIB_TARGET_AMDGPU_AMDGPUNEXTUSEANALYSIS_H
23
24#include "SIInstrInfo.h"
25#include "SIRegisterInfo.h"
26#include "llvm/CodeGen/LiveIntervals.h"
27#include "llvm/CodeGen/MachineLoopInfo.h"
28#include "llvm/CodeGen/MachineRegisterInfo.h"
29#include "llvm/CodeGen/TargetRegisterInfo.h"
30#include "llvm/IR/PassManager.h"
31#include "llvm/Support/Format.h"
32#include "llvm/Support/JSON.h"
33#include <limits>
34#include <optional>
35
36namespace llvm {
37
38class AMDGPUNextUseAnalysisImpl;
39
40//==============================================================================
41// NextUseDistance - Represents a distance in the next-use analysis. Currently
42// wraps a 64-bit int with special encoding for loop depth and unreachable
43// distances.
44//==============================================================================
45class NextUseDistance {
46public:
47 constexpr static NextUseDistance unreachable() {
48 return NextUseDistance(std::numeric_limits<int64_t>::max());
49 }
50
51 constexpr static NextUseDistance fromSize(unsigned Size, unsigned Depth) {
52 return NextUseDistance(Size).applyLoopWeight(Depth);
53 }
54
55 constexpr NextUseDistance(unsigned V) : Value(V) {}
56 constexpr NextUseDistance(int V) : Value(V) {}
57 constexpr NextUseDistance(const NextUseDistance &B) : Value(B.Value) {}
58
59 constexpr bool isUnreachable() const { return *this == unreachable(); }
60 constexpr bool isReachable() const { return !isUnreachable(); }
61
62 //----------------------------------------------------------------------------
63 // Assignment
64 //----------------------------------------------------------------------------
65 constexpr NextUseDistance &operator=(const NextUseDistance &B) {
66 Value = B.Value;
67 return *this;
68 }
69
70 constexpr NextUseDistance &operator=(unsigned V) {
71 Value = V;
72 return *this;
73 }
74
75 constexpr NextUseDistance &operator=(int V) {
76 Value = V;
77 return *this;
78 }
79
80 //----------------------------------------------------------------------------
81 // Arithmetic operators
82 //----------------------------------------------------------------------------
83 constexpr NextUseDistance &operator+=(const NextUseDistance &B) {
84 Value += B.Value;
85 return *this;
86 }
87
88 constexpr NextUseDistance &operator-=(const NextUseDistance &B) {
89 Value -= B.Value;
90 return *this;
91 }
92
93 constexpr NextUseDistance operator-() const {
94 return NextUseDistance(-Value);
95 }
96
97 constexpr NextUseDistance applyLoopWeight() const {
98 NextUseDistance W = fromLoopDepth(Depth: 1);
99 if (W.isUnreachable())
100 return unreachable();
101 constexpr int64_t MaxVal = std::numeric_limits<int64_t>::max();
102 if (Value != 0 && W.Value > MaxVal / Value)
103 return unreachable();
104 return NextUseDistance(Value * W.Value);
105 }
106
107 //----------------------------------------------------------------------------
108 // Comparison operators
109 //----------------------------------------------------------------------------
110 constexpr bool operator<(const NextUseDistance &B) const {
111 return Value < B.Value;
112 }
113
114 constexpr bool operator>(const NextUseDistance &B) const {
115 return Value > B.Value;
116 }
117
118 constexpr bool operator<=(const NextUseDistance &B) const {
119 return Value <= B.Value;
120 }
121
122 constexpr bool operator>=(const NextUseDistance &B) const {
123 return Value >= B.Value;
124 }
125
126 constexpr bool operator==(const NextUseDistance &B) const {
127 return Value == B.Value;
128 }
129
130 constexpr bool operator!=(const NextUseDistance &B) const {
131 return Value != B.Value;
132 }
133
134 //----------------------------------------------------------------------------
135 // Debugging
136 //----------------------------------------------------------------------------
137 format_object<int64_t> fmt() const { return format(Fmt: "%ld", Vals: Value); }
138
139 void print(raw_ostream &OS) const {
140 if (isUnreachable())
141 OS << "<unreachable>";
142 else
143 OS << fmt();
144 }
145
146 json::Value toJsonValue() const {
147 if (isUnreachable())
148 return "<unreachable>";
149 return Value;
150 }
151
152 std::string toString() const {
153 std::string Str;
154 llvm::raw_string_ostream OS(Str);
155 print(OS);
156 return OS.str();
157 }
158
159 constexpr int64_t getRawValue() const { return Value; }
160 using RawValueType = int64_t;
161
162private:
163 friend class AMDGPUNextUseAnalysisImpl;
164 int64_t Value;
165 constexpr explicit NextUseDistance(int64_t V) : Value(V) {}
166
167 constexpr static NextUseDistance fromLoopDepth(unsigned Depth) {
168 const unsigned Shift = 7 * Depth;
169
170 // Saturate?
171 if (Shift >= 63)
172 return unreachable();
173
174 // This implementation is multiplicative (f(a+b) == f(a) * f(b)) which we
175 // take advantage of below in applyLoopWeight(Depth).
176 return NextUseDistance(int64_t(1) << Shift);
177 }
178
179 // Semantically: apply fromLoopDepth(1) Depth times (compositional).
180 //
181 // Optimized to take advantage of multiplicative implementation of
182 // fromLoopDepth - a single multiply by fromLoopDepth(Depth) gives the same
183 // result. If fromLoopDepth is changed to a non-multiplicative formula,
184 // replace the body with something like:
185 //
186 // NextUseDistance D = *this;
187 // for (unsigned I = 0; I < Depth; ++I) {
188 // D = D.applyLoopWeight();
189 // if (D.isUnreachable())
190 // return unreachable();
191 // }
192 // return D;
193 //
194 constexpr NextUseDistance applyLoopWeight(unsigned Depth) const {
195 if (!Depth)
196 return *this;
197 NextUseDistance W = fromLoopDepth(Depth);
198 if (W.isUnreachable())
199 return unreachable();
200 constexpr int64_t MaxVal = std::numeric_limits<int64_t>::max();
201 if (Value != 0 && W.Value > MaxVal / Value)
202 return unreachable();
203 return NextUseDistance(Value * W.Value);
204 }
205};
206
207constexpr inline NextUseDistance operator+(NextUseDistance A,
208 const NextUseDistance &B) {
209 return A += B;
210}
211
212constexpr inline NextUseDistance operator-(NextUseDistance A,
213 const NextUseDistance &B) {
214 return A -= B;
215}
216
217constexpr inline NextUseDistance min(NextUseDistance A, NextUseDistance B) {
218 return A < B ? A : B;
219}
220
221constexpr inline NextUseDistance max(NextUseDistance A, NextUseDistance B) {
222 return A > B ? A : B;
223}
224
225//==============================================================================
226// AMDGPUNextUseAnalysis - Provides next-use distances for live registers or
227// sub-registers at a given MachineInstruction suitable for making spilling
228// decisions.
229//==============================================================================
230class AMDGPUNextUseAnalysis {
231 friend class AMDGPUNextUseAnalysisLegacyPass;
232 friend class AMDGPUNextUseAnalysisPrinterLegacyPass;
233 friend class AMDGPUNextUseAnalysisPass;
234 friend class AMDGPUNextUseAnalysisPrinterPass;
235
236 std::unique_ptr<AMDGPUNextUseAnalysisImpl> Impl;
237
238 AMDGPUNextUseAnalysis(const MachineFunction *, const MachineLoopInfo *);
239
240public:
241 AMDGPUNextUseAnalysis(AMDGPUNextUseAnalysis &&Other);
242 ~AMDGPUNextUseAnalysis();
243
244 AMDGPUNextUseAnalysis &operator=(AMDGPUNextUseAnalysis &&Other);
245
246 // Configuration flags for controlling the distance model. Defaults correspond
247 // to the Graphics preset.
248 struct Config {
249 // Count PHI instructions as having non-zero cost (distance and block
250 // size). When false, all PHIs share ID 0 and don't contribute to block
251 // size.
252 bool CountPhis = true;
253
254 // Restrict inter-block distances to forward-reachable paths only.
255 // When false, distances through back-edges are also considered.
256 bool ForwardOnly = true;
257
258 // Model PHI uses as belonging to their incoming edge's block, and apply
259 // full loop-aware reachability filtering including intermediate-def
260 // checks. When false, a simple same-block / forward-reachable check is
261 // used.
262 bool PreciseUseModeling = false;
263
264 // Promote uses that are inside a loop not yet entered or inside a directly
265 // nested inner loop to the end of that loop's preheader. This models the
266 // assumption that a spilled value will be reloaded at the preheader rather
267 // than at the actual use site. When false, direct shortest distance to the
268 // use is used instead.
269 bool PromoteToPreheader = false;
270
271 /// Named presets. See note in AMDGPUNextUseAnalysis.cpp associated with
272 /// 'amdgpu-next-use-analysis-config' regarding the historical context for
273 /// these.
274 static Config Graphics() { return {}; }
275 static Config Compute() {
276 Config Cfg;
277 Cfg.CountPhis = false;
278 Cfg.ForwardOnly = false;
279 Cfg.PreciseUseModeling = true;
280 Cfg.PromoteToPreheader = true;
281 return Cfg;
282 }
283 };
284
285 Config getConfig() const;
286 void setConfig(Config);
287
288 void getReachableUses(Register LiveReg, LaneBitmask LaneMask,
289 const MachineInstr &MI,
290 SmallVector<const MachineOperand *> &Uses) const;
291
292 /// \Returns the shortest next-use distance from \p CurMI for \p LiveReg.
293 NextUseDistance
294 getShortestDistance(Register LiveReg, const MachineInstr &CurMI,
295 const SmallVector<const MachineOperand *> &Uses,
296 const MachineOperand **ShortestUseOut = nullptr,
297 SmallVector<NextUseDistance> *Distances = nullptr) const;
298
299 struct UseDistancePair {
300 const MachineOperand *Use = nullptr;
301 NextUseDistance Dist = 0;
302 UseDistancePair() = default;
303 UseDistancePair(const MachineOperand *Use, NextUseDistance Dist)
304 : Use(Use), Dist(Dist) {}
305 };
306
307 void getNextUseDistances(const DenseMap<unsigned, LaneBitmask> &LiveRegs,
308 const MachineInstr &MI, UseDistancePair &Furthest,
309 UseDistancePair *FurthestSubreg = nullptr,
310 DenseMap<const MachineOperand *, UseDistancePair>
311 *RelevantUses = nullptr) const;
312};
313
314//==============================================================================
315// AMDGPUNextUseAnalysisLegacyPass - Legacy and New pass wrapper around
316// AMDGPUNextUseAnalysis
317//==============================================================================
318class AMDGPUNextUseAnalysisLegacyPass : public MachineFunctionPass {
319
320public:
321 static char ID;
322
323 AMDGPUNextUseAnalysisLegacyPass();
324
325 AMDGPUNextUseAnalysis &getNextUseAnalysis() { return *NUA; }
326 const AMDGPUNextUseAnalysis &getNextUseAnalysis() const { return *NUA; }
327 StringRef getPassName() const override;
328
329protected:
330 bool runOnMachineFunction(MachineFunction &) override;
331 void getAnalysisUsage(AnalysisUsage &AU) const override;
332
333private:
334 std::unique_ptr<AMDGPUNextUseAnalysis> NUA;
335};
336
337class AMDGPUNextUseAnalysisPass
338 : public AnalysisInfoMixin<AMDGPUNextUseAnalysisPass> {
339 friend AnalysisInfoMixin<AMDGPUNextUseAnalysisPass>;
340 static AnalysisKey Key;
341
342public:
343 using Result = AMDGPUNextUseAnalysis;
344 Result run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM);
345};
346
347//==============================================================================
348// AMDGPUNextUseAnalysisPrinterLegacyPass - Legacy Pass for printing
349// AMDGPUNextUseAnalysis results as JSON.
350//==============================================================================
351class AMDGPUNextUseAnalysisPrinterLegacyPass : public MachineFunctionPass {
352
353public:
354 static char ID;
355
356 AMDGPUNextUseAnalysisPrinterLegacyPass();
357
358 StringRef getPassName() const override;
359
360protected:
361 bool runOnMachineFunction(MachineFunction &) override;
362 void getAnalysisUsage(AnalysisUsage &AU) const override;
363};
364
365class AMDGPUNextUseAnalysisPrinterPass
366 : public RequiredPassInfoMixin<AMDGPUNextUseAnalysisPrinterPass> {
367 raw_ostream &OS;
368
369public:
370 explicit AMDGPUNextUseAnalysisPrinterPass(raw_ostream &OS) : OS(OS) {}
371 PreservedAnalyses run(MachineFunction &MF,
372 MachineFunctionAnalysisManager &MFAM);
373};
374
375} // namespace llvm
376#endif // LLVM_LIB_TARGET_AMDGPU_AMDGPUNEXTUSEANALYSIS_H
377