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