1 //===- LoopVectorizationLegality.cpp --------------------------------------===//
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
7 //===----------------------------------------------------------------------===//
9 // This file provides loop vectorization legality analysis. Original code
10 // resided in LoopVectorize.cpp for a long time.
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).
17 #include "llvm/Transforms/Vectorize/LoopVectorizationLegality.h"
18 #include "llvm/Analysis/Loads.h"
19 #include "llvm/Analysis/LoopInfo.h"
20 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
21 #include "llvm/Analysis/TargetLibraryInfo.h"
22 #include "llvm/Analysis/TargetTransformInfo.h"
23 #include "llvm/Analysis/ValueTracking.h"
24 #include "llvm/Analysis/VectorUtils.h"
25 #include "llvm/IR/IntrinsicInst.h"
26 #include "llvm/IR/PatternMatch.h"
27 #include "llvm/Transforms/Utils/SizeOpts.h"
28 #include "llvm/Transforms/Vectorize/LoopVectorize.h"
31 using namespace PatternMatch;
33 #define LV_NAME "loop-vectorize"
34 #define DEBUG_TYPE LV_NAME
37 EnableIfConversion("enable-if-conversion", cl::init(true), cl::Hidden,
38 cl::desc("Enable if-conversion during vectorization."));
42 HintsAllowReordering("hints-allow-reordering", cl::init(true), cl::Hidden,
43 cl::desc("Allow enabling loop hints to reorder "
44 "FP operations during vectorization."));
47 // TODO: Move size-based thresholds out of legality checking, make cost based
48 // decisions instead of hard thresholds.
49 static cl::opt<unsigned> VectorizeSCEVCheckThreshold(
50 "vectorize-scev-check-threshold", cl::init(16), cl::Hidden,
51 cl::desc("The maximum number of SCEV checks allowed."));
53 static cl::opt<unsigned> PragmaVectorizeSCEVCheckThreshold(
54 "pragma-vectorize-scev-check-threshold", cl::init(128), cl::Hidden,
55 cl::desc("The maximum number of SCEV checks allowed with a "
56 "vectorize(enable) pragma"));
58 static cl::opt<LoopVectorizeHints::ScalableForceKind>
59 ForceScalableVectorization(
60 "scalable-vectorization", cl::init(LoopVectorizeHints::SK_Unspecified),
62 cl::desc("Control whether the compiler can use scalable vectors to "
65 clEnumValN(LoopVectorizeHints::SK_FixedWidthOnly, "off",
66 "Scalable vectorization is disabled."),
68 LoopVectorizeHints::SK_PreferScalable, "preferred",
69 "Scalable vectorization is available and favored when the "
70 "cost is inconclusive."),
72 LoopVectorizeHints::SK_PreferScalable, "on",
73 "Scalable vectorization is available and favored when the "
74 "cost is inconclusive.")));
76 /// Maximum vectorization interleave count.
77 static const unsigned MaxInterleaveFactor = 16;
81 bool LoopVectorizeHints::Hint::validate(unsigned Val) {
84 return isPowerOf2_32(Val) && Val <= VectorizerParams::MaxVectorWidth;
86 return isPowerOf2_32(Val) && Val <= MaxInterleaveFactor;
92 return (Val == 0 || Val == 1);
97 LoopVectorizeHints::LoopVectorizeHints(const Loop *L,
98 bool InterleaveOnlyWhenForced,
99 OptimizationRemarkEmitter &ORE,
100 const TargetTransformInfo *TTI)
101 : Width("vectorize.width", VectorizerParams::VectorizationFactor, HK_WIDTH),
102 Interleave("interleave.count", InterleaveOnlyWhenForced, HK_INTERLEAVE),
103 Force("vectorize.enable", FK_Undefined, HK_FORCE),
104 IsVectorized("isvectorized", 0, HK_ISVECTORIZED),
105 Predicate("vectorize.predicate.enable", FK_Undefined, HK_PREDICATE),
106 Scalable("vectorize.scalable.enable", SK_Unspecified, HK_SCALABLE),
107 TheLoop(L), ORE(ORE) {
108 // Populate values with existing loop metadata.
109 getHintsFromMetadata();
111 // force-vector-interleave overrides DisableInterleaving.
112 if (VectorizerParams::isInterleaveForced())
113 Interleave.Value = VectorizerParams::VectorizationInterleave;
115 // If the metadata doesn't explicitly specify whether to enable scalable
116 // vectorization, then decide based on the following criteria (increasing
117 // level of priority):
120 // - Force option (always overrides)
121 if ((LoopVectorizeHints::ScalableForceKind)Scalable.Value == SK_Unspecified) {
123 Scalable.Value = TTI->enableScalableVectorization() ? SK_PreferScalable
127 // If the width is set, but the metadata says nothing about the scalable
128 // property, then assume it concerns only a fixed-width UserVF.
129 // If width is not set, the flag takes precedence.
130 Scalable.Value = SK_FixedWidthOnly;
133 // If the flag is set to force any use of scalable vectors, override the loop
135 if (ForceScalableVectorization.getValue() !=
136 LoopVectorizeHints::SK_Unspecified)
137 Scalable.Value = ForceScalableVectorization.getValue();
139 // Scalable vectorization is disabled if no preference is specified.
140 if ((LoopVectorizeHints::ScalableForceKind)Scalable.Value == SK_Unspecified)
141 Scalable.Value = SK_FixedWidthOnly;
143 if (IsVectorized.Value != 1)
144 // If the vectorization width and interleaving count are both 1 then
145 // consider the loop to have been already vectorized because there's
146 // nothing more that we can do.
148 getWidth() == ElementCount::getFixed(1) && getInterleave() == 1;
149 LLVM_DEBUG(if (InterleaveOnlyWhenForced && getInterleave() == 1) dbgs()
150 << "LV: Interleaving disabled by the pass manager\n");
153 void LoopVectorizeHints::setAlreadyVectorized() {
154 LLVMContext &Context = TheLoop->getHeader()->getContext();
156 MDNode *IsVectorizedMD = MDNode::get(
158 {MDString::get(Context, "llvm.loop.isvectorized"),
159 ConstantAsMetadata::get(ConstantInt::get(Context, APInt(32, 1)))});
160 MDNode *LoopID = TheLoop->getLoopID();
162 makePostTransformationMetadata(Context, LoopID,
163 {Twine(Prefix(), "vectorize.").str(),
164 Twine(Prefix(), "interleave.").str()},
166 TheLoop->setLoopID(NewLoopID);
168 // Update internal cache.
169 IsVectorized.Value = 1;
172 bool LoopVectorizeHints::allowVectorization(
173 Function *F, Loop *L, bool VectorizeOnlyWhenForced) const {
174 if (getForce() == LoopVectorizeHints::FK_Disabled) {
175 LLVM_DEBUG(dbgs() << "LV: Not vectorizing: #pragma vectorize disable.\n");
176 emitRemarkWithHints();
180 if (VectorizeOnlyWhenForced && getForce() != LoopVectorizeHints::FK_Enabled) {
181 LLVM_DEBUG(dbgs() << "LV: Not vectorizing: No #pragma vectorize enable.\n");
182 emitRemarkWithHints();
186 if (getIsVectorized() == 1) {
187 LLVM_DEBUG(dbgs() << "LV: Not vectorizing: Disabled/already vectorized.\n");
188 // FIXME: Add interleave.disable metadata. This will allow
189 // vectorize.disable to be used without disabling the pass and errors
190 // to differentiate between disabled vectorization and a width of 1.
192 return OptimizationRemarkAnalysis(vectorizeAnalysisPassName(),
193 "AllDisabled", L->getStartLoc(),
195 << "loop not vectorized: vectorization and interleaving are "
196 "explicitly disabled, or the loop has already been "
205 void LoopVectorizeHints::emitRemarkWithHints() const {
209 if (Force.Value == LoopVectorizeHints::FK_Disabled)
210 return OptimizationRemarkMissed(LV_NAME, "MissedExplicitlyDisabled",
211 TheLoop->getStartLoc(),
212 TheLoop->getHeader())
213 << "loop not vectorized: vectorization is explicitly disabled";
215 OptimizationRemarkMissed R(LV_NAME, "MissedDetails",
216 TheLoop->getStartLoc(), TheLoop->getHeader());
217 R << "loop not vectorized";
218 if (Force.Value == LoopVectorizeHints::FK_Enabled) {
219 R << " (Force=" << NV("Force", true);
220 if (Width.Value != 0)
221 R << ", Vector Width=" << NV("VectorWidth", getWidth());
222 if (getInterleave() != 0)
223 R << ", Interleave Count=" << NV("InterleaveCount", getInterleave());
231 const char *LoopVectorizeHints::vectorizeAnalysisPassName() const {
232 if (getWidth() == ElementCount::getFixed(1))
234 if (getForce() == LoopVectorizeHints::FK_Disabled)
236 if (getForce() == LoopVectorizeHints::FK_Undefined && getWidth().isZero())
238 return OptimizationRemarkAnalysis::AlwaysPrint;
241 bool LoopVectorizeHints::allowReordering() const {
242 // Allow the vectorizer to change the order of operations if enabling
243 // loop hints are provided
244 ElementCount EC = getWidth();
245 return HintsAllowReordering &&
246 (getForce() == LoopVectorizeHints::FK_Enabled ||
247 EC.getKnownMinValue() > 1);
250 void LoopVectorizeHints::getHintsFromMetadata() {
251 MDNode *LoopID = TheLoop->getLoopID();
255 // First operand should refer to the loop id itself.
256 assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
257 assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
259 for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
260 const MDString *S = nullptr;
261 SmallVector<Metadata *, 4> Args;
263 // The expected hint is either a MDString or a MDNode with the first
264 // operand a MDString.
265 if (const MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i))) {
266 if (!MD || MD->getNumOperands() == 0)
268 S = dyn_cast<MDString>(MD->getOperand(0));
269 for (unsigned i = 1, ie = MD->getNumOperands(); i < ie; ++i)
270 Args.push_back(MD->getOperand(i));
272 S = dyn_cast<MDString>(LoopID->getOperand(i));
273 assert(Args.size() == 0 && "too many arguments for MDString");
279 // Check if the hint starts with the loop metadata prefix.
280 StringRef Name = S->getString();
281 if (Args.size() == 1)
282 setHint(Name, Args[0]);
286 void LoopVectorizeHints::setHint(StringRef Name, Metadata *Arg) {
287 if (!Name.startswith(Prefix()))
289 Name = Name.substr(Prefix().size(), StringRef::npos);
291 const ConstantInt *C = mdconst::dyn_extract<ConstantInt>(Arg);
294 unsigned Val = C->getZExtValue();
296 Hint *Hints[] = {&Width, &Interleave, &Force,
297 &IsVectorized, &Predicate, &Scalable};
298 for (auto H : Hints) {
299 if (Name == H->Name) {
300 if (H->validate(Val))
303 LLVM_DEBUG(dbgs() << "LV: ignoring invalid hint '" << Name << "'\n");
309 // Return true if the inner loop \p Lp is uniform with regard to the outer loop
310 // \p OuterLp (i.e., if the outer loop is vectorized, all the vector lanes
311 // executing the inner loop will execute the same iterations). This check is
312 // very constrained for now but it will be relaxed in the future. \p Lp is
313 // considered uniform if it meets all the following conditions:
314 // 1) it has a canonical IV (starting from 0 and with stride 1),
315 // 2) its latch terminator is a conditional branch and,
316 // 3) its latch condition is a compare instruction whose operands are the
317 // canonical IV and an OuterLp invariant.
318 // This check doesn't take into account the uniformity of other conditions not
319 // related to the loop latch because they don't affect the loop uniformity.
321 // NOTE: We decided to keep all these checks and its associated documentation
322 // together so that we can easily have a picture of the current supported loop
323 // nests. However, some of the current checks don't depend on \p OuterLp and
324 // would be redundantly executed for each \p Lp if we invoked this function for
325 // different candidate outer loops. This is not the case for now because we
326 // don't currently have the infrastructure to evaluate multiple candidate outer
327 // loops and \p OuterLp will be a fixed parameter while we only support explicit
328 // outer loop vectorization. It's also very likely that these checks go away
329 // before introducing the aforementioned infrastructure. However, if this is not
330 // the case, we should move the \p OuterLp independent checks to a separate
331 // function that is only executed once for each \p Lp.
332 static bool isUniformLoop(Loop *Lp, Loop *OuterLp) {
333 assert(Lp->getLoopLatch() && "Expected loop with a single latch.");
335 // If Lp is the outer loop, it's uniform by definition.
338 assert(OuterLp->contains(Lp) && "OuterLp must contain Lp.");
341 PHINode *IV = Lp->getCanonicalInductionVariable();
343 LLVM_DEBUG(dbgs() << "LV: Canonical IV not found.\n");
348 BasicBlock *Latch = Lp->getLoopLatch();
349 auto *LatchBr = dyn_cast<BranchInst>(Latch->getTerminator());
350 if (!LatchBr || LatchBr->isUnconditional()) {
351 LLVM_DEBUG(dbgs() << "LV: Unsupported loop latch branch.\n");
356 auto *LatchCmp = dyn_cast<CmpInst>(LatchBr->getCondition());
359 dbgs() << "LV: Loop latch condition is not a compare instruction.\n");
363 Value *CondOp0 = LatchCmp->getOperand(0);
364 Value *CondOp1 = LatchCmp->getOperand(1);
365 Value *IVUpdate = IV->getIncomingValueForBlock(Latch);
366 if (!(CondOp0 == IVUpdate && OuterLp->isLoopInvariant(CondOp1)) &&
367 !(CondOp1 == IVUpdate && OuterLp->isLoopInvariant(CondOp0))) {
368 LLVM_DEBUG(dbgs() << "LV: Loop latch condition is not uniform.\n");
375 // Return true if \p Lp and all its nested loops are uniform with regard to \p
377 static bool isUniformLoopNest(Loop *Lp, Loop *OuterLp) {
378 if (!isUniformLoop(Lp, OuterLp))
381 // Check if nested loops are uniform.
382 for (Loop *SubLp : *Lp)
383 if (!isUniformLoopNest(SubLp, OuterLp))
389 static Type *convertPointerToIntegerType(const DataLayout &DL, Type *Ty) {
390 if (Ty->isPointerTy())
391 return DL.getIntPtrType(Ty);
393 // It is possible that char's or short's overflow when we ask for the loop's
394 // trip count, work around this by changing the type size.
395 if (Ty->getScalarSizeInBits() < 32)
396 return Type::getInt32Ty(Ty->getContext());
401 static Type *getWiderType(const DataLayout &DL, Type *Ty0, Type *Ty1) {
402 Ty0 = convertPointerToIntegerType(DL, Ty0);
403 Ty1 = convertPointerToIntegerType(DL, Ty1);
404 if (Ty0->getScalarSizeInBits() > Ty1->getScalarSizeInBits())
409 /// Check that the instruction has outside loop users and is not an
410 /// identified reduction variable.
411 static bool hasOutsideLoopUser(const Loop *TheLoop, Instruction *Inst,
412 SmallPtrSetImpl<Value *> &AllowedExit) {
413 // Reductions, Inductions and non-header phis are allowed to have exit users. All
414 // other instructions must not have external users.
415 if (!AllowedExit.count(Inst))
416 // Check that all of the users of the loop are inside the BB.
417 for (User *U : Inst->users()) {
418 Instruction *UI = cast<Instruction>(U);
419 // This user may be a reduction exit value.
420 if (!TheLoop->contains(UI)) {
421 LLVM_DEBUG(dbgs() << "LV: Found an outside user for : " << *UI << '\n');
428 /// Returns true if A and B have same pointer operands or same SCEVs addresses
429 static bool storeToSameAddress(ScalarEvolution *SE, StoreInst *A,
435 // Otherwise Compare pointers
436 Value *APtr = A->getPointerOperand();
437 Value *BPtr = B->getPointerOperand();
441 // Otherwise compare address SCEVs
442 if (SE->getSCEV(APtr) == SE->getSCEV(BPtr))
448 int LoopVectorizationLegality::isConsecutivePtr(Type *AccessTy,
450 const ValueToValueMap &Strides =
451 getSymbolicStrides() ? *getSymbolicStrides() : ValueToValueMap();
453 Function *F = TheLoop->getHeader()->getParent();
454 bool OptForSize = F->hasOptSize() ||
455 llvm::shouldOptimizeForSize(TheLoop->getHeader(), PSI, BFI,
456 PGSOQueryType::IRPass);
457 bool CanAddPredicate = !OptForSize;
458 int Stride = getPtrStride(PSE, AccessTy, Ptr, TheLoop, Strides,
459 CanAddPredicate, false);
460 if (Stride == 1 || Stride == -1)
465 bool LoopVectorizationLegality::isUniform(Value *V) {
466 return LAI->isUniform(V);
469 bool LoopVectorizationLegality::canVectorizeOuterLoop() {
470 assert(!TheLoop->isInnermost() && "We are not vectorizing an outer loop.");
471 // Store the result and return it at the end instead of exiting early, in case
472 // allowExtraAnalysis is used to report multiple reasons for not vectorizing.
474 bool DoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE);
476 for (BasicBlock *BB : TheLoop->blocks()) {
477 // Check whether the BB terminator is a BranchInst. Any other terminator is
478 // not supported yet.
479 auto *Br = dyn_cast<BranchInst>(BB->getTerminator());
481 reportVectorizationFailure("Unsupported basic block terminator",
482 "loop control flow is not understood by vectorizer",
483 "CFGNotUnderstood", ORE, TheLoop);
490 // Check whether the BranchInst is a supported one. Only unconditional
491 // branches, conditional branches with an outer loop invariant condition or
492 // backedges are supported.
493 // FIXME: We skip these checks when VPlan predication is enabled as we
494 // want to allow divergent branches. This whole check will be removed
495 // once VPlan predication is on by default.
496 if (Br && Br->isConditional() &&
497 !TheLoop->isLoopInvariant(Br->getCondition()) &&
498 !LI->isLoopHeader(Br->getSuccessor(0)) &&
499 !LI->isLoopHeader(Br->getSuccessor(1))) {
500 reportVectorizationFailure("Unsupported conditional branch",
501 "loop control flow is not understood by vectorizer",
502 "CFGNotUnderstood", ORE, TheLoop);
510 // Check whether inner loops are uniform. At this point, we only support
511 // simple outer loops scenarios with uniform nested loops.
512 if (!isUniformLoopNest(TheLoop /*loop nest*/,
513 TheLoop /*context outer loop*/)) {
514 reportVectorizationFailure("Outer loop contains divergent loops",
515 "loop control flow is not understood by vectorizer",
516 "CFGNotUnderstood", ORE, TheLoop);
523 // Check whether we are able to set up outer loop induction.
524 if (!setupOuterLoopInductions()) {
525 reportVectorizationFailure("Unsupported outer loop Phi(s)",
526 "Unsupported outer loop Phi(s)",
527 "UnsupportedPhi", ORE, TheLoop);
537 void LoopVectorizationLegality::addInductionPhi(
538 PHINode *Phi, const InductionDescriptor &ID,
539 SmallPtrSetImpl<Value *> &AllowedExit) {
540 Inductions[Phi] = ID;
542 // In case this induction also comes with casts that we know we can ignore
543 // in the vectorized loop body, record them here. All casts could be recorded
544 // here for ignoring, but suffices to record only the first (as it is the
545 // only one that may bw used outside the cast sequence).
546 const SmallVectorImpl<Instruction *> &Casts = ID.getCastInsts();
548 InductionCastsToIgnore.insert(*Casts.begin());
550 Type *PhiTy = Phi->getType();
551 const DataLayout &DL = Phi->getModule()->getDataLayout();
553 // Get the widest type.
554 if (!PhiTy->isFloatingPointTy()) {
556 WidestIndTy = convertPointerToIntegerType(DL, PhiTy);
558 WidestIndTy = getWiderType(DL, PhiTy, WidestIndTy);
561 // Int inductions are special because we only allow one IV.
562 if (ID.getKind() == InductionDescriptor::IK_IntInduction &&
563 ID.getConstIntStepValue() && ID.getConstIntStepValue()->isOne() &&
564 isa<Constant>(ID.getStartValue()) &&
565 cast<Constant>(ID.getStartValue())->isNullValue()) {
567 // Use the phi node with the widest type as induction. Use the last
568 // one if there are multiple (no good reason for doing this other
569 // than it is expedient). We've checked that it begins at zero and
570 // steps by one, so this is a canonical induction variable.
571 if (!PrimaryInduction || PhiTy == WidestIndTy)
572 PrimaryInduction = Phi;
575 // Both the PHI node itself, and the "post-increment" value feeding
576 // back into the PHI node may have external users.
577 // We can allow those uses, except if the SCEVs we have for them rely
578 // on predicates that only hold within the loop, since allowing the exit
579 // currently means re-using this SCEV outside the loop (see PR33706 for more
581 if (PSE.getPredicate().isAlwaysTrue()) {
582 AllowedExit.insert(Phi);
583 AllowedExit.insert(Phi->getIncomingValueForBlock(TheLoop->getLoopLatch()));
586 LLVM_DEBUG(dbgs() << "LV: Found an induction variable.\n");
589 bool LoopVectorizationLegality::setupOuterLoopInductions() {
590 BasicBlock *Header = TheLoop->getHeader();
592 // Returns true if a given Phi is a supported induction.
593 auto isSupportedPhi = [&](PHINode &Phi) -> bool {
594 InductionDescriptor ID;
595 if (InductionDescriptor::isInductionPHI(&Phi, TheLoop, PSE, ID) &&
596 ID.getKind() == InductionDescriptor::IK_IntInduction) {
597 addInductionPhi(&Phi, ID, AllowedExit);
600 // Bail out for any Phi in the outer loop header that is not a supported
604 << "LV: Found unsupported PHI for outer loop vectorization.\n");
609 if (llvm::all_of(Header->phis(), isSupportedPhi))
615 /// Checks if a function is scalarizable according to the TLI, in
616 /// the sense that it should be vectorized and then expanded in
617 /// multiple scalar calls. This is represented in the
618 /// TLI via mappings that do not specify a vector name, as in the
619 /// following example:
621 /// const VecDesc VecIntrinsics[] = {
622 /// {"llvm.phx.abs.i32", "", 4}
624 static bool isTLIScalarize(const TargetLibraryInfo &TLI, const CallInst &CI) {
625 const StringRef ScalarName = CI.getCalledFunction()->getName();
626 bool Scalarize = TLI.isFunctionVectorizable(ScalarName);
627 // Check that all known VFs are not associated to a vector
628 // function, i.e. the vector name is emty.
630 ElementCount WidestFixedVF, WidestScalableVF;
631 TLI.getWidestVF(ScalarName, WidestFixedVF, WidestScalableVF);
632 for (ElementCount VF = ElementCount::getFixed(2);
633 ElementCount::isKnownLE(VF, WidestFixedVF); VF *= 2)
634 Scalarize &= !TLI.isFunctionVectorizable(ScalarName, VF);
635 for (ElementCount VF = ElementCount::getScalable(1);
636 ElementCount::isKnownLE(VF, WidestScalableVF); VF *= 2)
637 Scalarize &= !TLI.isFunctionVectorizable(ScalarName, VF);
638 assert((WidestScalableVF.isZero() || !Scalarize) &&
639 "Caller may decide to scalarize a variant using a scalable VF");
644 bool LoopVectorizationLegality::canVectorizeInstrs() {
645 BasicBlock *Header = TheLoop->getHeader();
647 // For each block in the loop.
648 for (BasicBlock *BB : TheLoop->blocks()) {
649 // Scan the instructions in the block and look for hazards.
650 for (Instruction &I : *BB) {
651 if (auto *Phi = dyn_cast<PHINode>(&I)) {
652 Type *PhiTy = Phi->getType();
653 // Check that this PHI type is allowed.
654 if (!PhiTy->isIntegerTy() && !PhiTy->isFloatingPointTy() &&
655 !PhiTy->isPointerTy()) {
656 reportVectorizationFailure("Found a non-int non-pointer PHI",
657 "loop control flow is not understood by vectorizer",
658 "CFGNotUnderstood", ORE, TheLoop);
662 // If this PHINode is not in the header block, then we know that we
663 // can convert it to select during if-conversion. No need to check if
664 // the PHIs in this block are induction or reduction variables.
666 // Non-header phi nodes that have outside uses can be vectorized. Add
667 // them to the list of allowed exits.
668 // Unsafe cyclic dependencies with header phis are identified during
669 // legalization for reduction, induction and first order
671 AllowedExit.insert(&I);
675 // We only allow if-converted PHIs with exactly two incoming values.
676 if (Phi->getNumIncomingValues() != 2) {
677 reportVectorizationFailure("Found an invalid PHI",
678 "loop control flow is not understood by vectorizer",
679 "CFGNotUnderstood", ORE, TheLoop, Phi);
683 RecurrenceDescriptor RedDes;
684 if (RecurrenceDescriptor::isReductionPHI(Phi, TheLoop, RedDes, DB, AC,
686 Requirements->addExactFPMathInst(RedDes.getExactFPMathInst());
687 AllowedExit.insert(RedDes.getLoopExitInstr());
688 Reductions[Phi] = RedDes;
692 // TODO: Instead of recording the AllowedExit, it would be good to record the
693 // complementary set: NotAllowedExit. These include (but may not be
695 // 1. Reduction phis as they represent the one-before-last value, which
696 // is not available when vectorized
697 // 2. Induction phis and increment when SCEV predicates cannot be used
698 // outside the loop - see addInductionPhi
699 // 3. Non-Phis with outside uses when SCEV predicates cannot be used
700 // outside the loop - see call to hasOutsideLoopUser in the non-phi
702 // 4. FirstOrderRecurrence phis that can possibly be handled by
704 // By recording these, we can then reason about ways to vectorize each
705 // of these NotAllowedExit.
706 InductionDescriptor ID;
707 if (InductionDescriptor::isInductionPHI(Phi, TheLoop, PSE, ID)) {
708 addInductionPhi(Phi, ID, AllowedExit);
709 Requirements->addExactFPMathInst(ID.getExactFPMathInst());
713 if (RecurrenceDescriptor::isFirstOrderRecurrence(Phi, TheLoop,
715 AllowedExit.insert(Phi);
716 FirstOrderRecurrences.insert(Phi);
720 // As a last resort, coerce the PHI to a AddRec expression
721 // and re-try classifying it a an induction PHI.
722 if (InductionDescriptor::isInductionPHI(Phi, TheLoop, PSE, ID, true)) {
723 addInductionPhi(Phi, ID, AllowedExit);
727 reportVectorizationFailure("Found an unidentified PHI",
728 "value that could not be identified as "
729 "reduction is used outside the loop",
730 "NonReductionValueUsedOutsideLoop", ORE, TheLoop, Phi);
732 } // end of PHI handling
734 // We handle calls that:
735 // * Are debug info intrinsics.
736 // * Have a mapping to an IR intrinsic.
737 // * Have a vector version available.
738 auto *CI = dyn_cast<CallInst>(&I);
740 if (CI && !getVectorIntrinsicIDForCall(CI, TLI) &&
741 !isa<DbgInfoIntrinsic>(CI) &&
742 !(CI->getCalledFunction() && TLI &&
743 (!VFDatabase::getMappings(*CI).empty() ||
744 isTLIScalarize(*TLI, *CI)))) {
745 // If the call is a recognized math libary call, it is likely that
746 // we can vectorize it given loosened floating-point constraints.
749 TLI && CI->getCalledFunction() &&
750 CI->getType()->isFloatingPointTy() &&
751 TLI->getLibFunc(CI->getCalledFunction()->getName(), Func) &&
752 TLI->hasOptimizedCodeGen(Func);
755 // TODO: Ideally, we should not use clang-specific language here,
756 // but it's hard to provide meaningful yet generic advice.
757 // Also, should this be guarded by allowExtraAnalysis() and/or be part
758 // of the returned info from isFunctionVectorizable()?
759 reportVectorizationFailure(
760 "Found a non-intrinsic callsite",
761 "library call cannot be vectorized. "
762 "Try compiling with -fno-math-errno, -ffast-math, "
764 "CantVectorizeLibcall", ORE, TheLoop, CI);
766 reportVectorizationFailure("Found a non-intrinsic callsite",
767 "call instruction cannot be vectorized",
768 "CantVectorizeLibcall", ORE, TheLoop, CI);
773 // Some intrinsics have scalar arguments and should be same in order for
774 // them to be vectorized (i.e. loop invariant).
776 auto *SE = PSE.getSE();
777 Intrinsic::ID IntrinID = getVectorIntrinsicIDForCall(CI, TLI);
778 for (unsigned i = 0, e = CI->arg_size(); i != e; ++i)
779 if (isVectorIntrinsicWithScalarOpAtArg(IntrinID, i)) {
780 if (!SE->isLoopInvariant(PSE.getSCEV(CI->getOperand(i)), TheLoop)) {
781 reportVectorizationFailure("Found unvectorizable intrinsic",
782 "intrinsic instruction cannot be vectorized",
783 "CantVectorizeIntrinsic", ORE, TheLoop, CI);
789 // Check that the instruction return type is vectorizable.
790 // Also, we can't vectorize extractelement instructions.
791 if ((!VectorType::isValidElementType(I.getType()) &&
792 !I.getType()->isVoidTy()) ||
793 isa<ExtractElementInst>(I)) {
794 reportVectorizationFailure("Found unvectorizable type",
795 "instruction return type cannot be vectorized",
796 "CantVectorizeInstructionReturnType", ORE, TheLoop, &I);
800 // Check that the stored type is vectorizable.
801 if (auto *ST = dyn_cast<StoreInst>(&I)) {
802 Type *T = ST->getValueOperand()->getType();
803 if (!VectorType::isValidElementType(T)) {
804 reportVectorizationFailure("Store instruction cannot be vectorized",
805 "store instruction cannot be vectorized",
806 "CantVectorizeStore", ORE, TheLoop, ST);
810 // For nontemporal stores, check that a nontemporal vector version is
811 // supported on the target.
812 if (ST->getMetadata(LLVMContext::MD_nontemporal)) {
813 // Arbitrarily try a vector of 2 elements.
814 auto *VecTy = FixedVectorType::get(T, /*NumElts=*/2);
815 assert(VecTy && "did not find vectorized version of stored type");
816 if (!TTI->isLegalNTStore(VecTy, ST->getAlign())) {
817 reportVectorizationFailure(
818 "nontemporal store instruction cannot be vectorized",
819 "nontemporal store instruction cannot be vectorized",
820 "CantVectorizeNontemporalStore", ORE, TheLoop, ST);
825 } else if (auto *LD = dyn_cast<LoadInst>(&I)) {
826 if (LD->getMetadata(LLVMContext::MD_nontemporal)) {
827 // For nontemporal loads, check that a nontemporal vector version is
828 // supported on the target (arbitrarily try a vector of 2 elements).
829 auto *VecTy = FixedVectorType::get(I.getType(), /*NumElts=*/2);
830 assert(VecTy && "did not find vectorized version of load type");
831 if (!TTI->isLegalNTLoad(VecTy, LD->getAlign())) {
832 reportVectorizationFailure(
833 "nontemporal load instruction cannot be vectorized",
834 "nontemporal load instruction cannot be vectorized",
835 "CantVectorizeNontemporalLoad", ORE, TheLoop, LD);
840 // FP instructions can allow unsafe algebra, thus vectorizable by
841 // non-IEEE-754 compliant SIMD units.
842 // This applies to floating-point math operations and calls, not memory
843 // operations, shuffles, or casts, as they don't change precision or
845 } else if (I.getType()->isFloatingPointTy() && (CI || I.isBinaryOp()) &&
847 LLVM_DEBUG(dbgs() << "LV: Found FP op with unsafe algebra.\n");
848 Hints->setPotentiallyUnsafe();
851 // Reduction instructions are allowed to have exit users.
852 // All other instructions must not have external users.
853 if (hasOutsideLoopUser(TheLoop, &I, AllowedExit)) {
854 // We can safely vectorize loops where instructions within the loop are
855 // used outside the loop only if the SCEV predicates within the loop is
856 // same as outside the loop. Allowing the exit means reusing the SCEV
858 if (PSE.getPredicate().isAlwaysTrue()) {
859 AllowedExit.insert(&I);
862 reportVectorizationFailure("Value cannot be used outside the loop",
863 "value cannot be used outside the loop",
864 "ValueUsedOutsideLoop", ORE, TheLoop, &I);
870 if (!PrimaryInduction) {
871 if (Inductions.empty()) {
872 reportVectorizationFailure("Did not find one integer induction var",
873 "loop induction variable could not be identified",
874 "NoInductionVariable", ORE, TheLoop);
876 } else if (!WidestIndTy) {
877 reportVectorizationFailure("Did not find one integer induction var",
878 "integer loop induction variable could not be identified",
879 "NoIntegerInductionVariable", ORE, TheLoop);
882 LLVM_DEBUG(dbgs() << "LV: Did not find one integer induction var.\n");
886 // For first order recurrences, we use the previous value (incoming value from
887 // the latch) to check if it dominates all users of the recurrence. Bail out
888 // if we have to sink such an instruction for another recurrence, as the
889 // dominance requirement may not hold after sinking.
890 BasicBlock *LoopLatch = TheLoop->getLoopLatch();
891 if (any_of(FirstOrderRecurrences, [LoopLatch, this](const PHINode *Phi) {
893 cast<Instruction>(Phi->getIncomingValueForBlock(LoopLatch));
894 return SinkAfter.find(V) != SinkAfter.end();
898 // Now we know the widest induction type, check if our found induction
899 // is the same size. If it's not, unset it here and InnerLoopVectorizer
900 // will create another.
901 if (PrimaryInduction && WidestIndTy != PrimaryInduction->getType())
902 PrimaryInduction = nullptr;
907 bool LoopVectorizationLegality::canVectorizeMemory() {
908 LAI = &(*GetLAA)(*TheLoop);
909 const OptimizationRemarkAnalysis *LAR = LAI->getReport();
912 return OptimizationRemarkAnalysis(Hints->vectorizeAnalysisPassName(),
913 "loop not vectorized: ", *LAR);
917 if (!LAI->canVectorizeMemory())
920 // We can vectorize stores to invariant address when final reduction value is
921 // guaranteed to be stored at the end of the loop. Also, if decision to
922 // vectorize loop is made, runtime checks are added so as to make sure that
923 // invariant address won't alias with any other objects.
924 if (!LAI->getStoresToInvariantAddresses().empty()) {
925 // For each invariant address, check its last stored value is unconditional.
926 for (StoreInst *SI : LAI->getStoresToInvariantAddresses()) {
927 if (isInvariantStoreOfReduction(SI) &&
928 blockNeedsPredication(SI->getParent())) {
929 reportVectorizationFailure(
930 "We don't allow storing to uniform addresses",
931 "write of conditional recurring variant value to a loop "
932 "invariant address could not be vectorized",
933 "CantVectorizeStoreToLoopInvariantAddress", ORE, TheLoop);
938 if (LAI->hasDependenceInvolvingLoopInvariantAddress()) {
939 // For each invariant address, check its last stored value is the result
940 // of one of our reductions.
942 // We do not check if dependence with loads exists because they are
943 // currently rejected earlier in LoopAccessInfo::analyzeLoop. In case this
944 // behaviour changes we have to modify this code.
945 ScalarEvolution *SE = PSE.getSE();
946 SmallVector<StoreInst *, 4> UnhandledStores;
947 for (StoreInst *SI : LAI->getStoresToInvariantAddresses()) {
948 if (isInvariantStoreOfReduction(SI)) {
949 // Earlier stores to this address are effectively deadcode.
950 // With opaque pointers it is possible for one pointer to be used with
951 // different sizes of stored values:
952 // store i32 0, ptr %x
953 // store i8 0, ptr %x
954 // The latest store doesn't complitely overwrite the first one in the
955 // example. That is why we have to make sure that types of stored
957 // TODO: Check that bitwidth of unhandled store is smaller then the
958 // one that overwrites it and add a test.
959 erase_if(UnhandledStores, [SE, SI](StoreInst *I) {
960 return storeToSameAddress(SE, SI, I) &&
961 I->getValueOperand()->getType() ==
962 SI->getValueOperand()->getType();
966 UnhandledStores.push_back(SI);
969 bool IsOK = UnhandledStores.empty();
970 // TODO: we should also validate against InvariantMemSets.
972 reportVectorizationFailure(
973 "We don't allow storing to uniform addresses",
974 "write to a loop invariant address could not "
976 "CantVectorizeStoreToLoopInvariantAddress", ORE, TheLoop);
982 PSE.addPredicate(LAI->getPSE().getPredicate());
986 bool LoopVectorizationLegality::canVectorizeFPMath(
987 bool EnableStrictReductions) {
989 // First check if there is any ExactFP math or if we allow reassociations
990 if (!Requirements->getExactFPInst() || Hints->allowReordering())
993 // If the above is false, we have ExactFPMath & do not allow reordering.
994 // If the EnableStrictReductions flag is set, first check if we have any
995 // Exact FP induction vars, which we cannot vectorize.
996 if (!EnableStrictReductions ||
997 any_of(getInductionVars(), [&](auto &Induction) -> bool {
998 InductionDescriptor IndDesc = Induction.second;
999 return IndDesc.getExactFPMathInst();
1003 // We can now only vectorize if all reductions with Exact FP math also
1004 // have the isOrdered flag set, which indicates that we can move the
1005 // reduction operations in-loop.
1006 return (all_of(getReductionVars(), [&](auto &Reduction) -> bool {
1007 const RecurrenceDescriptor &RdxDesc = Reduction.second;
1008 return !RdxDesc.hasExactFPMath() || RdxDesc.isOrdered();
1012 bool LoopVectorizationLegality::isInvariantStoreOfReduction(StoreInst *SI) {
1013 return any_of(getReductionVars(), [&](auto &Reduction) -> bool {
1014 const RecurrenceDescriptor &RdxDesc = Reduction.second;
1015 return RdxDesc.IntermediateStore == SI;
1019 bool LoopVectorizationLegality::isInvariantAddressOfReduction(Value *V) {
1020 return any_of(getReductionVars(), [&](auto &Reduction) -> bool {
1021 const RecurrenceDescriptor &RdxDesc = Reduction.second;
1022 if (!RdxDesc.IntermediateStore)
1025 ScalarEvolution *SE = PSE.getSE();
1026 Value *InvariantAddress = RdxDesc.IntermediateStore->getPointerOperand();
1027 return V == InvariantAddress ||
1028 SE->getSCEV(V) == SE->getSCEV(InvariantAddress);
1032 bool LoopVectorizationLegality::isInductionPhi(const Value *V) const {
1033 Value *In0 = const_cast<Value *>(V);
1034 PHINode *PN = dyn_cast_or_null<PHINode>(In0);
1038 return Inductions.count(PN);
1041 const InductionDescriptor *
1042 LoopVectorizationLegality::getIntOrFpInductionDescriptor(PHINode *Phi) const {
1043 if (!isInductionPhi(Phi))
1045 auto &ID = getInductionVars().find(Phi)->second;
1046 if (ID.getKind() == InductionDescriptor::IK_IntInduction ||
1047 ID.getKind() == InductionDescriptor::IK_FpInduction)
1052 const InductionDescriptor *
1053 LoopVectorizationLegality::getPointerInductionDescriptor(PHINode *Phi) const {
1054 if (!isInductionPhi(Phi))
1056 auto &ID = getInductionVars().find(Phi)->second;
1057 if (ID.getKind() == InductionDescriptor::IK_PtrInduction)
1062 bool LoopVectorizationLegality::isCastedInductionVariable(
1063 const Value *V) const {
1064 auto *Inst = dyn_cast<Instruction>(V);
1065 return (Inst && InductionCastsToIgnore.count(Inst));
1068 bool LoopVectorizationLegality::isInductionVariable(const Value *V) const {
1069 return isInductionPhi(V) || isCastedInductionVariable(V);
1072 bool LoopVectorizationLegality::isFirstOrderRecurrence(
1073 const PHINode *Phi) const {
1074 return FirstOrderRecurrences.count(Phi);
1077 bool LoopVectorizationLegality::blockNeedsPredication(BasicBlock *BB) const {
1078 return LoopAccessInfo::blockNeedsPredication(BB, TheLoop, DT);
1081 bool LoopVectorizationLegality::blockCanBePredicated(
1082 BasicBlock *BB, SmallPtrSetImpl<Value *> &SafePtrs,
1083 SmallPtrSetImpl<const Instruction *> &MaskedOp,
1084 SmallPtrSetImpl<Instruction *> &ConditionalAssumes) const {
1085 for (Instruction &I : *BB) {
1086 // We can predicate blocks with calls to assume, as long as we drop them in
1087 // case we flatten the CFG via predication.
1088 if (match(&I, m_Intrinsic<Intrinsic::assume>())) {
1089 ConditionalAssumes.insert(&I);
1093 // Do not let llvm.experimental.noalias.scope.decl block the vectorization.
1094 // TODO: there might be cases that it should block the vectorization. Let's
1095 // ignore those for now.
1096 if (isa<NoAliasScopeDeclInst>(&I))
1099 // We might be able to hoist the load.
1100 if (I.mayReadFromMemory()) {
1101 auto *LI = dyn_cast<LoadInst>(&I);
1104 if (!SafePtrs.count(LI->getPointerOperand())) {
1105 MaskedOp.insert(LI);
1110 if (I.mayWriteToMemory()) {
1111 auto *SI = dyn_cast<StoreInst>(&I);
1114 // Predicated store requires some form of masking:
1115 // 1) masked store HW instruction,
1116 // 2) emulation via load-blend-store (only if safe and legal to do so,
1117 // be aware on the race conditions), or
1118 // 3) element-by-element predicate check and scalar store.
1119 MaskedOp.insert(SI);
1129 bool LoopVectorizationLegality::canVectorizeWithIfConvert() {
1130 if (!EnableIfConversion) {
1131 reportVectorizationFailure("If-conversion is disabled",
1132 "if-conversion is disabled",
1133 "IfConversionDisabled",
1138 assert(TheLoop->getNumBlocks() > 1 && "Single block loops are vectorizable");
1140 // A list of pointers which are known to be dereferenceable within scope of
1141 // the loop body for each iteration of the loop which executes. That is,
1142 // the memory pointed to can be dereferenced (with the access size implied by
1143 // the value's type) unconditionally within the loop header without
1144 // introducing a new fault.
1145 SmallPtrSet<Value *, 8> SafePointers;
1147 // Collect safe addresses.
1148 for (BasicBlock *BB : TheLoop->blocks()) {
1149 if (!blockNeedsPredication(BB)) {
1150 for (Instruction &I : *BB)
1151 if (auto *Ptr = getLoadStorePointerOperand(&I))
1152 SafePointers.insert(Ptr);
1156 // For a block which requires predication, a address may be safe to access
1157 // in the loop w/o predication if we can prove dereferenceability facts
1158 // sufficient to ensure it'll never fault within the loop. For the moment,
1159 // we restrict this to loads; stores are more complicated due to
1160 // concurrency restrictions.
1161 ScalarEvolution &SE = *PSE.getSE();
1162 for (Instruction &I : *BB) {
1163 LoadInst *LI = dyn_cast<LoadInst>(&I);
1164 if (LI && !LI->getType()->isVectorTy() && !mustSuppressSpeculation(*LI) &&
1165 isDereferenceableAndAlignedInLoop(LI, TheLoop, SE, *DT))
1166 SafePointers.insert(LI->getPointerOperand());
1170 // Collect the blocks that need predication.
1171 for (BasicBlock *BB : TheLoop->blocks()) {
1172 // We don't support switch statements inside loops.
1173 if (!isa<BranchInst>(BB->getTerminator())) {
1174 reportVectorizationFailure("Loop contains a switch statement",
1175 "loop contains a switch statement",
1176 "LoopContainsSwitch", ORE, TheLoop,
1177 BB->getTerminator());
1181 // We must be able to predicate all blocks that need to be predicated.
1182 if (blockNeedsPredication(BB)) {
1183 if (!blockCanBePredicated(BB, SafePointers, MaskedOp,
1184 ConditionalAssumes)) {
1185 reportVectorizationFailure(
1186 "Control flow cannot be substituted for a select",
1187 "control flow cannot be substituted for a select",
1188 "NoCFGForSelect", ORE, TheLoop,
1189 BB->getTerminator());
1195 // We can if-convert this loop.
1199 // Helper function to canVectorizeLoopNestCFG.
1200 bool LoopVectorizationLegality::canVectorizeLoopCFG(Loop *Lp,
1201 bool UseVPlanNativePath) {
1202 assert((UseVPlanNativePath || Lp->isInnermost()) &&
1203 "VPlan-native path is not enabled.");
1205 // TODO: ORE should be improved to show more accurate information when an
1206 // outer loop can't be vectorized because a nested loop is not understood or
1207 // legal. Something like: "outer_loop_location: loop not vectorized:
1208 // (inner_loop_location) loop control flow is not understood by vectorizer".
1210 // Store the result and return it at the end instead of exiting early, in case
1211 // allowExtraAnalysis is used to report multiple reasons for not vectorizing.
1213 bool DoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE);
1215 // We must have a loop in canonical form. Loops with indirectbr in them cannot
1216 // be canonicalized.
1217 if (!Lp->getLoopPreheader()) {
1218 reportVectorizationFailure("Loop doesn't have a legal pre-header",
1219 "loop control flow is not understood by vectorizer",
1220 "CFGNotUnderstood", ORE, TheLoop);
1221 if (DoExtraAnalysis)
1227 // We must have a single backedge.
1228 if (Lp->getNumBackEdges() != 1) {
1229 reportVectorizationFailure("The loop must have a single backedge",
1230 "loop control flow is not understood by vectorizer",
1231 "CFGNotUnderstood", ORE, TheLoop);
1232 if (DoExtraAnalysis)
1241 bool LoopVectorizationLegality::canVectorizeLoopNestCFG(
1242 Loop *Lp, bool UseVPlanNativePath) {
1243 // Store the result and return it at the end instead of exiting early, in case
1244 // allowExtraAnalysis is used to report multiple reasons for not vectorizing.
1246 bool DoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE);
1247 if (!canVectorizeLoopCFG(Lp, UseVPlanNativePath)) {
1248 if (DoExtraAnalysis)
1254 // Recursively check whether the loop control flow of nested loops is
1256 for (Loop *SubLp : *Lp)
1257 if (!canVectorizeLoopNestCFG(SubLp, UseVPlanNativePath)) {
1258 if (DoExtraAnalysis)
1267 bool LoopVectorizationLegality::canVectorize(bool UseVPlanNativePath) {
1268 // Store the result and return it at the end instead of exiting early, in case
1269 // allowExtraAnalysis is used to report multiple reasons for not vectorizing.
1272 bool DoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE);
1273 // Check whether the loop-related control flow in the loop nest is expected by
1275 if (!canVectorizeLoopNestCFG(TheLoop, UseVPlanNativePath)) {
1276 if (DoExtraAnalysis)
1282 // We need to have a loop header.
1283 LLVM_DEBUG(dbgs() << "LV: Found a loop: " << TheLoop->getHeader()->getName()
1286 // Specific checks for outer loops. We skip the remaining legal checks at this
1287 // point because they don't support outer loops.
1288 if (!TheLoop->isInnermost()) {
1289 assert(UseVPlanNativePath && "VPlan-native path is not enabled.");
1291 if (!canVectorizeOuterLoop()) {
1292 reportVectorizationFailure("Unsupported outer loop",
1293 "unsupported outer loop",
1294 "UnsupportedOuterLoop",
1296 // TODO: Implement DoExtraAnalysis when subsequent legal checks support
1301 LLVM_DEBUG(dbgs() << "LV: We can vectorize this outer loop!\n");
1305 assert(TheLoop->isInnermost() && "Inner loop expected.");
1306 // Check if we can if-convert non-single-bb loops.
1307 unsigned NumBlocks = TheLoop->getNumBlocks();
1308 if (NumBlocks != 1 && !canVectorizeWithIfConvert()) {
1309 LLVM_DEBUG(dbgs() << "LV: Can't if-convert the loop.\n");
1310 if (DoExtraAnalysis)
1316 // Check if we can vectorize the instructions and CFG in this loop.
1317 if (!canVectorizeInstrs()) {
1318 LLVM_DEBUG(dbgs() << "LV: Can't vectorize the instructions or CFG\n");
1319 if (DoExtraAnalysis)
1325 // Go over each instruction and look at memory deps.
1326 if (!canVectorizeMemory()) {
1327 LLVM_DEBUG(dbgs() << "LV: Can't vectorize due to memory conflicts\n");
1328 if (DoExtraAnalysis)
1334 LLVM_DEBUG(dbgs() << "LV: We can vectorize this loop"
1335 << (LAI->getRuntimePointerChecking()->Need
1336 ? " (with a runtime bound check)"
1340 unsigned SCEVThreshold = VectorizeSCEVCheckThreshold;
1341 if (Hints->getForce() == LoopVectorizeHints::FK_Enabled)
1342 SCEVThreshold = PragmaVectorizeSCEVCheckThreshold;
1344 if (PSE.getPredicate().getComplexity() > SCEVThreshold) {
1345 reportVectorizationFailure("Too many SCEV checks needed",
1346 "Too many SCEV assumptions need to be made and checked at runtime",
1347 "TooManySCEVRunTimeChecks", ORE, TheLoop);
1348 if (DoExtraAnalysis)
1354 // Okay! We've done all the tests. If any have failed, return false. Otherwise
1355 // we can vectorize, and at this point we don't have any other mem analysis
1356 // which may limit our maximum vectorization factor, so just return true with
1361 bool LoopVectorizationLegality::prepareToFoldTailByMasking() {
1363 LLVM_DEBUG(dbgs() << "LV: checking if tail can be folded by masking.\n");
1365 SmallPtrSet<const Value *, 8> ReductionLiveOuts;
1367 for (auto &Reduction : getReductionVars())
1368 ReductionLiveOuts.insert(Reduction.second.getLoopExitInstr());
1370 // TODO: handle non-reduction outside users when tail is folded by masking.
1371 for (auto *AE : AllowedExit) {
1372 // Check that all users of allowed exit values are inside the loop or
1373 // are the live-out of a reduction.
1374 if (ReductionLiveOuts.count(AE))
1376 for (User *U : AE->users()) {
1377 Instruction *UI = cast<Instruction>(U);
1378 if (TheLoop->contains(UI))
1382 << "LV: Cannot fold tail by masking, loop has an outside user for "
1388 // The list of pointers that we can safely read and write to remains empty.
1389 SmallPtrSet<Value *, 8> SafePointers;
1391 SmallPtrSet<const Instruction *, 8> TmpMaskedOp;
1392 SmallPtrSet<Instruction *, 8> TmpConditionalAssumes;
1394 // Check and mark all blocks for predication, including those that ordinarily
1395 // do not need predication such as the header block.
1396 for (BasicBlock *BB : TheLoop->blocks()) {
1397 if (!blockCanBePredicated(BB, SafePointers, TmpMaskedOp,
1398 TmpConditionalAssumes)) {
1399 LLVM_DEBUG(dbgs() << "LV: Cannot fold tail by masking as requested.\n");
1404 LLVM_DEBUG(dbgs() << "LV: can fold tail by masking.\n");
1406 MaskedOp.insert(TmpMaskedOp.begin(), TmpMaskedOp.end());
1407 ConditionalAssumes.insert(TmpConditionalAssumes.begin(),
1408 TmpConditionalAssumes.end());