| 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 | |
| 22 | namespace 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. |
| 42 | class GCNRematStrategy { |
| 43 | using RegionBoundaries = Rematerializer::RegionBoundaries; |
| 44 | using RegisterIdx = Rematerializer::RegisterIdx; |
| 45 | |
| 46 | public: |
| 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 | |
| 86 | private: |
| 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 | |