1 //===- LoopVectorizationLegality.cpp --------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file provides loop vectorization legality analysis. Original code
11 // resided in LoopVectorize.cpp for a long time.
13 // At this point, it is implemented as a utility class, not as an analysis
14 // pass. It should be easy to create an analysis pass around it if there
15 // is a need (but D45420 needs to happen first).
17 #include "llvm/Transforms/Vectorize/LoopVectorizationLegality.h"
18 #include "llvm/Analysis/VectorUtils.h"
19 #include "llvm/IR/IntrinsicInst.h"
23 #define LV_NAME "loop-vectorize"
24 #define DEBUG_TYPE LV_NAME
27 EnableIfConversion("enable-if-conversion", cl::init(true), cl::Hidden,
28 cl::desc("Enable if-conversion during vectorization."));
30 static cl::opt<unsigned> PragmaVectorizeMemoryCheckThreshold(
31 "pragma-vectorize-memory-check-threshold", cl::init(128), cl::Hidden,
32 cl::desc("The maximum allowed number of runtime memory checks with a "
33 "vectorize(enable) pragma."));
35 static cl::opt<unsigned> VectorizeSCEVCheckThreshold(
36 "vectorize-scev-check-threshold", cl::init(16), cl::Hidden,
37 cl::desc("The maximum number of SCEV checks allowed."));
39 static cl::opt<unsigned> PragmaVectorizeSCEVCheckThreshold(
40 "pragma-vectorize-scev-check-threshold", cl::init(128), cl::Hidden,
41 cl::desc("The maximum number of SCEV checks allowed with a "
42 "vectorize(enable) pragma"));
44 /// Maximum vectorization interleave count.
45 static const unsigned MaxInterleaveFactor = 16;
49 OptimizationRemarkAnalysis createLVMissedAnalysis(const char *PassName,
53 Value *CodeRegion = TheLoop->getHeader();
54 DebugLoc DL = TheLoop->getStartLoc();
57 CodeRegion = I->getParent();
58 // If there is no debug location attached to the instruction, revert back to
61 DL = I->getDebugLoc();
64 OptimizationRemarkAnalysis R(PassName, RemarkName, DL, CodeRegion);
65 R << "loop not vectorized: ";
69 bool LoopVectorizeHints::Hint::validate(unsigned Val) {
72 return isPowerOf2_32(Val) && Val <= VectorizerParams::MaxVectorWidth;
74 return isPowerOf2_32(Val) && Val <= MaxInterleaveFactor;
78 return (Val == 0 || Val == 1);
83 LoopVectorizeHints::LoopVectorizeHints(const Loop *L, bool DisableInterleaving,
84 OptimizationRemarkEmitter &ORE)
85 : Width("vectorize.width", VectorizerParams::VectorizationFactor, HK_WIDTH),
86 Interleave("interleave.count", DisableInterleaving, HK_UNROLL),
87 Force("vectorize.enable", FK_Undefined, HK_FORCE),
88 IsVectorized("isvectorized", 0, HK_ISVECTORIZED), TheLoop(L), ORE(ORE) {
89 // Populate values with existing loop metadata.
90 getHintsFromMetadata();
92 // force-vector-interleave overrides DisableInterleaving.
93 if (VectorizerParams::isInterleaveForced())
94 Interleave.Value = VectorizerParams::VectorizationInterleave;
96 if (IsVectorized.Value != 1)
97 // If the vectorization width and interleaving count are both 1 then
98 // consider the loop to have been already vectorized because there's
99 // nothing more that we can do.
100 IsVectorized.Value = Width.Value == 1 && Interleave.Value == 1;
101 LLVM_DEBUG(if (DisableInterleaving && Interleave.Value == 1) dbgs()
102 << "LV: Interleaving disabled by the pass manager\n");
105 bool LoopVectorizeHints::allowVectorization(Function *F, Loop *L,
106 bool AlwaysVectorize) const {
107 if (getForce() == LoopVectorizeHints::FK_Disabled) {
108 LLVM_DEBUG(dbgs() << "LV: Not vectorizing: #pragma vectorize disable.\n");
109 emitRemarkWithHints();
113 if (!AlwaysVectorize && getForce() != LoopVectorizeHints::FK_Enabled) {
114 LLVM_DEBUG(dbgs() << "LV: Not vectorizing: No #pragma vectorize enable.\n");
115 emitRemarkWithHints();
119 if (getIsVectorized() == 1) {
120 LLVM_DEBUG(dbgs() << "LV: Not vectorizing: Disabled/already vectorized.\n");
121 // FIXME: Add interleave.disable metadata. This will allow
122 // vectorize.disable to be used without disabling the pass and errors
123 // to differentiate between disabled vectorization and a width of 1.
125 return OptimizationRemarkAnalysis(vectorizeAnalysisPassName(),
126 "AllDisabled", L->getStartLoc(),
128 << "loop not vectorized: vectorization and interleaving are "
129 "explicitly disabled, or the loop has already been "
138 void LoopVectorizeHints::emitRemarkWithHints() const {
142 if (Force.Value == LoopVectorizeHints::FK_Disabled)
143 return OptimizationRemarkMissed(LV_NAME, "MissedExplicitlyDisabled",
144 TheLoop->getStartLoc(),
145 TheLoop->getHeader())
146 << "loop not vectorized: vectorization is explicitly disabled";
148 OptimizationRemarkMissed R(LV_NAME, "MissedDetails",
149 TheLoop->getStartLoc(), TheLoop->getHeader());
150 R << "loop not vectorized";
151 if (Force.Value == LoopVectorizeHints::FK_Enabled) {
152 R << " (Force=" << NV("Force", true);
153 if (Width.Value != 0)
154 R << ", Vector Width=" << NV("VectorWidth", Width.Value);
155 if (Interleave.Value != 0)
156 R << ", Interleave Count=" << NV("InterleaveCount", Interleave.Value);
164 const char *LoopVectorizeHints::vectorizeAnalysisPassName() const {
167 if (getForce() == LoopVectorizeHints::FK_Disabled)
169 if (getForce() == LoopVectorizeHints::FK_Undefined && getWidth() == 0)
171 return OptimizationRemarkAnalysis::AlwaysPrint;
174 void LoopVectorizeHints::getHintsFromMetadata() {
175 MDNode *LoopID = TheLoop->getLoopID();
179 // First operand should refer to the loop id itself.
180 assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
181 assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
183 for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
184 const MDString *S = nullptr;
185 SmallVector<Metadata *, 4> Args;
187 // The expected hint is either a MDString or a MDNode with the first
188 // operand a MDString.
189 if (const MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i))) {
190 if (!MD || MD->getNumOperands() == 0)
192 S = dyn_cast<MDString>(MD->getOperand(0));
193 for (unsigned i = 1, ie = MD->getNumOperands(); i < ie; ++i)
194 Args.push_back(MD->getOperand(i));
196 S = dyn_cast<MDString>(LoopID->getOperand(i));
197 assert(Args.size() == 0 && "too many arguments for MDString");
203 // Check if the hint starts with the loop metadata prefix.
204 StringRef Name = S->getString();
205 if (Args.size() == 1)
206 setHint(Name, Args[0]);
210 void LoopVectorizeHints::setHint(StringRef Name, Metadata *Arg) {
211 if (!Name.startswith(Prefix()))
213 Name = Name.substr(Prefix().size(), StringRef::npos);
215 const ConstantInt *C = mdconst::dyn_extract<ConstantInt>(Arg);
218 unsigned Val = C->getZExtValue();
220 Hint *Hints[] = {&Width, &Interleave, &Force, &IsVectorized};
221 for (auto H : Hints) {
222 if (Name == H->Name) {
223 if (H->validate(Val))
226 LLVM_DEBUG(dbgs() << "LV: ignoring invalid hint '" << Name << "'\n");
232 MDNode *LoopVectorizeHints::createHintMetadata(StringRef Name,
234 LLVMContext &Context = TheLoop->getHeader()->getContext();
236 MDString::get(Context, Name),
237 ConstantAsMetadata::get(ConstantInt::get(Type::getInt32Ty(Context), V))};
238 return MDNode::get(Context, MDs);
241 bool LoopVectorizeHints::matchesHintMetadataName(MDNode *Node,
242 ArrayRef<Hint> HintTypes) {
243 MDString *Name = dyn_cast<MDString>(Node->getOperand(0));
247 for (auto H : HintTypes)
248 if (Name->getString().endswith(H.Name))
253 void LoopVectorizeHints::writeHintsToMetadata(ArrayRef<Hint> HintTypes) {
254 if (HintTypes.empty())
257 // Reserve the first element to LoopID (see below).
258 SmallVector<Metadata *, 4> MDs(1);
259 // If the loop already has metadata, then ignore the existing operands.
260 MDNode *LoopID = TheLoop->getLoopID();
262 for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
263 MDNode *Node = cast<MDNode>(LoopID->getOperand(i));
264 // If node in update list, ignore old value.
265 if (!matchesHintMetadataName(Node, HintTypes))
270 // Now, add the missing hints.
271 for (auto H : HintTypes)
272 MDs.push_back(createHintMetadata(Twine(Prefix(), H.Name).str(), H.Value));
274 // Replace current metadata node with new one.
275 LLVMContext &Context = TheLoop->getHeader()->getContext();
276 MDNode *NewLoopID = MDNode::get(Context, MDs);
277 // Set operand 0 to refer to the loop id itself.
278 NewLoopID->replaceOperandWith(0, NewLoopID);
280 TheLoop->setLoopID(NewLoopID);
283 bool LoopVectorizationRequirements::doesNotMeet(
284 Function *F, Loop *L, const LoopVectorizeHints &Hints) {
285 const char *PassName = Hints.vectorizeAnalysisPassName();
287 if (UnsafeAlgebraInst && !Hints.allowReordering()) {
289 return OptimizationRemarkAnalysisFPCommute(
290 PassName, "CantReorderFPOps", UnsafeAlgebraInst->getDebugLoc(),
291 UnsafeAlgebraInst->getParent())
292 << "loop not vectorized: cannot prove it is safe to reorder "
293 "floating-point operations";
298 // Test if runtime memcheck thresholds are exceeded.
299 bool PragmaThresholdReached =
300 NumRuntimePointerChecks > PragmaVectorizeMemoryCheckThreshold;
301 bool ThresholdReached =
302 NumRuntimePointerChecks > VectorizerParams::RuntimeMemoryCheckThreshold;
303 if ((ThresholdReached && !Hints.allowReordering()) ||
304 PragmaThresholdReached) {
306 return OptimizationRemarkAnalysisAliasing(PassName, "CantReorderMemOps",
309 << "loop not vectorized: cannot prove it is safe to reorder "
312 LLVM_DEBUG(dbgs() << "LV: Too many memory checks needed.\n");
319 // Return true if the inner loop \p Lp is uniform with regard to the outer loop
320 // \p OuterLp (i.e., if the outer loop is vectorized, all the vector lanes
321 // executing the inner loop will execute the same iterations). This check is
322 // very constrained for now but it will be relaxed in the future. \p Lp is
323 // considered uniform if it meets all the following conditions:
324 // 1) it has a canonical IV (starting from 0 and with stride 1),
325 // 2) its latch terminator is a conditional branch and,
326 // 3) its latch condition is a compare instruction whose operands are the
327 // canonical IV and an OuterLp invariant.
328 // This check doesn't take into account the uniformity of other conditions not
329 // related to the loop latch because they don't affect the loop uniformity.
331 // NOTE: We decided to keep all these checks and its associated documentation
332 // together so that we can easily have a picture of the current supported loop
333 // nests. However, some of the current checks don't depend on \p OuterLp and
334 // would be redundantly executed for each \p Lp if we invoked this function for
335 // different candidate outer loops. This is not the case for now because we
336 // don't currently have the infrastructure to evaluate multiple candidate outer
337 // loops and \p OuterLp will be a fixed parameter while we only support explicit
338 // outer loop vectorization. It's also very likely that these checks go away
339 // before introducing the aforementioned infrastructure. However, if this is not
340 // the case, we should move the \p OuterLp independent checks to a separate
341 // function that is only executed once for each \p Lp.
342 static bool isUniformLoop(Loop *Lp, Loop *OuterLp) {
343 assert(Lp->getLoopLatch() && "Expected loop with a single latch.");
345 // If Lp is the outer loop, it's uniform by definition.
348 assert(OuterLp->contains(Lp) && "OuterLp must contain Lp.");
351 PHINode *IV = Lp->getCanonicalInductionVariable();
353 LLVM_DEBUG(dbgs() << "LV: Canonical IV not found.\n");
358 BasicBlock *Latch = Lp->getLoopLatch();
359 auto *LatchBr = dyn_cast<BranchInst>(Latch->getTerminator());
360 if (!LatchBr || LatchBr->isUnconditional()) {
361 LLVM_DEBUG(dbgs() << "LV: Unsupported loop latch branch.\n");
366 auto *LatchCmp = dyn_cast<CmpInst>(LatchBr->getCondition());
369 dbgs() << "LV: Loop latch condition is not a compare instruction.\n");
373 Value *CondOp0 = LatchCmp->getOperand(0);
374 Value *CondOp1 = LatchCmp->getOperand(1);
375 Value *IVUpdate = IV->getIncomingValueForBlock(Latch);
376 if (!(CondOp0 == IVUpdate && OuterLp->isLoopInvariant(CondOp1)) &&
377 !(CondOp1 == IVUpdate && OuterLp->isLoopInvariant(CondOp0))) {
378 LLVM_DEBUG(dbgs() << "LV: Loop latch condition is not uniform.\n");
385 // Return true if \p Lp and all its nested loops are uniform with regard to \p
387 static bool isUniformLoopNest(Loop *Lp, Loop *OuterLp) {
388 if (!isUniformLoop(Lp, OuterLp))
391 // Check if nested loops are uniform.
392 for (Loop *SubLp : *Lp)
393 if (!isUniformLoopNest(SubLp, OuterLp))
399 /// Check whether it is safe to if-convert this phi node.
401 /// Phi nodes with constant expressions that can trap are not safe to if
403 static bool canIfConvertPHINodes(BasicBlock *BB) {
404 for (PHINode &Phi : BB->phis()) {
405 for (Value *V : Phi.incoming_values())
406 if (auto *C = dyn_cast<Constant>(V))
413 static Type *convertPointerToIntegerType(const DataLayout &DL, Type *Ty) {
414 if (Ty->isPointerTy())
415 return DL.getIntPtrType(Ty);
417 // It is possible that char's or short's overflow when we ask for the loop's
418 // trip count, work around this by changing the type size.
419 if (Ty->getScalarSizeInBits() < 32)
420 return Type::getInt32Ty(Ty->getContext());
425 static Type *getWiderType(const DataLayout &DL, Type *Ty0, Type *Ty1) {
426 Ty0 = convertPointerToIntegerType(DL, Ty0);
427 Ty1 = convertPointerToIntegerType(DL, Ty1);
428 if (Ty0->getScalarSizeInBits() > Ty1->getScalarSizeInBits())
433 /// Check that the instruction has outside loop users and is not an
434 /// identified reduction variable.
435 static bool hasOutsideLoopUser(const Loop *TheLoop, Instruction *Inst,
436 SmallPtrSetImpl<Value *> &AllowedExit) {
437 // Reduction and Induction instructions are allowed to have exit users. All
438 // other instructions must not have external users.
439 if (!AllowedExit.count(Inst))
440 // Check that all of the users of the loop are inside the BB.
441 for (User *U : Inst->users()) {
442 Instruction *UI = cast<Instruction>(U);
443 // This user may be a reduction exit value.
444 if (!TheLoop->contains(UI)) {
445 LLVM_DEBUG(dbgs() << "LV: Found an outside user for : " << *UI << '\n');
452 int LoopVectorizationLegality::isConsecutivePtr(Value *Ptr) {
453 const ValueToValueMap &Strides =
454 getSymbolicStrides() ? *getSymbolicStrides() : ValueToValueMap();
456 int Stride = getPtrStride(PSE, Ptr, TheLoop, Strides, true, false);
457 if (Stride == 1 || Stride == -1)
462 bool LoopVectorizationLegality::isUniform(Value *V) {
463 return LAI->isUniform(V);
466 bool LoopVectorizationLegality::canVectorizeOuterLoop() {
467 assert(!TheLoop->empty() && "We are not vectorizing an outer loop.");
468 // Store the result and return it at the end instead of exiting early, in case
469 // allowExtraAnalysis is used to report multiple reasons for not vectorizing.
471 bool DoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE);
473 for (BasicBlock *BB : TheLoop->blocks()) {
474 // Check whether the BB terminator is a BranchInst. Any other terminator is
475 // not supported yet.
476 auto *Br = dyn_cast<BranchInst>(BB->getTerminator());
478 LLVM_DEBUG(dbgs() << "LV: Unsupported basic block terminator.\n");
479 ORE->emit(createMissedAnalysis("CFGNotUnderstood")
480 << "loop control flow is not understood by vectorizer");
487 // Check whether the BranchInst is a supported one. Only unconditional
488 // branches, conditional branches with an outer loop invariant condition or
489 // backedges are supported.
490 if (Br && Br->isConditional() &&
491 !TheLoop->isLoopInvariant(Br->getCondition()) &&
492 !LI->isLoopHeader(Br->getSuccessor(0)) &&
493 !LI->isLoopHeader(Br->getSuccessor(1))) {
494 LLVM_DEBUG(dbgs() << "LV: Unsupported conditional branch.\n");
495 ORE->emit(createMissedAnalysis("CFGNotUnderstood")
496 << "loop control flow is not understood by vectorizer");
504 // Check whether inner loops are uniform. At this point, we only support
505 // simple outer loops scenarios with uniform nested loops.
506 if (!isUniformLoopNest(TheLoop /*loop nest*/,
507 TheLoop /*context outer loop*/)) {
510 << "LV: Not vectorizing: Outer loop contains divergent loops.\n");
511 ORE->emit(createMissedAnalysis("CFGNotUnderstood")
512 << "loop control flow is not understood by vectorizer");
522 void LoopVectorizationLegality::addInductionPhi(
523 PHINode *Phi, const InductionDescriptor &ID,
524 SmallPtrSetImpl<Value *> &AllowedExit) {
525 Inductions[Phi] = ID;
527 // In case this induction also comes with casts that we know we can ignore
528 // in the vectorized loop body, record them here. All casts could be recorded
529 // here for ignoring, but suffices to record only the first (as it is the
530 // only one that may bw used outside the cast sequence).
531 const SmallVectorImpl<Instruction *> &Casts = ID.getCastInsts();
533 InductionCastsToIgnore.insert(*Casts.begin());
535 Type *PhiTy = Phi->getType();
536 const DataLayout &DL = Phi->getModule()->getDataLayout();
538 // Get the widest type.
539 if (!PhiTy->isFloatingPointTy()) {
541 WidestIndTy = convertPointerToIntegerType(DL, PhiTy);
543 WidestIndTy = getWiderType(DL, PhiTy, WidestIndTy);
546 // Int inductions are special because we only allow one IV.
547 if (ID.getKind() == InductionDescriptor::IK_IntInduction &&
548 ID.getConstIntStepValue() && ID.getConstIntStepValue()->isOne() &&
549 isa<Constant>(ID.getStartValue()) &&
550 cast<Constant>(ID.getStartValue())->isNullValue()) {
552 // Use the phi node with the widest type as induction. Use the last
553 // one if there are multiple (no good reason for doing this other
554 // than it is expedient). We've checked that it begins at zero and
555 // steps by one, so this is a canonical induction variable.
556 if (!PrimaryInduction || PhiTy == WidestIndTy)
557 PrimaryInduction = Phi;
560 // Both the PHI node itself, and the "post-increment" value feeding
561 // back into the PHI node may have external users.
562 // We can allow those uses, except if the SCEVs we have for them rely
563 // on predicates that only hold within the loop, since allowing the exit
564 // currently means re-using this SCEV outside the loop.
565 if (PSE.getUnionPredicate().isAlwaysTrue()) {
566 AllowedExit.insert(Phi);
567 AllowedExit.insert(Phi->getIncomingValueForBlock(TheLoop->getLoopLatch()));
570 LLVM_DEBUG(dbgs() << "LV: Found an induction variable.\n");
573 bool LoopVectorizationLegality::canVectorizeInstrs() {
574 BasicBlock *Header = TheLoop->getHeader();
576 // Look for the attribute signaling the absence of NaNs.
577 Function &F = *Header->getParent();
579 F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true";
581 // For each block in the loop.
582 for (BasicBlock *BB : TheLoop->blocks()) {
583 // Scan the instructions in the block and look for hazards.
584 for (Instruction &I : *BB) {
585 if (auto *Phi = dyn_cast<PHINode>(&I)) {
586 Type *PhiTy = Phi->getType();
587 // Check that this PHI type is allowed.
588 if (!PhiTy->isIntegerTy() && !PhiTy->isFloatingPointTy() &&
589 !PhiTy->isPointerTy()) {
590 ORE->emit(createMissedAnalysis("CFGNotUnderstood", Phi)
591 << "loop control flow is not understood by vectorizer");
592 LLVM_DEBUG(dbgs() << "LV: Found an non-int non-pointer PHI.\n");
596 // If this PHINode is not in the header block, then we know that we
597 // can convert it to select during if-conversion. No need to check if
598 // the PHIs in this block are induction or reduction variables.
600 // Check that this instruction has no outside users or is an
601 // identified reduction value with an outside user.
602 if (!hasOutsideLoopUser(TheLoop, Phi, AllowedExit))
604 ORE->emit(createMissedAnalysis("NeitherInductionNorReduction", Phi)
605 << "value could not be identified as "
606 "an induction or reduction variable");
610 // We only allow if-converted PHIs with exactly two incoming values.
611 if (Phi->getNumIncomingValues() != 2) {
612 ORE->emit(createMissedAnalysis("CFGNotUnderstood", Phi)
613 << "control flow not understood by vectorizer");
614 LLVM_DEBUG(dbgs() << "LV: Found an invalid PHI.\n");
618 RecurrenceDescriptor RedDes;
619 if (RecurrenceDescriptor::isReductionPHI(Phi, TheLoop, RedDes, DB, AC,
621 if (RedDes.hasUnsafeAlgebra())
622 Requirements->addUnsafeAlgebraInst(RedDes.getUnsafeAlgebraInst());
623 AllowedExit.insert(RedDes.getLoopExitInstr());
624 Reductions[Phi] = RedDes;
628 InductionDescriptor ID;
629 if (InductionDescriptor::isInductionPHI(Phi, TheLoop, PSE, ID)) {
630 addInductionPhi(Phi, ID, AllowedExit);
631 if (ID.hasUnsafeAlgebra() && !HasFunNoNaNAttr)
632 Requirements->addUnsafeAlgebraInst(ID.getUnsafeAlgebraInst());
636 if (RecurrenceDescriptor::isFirstOrderRecurrence(Phi, TheLoop,
638 FirstOrderRecurrences.insert(Phi);
642 // As a last resort, coerce the PHI to a AddRec expression
643 // and re-try classifying it a an induction PHI.
644 if (InductionDescriptor::isInductionPHI(Phi, TheLoop, PSE, ID, true)) {
645 addInductionPhi(Phi, ID, AllowedExit);
649 ORE->emit(createMissedAnalysis("NonReductionValueUsedOutsideLoop", Phi)
650 << "value that could not be identified as "
651 "reduction is used outside the loop");
652 LLVM_DEBUG(dbgs() << "LV: Found an unidentified PHI." << *Phi << "\n");
654 } // end of PHI handling
656 // We handle calls that:
657 // * Are debug info intrinsics.
658 // * Have a mapping to an IR intrinsic.
659 // * Have a vector version available.
660 auto *CI = dyn_cast<CallInst>(&I);
661 if (CI && !getVectorIntrinsicIDForCall(CI, TLI) &&
662 !isa<DbgInfoIntrinsic>(CI) &&
663 !(CI->getCalledFunction() && TLI &&
664 TLI->isFunctionVectorizable(CI->getCalledFunction()->getName()))) {
665 ORE->emit(createMissedAnalysis("CantVectorizeCall", CI)
666 << "call instruction cannot be vectorized");
668 dbgs() << "LV: Found a non-intrinsic, non-libfunc callsite.\n");
672 // Intrinsics such as powi,cttz and ctlz are legal to vectorize if the
673 // second argument is the same (i.e. loop invariant)
674 if (CI && hasVectorInstrinsicScalarOpd(
675 getVectorIntrinsicIDForCall(CI, TLI), 1)) {
676 auto *SE = PSE.getSE();
677 if (!SE->isLoopInvariant(PSE.getSCEV(CI->getOperand(1)), TheLoop)) {
678 ORE->emit(createMissedAnalysis("CantVectorizeIntrinsic", CI)
679 << "intrinsic instruction cannot be vectorized");
681 << "LV: Found unvectorizable intrinsic " << *CI << "\n");
686 // Check that the instruction return type is vectorizable.
687 // Also, we can't vectorize extractelement instructions.
688 if ((!VectorType::isValidElementType(I.getType()) &&
689 !I.getType()->isVoidTy()) ||
690 isa<ExtractElementInst>(I)) {
691 ORE->emit(createMissedAnalysis("CantVectorizeInstructionReturnType", &I)
692 << "instruction return type cannot be vectorized");
693 LLVM_DEBUG(dbgs() << "LV: Found unvectorizable type.\n");
697 // Check that the stored type is vectorizable.
698 if (auto *ST = dyn_cast<StoreInst>(&I)) {
699 Type *T = ST->getValueOperand()->getType();
700 if (!VectorType::isValidElementType(T)) {
701 ORE->emit(createMissedAnalysis("CantVectorizeStore", ST)
702 << "store instruction cannot be vectorized");
706 // FP instructions can allow unsafe algebra, thus vectorizable by
707 // non-IEEE-754 compliant SIMD units.
708 // This applies to floating-point math operations and calls, not memory
709 // operations, shuffles, or casts, as they don't change precision or
711 } else if (I.getType()->isFloatingPointTy() && (CI || I.isBinaryOp()) &&
713 LLVM_DEBUG(dbgs() << "LV: Found FP op with unsafe algebra.\n");
714 Hints->setPotentiallyUnsafe();
717 // Reduction instructions are allowed to have exit users.
718 // All other instructions must not have external users.
719 if (hasOutsideLoopUser(TheLoop, &I, AllowedExit)) {
720 ORE->emit(createMissedAnalysis("ValueUsedOutsideLoop", &I)
721 << "value cannot be used outside the loop");
727 if (!PrimaryInduction) {
728 LLVM_DEBUG(dbgs() << "LV: Did not find one integer induction var.\n");
729 if (Inductions.empty()) {
730 ORE->emit(createMissedAnalysis("NoInductionVariable")
731 << "loop induction variable could not be identified");
736 // Now we know the widest induction type, check if our found induction
737 // is the same size. If it's not, unset it here and InnerLoopVectorizer
738 // will create another.
739 if (PrimaryInduction && WidestIndTy != PrimaryInduction->getType())
740 PrimaryInduction = nullptr;
745 bool LoopVectorizationLegality::canVectorizeMemory() {
746 LAI = &(*GetLAA)(*TheLoop);
747 const OptimizationRemarkAnalysis *LAR = LAI->getReport();
750 return OptimizationRemarkAnalysis(Hints->vectorizeAnalysisPassName(),
751 "loop not vectorized: ", *LAR);
754 if (!LAI->canVectorizeMemory())
757 if (LAI->hasStoreToLoopInvariantAddress()) {
758 ORE->emit(createMissedAnalysis("CantVectorizeStoreToLoopInvariantAddress")
759 << "write to a loop invariant address could not be vectorized");
760 LLVM_DEBUG(dbgs() << "LV: We don't allow storing to uniform addresses\n");
764 Requirements->addRuntimePointerChecks(LAI->getNumRuntimePointerChecks());
765 PSE.addPredicate(LAI->getPSE().getUnionPredicate());
770 bool LoopVectorizationLegality::isInductionPhi(const Value *V) {
771 Value *In0 = const_cast<Value *>(V);
772 PHINode *PN = dyn_cast_or_null<PHINode>(In0);
776 return Inductions.count(PN);
779 bool LoopVectorizationLegality::isCastedInductionVariable(const Value *V) {
780 auto *Inst = dyn_cast<Instruction>(V);
781 return (Inst && InductionCastsToIgnore.count(Inst));
784 bool LoopVectorizationLegality::isInductionVariable(const Value *V) {
785 return isInductionPhi(V) || isCastedInductionVariable(V);
788 bool LoopVectorizationLegality::isFirstOrderRecurrence(const PHINode *Phi) {
789 return FirstOrderRecurrences.count(Phi);
792 bool LoopVectorizationLegality::blockNeedsPredication(BasicBlock *BB) {
793 return LoopAccessInfo::blockNeedsPredication(BB, TheLoop, DT);
796 bool LoopVectorizationLegality::blockCanBePredicated(
797 BasicBlock *BB, SmallPtrSetImpl<Value *> &SafePtrs) {
798 const bool IsAnnotatedParallel = TheLoop->isAnnotatedParallel();
800 for (Instruction &I : *BB) {
801 // Check that we don't have a constant expression that can trap as operand.
802 for (Value *Operand : I.operands()) {
803 if (auto *C = dyn_cast<Constant>(Operand))
807 // We might be able to hoist the load.
808 if (I.mayReadFromMemory()) {
809 auto *LI = dyn_cast<LoadInst>(&I);
812 if (!SafePtrs.count(LI->getPointerOperand())) {
813 // !llvm.mem.parallel_loop_access implies if-conversion safety.
814 // Otherwise, record that the load needs (real or emulated) masking
815 // and let the cost model decide.
816 if (!IsAnnotatedParallel)
822 if (I.mayWriteToMemory()) {
823 auto *SI = dyn_cast<StoreInst>(&I);
826 // Predicated store requires some form of masking:
827 // 1) masked store HW instruction,
828 // 2) emulation via load-blend-store (only if safe and legal to do so,
829 // be aware on the race conditions), or
830 // 3) element-by-element predicate check and scalar store.
841 bool LoopVectorizationLegality::canVectorizeWithIfConvert() {
842 if (!EnableIfConversion) {
843 ORE->emit(createMissedAnalysis("IfConversionDisabled")
844 << "if-conversion is disabled");
848 assert(TheLoop->getNumBlocks() > 1 && "Single block loops are vectorizable");
850 // A list of pointers that we can safely read and write to.
851 SmallPtrSet<Value *, 8> SafePointes;
853 // Collect safe addresses.
854 for (BasicBlock *BB : TheLoop->blocks()) {
855 if (blockNeedsPredication(BB))
858 for (Instruction &I : *BB)
859 if (auto *Ptr = getLoadStorePointerOperand(&I))
860 SafePointes.insert(Ptr);
863 // Collect the blocks that need predication.
864 BasicBlock *Header = TheLoop->getHeader();
865 for (BasicBlock *BB : TheLoop->blocks()) {
866 // We don't support switch statements inside loops.
867 if (!isa<BranchInst>(BB->getTerminator())) {
868 ORE->emit(createMissedAnalysis("LoopContainsSwitch", BB->getTerminator())
869 << "loop contains a switch statement");
873 // We must be able to predicate all blocks that need to be predicated.
874 if (blockNeedsPredication(BB)) {
875 if (!blockCanBePredicated(BB, SafePointes)) {
876 ORE->emit(createMissedAnalysis("NoCFGForSelect", BB->getTerminator())
877 << "control flow cannot be substituted for a select");
880 } else if (BB != Header && !canIfConvertPHINodes(BB)) {
881 ORE->emit(createMissedAnalysis("NoCFGForSelect", BB->getTerminator())
882 << "control flow cannot be substituted for a select");
887 // We can if-convert this loop.
891 // Helper function to canVectorizeLoopNestCFG.
892 bool LoopVectorizationLegality::canVectorizeLoopCFG(Loop *Lp,
893 bool UseVPlanNativePath) {
894 assert((UseVPlanNativePath || Lp->empty()) &&
895 "VPlan-native path is not enabled.");
897 // TODO: ORE should be improved to show more accurate information when an
898 // outer loop can't be vectorized because a nested loop is not understood or
899 // legal. Something like: "outer_loop_location: loop not vectorized:
900 // (inner_loop_location) loop control flow is not understood by vectorizer".
902 // Store the result and return it at the end instead of exiting early, in case
903 // allowExtraAnalysis is used to report multiple reasons for not vectorizing.
905 bool DoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE);
907 // We must have a loop in canonical form. Loops with indirectbr in them cannot
909 if (!Lp->getLoopPreheader()) {
910 LLVM_DEBUG(dbgs() << "LV: Loop doesn't have a legal pre-header.\n");
911 ORE->emit(createMissedAnalysis("CFGNotUnderstood")
912 << "loop control flow is not understood by vectorizer");
919 // We must have a single backedge.
920 if (Lp->getNumBackEdges() != 1) {
921 ORE->emit(createMissedAnalysis("CFGNotUnderstood")
922 << "loop control flow is not understood by vectorizer");
929 // We must have a single exiting block.
930 if (!Lp->getExitingBlock()) {
931 ORE->emit(createMissedAnalysis("CFGNotUnderstood")
932 << "loop control flow is not understood by vectorizer");
939 // We only handle bottom-tested loops, i.e. loop in which the condition is
940 // checked at the end of each iteration. With that we can assume that all
941 // instructions in the loop are executed the same number of times.
942 if (Lp->getExitingBlock() != Lp->getLoopLatch()) {
943 ORE->emit(createMissedAnalysis("CFGNotUnderstood")
944 << "loop control flow is not understood by vectorizer");
954 bool LoopVectorizationLegality::canVectorizeLoopNestCFG(
955 Loop *Lp, bool UseVPlanNativePath) {
956 // Store the result and return it at the end instead of exiting early, in case
957 // allowExtraAnalysis is used to report multiple reasons for not vectorizing.
959 bool DoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE);
960 if (!canVectorizeLoopCFG(Lp, UseVPlanNativePath)) {
967 // Recursively check whether the loop control flow of nested loops is
969 for (Loop *SubLp : *Lp)
970 if (!canVectorizeLoopNestCFG(SubLp, UseVPlanNativePath)) {
980 bool LoopVectorizationLegality::canVectorize(bool UseVPlanNativePath) {
981 // Store the result and return it at the end instead of exiting early, in case
982 // allowExtraAnalysis is used to report multiple reasons for not vectorizing.
985 bool DoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE);
986 // Check whether the loop-related control flow in the loop nest is expected by
988 if (!canVectorizeLoopNestCFG(TheLoop, UseVPlanNativePath)) {
995 // We need to have a loop header.
996 LLVM_DEBUG(dbgs() << "LV: Found a loop: " << TheLoop->getHeader()->getName()
999 // Specific checks for outer loops. We skip the remaining legal checks at this
1000 // point because they don't support outer loops.
1001 if (!TheLoop->empty()) {
1002 assert(UseVPlanNativePath && "VPlan-native path is not enabled.");
1004 if (!canVectorizeOuterLoop()) {
1005 LLVM_DEBUG(dbgs() << "LV: Not vectorizing: Unsupported outer loop.\n");
1006 // TODO: Implement DoExtraAnalysis when subsequent legal checks support
1011 LLVM_DEBUG(dbgs() << "LV: We can vectorize this outer loop!\n");
1015 assert(TheLoop->empty() && "Inner loop expected.");
1016 // Check if we can if-convert non-single-bb loops.
1017 unsigned NumBlocks = TheLoop->getNumBlocks();
1018 if (NumBlocks != 1 && !canVectorizeWithIfConvert()) {
1019 LLVM_DEBUG(dbgs() << "LV: Can't if-convert the loop.\n");
1020 if (DoExtraAnalysis)
1026 // Check if we can vectorize the instructions and CFG in this loop.
1027 if (!canVectorizeInstrs()) {
1028 LLVM_DEBUG(dbgs() << "LV: Can't vectorize the instructions or CFG\n");
1029 if (DoExtraAnalysis)
1035 // Go over each instruction and look at memory deps.
1036 if (!canVectorizeMemory()) {
1037 LLVM_DEBUG(dbgs() << "LV: Can't vectorize due to memory conflicts\n");
1038 if (DoExtraAnalysis)
1044 LLVM_DEBUG(dbgs() << "LV: We can vectorize this loop"
1045 << (LAI->getRuntimePointerChecking()->Need
1046 ? " (with a runtime bound check)"
1050 unsigned SCEVThreshold = VectorizeSCEVCheckThreshold;
1051 if (Hints->getForce() == LoopVectorizeHints::FK_Enabled)
1052 SCEVThreshold = PragmaVectorizeSCEVCheckThreshold;
1054 if (PSE.getUnionPredicate().getComplexity() > SCEVThreshold) {
1055 ORE->emit(createMissedAnalysis("TooManySCEVRunTimeChecks")
1056 << "Too many SCEV assumptions need to be made and checked "
1058 LLVM_DEBUG(dbgs() << "LV: Too many SCEV checks needed.\n");
1059 if (DoExtraAnalysis)
1065 // Okay! We've done all the tests. If any have failed, return false. Otherwise
1066 // we can vectorize, and at this point we don't have any other mem analysis
1067 // which may limit our maximum vectorization factor, so just return true with