1//===- LoopVectorizationPlanner.cpp - VF selection and planning -----------===//
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/// This file implements VFSelectionContext methods for loop vectorization
11/// VF selection, independent of cost-modeling decisions.
12///
13//===----------------------------------------------------------------------===//
14
15#include "LoopVectorizationPlanner.h"
16#include "VPlanUtils.h"
17#include "llvm/Analysis/LoopInfo.h"
18#include "llvm/Analysis/OptimizationRemarkEmitter.h"
19#include "llvm/Analysis/ScalarEvolution.h"
20#include "llvm/IR/DiagnosticInfo.h"
21#include "llvm/Support/CommandLine.h"
22#include "llvm/Support/Debug.h"
23#include "llvm/Support/MathExtras.h"
24#include "llvm/Transforms/Vectorize/LoopVectorizationLegality.h"
25#include "llvm/Transforms/Vectorize/LoopVectorize.h"
26
27using namespace llvm;
28using namespace LoopVectorizationUtils;
29
30#define DEBUG_TYPE "loop-vectorize"
31
32extern cl::opt<bool> VPlanBuildOuterloopStressTest;
33
34static cl::opt<bool> MaximizeBandwidth(
35 "vectorizer-maximize-bandwidth", cl::init(Val: false), cl::Hidden,
36 cl::desc("Maximize bandwidth when selecting vectorization factor which "
37 "will be determined by the smallest type in loop."));
38
39static cl::opt<bool> UseWiderVFIfCallVariantsPresent(
40 "vectorizer-maximize-bandwidth-for-vector-calls", cl::init(Val: true),
41 cl::Hidden,
42 cl::desc("Try wider VFs if they enable the use of vector variants"));
43
44static cl::opt<bool> ConsiderRegPressure(
45 "vectorizer-consider-reg-pressure", cl::init(Val: false), cl::Hidden,
46 cl::desc("Discard VFs if their register pressure is too high."));
47
48static cl::opt<bool> ForceTargetSupportsScalableVectors(
49 "force-target-supports-scalable-vectors", cl::init(Val: false), cl::Hidden,
50 cl::desc(
51 "Pretend that scalable vectors are supported, even if the target does "
52 "not support them. This flag should only be used for testing."));
53
54cl::opt<bool> llvm::PreferInLoopReductions(
55 "prefer-inloop-reductions", cl::init(Val: false), cl::Hidden,
56 cl::desc("Prefer in-loop vector reductions, "
57 "overriding the targets preference."));
58
59/// Note: This currently only applies to `llvm.masked.load` and
60/// `llvm.masked.store`. TODO: Extend this to cover other operations as needed.
61static cl::opt<bool> ForceTargetSupportsMaskedMemoryOps(
62 "force-target-supports-masked-memory-ops", cl::init(Val: false), cl::Hidden,
63 cl::desc("Assume the target supports masked memory operations (used for "
64 "testing)."));
65
66static cl::opt<bool> ForceTargetSupportsGatherScatterOps(
67 "force-target-supports-gather-scatter-ops", cl::init(Val: false), cl::Hidden,
68 cl::desc("Assume the target supports gather/scatter operations (used for "
69 "testing)."));
70
71static cl::opt<float> ScalableEpilogueVFCostScaleFactor(
72 "scalable-epilogue-vf-cost-scale-factor", cl::init(Val: 2.0), cl::Hidden,
73 cl::desc("Scale the cost of scalable epilogue VFs by this factor."));
74
75/// Write a \p DebugMsg about vectorization to the debug output stream. If \p I
76/// is passed, the message relates to that particular instruction.
77#ifndef NDEBUG
78static void debugVectorizationMessage(const StringRef Prefix,
79 const StringRef DebugMsg,
80 Instruction *I) {
81 dbgs() << "LV: " << Prefix << DebugMsg;
82 if (I != nullptr)
83 dbgs() << " " << *I;
84 else
85 dbgs() << '.';
86 dbgs() << '\n';
87}
88#endif
89
90/// Create an analysis remark that explains why vectorization failed
91/// \p RemarkName is the identifier for the remark. If \p I is passed it is an
92/// instruction that prevents vectorization. Otherwise \p TheLoop is used for
93/// the location of the remark. If \p DL is passed, use it as debug location for
94/// the remark. \return the remark object that can be streamed to.
95static OptimizationRemarkAnalysis createLVAnalysis(StringRef RemarkName,
96 const Loop *TheLoop,
97 Instruction *I,
98 DebugLoc DL = {}) {
99 BasicBlock *CodeRegion = I ? I->getParent() : TheLoop->getHeader();
100 // If debug location is attached to the instruction, use it. Otherwise if DL
101 // was not provided, use the loop's.
102 if (I && I->getDebugLoc())
103 DL = I->getDebugLoc();
104 else if (!DL)
105 DL = TheLoop->getStartLoc();
106
107 return OptimizationRemarkAnalysis(DEBUG_TYPE, RemarkName, DL, CodeRegion);
108}
109
110void LoopVectorizationUtils::reportVectorizationFailure(
111 const StringRef DebugMsg, const StringRef OREMsg, const StringRef ORETag,
112 OptimizationRemarkEmitter *ORE, const Loop *TheLoop, Instruction *I) {
113 LLVM_DEBUG(debugVectorizationMessage("Not vectorizing: ", DebugMsg, I));
114 ORE->emit(OptDiag: createLVAnalysis(RemarkName: ORETag, TheLoop, I)
115 << "loop not vectorized: " << OREMsg);
116}
117
118void LoopVectorizationUtils::reportVectorizationInfo(
119 const StringRef Msg, const StringRef ORETag, OptimizationRemarkEmitter *ORE,
120 const Loop *TheLoop, Instruction *I, DebugLoc DL) {
121 LLVM_DEBUG(debugVectorizationMessage("", Msg, I));
122 ORE->emit(OptDiag: createLVAnalysis(RemarkName: ORETag, TheLoop, I, DL) << Msg);
123}
124
125void LoopVectorizationUtils::reportVectorization(OptimizationRemarkEmitter *ORE,
126 Loop *TheLoop,
127 ElementCount VFWidth,
128 unsigned IC) {
129 LLVM_DEBUG(debugVectorizationMessage(
130 "Vectorizing: ", TheLoop->isInnermost() ? "innermost loop" : "outer loop",
131 nullptr));
132 StringRef LoopType = TheLoop->isInnermost() ? "" : "outer ";
133 ORE->emit(RemarkBuilder: [&]() {
134 return OptimizationRemark(DEBUG_TYPE, "Vectorized", TheLoop->getStartLoc(),
135 TheLoop->getHeader())
136 << "vectorized " << LoopType << "loop (vectorization width: "
137 << ore::NV("VectorizationFactor", VFWidth)
138 << ", interleaved count: " << ore::NV("InterleaveCount", IC) << ")";
139 });
140}
141
142bool VFSelectionContext::isLegalMaskedLoadOrStore(bool IsLoad, Type *ScalarTy,
143 Align Alignment,
144 unsigned AddressSpace) const {
145 return ForceTargetSupportsMaskedMemoryOps ||
146 (IsLoad ? TTI.isLegalMaskedLoad(DataType: ScalarTy, Alignment, AddressSpace)
147 : TTI.isLegalMaskedStore(DataType: ScalarTy, Alignment, AddressSpace));
148}
149
150bool VFSelectionContext::isLegalGatherOrScatter(Value *V,
151 ElementCount VF) const {
152 bool LI = isa<LoadInst>(Val: V);
153 bool SI = isa<StoreInst>(Val: V);
154 if (!LI && !SI)
155 return false;
156 auto *Ty = getLoadStoreType(I: V);
157 Align Align = getLoadStoreAlignment(I: V);
158 if (VF.isVector())
159 Ty = VectorType::get(ElementType: Ty, EC: VF);
160 return ForceTargetSupportsGatherScatterOps ||
161 (LI && TTI.isLegalMaskedGather(DataType: Ty, Alignment: Align)) ||
162 (SI && TTI.isLegalMaskedScatter(DataType: Ty, Alignment: Align));
163}
164
165bool VFSelectionContext::supportsScalableVectors() const {
166 return TTI.supportsScalableVectors() || ForceTargetSupportsScalableVectors ||
167 VectorizerParams::VectorizationFactor.isScalable();
168}
169
170bool VFSelectionContext::useMaxBandwidth(bool IsScalable) const {
171 TargetTransformInfo::RegisterKind RegKind =
172 IsScalable ? TargetTransformInfo::RGK_ScalableVector
173 : TargetTransformInfo::RGK_FixedWidthVector;
174 return MaximizeBandwidth || (MaximizeBandwidth.getNumOccurrences() == 0 &&
175 (TTI.shouldMaximizeVectorBandwidth(K: RegKind) ||
176 (UseWiderVFIfCallVariantsPresent &&
177 Legal->hasVectorCallVariants())));
178}
179
180bool VFSelectionContext::shouldConsiderRegPressureForVF(ElementCount VF) const {
181 if (ConsiderRegPressure.getNumOccurrences())
182 return ConsiderRegPressure;
183
184 // TODO: We should eventually consider register pressure for all targets. The
185 // TTI hook is temporary whilst target-specific issues are being fixed.
186 if (TTI.shouldConsiderVectorizationRegPressure())
187 return true;
188
189 if (!useMaxBandwidth(IsScalable: VF.isScalable()))
190 return false;
191 // Only calculate register pressure for VFs enabled by MaxBandwidth.
192 return ElementCount::isKnownGT(
193 LHS: VF, RHS: VF.isScalable() ? MaxPermissibleVFWithoutMaxBW.ScalableVF
194 : MaxPermissibleVFWithoutMaxBW.FixedVF);
195}
196
197ElementCount VFSelectionContext::clampVFByMaxTripCount(
198 ElementCount VF, unsigned MaxTripCount, unsigned UserIC,
199 bool FoldTailByMasking, bool RequiresScalarEpilogue) const {
200 unsigned EstimatedVF = VF.getKnownMinValue();
201 if (VF.isScalable() && F.hasFnAttribute(Kind: Attribute::VScaleRange)) {
202 auto Attr = F.getFnAttribute(Kind: Attribute::VScaleRange);
203 auto Min = Attr.getVScaleRangeMin();
204 EstimatedVF *= Min;
205 }
206
207 // When a scalar epilogue is required, at least one iteration of the scalar
208 // loop has to execute. Adjust MaxTripCount accordingly to avoid picking a
209 // max VF that results in a dead vector loop.
210 if (MaxTripCount > 0 && RequiresScalarEpilogue)
211 MaxTripCount -= 1;
212
213 // When the user specifies an interleave count, we need to ensure that
214 // VF * UserIC <= MaxTripCount to avoid a dead vector loop.
215 unsigned IC = UserIC > 0 ? UserIC : 1;
216 unsigned EstimatedVFTimesIC = EstimatedVF * IC;
217
218 if (MaxTripCount && MaxTripCount <= EstimatedVFTimesIC &&
219 (!FoldTailByMasking || isPowerOf2_32(Value: MaxTripCount))) {
220 // If upper bound loop trip count (TC) is known at compile time there is no
221 // point in choosing VF greater than TC / IC (as done in the loop below).
222 // Select maximum power of two which doesn't exceed TC / IC. If VF is
223 // scalable, we only fall back on a fixed VF when the TC is less than or
224 // equal to the known number of lanes.
225 auto ClampedUpperTripCount = llvm::bit_floor(Value: MaxTripCount / IC);
226 if (ClampedUpperTripCount == 0)
227 ClampedUpperTripCount = 1;
228 LLVM_DEBUG(dbgs() << "LV: Clamping the MaxVF to maximum power of two not "
229 "exceeding the constant trip count"
230 << (UserIC > 0 ? " divided by UserIC" : "") << ": "
231 << ClampedUpperTripCount << "\n");
232 return ElementCount::get(MinVal: ClampedUpperTripCount,
233 Scalable: FoldTailByMasking ? VF.isScalable() : false);
234 }
235 return VF;
236}
237
238ElementCount VFSelectionContext::getMaximizedVFForTarget(
239 unsigned MaxTripCount, unsigned SmallestType, unsigned WidestType,
240 ElementCount MaxSafeVF, unsigned UserIC, bool FoldTailByMasking,
241 bool RequiresScalarEpilogue) {
242 bool ComputeScalableMaxVF = MaxSafeVF.isScalable();
243 const TypeSize WidestRegister = TTI.getRegisterBitWidth(
244 K: ComputeScalableMaxVF ? TargetTransformInfo::RGK_ScalableVector
245 : TargetTransformInfo::RGK_FixedWidthVector);
246
247 // Convenience function to return the minimum of two ElementCounts.
248 auto MinVF = [](const ElementCount &LHS, const ElementCount &RHS) {
249 assert((LHS.isScalable() == RHS.isScalable()) &&
250 "Scalable flags must match");
251 return ElementCount::isKnownLT(LHS, RHS) ? LHS : RHS;
252 };
253
254 // Ensure MaxVF is a power of 2; the dependence distance bound may not be.
255 // Note that both WidestRegister and WidestType may not be a powers of 2.
256 auto MaxVectorElementCount = ElementCount::get(
257 MinVal: llvm::bit_floor(Value: WidestRegister.getKnownMinValue() / WidestType),
258 Scalable: ComputeScalableMaxVF);
259 MaxVectorElementCount = MinVF(MaxVectorElementCount, MaxSafeVF);
260 LLVM_DEBUG(dbgs() << "LV: The Widest register safe to use is: "
261 << (MaxVectorElementCount * WidestType) << " bits.\n");
262
263 if (!MaxVectorElementCount) {
264 LLVM_DEBUG(dbgs() << "LV: The target has no "
265 << (ComputeScalableMaxVF ? "scalable" : "fixed")
266 << " vector registers.\n");
267 return ElementCount::getFixed(MinVal: 1);
268 }
269
270 ElementCount MaxVF =
271 clampVFByMaxTripCount(VF: MaxVectorElementCount, MaxTripCount, UserIC,
272 FoldTailByMasking, RequiresScalarEpilogue);
273 // If the MaxVF was already clamped, there's no point in trying to pick a
274 // larger one.
275 if (MaxVF != MaxVectorElementCount)
276 return MaxVF;
277
278 if (MaxVF.isScalable())
279 MaxPermissibleVFWithoutMaxBW.ScalableVF = MaxVF;
280 else
281 MaxPermissibleVFWithoutMaxBW.FixedVF = MaxVF;
282
283 if (useMaxBandwidth(IsScalable: ComputeScalableMaxVF)) {
284 auto MaxVectorElementCountMaxBW = ElementCount::get(
285 MinVal: llvm::bit_floor(Value: WidestRegister.getKnownMinValue() / SmallestType),
286 Scalable: ComputeScalableMaxVF);
287 MaxVF = MinVF(MaxVectorElementCountMaxBW, MaxSafeVF);
288
289 if (ElementCount MinVF =
290 TTI.getMinimumVF(ElemWidth: SmallestType, IsScalable: ComputeScalableMaxVF)) {
291 if (ElementCount::isKnownLT(LHS: MaxVF, RHS: MinVF)) {
292 LLVM_DEBUG(dbgs() << "LV: Overriding calculated MaxVF(" << MaxVF
293 << ") with target's minimum: " << MinVF << '\n');
294 MaxVF = MinVF;
295 }
296 }
297
298 MaxVF = clampVFByMaxTripCount(VF: MaxVF, MaxTripCount, UserIC,
299 FoldTailByMasking, RequiresScalarEpilogue);
300 }
301 return MaxVF;
302}
303
304std::optional<unsigned> llvm::getMaxVScale(const Function &F,
305 const TargetTransformInfo &TTI) {
306 if (std::optional<unsigned> MaxVScale = TTI.getMaxVScale())
307 return MaxVScale;
308
309 if (F.hasFnAttribute(Kind: Attribute::VScaleRange))
310 return F.getFnAttribute(Kind: Attribute::VScaleRange).getVScaleRangeMax();
311
312 return std::nullopt;
313}
314
315bool VFSelectionContext::isScalableVectorizationAllowed() {
316 if (IsScalableVectorizationAllowed)
317 return *IsScalableVectorizationAllowed;
318
319 IsScalableVectorizationAllowed = false;
320 if (!supportsScalableVectors())
321 return false;
322
323 if (Hints->isScalableVectorizationDisabled()) {
324 reportVectorizationInfo(Msg: "Scalable vectorization is explicitly disabled",
325 ORETag: "ScalableVectorizationDisabled", ORE, TheLoop);
326 return false;
327 }
328
329 LLVM_DEBUG(dbgs() << "LV: Scalable vectorization is available\n");
330
331 auto MaxScalableVF = ElementCount::getScalable(
332 MinVal: std::numeric_limits<ElementCount::ScalarTy>::max());
333
334 // Test that the loop-vectorizer can legalize all operations for this MaxVF.
335 // FIXME: While for scalable vectors this is currently sufficient, this should
336 // be replaced by a more detailed mechanism that filters out specific VFs,
337 // instead of invalidating vectorization for a whole set of VFs based on the
338 // MaxVF.
339
340 // Disable scalable vectorization if the loop contains unsupported reductions.
341 if (!all_of(Range: Legal->getReductionVars(), P: [&](const auto &Reduction) -> bool {
342 return TTI.isLegalToVectorizeReduction(RdxDesc: Reduction.second, VF: MaxScalableVF);
343 })) {
344 reportVectorizationInfo(
345 Msg: "Scalable vectorization not supported for the reduction "
346 "operations found in this loop.",
347 ORETag: "ScalableVFUnfeasible", ORE, TheLoop);
348 return false;
349 }
350
351 // Disable scalable vectorization if the loop contains any instructions
352 // with element types not supported for scalable vectors.
353 if (any_of(Range&: ElementTypesInLoop, P: [&](Type *Ty) {
354 return !Ty->isVoidTy() && !TTI.isElementTypeLegalForScalableVector(Ty);
355 })) {
356 reportVectorizationInfo(Msg: "Scalable vectorization is not supported "
357 "for all element types found in this loop.",
358 ORETag: "ScalableVFUnfeasible", ORE, TheLoop);
359 return false;
360 }
361
362 if (!Legal->isSafeForAnyVectorWidth() && !getMaxVScale(F, TTI)) {
363 reportVectorizationInfo(Msg: "The target does not provide maximum vscale value "
364 "for safe distance analysis.",
365 ORETag: "ScalableVFUnfeasible", ORE, TheLoop);
366 return false;
367 }
368
369 IsScalableVectorizationAllowed = true;
370 return true;
371}
372
373ElementCount
374VFSelectionContext::getMaxLegalScalableVF(unsigned MaxSafeElements) {
375 if (!isScalableVectorizationAllowed())
376 return ElementCount::getScalable(MinVal: 0);
377
378 auto MaxScalableVF = ElementCount::getScalable(
379 MinVal: std::numeric_limits<ElementCount::ScalarTy>::max());
380 if (Legal->isSafeForAnyVectorWidth())
381 return MaxScalableVF;
382
383 std::optional<unsigned> MaxVScale = getMaxVScale(F, TTI);
384 // Limit MaxScalableVF by the maximum safe dependence distance.
385 MaxScalableVF = ElementCount::getScalable(MinVal: MaxSafeElements / *MaxVScale);
386
387 if (!MaxScalableVF)
388 reportVectorizationInfo(
389 Msg: "Max legal vector width too small, scalable vectorization "
390 "unfeasible.",
391 ORETag: "ScalableVFUnfeasible", ORE, TheLoop);
392
393 return MaxScalableVF;
394}
395
396FixedScalableVFPair VFSelectionContext::computeFeasibleMaxVF(
397 unsigned MaxTripCount, ElementCount UserVF, unsigned UserIC,
398 bool FoldTailByMasking, bool RequiresScalarEpilogue) {
399 auto [SmallestType, WidestType] = getSmallestAndWidestTypes();
400
401 // Get the maximum safe dependence distance in bits computed by LAA.
402 // It is computed by MaxVF * sizeOf(type) * 8, where type is taken from
403 // the memory accesses that is most restrictive (involved in the smallest
404 // dependence distance).
405 unsigned MaxSafeElementsPowerOf2 =
406 llvm::bit_floor(Value: Legal->getMaxSafeVectorWidthInBits() / WidestType);
407 if (!Legal->isSafeForAnyStoreLoadForwardDistances()) {
408 unsigned SLDist = Legal->getMaxStoreLoadForwardSafeDistanceInBits();
409 MaxSafeElementsPowerOf2 =
410 std::min(a: MaxSafeElementsPowerOf2, b: SLDist / WidestType);
411 }
412
413 auto MaxSafeFixedVF = ElementCount::getFixed(MinVal: MaxSafeElementsPowerOf2);
414 auto MaxSafeScalableVF = getMaxLegalScalableVF(MaxSafeElements: MaxSafeElementsPowerOf2);
415
416 if (!Legal->isSafeForAnyVectorWidth())
417 MaxSafeElements = MaxSafeElementsPowerOf2;
418
419 LLVM_DEBUG(dbgs() << "LV: The max safe fixed VF is: " << MaxSafeFixedVF
420 << ".\n");
421 LLVM_DEBUG(dbgs() << "LV: The max safe scalable VF is: " << MaxSafeScalableVF
422 << ".\n");
423
424 // First analyze the UserVF, fall back if the UserVF should be ignored.
425 if (UserVF) {
426 auto MaxSafeUserVF =
427 UserVF.isScalable() ? MaxSafeScalableVF : MaxSafeFixedVF;
428
429 if (ElementCount::isKnownLE(LHS: UserVF, RHS: MaxSafeUserVF)) {
430 // If `VF=vscale x N` is safe, then so is `VF=N`
431 if (UserVF.isScalable())
432 return FixedScalableVFPair(
433 ElementCount::getFixed(MinVal: UserVF.getKnownMinValue()), UserVF);
434
435 return UserVF;
436 }
437
438 assert(ElementCount::isKnownGT(UserVF, MaxSafeUserVF));
439
440 // Only clamp if the UserVF is not scalable. If the UserVF is scalable, it
441 // is better to ignore the hint and let the compiler choose a suitable VF.
442 if (!UserVF.isScalable()) {
443 LLVM_DEBUG(dbgs() << "LV: User VF=" << UserVF
444 << " is unsafe, clamping to max safe VF="
445 << MaxSafeFixedVF << ".\n");
446 ORE->emit(RemarkBuilder: [&]() {
447 return OptimizationRemarkAnalysis(DEBUG_TYPE, "VectorizationFactor",
448 TheLoop->getStartLoc(),
449 TheLoop->getHeader())
450 << "User-specified vectorization factor "
451 << ore::NV("UserVectorizationFactor", UserVF)
452 << " is unsafe, clamping to maximum safe vectorization factor "
453 << ore::NV("VectorizationFactor", MaxSafeFixedVF);
454 });
455 return MaxSafeFixedVF;
456 }
457
458 if (!supportsScalableVectors()) {
459 LLVM_DEBUG(dbgs() << "LV: User VF=" << UserVF
460 << " is ignored because scalable vectors are not "
461 "available.\n");
462 ORE->emit(RemarkBuilder: [&]() {
463 return OptimizationRemarkAnalysis(DEBUG_TYPE, "VectorizationFactor",
464 TheLoop->getStartLoc(),
465 TheLoop->getHeader())
466 << "User-specified vectorization factor "
467 << ore::NV("UserVectorizationFactor", UserVF)
468 << " is ignored because the target does not support scalable "
469 "vectors. The compiler will pick a more suitable value.";
470 });
471 } else {
472 LLVM_DEBUG(dbgs() << "LV: User VF=" << UserVF
473 << " is unsafe. Ignoring scalable UserVF.\n");
474 ORE->emit(RemarkBuilder: [&]() {
475 return OptimizationRemarkAnalysis(DEBUG_TYPE, "VectorizationFactor",
476 TheLoop->getStartLoc(),
477 TheLoop->getHeader())
478 << "User-specified vectorization factor "
479 << ore::NV("UserVectorizationFactor", UserVF)
480 << " is unsafe. Ignoring the hint to let the compiler pick a "
481 "more suitable value.";
482 });
483 }
484 }
485
486 LLVM_DEBUG(dbgs() << "LV: The Smallest and Widest types: " << SmallestType
487 << " / " << WidestType << " bits.\n");
488
489 FixedScalableVFPair Result(ElementCount::getFixed(MinVal: 1),
490 ElementCount::getScalable(MinVal: 0));
491 if (auto MaxVF = getMaximizedVFForTarget(
492 MaxTripCount, SmallestType, WidestType, MaxSafeVF: MaxSafeFixedVF, UserIC,
493 FoldTailByMasking, RequiresScalarEpilogue))
494 Result.FixedVF = MaxVF;
495
496 if (auto MaxVF = getMaximizedVFForTarget(
497 MaxTripCount, SmallestType, WidestType, MaxSafeVF: MaxSafeScalableVF, UserIC,
498 FoldTailByMasking, RequiresScalarEpilogue))
499 if (MaxVF.isScalable()) {
500 Result.ScalableVF = MaxVF;
501 LLVM_DEBUG(dbgs() << "LV: Found feasible scalable VF = " << MaxVF
502 << "\n");
503 }
504
505 return Result;
506}
507
508std::pair<unsigned, unsigned>
509VFSelectionContext::getSmallestAndWidestTypes() const {
510 unsigned MinWidth = -1U;
511 unsigned MaxWidth = 8;
512 const DataLayout &DL = F.getDataLayout();
513 // For in-loop reductions, no element types are added to ElementTypesInLoop
514 // if there are no loads/stores in the loop. In this case, check through the
515 // reduction variables to determine the maximum width.
516 if (ElementTypesInLoop.empty() && !Legal->getReductionVars().empty()) {
517 for (const auto &[_, RdxDesc] : Legal->getReductionVars()) {
518 // When finding the min width used by the recurrence we need to account
519 // for casts on the input operands of the recurrence.
520 MinWidth = std::min(
521 a: MinWidth,
522 b: std::min(a: RdxDesc.getMinWidthCastToRecurrenceTypeInBits(),
523 b: RdxDesc.getRecurrenceType()->getScalarSizeInBits()));
524 MaxWidth = std::max(a: MaxWidth,
525 b: RdxDesc.getRecurrenceType()->getScalarSizeInBits());
526 }
527 } else {
528 for (Type *T : ElementTypesInLoop) {
529 MinWidth = std::min<unsigned>(
530 a: MinWidth, b: DL.getTypeSizeInBits(Ty: T->getScalarType()).getFixedValue());
531 MaxWidth = std::max<unsigned>(
532 a: MaxWidth, b: DL.getTypeSizeInBits(Ty: T->getScalarType()).getFixedValue());
533 }
534 }
535
536 // If the loop has no loads/stores or reductions (e.g. a search loop with an
537 // early exit), MinWidth is never updated and is left at its sentinel value.
538 // Fall back to MaxWidth to keep the SmallestType <= WidestType invariant, so
539 // callers such as the max-bandwidth VF computation don't divide by the
540 // sentinel and collapse the VF to zero.
541 if (MinWidth == -1U)
542 MinWidth = MaxWidth;
543
544 return {MinWidth, MaxWidth};
545}
546
547void VFSelectionContext::collectElementTypesForWidening(
548 const SmallPtrSetImpl<const Value *> *ValuesToIgnore) {
549 ElementTypesInLoop.clear();
550 // For each block.
551 for (BasicBlock *BB : TheLoop->blocks()) {
552 // For each instruction in the loop.
553 for (Instruction &I : *BB) {
554 Type *T = I.getType();
555
556 // Skip ignored values.
557 if (ValuesToIgnore && ValuesToIgnore->contains(Ptr: &I))
558 continue;
559
560 // Only examine Loads, Stores and PHINodes.
561 if (!isa<LoadInst, StoreInst, PHINode>(Val: I))
562 continue;
563
564 // Examine PHI nodes that are reduction variables. Update the type to
565 // account for the recurrence type.
566 if (auto *PN = dyn_cast<PHINode>(Val: &I)) {
567 if (!Legal->isReductionVariable(PN))
568 continue;
569 const RecurrenceDescriptor &RdxDesc =
570 Legal->getRecurrenceDescriptor(PN);
571 if (PreferInLoopReductions || useOrderedReductions(RdxDesc) ||
572 TTI.preferInLoopReduction(Kind: RdxDesc.getRecurrenceKind(),
573 Ty: RdxDesc.getRecurrenceType()))
574 continue;
575 T = RdxDesc.getRecurrenceType();
576 }
577
578 // Examine the stored values.
579 if (auto *ST = dyn_cast<StoreInst>(Val: &I))
580 T = ST->getValueOperand()->getType();
581
582 assert(T->isSized() &&
583 "Expected the load/store/recurrence type to be sized");
584
585 ElementTypesInLoop.insert(Ptr: T);
586 }
587 }
588}
589
590void VFSelectionContext::initializeVScaleForTuning() {
591 if (!supportsScalableVectors())
592 return;
593
594 if (F.hasFnAttribute(Kind: Attribute::VScaleRange)) {
595 auto Attr = F.getFnAttribute(Kind: Attribute::VScaleRange);
596 auto Min = Attr.getVScaleRangeMin();
597 auto Max = Attr.getVScaleRangeMax();
598 if (Max && Min == Max) {
599 VScaleForTuning = Max;
600 return;
601 }
602 }
603
604 VScaleForTuning = TTI.getVScaleForTuning();
605}
606
607bool VFSelectionContext::useOrderedReductions(
608 const RecurrenceDescriptor &RdxDesc) const {
609 return !Hints->allowReordering() && RdxDesc.isOrdered();
610}
611
612bool VFSelectionContext::runtimeChecksRequired() {
613 LLVM_DEBUG(dbgs() << "LV: Performing code size checks.\n");
614
615 Loop *L = const_cast<Loop *>(TheLoop);
616 if (Legal->getRuntimePointerChecking()->Need) {
617 reportVectorizationFailure(
618 DebugMsg: "Runtime ptr check is required with -Os/-Oz",
619 OREMsg: "runtime pointer checks needed. Enable vectorization of this "
620 "loop with '#pragma clang loop vectorize(enable)' when "
621 "compiling with -Os/-Oz",
622 ORETag: "CantVersionLoopWithOptForSize", ORE, TheLoop: L);
623 return true;
624 }
625
626 if (!PSE.getPredicate().isAlwaysTrue()) {
627 reportVectorizationFailure(
628 DebugMsg: "Runtime SCEV check is required with -Os/-Oz",
629 OREMsg: "runtime SCEV checks needed. Enable vectorization of this "
630 "loop with '#pragma clang loop vectorize(enable)' when "
631 "compiling with -Os/-Oz",
632 ORETag: "CantVersionLoopWithOptForSize", ORE, TheLoop: L);
633 return true;
634 }
635
636 // FIXME: Avoid specializing for stride==1 instead of bailing out.
637 if (!Legal->getLAI()->getSymbolicStrides().empty()) {
638 reportVectorizationFailure(
639 DebugMsg: "Runtime stride check for small trip count",
640 OREMsg: "runtime stride == 1 checks needed. Enable vectorization of "
641 "this loop without such check by compiling with -Os/-Oz",
642 ORETag: "CantVersionLoopWithOptForSize", ORE, TheLoop: L);
643 return true;
644 }
645
646 return false;
647}
648
649void VFSelectionContext::computeMinimalBitwidths() {
650 MinBWs = computeMinimumValueSizes(Blocks: TheLoop->getBlocks(), DB&: *DB, TTI: &TTI);
651}
652
653void VFSelectionContext::collectInLoopReductions() {
654 // Avoid duplicating work finding in-loop reductions.
655 if (!InLoopReductions.empty())
656 return;
657
658 for (const auto &Reduction : Legal->getReductionVars()) {
659 PHINode *Phi = Reduction.first;
660 const RecurrenceDescriptor &RdxDesc = Reduction.second;
661
662 // Multi-use reductions (e.g., used in FindLastIV patterns) are handled
663 // separately and should not be considered for in-loop reductions.
664 if (RdxDesc.hasUsesOutsideReductionChain())
665 continue;
666
667 // We don't collect reductions that are type promoted (yet).
668 if (RdxDesc.getRecurrenceType() != Phi->getType())
669 continue;
670
671 // In-loop AnyOf and FindIV reductions are not yet supported.
672 RecurKind Kind = RdxDesc.getRecurrenceKind();
673 if (RecurrenceDescriptor::isAnyOfRecurrenceKind(Kind) ||
674 RecurrenceDescriptor::isFindIVRecurrenceKind(Kind) ||
675 RecurrenceDescriptor::isFindLastRecurrenceKind(Kind))
676 continue;
677
678 // If the target would prefer this reduction to happen "in-loop", then we
679 // want to record it as such.
680 if (!PreferInLoopReductions && !useOrderedReductions(RdxDesc) &&
681 !TTI.preferInLoopReduction(Kind, Ty: Phi->getType()))
682 continue;
683
684 // Check that we can correctly put the reductions into the loop, by
685 // finding the chain of operations that leads from the phi to the loop
686 // exit value.
687 SmallVector<Instruction *, 4> ReductionOperations =
688 RdxDesc.getReductionOpChain(Phi, L: const_cast<Loop *>(TheLoop));
689 bool InLoop = !ReductionOperations.empty();
690
691 if (InLoop) {
692 InLoopReductions.insert(Ptr: Phi);
693 // Add the elements to InLoopReductionImmediateChains for cost modelling.
694 Instruction *LastChain = Phi;
695 for (auto *I : ReductionOperations) {
696 InLoopReductionImmediateChains[I] = LastChain;
697 LastChain = I;
698 }
699 }
700 LLVM_DEBUG(dbgs() << "LV: Using " << (InLoop ? "inloop" : "out of loop")
701 << " reduction for phi: " << *Phi << "\n");
702 }
703}
704
705bool LoopVectorizationPlanner::isMoreProfitable(const VectorizationFactor &A,
706 const VectorizationFactor &B,
707 const unsigned MaxTripCount,
708 bool HasTail,
709 bool IsEpilogue) const {
710 InstructionCost CostA = A.Cost;
711 InstructionCost CostB = B.Cost;
712
713 // When there is a hint to always prefer scalable vectors, honour that hint.
714 if (Config.getHints().isScalableVectorizationAlwaysPreferred())
715 if (A.Width.isScalable() && CostA.isValid() && !B.Width.isScalable() &&
716 !B.Width.isScalar())
717 return true;
718
719 // Favor fixed VFs for epilogue loops by scaling the costs of scalable VFs
720 // 'ScalableEpilogueVFCostScaleFactor' (default 2.0). This is intended to
721 // model that fixed VFs are more likely to be fully unrolled (or optimized
722 // out) post vectorization. TODO: Reconsider this restriction for predicated
723 // epilogues (once supported).
724 if (IsEpilogue && A.Width.isScalable() != B.Width.isScalable() &&
725 A.Cost.isValid() && B.Cost.isValid()) {
726 auto [FixedCost, ScalableCost] = std::make_pair(x&: CostA, y&: CostB);
727 if (B.Width.isFixed())
728 std::swap(a&: FixedCost, b&: ScalableCost);
729
730 ScalableCost *= ScalableEpilogueVFCostScaleFactor;
731
732 if (FixedCost <= ScalableCost)
733 return A.Width.isFixed();
734 }
735
736 // Improve estimate for the vector width if it is scalable.
737 unsigned EstimatedWidthA = A.Width.getKnownMinValue();
738 unsigned EstimatedWidthB = B.Width.getKnownMinValue();
739 if (std::optional<unsigned> VScale = Config.getVScaleForTuning()) {
740 if (A.Width.isScalable())
741 EstimatedWidthA *= *VScale;
742 if (B.Width.isScalable())
743 EstimatedWidthB *= *VScale;
744 }
745
746 // When optimizing for size choose whichever is smallest, which will be the
747 // one with the smallest cost for the whole loop. On a tie pick the larger
748 // vector width, on the assumption that throughput will be greater.
749 if (Config.CostKind == TTI::TCK_CodeSize)
750 return CostA < CostB ||
751 (CostA == CostB && EstimatedWidthA > EstimatedWidthB);
752
753 // Assume vscale may be larger than 1 (or the value being tuned for),
754 // so that scalable vectorization is slightly favorable over fixed-width
755 // vectorization.
756 bool PreferScalable = !TTI.preferFixedOverScalableIfEqualCost() &&
757 A.Width.isScalable() && !B.Width.isScalable();
758
759 auto CmpFn = [PreferScalable](const InstructionCost &LHS,
760 const InstructionCost &RHS) {
761 return PreferScalable ? LHS <= RHS : LHS < RHS;
762 };
763
764 // To avoid the need for FP division:
765 // (CostA / EstimatedWidthA) < (CostB / EstimatedWidthB)
766 // <=> (CostA * EstimatedWidthB) < (CostB * EstimatedWidthA)
767 bool LowerCostWithoutTC =
768 CmpFn(CostA * EstimatedWidthB, CostB * EstimatedWidthA);
769 if (!MaxTripCount)
770 return LowerCostWithoutTC;
771
772 auto GetCostForTC = [MaxTripCount, HasTail](unsigned VF,
773 InstructionCost VectorCost,
774 InstructionCost ScalarCost) {
775 // If the trip count is a known (possibly small) constant, the trip count
776 // will be rounded up to an integer number of iterations under
777 // FoldTailByMasking. The total cost in that case will be
778 // VecCost*ceil(TripCount/VF). When not folding the tail, the total
779 // cost will be VecCost*floor(TC/VF) + ScalarCost*(TC%VF). There will be
780 // some extra overheads, but for the purpose of comparing the costs of
781 // different VFs we can use this to compare the total loop-body cost
782 // expected after vectorization.
783 if (HasTail)
784 return VectorCost * (MaxTripCount / VF) +
785 ScalarCost * (MaxTripCount % VF);
786 return VectorCost * divideCeil(Numerator: MaxTripCount, Denominator: VF);
787 };
788
789 auto RTCostA = GetCostForTC(EstimatedWidthA, CostA, A.ScalarCost);
790 auto RTCostB = GetCostForTC(EstimatedWidthB, CostB, B.ScalarCost);
791 bool LowerCostWithTC = CmpFn(RTCostA, RTCostB);
792 LLVM_DEBUG(if (LowerCostWithTC != LowerCostWithoutTC) {
793 dbgs() << "LV: VF " << (LowerCostWithTC ? A.Width : B.Width)
794 << " has lower cost than VF "
795 << (LowerCostWithTC ? B.Width : A.Width)
796 << " when taking the cost of the remaining scalar loop iterations "
797 "into consideration for a maximum trip count of "
798 << MaxTripCount << ".\n";
799 });
800 return LowerCostWithTC;
801}
802
803bool LoopVectorizationPlanner::isMoreProfitable(const VectorizationFactor &A,
804 const VectorizationFactor &B,
805 bool HasTail,
806 bool IsEpilogue) const {
807 const unsigned MaxTripCount = PSE.getSmallConstantMaxTripCount();
808 return LoopVectorizationPlanner::isMoreProfitable(A, B, MaxTripCount, HasTail,
809 IsEpilogue);
810}
811
812// TODO: we could return a pair of values that specify the max VF and
813// min VF, to be used in `buildVPlans(MinVF, MaxVF)` instead of
814// `buildVPlans(VF, VF)`. We cannot do it because VPLAN at the moment
815// doesn't have a cost model that can choose which plan to execute if
816// more than one is generated.
817FixedScalableVFPair
818VFSelectionContext::computeVPlanOuterloopVF(ElementCount UserVF) {
819 if (UserVF.isScalable() && !supportsScalableVectors()) {
820 reportVectorizationFailure(
821 DebugMsg: "Scalable vectorization requested but not supported by the target",
822 OREMsg: "the scalable user-specified vectorization width for outer-loop "
823 "vectorization cannot be used because the target does not support "
824 "scalable vectors.",
825 ORETag: "ScalableVFUnfeasible", ORE, TheLoop);
826 return FixedScalableVFPair::getNone();
827 }
828
829 ElementCount VF = UserVF;
830 if (VF.isZero()) {
831 auto [_, WidestType] = getSmallestAndWidestTypes();
832
833 auto RegKind = TTI.enableScalableVectorization()
834 ? TargetTransformInfo::RGK_ScalableVector
835 : TargetTransformInfo::RGK_FixedWidthVector;
836
837 TypeSize RegSize = TTI.getRegisterBitWidth(K: RegKind);
838 // The widest type may be wider than the register width and WidestType may
839 // not be a power of two; round the element count down to a power of two.
840 unsigned N = std::max<uint64_t>(
841 a: 1, b: llvm::bit_floor(Value: RegSize.getKnownMinValue() / WidestType));
842 VF = ElementCount::get(MinVal: N, Scalable: RegSize.isScalable());
843 LLVM_DEBUG(dbgs() << "LV: VPlan computed VF " << VF << ".\n");
844
845 // Make sure we have a VF > 1 for stress testing.
846 if (VPlanBuildOuterloopStressTest && VF.isScalar()) {
847 LLVM_DEBUG(dbgs() << "LV: VPlan stress testing: "
848 << "overriding computed VF.\n");
849 VF = ElementCount::getFixed(MinVal: 4);
850 }
851 }
852 assert(isPowerOf2_32(VF.getKnownMinValue()) &&
853 "VF needs to be a power of two");
854 if (VF.isScalar())
855 return FixedScalableVFPair::getNone();
856 LLVM_DEBUG(dbgs() << "LV: Using " << (!UserVF.isZero() ? "user " : "")
857 << "VF " << VF << " to build VPlans.\n");
858 return FixedScalableVFPair(VF);
859}
860
861/// \returns true if the VPlan contains header phi recipes that are not
862/// currently supported for epilogue vectorization.
863static bool hasUnsupportedHeaderPhiRecipe(VPlan &Plan) {
864 return any_of(
865 Range: Plan.getVectorLoopRegion()->getEntryBasicBlock()->phis(),
866 P: [](VPRecipeBase &R) {
867 switch (R.getVPRecipeID()) {
868 case VPRecipeBase::VPFirstOrderRecurrencePHISC:
869 // TODO: Add support for fixed-order recurrences.
870 return true;
871 case VPRecipeBase::VPWidenIntOrFpInductionSC:
872 return !cast<VPWidenIntOrFpInductionRecipe>(Val: &R)->getPHINode();
873 case VPRecipeBase::VPReductionPHISC: {
874 auto *RedPhi = cast<VPReductionPHIRecipe>(Val: &R);
875 // TODO: Support FMinNum/FMaxNum, FindLast reductions, and reductions
876 // without underlying values.
877 RecurKind Kind = RedPhi->getRecurrenceKind();
878 if (RecurrenceDescriptor::isFPMinMaxNumRecurrenceKind(Kind) ||
879 RecurrenceDescriptor::isFindLastRecurrenceKind(Kind) ||
880 !RedPhi->getUnderlyingValue())
881 return true;
882 // TODO: Add support for FindIV reductions with sunk expressions: the
883 // resume value from the main loop is in expression domain (e.g.,
884 // mul(ReducedIV, 3)), but the epilogue tracks raw IV values. A sunk
885 // expression is identified by a non-VPInstruction user of
886 // ComputeReductionResult.
887 if (RecurrenceDescriptor::isFindIVRecurrenceKind(Kind)) {
888 auto *RdxResult = vputils::findComputeReductionResult(PhiR: RedPhi);
889 assert(RdxResult &&
890 "FindIV reduction must have ComputeReductionResult");
891 return any_of(Range: RdxResult->users(),
892 P: std::not_fn(fn: IsaPred<VPInstruction>));
893 }
894 return false;
895 }
896 default:
897 return false;
898 };
899 });
900}
901
902bool LoopVectorizationPlanner::isCandidateForEpilogueVectorization(
903 VPlan &MainPlan) const {
904 // Bail out if the plan contains header phi recipes not yet supported
905 // for epilogue vectorization.
906 if (hasUnsupportedHeaderPhiRecipe(Plan&: MainPlan))
907 return false;
908
909 // Epilogue vectorization code has not been auditted to ensure it handles
910 // non-latch exits properly. It may be fine, but it needs auditted and
911 // tested.
912 // TODO: Add support for loops with an early exit.
913 if (OrigLoop->getExitingBlock() != OrigLoop->getLoopLatch())
914 return false;
915
916 return true;
917}
918