32using namespace PatternMatch;
34#define LV_NAME "loop-vectorize"
35#define DEBUG_TYPE LV_NAME
39 cl::desc(
"Enable if-conversion during vectorization."));
43 cl::desc(
"Enable recognition of non-constant strided "
44 "pointer induction variables."));
49 cl::desc(
"Allow enabling loop hints to reorder "
50 "FP operations during vectorization."));
57 cl::desc(
"The maximum number of SCEV checks allowed."));
61 cl::desc(
"The maximum number of SCEV checks allowed with a "
62 "vectorize(enable) pragma"));
68 cl::desc(
"Control whether the compiler can use scalable vectors to "
72 "Scalable vectorization is disabled."),
75 "Scalable vectorization is available and favored when the "
76 "cost is inconclusive."),
79 "Scalable vectorization is available and favored when the "
80 "cost is inconclusive.")));
87bool LoopVectorizeHints::Hint::validate(
unsigned Val) {
98 return (Val == 0 || Val == 1);
104 bool InterleaveOnlyWhenForced,
108 Interleave(
"interleave.count", InterleaveOnlyWhenForced, HK_INTERLEAVE),
109 Force(
"vectorize.enable", FK_Undefined, HK_FORCE),
110 IsVectorized(
"isvectorized", 0, HK_ISVECTORIZED),
111 Predicate(
"vectorize.predicate.enable", FK_Undefined, HK_PREDICATE),
112 Scalable(
"vectorize.scalable.enable", SK_Unspecified, HK_SCALABLE),
113 TheLoop(L), ORE(ORE) {
115 getHintsFromMetadata();
149 if (IsVectorized.Value != 1)
156 <<
"LV: Interleaving disabled by the pass manager\n");
169 {
Twine(Prefix(),
"vectorize.").
str(),
170 Twine(Prefix(),
"interleave.").
str()},
175 IsVectorized.Value = 1;
181 LLVM_DEBUG(
dbgs() <<
"LV: Not vectorizing: #pragma vectorize disable.\n");
187 LLVM_DEBUG(
dbgs() <<
"LV: Not vectorizing: No #pragma vectorize enable.\n");
193 LLVM_DEBUG(
dbgs() <<
"LV: Not vectorizing: Disabled/already vectorized.\n");
199 "AllDisabled", L->getStartLoc(),
201 <<
"loop not vectorized: vectorization and interleaving are "
202 "explicitly disabled, or the loop has already been "
219 <<
"loop not vectorized: vectorization is explicitly disabled";
223 R <<
"loop not vectorized";
225 R <<
" (Force=" << NV(
"Force", true);
226 if (Width.Value != 0)
227 R <<
", Vector Width=" << NV(
"VectorWidth", getWidth());
228 if (getInterleave() != 0)
229 R <<
", Interleave Count=" << NV(
"InterleaveCount", getInterleave());
252 EC.getKnownMinValue() > 1);
255void LoopVectorizeHints::getHintsFromMetadata() {
270 if (
const MDNode *MD = dyn_cast<MDNode>(MDO)) {
271 if (!MD || MD->getNumOperands() == 0)
273 S = dyn_cast<MDString>(MD->getOperand(0));
274 for (
unsigned Idx = 1;
Idx < MD->getNumOperands(); ++
Idx)
275 Args.push_back(MD->getOperand(
Idx));
277 S = dyn_cast<MDString>(MDO);
278 assert(Args.size() == 0 &&
"too many arguments for MDString");
286 if (
Args.size() == 1)
287 setHint(
Name, Args[0]);
292 if (!
Name.starts_with(Prefix()))
296 const ConstantInt *
C = mdconst::dyn_extract<ConstantInt>(Arg);
299 unsigned Val =
C->getZExtValue();
301 Hint *Hints[] = {&Width, &Interleave, &Force,
302 &IsVectorized, &Predicate, &Scalable};
303 for (
auto *
H : Hints) {
304 if (
Name ==
H->Name) {
305 if (
H->validate(Val))
354 auto *LatchBr = dyn_cast<BranchInst>(Latch->
getTerminator());
355 if (!LatchBr || LatchBr->isUnconditional()) {
361 auto *LatchCmp = dyn_cast<CmpInst>(LatchBr->getCondition());
364 dbgs() <<
"LV: Loop latch condition is not a compare instruction.\n");
368 Value *CondOp0 = LatchCmp->getOperand(0);
369 Value *CondOp1 = LatchCmp->getOperand(1);
370 Value *IVUpdate =
IV->getIncomingValueForBlock(Latch);
373 LLVM_DEBUG(
dbgs() <<
"LV: Loop latch condition is not uniform.\n");
387 for (
Loop *SubLp : *Lp)
396 return DL.getIntPtrType(Ty);
420 if (!AllowedExit.
count(Inst))
426 LLVM_DEBUG(
dbgs() <<
"LV: Found an outside user for : " << *UI <<
'\n');
441 Value *APtr =
A->getPointerOperand();
442 Value *BPtr =
B->getPointerOperand();
456 const auto &Strides =
460 bool OptForSize =
F->hasOptSize() ||
463 bool CanAddPredicate = !OptForSize;
465 CanAddPredicate,
false).value_or(0);
466 if (Stride == 1 || Stride == -1)
482class SCEVAddRecForUniformityRewriter
485 unsigned StepMultiplier;
494 bool CannotAnalyze =
false;
496 bool canAnalyze()
const {
return !CannotAnalyze; }
499 SCEVAddRecForUniformityRewriter(
ScalarEvolution &SE,
unsigned StepMultiplier,
500 unsigned Offset,
Loop *TheLoop)
506 "addrec outside of TheLoop must be invariant and should have been "
512 if (!SE.isLoopInvariant(Step, TheLoop)) {
513 CannotAnalyze =
true;
516 const SCEV *NewStep =
517 SE.getMulExpr(Step, SE.getConstant(Ty, StepMultiplier));
518 const SCEV *ScaledOffset = SE.getMulExpr(Step, SE.getConstant(Ty, Offset));
519 const SCEV *NewStart = SE.getAddExpr(Expr->
getStart(), ScaledOffset);
524 if (CannotAnalyze || SE.isLoopInvariant(S, TheLoop))
530 if (SE.isLoopInvariant(S, TheLoop))
533 CannotAnalyze =
true;
539 CannotAnalyze =
true;
544 unsigned StepMultiplier,
unsigned Offset,
551 [](
const SCEV *S) {
return isa<SCEVUDivExpr>(S); }))
554 SCEVAddRecForUniformityRewriter
Rewriter(SE, StepMultiplier, Offset,
576 auto *SE = PSE.
getSE();
584 const SCEV *FirstLaneExpr =
585 SCEVAddRecForUniformityRewriter::rewrite(S, *SE, FixedVF, 0, TheLoop);
586 if (isa<SCEVCouldNotCompute>(FirstLaneExpr))
592 return all_of(
reverse(seq<unsigned>(1, FixedVF)), [&](
unsigned I) {
593 const SCEV *IthLaneExpr =
594 SCEVAddRecForUniformityRewriter::rewrite(S, *SE, FixedVF,
I, TheLoop);
595 return FirstLaneExpr == IthLaneExpr;
611bool LoopVectorizationLegality::canVectorizeOuterLoop() {
621 auto *Br = dyn_cast<BranchInst>(BB->getTerminator());
624 "loop control flow is not understood by vectorizer",
625 "CFGNotUnderstood", ORE, TheLoop);
638 if (Br && Br->isConditional() &&
643 "loop control flow is not understood by vectorizer",
644 "CFGNotUnderstood", ORE, TheLoop);
657 "loop control flow is not understood by vectorizer",
658 "CFGNotUnderstood", ORE, TheLoop);
666 if (!setupOuterLoopInductions()) {
668 "Unsupported outer loop Phi(s)",
669 "UnsupportedPhi", ORE, TheLoop);
679void LoopVectorizationLegality::addInductionPhi(
682 Inductions[
Phi] =
ID;
705 ID.getConstIntStepValue() &&
ID.getConstIntStepValue()->isOne() &&
706 isa<Constant>(
ID.getStartValue()) &&
707 cast<Constant>(
ID.getStartValue())->isNullValue()) {
713 if (!PrimaryInduction || PhiTy == WidestIndTy)
714 PrimaryInduction =
Phi;
731bool LoopVectorizationLegality::setupOuterLoopInductions() {
735 auto IsSupportedPhi = [&](
PHINode &
Phi) ->
bool {
739 addInductionPhi(&Phi,
ID, AllowedExit);
745 dbgs() <<
"LV: Found unsupported PHI for outer loop vectorization.\n");
768 TLI.
getWidestVF(ScalarName, WidestFixedVF, WidestScalableVF);
776 "Caller may decide to scalarize a variant using a scalable VF");
781bool LoopVectorizationLegality::canVectorizeInstrs() {
788 if (
auto *Phi = dyn_cast<PHINode>(&
I)) {
789 Type *PhiTy = Phi->getType();
794 "loop control flow is not understood by vectorizer",
795 "CFGNotUnderstood", ORE, TheLoop);
813 if (
Phi->getNumIncomingValues() != 2) {
815 "loop control flow is not understood by vectorizer",
816 "CFGNotUnderstood", ORE, TheLoop, Phi);
825 Reductions[
Phi] = RedDes;
833 auto IsDisallowedStridedPointerInduction =
838 ID.getConstIntStepValue() ==
nullptr;
857 !IsDisallowedStridedPointerInduction(
ID)) {
858 addInductionPhi(Phi,
ID, AllowedExit);
865 FixedOrderRecurrences.
insert(Phi);
872 !IsDisallowedStridedPointerInduction(
ID)) {
873 addInductionPhi(Phi,
ID, AllowedExit);
878 "value that could not be identified as "
879 "reduction is used outside the loop",
880 "NonReductionValueUsedOutsideLoop", ORE, TheLoop, Phi);
888 auto *CI = dyn_cast<CallInst>(&
I);
891 !isa<DbgInfoIntrinsic>(CI) &&
892 !(CI->getCalledFunction() && TLI &&
899 TLI && CI->getCalledFunction() &&
900 CI->getType()->isFloatingPointTy() &&
901 TLI->
getLibFunc(CI->getCalledFunction()->getName(), Func) &&
910 "Found a non-intrinsic callsite",
911 "library call cannot be vectorized. "
912 "Try compiling with -fno-math-errno, -ffast-math, "
914 "CantVectorizeLibcall", ORE, TheLoop, CI);
917 "call instruction cannot be vectorized",
918 "CantVectorizeLibcall", ORE, TheLoop, CI);
926 auto *SE = PSE.
getSE();
928 for (
unsigned Idx = 0;
Idx < CI->arg_size(); ++
Idx)
933 "intrinsic instruction cannot be vectorized",
934 "CantVectorizeIntrinsic", ORE, TheLoop, CI);
943 VecCallVariantsFound =
true;
948 !
I.getType()->isVoidTy()) ||
949 isa<ExtractElementInst>(
I)) {
951 "instruction return type cannot be vectorized",
952 "CantVectorizeInstructionReturnType", ORE, TheLoop, &
I);
957 if (
auto *ST = dyn_cast<StoreInst>(&
I)) {
958 Type *
T =
ST->getValueOperand()->getType();
961 "store instruction cannot be vectorized",
962 "CantVectorizeStore", ORE, TheLoop, ST);
968 if (
ST->getMetadata(LLVMContext::MD_nontemporal)) {
971 assert(VecTy &&
"did not find vectorized version of stored type");
974 "nontemporal store instruction cannot be vectorized",
975 "nontemporal store instruction cannot be vectorized",
976 "CantVectorizeNontemporalStore", ORE, TheLoop, ST);
981 }
else if (
auto *LD = dyn_cast<LoadInst>(&
I)) {
982 if (
LD->getMetadata(LLVMContext::MD_nontemporal)) {
986 assert(VecTy &&
"did not find vectorized version of load type");
989 "nontemporal load instruction cannot be vectorized",
990 "nontemporal load instruction cannot be vectorized",
991 "CantVectorizeNontemporalLoad", ORE, TheLoop, LD);
1001 }
else if (
I.getType()->isFloatingPointTy() && (CI ||
I.isBinaryOp()) &&
1004 Hints->setPotentiallyUnsafe();
1019 "value cannot be used outside the loop",
1020 "ValueUsedOutsideLoop", ORE, TheLoop, &
I);
1026 if (!PrimaryInduction) {
1027 if (Inductions.
empty()) {
1029 "loop induction variable could not be identified",
1030 "NoInductionVariable", ORE, TheLoop);
1035 "integer loop induction variable could not be identified",
1036 "NoIntegerInductionVariable", ORE, TheLoop);
1039 LLVM_DEBUG(
dbgs() <<
"LV: Did not find one integer induction var.\n");
1045 if (PrimaryInduction && WidestIndTy != PrimaryInduction->
getType())
1046 PrimaryInduction =
nullptr;
1051bool LoopVectorizationLegality::canVectorizeMemory() {
1052 LAI = &LAIs.
getInfo(*TheLoop);
1057 "loop not vectorized: ", *LAR);
1066 "write to a loop invariant address could not "
1068 "CantVectorizeStoreToLoopInvariantAddress", ORE,
1086 "We don't allow storing to uniform addresses",
1087 "write of conditional recurring variant value to a loop "
1088 "invariant address could not be vectorized",
1089 "CantVectorizeStoreToLoopInvariantAddress", ORE, TheLoop);
1099 "Invariant address is calculated inside the loop",
1100 "write to a loop invariant address could not "
1102 "CantVectorizeStoreToLoopInvariantAddress", ORE, TheLoop);
1130 I->getValueOperand()->getType() ==
1131 SI->getValueOperand()->getType();
1138 bool IsOK = UnhandledStores.
empty();
1142 "We don't allow storing to uniform addresses",
1143 "write to a loop invariant address could not "
1145 "CantVectorizeStoreToLoopInvariantAddress", ORE, TheLoop);
1156 bool EnableStrictReductions) {
1165 if (!EnableStrictReductions ||
1196 return V == InvariantAddress ||
1203 PHINode *PN = dyn_cast_or_null<PHINode>(In0);
1207 return Inductions.
count(PN);
1232 const Value *V)
const {
1233 auto *Inst = dyn_cast<Instruction>(V);
1234 return (Inst && InductionCastsToIgnore.
count(Inst));
1243 return FixedOrderRecurrences.
count(Phi);
1250bool LoopVectorizationLegality::blockCanBePredicated(
1256 if (
match(&
I, m_Intrinsic<Intrinsic::assume>())) {
1264 if (isa<NoAliasScopeDeclInst>(&
I))
1271 if (
CallInst *CI = dyn_cast<CallInst>(&
I))
1278 if (
auto *LI = dyn_cast<LoadInst>(&
I)) {
1279 if (!SafePtrs.
count(LI->getPointerOperand()))
1289 if (
auto *SI = dyn_cast<StoreInst>(&
I)) {
1294 if (
I.mayReadFromMemory() ||
I.mayWriteToMemory() ||
I.mayThrow())
1301bool LoopVectorizationLegality::canVectorizeWithIfConvert() {
1304 "if-conversion is disabled",
1305 "IfConversionDisabled",
1346 if (isa<SwitchInst>(BB->getTerminator())) {
1349 "loop contains an unsupported switch",
1350 "LoopContainsUnsupportedSwitch", ORE,
1351 TheLoop, BB->getTerminator());
1354 }
else if (!isa<BranchInst>(BB->getTerminator())) {
1356 "loop contains an unsupported terminator",
1357 "LoopContainsUnsupportedTerminator", ORE,
1358 TheLoop, BB->getTerminator());
1364 !blockCanBePredicated(BB, SafePointers, MaskedOp)) {
1366 "Control flow cannot be substituted for a select",
1367 "control flow cannot be substituted for a select",
"NoCFGForSelect",
1368 ORE, TheLoop, BB->getTerminator());
1378bool LoopVectorizationLegality::canVectorizeLoopCFG(
Loop *Lp,
1379 bool UseVPlanNativePath) {
1381 "VPlan-native path is not enabled.");
1397 "loop control flow is not understood by vectorizer",
1398 "CFGNotUnderstood", ORE, TheLoop);
1399 if (DoExtraAnalysis)
1408 "loop control flow is not understood by vectorizer",
1409 "CFGNotUnderstood", ORE, TheLoop);
1410 if (DoExtraAnalysis)
1419bool LoopVectorizationLegality::canVectorizeLoopNestCFG(
1420 Loop *Lp,
bool UseVPlanNativePath) {
1425 if (!canVectorizeLoopCFG(Lp, UseVPlanNativePath)) {
1426 if (DoExtraAnalysis)
1434 for (
Loop *SubLp : *Lp)
1435 if (!canVectorizeLoopNestCFG(SubLp, UseVPlanNativePath)) {
1436 if (DoExtraAnalysis)
1453 if (!canVectorizeLoopNestCFG(TheLoop, UseVPlanNativePath)) {
1454 if (DoExtraAnalysis)
1467 assert(UseVPlanNativePath &&
"VPlan-native path is not enabled.");
1469 if (!canVectorizeOuterLoop()) {
1471 "unsupported outer loop",
1472 "UnsupportedOuterLoop",
1486 if (NumBlocks != 1 && !canVectorizeWithIfConvert()) {
1488 if (DoExtraAnalysis)
1495 if (!canVectorizeInstrs()) {
1496 LLVM_DEBUG(
dbgs() <<
"LV: Can't vectorize the instructions or CFG\n");
1497 if (DoExtraAnalysis)
1504 if (!canVectorizeMemory()) {
1505 LLVM_DEBUG(
dbgs() <<
"LV: Can't vectorize due to memory conflicts\n");
1506 if (DoExtraAnalysis)
1514 "could not determine number of loop iterations",
1515 "CantComputeNumberOfIterations", ORE, TheLoop);
1516 if (DoExtraAnalysis)
1524 ?
" (with a runtime bound check)"
1534 "Too many SCEV assumptions need to be made and checked at runtime",
1535 "TooManySCEVRunTimeChecks", ORE, TheLoop);
1536 if (DoExtraAnalysis)
1551 LLVM_DEBUG(
dbgs() <<
"LV: checking if tail can be folded by masking.\n");
1559 for (
auto *AE : AllowedExit) {
1562 if (ReductionLiveOuts.
count(AE))
1564 for (
User *U : AE->users()) {
1570 <<
"LV: Cannot fold tail by masking, loop has an outside user for "
1577 PHINode *OrigPhi = Entry.first;
1579 auto *UI = cast<Instruction>(U);
1581 LLVM_DEBUG(
dbgs() <<
"LV: Cannot fold tail by masking, loop IV has an "
1596 if (!blockCanBePredicated(BB, SafePointers, TmpMaskedOp)) {
1614 [[maybe_unused]]
bool R = blockCanBePredicated(BB, SafePointers, MaskedOp);
1615 assert(R &&
"Must be able to predicate block when tail-folding.");
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
loop Loop Strength Reduction
static cl::opt< LoopVectorizeHints::ScalableForceKind > ForceScalableVectorization("scalable-vectorization", cl::init(LoopVectorizeHints::SK_Unspecified), cl::Hidden, cl::desc("Control whether the compiler can use scalable vectors to " "vectorize a loop"), cl::values(clEnumValN(LoopVectorizeHints::SK_FixedWidthOnly, "off", "Scalable vectorization is disabled."), clEnumValN(LoopVectorizeHints::SK_PreferScalable, "preferred", "Scalable vectorization is available and favored when the " "cost is inconclusive."), clEnumValN(LoopVectorizeHints::SK_PreferScalable, "on", "Scalable vectorization is available and favored when the " "cost is inconclusive.")))
static cl::opt< unsigned > PragmaVectorizeSCEVCheckThreshold("pragma-vectorize-scev-check-threshold", cl::init(128), cl::Hidden, cl::desc("The maximum number of SCEV checks allowed with a " "vectorize(enable) pragma"))
static const unsigned MaxInterleaveFactor
Maximum vectorization interleave count.
static cl::opt< bool > AllowStridedPointerIVs("lv-strided-pointer-ivs", cl::init(false), cl::Hidden, cl::desc("Enable recognition of non-constant strided " "pointer induction variables."))
static cl::opt< unsigned > VectorizeSCEVCheckThreshold("vectorize-scev-check-threshold", cl::init(16), cl::Hidden, cl::desc("The maximum number of SCEV checks allowed."))
static cl::opt< bool > EnableIfConversion("enable-if-conversion", cl::init(true), cl::Hidden, cl::desc("Enable if-conversion during vectorization."))
This file defines the LoopVectorizationLegality class.
static bool rewrite(Function &F)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void visit(MachineFunction &MF, MachineBasicBlock &Start, std::function< void(MachineBasicBlock *)> op)
Virtual Register Rewriter
static const uint32_t IV[8]
Class for arbitrary precision integers.
LLVM Basic Block Representation.
const Function * getParent() const
Return the enclosing method, or null if none.
LLVMContext & getContext() const
Get the context in which this basic block lives.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
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.
This is the shared class of boolean and integer constants.
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)
constexpr bool isScalar() const
Exactly one element.
static FixedVectorType * get(Type *ElementType, unsigned NumElts)
A struct for saving information about induction variables.
@ IK_FpInduction
Floating point induction variable.
@ IK_PtrInduction
Pointer induction var. Step = C.
@ IK_IntInduction
Integer induction variable. Step = C.
static bool isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE, InductionDescriptor &D, const SCEV *Expr=nullptr, SmallVectorImpl< Instruction * > *CastsToIgnore=nullptr)
Returns true if Phi is an induction in the loop L.
Instruction * getExactFPMathInst()
Returns floating-point induction operator that does not allow reassociation (transforming the inducti...
This is an important class for using LLVM in a threaded context.
An instruction for reading from memory.
Value * getPointerOperand()
const LoopAccessInfo & getInfo(Loop &L)
ArrayRef< StoreInst * > getStoresToInvariantAddresses() const
Return the list of stores to invariant addresses.
const OptimizationRemarkAnalysis * getReport() const
The diagnostics report generated for the analysis.
const RuntimePointerChecking * getRuntimePointerChecking() const
bool canVectorizeMemory() const
Return true we can analyze the memory accesses in the loop and there are no memory dependence cycles.
bool isInvariant(Value *V) const
Returns true if value V is loop invariant.
bool hasLoadStoreDependenceInvolvingLoopInvariantAddress() const
Return true if the loop has memory dependence involving a load and a store to an invariant address,...
const PredicatedScalarEvolution & getPSE() const
Used to add runtime SCEV checks.
static bool blockNeedsPredication(BasicBlock *BB, Loop *TheLoop, DominatorTree *DT)
Return true if the block BB needs to be predicated in order for the loop to be vectorized.
const DenseMap< Value *, const SCEV * > & getSymbolicStrides() const
If an access has a symbolic strides, this maps the pointer value to the stride symbol.
bool hasStoreStoreDependenceInvolvingLoopInvariantAddress() const
Return true if the loop has memory dependence involving two stores to an invariant address,...
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
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 getNumBlocks() const
Get the number of blocks in this loop in constant time.
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.
bool isLoopExiting(const BlockT *BB) const
True if terminator in the block can branch to another block that is outside of the current loop.
bool isLoopHeader(const BlockT *BB) const
bool isInvariantStoreOfReduction(StoreInst *SI)
Returns True if given store is a final invariant store of one of the reductions found in the loop.
bool isInvariantAddressOfReduction(Value *V)
Returns True if given address is invariant and is used to store recurrent expression.
bool blockNeedsPredication(BasicBlock *BB) const
Return true if the block BB needs to be predicated in order for the loop to be vectorized.
bool canVectorize(bool UseVPlanNativePath)
Returns true if it is legal to vectorize this loop.
int isConsecutivePtr(Type *AccessTy, Value *Ptr) const
Check if this pointer is consecutive when vectorizing.
bool canVectorizeFPMath(bool EnableStrictReductions)
Returns true if it is legal to vectorize the FP math operations in this loop.
bool isFixedOrderRecurrence(const PHINode *Phi) const
Returns True if Phi is a fixed-order recurrence in this loop.
const InductionDescriptor * getPointerInductionDescriptor(PHINode *Phi) const
Returns a pointer to the induction descriptor, if Phi is pointer induction.
const InductionDescriptor * getIntOrFpInductionDescriptor(PHINode *Phi) const
Returns a pointer to the induction descriptor, if Phi is an integer or floating point induction.
bool isInductionPhi(const Value *V) const
Returns True if V is a Phi node of an induction variable in this loop.
bool isUniform(Value *V, ElementCount VF) const
Returns true if value V is uniform across VF lanes, when VF is provided, and otherwise if V is invari...
const InductionList & getInductionVars() const
Returns the induction variables found in the loop.
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.
bool canFoldTailByMasking() const
Return true if we can vectorize this loop while folding its tail by masking.
void prepareToFoldTailByMasking()
Mark all respective loads/stores for masking.
bool isUniformMemOp(Instruction &I, ElementCount VF) const
A uniform memory op is a load or store which accesses the same memory location on all VF lanes,...
bool isInductionVariable(const Value *V) const
Returns True if V can be considered as an induction variable in this loop.
bool isCastedInductionVariable(const Value *V) const
Returns True if V is a cast that is part of an induction def-use chain, and had been proven to be red...
Instruction * getExactFPInst()
void addExactFPMathInst(Instruction *I)
Track the 1st floating-point instruction that can not be reassociated.
@ SK_PreferScalable
Vectorize loops using scalable vectors or fixed-width vectors, but favor scalable vectors when the co...
@ SK_Unspecified
Not selected.
@ SK_FixedWidthOnly
Disables vectorization with scalable vectors.
enum ForceKind getForce() const
bool allowVectorization(Function *F, Loop *L, bool VectorizeOnlyWhenForced) const
bool allowReordering() const
When enabling loop hints are provided we allow the vectorizer to change the order of operations that ...
void emitRemarkWithHints() const
Dumps all the hint information.
ElementCount getWidth() const
@ FK_Enabled
Forcing enabled.
@ FK_Undefined
Not selected.
@ FK_Disabled
Forcing disabled.
void setAlreadyVectorized()
Mark the loop L as already vectorized by setting the width to 1.
LoopVectorizeHints(const Loop *L, bool InterleaveOnlyWhenForced, OptimizationRemarkEmitter &ORE, const TargetTransformInfo *TTI=nullptr)
const char * vectorizeAnalysisPassName() const
If hints are provided that force vectorization, use the AlwaysPrint pass name to force the frontend t...
unsigned getInterleave() const
unsigned getIsVectorized() const
Represents a single loop in the control flow graph.
DebugLoc getStartLoc() const
Return the debug location of the start of this loop.
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
PHINode * getCanonicalInductionVariable() const
Check to see if the loop has a canonical induction variable: an integer recurrence that starts at 0 a...
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
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
unsigned getNumOperands() const
Return number of MDNode operands.
Tracking metadata reference owned by Metadata.
StringRef getString() const
static MDString * get(LLVMContext &Context, StringRef Str)
size_type count(const KeyT &Key) const
iterator find(const KeyT &Key)
void addPredicate(const SCEVPredicate &Pred)
Adds a new predicate.
ScalarEvolution * getSE() const
Returns the ScalarEvolution analysis used.
const SCEVPredicate & getPredicate() const
const SCEV * getBackedgeTakenCount()
Get the (predicated) backedge count for the analyzed loop.
const SCEV * getSCEV(Value *V)
Returns the SCEV expression of V, in the context of the current SCEV predicate.
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 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.
Instruction * getLoopExitInstr() const
static 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 isOrdered() const
Expose an ordered FP reduction to the instance users.
StoreInst * IntermediateStore
Reductions may store temporary or final result to an invariant address.
bool Need
This flag indicates if we need to add the runtime check.
This node represents a polynomial recurrence on the trip count of the specified loop.
const SCEV * getStart() const
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
const Loop * getLoop() const
virtual unsigned getComplexity() const
Returns the estimated complexity of this predicate.
virtual bool isAlwaysTrue() const =0
Returns true if the predicate is always true.
This visitor recursively visits a SCEV expression and re-writes it.
const SCEV * visit(const SCEV *S)
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
This class represents an analyzed expression in the program.
The main scalar evolution driver.
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
const SCEV * getCouldNotCompute()
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
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...
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()
StringRef - Represent a constant reference to a string, i.e.
static constexpr size_t npos
Provides information about what library functions are available for the current target.
bool hasOptimizedCodeGen(LibFunc F) const
Tests if the function is both available and a candidate for optimized code generation.
void getWidestVF(StringRef ScalarF, ElementCount &FixedVF, ElementCount &ScalableVF) const
Returns the largest vectorization factor used in the list of vector functions.
bool getLibFunc(StringRef funcName, LibFunc &F) const
Searches for a particular function name.
bool isFunctionVectorizable(StringRef F, const ElementCount &VF) const
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
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.
bool isVectorTy() const
True if this is an instance of VectorType.
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.
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
bool isFloatingPointTy() const
Return true if this is one of the floating-point types.
static IntegerType * getInt32Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
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.
iterator_range< user_iterator > users()
StringRef getName() const
Return a constant reference to the value's name.
static 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 isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
constexpr ScalarTy getKnownMinValue() const
Returns the minimum value this quantity can represent.
constexpr bool isZero() const
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ C
The default llvm calling convention, compatible with C.
bool match(Val *V, const Pattern &P)
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
initializer< Ty > init(const Ty &Val)
NodeAddr< PhiNode * > Phi
NodeAddr< FuncNode * > Func
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.
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.
Intrinsic::ID getVectorIntrinsicIDForCall(const CallInst *CI, const TargetLibraryInfo *TLI)
Returns intrinsic ID for call.
cl::opt< bool > HintsAllowReordering("hints-allow-reordering", cl::init(true), cl::Hidden, cl::desc("Allow enabling loop hints to reorder " "FP operations during vectorization."))
static Type * getWiderType(const DataLayout &DL, Type *Ty0, Type *Ty1)
const Value * getLoadStorePointerOperand(const Value *V)
A helper function that returns the pointer operand of a load or store instruction.
static Type * convertPointerToIntegerType(const DataLayout &DL, Type *Ty)
static bool isUniformLoopNest(Loop *Lp, Loop *OuterLp)
bool shouldOptimizeForSize(const MachineFunction *MF, ProfileSummaryInfo *PSI, const MachineBlockFrequencyInfo *BFI, PGSOQueryType QueryType=PGSOQueryType::Other)
Returns true if machine function MF is suggested to be size-optimized based on the profile.
static bool isUniformLoop(Loop *Lp, Loop *OuterLp)
bool mustSuppressSpeculation(const LoadInst &LI)
Return true if speculation of the given load must be suppressed to avoid ordering or interfering with...
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.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
std::optional< int64_t > getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy, Value *Ptr, const Loop *Lp, const DenseMap< Value *, const SCEV * > &StridesMap=DenseMap< Value *, const SCEV * >(), bool Assume=false, bool ShouldCheckWrap=true)
If the pointer has a constant stride return it in units of the access type size.
bool isDereferenceableAndAlignedInLoop(LoadInst *LI, Loop *L, ScalarEvolution &SE, DominatorTree &DT, AssumptionCache *AC=nullptr)
Return true if we can prove that the given load (which is assumed to be within the specified loop) wo...
static bool hasOutsideLoopUser(const Loop *TheLoop, Instruction *Inst, SmallPtrSetImpl< Value * > &AllowedExit)
Check that the instruction has outside loop users and is not an identified reduction variable.
static bool storeToSameAddress(ScalarEvolution *SE, StoreInst *A, StoreInst *B)
Returns true if A and B have same pointer operands or same SCEVs addresses.
void reportVectorizationFailure(const StringRef DebugMsg, const StringRef OREMsg, const StringRef ORETag, OptimizationRemarkEmitter *ORE, Loop *TheLoop, Instruction *I=nullptr)
Reports a vectorization failure: print DebugMsg for debugging purposes along with the corresponding o...
llvm::MDNode * makePostTransformationMetadata(llvm::LLVMContext &Context, MDNode *OrigLoopID, llvm::ArrayRef< llvm::StringRef > RemovePrefixes, llvm::ArrayRef< llvm::MDNode * > AddAttrs)
Create a new LoopID after the loop has been transformed.
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 isVectorIntrinsicWithScalarOpAtArg(Intrinsic::ID ID, unsigned ScalarOpdIdx)
Identifies if the vector form of the intrinsic has a scalar operand.
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 ...
bool SCEVExprContains(const SCEV *Root, PredTy Pred)
Return true if any node in Root satisfies the predicate Pred.
An object of this class is returned by queries that could not be answered.
TODO: The following VectorizationFactor was pulled out of LoopVectorizationCostModel class.
Collection of parameters shared beetween the Loop Vectorizer and the Loop Access Analysis.
static const unsigned MaxVectorWidth
Maximum SIMD width.
static bool isInterleaveForced()
True if force-vector-interleave was specified by the user.
static unsigned VectorizationInterleave
Interleave factor as overridden by the user.