41#define LV_NAME "loop-vectorize"
42#define DEBUG_TYPE LV_NAME
49bool LoopVectorizeHints::Hint::validate(
unsigned Val) {
56 return (Val == 0 || Val == 1);
63 bool InterleaveOnlyWhenForced,
67 Width(
"vectorize.width",
69 Interleave(
"interleave.count", InterleaveOnlyWhenForced, HK_INTERLEAVE),
70 Force(
FK_Undefined), IsVectorized(
"isvectorized", 0, HK_ISVECTORIZED),
72 TheLoop(L), ORE(ORE) {
74 getHintsFromMetadata();
81 auto ComputeScalable =
89 return ForceScalableHint;
93 return ForceScalableOpt;
96 if (ForceWidthOpt.isScalable())
102 if (
TTI &&
TTI->enableScalableVectorization())
112 if (IsVectorized.Value != 1)
119 <<
"LV: Interleaving disabled by the pass manager\n");
123 TheLoop->addIntLoopAttribute(
"llvm.loop.isvectorized", 1,
124 {
Twine(Prefix(),
"vectorize.").
str(),
125 Twine(Prefix(),
"interleave.").
str()});
128 IsVectorized.Value = 1;
131void LoopVectorizeHints::reportDisallowedVectorization(
134 LLVM_DEBUG(
dbgs() <<
"LV: Not vectorizing: " << DebugMsg <<
".\n");
137 <<
"loop not vectorized: " << RemarkMsg);
141 Loop *L,
bool VectorizeOnlyWhenForced)
const {
144 reportDisallowedVectorization(
"#pragma vectorize disable",
145 "MissedExplicitlyDisabled",
146 "vectorization is explicitly disabled", L);
148 reportDisallowedVectorization(
"loop hasDisableAllTransformsHint",
149 "MissedTransformsDisabled",
150 "loop transformations are disabled", L);
158 reportDisallowedVectorization(
159 "VectorizeOnlyWhenForced is set, and no #pragma vectorize enable",
160 "MissedForceOnly",
"only vectorizing loops that explicitly request it",
166 LLVM_DEBUG(
dbgs() <<
"LV: Not vectorizing: Disabled/already vectorized.\n");
172 L->getStartLoc(), L->getHeader())
173 <<
"loop not vectorized: vectorization and interleaving are "
174 "explicitly disabled, or the loop has already been "
189 TheLoop->getStartLoc(),
190 TheLoop->getHeader())
191 <<
"loop not vectorized: vectorization is explicitly disabled";
194 TheLoop->getHeader());
195 R <<
"loop not vectorized";
197 R <<
" (Force=" << NV(
"Force",
true);
198 if (Width.Value != 0)
199 R <<
", Vector Width=" << NV(
"VectorWidth",
getWidth());
201 R <<
", Interleave Count=" << NV(
"InterleaveCount",
getInterleave());
217 return Opts.hints_allow_reordering &&
219 EC.getKnownMinValue() > 1);
222void LoopVectorizeHints::getHintsFromMetadata() {
238 if (!MD || MD->getNumOperands() == 0)
241 for (
unsigned Idx = 1; Idx < MD->getNumOperands(); ++Idx)
242 Args.push_back(MD->getOperand(Idx));
245 assert(Args.size() == 0 &&
"too many arguments for MDString");
255 if (Name ==
"llvm.loop.vectorize.enable")
257 else if (Name ==
"llvm.loop.vectorize.disable")
259 else if (Name ==
"llvm.loop.vectorize.fp_unsafe.enable")
261 else if (Name ==
"llvm.loop.vectorize.fp_unsafe.disable")
263 else if (Name ==
"llvm.loop.vectorize.predicate.enable")
265 else if (Name ==
"llvm.loop.vectorize.predicate.disable")
267 else if (Name ==
"llvm.loop.vectorize.scalable.enable")
269 else if (Name ==
"llvm.loop.vectorize.scalable.disable")
273 if (
Args.size() == 1)
274 setHint(Name, Args[0]);
279 if (!
Name.consume_front(Prefix()))
285 unsigned Val =
C->getZExtValue();
290 Hint *Hints[] = {&Width, &Interleave, &IsVectorized};
291 for (
auto *
H : Hints) {
292 if (Name ==
H->Name) {
293 if (
H->validate(Val))
296 LLVM_DEBUG(
dbgs() <<
"LV: ignoring invalid hint '" << Name <<
"'\n");
303 assert(Ty->isIntOrPtrTy() &&
"Expected integer or pointer type");
305 if (Ty->isPointerTy())
306 return DL.getIntPtrType(Ty->getContext(), Ty->getPointerAddressSpace());
310 if (Ty->getScalarSizeInBits() < 32)
331 Value *APtr =
A->getPointerOperand();
332 Value *BPtr =
B->getPointerOperand();
341 if (!AllowRuntimeSCEVChecks || !TheLoop->isInnermost())
358 const auto &Strides = LAI && AllowRuntimeSCEVChecks
359 ? LAI->getSymbolicStrides()
362 int Stride =
getPtrStride(PSE, AccessTy, Ptr, TheLoop, *DT, Strides,
false,
363 AllowRuntimeSCEVChecks ? &Predicates :
nullptr)
365 if (Stride != 1 && Stride != -1)
367 PSE.addPredicates(Predicates);
372 return LAI->isInvariant(V);
382class SCEVAddRecForUniformityRewriter
385 unsigned StepMultiplier;
394 bool CannotAnalyze =
false;
396 bool canAnalyze()
const {
return !CannotAnalyze; }
399 SCEVAddRecForUniformityRewriter(
ScalarEvolution &SE,
unsigned StepMultiplier,
404 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
406 "addrec outside of TheLoop must be invariant and should have been "
412 if (!SE.isLoopInvariant(Step, TheLoop)) {
413 CannotAnalyze =
true;
416 const SCEV *NewStep =
417 SE.getMulExpr(Step, SE.getConstant(Ty, StepMultiplier));
418 const SCEV *ScaledOffset = SE.getMulExpr(Step, SE.getConstant(Ty, Offset));
419 const SCEV *NewStart =
421 return SE.getAddRecExpr(NewStart, NewStep, TheLoop,
SCEV::FlagNone);
424 const SCEV *
visit(
const SCEV *S) {
425 if (CannotAnalyze || SE.isLoopInvariant(S, TheLoop))
430 const SCEV *visitUnknown(
const SCEVUnknown *S) {
431 if (SE.isLoopInvariant(S, TheLoop))
434 CannotAnalyze =
true;
438 const SCEV *visitCouldNotCompute(
const SCEVCouldNotCompute *S) {
440 CannotAnalyze =
true;
444 static const SCEV *rewrite(
const SCEV *S, ScalarEvolution &SE,
445 unsigned StepMultiplier,
unsigned Offset,
455 SCEVAddRecForUniformityRewriter
Rewriter(SE, StepMultiplier, Offset,
468 Value *V, std::optional<ElementCount> VF)
const {
471 if (!VF || VF->isScalable())
478 auto *SE = PSE.getSE();
485 unsigned FixedVF = VF->getKnownMinValue();
486 const SCEV *FirstLaneExpr =
487 SCEVAddRecForUniformityRewriter::rewrite(S, *SE, FixedVF, 0, TheLoop);
495 const SCEV *IthLaneExpr =
496 SCEVAddRecForUniformityRewriter::rewrite(S, *SE, FixedVF,
I, TheLoop);
497 return FirstLaneExpr == IthLaneExpr;
522 Type *Ty =
I.getType();
535 "instruction return type cannot be vectorized",
536 "CantVectorizeInstructionReturnType", ORE,
543 "CantVectorizeStore", ORE, TheLoop,
SI);
556 if (
none_of(
I.operands(), [](
Value *
Op) { return Op->isSwiftError(); }))
559 "swifterror value cannot be vectorized",
560 "CantVectorizeSwiftError", ORE, TheLoop, &
I);
572 "call with operand bundles cannot be vectorized",
573 "CantVectorizeOperandBundles", ORE, TheLoop, &
I);
577bool LoopVectorizationLegality::canVectorizeOuterLoop() {
594 if (!DoExtraAnalysis)
600 for (Instruction &
I : *BB) {
601 if (!
I.isAtomic() && !
I.isVolatile())
604 "Unsupported volatile or atomic memory operation",
605 "instruction cannot be vectorized",
"CantVectorizeInstruction", ORE,
618 "Unsupported basic block terminator",
619 "loop control flow is not understood by vectorizer",
620 "CFGNotUnderstood", ORE, TheLoop);
634 if (Br && !TheLoop->isLoopLatch(BB)) {
635 bool IsUniformCondBr = TheLoop->isLoopInvariant(Br->getCondition());
637 Value *Lhs =
nullptr;
638 Value *Rhs =
nullptr;
639 auto *SE = PSE.getSE();
642 const SCEV *LhsExpr = PSE.getSCEV(Lhs);
643 const SCEV *RhsExpr = PSE.getSCEV(Rhs);
651 if (!IsUniformCondBr) {
653 "Outer loop contains divergent conditional branch",
654 "loop control flow is not understood by vectorizer",
655 "CFGNotUnderstood", ORE, TheLoop);
668 SmallVector<Loop *, 4> LoopNest = TheLoop->getLoopsInPreorder();
670 if (Lp->getExitingBlock() != Lp->getLoopLatch()) {
672 "Nested loop does not exit via its latch",
673 "loop control flow is not understood by vectorizer",
674 "CFGNotUnderstood", ORE, TheLoop);
683 if (!setupOuterLoopInductions()) {
685 "UnsupportedPhi", ORE, TheLoop);
694 if (!canDetermineWidestInductionType())
700bool LoopVectorizationLegality::canDetermineWidestInductionType() {
701 if (Inductions.empty()) {
703 "Did not find one integer induction var",
704 "loop induction variable could not be identified",
705 "NoInductionVariable", ORE, TheLoop);
710 "Did not find one integer induction var",
711 "integer loop induction variable could not be identified",
712 "NoIntegerInductionVariable", ORE, TheLoop);
718void LoopVectorizationLegality::addInductionPhi(
PHINode *Phi,
720 Inductions[
Phi] =
ID;
723 const DataLayout &
DL =
Phi->getDataLayout();
726 "Expected int, ptr, or FP induction phi type");
738 ID.getConstStepValue() &&
ID.getConstStepValue()->isOne() &&
746 if (!PrimaryInduction || PhiTy == WidestIndTy)
747 PrimaryInduction =
Phi;
753bool LoopVectorizationLegality::addConditionalInduction(
755 DenseMap<Value *, const SCEVAddRecExpr *> CompressedPtrsForCondID;
759 "Unsupported user of conditional induction found",
760 "UnsupportedConditionalInductionUse", ORE, TheLoop);
764 ConditionalInductions[
Phi] = CondID;
766 for (
auto [Ptr, PtrAddRec] : CompressedPtrsForCondID) {
767 LLVM_DEBUG(
dbgs() <<
"LV: Found compressed pointer: " << *Ptr <<
'\n');
768 assert(PtrAddRec->isAffine() &&
"Expected affine SCEVAddRecExpr");
769 CompressedPtrs[Ptr] = CompressedPtrInfo{
Phi, PtrAddRec};
781 const VectorizeOptions &Opts) {
782 if (Opts.lv_strided_pointer_ivs)
785 !ID.getConstStepValue();
788bool LoopVectorizationLegality::setupOuterLoopInductions() {
792 auto IsSupportedPhi = [&](
PHINode &Phi) ->
bool {
798 addInductionPhi(&Phi, ID);
804 dbgs() <<
"LV: Found unsupported PHI for outer loop vectorization.\n");
822 bool Scalarize =
TLI.isFunctionVectorizable(ScalarName);
827 TLI.getWidestVF(ScalarName, WidestFixedVF, WidestScalableVF);
830 Scalarize &= !
TLI.isFunctionVectorizable(ScalarName, VF);
833 Scalarize &= !
TLI.isFunctionVectorizable(ScalarName, VF);
835 "Caller may decide to scalarize a variant using a scalable VF");
840bool LoopVectorizationLegality::canVectorizeInstrs() {
848 Result &= canVectorizeInstr(
I);
849 if (!DoExtraAnalysis && !Result)
854 if (!PrimaryInduction) {
855 if (!canDetermineWidestInductionType())
857 LLVM_DEBUG(
dbgs() <<
"LV: Did not find one integer induction var.\n");
862 if (PrimaryInduction && WidestIndTy != PrimaryInduction->getType())
863 PrimaryInduction =
nullptr;
868bool LoopVectorizationLegality::canVectorizeInstr(
Instruction &
I) {
878 "Found a non-int non-pointer PHI",
879 "loop control flow is not understood by vectorizer",
880 "CFGNotUnderstood", ORE, TheLoop);
895 if (
Phi->getNumIncomingValues() != 2) {
897 "Found an invalid PHI",
898 "loop control flow is not understood by vectorizer",
899 "CFGNotUnderstood", ORE, TheLoop, Phi);
903 RecurrenceDescriptor RedDes;
907 Reductions[
Phi] = std::move(RedDes);
911 "Only min/max recurrences are allowed to have multiple uses "
916 InductionDescriptor
ID;
919 addInductionPhi(Phi, ID);
920 Requirements->addExactFPMathInst(
ID.getExactFPMathInst());
924 ConditionalInductionDescriptor CondID;
925 if (Opts.lv_compressing_patterns &&
927 Phi, TheLoop, CondID, *PSE.getSE())) {
928 return addConditionalInduction(Phi, CondID);
932 FixedOrderRecurrences.insert(Phi);
940 addInductionPhi(Phi, ID);
946 "pointer induction with a non-constant step "
947 "could not be vectorized",
948 "StridedPointerInduction", ORE, TheLoop, Phi);
953 "value that could not be identified as "
954 "reduction is used outside the loop",
955 "NonReductionValueUsedOutsideLoop", ORE, TheLoop,
970 !(CI->getCalledFunction() && TLI &&
975 TLI && CI->getCalledFunction() && CI->getType()->isFloatingPointTy() &&
976 TLI->hasOptimizedCodeGen(
977 TLI->getLibFunc(CI->getCalledFunction()->getName()));
985 "Found a non-intrinsic callsite",
986 "library call cannot be vectorized. "
987 "Try compiling with -fno-math-errno, -ffast-math, "
989 "CantVectorizeLibcall", ORE, TheLoop, CI);
992 "call instruction cannot be vectorized",
993 "CantVectorizeLibcall", ORE, TheLoop, CI);
1001 auto *SE = PSE.getSE();
1003 for (
unsigned Idx = 0;
Idx < CI->arg_size(); ++
Idx)
1005 if (!SE->
isLoopInvariant(PSE.getSCEV(CI->getOperand(Idx)), TheLoop)) {
1007 "Found unvectorizable intrinsic",
1008 "intrinsic instruction cannot be vectorized",
1009 "CantVectorizeIntrinsic", ORE, TheLoop, CI);
1018 VecCallVariantsFound =
true;
1027 if (
ST->getMetadata(LLVMContext::MD_nontemporal)) {
1031 assert(VecTy &&
"did not find vectorized version of stored type");
1032 if (!TTI->isLegalNTStore(VecTy,
ST->getAlign())) {
1034 "nontemporal store instruction cannot be vectorized",
1035 "CantVectorizeNontemporalStore", ORE, TheLoop, ST);
1041 if (
LD->getMetadata(LLVMContext::MD_nontemporal)) {
1045 assert(VecTy &&
"did not find vectorized version of load type");
1046 if (!TTI->isLegalNTLoad(VecTy,
LD->getAlign())) {
1048 "nontemporal load instruction cannot be vectorized",
1049 "CantVectorizeNontemporalLoad", ORE, TheLoop, LD);
1059 }
else if (((
I.getType()->isFloatingPointTy() && (CI ||
I.isBinaryOp())) ||
1065 Hints->setPotentiallyUnsafe();
1100 Value *HIncVal =
nullptr;
1107 else if (
match(HUpdateOp,
1127 Value *HIdx =
nullptr;
1128 for (
Value *Index :
GEP->indices()) {
1151 if (!AR || AR->getLoop() != TheLoop)
1165 LLVM_DEBUG(
dbgs() <<
"LV: Found histogram for: " << *HSt <<
"\n");
1168 Histograms.
emplace_back(IndexedLoad, HUpdateOp, HSt, UpdateKind);
1172bool LoopVectorizationLegality::canVectorizeIndirectUnsafeDependences() {
1175 if (!Opts.enable_histogram_loop_vectorization)
1212 LLVM_DEBUG(
dbgs() <<
"LV: Checking for a histogram on: " << *SI <<
"\n");
1213 return findHistogram(LI, SI, TheLoop, LAI->getPSE(), Histograms);
1216bool LoopVectorizationLegality::canVectorizeMemory() {
1217 LAI = &LAIs.getInfo(*TheLoop);
1218 const OptimizationRemarkAnalysis *LAR = LAI->getReport();
1221 return OptimizationRemarkAnalysis(
LV_NAME,
"loop not vectorized: ", *LAR);
1229 if (!LAI->getStoresToInvariantAddresses().empty()) {
1232 for (StoreInst *SI : LAI->getStoresToInvariantAddresses()) {
1238 "We don't allow storing to uniform addresses",
1239 "write of conditional recurring variant value to a loop "
1240 "invariant address could not be vectorized",
1241 "CantVectorizeStoreToLoopInvariantAddress", ORE, TheLoop);
1249 if (TheLoop->contains(Ptr)) {
1251 "Invariant address is calculated inside the loop",
1252 "write to a loop invariant address could not "
1254 "CantVectorizeStoreToLoopInvariantAddress", ORE, TheLoop);
1260 if (LAI->hasStoreStoreDependenceInvolvingLoopInvariantAddress()) {
1266 ScalarEvolution *SE = PSE.getSE();
1268 for (StoreInst *SI : LAI->getStoresToInvariantAddresses()) {
1280 erase_if(UnhandledStores, [SE, SI](StoreInst *
I) {
1282 I->getValueOperand()->getType() ==
1283 SI->getValueOperand()->getType();
1290 bool IsOK = UnhandledStores.
empty();
1294 "We don't allow storing to uniform addresses",
1295 "write to a loop invariant address could not "
1297 "CantVectorizeStoreToLoopInvariantAddress", ORE, TheLoop);
1303 if (!LAI->canVectorizeMemory()) {
1306 "Cannot vectorize unsafe dependencies in uncountable exit loop with "
1308 "CantVectorizeUnsafeDependencyForEELoopWithSideEffects", ORE,
1313 return canVectorizeIndirectUnsafeDependences();
1316 if (LAI->hasLoadStoreDependenceInvolvingLoopInvariantAddress()) {
1318 "write to a loop invariant address could not "
1320 "CantVectorizeStoreToLoopInvariantAddress", ORE,
1325 PSE.addPredicate(LAI->getPSE().getPredicate());
1330 bool EnableStrictReductions) {
1333 if (!Requirements->getExactFPInst() || Hints->allowReordering())
1339 if (!EnableStrictReductions ||
1369 Value *InvariantAddress =
1371 return V == InvariantAddress ||
1382 return Inductions.count(PN);
1387 return FixedOrderRecurrences.count(Phi);
1398 !canVectorizeLoopCFG(TheLoop,
false) &&
1399 "Loop shape should have been rejected by earlier checks");
1412bool LoopVectorizationLegality::blockCanBePredicated(
1413 BasicBlock *BB, SafeAccessesTy &SafeAccesses,
1441 auto It = SafeAccesses.find(LI->getPointerOperand());
1442 TypeSize
Size = LI->getDataLayout().getTypeStoreSize(LI->getType());
1443 if (
Size.isScalable() || It == SafeAccesses.end() ||
1444 It->second.MaxAlign < LI->getAlign() ||
1445 It->second.MaxSizeInBytes <
Size.getFixedValue())
1460 if (
I.mayReadFromMemory() ||
I.mayWriteToMemory() ||
I.mayThrow())
1467bool LoopVectorizationLegality::canVectorizeWithIfConvert() {
1468 if (!Opts.enable_if_conversion) {
1470 "IfConversionDisabled", ORE, TheLoop);
1474 assert(TheLoop->getNumBlocks() > 1 &&
"Single block loops are vectorizable");
1480 SafeAccessesTy SafeAccesses;
1481 auto RecordSafeAccess = [&SafeAccesses](
Instruction &
I) {
1486 if (
Size.isScalable())
1489 auto &
Info = SafeAccesses[Ptr];
1490 Info.MaxAlign = std::max(
Info.MaxAlign, Alignment);
1491 Info.MaxSizeInBytes = std::max(
Info.MaxSizeInBytes,
Size.getFixedValue());
1495 for (BasicBlock *BB : TheLoop->blocks()) {
1497 for (Instruction &
I : *BB)
1498 RecordSafeAccess(
I);
1507 ScalarEvolution &SE = *PSE.getSE();
1509 for (Instruction &
I : *BB) {
1519 auto CanSpeculatePointerOp = [
this](
Value *Ptr) {
1521 SmallPtrSet<Value *, 4> Visited;
1522 while (!Worklist.
empty()) {
1524 if (!Visited.
insert(CurrV).second)
1528 if (!CurrI || !TheLoop->contains(CurrI)) {
1529 BasicBlock *LoopPred = TheLoop->getLoopPredecessor();
1532 "Loop with multiple predecessors should have been rejected "
1557 CanSpeculatePointerOp(LI->getPointerOperand()) &&
1560 RecordSafeAccess(*LI);
1566 for (BasicBlock *BB : TheLoop->blocks()) {
1570 if (TheLoop->isLoopExiting(BB)) {
1572 "LoopContainsUnsupportedSwitch", ORE,
1573 TheLoop, BB->getTerminator());
1578 "LoopContainsUnsupportedTerminator", ORE,
1579 TheLoop, BB->getTerminator());
1585 !blockCanBePredicated(BB, SafeAccesses, ConditionallyExecutedOps)) {
1587 "Control flow cannot be substituted for a select",
"NoCFGForSelect",
1588 ORE, TheLoop, BB->getTerminator());
1598bool LoopVectorizationLegality::canVectorizeLoopCFG(
1599 Loop *Lp,
bool UseVPlanNativePath)
const {
1601 "VPlan-native path is not enabled.");
1611 bool DoExtraAnalysis = ORE->allowExtraAnalysis(
DEBUG_TYPE);
1619 "Loop doesn't have a legal pre-header",
1620 "loop control flow is not understood by vectorizer",
"CFGNotUnderstood",
1622 if (DoExtraAnalysis)
1631 "The loop must have a single backedge",
1632 "loop control flow is not understood by vectorizer",
"CFGNotUnderstood",
1634 if (DoExtraAnalysis)
1644 "The loop latch terminator is not a UncondBrInst/CondBrInst",
1645 "loop control flow is not understood by vectorizer",
"CFGNotUnderstood",
1647 if (DoExtraAnalysis)
1656bool LoopVectorizationLegality::canVectorizeLoopNestCFG(
1657 Loop *Lp,
bool UseVPlanNativePath) {
1661 bool DoExtraAnalysis = ORE->allowExtraAnalysis(
DEBUG_TYPE);
1662 if (!canVectorizeLoopCFG(Lp, UseVPlanNativePath)) {
1663 if (DoExtraAnalysis)
1671 for (
Loop *SubLp : *Lp)
1672 if (!canVectorizeLoopNestCFG(SubLp, UseVPlanNativePath)) {
1673 if (DoExtraAnalysis)
1696 Value *IVUpdate, *Limit;
1738 *PSE.getSE(), TheLoop))
1739 return CountableCmp;
1744bool LoopVectorizationLegality::isVectorizableEarlyExitLoop() {
1748 "Cannot vectorize early exit loop",
1749 "NoLatchEarlyExit", ORE, TheLoop);
1753 if (!FixedOrderRecurrences.
empty()) {
1755 "Found fixed-order recurrences in early-exit loop",
1756 "Cannot vectorize early exit loop with fixed-order recurrences",
1757 "RecurrencesInEarlyExitLoop", ORE, TheLoop);
1761 SmallVector<BasicBlock *, 8> ExitingBlocks;
1762 TheLoop->getExitingBlocks(ExitingBlocks);
1767 for (BasicBlock *BB : ExitingBlocks) {
1769 PSE.getSE()->getPredicatedExitCount(TheLoop, BB, &Predicates);
1773 "Early exiting block does not have exactly two successors",
1774 "Incorrect number of successors from early exiting block",
1775 "EarlyExitTooManySuccessors", ORE, TheLoop);
1781 CountableExitingBlocks.push_back(BB);
1789 if (UncountableExitingBlocks.
empty()) {
1790 LLVM_DEBUG(
dbgs() <<
"LV: Could not find any uncountable exits\n");
1798 "Cannot determine symbolic max exit count for latch block",
1799 "Cannot vectorize early exit loop",
1800 "UnknownLatchExitCountEarlyExitLoop", ORE, TheLoop);
1811 "Latch block does not have a countable exit condition",
1812 "NoCountableConditionInLatchBlock", ORE, TheLoop);
1820 switch (
I->getOpcode()) {
1821 case Instruction::Load:
1822 case Instruction::Store:
1823 case Instruction::PHI:
1824 case Instruction::UncondBr:
1825 case Instruction::CondBr:
1833 bool HasSideEffects =
false;
1834 for (
auto *BB : TheLoop->blocks())
1835 for (
auto &
I : *BB) {
1838 if (
I.mayWriteToMemory()) {
1840 HasSideEffects =
true;
1846 "Complex writes to memory unsupported in early exit loops",
1847 "Cannot vectorize early exit loop with complex writes to memory",
1848 "WritesInEarlyExitLoop", ORE, TheLoop);
1852 if (!IsSafeOperation(&
I)) {
1854 "cannot be speculatively executed",
1855 "UnsafeOperationsEarlyExitLoop", ORE,
1863 if (!HasSideEffects) {
1869 "Loop may fault",
"Cannot vectorize non-read-only early exit loop",
1870 "NonReadOnlyEarlyExitLoop", ORE, TheLoop);
1875 for (BasicBlock *ExitingBB : UncountableExitingBlocks) {
1876 if (!canUncountableExitConditionLoadBeMoved(ExitingBB))
1882 for (LoadInst *LI : NonDerefLoads) {
1887 "Loop contains potentially faulting strided load",
1888 "Cannot vectorize early exit loop with "
1889 "strided fault-only-first load",
1890 "EarlyExitLoopWithStridedFaultOnlyFirstLoad", ORE, TheLoop);
1902 [[maybe_unused]]
const SCEV *SymbolicMaxBTC =
1903 PSE.getSymbolicMaxBackedgeTakenCount();
1907 "Failed to get symbolic expression for backedge taken count");
1908 LLVM_DEBUG(
dbgs() <<
"LV: Found an early exit loop with symbolic max "
1909 "backedge taken count: "
1910 << *SymbolicMaxBTC <<
'\n');
1916bool LoopVectorizationLegality::canUncountableExitConditionLoadBeMoved(
1924 using namespace llvm::PatternMatch;
1934 Other, *PSE.getSE(), TheLoop)) {
1936 "Early exit loop with store but no supported condition load",
1937 "NoConditionLoadForEarlyExitLoop", ORE, TheLoop);
1944 if (!TheLoop->isLoopInvariant(
Other)) {
1946 "Early exit loop with store but no supported condition load",
1947 "NoConditionLoadForEarlyExitLoop", ORE, TheLoop);
1954 if (!AR || AR->getLoop() != TheLoop || !AR->isAffine()) {
1956 "Uncountable exit condition depends on load with an address that is "
1957 "not an add recurrence in the loop",
1958 "EarlyExitLoadInvariantAddress", ORE, TheLoop);
1962 ICFLoopSafetyInfo SafetyInfo(TheLoop);
1966 if (!SafetyInfo.isGuaranteedToExecute(*
Load, DT)) {
1968 "Load for uncountable exit not guaranteed to execute",
1969 "ConditionalUncountableExitLoad", ORE, TheLoop);
1976 for (
auto *BB : TheLoop->blocks()) {
1977 for (
auto &
I : *BB) {
1987 if (
I.mayReadOrWriteMemory()) {
1989 ConditionallyExecutedOps.insert(&
I);
1993 AliasResult AR = AA->alias(Ptr,
SI->getPointerOperand());
1999 "Cannot determine whether critical uncountable exit load address "
2000 "does not alias with a memory write",
2001 "CantVectorizeAliasWithCriticalUncountableExitLoad", ORE, TheLoop);
2015 bool DoExtraAnalysis = ORE->allowExtraAnalysis(
DEBUG_TYPE);
2018 if (!canVectorizeLoopNestCFG(TheLoop, UseVPlanNativePath)) {
2019 if (DoExtraAnalysis) {
2028 LLVM_DEBUG(
dbgs() <<
"LV: Found a loop: " << TheLoop->getHeader()->getName()
2033 if (!TheLoop->isInnermost()) {
2034 assert(UseVPlanNativePath &&
"VPlan-native path is not enabled.");
2036 if (!canVectorizeOuterLoop()) {
2038 "UnsupportedOuterLoop", ORE, TheLoop);
2048 assert(TheLoop->isInnermost() &&
"Inner loop expected.");
2050 unsigned NumBlocks = TheLoop->getNumBlocks();
2051 if (NumBlocks != 1 && !canVectorizeWithIfConvert()) {
2053 if (DoExtraAnalysis)
2060 if (!canVectorizeInstrs()) {
2061 LLVM_DEBUG(
dbgs() <<
"LV: Can't vectorize the instructions or CFG\n");
2062 if (DoExtraAnalysis)
2069 !isVectorizableEarlyExitLoop()) {
2071 "Must be false without vectorizable early-exit loop");
2072 if (TheLoop->getExitingBlock())
2074 "UnsupportedUncountableLoop", ORE, TheLoop);
2075 if (DoExtraAnalysis)
2082 if (!canVectorizeMemory()) {
2083 LLVM_DEBUG(
dbgs() <<
"LV: Can't vectorize due to memory conflicts\n");
2084 if (DoExtraAnalysis)
2092 !LAI->getStoresToInvariantAddresses().empty()) {
2093 LLVM_DEBUG(
dbgs() <<
"LV: Cannot vectorize early exit loops with stores to "
2094 "loop-invariant addresses\n");
2096 "to loop-invariant addresses",
2097 "LoopInvariantStoresInEELoop", ORE, TheLoop);
2102 LLVM_DEBUG(
dbgs() <<
"LV: Loop passed LoopVectorizationLegality checks"
2103 << (LAI->getRuntimePointerChecking()->Need
2104 ?
" (with a runtime bound check)"
2121 if (TheLoop->getExitingBlock() != TheLoop->getLoopLatch()) {
2124 <<
"LV: Cannot fold tail by masking. Requires a singe latch exit\n");
2130 LLVM_DEBUG(
dbgs() <<
"LV: Cannot tail fold by masking. Loop contains an "
2131 "uncountable early exit.\n");
2135 LLVM_DEBUG(
dbgs() <<
"LV: checking if tail can be folded by masking.\n");
2138 SafeAccessesTy SafeAccesses;
2144 if (!blockCanBePredicated(BB, SafeAccesses, TmpMaskedOp)) {
2157 SafeAccessesTy SafeAccesses;
2163 [[maybe_unused]]
bool R =
2164 blockCanBePredicated(BB, SafeAccesses, TailFoldedMaskedOp);
2165 assert(R &&
"Must be able to predicate block when tail-folding.");
const TargetLowering & TLI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static const unsigned MaxInterleaveFactor
Maximum vectorization interleave count.
This file defines the LoopVectorizationLegality class.
This file provides a LoopVectorizationPlanner class.
Contains a collection of routines for determining if a given instruction is guaranteed to execute if ...
SmallVector< MachineOperand, 4 > Cond
static void visit(BasicBlock &Start, std::function< bool(BasicBlock *)> op)
virt reg Virtual Register Rewriter
@ NoAlias
The two locations do not alias at all.
LLVM Basic Block Representation.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
This class represents a function call, abstracting a target machine's calling convention.
@ FCMP_ORD
0 1 1 1 True if ordered (no nans)
@ FCMP_UNO
1 0 0 0 True if unordered: isnan(X) | isnan(Y)
Describes a conditional induction variable: an induction variable that is updated only on loop iterat...
static LLVM_ABI bool isConditionalInductionPHI(PHINode *PN, const Loop *L, ConditionalInductionDescriptor &Desc, ScalarEvolution &SE)
Returns true if PN is a conditional induction variable in the loop L.
A parsed version of the target data layout string in and methods for querying it.
static constexpr ElementCount getScalable(ScalarTy MinVal)
static constexpr ElementCount getFixed(ScalarTy MinVal)
static LLVM_ABI FixedVectorType * get(Type *ElementType, unsigned NumElts)
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
A struct for saving information about induction variables.
Instruction * getExactFPMathInst() const
Returns floating-point induction operator that does not allow reassociation (transforming the inducti...
static LLVM_ABI bool isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE, InductionDescriptor &D, ArrayRef< const SCEVPredicate * > NoWrapPreds={}, const SCEV *Expr=nullptr, SmallVectorImpl< Instruction * > *CastsToIgnore=nullptr)
Returns true if Phi is an induction in the loop L.
@ IK_PtrInduction
Pointer induction var. Step = C.
@ IK_IntInduction
Integer induction variable. Step = C.
Class to represent integer types.
An instruction for reading from memory.
const MemoryDepChecker & getDepChecker() const
the Memory Dependence Checker which can determine the loop-independent and loop-carried dependences b...
static LLVM_ABI bool blockNeedsPredication(const BasicBlock *BB, const Loop *TheLoop, const DominatorTree *DT)
Return true if the block BB needs to be predicated in order for the loop to be vectorized.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
bool isInnermost() const
Return true if the loop does not contain any (natural) loops.
unsigned getNumBackEdges() const
Calculate the number of back edges to the loop header.
BlockT * getHeader() const
iterator_range< block_iterator > blocks() const
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
LLVM_ABI bool isInvariantStoreOfReduction(StoreInst *SI)
Returns True if given store is a final invariant store of one of the reductions found in the loop.
LLVM_ABI void collectUnitStridePredicates() const
Add unit stride predicates for memory accesses to PSE, if runtime checks are allowed and an inner loo...
LLVM_ABI bool isInvariantAddressOfReduction(Value *V)
Returns True if given address is invariant and is used to store recurrent expression.
LLVM_ABI bool canVectorize(bool UseVPlanNativePath)
Returns true if it is legal to vectorize this loop.
LLVM_ABI bool blockNeedsPredication(const BasicBlock *BB) const
Return true if the block BB needs to be predicated in order for the loop to be vectorized.
LLVM_ABI int isConsecutivePtr(Type *AccessTy, Value *Ptr) const
Check if this pointer is consecutive when vectorizing.
bool hasUncountableExitWithSideEffects() const
Returns true if this is an early exit loop with state-changing or potentially-faulting operations and...
LLVM_ABI bool canVectorizeFPMath(bool EnableStrictReductions)
Returns true if it is legal to vectorize the FP math operations in this loop.
LLVM_ABI bool isFixedOrderRecurrence(const PHINode *Phi) const
Returns True if Phi is a fixed-order recurrence in this loop.
LLVM_ABI bool isInductionPhi(const Value *V) const
Returns True if V is a Phi node of an induction variable in this loop.
LLVM_ABI Instruction * findCountableComparisonInCombinedCondition(Value *Cond) const
If Cond is a combined exit condition featuring uncountable and countable comparisons,...
const InductionList & getInductionVars() const
Returns the induction variables found in the loop.
LLVM_ABI bool isInvariant(Value *V) const
Returns true if V is invariant across all loop iterations according to SCEV.
const ReductionList & getReductionVars() const
Returns the reduction variables found in the loop.
LLVM_ABI bool canFoldTailByMasking() const
Return true if we can vectorize this loop while folding its tail by masking.
LLVM_ABI void prepareToFoldTailByMasking()
Mark all respective loads/stores for masking.
bool hasUncountableEarlyExit() const
Returns true if the loop has uncountable early exits, i.e.
LLVM_ABI bool isUniformMemOp(Instruction &I, std::optional< ElementCount > VF) const
A uniform memory op is a load or store which accesses the same memory location on all VF lanes,...
LLVM_ABI bool isUniform(Value *V, std::optional< ElementCount > VF) const
Returns true if value V is uniform across VF lanes, when VF is provided, and otherwise if V is invari...
@ SK_PreferScalable
Vectorize loops using scalable vectors or fixed-width vectors, but favor scalable vectors when the co...
@ SK_AlwaysScalable
Always vectorize loops using scalable vectors if feasible (i.e.
@ SK_Unspecified
Not selected.
@ SK_FixedWidthOnly
Disables vectorization with scalable vectors.
enum ForceKind getForce() const
LLVM_ABI bool allowReordering() const
When enabling loop hints are provided we allow the vectorizer to change the order of operations that ...
LLVM_ABI LoopVectorizeHints(const VectorizeOptions &Opts, const Loop *L, bool InterleaveOnlyWhenForced, OptimizationRemarkEmitter &ORE, const TargetTransformInfo *TTI=nullptr)
LLVM_ABI void emitRemarkWithHints() const
Dumps all the hint information.
LLVM_ABI bool allowVectorization(Loop *L, bool VectorizeOnlyWhenForced) const
ElementCount getWidth() const
@ FK_Enabled
Forcing enabled.
@ FK_Undefined
Not selected.
@ FK_Disabled
Forcing disabled.
LLVM_ABI void setAlreadyVectorized()
Mark the loop L as already vectorized by setting the width to 1.
unsigned getInterleave() const
unsigned getIsVectorized() const
Represents a single loop in the control flow graph.
LLVM_ABI bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
LLVM_ABI MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
const MDOperand & getOperand(unsigned I) const
ArrayRef< MDOperand > operands() const
unsigned getNumOperands() const
Return number of MDNode operands.
Tracking metadata reference owned by Metadata.
LLVM_ABI StringRef getString() const
Checks memory dependences among accesses to the same underlying object to determine whether there vec...
const SmallVectorImpl< Dependence > * getDependences() const
Returns the memory dependences.
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
ScalarEvolution * getSE() const
Returns the ScalarEvolution analysis used.
The RecurrenceDescriptor is used to identify recurrences variables in a loop.
Instruction * getExactFPMathInst() const
Returns 1st non-reassociative FP instruction in the PHI node's use-chain.
static LLVM_ABI bool isFixedOrderRecurrence(PHINode *Phi, Loop *TheLoop, DominatorTree *DT)
Returns true if Phi is a fixed-order recurrence.
bool hasExactFPMath() const
Returns true if the recurrence has floating-point math that requires precise (ordered) operations.
static LLVM_ABI bool isReductionPHI(PHINode *Phi, Loop *TheLoop, RecurrenceDescriptor &RedDes, DemandedBits *DB=nullptr, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr, ScalarEvolution *SE=nullptr)
Returns true if Phi is a reduction in TheLoop.
bool hasUsesOutsideReductionChain() const
Returns true if the reduction PHI has any uses outside the reduction chain.
RecurKind getRecurrenceKind() const
bool isOrdered() const
Expose an ordered FP reduction to the instance users.
StoreInst * IntermediateStore
Reductions may store temporary or final result to an invariant address.
static bool isMinMaxRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is any min/max kind.
const Loop * getLoop() const
SCEVUse getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
This visitor recursively visits a SCEV expression and re-writes it.
const SCEV * visit(const SCEV *S)
This class represents an analyzed expression in the program.
Type * getType() const
Return the LLVM type of this SCEV expression.
static constexpr auto FlagNone
The main scalar evolution driver.
LLVM_ABI const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
LLVM_ABI bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
LLVM_ABI bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
LLVM_ABI bool isLoopUniform(const SCEV *S, const Loop *L)
Returns true if the given SCEV is loop-uniform with respect to the specified loop L.
LLVM_ABI const SCEV * getCouldNotCompute()
@ SymbolicMaximum
An expression which provides an upper bound on the exact trip count.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Value * getPointerOperand()
Represent a constant reference to a string, i.e.
Provides information about what library functions are available for the current target.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
LLVM_ABI std::string str() const
Return the twine contents as a std::string.
The instances of the Type class are immutable: once they are created, they are never changed.
static LLVM_ABI IntegerType * getInt32Ty(LLVMContext &C)
bool isPointerTy() const
True if this is an instance of PointerType.
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
bool isFloatingPointTy() const
Return true if this is one of the floating-point types.
bool isIntOrPtrTy() const
Return true if this is an integer type or a pointer type.
bool isIntegerTy() const
True if this is an instance of IntegerType.
Value * getOperand(unsigned i) const
static bool hasMaskedVariant(const CallInst &CI, std::optional< ElementCount > VF=std::nullopt)
static SmallVector< VFInfo, 8 > getMappings(const CallInst &CI)
Retrieve all the VFInfo instances associated to the CallInst CI.
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
static LLVM_ABI bool isValidElementType(Type *ElemTy)
Return true if the specified type is valid as a element type.
static constexpr bool isKnownLE(const FixedOrScalableQuantity &LHS, const FixedOrScalableQuantity &RHS)
constexpr bool isZero() const
const ParentTy * getParent() const
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
@ BasicBlock
Various leaf nodes.
void reportVectorizationFailure(const StringRef DebugMsg, const StringRef OREMsg, const StringRef ORETag, OptimizationRemarkEmitter *ORE, const Loop *TheLoop, Instruction *I=nullptr)
Reports a vectorization failure: print DebugMsg for debugging purposes along with the corresponding o...
TwoOps_match< ValueOpTy, PointerOpTy, Instruction::Store > m_Store(const ValueOpTy &ValueOp, const PointerOpTy &PointerOp)
Matches StoreInst.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
bool match(Val *V, const Pattern &P)
match_bind< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
auto m_UMin(const Opnd0 &Op0, const Opnd1 &Op1)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
CmpClass_match< LHS, RHS, CmpInst, true > m_c_Cmp(const LHS &L, const RHS &R)
CmpClass_match< LHS, RHS, ICmpInst, true > m_c_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
Matches an ICmp with a predicate over LHS and RHS in either order.
auto m_UMax(const Opnd0 &Op0, const Opnd1 &Op1)
auto m_Value()
Match an arbitrary value and ignore it.
match_combine_or< match_combine_or< CastInst_match< OpTy, ZExtInst >, CastInst_match< OpTy, SExtInst > >, OpTy > m_ZExtOrSExtOrSelf(const OpTy &Op)
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
OneOps_match< OpTy, Instruction::Load > m_Load(const OpTy &Op)
Matches LoadInst.
auto m_Intrinsic(const Ts &...Ops)
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
cst_pred_ty< is_one > m_scev_One()
Match an integer 1.
specificloop_ty m_SpecificLoop(const Loop *L)
bool match(const SCEV *S, const Pattern &P)
SCEVAffineAddRec_match< Op0_t, Op1_t, match_isa< const Loop > > m_scev_AffineAddRec(const Op0_t &Op0, const Op1_t &Op1)
std::enable_if_t< detail::IsValidPointer< X, Y >::value, X * > dyn_extract(Y &&MD)
Extract a Value from Metadata, if any.
Add a small namespace to avoid name clashes with the classes used in the streaming interface.
NodeAddr< PhiNode * > Phi
friend class Instruction
Iterator for Instructions in a `BasicBlock.
bool isSimple(Instruction *I)
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
LLVM_ABI bool collectCompressedPtrs(DenseMap< Value *, const SCEVAddRecExpr * > &CompressedPtrs, const Loop &L, const ConditionalInductionDescriptor &CondID, ScalarEvolution &SE)
Collect pointer values used by loads and stores whose addresses are derived from the conditional indu...
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
LLVM_ABI Intrinsic::ID getVectorIntrinsicIDForCall(const CallInst *CI, const TargetLibraryInfo *TLI)
Returns intrinsic ID for call.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
auto successors(const MachineBasicBlock *BB)
const Value * getLoadStorePointerOperand(const Value *V)
A helper function that returns the pointer operand of a load or store instruction.
@ Load
The value being inserted comes from a load (InsertElement only).
static bool canWidenTypes(Instruction &I, bool AllowStructCalls, OptimizationRemarkEmitter *ORE, Loop *TheLoop)
Returns true if the types produced and stored by I can be widened, otherwise reports a vectorization ...
static bool canVectorizeOperandBundles(Instruction &I, OptimizationRemarkEmitter *ORE, Loop *TheLoop)
Calls with operand bundles other than llvm.assume cannot be widened.
static bool matchCombinedExitCondition(Value *Cond, Instruction *&CountableCond, Value *&Ptr, Instruction *&Load, Value *&Other, ScalarEvolution &SE, Loop *TheLoop)
Matches a combined exit condition consisting of an uncountable condition and a countable condition,...
HistogramUpdateKind
The kind of update operation performed on the buckets of a histogram, i.e.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
LLVM_ABI bool mustSuppressSpeculation(const LoadInst &LI)
Return true if speculation of the given load must be suppressed to avoid ordering or interfering with...
Align getLoadStoreAlignment(const Value *I)
A helper function that returns the alignment of load or store instruction.
LLVM_ABI bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true, bool IgnoreUBImplyingAttrs=true)
Return true if the instruction does not have any effects besides calculating the result and does not ...
LLVM_ABI std::optional< int64_t > getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy, Value *Ptr, const Loop *Lp, const DominatorTree &DT, const SymbolicStrideMap &StridesMap=SymbolicStrideMap(), bool ShouldCheckWrap=true, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
If the pointer has a constant stride return it in units of the access type size.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
auto dyn_cast_or_null(const Y &Val)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
auto reverse(ContainerTy &&C)
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
DenseMap< Value *, const SCEVUnknown * > SymbolicStrideMap
Maps a pointer to its symbolic (non-constant) stride.
static IntegerType * getWiderInductionTy(const DataLayout &DL, Type *Ty0, Type *Ty1)
static IntegerType * getInductionIntegerTy(const DataLayout &DL, Type *Ty)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
LLVM_ABI bool hasDisableAllTransformsHint(const Loop *L)
Look for the loop attribute that disables all transformation heuristic.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
static bool storeToSameAddress(ScalarEvolution *SE, StoreInst *A, StoreInst *B)
Returns true if A and B have same pointer operands or same SCEVs addresses.
bool canVectorizeTy(Type *Ty)
Returns true if Ty is a valid vector element type, void, or an unpacked literal struct where all elem...
static bool isDisallowedStridedPointerInduction(const InductionDescriptor &ID, const VectorizeOptions &Opts)
Returns true if ID is a pointer induction with a non-constant step.
LLVM_ABI bool isVectorIntrinsicWithScalarOpAtArg(Intrinsic::ID ID, unsigned ScalarOpdIdx, const TargetTransformInfo *TTI)
Identifies if the vector form of the intrinsic has a scalar operand.
DWARFExpression::Operation Op
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
static bool canVectorizeSwiftErrorUses(Instruction &I, OptimizationRemarkEmitter *ORE, Loop *TheLoop)
Returns true if I does not use a swifterror value, otherwise reports a vectorization failure for TheL...
LLVM_ABI bool isReadOnlyLoop(Loop *L, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, SmallVectorImpl< LoadInst * > &NonDereferenceableAndAlignedLoads, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
Returns true if the loop contains read-only memory accesses and doesn't throw.
constexpr auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Type * getLoadStoreType(const Value *I)
A helper function that returns the type of a load or store instruction.
static bool matchUncountableExitCondition(Value *Cond, Value *&Ptr, Instruction *&Load, Value *&Other)
Matches an exit condition formed by comparing a value loaded from memory with another term.
static bool findHistogram(LoadInst *LI, StoreInst *HSt, Loop *TheLoop, const PredicatedScalarEvolution &PSE, SmallVectorImpl< HistogramInfo > &Histograms)
Find histogram operations that match high-level code in loops:
LLVM_ABI bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Returns true if V cannot be poison, but may be undef.
static bool isTLIScalarize(const TargetLibraryInfo &TLI, const CallInst &CI)
Checks if a function is scalarizable according to the TLI, in the sense that it should be vectorized ...
static bool matchCountableExitCondition(Value *Cond, ScalarEvolution &SE, Loop *TheLoop)
Matches an exit condition formed by comparing the current value of an affine add recurrence in the gi...
LLVM_ABI bool isDereferenceableAndAlignedInLoop(LoadInst *LI, Loop *L, ScalarEvolution &SE, DominatorTree &DT, AssumptionCache *AC=nullptr, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
Return true if we can prove that the given load (which is assumed to be within the specified loop) wo...
static bool canWidenResultType(const Instruction &I, bool AllowStructCalls)
Returns true if the type produced by I can be widened.
constexpr detail::IsaCheckPredicate< Types... > IsaPred
Function object wrapper for the llvm::isa type check.
SCEVUseT< const SCEV * > SCEVUse
bool SCEVExprContains(const SCEV *Root, PredTy Pred)
Return true if any node in Root satisfies the predicate Pred.
Dependece between memory access instructions.
Instruction * getDestination(const MemoryDepChecker &DepChecker) const
Return the destination instruction of the dependence.
Instruction * getSource(const MemoryDepChecker &DepChecker) const
Return the source instruction of the dependence.
static LLVM_ABI VectorizationSafetyStatus isSafeForVectorization(DepType Type)
Dependence types that don't prevent vectorization.
TODO: The following VectorizationFactor was pulled out of LoopVectorizationCostModel class.
Collection of parameters shared beetween the Loop Vectorizer and the Loop Access Analysis.
static LLVM_ABI const unsigned MaxVectorWidth
Maximum SIMD width.
static LLVM_ABI bool isInterleaveForced()
True if force-vector-interleave was specified by the user.
static LLVM_ABI unsigned VectorizationInterleave
Interleave factor as overridden by the user.
static LLVM_ABI ElementCount VectorizationFactor
VF as overridden by the user.