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