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