| 1 | //===-- GCNRematStrategy.cpp - 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 | /// Implements the rematerialization strategy. |
| 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
| 14 | #include "GCNRematStrategy.h" |
| 15 | #include "GCNRegPressure.h" |
| 16 | #include "SIMachineFunctionInfo.h" |
| 17 | #include "llvm/ADT/BitVector.h" |
| 18 | #include "llvm/CodeGen/MachineBasicBlock.h" |
| 19 | #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" |
| 20 | #include "llvm/CodeGen/RegisterPressure.h" |
| 21 | #include "llvm/CodeGen/TargetRegisterInfo.h" |
| 22 | #include "llvm/MC/LaneBitmask.h" |
| 23 | #include "llvm/Support/Debug.h" |
| 24 | |
| 25 | #define DEBUG_TYPE "gcn-rematerialization-strategy" |
| 26 | |
| 27 | using namespace llvm; |
| 28 | using RegSubRegPair = TargetInstrInfo::RegSubRegPair; |
| 29 | using RegisterIdx = Rematerializer::RegisterIdx; |
| 30 | |
| 31 | GCNRematStrategy::RematRegions::RematRegions( |
| 32 | ArrayRef<RegionBoundaries> Regions, |
| 33 | MutableArrayRef<GCNRPTracker::LiveRegSet> LiveIns, |
| 34 | MutableArrayRef<GCNRPTracker::LiveRegSet> LiveOuts, LiveIntervals &LIS, |
| 35 | const MachineBlockFrequencyInfo &MBFI, const MachineRegisterInfo &MRI) |
| 36 | : Bounds(Regions), LiveIns(LiveIns), LiveOuts(LiveOuts), |
| 37 | Frequencies(Regions.size(), 0), LIS(LIS), MRI(MRI) { |
| 38 | assert(LiveIns.size() == Regions.size()); |
| 39 | assert(LiveOuts.size() == Regions.size()); |
| 40 | |
| 41 | // Derive frequency of each region. Frequencies are scaled down if they are |
| 42 | // high to avoid overflow/underflow when combining them. |
| 43 | MinFreq = MBFI.getEntryFreq().getFrequency(); |
| 44 | MaxFreq = 0; |
| 45 | for (unsigned RegionIdx : seq(Size: Regions.size())) { |
| 46 | MachineBasicBlock *MBB = Regions[RegionIdx].first->getParent(); |
| 47 | uint64_t BlockFreq = MBFI.getBlockFreq(MBB).getFrequency(); |
| 48 | Frequencies[RegionIdx] = BlockFreq; |
| 49 | if (BlockFreq && BlockFreq < MinFreq) |
| 50 | MinFreq = BlockFreq; |
| 51 | else if (BlockFreq > MaxFreq) |
| 52 | MaxFreq = BlockFreq; |
| 53 | } |
| 54 | if (!MinFreq) |
| 55 | return; |
| 56 | |
| 57 | // Scale everything down if frequencies are high. |
| 58 | if (MinFreq >= FreqScaleFactor * FreqScaleFactor) { |
| 59 | for (uint64_t &Freq : Frequencies) |
| 60 | Freq /= FreqScaleFactor; |
| 61 | MinFreq /= FreqScaleFactor; |
| 62 | MaxFreq /= FreqScaleFactor; |
| 63 | } |
| 64 | } |
| 65 | |
| 66 | GCNRegPressure GCNRematStrategy::RematRegions::computeMaxRegPressure( |
| 67 | unsigned RegionIdx) const { |
| 68 | assert(RegionIdx < Bounds.size() && "out of bounds" ); |
| 69 | const auto &[Begin, End] = Bounds[RegionIdx]; |
| 70 | if (Begin == End) |
| 71 | return llvm::getRegPressure(MRI, LiveRegs&: LiveIns[RegionIdx]); |
| 72 | GCNDownwardRPTracker RPTracker(LIS); |
| 73 | RPTracker.advance(Begin, End, LiveRegsCopy: &LiveIns[RegionIdx]); |
| 74 | return RPTracker.moveMaxPressure(); |
| 75 | } |
| 76 | |
| 77 | void GCNRematStrategy::RematRegions::removeFromLiveMaps( |
| 78 | Register Reg, const BitVector &LiveIn, const BitVector &LiveOut) { |
| 79 | for (unsigned I : LiveIn.set_bits()) |
| 80 | LiveIns[I].erase(Val: Reg); |
| 81 | for (unsigned I : LiveOut.set_bits()) |
| 82 | LiveOuts[I].erase(Val: Reg); |
| 83 | } |
| 84 | |
| 85 | void GCNRematStrategy::RematRegions::addToLiveMaps(Register Reg, |
| 86 | LaneBitmask Mask, |
| 87 | const BitVector &LiveIn, |
| 88 | const BitVector &LiveOut) { |
| 89 | std::pair<Register, LaneBitmask> LiveReg(Reg, Mask); |
| 90 | for (unsigned I : LiveIn.set_bits()) |
| 91 | LiveIns[I].insert(KV: LiveReg); |
| 92 | for (unsigned I : LiveOut.set_bits()) |
| 93 | LiveOuts[I].insert(KV: LiveReg); |
| 94 | } |
| 95 | |
| 96 | GCNRematStrategy::RematTargets::RematTargets( |
| 97 | unsigned MaxSGPRs, unsigned MaxVGPRs, bool SpillReduction, |
| 98 | const MachineFunction &MF, const RematRegions &Regions, |
| 99 | ArrayRef<GCNRegPressure> *MaxPressure) |
| 100 | : ExcessRP(Regions.size()), Regions(Regions), |
| 101 | SpillReduction(SpillReduction) { |
| 102 | RPTargets.reserve(N: Regions.size()); |
| 103 | for (unsigned RegionIdx : seq(Size: Regions.size())) { |
| 104 | if (MaxPressure) { |
| 105 | RPTargets.emplace_back(Args&: MaxSGPRs, Args&: MaxVGPRs, Args: MF, Args: (*MaxPressure)[RegionIdx]); |
| 106 | } else { |
| 107 | RPTargets.emplace_back(Args&: MaxSGPRs, Args&: MaxVGPRs, Args: MF, |
| 108 | Args: Regions.computeMaxRegPressure(RegionIdx)); |
| 109 | } |
| 110 | if (!RPTargets.back().satisfied()) |
| 111 | ExcessRP.set(RegionIdx); |
| 112 | } |
| 113 | } |
| 114 | |
| 115 | void GCNRematStrategy::RematTargets::updateRPTargets( |
| 116 | const BitVector &UpdateRegions, const GCNRegPressure &RPSave) { |
| 117 | for (unsigned I : UpdateRegions.set_bits()) { |
| 118 | RPTargets[I].saveRP(SaveRP: RPSave); |
| 119 | if (ExcessRP[I] && RPTargets[I].satisfied()) { |
| 120 | LLVM_DEBUG(dbgs() << " [" << I << "] Target reached!\n" ); |
| 121 | ExcessRP.reset(Idx: I); |
| 122 | } |
| 123 | } |
| 124 | } |
| 125 | |
| 126 | bool GCNRematStrategy::RematTargets::updateAndVerifyRPTargets( |
| 127 | const BitVector &UpdateRegions) { |
| 128 | bool TooOptimistic = false; |
| 129 | for (unsigned RegionIdx : UpdateRegions.set_bits()) { |
| 130 | GCNRPTarget &Target = RPTargets[RegionIdx]; |
| 131 | Target.setRP(Regions.computeMaxRegPressure(RegionIdx)); |
| 132 | |
| 133 | // Since we were optimistic in assessing RP decreases in these regions, we |
| 134 | // may need to remark the target as a target region if RP didn't decrease |
| 135 | // as expected. |
| 136 | if (!ExcessRP.test(Idx: RegionIdx) && !Target.satisfied()) { |
| 137 | LLVM_DEBUG(dbgs() << " [" << RegionIdx << "] Incorrect RP estimation\n" ); |
| 138 | TooOptimistic = true; |
| 139 | ExcessRP.set(RegionIdx); |
| 140 | } |
| 141 | } |
| 142 | return TooOptimistic; |
| 143 | } |
| 144 | |
| 145 | void GCNRematStrategy::RematCandidate::init(const RematRegions &RF, |
| 146 | const Rematerializer &Remater, |
| 147 | const MachineRegisterInfo &MRI) { |
| 148 | const Rematerializer::Reg &Reg = Remater.getReg(RegIdx); |
| 149 | Register DefReg = Reg.getDefReg(); |
| 150 | |
| 151 | Live |= LiveIn; |
| 152 | Live |= LiveOut; |
| 153 | |
| 154 | for (unsigned I : Live.set_bits()) { |
| 155 | // If the register is both unused and live-through in the region, the |
| 156 | // latter's RP is guaranteed to decrease. |
| 157 | if (!LiveIn[I] || !LiveOut[I] || Reg.Uses.contains(Val: I)) |
| 158 | UnpredictableRPSave.set(I); |
| 159 | } |
| 160 | RPSave.inc(Reg: DefReg, PrevMask: LaneBitmask::getNone(), NewMask: Reg.Mask, MRI); |
| 161 | |
| 162 | // Estimate the difference in instruction execution frequency that will be |
| 163 | // induced by the rematerialization. A rematerialization from the least |
| 164 | // frequent region to the most frequent region should yield the greatest |
| 165 | // frequency penalty (most negative frequency difference). When the register |
| 166 | // has users in its defining region the original instruction(s) won't be |
| 167 | // deleted so there is no frequency gain in the defining region. |
| 168 | int64_t DefOrMin = |
| 169 | Reg.hasUsersInDefRegion() ? 0 : RF.getFrequencyOrMin(RegionIdx: Reg.DefRegion); |
| 170 | int64_t UseOrMax = 0; |
| 171 | for (const auto &[UseRegion, _] : Reg.Uses) { |
| 172 | if (Reg.DefRegion == UseRegion) |
| 173 | continue; |
| 174 | UseOrMax += RF.getFrequencyOrMax(RegionIdx: UseRegion); |
| 175 | } |
| 176 | FreqDiff = DefOrMin - UseOrMax; |
| 177 | } |
| 178 | |
| 179 | void GCNRematStrategy::RematCandidate::update(const RematTargets &Targets) { |
| 180 | MaxFreq = RegionImpact = 0; |
| 181 | for (unsigned RegionIdx : Targets.ExcessRP.set_bits()) { |
| 182 | if (!Live[RegionIdx]) |
| 183 | continue; |
| 184 | |
| 185 | // The rematerialization must contribute positively in at least one |
| 186 | // register class with usage above the RP target for this region to |
| 187 | // contribute to the score. |
| 188 | const GCNRPTarget &RegionTarget = Targets.RPTargets[RegionIdx]; |
| 189 | const unsigned NumRegsBenefit = RegionTarget.getNumRegsBenefit(SaveRP: RPSave); |
| 190 | if (!NumRegsBenefit) |
| 191 | continue; |
| 192 | |
| 193 | // Regions in which RP is guaranteed to decrease have more weight. |
| 194 | RegionImpact += (UnpredictableRPSave[RegionIdx] ? 1 : 2) * NumRegsBenefit; |
| 195 | |
| 196 | if (Targets.SpillReduction) { |
| 197 | uint64_t Freq = Targets.Regions.getFrequency(RegionIdx); |
| 198 | if (UnpredictableRPSave[RegionIdx]) { |
| 199 | // Apply a frequency penalty in regions in which we are not sure that RP |
| 200 | // will decrease. |
| 201 | Freq /= 2; |
| 202 | } |
| 203 | MaxFreq = std::max(a: MaxFreq, b: Freq); |
| 204 | } |
| 205 | } |
| 206 | } |
| 207 | |
| 208 | bool GCNRematStrategy::RematCandidate::maybeBeneficial( |
| 209 | const RematTargets &Targets) const { |
| 210 | for (unsigned I : Targets.ExcessRP.set_bits()) { |
| 211 | if (Live[I] && Targets.RPTargets[I].isSaveBeneficial(SaveRP: RPSave)) |
| 212 | return true; |
| 213 | } |
| 214 | return false; |
| 215 | } |
| 216 | |
| 217 | void GCNRematStrategy::RematCandidate::rematerialize( |
| 218 | Rematerializer &Remater) const { |
| 219 | const Rematerializer::Reg &Reg = Remater.getReg(RegIdx); |
| 220 | |
| 221 | // All rematerializable dependencies are re-used for all rematerializations. |
| 222 | Rematerializer::DependencyReuseInfo DRI; |
| 223 | for (RegisterIdx DepRegIdx : Reg.Dependencies) |
| 224 | DRI.reuse(DepIdx: DepRegIdx); |
| 225 | |
| 226 | // Rematerialize once per using region, except in the defining region. |
| 227 | SmallVector<unsigned, 8> RematRegions; |
| 228 | RematRegions.reserve(N: Reg.Uses.size()); |
| 229 | for (const auto &[UseRegion, _] : Reg.Uses) { |
| 230 | if (Reg.DefRegion != UseRegion) |
| 231 | RematRegions.push_back(Elt: UseRegion); |
| 232 | } |
| 233 | for (const unsigned UseRegion : RematRegions) { |
| 234 | Rematerializer::DependencyReuseInfo RegionDRI(DRI); |
| 235 | Remater.rematerializeToRegion(RootIdx: RegIdx, UseRegion, DRI&: RegionDRI); |
| 236 | } |
| 237 | } |
| 238 | |
| 239 | void GCNRematStrategy::rematerializeFor( |
| 240 | unsigned MaxSGPRs, unsigned MaxVGPRs, bool SpillReduction, |
| 241 | BitVector &AffectedRegions, MutableArrayRef<GCNRegPressure> *MaxPressure) { |
| 242 | assert(AffectedRegions.size() == Regions.size()); |
| 243 | assert(!MaxPressure || MaxPressure->size() == Regions.size()); |
| 244 | |
| 245 | RematTargets Targets(MaxSGPRs, MaxVGPRs, SpillReduction, MF, Regions, |
| 246 | MaxPressure); |
| 247 | if (Targets.allAchieved()) |
| 248 | return; |
| 249 | if (!CandidatesCreated) { |
| 250 | Remater.analyze(); |
| 251 | createCandidates(); |
| 252 | } |
| 253 | |
| 254 | LLVM_DEBUG({ |
| 255 | dbgs() << "Rematerializing across regions to reduce RP below target in " |
| 256 | "function " ; |
| 257 | MF.getFunction().printAsOperand(dbgs(), /*PrintType=*/false); |
| 258 | dbgs() << '\n' |
| 259 | << Candidates.size() |
| 260 | << " rematerialization candidates were identified in the function\n" |
| 261 | << Targets.print() << '\n'; |
| 262 | MF.print(dbgs(), LIS.getSlotIndexes()); |
| 263 | }); |
| 264 | |
| 265 | // Keep track of all useful candidates. |
| 266 | SmallVector<unsigned, 8> CandidateOrder; |
| 267 | for (auto [CandIdx, Cand] : enumerate(First&: Candidates)) { |
| 268 | Cand.update(Targets); |
| 269 | if (!Cand.hasNullScore()) |
| 270 | CandidateOrder.push_back(Elt: CandIdx); |
| 271 | } |
| 272 | |
| 273 | // Rematerialize registers in successive rounds until all RP targets are |
| 274 | // satisifed or until we run out of rematerialization candidates. |
| 275 | BitVector RecomputeRP(Regions.size()); |
| 276 | for (;;) { |
| 277 | RecomputeRP.reset(); |
| 278 | |
| 279 | // Sort candidates in increasing score order. |
| 280 | sort(C&: CandidateOrder, Comp: [&](unsigned LHSIndex, unsigned RHSIndex) { |
| 281 | return Candidates[LHSIndex] < Candidates[RHSIndex]; |
| 282 | }); |
| 283 | |
| 284 | LLVM_DEBUG({ |
| 285 | dbgs() << "==== NEW REMAT ROUND ====\n" |
| 286 | << "Candidates with non-null score, in rematerialization order:\n" ; |
| 287 | for (const RematCandidate &Cand : reverse(Candidates)) { |
| 288 | dbgs() << " " << Cand.print() << " | " |
| 289 | << Remater.printRematReg(Cand.RegIdx) << '\n'; |
| 290 | } |
| 291 | dbgs() << Targets.print(); |
| 292 | }); |
| 293 | |
| 294 | // Rematerialize registers in decreasing score order until we estimate |
| 295 | // that all RP targets are satisfied or until rematerialization candidates |
| 296 | // are no longer useful to decrease RP. |
| 297 | while (!CandidateOrder.empty()) { |
| 298 | const RematCandidate &Cand = Candidates[CandidateOrder.back()]; |
| 299 | const Rematerializer::Reg &Reg = Remater.getReg(RegIdx: Cand.RegIdx); |
| 300 | |
| 301 | // When previous rematerializations in this round have already satisfied |
| 302 | // RP targets in all regions this rematerialization can impact, we have a |
| 303 | // good indication that our scores have diverged significantly from |
| 304 | // reality, in which case we interrupt this round and re-score. This also |
| 305 | // ensures that every rematerialization we perform is possibly impactful |
| 306 | // in at least one target region. |
| 307 | if (!Cand.maybeBeneficial(Targets)) { |
| 308 | LLVM_DEBUG(dbgs() << "Interrupt round on stale score for " |
| 309 | << Cand.print() << " | " |
| 310 | << Remater.printRematReg(Cand.RegIdx)); |
| 311 | break; |
| 312 | } |
| 313 | CandidateOrder.pop_back(); |
| 314 | |
| 315 | #ifdef EXPENSIVE_CHECKS |
| 316 | // All uses outside the defining region are known to be available / live |
| 317 | // at the remat points. Thus, the uses should already be live in to |
| 318 | // those using regions. |
| 319 | const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo(); |
| 320 | for (const MachineInstr *DefMI : Reg.Defs) { |
| 321 | for (const MachineOperand &MO : DefMI->operands()) { |
| 322 | // Exclude the defined register. We are rematerializing all |
| 323 | // instructions defining it so we don't care that its value is |
| 324 | // available at the remat point. |
| 325 | if (!MO.isReg() || !MO.getReg() || !MO.readsReg() || MO.isDef()) |
| 326 | continue; |
| 327 | |
| 328 | Register UseReg = MO.getReg(); |
| 329 | if (!UseReg.isVirtual()) |
| 330 | continue; |
| 331 | |
| 332 | LiveInterval &LI = LIS.getInterval(UseReg); |
| 333 | LaneBitmask LM = MRI.getMaxLaneMaskForVReg(MO.getReg()); |
| 334 | if (LI.hasSubRanges() && MO.getSubReg()) |
| 335 | LM = TRI.getSubRegIndexLaneMask(MO.getSubReg()); |
| 336 | |
| 337 | for (const auto &[UseRegion, _] : Reg.Uses) { |
| 338 | if (UseRegion == Reg.DefRegion) |
| 339 | continue; |
| 340 | LaneBitmask LiveInMask = Regions.getLiveIns(UseRegion).at(UseReg); |
| 341 | LaneBitmask UncoveredLanes = LM & ~(LiveInMask & LM); |
| 342 | // If this register has lanes not covered by the LiveIns, be sure |
| 343 | // they do not map to any subrange. ref: |
| 344 | // machine-scheduler-sink-trivial-remats.mir::omitted_subrange |
| 345 | if (UncoveredLanes.any()) { |
| 346 | assert(LI.hasSubRanges()); |
| 347 | for (LiveInterval::SubRange &SR : LI.subranges()) |
| 348 | assert((SR.LaneMask & UncoveredLanes).none()); |
| 349 | } |
| 350 | } |
| 351 | } |
| 352 | } |
| 353 | #endif |
| 354 | |
| 355 | // Remove the register from all regions where it is a live-in or live-out, |
| 356 | // then rematerialize the register. |
| 357 | LLVM_DEBUG(dbgs() << "** REMAT " << Remater.printRematReg(Cand.RegIdx) |
| 358 | << '\n'); |
| 359 | Regions.removeFromLiveMaps(Reg: Reg.getDefReg(), LiveIn: Cand.LiveIn, LiveOut: Cand.LiveOut); |
| 360 | if (Recorder) { |
| 361 | Recorder->LiveMapUpdates.emplace_back(Args: Cand.RegIdx, Args: Cand.LiveIn, |
| 362 | Args: Cand.LiveOut); |
| 363 | } |
| 364 | Cand.rematerialize(Remater); |
| 365 | |
| 366 | // Adjust RP targets. The save is guaranteed in regions in which the |
| 367 | // register is live-through and unused but optimistic in all other regions |
| 368 | // where the register is live. |
| 369 | Targets.updateRPTargets(UpdateRegions: Cand.Live, RPSave: Cand.RPSave); |
| 370 | RecomputeRP |= Cand.UnpredictableRPSave; |
| 371 | AffectedRegions |= Cand.Live; |
| 372 | if (Targets.allAchieved()) { |
| 373 | LLVM_DEBUG(dbgs() << "All targets cleared, verifying...\n" ); |
| 374 | break; |
| 375 | } |
| 376 | } |
| 377 | |
| 378 | if (!Targets.updateAndVerifyRPTargets(UpdateRegions: RecomputeRP) && |
| 379 | Targets.allAchieved()) { |
| 380 | LLVM_DEBUG(dbgs() << "Objectives achieved!\n" ); |
| 381 | break; |
| 382 | } |
| 383 | |
| 384 | // Update the score of remaining candidates and filter out those that have |
| 385 | // become useless from the vector. Candidates never become useful after |
| 386 | // having been useless for a round, so we can freely drop them without |
| 387 | // losing any future rematerialization opportunity. |
| 388 | unsigned NumUsefulCandidates = 0; |
| 389 | for (unsigned CandIdx : CandidateOrder) { |
| 390 | RematCandidate &Candidate = Candidates[CandIdx]; |
| 391 | Candidate.update(Targets); |
| 392 | if (!Candidate.hasNullScore()) |
| 393 | CandidateOrder[NumUsefulCandidates++] = CandIdx; |
| 394 | } |
| 395 | if (NumUsefulCandidates == 0) { |
| 396 | LLVM_DEBUG(dbgs() << "Stop on exhausted rematerialization candidates\n" ); |
| 397 | break; |
| 398 | } |
| 399 | CandidateOrder.truncate(N: NumUsefulCandidates); |
| 400 | } |
| 401 | |
| 402 | if (!MaxPressure) |
| 403 | return; |
| 404 | for (unsigned RegionIdx : AffectedRegions.set_bits()) |
| 405 | (*MaxPressure)[RegionIdx] = Targets.RPTargets[RegionIdx].getCurrentRP(); |
| 406 | } |
| 407 | |
| 408 | void GCNRematStrategy::createCandidates() { |
| 409 | CandidatesCreated = true; |
| 410 | |
| 411 | // Set of registers already marked for potential remterialization; used to |
| 412 | // avoid rematerialization chains. |
| 413 | SmallSet<Register, 4> MarkedRegs; |
| 414 | |
| 415 | // Map registers to candidate indices. Use ~0u as null value since 0 is a |
| 416 | // valid index. |
| 417 | IndexedMap<unsigned, VirtReg2IndexFunctor> DefRegToCandIdx(~0u); |
| 418 | DefRegToCandIdx.resize(S: MRI.getNumVirtRegs()); |
| 419 | const unsigned NumRegions = Regions.size(); |
| 420 | |
| 421 | for (unsigned RegIdx = 0, E = Remater.getNumRegs(); RegIdx < E; ++RegIdx) { |
| 422 | const Rematerializer::Reg &CandReg = Remater.getReg(RegIdx); |
| 423 | if (!CandReg.hasUsersOutsideDefRegion()) |
| 424 | continue; |
| 425 | |
| 426 | // Rematerialization moves the defining instruction into the region of its |
| 427 | // uses, which may sit under different control dependencies (e.g., across a |
| 428 | // change of EXEC). Convergent operations must not be made control-dependent |
| 429 | // on additional values, so they cannot be safely relocated this way. This |
| 430 | // mirrors the check MachineSink performs before sinking an instruction. |
| 431 | if (any_of(Range: CandReg.Defs, |
| 432 | P: [](const MachineInstr *DefMI) { return DefMI->isConvergent(); })) |
| 433 | continue; |
| 434 | |
| 435 | // Rematerializing a load into multiple using regions duplicates the |
| 436 | // memory access itself. Conservatively restrict rematerialization of loads |
| 437 | // to a single region. |
| 438 | if (CandReg.Uses.size() > 1 && |
| 439 | any_of(Range: CandReg.Defs, |
| 440 | P: [](const MachineInstr *DefMI) { return DefMI->mayLoad(); })) |
| 441 | continue; |
| 442 | |
| 443 | // We further filter the registers that we can rematerialize based on our |
| 444 | // current tracking capabilities in the strategy. This ensures that we are |
| 445 | // not extending any live range while rematerializing, and that |
| 446 | // rematerializing any register candidate will not affect other candidates. |
| 447 | |
| 448 | // All register dependencies should not already be considered |
| 449 | // rematerializable. |
| 450 | if (llvm::any_of(Range: CandReg.Dependencies, P: [&](RegisterIdx DepRegIdx) { |
| 451 | return MarkedRegs.contains(V: Remater.getReg(RegIdx: DepRegIdx).getDefReg()); |
| 452 | })) |
| 453 | continue; |
| 454 | |
| 455 | if (!candidateHasValidUsers(CandIdx: RegIdx, MarkedRegs)) |
| 456 | continue; |
| 457 | |
| 458 | Register DefReg = CandReg.getDefReg(); |
| 459 | MarkedRegs.insert(V: DefReg); |
| 460 | DefRegToCandIdx[DefReg] = static_cast<unsigned>(Candidates.size()); |
| 461 | Candidates.emplace_back(Args&: RegIdx, Args: NumRegions); |
| 462 | } |
| 463 | |
| 464 | // Initialize the LiveIn and LiveOut sets of all candidates. This is more |
| 465 | // efficient than querying those structures for each candidate separately. |
| 466 | for (unsigned RegionIdx = 0; RegionIdx < NumRegions; ++RegionIdx) { |
| 467 | for (const auto &[Reg, Mask] : Regions.getLiveIns(RegionIdx)) { |
| 468 | if (Register::isPhysicalRegister(Reg)) |
| 469 | continue; |
| 470 | unsigned CandIdx = DefRegToCandIdx[Reg]; |
| 471 | if (CandIdx != ~0u) |
| 472 | Candidates[CandIdx].LiveIn.set(RegionIdx); |
| 473 | } |
| 474 | for (const auto &[Reg, Mask] : Regions.getLiveOuts(RegionIdx)) { |
| 475 | if (Register::isPhysicalRegister(Reg)) |
| 476 | continue; |
| 477 | unsigned CandIdx = DefRegToCandIdx[Reg]; |
| 478 | if (CandIdx != ~0u) |
| 479 | Candidates[CandIdx].LiveOut.set(RegionIdx); |
| 480 | } |
| 481 | } |
| 482 | |
| 483 | for (RematCandidate &Cand : Candidates) |
| 484 | Cand.init(RF: Regions, Remater, MRI); |
| 485 | } |
| 486 | |
| 487 | bool GCNRematStrategy::candidateHasValidUsers( |
| 488 | RegisterIdx CandIdx, const SmallSet<Register, 4> &MarkedRegs) const { |
| 489 | const Rematerializer::Reg &CandReg = Remater.getReg(RegIdx: CandIdx); |
| 490 | SlotIndex RefIdx = |
| 491 | LIS.getInstructionIndex(Instr: *CandReg.getLastDef()).getRegSlot(EC: true); |
| 492 | |
| 493 | for (const auto &[UseRegion, Users] : CandReg.Uses) { |
| 494 | // Users cannot themselves be rematerializable. |
| 495 | if (llvm::any_of(Range: Users, P: [&](const MachineInstr *UserMI) { |
| 496 | assert(UserMI->getNumOperands() > 0 && |
| 497 | "user must have at least one operand" ); |
| 498 | // A user is rematerializable if its first register operand (its |
| 499 | // register def) was marked already. |
| 500 | const MachineOperand &DefMO = UserMI->getOperand(i: 0); |
| 501 | return DefMO.isReg() && MarkedRegs.contains(V: DefMO.getReg()); |
| 502 | })) |
| 503 | return false; |
| 504 | |
| 505 | MachineInstr *FirstUseMI = CandReg.getRegionUseBounds(UseRegion, LIS).first; |
| 506 | assert(FirstUseMI && "there must be a user in the region" ); |
| 507 | SlotIndex FirstUseIdx = |
| 508 | LIS.getInstructionIndex(Instr: *FirstUseMI).getRegSlot(EC: true); |
| 509 | |
| 510 | // All dependencies must be available at the first use in the region. |
| 511 | if (llvm::any_of(Range: CandReg.Dependencies, P: [&](RegisterIdx DepRegIdx) { |
| 512 | const Rematerializer::Reg &DepReg = Remater.getReg(RegIdx: DepRegIdx); |
| 513 | Register DepDefReg = DepReg.getDefReg(); |
| 514 | return !Remater.isRegIdenticalAtUses(Reg: DepDefReg, Mask: DepReg.Mask, RefSlot: RefIdx, |
| 515 | Uses: {FirstUseIdx}); |
| 516 | })) |
| 517 | return false; |
| 518 | if (llvm::any_of(Range: Remater.getUnrematableDeps(RegIdx: CandIdx), |
| 519 | P: [&](const std::pair<Register, LaneBitmask> &RegAndMask) { |
| 520 | const auto &[Reg, Mask] = RegAndMask; |
| 521 | return !Remater.isRegIdenticalAtUses(Reg, Mask, RefSlot: RefIdx, |
| 522 | Uses: {FirstUseIdx}); |
| 523 | })) |
| 524 | return false; |
| 525 | } |
| 526 | return true; |
| 527 | } |
| 528 | |
| 529 | void GCNRematStrategy::rollbackRecordedRemats() { |
| 530 | // Roll back changes made by the strategy. |
| 531 | assert(Recorder && "recorder should be defined" ); |
| 532 | Recorder->Listener.rollback(Remater); |
| 533 | for (const auto &[RegIdx, LiveIn, LiveOut] : Recorder->LiveMapUpdates) { |
| 534 | const Rematerializer::Reg &Reg = Remater.getReg(RegIdx); |
| 535 | Regions.addToLiveMaps(Reg: Reg.getDefReg(), Mask: Reg.Mask, LiveIn, LiveOut); |
| 536 | } |
| 537 | } |
| 538 | |
| 539 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| 540 | Printable GCNRematStrategy::RematCandidate::print() const { |
| 541 | return Printable([&](raw_ostream &OS) { |
| 542 | OS << '(' << MaxFreq << ", " << FreqDiff << ", " << RegionImpact << ')'; |
| 543 | }); |
| 544 | } |
| 545 | |
| 546 | Printable GCNRematStrategy::RematTargets::print() const { |
| 547 | return Printable([&](raw_ostream &OS) { |
| 548 | if (allAchieved()) { |
| 549 | OS << "No target regions\n" ; |
| 550 | return; |
| 551 | } |
| 552 | OS << "Target regions:\n" ; |
| 553 | for (unsigned I : ExcessRP.set_bits()) |
| 554 | OS << " [" << I << "] " << RPTargets[I] << '\n'; |
| 555 | }); |
| 556 | } |
| 557 | #endif |
| 558 | |