LLVM 17.0.0git
|
LoopVectorizationLegality checks if it is legal to vectorize a loop, and to what vectorization factor. More...
#include "llvm/Transforms/Vectorize/LoopVectorizationLegality.h"
Public Types | |
using | ReductionList = MapVector< PHINode *, RecurrenceDescriptor > |
ReductionList contains the reduction descriptors for all of the reductions that were found in the loop. | |
using | InductionList = MapVector< PHINode *, InductionDescriptor > |
InductionList saves induction variables and maps them to the induction descriptor. | |
using | RecurrenceSet = SmallPtrSet< const PHINode *, 8 > |
RecurrenceSet contains the phi nodes that are recurrences other than inductions and reductions. | |
Public Member Functions | |
LoopVectorizationLegality (Loop *L, PredicatedScalarEvolution &PSE, DominatorTree *DT, TargetTransformInfo *TTI, TargetLibraryInfo *TLI, Function *F, LoopAccessInfoManager &LAIs, LoopInfo *LI, OptimizationRemarkEmitter *ORE, LoopVectorizationRequirements *R, LoopVectorizeHints *H, DemandedBits *DB, AssumptionCache *AC, BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI) | |
bool | canVectorize (bool UseVPlanNativePath) |
Returns true if it is legal to vectorize this loop. | |
bool | canVectorizeFPMath (bool EnableStrictReductions) |
Returns true if it is legal to vectorize the FP math operations in this loop. | |
bool | prepareToFoldTailByMasking () |
Return true if we can vectorize this loop while folding its tail by masking, and mark all respective loads/stores for masking. | |
PHINode * | getPrimaryInduction () |
Returns the primary induction variable. | |
const ReductionList & | getReductionVars () const |
Returns the reduction variables found in the loop. | |
const InductionList & | getInductionVars () const |
Returns the induction variables found in the loop. | |
RecurrenceSet & | getFixedOrderRecurrences () |
Return the fixed-order recurrences found in the loop. | |
Type * | getWidestInductionType () |
Returns the widest induction type. | |
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 | isInductionPhi (const Value *V) const |
Returns True if V is a Phi node of an induction variable in this loop. | |
const InductionDescriptor * | getIntOrFpInductionDescriptor (PHINode *Phi) const |
Returns a pointer to the induction descriptor, if Phi is an integer or floating point induction. | |
const InductionDescriptor * | getPointerInductionDescriptor (PHINode *Phi) const |
Returns a pointer to the induction descriptor, if Phi is pointer induction. | |
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 redundant under a runtime guard (in other words, the cast has the same SCEV expression as the induction phi). | |
bool | isInductionVariable (const Value *V) const |
Returns True if V can be considered as an induction variable in this loop. | |
bool | isReductionVariable (PHINode *PN) const |
Returns True if PN is a reduction variable in this loop. | |
bool | isFixedOrderRecurrence (const PHINode *Phi) const |
Returns True if Phi is a fixed-order recurrence in this loop. | |
bool | blockNeedsPredication (BasicBlock *BB) const |
Return true if the block BB needs to be predicated in order for the loop to be vectorized. | |
int | isConsecutivePtr (Type *AccessTy, Value *Ptr) const |
Check if this pointer is consecutive when vectorizing. | |
bool | isUniform (Value *V) const |
Returns true if the value V is uniform within the loop. | |
bool | isUniformMemOp (Instruction &I) const |
A uniform memory op is a load or store which accesses the same memory location on all lanes. | |
const RuntimePointerChecking * | getRuntimePointerChecking () const |
Returns the information that we collected about runtime memory check. | |
const LoopAccessInfo * | getLAI () const |
bool | isSafeForAnyVectorWidth () const |
unsigned | getMaxSafeDepDistBytes () |
uint64_t | getMaxSafeVectorWidthInBits () const |
bool | isMaskRequired (const Instruction *I) const |
Returns true if vector representation of the instruction I requires mask. | |
unsigned | getNumStores () const |
unsigned | getNumLoads () const |
const SmallPtrSetImpl< Instruction * > & | getConditionalAssumes () const |
Returns all assume calls in predicated blocks. | |
PredicatedScalarEvolution * | getPredicatedScalarEvolution () const |
Loop * | getLoop () const |
LoopInfo * | getLoopInfo () const |
AssumptionCache * | getAssumptionCache () const |
ScalarEvolution * | getScalarEvolution () const |
DominatorTree * | getDominatorTree () const |
LoopVectorizationLegality checks if it is legal to vectorize a loop, and to what vectorization factor.
This class does not look at the profitability of vectorization, only the legality. This class has two main kinds of checks:
Definition at line 241 of file LoopVectorizationLegality.h.
InductionList saves induction variables and maps them to the induction descriptor.
Definition at line 259 of file LoopVectorizationLegality.h.
RecurrenceSet contains the phi nodes that are recurrences other than inductions and reductions.
Definition at line 263 of file LoopVectorizationLegality.h.
ReductionList contains the reduction descriptors for all of the reductions that were found in the loop.
Definition at line 255 of file LoopVectorizationLegality.h.
|
inline |
Definition at line 243 of file LoopVectorizationLegality.h.
bool llvm::LoopVectorizationLegality::blockNeedsPredication | ( | BasicBlock * | BB | ) | const |
Return true if the block BB needs to be predicated in order for the loop to be vectorized.
Definition at line 1115 of file LoopVectorizationLegality.cpp.
References llvm::LoopAccessInfo::blockNeedsPredication().
Referenced by llvm::LoopVectorizationCostModel::blockNeedsPredicationForAnyReason(), llvm::LoopVectorizationCostModel::expectedCost(), llvm::LoopVectorizationCostModel::isPredicatedInst(), and isUniformMemOp().
Returns true if it is legal to vectorize this loop.
This does not mean that it is profitable to vectorize this loop, only that it is legal to do so. Temporarily taking UseVPlanNativePath parameter. If true, take the new code path being implemented for outer loop vectorization (should be functional for inner loop vectorization) based on VPlan. If false, good old LV code.
Definition at line 1309 of file LoopVectorizationLegality.cpp.
References llvm::OptimizationRemarkEmitter::allowExtraAnalysis(), assert(), llvm::dbgs(), DEBUG_TYPE, llvm::LoopVectorizeHints::FK_Enabled, llvm::SCEVPredicate::getComplexity(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::Value::getName(), llvm::LoopBase< BlockT, LoopT >::getNumBlocks(), llvm::PredicatedScalarEvolution::getPredicate(), llvm::LoopAccessInfo::getRuntimePointerChecking(), llvm::LoopBase< BlockT, LoopT >::isInnermost(), LLVM_DEBUG, llvm::RuntimePointerChecking::Need, PragmaVectorizeSCEVCheckThreshold, llvm::reportVectorizationFailure(), and VectorizeSCEVCheckThreshold.
Referenced by llvm::LoopVectorizePass::processLoop().
Returns true if it is legal to vectorize the FP math operations in this loop.
Vectorizing is legal if we allow reordering of FP operations, or if we can use in-order reductions.
Definition at line 1024 of file LoopVectorizationLegality.cpp.
References llvm::all_of(), llvm::any_of(), llvm::LoopVectorizationRequirements::getExactFPInst(), llvm::InductionDescriptor::getExactFPMathInst(), getInductionVars(), getReductionVars(), llvm::RecurrenceDescriptor::hasExactFPMath(), llvm::RecurrenceDescriptor::isOrdered(), and Reduction.
Referenced by llvm::LoopVectorizePass::processLoop().
|
inline |
Definition at line 397 of file LoopVectorizationLegality.h.
Referenced by llvm::ARMTTIImpl::preferPredicateOverEpilogue().
|
inline |
Returns all assume calls in predicated blocks.
They need to be dropped when flattening the CFG.
Definition at line 385 of file LoopVectorizationLegality.h.
|
inline |
Definition at line 401 of file LoopVectorizationLegality.h.
Referenced by llvm::ARMTTIImpl::preferPredicateOverEpilogue().
|
inline |
Return the fixed-order recurrences found in the loop.
Definition at line 294 of file LoopVectorizationLegality.h.
Referenced by llvm::AArch64TTIImpl::preferPredicateOverEpilogue().
|
inline |
Returns the induction variables found in the loop.
Definition at line 291 of file LoopVectorizationLegality.h.
Referenced by canVectorizeFPMath(), llvm::LoopVectorizationCostModel::collectValuesToIgnore(), llvm::InnerLoopVectorizer::createInductionResumeValues(), llvm::InnerLoopVectorizer::fixVectorizedLoop(), getIntOrFpInductionDescriptor(), and getPointerInductionDescriptor().
const InductionDescriptor * llvm::LoopVectorizationLegality::getIntOrFpInductionDescriptor | ( | PHINode * | Phi | ) | const |
Returns a pointer to the induction descriptor, if Phi
is an integer or floating point induction.
Definition at line 1080 of file LoopVectorizationLegality.cpp.
References llvm::MapVector< KeyT, ValueT, MapType, VectorType >::find(), getInductionVars(), llvm::InductionDescriptor::IK_FpInduction, llvm::InductionDescriptor::IK_IntInduction, and isInductionPhi().
|
inline |
Definition at line 362 of file LoopVectorizationLegality.h.
Referenced by llvm::LoopVectorizationPlanner::executePlan(), llvm::ARMTTIImpl::preferPredicateOverEpilogue(), llvm::LoopVectorizePass::processLoop(), processLoopInVPlanNativePath(), and llvm::LoopVectorizationCostModel::runtimeChecksRequired().
|
inline |
Definition at line 393 of file LoopVectorizationLegality.h.
Referenced by llvm::AArch64TTIImpl::preferPredicateOverEpilogue(), and llvm::ARMTTIImpl::preferPredicateOverEpilogue().
|
inline |
Definition at line 395 of file LoopVectorizationLegality.h.
Referenced by llvm::ARMTTIImpl::preferPredicateOverEpilogue().
|
inline |
Definition at line 368 of file LoopVectorizationLegality.h.
References llvm::LoopAccessInfo::getMaxSafeDepDistBytes().
Referenced by llvm::LoopVectorizationCostModel::selectInterleaveCount().
|
inline |
Definition at line 370 of file LoopVectorizationLegality.h.
References llvm::LoopAccessInfo::getDepChecker(), and llvm::MemoryDepChecker::getMaxSafeVectorWidthInBits().
|
inline |
Definition at line 381 of file LoopVectorizationLegality.h.
References llvm::LoopAccessInfo::getNumLoads().
Referenced by llvm::LoopVectorizationCostModel::selectInterleaveCount().
|
inline |
Definition at line 380 of file LoopVectorizationLegality.h.
References llvm::LoopAccessInfo::getNumStores().
Referenced by llvm::LoopVectorizationCostModel::selectInterleaveCount().
const InductionDescriptor * llvm::LoopVectorizationLegality::getPointerInductionDescriptor | ( | PHINode * | Phi | ) | const |
Returns a pointer to the induction descriptor, if Phi
is pointer induction.
Definition at line 1091 of file LoopVectorizationLegality.cpp.
References llvm::MapVector< KeyT, ValueT, MapType, VectorType >::find(), getInductionVars(), llvm::InductionDescriptor::IK_PtrInduction, and isInductionPhi().
|
inline |
Definition at line 389 of file LoopVectorizationLegality.h.
Referenced by llvm::AArch64TTIImpl::preferPredicateOverEpilogue().
|
inline |
Returns the primary induction variable.
Definition at line 285 of file LoopVectorizationLegality.h.
Referenced by llvm::InnerLoopVectorizer::createInductionResumeValue(), and llvm::LoopVectorizationCostModel::isOptimizableIVTruncate().
|
inline |
Returns the reduction variables found in the loop.
Definition at line 288 of file LoopVectorizationLegality.h.
Referenced by canVectorizeFPMath(), llvm::LoopVectorizationCostModel::canVectorizeReductions(), llvm::LoopVectorizationCostModel::collectElementTypesForWidening(), llvm::LoopVectorizationCostModel::collectInLoopReductions(), llvm::LoopVectorizationCostModel::collectValuesToIgnore(), llvm::LoopVectorizationCostModel::getSmallestAndWidestTypes(), isInvariantAddressOfReduction(), isInvariantStoreOfReduction(), llvm::AArch64TTIImpl::preferPredicateOverEpilogue(), prepareToFoldTailByMasking(), llvm::LoopVectorizationCostModel::selectInterleaveCount(), and llvm::VPRecipeBuilder::tryToCreateWidenRecipe().
|
inline |
Returns the information that we collected about runtime memory check.
Definition at line 358 of file LoopVectorizationLegality.h.
References llvm::LoopAccessInfo::getRuntimePointerChecking().
Referenced by llvm::LoopVectorizationCostModel::computeMaxVF(), llvm::LoopVectorizationCostModel::runtimeChecksRequired(), and llvm::LoopVectorizationCostModel::selectInterleaveCount().
|
inline |
Definition at line 399 of file LoopVectorizationLegality.h.
References llvm::PredicatedScalarEvolution::getSE().
Referenced by llvm::ARMTTIImpl::preferPredicateOverEpilogue().
|
inline |
Returns the widest induction type.
Definition at line 297 of file LoopVectorizationLegality.h.
Returns True if V is a cast that is part of an induction def-use chain, and had been proven to be redundant under a runtime guard (in other words, the cast has the same SCEV expression as the induction phi).
Definition at line 1100 of file LoopVectorizationLegality.cpp.
References llvm::SmallPtrSetImpl< PtrType >::count().
Referenced by isInductionVariable().
Check if this pointer is consecutive when vectorizing.
This happens when the last index of the GEP is the induction variable, or that the pointer itself is an induction variable. This check allows us to vectorize A[idx] into a wide load/store. Returns: 0 - Stride is unknown or non-consecutive. 1 - Address is consecutive. -1 - Address is consecutive, and decreasing. NOTE: This method must only be used before modifying the original scalar loop. Do not use after invoking 'createVectorizedLoopSkeleton' (PR34965).
Definition at line 453 of file LoopVectorizationLegality.cpp.
References F, llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::BasicBlock::getParent(), llvm::getPtrStride(), llvm::LoopAccessInfo::getSymbolicStrides(), llvm::IRPass, Ptr, and llvm::shouldOptimizeForSize().
Referenced by llvm::LoopVectorizationCostModel::isLegalMaskedLoad(), llvm::LoopVectorizationCostModel::isLegalMaskedStore(), llvm::LoopVectorizationCostModel::memoryInstructionCanBeWidened(), and llvm::LoopVectorizationCostModel::setCostBasedWideningDecision().
Returns True if Phi is a fixed-order recurrence in this loop.
Definition at line 1110 of file LoopVectorizationLegality.cpp.
References llvm::SmallPtrSetImpl< PtrType >::count().
Referenced by llvm::VPRecipeBuilder::tryToCreateWidenRecipe().
Returns True if V is a Phi node of an induction variable in this loop.
Definition at line 1070 of file LoopVectorizationLegality.cpp.
References llvm::MapVector< KeyT, ValueT, MapType, VectorType >::count().
Referenced by getIntOrFpInductionDescriptor(), getPointerInductionDescriptor(), isInductionVariable(), and llvm::LoopVectorizationCostModel::isOptimizableIVTruncate().
Returns True if V can be considered as an induction variable in this loop.
V can be the induction phi, or some redundant cast in the def-use chain of the inducion phi.
Definition at line 1106 of file LoopVectorizationLegality.cpp.
References isCastedInductionVariable(), and isInductionPhi().
Returns True if given address is invariant and is used to store recurrent expression.
Definition at line 1057 of file LoopVectorizationLegality.cpp.
References llvm::any_of(), llvm::StoreInst::getPointerOperand(), getReductionVars(), llvm::ScalarEvolution::getSCEV(), llvm::PredicatedScalarEvolution::getSE(), llvm::RecurrenceDescriptor::IntermediateStore, and Reduction.
Referenced by llvm::LoopVectorizationCostModel::collectValuesToIgnore().
Returns True if given store is a final invariant store of one of the reductions found in the loop.
Definition at line 1050 of file LoopVectorizationLegality.cpp.
References llvm::any_of(), getReductionVars(), llvm::RecurrenceDescriptor::IntermediateStore, Reduction, and SI.
|
inline |
Returns true if vector representation of the instruction I
requires mask.
Definition at line 376 of file LoopVectorizationLegality.h.
References I.
Referenced by llvm::LoopVectorizationCostModel::getVectorCallCost(), llvm::LoopVectorizationCostModel::interleavedAccessCanBeWidened(), and llvm::LoopVectorizationCostModel::isPredicatedInst().
Returns True if PN is a reduction variable in this loop.
Definition at line 329 of file LoopVectorizationLegality.h.
References llvm::MapVector< KeyT, ValueT, MapType, VectorType >::count().
Referenced by llvm::LoopVectorizationCostModel::collectElementTypesForWidening(), llvm::InnerLoopVectorizer::fixReduction(), and llvm::VPRecipeBuilder::tryToCreateWidenRecipe().
|
inline |
Definition at line 364 of file LoopVectorizationLegality.h.
References llvm::LoopAccessInfo::getDepChecker(), and llvm::MemoryDepChecker::isSafeForAnyVectorWidth().
Returns true if the value V is uniform within the loop.
Definition at line 474 of file LoopVectorizationLegality.cpp.
References llvm::LoopAccessInfo::isUniform().
Referenced by llvm::LoopVectorizationCostModel::getDivRemSpeculationCost(), and isUniformMemOp().
bool llvm::LoopVectorizationLegality::isUniformMemOp | ( | Instruction & | I | ) | const |
A uniform memory op is a load or store which accesses the same memory location on all lanes.
Definition at line 478 of file LoopVectorizationLegality.cpp.
References blockNeedsPredication(), llvm::getLoadStorePointerOperand(), I, isUniform(), and Ptr.
Referenced by llvm::LoopVectorizationCostModel::isPredicatedInst(), and llvm::LoopVectorizationCostModel::setCostBasedWideningDecision().
bool llvm::LoopVectorizationLegality::prepareToFoldTailByMasking | ( | ) |
Return true if we can vectorize this loop while folding its tail by masking, and mark all respective loads/stores for masking.
This object's state is only modified iff this function returns true.
Definition at line 1403 of file LoopVectorizationLegality.cpp.
References llvm::SmallPtrSetImpl< PtrType >::begin(), llvm::LoopBase< BlockT, LoopT >::blocks(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), llvm::SmallPtrSetImpl< PtrType >::end(), getReductionVars(), llvm::SmallPtrSetImpl< PtrType >::insert(), LLVM_DEBUG, and Reduction.
Referenced by llvm::LoopVectorizationCostModel::computeMaxVF().