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