1//===- VPlanAnalysis.cpp - Various Analyses working on VPlan ----*- 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#include "VPlanAnalysis.h"
10#include "VPlan.h"
11#include "VPlanCFG.h"
12#include "VPlanDominatorTree.h"
13#include "VPlanHelpers.h"
14#include "VPlanPatternMatch.h"
15#include "llvm/ADT/PostOrderIterator.h"
16#include "llvm/Analysis/TargetTransformInfo.h"
17
18using namespace llvm;
19using namespace VPlanPatternMatch;
20
21#define DEBUG_TYPE "vplan"
22
23void llvm::collectEphemeralRecipesForVPlan(
24 VPlan &Plan, DenseSet<VPRecipeBase *> &EphRecipes) {
25 // First, collect seed recipes which are operands of assumes.
26 SmallVector<VPRecipeBase *> Worklist;
27 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
28 Range: vp_depth_first_deep(G: Plan.getVectorLoopRegion()->getEntry()))) {
29 for (VPRecipeBase &R : *VPBB) {
30 auto *RepR = dyn_cast<VPReplicateRecipe>(Val: &R);
31 if (!RepR || !match(V: RepR, P: m_Intrinsic<Intrinsic::assume>()))
32 continue;
33 Worklist.push_back(Elt: RepR);
34 EphRecipes.insert(V: RepR);
35 }
36 }
37
38 // Process operands of candidates in worklist and add them to the set of
39 // ephemeral recipes, if they don't have side-effects and are only used by
40 // other ephemeral recipes.
41 while (!Worklist.empty()) {
42 VPRecipeBase *Cur = Worklist.pop_back_val();
43 for (VPValue *Op : Cur->operands()) {
44 auto *OpR = Op->getDefiningRecipe();
45 if (!OpR || OpR->mayHaveSideEffects() || EphRecipes.contains(V: OpR))
46 continue;
47 if (any_of(Range: Op->users(), P: [EphRecipes](VPUser *U) {
48 auto *UR = dyn_cast<VPRecipeBase>(Val: U);
49 return !UR || !EphRecipes.contains(V: UR);
50 }))
51 continue;
52 EphRecipes.insert(V: OpR);
53 Worklist.push_back(Elt: OpR);
54 }
55 }
56}
57
58bool VPDominatorTree::properlyDominates(const VPRecipeBase *A,
59 const VPRecipeBase *B) const {
60 if (A == B)
61 return false;
62
63 auto LocalComesBefore = [](const VPRecipeBase *A, const VPRecipeBase *B) {
64 for (auto &R : *A->getParent()) {
65 if (&R == A)
66 return true;
67 if (&R == B)
68 return false;
69 }
70 llvm_unreachable("recipe not found");
71 };
72 const VPBlockBase *ParentA = A->getParent();
73 const VPBlockBase *ParentB = B->getParent();
74 if (ParentA == ParentB)
75 return LocalComesBefore(A, B);
76
77 return Base::properlyDominates(A: ParentA, B: ParentB);
78}
79
80InstructionCost
81VPRegisterUsage::spillCost(const TargetTransformInfo &TTI,
82 TargetTransformInfo::TargetCostKind CostKind,
83 unsigned OverrideMaxNumRegs) const {
84 InstructionCost Cost;
85 for (const auto &[RegClass, MaxUsers] : MaxLocalUsers) {
86 unsigned AvailableRegs = OverrideMaxNumRegs > 0
87 ? OverrideMaxNumRegs
88 : TTI.getNumberOfRegisters(ClassID: RegClass);
89 if (MaxUsers > AvailableRegs) {
90 // Assume that for each register used past what's available we get one
91 // spill and reload.
92 unsigned Spills = MaxUsers - AvailableRegs;
93 InstructionCost SpillCost =
94 TTI.getRegisterClassSpillCost(ClassID: RegClass, CostKind) +
95 TTI.getRegisterClassReloadCost(ClassID: RegClass, CostKind);
96 InstructionCost TotalCost = Spills * SpillCost;
97 LLVM_DEBUG(dbgs() << "LV(REG): Cost of " << TotalCost << " from "
98 << Spills << " spills of "
99 << TTI.getRegisterClassName(RegClass) << "\n");
100 Cost += TotalCost;
101 }
102 }
103 return Cost;
104}
105
106SmallVector<VPRegisterUsage, 8>
107llvm::calculateRegisterUsageForPlan(VPlan &Plan, ArrayRef<ElementCount> VFs,
108 const TargetTransformInfo &TTI) {
109 DenseSet<VPRecipeBase *> EphemeralRecipes;
110 collectEphemeralRecipesForVPlan(Plan, EphRecipes&: EphemeralRecipes);
111
112 // Each 'key' in the map opens a new interval. The values
113 // of the map are the index of the 'last seen' usage of the
114 // VPValue that is the key.
115 using IntervalMap = SmallDenseMap<VPValue *, unsigned, 16>;
116
117 // Maps indices to recipes.
118 SmallVector<VPRecipeBase *, 64> Idx2Recipe;
119 // Marks the end of each interval.
120 IntervalMap EndPoint;
121 // Saves the list of VPValues that are used in the loop.
122 SmallPtrSet<VPValue *, 8> Ends;
123 // Saves the list of values that are used in the loop but are defined outside
124 // the loop (not including non-recipe values such as arguments and
125 // constants).
126 SmallSetVector<VPValue *, 8> LoopInvariants;
127 if (!Plan.getVectorTripCount().user_empty())
128 LoopInvariants.insert(X: &Plan.getVectorTripCount());
129
130 // We scan the loop in a topological order in order and assign a number to
131 // each recipe. We use RPO to ensure that defs are met before their users. We
132 // assume that each recipe that has in-loop users starts an interval. We
133 // record every time that an in-loop value is used, so we have a list of the
134 // first occurences of each recipe and last occurrence of each VPValue.
135 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();
136 ReversePostOrderTraversal<VPBlockDeepTraversalWrapper<VPBlockBase *>> RPOT(
137 LoopRegion);
138 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(Range&: RPOT)) {
139 if (!VPBB->getParent())
140 break;
141 for (VPRecipeBase &R : *VPBB) {
142 Idx2Recipe.push_back(Elt: &R);
143
144 // Save the end location of each USE.
145 for (VPValue *U : R.operands()) {
146 if (isa<VPRecipeValue>(Val: U)) {
147 // Overwrite previous end points.
148 EndPoint[U] = Idx2Recipe.size();
149 Ends.insert(Ptr: U);
150 } else if (auto *IRV = dyn_cast<VPIRValue>(Val: U)) {
151 // Ignore non-recipe values such as arguments, constants, etc.
152 // FIXME: Might need some motivation why these values are ignored. If
153 // for example an argument is used inside the loop it will increase
154 // the register pressure (so shouldn't we add it to LoopInvariants).
155 if (!isa<Instruction>(Val: IRV->getValue()))
156 continue;
157 // This recipe is outside the loop, record it and continue.
158 LoopInvariants.insert(X: U);
159 }
160 // Other types of VPValue are currently not tracked.
161 }
162 }
163 if (VPBB == LoopRegion->getExiting()) {
164 // VPWidenIntOrFpInductionRecipes are used implicitly at the end of the
165 // exiting block, where their increment will get materialized eventually.
166 for (auto &R : LoopRegion->getEntryBasicBlock()->phis()) {
167 if (auto *WideIV = dyn_cast<VPWidenIntOrFpInductionRecipe>(Val: &R)) {
168 EndPoint[WideIV] = Idx2Recipe.size();
169 Ends.insert(Ptr: WideIV);
170 }
171 }
172 }
173 }
174
175 // Saves the list of intervals that end with the index in 'key'.
176 using VPValueList = SmallVector<VPValue *, 2>;
177 SmallDenseMap<unsigned, VPValueList, 16> TransposeEnds;
178
179 // Next, we transpose the EndPoints into a multi map that holds the list of
180 // intervals that *end* at a specific location.
181 for (auto &Interval : EndPoint)
182 TransposeEnds[Interval.second].push_back(Elt: Interval.first);
183
184 SmallPtrSet<VPValue *, 8> OpenIntervals;
185 SmallVector<VPRegisterUsage, 8> RUs(VFs.size());
186 SmallVector<SmallMapVector<unsigned, unsigned, 4>, 8> MaxUsages(VFs.size());
187
188 LLVM_DEBUG(dbgs() << "LV(REG): Calculating max register usage:\n");
189
190 const auto &TTICapture = TTI;
191 auto GetRegUsage = [&TTICapture](Type *Ty, ElementCount VF) -> unsigned {
192 if (Ty->isTokenTy() || !VectorType::isValidElementType(ElemTy: Ty) ||
193 (VF.isScalable() &&
194 !TTICapture.isElementTypeLegalForScalableVector(Ty)))
195 return 0;
196 return TTICapture.getRegUsageForType(Ty: VectorType::get(ElementType: Ty, EC: VF));
197 };
198
199 VPValue *CanIV = LoopRegion->getCanonicalIV();
200 // Note: canonical IVs are retained even if they have no users.
201 if (!CanIV->user_empty())
202 OpenIntervals.insert(Ptr: CanIV);
203
204 // We scan the instructions linearly and record each time that a new interval
205 // starts, by placing it in a set. If we find this value in TransposEnds then
206 // we remove it from the set. The max register usage is the maximum register
207 // usage of the recipes of the set.
208 for (unsigned int Idx = 0, Sz = Idx2Recipe.size(); Idx < Sz; ++Idx) {
209 VPRecipeBase *R = Idx2Recipe[Idx];
210
211 // Remove all of the VPValues that end at this location.
212 VPValueList &List = TransposeEnds[Idx];
213 for (VPValue *ToRemove : List)
214 OpenIntervals.erase(Ptr: ToRemove);
215
216 // Ignore recipes that are never used within the loop and do not have side
217 // effects.
218 if (none_of(Range: R->definedValues(),
219 P: [&Ends](VPValue *Def) { return Ends.count(Ptr: Def); }) &&
220 !R->mayHaveSideEffects())
221 continue;
222
223 // Skip recipes for ephemeral values, i.e. those only feeding assumes. They
224 // are removed before code generation and must not contribute to the
225 // register pressure of the plan.
226 if (EphemeralRecipes.contains(V: R))
227 continue;
228
229 // For each VF find the maximum usage of registers.
230 for (unsigned J = 0, E = VFs.size(); J < E; ++J) {
231 // Count the number of registers used, per register class, given all open
232 // intervals.
233 // Note that elements in this SmallMapVector will be default constructed
234 // as 0. So we can use "RegUsage[ClassID] += n" in the code below even if
235 // there is no previous entry for ClassID.
236 SmallMapVector<unsigned, unsigned, 4> RegUsage;
237
238 for (auto *VPV : OpenIntervals) {
239 // Skip artificial values or values that weren't present in the original
240 // loop.
241 // TODO: Remove skipping values that weren't present in the original
242 // loop after removing the legacy
243 // LoopVectorizationCostModel::calculateRegisterUsage
244 if (isa<VPVectorPointerRecipe, VPVectorEndPointerRecipe,
245 VPBranchOnMaskRecipe>(Val: VPV) ||
246 match(V: VPV, P: m_ExtractLastPart(Op0: m_VPValue())))
247 continue;
248
249 if (VFs[J].isScalar() || VPV == CanIV ||
250 isa<VPReplicateRecipe, VPDerivedIVRecipe,
251 VPCurrentIterationPHIRecipe, VPScalarIVStepsRecipe>(Val: VPV) ||
252 (isa<VPInstruction>(Val: VPV) && vputils::onlyScalarValuesUsed(Def: VPV)) ||
253 (isa<VPReductionPHIRecipe>(Val: VPV) &&
254 (cast<VPReductionPHIRecipe>(Val: VPV))->isInLoop())) {
255 unsigned ClassID =
256 TTI.getRegisterClassForType(Vector: false, Ty: VPV->getScalarType());
257 // FIXME: The target might use more than one register for the type
258 // even in the scalar case.
259 RegUsage[ClassID] += 1;
260 } else {
261 // The output from scaled phis and scaled reductions actually has
262 // fewer lanes than the VF.
263 unsigned ScaleFactor =
264 vputils::getVFScaleFactor(R: VPV->getDefiningRecipe());
265 ElementCount VF = VFs[J];
266 if (ScaleFactor > 1) {
267 VF = VFs[J].divideCoefficientBy(RHS: ScaleFactor);
268 LLVM_DEBUG(dbgs() << "LV(REG): Scaled down VF from " << VFs[J]
269 << " to " << VF << " for " << *R << "\n";);
270 }
271
272 Type *ScalarTy = VPV->getScalarType();
273 unsigned ClassID = TTI.getRegisterClassForType(Vector: true, Ty: ScalarTy);
274 RegUsage[ClassID] += GetRegUsage(ScalarTy, VF);
275 }
276 }
277
278 for (const auto &Pair : RegUsage) {
279 auto &Entry = MaxUsages[J][Pair.first];
280 Entry = std::max(a: Entry, b: Pair.second);
281 }
282 }
283
284 LLVM_DEBUG(dbgs() << "LV(REG): At #" << Idx << " Interval # "
285 << OpenIntervals.size() << '\n');
286
287 // Add used VPValues defined by the current recipe to the list of open
288 // intervals.
289 for (VPValue *DefV : R->definedValues())
290 if (Ends.contains(Ptr: DefV))
291 OpenIntervals.insert(Ptr: DefV);
292 }
293
294 // We also search for instructions that are defined outside the loop, but are
295 // used inside the loop. We need this number separately from the max-interval
296 // usage number because when we unroll, loop-invariant values do not take
297 // more register.
298 VPRegisterUsage RU;
299 for (unsigned Idx = 0, End = VFs.size(); Idx < End; ++Idx) {
300 // Note that elements in this SmallMapVector will be default constructed
301 // as 0. So we can use "Invariant[ClassID] += n" in the code below even if
302 // there is no previous entry for ClassID.
303 SmallMapVector<unsigned, unsigned, 4> Invariant;
304
305 for (auto *In : LoopInvariants) {
306 // FIXME: The target might use more than one register for the type
307 // even in the scalar case.
308 bool IsScalar = vputils::onlyScalarValuesUsed(Def: In);
309
310 ElementCount VF = IsScalar ? ElementCount::getFixed(MinVal: 1) : VFs[Idx];
311 unsigned ClassID =
312 TTI.getRegisterClassForType(Vector: VF.isVector(), Ty: In->getScalarType());
313 Invariant[ClassID] += GetRegUsage(In->getScalarType(), VF);
314 }
315
316 LLVM_DEBUG({
317 dbgs() << "LV(REG): VF = " << VFs[Idx] << '\n';
318 dbgs() << "LV(REG): Found max usage: " << MaxUsages[Idx].size()
319 << " item\n";
320 for (const auto &pair : MaxUsages[Idx]) {
321 dbgs() << "LV(REG): RegisterClass: "
322 << TTI.getRegisterClassName(pair.first) << ", " << pair.second
323 << " registers\n";
324 }
325 dbgs() << "LV(REG): Found invariant usage: " << Invariant.size()
326 << " item\n";
327 for (const auto &pair : Invariant) {
328 dbgs() << "LV(REG): RegisterClass: "
329 << TTI.getRegisterClassName(pair.first) << ", " << pair.second
330 << " registers\n";
331 }
332 });
333
334 RU.LoopInvariantRegs = Invariant;
335 RU.MaxLocalUsers = MaxUsages[Idx];
336 RUs[Idx] = RU;
337 }
338
339 return RUs;
340}
341