1//===- LoopVectorizationLegality.cpp --------------------------------------===//
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// This file provides loop vectorization legality analysis. Original code
10// resided in LoopVectorize.cpp for a long time.
11//
12// At this point, it is implemented as a utility class, not as an analysis
13// pass. It should be easy to create an analysis pass around it if there
14// is a need (but D45420 needs to happen first).
15//
16
17#include "llvm/Transforms/Vectorize/LoopVectorizationLegality.h"
18#include "LoopVectorizationPlanner.h"
19#include "VectorizeOptions.h"
20#include "llvm/Analysis/AliasAnalysis.h"
21#include "llvm/Analysis/Loads.h"
22#include "llvm/Analysis/LoopInfo.h"
23#include "llvm/Analysis/MustExecute.h"
24#include "llvm/Analysis/OptimizationRemarkEmitter.h"
25#include "llvm/Analysis/ScalarEvolutionExpressions.h"
26#include "llvm/Analysis/ScalarEvolutionPatternMatch.h"
27#include "llvm/Analysis/TargetLibraryInfo.h"
28#include "llvm/Analysis/TargetTransformInfo.h"
29#include "llvm/Analysis/ValueTracking.h"
30#include "llvm/Analysis/VectorUtils.h"
31#include "llvm/IR/Dominators.h"
32#include "llvm/IR/IntrinsicInst.h"
33#include "llvm/IR/PatternMatch.h"
34#include "llvm/Transforms/Utils/SizeOpts.h"
35#include "llvm/Transforms/Vectorize/LoopVectorize.h"
36
37using namespace llvm;
38using namespace PatternMatch;
39using namespace LoopVectorizationUtils;
40
41#define LV_NAME "loop-vectorize"
42#define DEBUG_TYPE LV_NAME
43
44/// Maximum vectorization interleave count.
45static const unsigned MaxInterleaveFactor = 16;
46
47namespace llvm {
48
49bool LoopVectorizeHints::Hint::validate(unsigned Val) {
50 switch (Kind) {
51 case HK_WIDTH:
52 return isPowerOf2_32(Value: Val) && Val <= VectorizerParams::MaxVectorWidth;
53 case HK_INTERLEAVE:
54 return isPowerOf2_32(Value: Val) && Val <= MaxInterleaveFactor;
55 case HK_ISVECTORIZED:
56 return (Val == 0 || Val == 1);
57 }
58 return false;
59}
60
61LoopVectorizeHints::LoopVectorizeHints(const VectorizeOptions &Opts,
62 const Loop *L,
63 bool InterleaveOnlyWhenForced,
64 OptimizationRemarkEmitter &ORE,
65 const TargetTransformInfo *TTI)
66 : Opts(Opts),
67 Width("vectorize.width",
68 VectorizerParams::VectorizationFactor.getKnownMinValue(), HK_WIDTH),
69 Interleave("interleave.count", InterleaveOnlyWhenForced, HK_INTERLEAVE),
70 Force(FK_Undefined), IsVectorized("isvectorized", 0, HK_ISVECTORIZED),
71 Predicate(FK_Undefined), Scalable(SK_Unspecified), TheLoop(L), ORE(ORE) {
72 // Populate values with existing loop metadata.
73 getHintsFromMetadata();
74
75 // force-vector-interleave overrides DisableInterleaving.
76 if (VectorizerParams::isInterleaveForced())
77 Interleave.Value = VectorizerParams::VectorizationInterleave;
78
79 // Decide whether to enable scalable vectorization.
80 auto ComputeScalable =
81 [TTI](ScalableForceKind ForceScalableHint,
82 ScalableForceKind ForceScalableOpt, unsigned ForceWidth,
83 ElementCount ForceWidthOpt) -> ScalableForceKind {
84 // Loop hints have the highest precedence.
85 assert(ForceScalableHint != SK_AlwaysScalable && "Unexpected loop hint.");
86 if (ForceScalableHint == SK_PreferScalable ||
87 ForceScalableHint == SK_FixedWidthOnly)
88 return ForceScalableHint;
89
90 // Then, consider -scalable-vectorization=(always|off|on).
91 if (ForceScalableOpt != SK_Unspecified)
92 return ForceScalableOpt;
93
94 // Then, infer scalability from a preferred VF.
95 if (ForceWidthOpt.isScalable())
96 return SK_AlwaysScalable;
97 if (ForceWidth)
98 return SK_FixedWidthOnly;
99
100 // Finally, listen to TTI.
101 if (TTI && TTI->enableScalableVectorization())
102 return SK_PreferScalable;
103
104 // Preference unspecified, fallback to fixed-length vectorization.
105 return SK_FixedWidthOnly;
106 };
107 Scalable =
108 ComputeScalable(ScalableForceKind(Scalable), Opts.scalable_vectorization,
109 Width.Value, VectorizerParams::VectorizationFactor);
110
111 if (IsVectorized.Value != 1)
112 // If the vectorization width and interleaving count are both 1 then
113 // consider the loop to have been already vectorized because there's
114 // nothing more that we can do.
115 IsVectorized.Value =
116 getWidth() == ElementCount::getFixed(MinVal: 1) && getInterleave() == 1;
117 LLVM_DEBUG(if (InterleaveOnlyWhenForced && getInterleave() == 1) dbgs()
118 << "LV: Interleaving disabled by the pass manager\n");
119}
120
121void LoopVectorizeHints::setAlreadyVectorized() {
122 TheLoop->addIntLoopAttribute(Name: "llvm.loop.isvectorized", Value: 1,
123 RemovePrefixes: {Twine(Prefix(), "vectorize.").str(),
124 Twine(Prefix(), "interleave.").str()});
125
126 // Update internal cache.
127 IsVectorized.Value = 1;
128}
129
130void LoopVectorizeHints::reportDisallowedVectorization(
131 const StringRef DebugMsg, const StringRef RemarkName,
132 const StringRef RemarkMsg, const Loop *L) const {
133 LLVM_DEBUG(dbgs() << "LV: Not vectorizing: " << DebugMsg << ".\n");
134 ORE.emit(OptDiag: OptimizationRemarkMissed(LV_NAME, RemarkName, L->getStartLoc(),
135 L->getHeader())
136 << "loop not vectorized: " << RemarkMsg);
137}
138
139bool LoopVectorizeHints::allowVectorization(
140 Loop *L, bool VectorizeOnlyWhenForced) const {
141 if (getForce() == LoopVectorizeHints::FK_Disabled) {
142 if (Force == LoopVectorizeHints::FK_Disabled) {
143 reportDisallowedVectorization(DebugMsg: "#pragma vectorize disable",
144 RemarkName: "MissedExplicitlyDisabled",
145 RemarkMsg: "vectorization is explicitly disabled", L);
146 } else if (hasDisableAllTransformsHint(L)) {
147 reportDisallowedVectorization(DebugMsg: "loop hasDisableAllTransformsHint",
148 RemarkName: "MissedTransformsDisabled",
149 RemarkMsg: "loop transformations are disabled", L);
150 } else {
151 llvm_unreachable("loop vect disabled for an unknown reason");
152 }
153 return false;
154 }
155
156 if (VectorizeOnlyWhenForced && getForce() != LoopVectorizeHints::FK_Enabled) {
157 reportDisallowedVectorization(
158 DebugMsg: "VectorizeOnlyWhenForced is set, and no #pragma vectorize enable",
159 RemarkName: "MissedForceOnly", RemarkMsg: "only vectorizing loops that explicitly request it",
160 L);
161 return false;
162 }
163
164 if (getIsVectorized() == 1) {
165 LLVM_DEBUG(dbgs() << "LV: Not vectorizing: Disabled/already vectorized.\n");
166 // FIXME: Add interleave.disable metadata. This will allow
167 // vectorize.disable to be used without disabling the pass and errors
168 // to differentiate between disabled vectorization and a width of 1.
169 ORE.emit(RemarkBuilder: [&]() {
170 return OptimizationRemarkAnalysis(LV_NAME, "AllDisabled",
171 L->getStartLoc(), L->getHeader())
172 << "loop not vectorized: vectorization and interleaving are "
173 "explicitly disabled, or the loop has already been "
174 "vectorized";
175 });
176 return false;
177 }
178
179 return true;
180}
181
182void LoopVectorizeHints::emitRemarkWithHints() const {
183 using namespace ore;
184
185 ORE.emit(RemarkBuilder: [&]() {
186 if (Force == LoopVectorizeHints::FK_Disabled)
187 return OptimizationRemarkMissed(LV_NAME, "MissedExplicitlyDisabled",
188 TheLoop->getStartLoc(),
189 TheLoop->getHeader())
190 << "loop not vectorized: vectorization is explicitly disabled";
191
192 OptimizationRemarkMissed R(LV_NAME, "MissedDetails", TheLoop->getStartLoc(),
193 TheLoop->getHeader());
194 R << "loop not vectorized";
195 if (Force == LoopVectorizeHints::FK_Enabled) {
196 R << " (Force=" << NV("Force", true);
197 if (Width.Value != 0)
198 R << ", Vector Width=" << NV("VectorWidth", getWidth());
199 if (getInterleave() != 0)
200 R << ", Interleave Count=" << NV("InterleaveCount", getInterleave());
201 R << ")";
202 }
203 return R;
204 });
205}
206
207bool LoopVectorizeHints::allowReordering() const {
208 // Allow the vectorizer to change the order of operations if enabling
209 // loop hints are provided
210 ElementCount EC = getWidth();
211 return Opts.hints_allow_reordering &&
212 (getForce() == LoopVectorizeHints::FK_Enabled ||
213 EC.getKnownMinValue() > 1);
214}
215
216void LoopVectorizeHints::getHintsFromMetadata() {
217 MDNode *LoopID = TheLoop->getLoopID();
218 if (!LoopID)
219 return;
220
221 // First operand should refer to the loop id itself.
222 assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
223 assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
224
225 for (const MDOperand &MDO : llvm::drop_begin(RangeOrContainer: LoopID->operands())) {
226 const MDString *S = nullptr;
227 SmallVector<Metadata *, 4> Args;
228
229 // The expected hint is either a MDString or a MDNode with the first
230 // operand a MDString.
231 if (const MDNode *MD = dyn_cast<MDNode>(Val: MDO)) {
232 if (!MD || MD->getNumOperands() == 0)
233 continue;
234 S = dyn_cast<MDString>(Val: MD->getOperand(I: 0));
235 for (unsigned Idx = 1; Idx < MD->getNumOperands(); ++Idx)
236 Args.push_back(Elt: MD->getOperand(I: Idx));
237 } else {
238 S = dyn_cast<MDString>(Val: MDO);
239 assert(Args.size() == 0 && "too many arguments for MDString");
240 }
241
242 if (!S)
243 continue;
244
245 // Check if the hint starts with the loop metadata prefix.
246 StringRef Name = S->getString();
247 // The single-operand enable/disable pair carries no argument.
248 if (Args.empty()) {
249 if (Name == "llvm.loop.vectorize.enable")
250 Force = FK_Enabled;
251 else if (Name == "llvm.loop.vectorize.disable")
252 Force = FK_Disabled;
253 else if (Name == "llvm.loop.vectorize.predicate.enable")
254 Predicate = FK_Enabled;
255 else if (Name == "llvm.loop.vectorize.predicate.disable")
256 Predicate = FK_Disabled;
257 else if (Name == "llvm.loop.vectorize.scalable.enable")
258 Scalable = SK_PreferScalable;
259 else if (Name == "llvm.loop.vectorize.scalable.disable")
260 Scalable = SK_FixedWidthOnly;
261 continue;
262 }
263 if (Args.size() == 1)
264 setHint(Name, Arg: Args[0]);
265 }
266}
267
268void LoopVectorizeHints::setHint(StringRef Name, Metadata *Arg) {
269 if (!Name.consume_front(Prefix: Prefix()))
270 return;
271
272 const ConstantInt *C = mdconst::dyn_extract<ConstantInt>(MD&: Arg);
273 if (!C)
274 return;
275 unsigned Val = C->getZExtValue();
276
277 // Force, Predicate, and Scalable are omitted: they are only spelled as
278 // single-operand enable/disable nodes, which never reach setHint().
279 Hint *Hints[] = {&Width, &Interleave, &IsVectorized};
280 for (auto *H : Hints) {
281 if (Name == H->Name) {
282 if (H->validate(Val))
283 H->Value = Val;
284 else
285 LLVM_DEBUG(dbgs() << "LV: ignoring invalid hint '" << Name << "'\n");
286 break;
287 }
288 }
289}
290
291static IntegerType *getInductionIntegerTy(const DataLayout &DL, Type *Ty) {
292 assert(Ty->isIntOrPtrTy() && "Expected integer or pointer type");
293
294 if (Ty->isPointerTy())
295 return DL.getIntPtrType(C&: Ty->getContext(), AddressSpace: Ty->getPointerAddressSpace());
296
297 // It is possible that char's or short's overflow when we ask for the loop's
298 // trip count, work around this by changing the type size.
299 if (Ty->getScalarSizeInBits() < 32)
300 return Type::getInt32Ty(C&: Ty->getContext());
301
302 return cast<IntegerType>(Val: Ty);
303}
304
305static IntegerType *getWiderInductionTy(const DataLayout &DL, Type *Ty0,
306 Type *Ty1) {
307 IntegerType *TyA = getInductionIntegerTy(DL, Ty: Ty0);
308 IntegerType *TyB = getInductionIntegerTy(DL, Ty: Ty1);
309 return TyA->getScalarSizeInBits() > TyB->getScalarSizeInBits() ? TyA : TyB;
310}
311
312/// Returns true if A and B have same pointer operands or same SCEVs addresses
313static bool storeToSameAddress(ScalarEvolution *SE, StoreInst *A,
314 StoreInst *B) {
315 // Compare store
316 if (A == B)
317 return true;
318
319 // Otherwise Compare pointers
320 Value *APtr = A->getPointerOperand();
321 Value *BPtr = B->getPointerOperand();
322 if (APtr == BPtr)
323 return true;
324
325 // Otherwise compare address SCEVs
326 return SE->getSCEV(V: APtr) == SE->getSCEV(V: BPtr);
327}
328
329void LoopVectorizationLegality::collectUnitStridePredicates() const {
330 if (!AllowRuntimeSCEVChecks || !TheLoop->isInnermost())
331 return;
332
333 for (BasicBlock *BB : TheLoop->blocks())
334 for (Instruction &I : *BB)
335 if (Value *Ptr = getLoadStorePointerOperand(V: &I))
336 isConsecutivePtr(AccessTy: getLoadStoreType(I: &I), Ptr);
337}
338
339int LoopVectorizationLegality::isConsecutivePtr(Type *AccessTy,
340 Value *Ptr) const {
341 // FIXME: Currently, the set of symbolic strides is sometimes queried before
342 // it's collected. This happens from canVectorizeWithIfConvert, when the
343 // pointer is checked to reference consecutive elements suitable for a
344 // masked access.
345 // Stride versioning requires adding a SCEV equality predicate; only consult
346 // the symbolic strides when runtime SCEV checks are permitted.
347 const auto &Strides = LAI && AllowRuntimeSCEVChecks
348 ? LAI->getSymbolicStrides()
349 : SymbolicStrideMap();
350 SmallVector<const SCEVPredicate *> Predicates;
351 int Stride = getPtrStride(PSE, AccessTy, Ptr, Lp: TheLoop, DT: *DT, StridesMap: Strides, ShouldCheckWrap: false,
352 Predicates: AllowRuntimeSCEVChecks ? &Predicates : nullptr)
353 .value_or(u: 0);
354 if (Stride != 1 && Stride != -1)
355 return 0;
356 PSE.addPredicates(Preds: Predicates);
357 return Stride;
358}
359
360bool LoopVectorizationLegality::isInvariant(Value *V) const {
361 return LAI->isInvariant(V);
362}
363
364namespace {
365/// A rewriter to build the SCEVs for each of the VF lanes in the expected
366/// vectorized loop, which can then be compared to detect their uniformity. This
367/// is done by replacing the AddRec SCEVs of the original scalar loop (TheLoop)
368/// with new AddRecs where the step is multiplied by StepMultiplier and Offset *
369/// Step is added. Also checks if all sub-expressions are analyzable w.r.t.
370/// uniformity.
371class SCEVAddRecForUniformityRewriter
372 : public SCEVRewriteVisitor<SCEVAddRecForUniformityRewriter> {
373 /// Multiplier to be applied to the step of AddRecs in TheLoop.
374 unsigned StepMultiplier;
375
376 /// Offset to be added to the AddRecs in TheLoop.
377 unsigned Offset;
378
379 /// Loop for which to rewrite AddRecsFor.
380 Loop *TheLoop;
381
382 /// Is any sub-expressions not analyzable w.r.t. uniformity?
383 bool CannotAnalyze = false;
384
385 bool canAnalyze() const { return !CannotAnalyze; }
386
387public:
388 SCEVAddRecForUniformityRewriter(ScalarEvolution &SE, unsigned StepMultiplier,
389 unsigned Offset, Loop *TheLoop)
390 : SCEVRewriteVisitor(SE), StepMultiplier(StepMultiplier), Offset(Offset),
391 TheLoop(TheLoop) {}
392
393 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
394 assert(Expr->getLoop() == TheLoop &&
395 "addrec outside of TheLoop must be invariant and should have been "
396 "handled earlier");
397 // Build a new AddRec by multiplying the step by StepMultiplier and
398 // incrementing the start by Offset * step.
399 Type *Ty = Expr->getType();
400 const SCEV *Step = Expr->getStepRecurrence(SE);
401 if (!SE.isLoopInvariant(S: Step, L: TheLoop)) {
402 CannotAnalyze = true;
403 return Expr;
404 }
405 const SCEV *NewStep =
406 SE.getMulExpr(LHS: Step, RHS: SE.getConstant(Ty, V: StepMultiplier));
407 const SCEV *ScaledOffset = SE.getMulExpr(LHS: Step, RHS: SE.getConstant(Ty, V: Offset));
408 const SCEV *NewStart =
409 SE.getAddExpr(LHS: Expr->getStart(), RHS: SCEVUse(ScaledOffset));
410 return SE.getAddRecExpr(Start: NewStart, Step: NewStep, L: TheLoop, Flags: SCEV::FlagNone);
411 }
412
413 const SCEV *visit(const SCEV *S) {
414 if (CannotAnalyze || SE.isLoopInvariant(S, L: TheLoop))
415 return S;
416 return SCEVRewriteVisitor<SCEVAddRecForUniformityRewriter>::visit(S);
417 }
418
419 const SCEV *visitUnknown(const SCEVUnknown *S) {
420 if (SE.isLoopInvariant(S, L: TheLoop))
421 return S;
422 // The value could vary across iterations.
423 CannotAnalyze = true;
424 return S;
425 }
426
427 const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *S) {
428 // Could not analyze the expression.
429 CannotAnalyze = true;
430 return S;
431 }
432
433 static const SCEV *rewrite(const SCEV *S, ScalarEvolution &SE,
434 unsigned StepMultiplier, unsigned Offset,
435 Loop *TheLoop) {
436 /// Bail out if the expression does not contain an UDiv expression.
437 /// Uniform values which are not loop invariant require operations to strip
438 /// out the lowest bits. For now just look for UDivs and use it to avoid
439 /// re-writing UDIV-free expressions for other lanes to limit compile time.
440 if (!SCEVExprContains(Root: S,
441 Pred: [](const SCEV *S) { return isa<SCEVUDivExpr>(Val: S); }))
442 return SE.getCouldNotCompute();
443
444 SCEVAddRecForUniformityRewriter Rewriter(SE, StepMultiplier, Offset,
445 TheLoop);
446 const SCEV *Result = Rewriter.visit(S);
447
448 if (Rewriter.canAnalyze())
449 return Result;
450 return SE.getCouldNotCompute();
451 }
452};
453
454} // namespace
455
456bool LoopVectorizationLegality::isUniform(
457 Value *V, std::optional<ElementCount> VF) const {
458 if (isInvariant(V))
459 return true;
460 if (!VF || VF->isScalable())
461 return false;
462 if (VF->isScalar())
463 return true;
464
465 // Since we rely on SCEV for uniformity, if the type is not SCEVable, it is
466 // never considered uniform.
467 auto *SE = PSE.getSE();
468 if (!SE->isSCEVable(Ty: V->getType()))
469 return false;
470 const SCEV *S = SE->getSCEV(V);
471
472 // Rewrite AddRecs in TheLoop to step by VF and check if the expression for
473 // lane 0 matches the expressions for all other lanes.
474 unsigned FixedVF = VF->getKnownMinValue();
475 const SCEV *FirstLaneExpr =
476 SCEVAddRecForUniformityRewriter::rewrite(S, SE&: *SE, StepMultiplier: FixedVF, Offset: 0, TheLoop);
477 if (isa<SCEVCouldNotCompute>(Val: FirstLaneExpr))
478 return false;
479
480 // Make sure the expressions for lanes FixedVF-1..1 match the expression for
481 // lane 0. We check lanes in reverse order for compile-time, as frequently
482 // checking the last lane is sufficient to rule out uniformity.
483 return all_of(Range: reverse(C: seq<unsigned>(Begin: 1, End: FixedVF)), P: [&](unsigned I) {
484 const SCEV *IthLaneExpr =
485 SCEVAddRecForUniformityRewriter::rewrite(S, SE&: *SE, StepMultiplier: FixedVF, Offset: I, TheLoop);
486 return FirstLaneExpr == IthLaneExpr;
487 });
488}
489
490bool LoopVectorizationLegality::isUniformMemOp(
491 Instruction &I, std::optional<ElementCount> VF) const {
492 Value *Ptr = getLoadStorePointerOperand(V: &I);
493 if (!Ptr)
494 return false;
495 // Note: There's nothing inherent which prevents predicated loads and
496 // stores from being uniform. The current lowering simply doesn't handle
497 // it; in particular, the cost model distinguishes scatter/gather from
498 // scalar w/predication, and we currently rely on the scalar path.
499 return isUniform(V: Ptr, VF) && !blockNeedsPredication(BB: I.getParent());
500}
501
502/// Returns true if the type produced by \p I can be widened. Casts from vector
503/// types and extractelement instructions cannot be widened. Struct results are
504/// only supported if \p AllowStructCalls is set, for calls whose users are all
505/// extractvalue instructions and whose struct element types can be widened.
506static bool canWidenResultType(const Instruction &I, bool AllowStructCalls) {
507 if (isa<ExtractElementInst>(Val: I) ||
508 (isa<CastInst>(Val: I) &&
509 !VectorType::isValidElementType(ElemTy: I.getOperand(i: 0)->getType())))
510 return false;
511 Type *Ty = I.getType();
512 if (!isa<StructType>(Val: Ty))
513 return canVectorizeTy(Ty);
514 return AllowStructCalls && isa<CallInst>(Val: I) && canVectorizeTy(Ty) &&
515 all_of(Range: I.users(), P: IsaPred<ExtractValueInst>);
516}
517
518/// Returns true if the types produced and stored by \p I can be widened,
519/// otherwise reports a vectorization failure for \p TheLoop and returns false.
520static bool canWidenTypes(Instruction &I, bool AllowStructCalls,
521 OptimizationRemarkEmitter *ORE, Loop *TheLoop) {
522 if (!canWidenResultType(I, AllowStructCalls)) {
523 reportVectorizationFailure(DebugMsg: "Found unvectorizable type",
524 OREMsg: "instruction return type cannot be vectorized",
525 ORETag: "CantVectorizeInstructionReturnType", ORE,
526 TheLoop, I: &I);
527 return false;
528 }
529 auto *SI = dyn_cast<StoreInst>(Val: &I);
530 if (SI && !VectorType::isValidElementType(ElemTy: SI->getValueOperand()->getType())) {
531 reportVectorizationFailure(DebugMsg: "Store instruction cannot be vectorized",
532 ORETag: "CantVectorizeStore", ORE, TheLoop, I: SI);
533 return false;
534 }
535 return true;
536}
537
538/// Returns true if \p I does not use a swifterror value, otherwise reports a
539/// vectorization failure for \p TheLoop and returns false.
540/// TODO: Allow unmasked uniform accesses through loop-invariant swifterror
541/// pointers once memory operations on them are guaranteed to stay scalar.
542static bool canVectorizeSwiftErrorUses(Instruction &I,
543 OptimizationRemarkEmitter *ORE,
544 Loop *TheLoop) {
545 if (none_of(Range: I.operands(), P: [](Value *Op) { return Op->isSwiftError(); }))
546 return true;
547 reportVectorizationFailure(DebugMsg: "Found a use of a swifterror value",
548 OREMsg: "swifterror value cannot be vectorized",
549 ORETag: "CantVectorizeSwiftError", ORE, TheLoop, I: &I);
550 return false;
551}
552
553/// Calls with operand bundles other than llvm.assume cannot be widened.
554static bool canVectorizeOperandBundles(Instruction &I,
555 OptimizationRemarkEmitter *ORE,
556 Loop *TheLoop) {
557 auto *CB = dyn_cast<CallBase>(Val: &I);
558 if (!CB || !CB->hasOperandBundles() || isa<AssumeInst>(Val: CB))
559 return true;
560 reportVectorizationFailure(DebugMsg: "Found a call with operand bundles",
561 OREMsg: "call with operand bundles cannot be vectorized",
562 ORETag: "CantVectorizeOperandBundles", ORE, TheLoop, I: &I);
563 return false;
564}
565
566bool LoopVectorizationLegality::canVectorizeOuterLoop() {
567 assert(!TheLoop->isInnermost() && "We are not vectorizing an outer loop.");
568 // Store the result and return it at the end instead of exiting early, in case
569 // allowExtraAnalysis is used to report multiple reasons for not vectorizing.
570 bool Result = true;
571 bool DoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE);
572
573 for (BasicBlock *BB : TheLoop->blocks()) {
574 // Instructions in the loop nest are widened, so the types they produce and
575 // store must be widenable. Struct-returning calls are not supported yet.
576 // Uses of swifterror values must remain scalar. Calls with operand bundles
577 // cannot be widened.
578 for (Instruction &I : *BB) {
579 if (canWidenTypes(I, /*AllowStructCalls=*/false, ORE, TheLoop) &&
580 canVectorizeSwiftErrorUses(I, ORE, TheLoop) &&
581 canVectorizeOperandBundles(I, ORE, TheLoop))
582 continue;
583 if (!DoExtraAnalysis)
584 return false;
585 Result = false;
586 }
587
588 // Don't try to vectorize outer loops with atomic or volatile accesses.
589 for (Instruction &I : *BB) {
590 if (!I.isAtomic() && !I.isVolatile())
591 continue;
592 reportVectorizationFailure(
593 DebugMsg: "Unsupported volatile or atomic memory operation",
594 OREMsg: "instruction cannot be vectorized", ORETag: "CantVectorizeInstruction", ORE,
595 TheLoop, I: &I);
596 if (DoExtraAnalysis)
597 Result = false;
598 else
599 return false;
600 }
601
602 // Check whether the BB terminator is a branch. Any other terminator is
603 // not supported yet.
604 Instruction *Term = BB->getTerminator();
605 if (!isa<UncondBrInst, CondBrInst>(Val: Term)) {
606 reportVectorizationFailure(
607 DebugMsg: "Unsupported basic block terminator",
608 OREMsg: "loop control flow is not understood by vectorizer",
609 ORETag: "CFGNotUnderstood", ORE, TheLoop);
610 if (DoExtraAnalysis)
611 Result = false;
612 else
613 return false;
614 }
615
616 // Check whether the branch is a supported one. Only unconditional
617 // branches, conditional branches with an outer loop uniform condition or
618 // backedges are supported.
619 // FIXME: We skip these checks when VPlan predication is enabled as we
620 // want to allow divergent branches. This whole check will be removed
621 // once VPlan predication is on by default.
622 auto *Br = dyn_cast<CondBrInst>(Val: Term);
623 if (Br && !TheLoop->isLoopLatch(BB)) {
624 bool IsUniformCondBr = TheLoop->isLoopInvariant(V: Br->getCondition());
625
626 Value *Lhs = nullptr;
627 Value *Rhs = nullptr;
628 auto *SE = PSE.getSE();
629 if (match(V: Br->getCondition(), P: m_c_ICmp(L: m_Value(V&: Lhs), R: m_Value(V&: Rhs))) &&
630 !IsUniformCondBr && SE->isSCEVable(Ty: Lhs->getType())) {
631 const SCEV *LhsExpr = PSE.getSCEV(V: Lhs);
632 const SCEV *RhsExpr = PSE.getSCEV(V: Rhs);
633 IsUniformCondBr |= (SE->isLoopUniform(S: LhsExpr, L: TheLoop) &&
634 SE->isLoopUniform(S: RhsExpr, L: TheLoop));
635 }
636
637 // If the condition is not uniform, report a failure. We currently require
638 // uniform conditions to avoid the complexity of vectorizing divergent
639 // control flow in the outer loop.
640 if (!IsUniformCondBr) {
641 reportVectorizationFailure(
642 DebugMsg: "Outer loop contains divergent conditional branch",
643 OREMsg: "loop control flow is not understood by vectorizer",
644 ORETag: "CFGNotUnderstood", ORE, TheLoop);
645 if (DoExtraAnalysis)
646 Result = false;
647 else
648 return false;
649 }
650 }
651 }
652
653 // Each nested loop must exit via its latch only, as a region with the latch
654 // as its only exiting block is created for it. Note that the branch check
655 // rejects divergent exits, but exits with an outer-loop uniform condition
656 // are allowed through.
657 SmallVector<Loop *, 4> LoopNest = TheLoop->getLoopsInPreorder();
658 for (Loop *Lp : drop_begin(RangeOrContainer&: LoopNest)) {
659 if (Lp->getExitingBlock() != Lp->getLoopLatch()) {
660 reportVectorizationFailure(
661 DebugMsg: "Nested loop does not exit via its latch",
662 OREMsg: "loop control flow is not understood by vectorizer",
663 ORETag: "CFGNotUnderstood", ORE, TheLoop);
664 if (DoExtraAnalysis)
665 Result = false;
666 else
667 return false;
668 }
669 }
670
671 // Check whether we are able to set up outer loop induction.
672 if (!setupOuterLoopInductions()) {
673 reportVectorizationFailure(DebugMsg: "Unsupported outer loop Phi(s)",
674 ORETag: "UnsupportedPhi", ORE, TheLoop);
675 if (DoExtraAnalysis)
676 Result = false;
677 else
678 return false;
679 }
680
681 // Like for inner loops, the widest induction type is used for the canonical
682 // IV and trip count.
683 if (!canDetermineWidestInductionType())
684 return false;
685
686 return Result;
687}
688
689bool LoopVectorizationLegality::canDetermineWidestInductionType() {
690 if (Inductions.empty()) {
691 reportVectorizationFailure(
692 DebugMsg: "Did not find one integer induction var",
693 OREMsg: "loop induction variable could not be identified",
694 ORETag: "NoInductionVariable", ORE, TheLoop);
695 return false;
696 }
697 if (!WidestIndTy) {
698 reportVectorizationFailure(
699 DebugMsg: "Did not find one integer induction var",
700 OREMsg: "integer loop induction variable could not be identified",
701 ORETag: "NoIntegerInductionVariable", ORE, TheLoop);
702 return false;
703 }
704 return true;
705}
706
707void LoopVectorizationLegality::addInductionPhi(PHINode *Phi,
708 const InductionDescriptor &ID) {
709 Inductions[Phi] = ID;
710
711 Type *PhiTy = Phi->getType();
712 const DataLayout &DL = Phi->getDataLayout();
713
714 assert((PhiTy->isIntOrPtrTy() || PhiTy->isFloatingPointTy()) &&
715 "Expected int, ptr, or FP induction phi type");
716
717 // Get the widest type.
718 if (PhiTy->isIntOrPtrTy()) {
719 if (!WidestIndTy)
720 WidestIndTy = getInductionIntegerTy(DL, Ty: PhiTy);
721 else
722 WidestIndTy = getWiderInductionTy(DL, Ty0: PhiTy, Ty1: WidestIndTy);
723 }
724
725 // Int inductions are special because we only allow one IV.
726 if (ID.getKind() == InductionDescriptor::IK_IntInduction &&
727 ID.getConstStepValue() && ID.getConstStepValue()->isOne() &&
728 isa<Constant>(Val: ID.getStartValue()) &&
729 cast<Constant>(Val: ID.getStartValue())->isNullValue()) {
730
731 // Use the phi node with the widest type as induction. Use the last
732 // one if there are multiple (no good reason for doing this other
733 // than it is expedient). We've checked that it begins at zero and
734 // steps by one, so this is a canonical induction variable.
735 if (!PrimaryInduction || PhiTy == WidestIndTy)
736 PrimaryInduction = Phi;
737 }
738
739 LLVM_DEBUG(dbgs() << "LV: Found an induction variable.\n");
740}
741
742bool LoopVectorizationLegality::addConditionalInduction(
743 PHINode *Phi, const ConditionalInductionDescriptor &CondID) {
744 DenseMap<Value *, const SCEVAddRecExpr *> CompressedPtrsForCondID;
745 if (!collectCompressedPtrs(CompressedPtrs&: CompressedPtrsForCondID, L: *TheLoop, CondID,
746 SE&: *PSE.getSE())) {
747 reportVectorizationFailure(
748 DebugMsg: "Unsupported user of conditional induction found",
749 ORETag: "UnsupportedConditionalInductionUse", ORE, TheLoop);
750 return false;
751 }
752
753 ConditionalInductions[Phi] = CondID;
754
755 for (auto [Ptr, PtrAddRec] : CompressedPtrsForCondID) {
756 LLVM_DEBUG(dbgs() << "LV: Found compressed pointer: " << *Ptr << '\n');
757 assert(PtrAddRec->isAffine() && "Expected affine SCEVAddRecExpr");
758 CompressedPtrs[Ptr] = CompressedPtrInfo{.ConditionalInductionPHI: Phi, .PtrSCEV: PtrAddRec};
759 }
760
761 return true;
762}
763
764/// Returns true if \p ID is a pointer induction with a non-constant step. Such
765/// inductions are rejected unless -lv-strided-pointer-ivs is set, to preserve
766/// historical vectorizer behavior after a generalization of the IVDescriptor
767/// code. The intent is to remove this check, but issues around code quality
768/// for such loops have to be fixed first.
769static bool isDisallowedStridedPointerInduction(const InductionDescriptor &ID,
770 const VectorizeOptions &Opts) {
771 if (Opts.lv_strided_pointer_ivs)
772 return false;
773 return ID.getKind() == InductionDescriptor::IK_PtrInduction &&
774 !ID.getConstStepValue();
775}
776
777bool LoopVectorizationLegality::setupOuterLoopInductions() {
778 BasicBlock *Header = TheLoop->getHeader();
779
780 // Returns true if a given Phi is a supported induction.
781 auto IsSupportedPhi = [&](PHINode &Phi) -> bool {
782 InductionDescriptor ID;
783 if (InductionDescriptor::isInductionPHI(Phi: &Phi, L: TheLoop, PSE, D&: ID) &&
784 (ID.getKind() == InductionDescriptor::IK_IntInduction ||
785 ID.getKind() == InductionDescriptor::IK_PtrInduction) &&
786 !isDisallowedStridedPointerInduction(ID, Opts)) {
787 addInductionPhi(Phi: &Phi, ID);
788 return true;
789 }
790 // Bail out for any Phi in the outer loop header that is not a supported
791 // induction.
792 LLVM_DEBUG(
793 dbgs() << "LV: Found unsupported PHI for outer loop vectorization.\n");
794 return false;
795 };
796
797 return llvm::all_of(Range: Header->phis(), P: IsSupportedPhi);
798}
799
800/// Checks if a function is scalarizable according to the TLI, in
801/// the sense that it should be vectorized and then expanded in
802/// multiple scalar calls. This is represented in the
803/// TLI via mappings that do not specify a vector name, as in the
804/// following example:
805///
806/// const VecDesc VecIntrinsics[] = {
807/// {"llvm.phx.abs.i32", "", 4}
808/// };
809static bool isTLIScalarize(const TargetLibraryInfo &TLI, const CallInst &CI) {
810 const StringRef ScalarName = CI.getCalledFunction()->getName();
811 bool Scalarize = TLI.isFunctionVectorizable(F: ScalarName);
812 // Check that all known VFs are not associated to a vector
813 // function, i.e. the vector name is emty.
814 if (Scalarize) {
815 ElementCount WidestFixedVF, WidestScalableVF;
816 TLI.getWidestVF(ScalarF: ScalarName, FixedVF&: WidestFixedVF, ScalableVF&: WidestScalableVF);
817 for (ElementCount VF = ElementCount::getFixed(MinVal: 2);
818 ElementCount::isKnownLE(LHS: VF, RHS: WidestFixedVF); VF *= 2)
819 Scalarize &= !TLI.isFunctionVectorizable(F: ScalarName, VF);
820 for (ElementCount VF = ElementCount::getScalable(MinVal: 1);
821 ElementCount::isKnownLE(LHS: VF, RHS: WidestScalableVF); VF *= 2)
822 Scalarize &= !TLI.isFunctionVectorizable(F: ScalarName, VF);
823 assert((WidestScalableVF.isZero() || !Scalarize) &&
824 "Caller may decide to scalarize a variant using a scalable VF");
825 }
826 return Scalarize;
827}
828
829bool LoopVectorizationLegality::canVectorizeInstrs() {
830 bool DoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE);
831 bool Result = true;
832
833 // For each block in the loop.
834 for (BasicBlock *BB : TheLoop->blocks()) {
835 // Scan the instructions in the block and look for hazards.
836 for (Instruction &I : *BB) {
837 Result &= canVectorizeInstr(I);
838 if (!DoExtraAnalysis && !Result)
839 return false;
840 }
841 }
842
843 if (!PrimaryInduction) {
844 if (!canDetermineWidestInductionType())
845 return false;
846 LLVM_DEBUG(dbgs() << "LV: Did not find one integer induction var.\n");
847 }
848
849 // Now we know the widest induction type, check if our found induction
850 // is the same size. If it's not, unset it here.
851 if (PrimaryInduction && WidestIndTy != PrimaryInduction->getType())
852 PrimaryInduction = nullptr;
853
854 return Result;
855}
856
857bool LoopVectorizationLegality::canVectorizeInstr(Instruction &I) {
858 BasicBlock *BB = I.getParent();
859 BasicBlock *Header = TheLoop->getHeader();
860
861 if (auto *Phi = dyn_cast<PHINode>(Val: &I)) {
862 Type *PhiTy = Phi->getType();
863 // Check that this PHI type is allowed.
864 if (!PhiTy->isIntegerTy() && !PhiTy->isFloatingPointTy() &&
865 !PhiTy->isPointerTy()) {
866 reportVectorizationFailure(
867 DebugMsg: "Found a non-int non-pointer PHI",
868 OREMsg: "loop control flow is not understood by vectorizer",
869 ORETag: "CFGNotUnderstood", ORE, TheLoop);
870 return false;
871 }
872
873 // If this PHINode is not in the header block, then we know that we
874 // can convert it to select during if-conversion. No need to check if
875 // the PHIs in this block are induction or reduction variables.
876 if (BB != Header) {
877 // Non-header phi nodes that have outside uses can be vectorized. Unsafe
878 // cyclic dependencies with header phis are identified during legalization
879 // for reduction, induction and fixed order recurrences.
880 return true;
881 }
882
883 // We only allow if-converted PHIs with exactly two incoming values.
884 if (Phi->getNumIncomingValues() != 2) {
885 reportVectorizationFailure(
886 DebugMsg: "Found an invalid PHI",
887 OREMsg: "loop control flow is not understood by vectorizer",
888 ORETag: "CFGNotUnderstood", ORE, TheLoop, I: Phi);
889 return false;
890 }
891
892 RecurrenceDescriptor RedDes;
893 if (RecurrenceDescriptor::isReductionPHI(Phi, TheLoop, RedDes, DB, AC, DT,
894 SE: PSE.getSE())) {
895 Requirements->addExactFPMathInst(I: RedDes.getExactFPMathInst());
896 Reductions[Phi] = std::move(RedDes);
897 assert((!RedDes.hasUsesOutsideReductionChain() ||
898 RecurrenceDescriptor::isMinMaxRecurrenceKind(
899 RedDes.getRecurrenceKind())) &&
900 "Only min/max recurrences are allowed to have multiple uses "
901 "currently");
902 return true;
903 }
904
905 InductionDescriptor ID;
906 if (InductionDescriptor::isInductionPHI(Phi, L: TheLoop, PSE, D&: ID) &&
907 !isDisallowedStridedPointerInduction(ID, Opts)) {
908 addInductionPhi(Phi, ID);
909 Requirements->addExactFPMathInst(I: ID.getExactFPMathInst());
910 return true;
911 }
912
913 ConditionalInductionDescriptor CondID;
914 if (Opts.lv_compressing_patterns &&
915 ConditionalInductionDescriptor::isConditionalInductionPHI(
916 PN: Phi, L: TheLoop, Desc&: CondID, SE&: *PSE.getSE())) {
917 return addConditionalInduction(Phi, CondID);
918 }
919
920 if (RecurrenceDescriptor::isFixedOrderRecurrence(Phi, TheLoop, DT)) {
921 FixedOrderRecurrences.insert(Ptr: Phi);
922 return true;
923 }
924
925 // As a last resort, coerce the PHI to a AddRec expression
926 // and re-try classifying it a an induction PHI.
927 if (InductionDescriptor::isInductionPHI(Phi, L: TheLoop, PSE, D&: ID, Assume: true) &&
928 !isDisallowedStridedPointerInduction(ID, Opts)) {
929 addInductionPhi(Phi, ID);
930 return true;
931 }
932
933 if (isDisallowedStridedPointerInduction(ID, Opts)) {
934 reportVectorizationFailure(DebugMsg: "Found a disallowed pointer induction",
935 OREMsg: "pointer induction with a non-constant step "
936 "could not be vectorized",
937 ORETag: "StridedPointerInduction", ORE, TheLoop, I: Phi);
938 return false;
939 }
940
941 reportVectorizationFailure(DebugMsg: "Found an unidentified PHI",
942 OREMsg: "value that could not be identified as "
943 "reduction is used outside the loop",
944 ORETag: "NonReductionValueUsedOutsideLoop", ORE, TheLoop,
945 I: Phi);
946 return false;
947 } // end of PHI handling
948
949 if (!canVectorizeSwiftErrorUses(I, ORE, TheLoop) ||
950 !canVectorizeOperandBundles(I, ORE, TheLoop))
951 return false;
952
953 // We handle calls that:
954 // * Have a mapping to an IR intrinsic.
955 // * Have a vector version available.
956 auto *CI = dyn_cast<CallInst>(Val: &I);
957
958 if (CI && !getVectorIntrinsicIDForCall(CI, TLI) &&
959 !(CI->getCalledFunction() && TLI &&
960 (!VFDatabase::getMappings(CI: *CI).empty() || isTLIScalarize(TLI: *TLI, CI: *CI)))) {
961 // If the call is a recognized math libary call, it is likely that
962 // we can vectorize it given loosened floating-point constraints.
963 bool IsMathLibCall =
964 TLI && CI->getCalledFunction() && CI->getType()->isFloatingPointTy() &&
965 TLI->hasOptimizedCodeGen(
966 F: TLI->getLibFunc(funcName: CI->getCalledFunction()->getName()));
967
968 if (IsMathLibCall) {
969 // TODO: Ideally, we should not use clang-specific language here,
970 // but it's hard to provide meaningful yet generic advice.
971 // Also, should this be guarded by allowExtraAnalysis() and/or be part
972 // of the returned info from isFunctionVectorizable()?
973 reportVectorizationFailure(
974 DebugMsg: "Found a non-intrinsic callsite",
975 OREMsg: "library call cannot be vectorized. "
976 "Try compiling with -fno-math-errno, -ffast-math, "
977 "or similar flags",
978 ORETag: "CantVectorizeLibcall", ORE, TheLoop, I: CI);
979 } else {
980 reportVectorizationFailure(DebugMsg: "Found a non-intrinsic callsite",
981 OREMsg: "call instruction cannot be vectorized",
982 ORETag: "CantVectorizeLibcall", ORE, TheLoop, I: CI);
983 }
984 return false;
985 }
986
987 // Some intrinsics have scalar arguments and should be same in order for
988 // them to be vectorized (i.e. loop invariant).
989 if (CI) {
990 auto *SE = PSE.getSE();
991 Intrinsic::ID IntrinID = getVectorIntrinsicIDForCall(CI, TLI);
992 for (unsigned Idx = 0; Idx < CI->arg_size(); ++Idx)
993 if (isVectorIntrinsicWithScalarOpAtArg(ID: IntrinID, ScalarOpdIdx: Idx, TTI)) {
994 if (!SE->isLoopInvariant(S: PSE.getSCEV(V: CI->getOperand(i_nocapture: Idx)), L: TheLoop)) {
995 reportVectorizationFailure(
996 DebugMsg: "Found unvectorizable intrinsic",
997 OREMsg: "intrinsic instruction cannot be vectorized",
998 ORETag: "CantVectorizeIntrinsic", ORE, TheLoop, I: CI);
999 return false;
1000 }
1001 }
1002 }
1003
1004 // If we found a vectorized variant of a function, note that so LV can
1005 // make better decisions about maximum VF.
1006 if (CI && !VFDatabase::getMappings(CI: *CI).empty())
1007 VecCallVariantsFound = true;
1008
1009 // Check that the instruction return and stored types are vectorizable.
1010 if (!canWidenTypes(I, /*AllowStructCalls=*/true, ORE, TheLoop))
1011 return false;
1012
1013 if (auto *ST = dyn_cast<StoreInst>(Val: &I)) {
1014 // For nontemporal stores, check that a nontemporal vector version is
1015 // supported on the target.
1016 if (ST->getMetadata(KindID: LLVMContext::MD_nontemporal)) {
1017 // Arbitrarily try a vector of 2 elements.
1018 auto *VecTy =
1019 FixedVectorType::get(ElementType: ST->getValueOperand()->getType(), /*NumElts=*/2);
1020 assert(VecTy && "did not find vectorized version of stored type");
1021 if (!TTI->isLegalNTStore(DataType: VecTy, Alignment: ST->getAlign())) {
1022 reportVectorizationFailure(
1023 DebugMsg: "nontemporal store instruction cannot be vectorized",
1024 ORETag: "CantVectorizeNontemporalStore", ORE, TheLoop, I: ST);
1025 return false;
1026 }
1027 }
1028
1029 } else if (auto *LD = dyn_cast<LoadInst>(Val: &I)) {
1030 if (LD->getMetadata(KindID: LLVMContext::MD_nontemporal)) {
1031 // For nontemporal loads, check that a nontemporal vector version is
1032 // supported on the target (arbitrarily try a vector of 2 elements).
1033 auto *VecTy = FixedVectorType::get(ElementType: I.getType(), /*NumElts=*/2);
1034 assert(VecTy && "did not find vectorized version of load type");
1035 if (!TTI->isLegalNTLoad(DataType: VecTy, Alignment: LD->getAlign())) {
1036 reportVectorizationFailure(
1037 DebugMsg: "nontemporal load instruction cannot be vectorized",
1038 ORETag: "CantVectorizeNontemporalLoad", ORE, TheLoop, I: LD);
1039 return false;
1040 }
1041 }
1042
1043 // FP instructions can allow unsafe algebra, thus vectorizable by
1044 // non-IEEE-754 compliant SIMD units.
1045 // This applies to floating-point math operations, calls and compares
1046 // other than NaN checks, not memory operations, shuffles, or casts, as they
1047 // don't change precision or semantics.
1048 } else if (((I.getType()->isFloatingPointTy() && (CI || I.isBinaryOp())) ||
1049 (isa<FCmpInst>(Val: I) &&
1050 !is_contained(Set: {FCmpInst::FCMP_ORD, FCmpInst::FCMP_UNO},
1051 Element: cast<FCmpInst>(Val&: I).getPredicate()))) &&
1052 !I.isFast()) {
1053 LLVM_DEBUG(dbgs() << "LV: Found potentially unsafe FP op.\n");
1054 Hints->setPotentiallyUnsafe();
1055 }
1056
1057 return true;
1058}
1059
1060/// Find histogram operations that match high-level code in loops:
1061/// \code
1062/// buckets[indices[i]] = UpdateOp(buckets[indices[i]], Val);
1063/// \endcode
1064/// Where UpdateOp can be add, sub, uadd.sat, umax, or umin.
1065///
1066/// It matches a pattern starting from \p HSt, which Stores to the 'buckets'
1067/// array the computed histogram. It uses an update instruction to update all
1068/// counts, storing them using a loop-variant index Load from the 'indices'
1069/// input array.
1070///
1071/// On successful matches it updates the STATISTIC 'HistogramsDetected',
1072/// regardless of hardware support. When there is support, it additionally
1073/// stores the UpdateOp/Load pairs in \p HistogramCounts, as well the pointers
1074/// used to update histogram in \p HistogramPtrs.
1075static bool findHistogram(LoadInst *LI, StoreInst *HSt, Loop *TheLoop,
1076 const PredicatedScalarEvolution &PSE,
1077 SmallVectorImpl<HistogramInfo> &Histograms) {
1078
1079 // Store value must come from an update operation (binary op or intrinsic).
1080 Instruction *HPtrInstr = nullptr;
1081 Instruction *HUpdateOp = nullptr;
1082 if (!match(V: HSt, P: m_Store(ValueOp: m_Instruction(I&: HUpdateOp), PointerOp: m_Instruction(I&: HPtrInstr))))
1083 return false;
1084
1085 // The update operation must modify the bucket value by a loop invariant
1086 // amount. Supported operations: add, sub, uadd.sat, umax, umin.
1087 // FIXME: We assume the loop invariant term is on the RHS.
1088 // Fine for an immediate/constant, but maybe not a generic value?
1089 Value *HIncVal = nullptr;
1090 HistogramUpdateKind UpdateKind;
1091 auto Bucket = m_Load(Op: m_Specific(V: HPtrInstr));
1092 if (match(V: HUpdateOp, P: m_Add(L: Bucket, R: m_Value(V&: HIncVal))))
1093 UpdateKind = HistogramUpdateKind::Add;
1094 else if (match(V: HUpdateOp, P: m_Sub(L: Bucket, R: m_Value(V&: HIncVal))))
1095 UpdateKind = HistogramUpdateKind::Sub;
1096 else if (match(V: HUpdateOp,
1097 P: m_Intrinsic<Intrinsic::uadd_sat>(Ops: Bucket, Ops: m_Value(V&: HIncVal))))
1098 UpdateKind = HistogramUpdateKind::UAddSat;
1099 else if (match(V: HUpdateOp, P: m_UMax(Op0: Bucket, Op1: m_Value(V&: HIncVal))))
1100 UpdateKind = HistogramUpdateKind::UMax;
1101 else if (match(V: HUpdateOp, P: m_UMin(Op0: Bucket, Op1: m_Value(V&: HIncVal))))
1102 UpdateKind = HistogramUpdateKind::UMin;
1103 else
1104 return false;
1105
1106 // Make sure the increment value is loop invariant.
1107 if (!TheLoop->isLoopInvariant(V: HIncVal))
1108 return false;
1109
1110 // The address to store is calculated through a GEP Instruction.
1111 GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Val: HPtrInstr);
1112 if (!GEP)
1113 return false;
1114
1115 // Restrict address calculation to constant indices except for the last term.
1116 Value *HIdx = nullptr;
1117 for (Value *Index : GEP->indices()) {
1118 if (HIdx)
1119 return false;
1120 if (!isa<ConstantInt>(Val: Index))
1121 HIdx = Index;
1122 }
1123
1124 if (!HIdx)
1125 return false;
1126
1127 // Check that the index is calculated by loading from another array. Ignore
1128 // any extensions.
1129 // FIXME: Support indices from other sources than a linear load from memory?
1130 // We're currently trying to match an operation looping over an array
1131 // of indices, but there could be additional levels of indirection
1132 // in place, or possibly some additional calculation to form the index
1133 // from the loaded data.
1134 Value *VPtrVal;
1135 if (!match(V: HIdx, P: m_ZExtOrSExtOrSelf(Op: m_Load(Op: m_Value(V&: VPtrVal)))))
1136 return false;
1137
1138 // Make sure the index address varies in this loop, not an outer loop.
1139 const auto *AR = dyn_cast<SCEVAddRecExpr>(Val: PSE.getSE()->getSCEV(V: VPtrVal));
1140 if (!AR || AR->getLoop() != TheLoop)
1141 return false;
1142
1143 // Ensure we'll have the same mask by checking that all parts of the histogram
1144 // (gather load, update, scatter store) are in the same block.
1145 LoadInst *IndexedLoad = cast<LoadInst>(Val: HUpdateOp->getOperand(i: 0));
1146 BasicBlock *LdBB = IndexedLoad->getParent();
1147 if (LdBB != HUpdateOp->getParent() || LdBB != HSt->getParent())
1148 return false;
1149
1150 // The bucket value and its update must not be used outside the histogram.
1151 if (!IndexedLoad->hasOneUse() || !HUpdateOp->hasOneUse())
1152 return false;
1153
1154 LLVM_DEBUG(dbgs() << "LV: Found histogram for: " << *HSt << "\n");
1155
1156 // Store the operations that make up the histogram.
1157 Histograms.emplace_back(Args&: IndexedLoad, Args&: HUpdateOp, Args&: HSt, Args&: UpdateKind);
1158 return true;
1159}
1160
1161bool LoopVectorizationLegality::canVectorizeIndirectUnsafeDependences() {
1162 // For now, we only support an IndirectUnsafe dependency that calculates
1163 // a histogram
1164 if (!Opts.enable_histogram_loop_vectorization)
1165 return false;
1166
1167 // Find a single IndirectUnsafe dependency.
1168 const MemoryDepChecker::Dependence *IUDep = nullptr;
1169 const MemoryDepChecker &DepChecker = LAI->getDepChecker();
1170 const auto *Deps = DepChecker.getDependences();
1171 // If there were too many dependences, LAA abandons recording them. We can't
1172 // proceed safely if we don't know what the dependences are.
1173 if (!Deps)
1174 return false;
1175
1176 for (const MemoryDepChecker::Dependence &Dep : *Deps) {
1177 // Ignore dependencies that are either known to be safe or can be
1178 // checked at runtime.
1179 if (MemoryDepChecker::Dependence::isSafeForVectorization(Type: Dep.Type) !=
1180 MemoryDepChecker::VectorizationSafetyStatus::Unsafe)
1181 continue;
1182
1183 // We're only interested in IndirectUnsafe dependencies here, where the
1184 // address might come from a load from memory. We also only want to handle
1185 // one such dependency, at least for now.
1186 if (Dep.Type != MemoryDepChecker::Dependence::IndirectUnsafe || IUDep)
1187 return false;
1188
1189 IUDep = &Dep;
1190 }
1191 if (!IUDep)
1192 return false;
1193
1194 // For now only normal loads and stores are supported.
1195 LoadInst *LI = dyn_cast<LoadInst>(Val: IUDep->getSource(DepChecker));
1196 StoreInst *SI = dyn_cast<StoreInst>(Val: IUDep->getDestination(DepChecker));
1197
1198 if (!LI || !SI)
1199 return false;
1200
1201 LLVM_DEBUG(dbgs() << "LV: Checking for a histogram on: " << *SI << "\n");
1202 return findHistogram(LI, HSt: SI, TheLoop, PSE: LAI->getPSE(), Histograms);
1203}
1204
1205bool LoopVectorizationLegality::canVectorizeMemory() {
1206 LAI = &LAIs.getInfo(L&: *TheLoop);
1207 const OptimizationRemarkAnalysis *LAR = LAI->getReport();
1208 if (LAR) {
1209 ORE->emit(RemarkBuilder: [&]() {
1210 return OptimizationRemarkAnalysis(LV_NAME, "loop not vectorized: ", *LAR);
1211 });
1212 }
1213
1214 // We can vectorize stores to invariant address when final reduction value is
1215 // guaranteed to be stored at the end of the loop. Also, if decision to
1216 // vectorize loop is made, runtime checks are added so as to make sure that
1217 // invariant address won't alias with any other objects.
1218 if (!LAI->getStoresToInvariantAddresses().empty()) {
1219 // For each invariant address, check if last stored value is unconditional
1220 // and the address is not calculated inside the loop.
1221 for (StoreInst *SI : LAI->getStoresToInvariantAddresses()) {
1222 if (!isInvariantStoreOfReduction(SI))
1223 continue;
1224
1225 if (blockNeedsPredication(BB: SI->getParent())) {
1226 reportVectorizationFailure(
1227 DebugMsg: "We don't allow storing to uniform addresses",
1228 OREMsg: "write of conditional recurring variant value to a loop "
1229 "invariant address could not be vectorized",
1230 ORETag: "CantVectorizeStoreToLoopInvariantAddress", ORE, TheLoop);
1231 return false;
1232 }
1233
1234 // Invariant address should be defined outside of loop. LICM pass usually
1235 // makes sure it happens, but in rare cases it does not, we do not want
1236 // to overcomplicate vectorization to support this case.
1237 if (Instruction *Ptr = dyn_cast<Instruction>(Val: SI->getPointerOperand())) {
1238 if (TheLoop->contains(Inst: Ptr)) {
1239 reportVectorizationFailure(
1240 DebugMsg: "Invariant address is calculated inside the loop",
1241 OREMsg: "write to a loop invariant address could not "
1242 "be vectorized",
1243 ORETag: "CantVectorizeStoreToLoopInvariantAddress", ORE, TheLoop);
1244 return false;
1245 }
1246 }
1247 }
1248
1249 if (LAI->hasStoreStoreDependenceInvolvingLoopInvariantAddress()) {
1250 // For each invariant address, check its last stored value is the result
1251 // of one of our reductions.
1252 //
1253 // We do not check if dependence with loads exists because that is already
1254 // checked via hasLoadStoreDependenceInvolvingLoopInvariantAddress.
1255 ScalarEvolution *SE = PSE.getSE();
1256 SmallVector<StoreInst *, 4> UnhandledStores;
1257 for (StoreInst *SI : LAI->getStoresToInvariantAddresses()) {
1258 if (isInvariantStoreOfReduction(SI)) {
1259 // Earlier stores to this address are effectively deadcode.
1260 // With opaque pointers it is possible for one pointer to be used with
1261 // different sizes of stored values:
1262 // store i32 0, ptr %x
1263 // store i8 0, ptr %x
1264 // The latest store doesn't complitely overwrite the first one in the
1265 // example. That is why we have to make sure that types of stored
1266 // values are same.
1267 // TODO: Check that bitwidth of unhandled store is smaller then the
1268 // one that overwrites it and add a test.
1269 erase_if(C&: UnhandledStores, P: [SE, SI](StoreInst *I) {
1270 return storeToSameAddress(SE, A: SI, B: I) &&
1271 I->getValueOperand()->getType() ==
1272 SI->getValueOperand()->getType();
1273 });
1274 continue;
1275 }
1276 UnhandledStores.push_back(Elt: SI);
1277 }
1278
1279 bool IsOK = UnhandledStores.empty();
1280 // TODO: we should also validate against InvariantMemSets.
1281 if (!IsOK) {
1282 reportVectorizationFailure(
1283 DebugMsg: "We don't allow storing to uniform addresses",
1284 OREMsg: "write to a loop invariant address could not "
1285 "be vectorized",
1286 ORETag: "CantVectorizeStoreToLoopInvariantAddress", ORE, TheLoop);
1287 return false;
1288 }
1289 }
1290 }
1291
1292 if (!LAI->canVectorizeMemory()) {
1293 if (hasUncountableExitWithSideEffects()) {
1294 reportVectorizationFailure(
1295 DebugMsg: "Cannot vectorize unsafe dependencies in uncountable exit loop with "
1296 "side effects",
1297 ORETag: "CantVectorizeUnsafeDependencyForEELoopWithSideEffects", ORE,
1298 TheLoop);
1299 return false;
1300 }
1301
1302 return canVectorizeIndirectUnsafeDependences();
1303 }
1304
1305 if (LAI->hasLoadStoreDependenceInvolvingLoopInvariantAddress()) {
1306 reportVectorizationFailure(DebugMsg: "We don't allow storing to uniform addresses",
1307 OREMsg: "write to a loop invariant address could not "
1308 "be vectorized",
1309 ORETag: "CantVectorizeStoreToLoopInvariantAddress", ORE,
1310 TheLoop);
1311 return false;
1312 }
1313
1314 PSE.addPredicate(Pred: LAI->getPSE().getPredicate());
1315 return true;
1316}
1317
1318bool LoopVectorizationLegality::canVectorizeFPMath(
1319 bool EnableStrictReductions) {
1320
1321 // First check if there is any ExactFP math or if we allow reassociations
1322 if (!Requirements->getExactFPInst() || Hints->allowReordering())
1323 return true;
1324
1325 // If the above is false, we have ExactFPMath & do not allow reordering.
1326 // If the EnableStrictReductions flag is set, first check if we have any
1327 // Exact FP induction vars, which we cannot vectorize.
1328 if (!EnableStrictReductions ||
1329 any_of(Range: getInductionVars().values(),
1330 P: [](const InductionDescriptor &IndDesc) -> bool {
1331 return IndDesc.getExactFPMathInst();
1332 }))
1333 return false;
1334
1335 // We can now only vectorize if all reductions with Exact FP math also
1336 // have the isOrdered flag set, which indicates that we can move the
1337 // reduction operations in-loop.
1338 return (all_of(Range: getReductionVars().values(),
1339 P: [](const RecurrenceDescriptor &RdxDesc) -> bool {
1340 return !RdxDesc.hasExactFPMath() || RdxDesc.isOrdered();
1341 }));
1342}
1343
1344bool LoopVectorizationLegality::isInvariantStoreOfReduction(StoreInst *SI) {
1345 return any_of(Range: getReductionVars().values(),
1346 P: [&](const RecurrenceDescriptor &RdxDesc) -> bool {
1347 return RdxDesc.IntermediateStore == SI;
1348 });
1349}
1350
1351bool LoopVectorizationLegality::isInvariantAddressOfReduction(Value *V) {
1352 return any_of(Range: getReductionVars().values(),
1353 P: [&](const RecurrenceDescriptor &RdxDesc) -> bool {
1354 if (!RdxDesc.IntermediateStore)
1355 return false;
1356
1357 ScalarEvolution *SE = PSE.getSE();
1358 Value *InvariantAddress =
1359 RdxDesc.IntermediateStore->getPointerOperand();
1360 return V == InvariantAddress ||
1361 SE->getSCEV(V) == SE->getSCEV(V: InvariantAddress);
1362 });
1363}
1364
1365bool LoopVectorizationLegality::isInductionPhi(const Value *V) const {
1366 Value *In0 = const_cast<Value *>(V);
1367 PHINode *PN = dyn_cast_or_null<PHINode>(Val: In0);
1368 if (!PN)
1369 return false;
1370
1371 return Inductions.count(Key: PN);
1372}
1373
1374bool LoopVectorizationLegality::isFixedOrderRecurrence(
1375 const PHINode *Phi) const {
1376 return FixedOrderRecurrences.count(Ptr: Phi);
1377}
1378
1379bool LoopVectorizationLegality::blockNeedsPredication(
1380 const BasicBlock *BB) const {
1381 BasicBlock *Latch = TheLoop->getLoopLatch();
1382
1383 // Without a latch, we cannot properly answer blockNeedsPredication,
1384 // return early.
1385 if (!Latch) {
1386 assert(ORE->allowExtraAnalysis(DEBUG_TYPE) &&
1387 !canVectorizeLoopCFG(TheLoop, /*UseVPlanNativePath=*/false) &&
1388 "Loop shape should have been rejected by earlier checks");
1389 return false;
1390 }
1391
1392 // When vectorizing early exits, create predicates for the latch block only.
1393 // For a single early exit, it must be a direct predecessor of the latch.
1394 // For multiple early exits, they form a chain where each exiting block
1395 // dominates all subsequent blocks up to the latch.
1396 if (hasUncountableEarlyExit())
1397 return BB == Latch;
1398 return LoopAccessInfo::blockNeedsPredication(BB, TheLoop, DT);
1399}
1400
1401bool LoopVectorizationLegality::blockCanBePredicated(
1402 BasicBlock *BB, SafeAccessesTy &SafeAccesses,
1403 SmallPtrSetImpl<const Instruction *> &MaskedOp) const {
1404 for (Instruction &I : *BB) {
1405 // We can predicate blocks with calls to assume, as long as we drop them in
1406 // case we flatten the CFG via predication.
1407 if (match(V: &I, P: m_Intrinsic<Intrinsic::assume>())) {
1408 MaskedOp.insert(Ptr: &I);
1409 continue;
1410 }
1411
1412 // Do not let llvm.experimental.noalias.scope.decl block the vectorization.
1413 // TODO: there might be cases that it should block the vectorization. Let's
1414 // ignore those for now.
1415 if (isa<NoAliasScopeDeclInst>(Val: &I))
1416 continue;
1417
1418 // We can allow masked calls if there's at least one vector variant, even
1419 // if we end up scalarizing due to the cost model calculations.
1420 // TODO: Allow other calls if they have appropriate attributes... readonly
1421 // and argmemonly?
1422 if (CallInst *CI = dyn_cast<CallInst>(Val: &I))
1423 if (VFDatabase::hasMaskedVariant(CI: *CI)) {
1424 MaskedOp.insert(Ptr: CI);
1425 continue;
1426 }
1427
1428 // Loads are handled via masking (or speculated if safe to do so.)
1429 if (auto *LI = dyn_cast<LoadInst>(Val: &I)) {
1430 auto It = SafeAccesses.find(Val: LI->getPointerOperand());
1431 TypeSize Size = LI->getDataLayout().getTypeStoreSize(Ty: LI->getType());
1432 if (Size.isScalable() || It == SafeAccesses.end() ||
1433 It->second.MaxAlign < LI->getAlign() ||
1434 It->second.MaxSizeInBytes < Size.getFixedValue())
1435 MaskedOp.insert(Ptr: LI);
1436 continue;
1437 }
1438
1439 // Predicated store requires some form of masking:
1440 // 1) masked store HW instruction,
1441 // 2) emulation via load-blend-store (only if safe and legal to do so,
1442 // be aware on the race conditions), or
1443 // 3) element-by-element predicate check and scalar store.
1444 if (auto *SI = dyn_cast<StoreInst>(Val: &I)) {
1445 MaskedOp.insert(Ptr: SI);
1446 continue;
1447 }
1448
1449 if (I.mayReadFromMemory() || I.mayWriteToMemory() || I.mayThrow())
1450 return false;
1451 }
1452
1453 return true;
1454}
1455
1456bool LoopVectorizationLegality::canVectorizeWithIfConvert() {
1457 if (!Opts.enable_if_conversion) {
1458 reportVectorizationFailure(DebugMsg: "If-conversion is disabled",
1459 ORETag: "IfConversionDisabled", ORE, TheLoop);
1460 return false;
1461 }
1462
1463 assert(TheLoop->getNumBlocks() > 1 && "Single block loops are vectorizable");
1464
1465 // Record the maximum fixed access size and alignment known to be safe for
1466 // each pointer in every executed iteration. A conditional load can execute
1467 // unconditionally if its size and alignment do not exceed these bounds.
1468 // Scalable accesses do not establish either size or alignment.
1469 SafeAccessesTy SafeAccesses;
1470 auto RecordSafeAccess = [&SafeAccesses](Instruction &I) {
1471 Value *Ptr = getLoadStorePointerOperand(V: &I);
1472 if (!Ptr)
1473 return;
1474 TypeSize Size = I.getDataLayout().getTypeStoreSize(Ty: getLoadStoreType(I: &I));
1475 if (Size.isScalable())
1476 return;
1477 Align Alignment = getLoadStoreAlignment(I: &I);
1478 auto &Info = SafeAccesses[Ptr];
1479 Info.MaxAlign = std::max(a: Info.MaxAlign, b: Alignment);
1480 Info.MaxSizeInBytes = std::max(a: Info.MaxSizeInBytes, b: Size.getFixedValue());
1481 };
1482
1483 // Collect safe accesses.
1484 for (BasicBlock *BB : TheLoop->blocks()) {
1485 if (!blockNeedsPredication(BB)) {
1486 for (Instruction &I : *BB)
1487 RecordSafeAccess(I);
1488 continue;
1489 }
1490
1491 // For a block which requires predication, a address may be safe to access
1492 // in the loop w/o predication if we can prove dereferenceability facts
1493 // sufficient to ensure it'll never fault within the loop. For the moment,
1494 // we restrict this to loads; stores are more complicated due to
1495 // concurrency restrictions.
1496 ScalarEvolution &SE = *PSE.getSE();
1497 SmallVector<const SCEVPredicate *, 4> Predicates;
1498 for (Instruction &I : *BB) {
1499 LoadInst *LI = dyn_cast<LoadInst>(Val: &I);
1500
1501 // Make sure we can execute all computations feeding into Ptr in the loop
1502 // w/o triggering UB and that none of the out-of-loop operands are poison.
1503 // We do not need to check if operations inside the loop can produce
1504 // poison due to flags (e.g. due to an inbounds GEP going out of bounds),
1505 // because flags will be dropped when executing them unconditionally.
1506 // TODO: Results could be improved by considering poison-propagation
1507 // properties of visited ops.
1508 auto CanSpeculatePointerOp = [this](Value *Ptr) {
1509 SmallVector<Value *> Worklist = {Ptr};
1510 SmallPtrSet<Value *, 4> Visited;
1511 while (!Worklist.empty()) {
1512 Value *CurrV = Worklist.pop_back_val();
1513 if (!Visited.insert(Ptr: CurrV).second)
1514 continue;
1515
1516 auto *CurrI = dyn_cast<Instruction>(Val: CurrV);
1517 if (!CurrI || !TheLoop->contains(Inst: CurrI)) {
1518 BasicBlock *LoopPred = TheLoop->getLoopPredecessor();
1519 Instruction *CtxI = LoopPred ? LoopPred->getTerminator() : nullptr;
1520 assert((CtxI || ORE->allowExtraAnalysis(DEBUG_TYPE)) &&
1521 "Loop with multiple predecessors should have been rejected "
1522 "early.");
1523 // If operands from outside the loop may be poison then Ptr may also
1524 // be poison.
1525 if (!isGuaranteedNotToBePoison(V: CurrV, AC, CtxI, DT))
1526 return false;
1527 continue;
1528 }
1529
1530 // A loaded value may be poison, independent of any flags.
1531 if (isa<LoadInst>(Val: CurrI) && !isGuaranteedNotToBePoison(V: CurrV, AC))
1532 return false;
1533
1534 // For other ops, assume poison can only be introduced via flags,
1535 // which can be dropped.
1536 if (!isa<PHINode>(Val: CurrI) && !isSafeToSpeculativelyExecute(I: CurrI))
1537 return false;
1538 append_range(C&: Worklist, R: CurrI->operands());
1539 }
1540 return true;
1541 };
1542 // Pass the Predicates pointer to isDereferenceableAndAlignedInLoop so
1543 // that it will consider loops that need guarding by SCEV checks. The
1544 // vectoriser will generate these checks if we decide to vectorise.
1545 if (LI && !LI->getType()->isVectorTy() && !mustSuppressSpeculation(LI: *LI) &&
1546 CanSpeculatePointerOp(LI->getPointerOperand()) &&
1547 isDereferenceableAndAlignedInLoop(LI, L: TheLoop, SE, DT&: *DT, AC,
1548 Predicates: &Predicates))
1549 RecordSafeAccess(*LI);
1550 Predicates.clear();
1551 }
1552 }
1553
1554 // Collect the blocks that need predication.
1555 for (BasicBlock *BB : TheLoop->blocks()) {
1556 // We support only branches and switch statements as terminators inside the
1557 // loop.
1558 if (isa<SwitchInst>(Val: BB->getTerminator())) {
1559 if (TheLoop->isLoopExiting(BB)) {
1560 reportVectorizationFailure(DebugMsg: "Loop contains an unsupported switch",
1561 ORETag: "LoopContainsUnsupportedSwitch", ORE,
1562 TheLoop, I: BB->getTerminator());
1563 return false;
1564 }
1565 } else if (!isa<UncondBrInst, CondBrInst>(Val: BB->getTerminator())) {
1566 reportVectorizationFailure(DebugMsg: "Loop contains an unsupported terminator",
1567 ORETag: "LoopContainsUnsupportedTerminator", ORE,
1568 TheLoop, I: BB->getTerminator());
1569 return false;
1570 }
1571
1572 // We must be able to predicate all blocks that need to be predicated.
1573 if (blockNeedsPredication(BB) &&
1574 !blockCanBePredicated(BB, SafeAccesses, MaskedOp&: ConditionallyExecutedOps)) {
1575 reportVectorizationFailure(
1576 DebugMsg: "Control flow cannot be substituted for a select", ORETag: "NoCFGForSelect",
1577 ORE, TheLoop, I: BB->getTerminator());
1578 return false;
1579 }
1580 }
1581
1582 // We can if-convert this loop.
1583 return true;
1584}
1585
1586// Helper function to canVectorizeLoopNestCFG.
1587bool LoopVectorizationLegality::canVectorizeLoopCFG(
1588 Loop *Lp, bool UseVPlanNativePath) const {
1589 assert((UseVPlanNativePath || Lp->isInnermost()) &&
1590 "VPlan-native path is not enabled.");
1591
1592 // TODO: ORE should be improved to show more accurate information when an
1593 // outer loop can't be vectorized because a nested loop is not understood or
1594 // legal. Something like: "outer_loop_location: loop not vectorized:
1595 // (inner_loop_location) loop control flow is not understood by vectorizer".
1596
1597 // Store the result and return it at the end instead of exiting early, in case
1598 // allowExtraAnalysis is used to report multiple reasons for not vectorizing.
1599 bool Result = true;
1600 bool DoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE);
1601
1602 // We must have a loop in canonical form. Loops with indirectbr in them cannot
1603 // be canonicalized. The preheader must also be terminated by an unconditional
1604 // branch, which gets replaced when creating the vector loop.
1605 BasicBlock *Preheader = Lp->getLoopPreheader();
1606 if (!Preheader || !isa<UncondBrInst>(Val: Preheader->getTerminator())) {
1607 reportVectorizationFailure(
1608 DebugMsg: "Loop doesn't have a legal pre-header",
1609 OREMsg: "loop control flow is not understood by vectorizer", ORETag: "CFGNotUnderstood",
1610 ORE, TheLoop);
1611 if (DoExtraAnalysis)
1612 Result = false;
1613 else
1614 return false;
1615 }
1616
1617 // We must have a single backedge.
1618 if (Lp->getNumBackEdges() != 1) {
1619 reportVectorizationFailure(
1620 DebugMsg: "The loop must have a single backedge",
1621 OREMsg: "loop control flow is not understood by vectorizer", ORETag: "CFGNotUnderstood",
1622 ORE, TheLoop);
1623 if (DoExtraAnalysis)
1624 Result = false;
1625 else
1626 return false;
1627 }
1628
1629 // The latch must be terminated by a branch.
1630 BasicBlock *Latch = Lp->getLoopLatch();
1631 if (Latch && !isa<UncondBrInst, CondBrInst>(Val: Latch->getTerminator())) {
1632 reportVectorizationFailure(
1633 DebugMsg: "The loop latch terminator is not a UncondBrInst/CondBrInst",
1634 OREMsg: "loop control flow is not understood by vectorizer", ORETag: "CFGNotUnderstood",
1635 ORE, TheLoop);
1636 if (DoExtraAnalysis)
1637 Result = false;
1638 else
1639 return false;
1640 }
1641
1642 return Result;
1643}
1644
1645bool LoopVectorizationLegality::canVectorizeLoopNestCFG(
1646 Loop *Lp, bool UseVPlanNativePath) {
1647 // Store the result and return it at the end instead of exiting early, in case
1648 // allowExtraAnalysis is used to report multiple reasons for not vectorizing.
1649 bool Result = true;
1650 bool DoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE);
1651 if (!canVectorizeLoopCFG(Lp, UseVPlanNativePath)) {
1652 if (DoExtraAnalysis)
1653 Result = false;
1654 else
1655 return false;
1656 }
1657
1658 // Recursively check whether the loop control flow of nested loops is
1659 // understood.
1660 for (Loop *SubLp : *Lp)
1661 if (!canVectorizeLoopNestCFG(Lp: SubLp, UseVPlanNativePath)) {
1662 if (DoExtraAnalysis)
1663 Result = false;
1664 else
1665 return false;
1666 }
1667
1668 return Result;
1669}
1670
1671/// Matches an exit condition formed by comparing a value loaded from memory
1672/// with another term. Binds the pointer, load, and the other comparison term.
1673static bool matchUncountableExitCondition(Value *Cond, Value *&Ptr,
1674 Instruction *&Load, Value *&Other) {
1675 return match(
1676 V: Cond, P: m_c_Cmp(L: m_Instruction(I&: Load, P: m_Load(Op: m_Value(V&: Ptr))), R: m_Value(V&: Other)));
1677}
1678
1679/// Matches an exit condition formed by comparing the current value of an
1680/// affine add recurrence in the given loop with a stride of 1 against a
1681/// loop-invariant term.
1682static bool matchCountableExitCondition(Value *Cond, ScalarEvolution &SE,
1683 Loop *TheLoop) {
1684 using namespace llvm::SCEVPatternMatch;
1685 Value *IVUpdate, *Limit;
1686 return match(V: Cond, P: m_c_ICmp(L: m_Value(V&: IVUpdate, P: m_Add(L: m_Value(), R: m_Value())),
1687 R: m_Value(V&: Limit))) &&
1688 TheLoop->isLoopInvariant(V: Limit) &&
1689 SCEVPatternMatch::match(S: SE.getSCEV(V: IVUpdate),
1690 P: m_scev_AffineAddRec(Op0: m_SCEV(), Op1: m_scev_One(),
1691 L: m_SpecificLoop(L: TheLoop)));
1692}
1693
1694/// Matches a combined exit condition consisting of an uncountable condition and
1695/// a countable condition, combined by an or. Binds the pointer, load, the
1696/// second comparison term for the uncountable condition, and the comparison for
1697/// the countable condition.
1698static bool matchCombinedExitCondition(Value *Cond, Instruction *&CountableCond,
1699 Value *&Ptr, Instruction *&Load,
1700 Value *&Other, ScalarEvolution &SE,
1701 Loop *TheLoop) {
1702 Value *L, *R;
1703 if (!match(V: Cond, P: m_LogicalOr(L: m_Value(V&: L), R: m_Value(V&: R))))
1704 return false;
1705
1706 if (matchCountableExitCondition(Cond: L, SE, TheLoop) &&
1707 matchUncountableExitCondition(Cond: R, Ptr, Load, Other)) {
1708 CountableCond = cast<Instruction>(Val: L);
1709 return true;
1710 }
1711
1712 if (matchCountableExitCondition(Cond: R, SE, TheLoop) &&
1713 matchUncountableExitCondition(Cond: L, Ptr, Load, Other)) {
1714 CountableCond = cast<Instruction>(Val: R);
1715 return true;
1716 }
1717
1718 return false;
1719}
1720
1721Instruction *
1722LoopVectorizationLegality::findCountableComparisonInCombinedCondition(
1723 Value *Cond) const {
1724 Value *Ptr, *Other;
1725 Instruction *Load, *CountableCmp;
1726 if (matchCombinedExitCondition(Cond, CountableCond&: CountableCmp, Ptr, Load, Other,
1727 SE&: *PSE.getSE(), TheLoop))
1728 return CountableCmp;
1729
1730 return nullptr;
1731}
1732
1733bool LoopVectorizationLegality::isVectorizableEarlyExitLoop() {
1734 BasicBlock *LatchBB = TheLoop->getLoopLatch();
1735 if (!LatchBB) {
1736 reportVectorizationFailure(DebugMsg: "Loop does not have a latch",
1737 OREMsg: "Cannot vectorize early exit loop",
1738 ORETag: "NoLatchEarlyExit", ORE, TheLoop);
1739 return false;
1740 }
1741
1742 if (!FixedOrderRecurrences.empty()) {
1743 reportVectorizationFailure(
1744 DebugMsg: "Found fixed-order recurrences in early-exit loop",
1745 OREMsg: "Cannot vectorize early exit loop with fixed-order recurrences",
1746 ORETag: "RecurrencesInEarlyExitLoop", ORE, TheLoop);
1747 return false;
1748 }
1749
1750 SmallVector<BasicBlock *, 8> ExitingBlocks;
1751 TheLoop->getExitingBlocks(ExitingBlocks);
1752
1753 // Keep a record of all the exiting blocks.
1754 SmallVector<const SCEVPredicate *, 4> Predicates;
1755 SmallVector<BasicBlock *> UncountableExitingBlocks;
1756 for (BasicBlock *BB : ExitingBlocks) {
1757 const SCEV *EC =
1758 PSE.getSE()->getPredicatedExitCount(L: TheLoop, ExitingBlock: BB, Predicates: &Predicates);
1759 if (isa<SCEVCouldNotCompute>(Val: EC)) {
1760 if (size(Range: successors(BB)) != 2) {
1761 reportVectorizationFailure(
1762 DebugMsg: "Early exiting block does not have exactly two successors",
1763 OREMsg: "Incorrect number of successors from early exiting block",
1764 ORETag: "EarlyExitTooManySuccessors", ORE, TheLoop);
1765 return false;
1766 }
1767
1768 UncountableExitingBlocks.push_back(Elt: BB);
1769 } else
1770 CountableExitingBlocks.push_back(Elt: BB);
1771 }
1772 // We can safely ignore the predicates here because when vectorizing the loop
1773 // the PredicatatedScalarEvolution class will keep track of all predicates
1774 // for each exiting block anyway. This happens when calling
1775 // PSE.getSymbolicMaxBackedgeTakenCount() below.
1776 Predicates.clear();
1777
1778 if (UncountableExitingBlocks.empty()) {
1779 LLVM_DEBUG(dbgs() << "LV: Could not find any uncountable exits\n");
1780 return false;
1781 }
1782
1783 // The latch block must have a countable exit.
1784 if (isa<SCEVCouldNotCompute>(Val: PSE.getSE()->getPredicatedExitCount(
1785 L: TheLoop, ExitingBlock: LatchBB, Predicates: &Predicates, Kind: ScalarEvolution::SymbolicMaximum))) {
1786 reportVectorizationFailure(
1787 DebugMsg: "Cannot determine symbolic max exit count for latch block",
1788 OREMsg: "Cannot vectorize early exit loop",
1789 ORETag: "UnknownLatchExitCountEarlyExitLoop", ORE, TheLoop);
1790 return false;
1791 }
1792
1793 if (!is_contained(Range&: CountableExitingBlocks, Element: LatchBB)) {
1794 // If not a separate counted exit in the latch, then check for a combined
1795 // countable and uncountable exit.
1796 auto *Br = dyn_cast<CondBrInst>(Val: LatchBB->getTerminator());
1797 if (!Br ||
1798 !findCountableComparisonInCombinedCondition(Cond: Br->getCondition())) {
1799 reportVectorizationFailure(
1800 DebugMsg: "Latch block does not have a countable exit condition",
1801 ORETag: "NoCountableConditionInLatchBlock", ORE, TheLoop);
1802 return false;
1803 }
1804 }
1805
1806 // Check to see if there are instructions that could potentially generate
1807 // exceptions or have side-effects.
1808 auto IsSafeOperation = [](Instruction *I) -> bool {
1809 switch (I->getOpcode()) {
1810 case Instruction::Load:
1811 case Instruction::Store:
1812 case Instruction::PHI:
1813 case Instruction::UncondBr:
1814 case Instruction::CondBr:
1815 // These are checked separately.
1816 return true;
1817 default:
1818 return isSafeToSpeculativelyExecute(I);
1819 }
1820 };
1821
1822 bool HasSideEffects = false;
1823 for (auto *BB : TheLoop->blocks())
1824 for (auto &I : *BB) {
1825 if (isa<PseudoProbeInst>(Val: I))
1826 continue;
1827 if (I.mayWriteToMemory()) {
1828 if (isa<StoreInst>(Val: &I) && cast<StoreInst>(Val: &I)->isSimple()) {
1829 HasSideEffects = true;
1830 continue;
1831 }
1832
1833 // We don't support complex writes to memory.
1834 reportVectorizationFailure(
1835 DebugMsg: "Complex writes to memory unsupported in early exit loops",
1836 OREMsg: "Cannot vectorize early exit loop with complex writes to memory",
1837 ORETag: "WritesInEarlyExitLoop", ORE, TheLoop);
1838 return false;
1839 }
1840
1841 if (!IsSafeOperation(&I)) {
1842 reportVectorizationFailure(DebugMsg: "Early exit loop contains operations that "
1843 "cannot be speculatively executed",
1844 ORETag: "UnsafeOperationsEarlyExitLoop", ORE,
1845 TheLoop);
1846 return false;
1847 }
1848 }
1849
1850 SmallVector<LoadInst *, 4> NonDerefLoads;
1851 // TODO: Handle loops that may fault.
1852 if (!HasSideEffects) {
1853 // Read-only loop.
1854 Predicates.clear();
1855 if (!isReadOnlyLoop(L: TheLoop, SE: PSE.getSE(), DT, AC, NonDereferenceableAndAlignedLoads&: NonDerefLoads,
1856 Predicates: &Predicates)) {
1857 reportVectorizationFailure(
1858 DebugMsg: "Loop may fault", OREMsg: "Cannot vectorize non-read-only early exit loop",
1859 ORETag: "NonReadOnlyEarlyExitLoop", ORE, TheLoop);
1860 return false;
1861 }
1862 } else {
1863 // Check all uncountable exiting blocks for movable loads.
1864 for (BasicBlock *ExitingBB : UncountableExitingBlocks) {
1865 if (!canUncountableExitConditionLoadBeMoved(ExitingBlock: ExitingBB))
1866 return false;
1867 }
1868 }
1869
1870 // Check non-dereferenceable loads if any.
1871 for (LoadInst *LI : NonDerefLoads) {
1872 // Only support unit-stride access for now.
1873 int Stride = isConsecutivePtr(AccessTy: LI->getType(), Ptr: LI->getPointerOperand());
1874 if (Stride != 1) {
1875 reportVectorizationFailure(
1876 DebugMsg: "Loop contains potentially faulting strided load",
1877 OREMsg: "Cannot vectorize early exit loop with "
1878 "strided fault-only-first load",
1879 ORETag: "EarlyExitLoopWithStridedFaultOnlyFirstLoad", ORE, TheLoop);
1880 return false;
1881 }
1882 }
1883
1884 // We're only handling combined exit conditions via masking at present, which
1885 // is used for loops with side effects.
1886 // TODO: Support readonly loops with combined exit conditions.
1887 // TODO: Decouple style from the presence of side effects.
1888 if (!llvm::is_contained(Range&: CountableExitingBlocks, Element: LatchBB) && !HasSideEffects)
1889 return false;
1890
1891 [[maybe_unused]] const SCEV *SymbolicMaxBTC =
1892 PSE.getSymbolicMaxBackedgeTakenCount();
1893 // Since we have an exact exit count for the latch and the early exit
1894 // dominates the latch, then this should guarantee a computed SCEV value.
1895 assert(!isa<SCEVCouldNotCompute>(SymbolicMaxBTC) &&
1896 "Failed to get symbolic expression for backedge taken count");
1897 LLVM_DEBUG(dbgs() << "LV: Found an early exit loop with symbolic max "
1898 "backedge taken count: "
1899 << *SymbolicMaxBTC << '\n');
1900 UncountableExitType = HasSideEffects ? UncountableExitTrait::ReadWrite
1901 : UncountableExitTrait::ReadOnly;
1902 return true;
1903}
1904
1905bool LoopVectorizationLegality::canUncountableExitConditionLoadBeMoved(
1906 BasicBlock *ExitingBlock) {
1907 // Try to find a load in the critical path for the uncountable exit condition.
1908 // This is currently matching about the simplest form we can, expecting
1909 // only one in-loop load, the result of which is directly compared against
1910 // a loop-invariant value.
1911 auto *Br = cast<CondBrInst>(Val: ExitingBlock->getTerminator());
1912
1913 using namespace llvm::PatternMatch;
1914 Value *Ptr, *Other;
1915 Instruction *L, *CountableCond;
1916 // We want to match either an uncounted condition (loaded value compared
1917 // against a loop invariant value) or the combination (via logical or) of
1918 // an uncounted condition with a counted condition (integer comparison of
1919 // an induction variable for which we can identify an add recurrence within
1920 // this loop).
1921 if (!matchUncountableExitCondition(Cond: Br->getCondition(), Ptr, Load&: L, Other) &&
1922 !matchCombinedExitCondition(Cond: Br->getCondition(), CountableCond, Ptr, Load&: L,
1923 Other, SE&: *PSE.getSE(), TheLoop)) {
1924 reportVectorizationFailure(
1925 DebugMsg: "Early exit loop with store but no supported condition load",
1926 ORETag: "NoConditionLoadForEarlyExitLoop", ORE, TheLoop);
1927 return false;
1928 }
1929
1930 // Bail if the uncountable exit load is compared against a non-invariant
1931 // value.
1932 // TODO: Remove this restriction.
1933 if (!TheLoop->isLoopInvariant(V: Other)) {
1934 reportVectorizationFailure(
1935 DebugMsg: "Early exit loop with store but no supported condition load",
1936 ORETag: "NoConditionLoadForEarlyExitLoop", ORE, TheLoop);
1937 return false;
1938 }
1939
1940 // Make sure that the load address is not loop invariant; we want an
1941 // address calculation that we can rotate to the next vector iteration.
1942 const auto *AR = dyn_cast<SCEVAddRecExpr>(Val: PSE.getSE()->getSCEV(V: Ptr));
1943 if (!AR || AR->getLoop() != TheLoop || !AR->isAffine()) {
1944 reportVectorizationFailure(
1945 DebugMsg: "Uncountable exit condition depends on load with an address that is "
1946 "not an add recurrence in the loop",
1947 ORETag: "EarlyExitLoadInvariantAddress", ORE, TheLoop);
1948 return false;
1949 }
1950
1951 ICFLoopSafetyInfo SafetyInfo(TheLoop);
1952 LoadInst *Load = cast<LoadInst>(Val: L);
1953 // We need to know that load will be executed before we can hoist a
1954 // copy out to run just before the first iteration.
1955 if (!SafetyInfo.isGuaranteedToExecute(Inst: *Load, DT)) {
1956 reportVectorizationFailure(
1957 DebugMsg: "Load for uncountable exit not guaranteed to execute",
1958 ORETag: "ConditionalUncountableExitLoad", ORE, TheLoop);
1959 return false;
1960 }
1961
1962 // Prohibit any potential aliasing with any instruction in the loop which
1963 // might store to memory.
1964 // FIXME: Relax this constraint where possible.
1965 for (auto *BB : TheLoop->blocks()) {
1966 for (auto &I : *BB) {
1967 if (&I == Load)
1968 continue;
1969
1970 // Pseudo-probes are placeholders with no real memory
1971 // access, so they cannot alias the exit condition load and do not need
1972 // to be masked.
1973 if (isa<PseudoProbeInst>(Val: I))
1974 continue;
1975
1976 if (I.mayReadOrWriteMemory()) {
1977 // We need to mask all other memory ops.
1978 ConditionallyExecutedOps.insert(Ptr: &I);
1979 if (isa<LoadInst>(Val: &I))
1980 continue;
1981 if (auto *SI = dyn_cast<StoreInst>(Val: &I)) {
1982 AliasResult AR = AA->alias(V1: Ptr, V2: SI->getPointerOperand());
1983 if (AR == AliasResult::NoAlias)
1984 continue;
1985 }
1986
1987 reportVectorizationFailure(
1988 DebugMsg: "Cannot determine whether critical uncountable exit load address "
1989 "does not alias with a memory write",
1990 ORETag: "CantVectorizeAliasWithCriticalUncountableExitLoad", ORE, TheLoop);
1991 return false;
1992 }
1993 }
1994 }
1995
1996 return true;
1997}
1998
1999bool LoopVectorizationLegality::canVectorize(bool UseVPlanNativePath) {
2000 // Store the result and return it at the end instead of exiting early, in case
2001 // allowExtraAnalysis is used to report multiple reasons for not vectorizing.
2002 bool Result = true;
2003
2004 bool DoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE);
2005 // Check whether the loop-related control flow in the loop nest is expected by
2006 // vectorizer.
2007 if (!canVectorizeLoopNestCFG(Lp: TheLoop, UseVPlanNativePath)) {
2008 if (DoExtraAnalysis) {
2009 LLVM_DEBUG(dbgs() << "LV: legality check failed: loop nest");
2010 Result = false;
2011 } else {
2012 return false;
2013 }
2014 }
2015
2016 // We need to have a loop header.
2017 LLVM_DEBUG(dbgs() << "LV: Found a loop: " << TheLoop->getHeader()->getName()
2018 << '\n');
2019
2020 // Specific checks for outer loops. We skip the remaining legal checks at this
2021 // point because they don't support outer loops.
2022 if (!TheLoop->isInnermost()) {
2023 assert(UseVPlanNativePath && "VPlan-native path is not enabled.");
2024
2025 if (!canVectorizeOuterLoop()) {
2026 reportVectorizationFailure(DebugMsg: "Unsupported outer loop",
2027 ORETag: "UnsupportedOuterLoop", ORE, TheLoop);
2028 // TODO: Implement DoExtraAnalysis when subsequent legal checks support
2029 // outer loops.
2030 return false;
2031 }
2032
2033 LLVM_DEBUG(dbgs() << "LV: We can vectorize this outer loop!\n");
2034 return Result;
2035 }
2036
2037 assert(TheLoop->isInnermost() && "Inner loop expected.");
2038 // Check if we can if-convert non-single-bb loops.
2039 unsigned NumBlocks = TheLoop->getNumBlocks();
2040 if (NumBlocks != 1 && !canVectorizeWithIfConvert()) {
2041 LLVM_DEBUG(dbgs() << "LV: Can't if-convert the loop.\n");
2042 if (DoExtraAnalysis)
2043 Result = false;
2044 else
2045 return false;
2046 }
2047
2048 // Check if we can vectorize the instructions and CFG in this loop.
2049 if (!canVectorizeInstrs()) {
2050 LLVM_DEBUG(dbgs() << "LV: Can't vectorize the instructions or CFG\n");
2051 if (DoExtraAnalysis)
2052 Result = false;
2053 else
2054 return false;
2055 }
2056
2057 if (isa<SCEVCouldNotCompute>(Val: PSE.getBackedgeTakenCount()) &&
2058 !isVectorizableEarlyExitLoop()) {
2059 assert(UncountableExitType == UncountableExitTrait::None &&
2060 "Must be false without vectorizable early-exit loop");
2061 if (TheLoop->getExitingBlock())
2062 reportVectorizationFailure(DebugMsg: "Cannot vectorize uncountable loop",
2063 ORETag: "UnsupportedUncountableLoop", ORE, TheLoop);
2064 if (DoExtraAnalysis)
2065 Result = false;
2066 else
2067 return false;
2068 }
2069
2070 // Go over each instruction and look at memory deps.
2071 if (!canVectorizeMemory()) {
2072 LLVM_DEBUG(dbgs() << "LV: Can't vectorize due to memory conflicts\n");
2073 if (DoExtraAnalysis)
2074 Result = false;
2075 else
2076 return false;
2077 }
2078
2079 // TODO: Remove this restriction, should be straightforward to support.
2080 if (UncountableExitType != UncountableExitTrait::None &&
2081 !LAI->getStoresToInvariantAddresses().empty()) {
2082 LLVM_DEBUG(dbgs() << "LV: Cannot vectorize early exit loops with stores to "
2083 "loop-invariant addresses\n");
2084 reportVectorizationFailure(DebugMsg: "Cannot vectorize early exit loops with stores "
2085 "to loop-invariant addresses",
2086 ORETag: "LoopInvariantStoresInEELoop", ORE, TheLoop);
2087 return false;
2088 }
2089
2090 if (Result) {
2091 LLVM_DEBUG(dbgs() << "LV: Loop passed LoopVectorizationLegality checks"
2092 << (LAI->getRuntimePointerChecking()->Need
2093 ? " (with a runtime bound check)"
2094 : "")
2095 << "!\n");
2096 }
2097
2098 // Okay! We've done all the tests. If any have failed, return false. Otherwise
2099 // we can vectorize, and at this point we don't have any other mem analysis
2100 // which may limit our maximum vectorization factor, so just return true with
2101 // no restrictions.
2102 return Result;
2103}
2104
2105bool LoopVectorizationLegality::canFoldTailByMasking() const {
2106 // The only loops we can vectorize without a scalar epilogue, are loops with
2107 // a bottom-test and a single exiting block. We'd have to handle the fact
2108 // that not every instruction executes on the last iteration. This will
2109 // require a lane mask which varies through the vector loop body. (TODO)
2110 if (TheLoop->getExitingBlock() != TheLoop->getLoopLatch()) {
2111 LLVM_DEBUG(
2112 dbgs()
2113 << "LV: Cannot fold tail by masking. Requires a singe latch exit\n");
2114 return false;
2115 }
2116
2117 // TODO: Support tail folding with uncountable exits.
2118 if (hasUncountableEarlyExit()) {
2119 LLVM_DEBUG(dbgs() << "LV: Cannot tail fold by masking. Loop contains an "
2120 "uncountable early exit.\n");
2121 return false;
2122 }
2123
2124 LLVM_DEBUG(dbgs() << "LV: checking if tail can be folded by masking.\n");
2125
2126 // No accesses are known to be safe in inactive lanes of the folded tail.
2127 SafeAccessesTy SafeAccesses;
2128
2129 // Check all blocks for predication, including those that ordinarily do not
2130 // need predication such as the header block.
2131 SmallPtrSet<const Instruction *, 8> TmpMaskedOp;
2132 for (BasicBlock *BB : TheLoop->blocks()) {
2133 if (!blockCanBePredicated(BB, SafeAccesses, MaskedOp&: TmpMaskedOp)) {
2134 LLVM_DEBUG(dbgs() << "LV: Cannot fold tail by masking.\n");
2135 return false;
2136 }
2137 }
2138
2139 LLVM_DEBUG(dbgs() << "LV: can fold tail by masking.\n");
2140
2141 return true;
2142}
2143
2144void LoopVectorizationLegality::prepareToFoldTailByMasking() {
2145 // No accesses are known to be safe in inactive lanes of the folded tail.
2146 SafeAccessesTy SafeAccesses;
2147
2148 // Mark all blocks for predication, including those that ordinarily do not
2149 // need predication such as the header block, and collect instructions needing
2150 // predication in TailFoldedMaskedOp.
2151 for (BasicBlock *BB : TheLoop->blocks()) {
2152 [[maybe_unused]] bool R =
2153 blockCanBePredicated(BB, SafeAccesses, MaskedOp&: TailFoldedMaskedOp);
2154 assert(R && "Must be able to predicate block when tail-folding.");
2155 }
2156}
2157
2158} // namespace llvm
2159