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 "LoopVectorizationPlanner.h"
11#include "VPlan.h"
12#include "VPlanCFG.h"
13#include "VPlanDominatorTree.h"
14#include "VPlanHelpers.h"
15#include "VPlanPatternMatch.h"
16#include "VPlanUtils.h"
17#include "llvm/ADT/PostOrderIterator.h"
18#include "llvm/Analysis/AliasAnalysis.h"
19#include "llvm/Analysis/ScalarEvolutionExpressions.h"
20#include "llvm/Analysis/TargetTransformInfo.h"
21
22using namespace llvm;
23using namespace VPlanPatternMatch;
24
25#define DEBUG_TYPE "vplan"
26
27void llvm::collectEphemeralRecipesForVPlan(
28 VPlan &Plan, DenseSet<VPRecipeBase *> &EphRecipes) {
29 // First, collect seed recipes which are operands of assumes.
30 SmallVector<VPRecipeBase *> Worklist;
31 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
32 Range: vp_depth_first_deep(G: Plan.getVectorLoopRegion()->getEntry()))) {
33 for (VPReplicateRecipe &RepR : make_isa_range<VPReplicateRecipe>(Range&: *VPBB)) {
34 if (!match(V: &RepR, P: m_Intrinsic<Intrinsic::assume>()))
35 continue;
36 Worklist.push_back(Elt: &RepR);
37 EphRecipes.insert(V: &RepR);
38 }
39 }
40
41 // Process operands of candidates in worklist and add them to the set of
42 // ephemeral recipes, if they don't have side-effects and are only used by
43 // other ephemeral recipes.
44 while (!Worklist.empty()) {
45 VPRecipeBase *Cur = Worklist.pop_back_val();
46 for (VPValue *Op : Cur->operands()) {
47 auto *OpR = Op->getDefiningRecipe();
48 if (!OpR || OpR->mayHaveSideEffects() || EphRecipes.contains(V: OpR))
49 continue;
50 if (any_of(Range: Op->users(), P: [EphRecipes](VPUser *U) {
51 auto *UR = dyn_cast<VPRecipeBase>(Val: U);
52 return !UR || !EphRecipes.contains(V: UR);
53 }))
54 continue;
55 EphRecipes.insert(V: OpR);
56 Worklist.push_back(Elt: OpR);
57 }
58 }
59}
60
61bool VPDominatorTree::properlyDominates(const VPRecipeBase *A,
62 const VPRecipeBase *B) const {
63 if (A == B)
64 return false;
65
66 auto LocalComesBefore = [](const VPRecipeBase *A, const VPRecipeBase *B) {
67 for (auto &R : *A->getParent()) {
68 if (&R == A)
69 return true;
70 if (&R == B)
71 return false;
72 }
73 llvm_unreachable("recipe not found");
74 };
75 const VPBlockBase *ParentA = A->getParent();
76 const VPBlockBase *ParentB = B->getParent();
77 if (ParentA == ParentB)
78 return LocalComesBefore(A, B);
79
80 return Base::properlyDominates(A: ParentA, B: ParentB);
81}
82
83InstructionCost
84VPRegisterUsage::spillCost(const TargetTransformInfo &TTI,
85 TargetTransformInfo::TargetCostKind CostKind,
86 unsigned OverrideMaxNumRegs) const {
87 InstructionCost Cost;
88 for (const auto &[RegClass, MaxUsers] : MaxLocalUsers) {
89 unsigned AvailableRegs = OverrideMaxNumRegs > 0
90 ? OverrideMaxNumRegs
91 : TTI.getNumberOfRegisters(ClassID: RegClass);
92 if (MaxUsers > AvailableRegs) {
93 // Assume that for each register used past what's available we get one
94 // spill and reload.
95 unsigned Spills = MaxUsers - AvailableRegs;
96 InstructionCost SpillCost =
97 TTI.getRegisterClassSpillCost(ClassID: RegClass, CostKind) +
98 TTI.getRegisterClassReloadCost(ClassID: RegClass, CostKind);
99 InstructionCost TotalCost = Spills * SpillCost;
100 LLVM_DEBUG(dbgs() << "LV(REG): Cost of " << TotalCost << " from "
101 << Spills << " spills of "
102 << TTI.getRegisterClassName(RegClass) << "\n");
103 Cost += TotalCost;
104 }
105 }
106 return Cost;
107}
108
109SmallVector<VPRegisterUsage, 8>
110llvm::calculateRegisterUsageForPlan(VPlan &Plan, ArrayRef<ElementCount> VFs,
111 const TargetTransformInfo &TTI) {
112 DenseSet<VPRecipeBase *> EphemeralRecipes;
113 collectEphemeralRecipesForVPlan(Plan, EphRecipes&: EphemeralRecipes);
114
115 // Each 'key' in the map opens a new interval. The values
116 // of the map are the index of the 'last seen' usage of the
117 // VPValue that is the key.
118 using IntervalMap = SmallDenseMap<VPValue *, unsigned, 16>;
119
120 // Maps indices to recipes.
121 SmallVector<VPRecipeBase *, 64> Idx2Recipe;
122 // Marks the end of each interval.
123 IntervalMap EndPoint;
124 // Saves the list of VPValues that are used in the loop.
125 SmallPtrSet<VPValue *, 8> Ends;
126 // Saves the list of values that are used in the loop but are defined outside
127 // the loop (not including non-recipe values such as arguments and
128 // constants).
129 SmallSetVector<VPValue *, 8> LoopInvariants;
130 if (!Plan.getVectorTripCount().user_empty())
131 LoopInvariants.insert(X: &Plan.getVectorTripCount());
132
133 // We scan the loop in a topological order in order and assign a number to
134 // each recipe. We use RPO to ensure that defs are met before their users. We
135 // assume that each recipe that has in-loop users starts an interval. We
136 // record every time that an in-loop value is used, so we have a list of the
137 // first occurences of each recipe and last occurrence of each VPValue.
138 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();
139 ReversePostOrderTraversal<VPBlockDeepTraversalWrapper<VPBlockBase *>> RPOT(
140 LoopRegion);
141 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(Range&: RPOT)) {
142 if (!VPBB->getParent())
143 break;
144 for (VPRecipeBase &R : *VPBB) {
145 Idx2Recipe.push_back(Elt: &R);
146
147 // Save the end location of each USE.
148 for (VPValue *U : R.operands()) {
149 if (isa<VPRecipeValue>(Val: U)) {
150 // Overwrite previous end points.
151 EndPoint[U] = Idx2Recipe.size();
152 Ends.insert(Ptr: U);
153 } else if (auto *IRV = dyn_cast<VPIRValue>(Val: U)) {
154 // Ignore non-recipe values such as arguments, constants, etc.
155 // FIXME: Might need some motivation why these values are ignored. If
156 // for example an argument is used inside the loop it will increase
157 // the register pressure (so shouldn't we add it to LoopInvariants).
158 if (!isa<Instruction>(Val: IRV->getValue()))
159 continue;
160 // This recipe is outside the loop, record it and continue.
161 LoopInvariants.insert(X: U);
162 }
163 // Other types of VPValue are currently not tracked.
164 }
165 }
166 if (VPBB == LoopRegion->getExiting()) {
167 // VPWidenIntOrFpInductionRecipes are used implicitly at the end of the
168 // exiting block, where their increment will get materialized eventually.
169 for (auto &WideIV : make_isa_range<VPWidenIntOrFpInductionRecipe>(
170 Range: LoopRegion->getEntryBasicBlock()->phis())) {
171 EndPoint[&WideIV] = Idx2Recipe.size();
172 Ends.insert(Ptr: &WideIV);
173 }
174 }
175 }
176
177 // Saves the list of intervals that end with the index in 'key'.
178 using VPValueList = SmallVector<VPValue *, 2>;
179 SmallDenseMap<unsigned, VPValueList, 16> TransposeEnds;
180
181 // Next, we transpose the EndPoints into a multi map that holds the list of
182 // intervals that *end* at a specific location.
183 for (auto &Interval : EndPoint)
184 TransposeEnds[Interval.second].push_back(Elt: Interval.first);
185
186 SmallPtrSet<VPValue *, 8> OpenIntervals;
187 SmallVector<VPRegisterUsage, 8> RUs(VFs.size());
188 SmallVector<SmallMapVector<unsigned, unsigned, 4>, 8> MaxUsages(VFs.size());
189
190 LLVM_DEBUG(dbgs() << "LV(REG): Calculating max register usage:\n");
191
192 const auto &TTICapture = TTI;
193 auto GetRegUsage = [&TTICapture](Type *Ty, ElementCount VF) -> unsigned {
194 if (Ty->isTokenTy() || !VectorType::isValidElementType(ElemTy: Ty) ||
195 (VF.isScalable() &&
196 !TTICapture.isElementTypeLegalForScalableVector(Ty)))
197 return 0;
198 return TTICapture.getRegUsageForType(Ty: VectorType::get(ElementType: Ty, EC: VF));
199 };
200
201 VPValue *CanIV = LoopRegion->getCanonicalIV();
202 // Note: canonical IVs are retained even if they have no users.
203 if (!CanIV->user_empty())
204 OpenIntervals.insert(Ptr: CanIV);
205
206 // We scan the instructions linearly and record each time that a new interval
207 // starts, by placing it in a set. If we find this value in TransposEnds then
208 // we remove it from the set. The max register usage is the maximum register
209 // usage of the recipes of the set.
210 for (unsigned int Idx = 0, Sz = Idx2Recipe.size(); Idx < Sz; ++Idx) {
211 VPRecipeBase *R = Idx2Recipe[Idx];
212
213 // Remove all of the VPValues that end at this location.
214 VPValueList &List = TransposeEnds[Idx];
215 for (VPValue *ToRemove : List)
216 OpenIntervals.erase(Ptr: ToRemove);
217
218 // Ignore recipes that are never used within the loop and do not have side
219 // effects.
220 if (none_of(Range: R->definedValues(),
221 P: [&Ends](VPValue *Def) { return Ends.count(Ptr: Def); }) &&
222 !R->mayHaveSideEffects())
223 continue;
224
225 // Skip recipes for ephemeral values, i.e. those only feeding assumes. They
226 // are removed before code generation and must not contribute to the
227 // register pressure of the plan.
228 if (EphemeralRecipes.contains(V: R))
229 continue;
230
231 // For each VF find the maximum usage of registers.
232 for (unsigned J = 0, E = VFs.size(); J < E; ++J) {
233 // Count the number of registers used, per register class, given all open
234 // intervals.
235 // Note that elements in this SmallMapVector will be default constructed
236 // as 0. So we can use "RegUsage[ClassID] += n" in the code below even if
237 // there is no previous entry for ClassID.
238 SmallMapVector<unsigned, unsigned, 4> RegUsage;
239
240 for (auto *VPV : OpenIntervals) {
241 // Skip artificial values or values that weren't present in the original
242 // loop.
243 // TODO: Remove skipping values that weren't present in the original
244 // loop after removing the legacy
245 // LoopVectorizationCostModel::calculateRegisterUsage
246 if (isa<VPVectorPointerRecipe, VPVectorEndPointerRecipe,
247 VPBranchOnMaskRecipe>(Val: VPV) ||
248 match(V: VPV, P: m_ExtractLastPart(Op0: m_VPValue())))
249 continue;
250
251 if (VFs[J].isScalar() || VPV == CanIV ||
252 isa<VPReplicateRecipe, VPDerivedIVRecipe,
253 VPCurrentIterationPHIRecipe, VPScalarIVStepsRecipe>(Val: VPV) ||
254 (isa<VPInstruction>(Val: VPV) && vputils::onlyScalarValuesUsed(Def: VPV)) ||
255 (isa<VPReductionPHIRecipe>(Val: VPV) &&
256 (cast<VPReductionPHIRecipe>(Val: VPV))->isInLoop())) {
257 unsigned ClassID =
258 TTI.getRegisterClassForType(Vector: false, Ty: VPV->getScalarType());
259 // FIXME: The target might use more than one register for the type
260 // even in the scalar case.
261 RegUsage[ClassID] += 1;
262 } else {
263 // The output from scaled phis and scaled reductions actually has
264 // fewer lanes than the VF.
265 unsigned ScaleFactor =
266 vputils::getVFScaleFactor(R: VPV->getDefiningRecipe());
267 ElementCount VF = VFs[J];
268 if (ScaleFactor > 1) {
269 VF = VFs[J].divideCoefficientBy(RHS: ScaleFactor);
270 LLVM_DEBUG(dbgs() << "LV(REG): Scaled down VF from " << VFs[J]
271 << " to " << VF << " for " << *R << "\n";);
272 }
273
274 Type *ScalarTy = VPV->getScalarType();
275 unsigned ClassID = TTI.getRegisterClassForType(Vector: true, Ty: ScalarTy);
276 RegUsage[ClassID] += GetRegUsage(ScalarTy, VF);
277 }
278 }
279
280 for (const auto &Pair : RegUsage) {
281 auto &Entry = MaxUsages[J][Pair.first];
282 Entry = std::max(a: Entry, b: Pair.second);
283 }
284 }
285
286 LLVM_DEBUG(dbgs() << "LV(REG): At #" << Idx << " Interval # "
287 << OpenIntervals.size() << '\n');
288
289 // Add used VPValues defined by the current recipe to the list of open
290 // intervals.
291 for (VPValue *DefV : R->definedValues())
292 if (Ends.contains(Ptr: DefV))
293 OpenIntervals.insert(Ptr: DefV);
294 }
295
296 // We also search for instructions that are defined outside the loop, but are
297 // used inside the loop. We need this number separately from the max-interval
298 // usage number because when we unroll, loop-invariant values do not take
299 // more register.
300 VPRegisterUsage RU;
301 for (unsigned Idx = 0, End = VFs.size(); Idx < End; ++Idx) {
302 // Note that elements in this SmallMapVector will be default constructed
303 // as 0. So we can use "Invariant[ClassID] += n" in the code below even if
304 // there is no previous entry for ClassID.
305 SmallMapVector<unsigned, unsigned, 4> Invariant;
306
307 for (auto *In : LoopInvariants) {
308 // FIXME: The target might use more than one register for the type
309 // even in the scalar case.
310 bool IsScalar = vputils::onlyScalarValuesUsed(Def: In);
311
312 ElementCount VF = IsScalar ? ElementCount::getFixed(MinVal: 1) : VFs[Idx];
313 unsigned ClassID =
314 TTI.getRegisterClassForType(Vector: VF.isVector(), Ty: In->getScalarType());
315 Invariant[ClassID] += GetRegUsage(In->getScalarType(), VF);
316 }
317
318 LLVM_DEBUG({
319 dbgs() << "LV(REG): VF = " << VFs[Idx] << '\n';
320 dbgs() << "LV(REG): Found max usage: " << MaxUsages[Idx].size()
321 << " item\n";
322 for (const auto &pair : MaxUsages[Idx]) {
323 dbgs() << "LV(REG): RegisterClass: "
324 << TTI.getRegisterClassName(pair.first) << ", " << pair.second
325 << " registers\n";
326 }
327 dbgs() << "LV(REG): Found invariant usage: " << Invariant.size()
328 << " item\n";
329 for (const auto &pair : Invariant) {
330 dbgs() << "LV(REG): RegisterClass: "
331 << TTI.getRegisterClassName(pair.first) << ", " << pair.second
332 << " registers\n";
333 }
334 });
335
336 RU.LoopInvariantRegs = Invariant;
337 RU.MaxLocalUsers = MaxUsages[Idx];
338 RUs[Idx] = RU;
339 }
340
341 return RUs;
342}
343
344//===----------------------------------------------------------------------===//
345// Outer-loop memory safety analysis.
346//===----------------------------------------------------------------------===//
347
348/// Returns the live-in IR value \p Ptr is based on, looking through GEPs, or
349/// nullptr if there is none.
350static const Value *getBaseObject(VPValue *Ptr) {
351 while (auto *VPI = dyn_cast<VPInstruction>(Val: Ptr)) {
352 if (VPI->getOpcode() != Instruction::GetElementPtr)
353 break;
354 Ptr = VPI->getOperand(N: 0);
355 }
356 auto *IRV = dyn_cast<VPIRValue>(Val: Ptr);
357 return IRV ? IRV->getValue() : nullptr;
358}
359
360/// Returns true if \p ObjA and \p ObjB are known and \p AA proves they don't
361/// alias.
362static bool provablyDistinctObjects(AAResults &AA, const Value *ObjA,
363 const Value *ObjB) {
364 return ObjA && ObjB && AA.isNoAlias(V1: ObjA, V2: ObjB);
365}
366
367/// Returns true if a store of \p StoredTy to \p Addr in \p VPBB writes
368/// different locations on each iteration of \p OuterLoop.
369static bool writesDisjointLocationsPerIteration(VPValue *Addr, Type *StoredTy,
370 VPBasicBlock *VPBB,
371 VPBasicBlock *Latch,
372 const VPDominatorTree &VPDT,
373 PredicatedScalarEvolution &PSE,
374 const Loop *OuterLoop) {
375 // The address cannot repeat if it is an nusw GEP on a live-in base executed
376 // in every iteration, with a single index that does not wrap.
377 auto *GEP = dyn_cast<VPInstruction>(Val: Addr);
378 if (!GEP || GEP->getOpcode() != Instruction::GetElementPtr ||
379 GEP->getNumOperands() != 2 || !isa<VPIRValue>(Val: GEP->getOperand(N: 0)) ||
380 !GEP->getGEPNoWrapFlags().hasNoUnsignedSignedWrap() ||
381 !VPDT.dominates(A: VPBB, B: Latch))
382 return false;
383 auto *Idx = dyn_cast<SCEVAddRecExpr>(
384 Val: vputils::getSCEVExprForVPValue(V: GEP->getOperand(N: 1), PSE, L: OuterLoop));
385 if (!Idx || !Idx->hasNoUnsignedWrap())
386 return false;
387
388 if (hasIrregularType(Ty: StoredTy, DL: Latch->getPlan()->getDataLayout()))
389 return false;
390
391 // Stride != 0 ensures no write-after-write.
392 std::optional<int64_t> Stride =
393 vputils::getConstantStride(Addr, AccessTy: StoredTy, PSE, L: OuterLoop);
394 return Stride && *Stride != 0;
395}
396
397bool llvm::proveOuterLoopMemorySafety(VPlan &Plan,
398 PredicatedScalarEvolution &PSE,
399 AAResults &AA,
400 const VPDominatorTree &VPDT,
401 const Loop *OuterLoop) {
402 SmallVector<const Value *> LoadObjects;
403 SmallVector<const Value *> StoreObjects;
404 auto [Header, Latch] = VPBlockUtils::getPlainCFGHeaderAndLatch(Plan);
405 for (VPBasicBlock *VPBB : vp_rpo_plain_cfg_loop_body(Header)) {
406 for (VPRecipeBase &R : *VPBB) {
407 if (!R.mayReadOrWriteMemory())
408 continue;
409 VPValue *Addr, *StoredVal;
410 if (match(V: &R, P: m_VPInstruction<Instruction::Load>(Ops: m_VPValue(V&: Addr)))) {
411 LoadObjects.push_back(Elt: getBaseObject(Ptr: Addr));
412 continue;
413 }
414 // Bail out on any other memory accesses or write-after-write conflict in
415 // the outer loop.
416 if (!match(V: &R, P: m_VPInstruction<Instruction::Store>(Ops: m_VPValue(V&: StoredVal),
417 Ops: m_VPValue(V&: Addr))) ||
418 !writesDisjointLocationsPerIteration(Addr, StoredTy: StoredVal->getScalarType(),
419 VPBB, Latch, VPDT, PSE,
420 OuterLoop))
421 return false;
422 StoreObjects.push_back(Elt: getBaseObject(Ptr: Addr));
423 }
424 }
425
426 // Stores must access objects not accessed by any other load or store in the
427 // nest.
428 for (auto [I, StoreObj] : enumerate(First&: StoreObjects))
429 for (const Value *Obj : concat<const Value *const>(
430 Ranges: ArrayRef(StoreObjects).drop_front(N: I + 1), Ranges&: LoadObjects))
431 if (!provablyDistinctObjects(AA, ObjA: StoreObj, ObjB: Obj))
432 return false;
433 return true;
434}
435