1//===-- GCNRematStrategy.h - Rematerialization strategy -*- 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/// \file
10/// Rematerialization strategy, based on the target-independent rematerializer.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_LIB_TARGET_AMDGPU_GCNREMATSTRATEGY_H
15#define LLVM_LIB_TARGET_AMDGPU_GCNREMATSTRATEGY_H
16
17#include "GCNRegPressure.h"
18#include "SIMachineFunctionInfo.h"
19#include "llvm/ADT/ArrayRef.h"
20#include "llvm/CodeGen/Rematerializer.h"
21
22namespace llvm {
23
24/// Rematerializes registers across code regions to achieve register pressure
25/// targets. The strategy updates region boundaries and live-ins/live-outs as it
26/// rematerializes. It uses the target independent rematerializers to expose
27/// rematerializable registers and perform rematerializations.
28///
29/// The strategy only supports rematerializing registers that meet all of the
30/// following constraints.
31/// 1. The register is virtual and has a single defining instruction.
32/// 2. The single defining instruction is either deemed rematerializable by the
33/// target-independent logic, or if not, has no non-constant and
34/// non-ignorable physical register use.
35/// 3 The register has no virtual register use whose live range would be
36/// extended by the rematerialization.
37/// 4. The register has at least one user outside its defining region. If
38/// rematerialized, one copy is made per using region and the original
39/// register stays if the defining region has users.
40/// 5. The register is not used by or using another register that is going to be
41/// rematerialized.
42class GCNRematStrategy {
43 using RegionBoundaries = Rematerializer::RegionBoundaries;
44 using RegisterIdx = Rematerializer::RegisterIdx;
45
46public:
47 /// Creates a strategy that can rematerialize across \p Regions whose live-ins
48 /// \p LiveIns and live-outs \p LiveOuts are provided. The underlying
49 /// rematerializer is created and initialized.
50 GCNRematStrategy(MachineFunction &MF,
51 MutableArrayRef<RegionBoundaries> Regions,
52 MutableArrayRef<GCNRPTracker::LiveRegSet> LiveIns,
53 MutableArrayRef<GCNRPTracker::LiveRegSet> LiveOuts,
54 LiveIntervals &LIS, const MachineBlockFrequencyInfo &MBFI)
55 : Regions(Regions, LiveIns, LiveOuts, LIS, MBFI, MF.getRegInfo()),
56 Remater(MF, Regions, LIS), MF(MF), MRI(MF.getRegInfo()), LIS(LIS) {}
57
58 /// Rematerializes with the goal of reducing the maximum pressure in all \ref
59 /// Regions to \p MaxSGPRs SGPRs and \p MaxVGPRs VGPRs. \p SpillReduction
60 /// indicates whether that register pressure target allows to reduce spilling,
61 /// which influences rematerialization decisions. Regions which are
62 /// rematerialized from/into/over have their corresponding index set in \p
63 /// AffectedRegions. When not null, \p MaxPressure provides initial maximum
64 /// pressure for all regions and contains updated maximum pressures when the
65 /// function returns.
66 void rematerializeFor(unsigned MaxSGPRs, unsigned MaxVGPRs,
67 bool SpillReduction, BitVector &AffectedRegions,
68 MutableArrayRef<GCNRegPressure> *MaxPressure = nullptr);
69
70 /// Starts recording rematerializations for eventual rollback.
71 void startRecordingRemats() {
72 assert(!Recorder && "recorder already defined");
73 Recorder = std::make_unique<RematRecorder>(args&: Remater);
74 }
75
76 /// Stops recording rematerializations and clears all recorded ones.
77 void clearRecordedRemats() {
78 assert(Recorder && "recorder not defined");
79 Remater.removeListener(Listen: &Recorder->Listener);
80 Recorder.reset(p: nullptr);
81 }
82
83 /// Rolls back all recorded rematerializations.
84 void rollbackRecordedRemats();
85
86private:
87 /// Groups information about code regions to rematerialize across.
88 struct RematRegions {
89 /// Boundaries of regions across which the strategy rematerializes.
90 /// FIXME: the rematerializer updates them when necessary, but the strategy
91 /// should be responsible for that.
92 ArrayRef<RegionBoundaries> Bounds;
93
94 RematRegions(ArrayRef<RegionBoundaries> Regions,
95 MutableArrayRef<GCNRPTracker::LiveRegSet> LiveIns,
96 MutableArrayRef<GCNRPTracker::LiveRegSet> LiveOuts,
97 LiveIntervals &LIS, const MachineBlockFrequencyInfo &MBFI,
98 const MachineRegisterInfo &MRI);
99
100 /// Returns the number of rematerialization regions.
101 unsigned size() const { return Bounds.size(); }
102
103 uint64_t getFrequency(unsigned RegionIdx) const {
104 return Frequencies[RegionIdx];
105 }
106
107 uint64_t getFrequencyOr(unsigned RegionIdx, uint64_t Default = 0) const {
108 uint64_t RegionFreq = Frequencies[RegionIdx];
109 return RegionFreq ? RegionFreq : Default;
110 }
111
112 uint64_t getFrequencyOrMax(unsigned RegionIdx) const {
113 return getFrequencyOr(RegionIdx, Default: MaxFreq);
114 }
115
116 uint64_t getFrequencyOrMin(unsigned RegionIdx) const {
117 return getFrequencyOr(RegionIdx, Default: MinFreq);
118 }
119
120 /// Returns up-to-date live-ins for region \p RegionIdx.
121 const GCNRPTracker::LiveRegSet &getLiveIns(unsigned RegionIdx) const {
122 assert(RegionIdx < size() && "out of bounds");
123 return LiveIns[RegionIdx];
124 }
125
126 /// Returns up-to-date live-outs for region \p RegionIdx.
127 const GCNRPTracker::LiveRegSet &getLiveOuts(unsigned RegionIdx) const {
128 assert(RegionIdx < size() && "out of bounds");
129 return LiveOuts[RegionIdx];
130 }
131
132 /// Computes the up-to-date maximum register pressure in \p RegionIdx.
133 GCNRegPressure computeMaxRegPressure(unsigned RegionIdx) const;
134
135 /// Removes register \p Reg from the live-ins of regions set in \p LiveIn
136 /// and the live-outs of regions set in \p LiveOut.
137 void removeFromLiveMaps(Register Reg, const BitVector &LiveIn,
138 const BitVector &LiveOut);
139
140 /// Adds register \p Reg with mask \p Mask to the live-ins of regions set in
141 /// \p LiveIn and the live-outs of regions set in \p LiveOut.
142 void addToLiveMaps(Register Reg, LaneBitmask Mask, const BitVector &LiveIn,
143 const BitVector &LiveOut);
144
145 private:
146 static const uint64_t FreqScaleFactor = 1024;
147
148 /// Current live-ins and live-outs for each region.
149 MutableArrayRef<GCNRPTracker::LiveRegSet> LiveIns, LiveOuts;
150 /// Scaled per-region execution frequencies. 0 when unknown.
151 SmallVector<uint64_t> Frequencies;
152 /// Scaled minimum and maximum observed frequencies.
153 uint64_t MinFreq, MaxFreq;
154
155 LiveIntervals &LIS;
156 const MachineRegisterInfo &MRI;
157 };
158
159 /// Tracks progress in reducing register pressure against a target.
160 struct RematTargets {
161 /// Register pressure targets for all regions.
162 SmallVector<GCNRPTarget> RPTargets;
163 /// Regions which are above the RP target.
164 BitVector ExcessRP;
165 /// Regions to rematerialize across.
166 const RematRegions &Regions;
167 /// Whether the register pressure target allows to reduce spilling.
168 const bool SpillReduction;
169
170 /// Sets a target \ref of maximum \p MaxSGPRs SGPRs and \p MaxVGPRs VGPRs
171 /// per region. \p SpillReduction indicates whether that register pressure
172 /// target allows to reduce spilling. When not null, \p MaxPressure provides
173 /// initial maximum pressure for all regions.
174 RematTargets(unsigned MaxSGPRs, unsigned MaxVGPRs, bool SpillReduction,
175 const MachineFunction &MF, const RematRegions &Regions,
176 ArrayRef<GCNRegPressure> *MaxPressure = nullptr);
177
178 /// Returns whether the RP target is thought to be achieved in all regions.
179 bool allAchieved() const { return ExcessRP.none(); }
180
181 /// In all regions set in \p UpdateRegions, saves pressure \p RPSave and
182 /// clear it as a target if its RP target has been reached.
183 void updateRPTargets(const BitVector &UpdateRegions,
184 const GCNRegPressure &RPSave);
185
186 /// Fully recomputes RP from the DAG in \p UpdateRegions. Among those
187 /// regions, sets again all targets that were optimistically marked as
188 /// satisfied but are actually not, and returns whether there were any such
189 /// regions.
190 bool updateAndVerifyRPTargets(const BitVector &UpdateRegions);
191
192#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
193 Printable print() const;
194#endif
195 };
196
197 /// A scored rematerialization candidate. Higher scores indicate more
198 /// beneficial rematerializations. A null score indicates the
199 /// rematerialization is not helpful to reduce RP in regions with excess RP.
200 struct RematCandidate {
201 /// The register index handle in the rematerializer.
202 RegisterIdx RegIdx;
203 /// Regions in which the register is live-in/live-out/live anywhere.
204 BitVector LiveIn, LiveOut, Live;
205 /// Subset of \ref Live regions in which the rematerialization is not
206 /// guaranteed to reduce RP (i.e., regions in which the register is not
207 /// live-through and unused).
208 BitVector UnpredictableRPSave;
209 /// Expected register pressure decrease induced by rematerializing this
210 /// candidate.
211 GCNRegPressure RPSave;
212
213 RematCandidate(RegisterIdx RegIdx, unsigned NumRegions)
214 : RegIdx(RegIdx), LiveIn(NumRegions), LiveOut(NumRegions),
215 Live(NumRegions), UnpredictableRPSave(NumRegions) {}
216
217 /// Initializes the candidate with state-independent characteristics.
218 /// This doesn't update the actual score (call \ref update for this).
219 /// Note: LiveIn/LiveOut must be pre-populated before calling this.
220 void init(const RematRegions &RF, const Rematerializer &Remater,
221 const MachineRegisterInfo &MRI);
222
223 /// Updates the rematerialization's score w.r.t. the current \p Targets.
224 void update(const RematTargets &Targets);
225
226 /// Determines whether this rematerialization may be beneficial in at
227 /// least one region with excess RP.
228 bool maybeBeneficial(const RematTargets &Targets) const;
229
230 /// Rematerializes the candidate using the \p Remater.
231 void rematerialize(Rematerializer &Remater) const;
232
233 /// Returns whether the current score is null, indicating the
234 /// rematerialization is useless.
235 bool hasNullScore() const { return !RegionImpact; }
236
237 /// Compare score components of non-null scores pair-wise. Scores
238 /// shouldn't be null (as defined by \ref hasNullScore).
239 bool operator<(const RematCandidate &O) const {
240 assert(!hasNullScore() && "this has null score");
241 assert(!O.hasNullScore() && "other has null score");
242 if (MaxFreq != O.MaxFreq)
243 return MaxFreq < O.MaxFreq;
244 if (FreqDiff != O.FreqDiff)
245 return FreqDiff < O.FreqDiff;
246 if (RegionImpact != O.RegionImpact)
247 return RegionImpact < O.RegionImpact;
248 // Break ties using register index handles. If the two registers are
249 // connected in some dependency DAG of rematerializable registers, this
250 // will tend to give a higher score to the register further from the
251 // dependency DAG's root. If the two registers are disconnected, this
252 // will give a higher score to the register with lower virtual register
253 // index. In general, within a region, this should prefer registers
254 // defined earlier that have longer live ranges in their defining region
255 // (since the registers we consider are always live-out in their
256 // defining region).
257 return RegIdx > O.RegIdx;
258 }
259
260#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
261 Printable print() const;
262#endif
263
264 private:
265 // The three members below are the scoring components, top to bottom from
266 // most important to least important when comparing candidates.
267
268 /// Frequency of impacted target region with highest known frequency. This
269 /// only matters when the strategy is trying to reduce spilling, so it is
270 /// always 0 when it is not.
271 uint64_t MaxFreq;
272 /// Frequency difference between defining and using regions. Negative
273 /// values indicate we are rematerializing to higher frequency regions;
274 /// positive values indicate the contrary.
275 int64_t FreqDiff;
276 /// Expected number of target regions impacted by the rematerialization,
277 /// scaled by the size of the register being rematerialized.
278 unsigned RegionImpact;
279 };
280
281 struct RematRecorder {
282 struct LiveMapUpdate {
283 /// The register index handle in the rematerializer.
284 RegisterIdx RegIdx;
285 /// Regions in which the original register was live-in or live-out.
286 BitVector LiveIn, LiveOut;
287
288 LiveMapUpdate(RegisterIdx RegIdx, const BitVector &LiveIn,
289 const BitVector &LiveOut)
290 : RegIdx(RegIdx), LiveIn(LiveIn), LiveOut(LiveOut) {}
291 };
292
293 /// Rematerializer listener which can rollback rematerializations.
294 Rollbacker Listener;
295 /// Registers removed from live-maps along with bitvectors indicationg the
296 /// regions in which they were live-ins and live-outs.
297 SmallVector<LiveMapUpdate> LiveMapUpdates;
298
299 /// Attaches the rollback listener to the rematerializer.
300 RematRecorder(Rematerializer &Remater) { Remater.addListener(Listen: &Listener); }
301 };
302
303 /// Code regions to rematerialize across. Region bounds are updated by the
304 /// rematerializer as necessary when rematerializations occur at region
305 /// boundaries.
306 RematRegions Regions;
307 /// Rematerializer, initialized with the same rematerialization regions as the
308 /// strategy.
309 Rematerializer Remater;
310 /// Candidates for rematerializations.
311 SmallVector<RematCandidate, 0> Candidates;
312 /// Whether candidates were already created, implying that the rematerializer
313 /// was also fully initialized.
314 bool CandidatesCreated = false;
315 /// When not null, records all rematerializations.
316 std::unique_ptr<RematRecorder> Recorder;
317
318 const MachineFunction &MF;
319 const MachineRegisterInfo &MRI;
320 LiveIntervals &LIS;
321
322 /// Creates rematerialization candidates. The strategy has more restrictions
323 /// on what it can rematerialize compared to the rematerializer.
324 void createCandidates();
325
326 /// Determines whether users of rematerialization candidate \p CandIdx are
327 /// compatible with the strategy's rematerialization constraints/limitations.
328 /// Registers in \p MarkedRegs have already been deemed rematerializable by
329 /// the strategy.
330 bool candidateHasValidUsers(RegisterIdx CandIdx,
331 const SmallSet<Register, 4> &MarkedRegs) const;
332};
333
334} // namespace llvm
335
336#endif // LLVM_LIB_TARGET_AMDGPU_GCNREMATSTRATEGY_H
337