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 = DenseMap< PHINode *, RecurrenceDescriptor >
	ReductionList contains the reduction descriptors for all of the reductions that were found in the loop. More...

using	InductionList = MapVector< PHINode *, InductionDescriptor >
	InductionList saves induction variables and maps them to the induction descriptor. More...

using	RecurrenceSet = SmallPtrSet< const PHINode *, 8 >
	RecurrenceSet contains the phi nodes that are recurrences other than inductions and reductions. More...

Public Member Functions
	LoopVectorizationLegality (Loop L, PredicatedScalarEvolution &PSE, DominatorTree DT, TargetLibraryInfo TLI, AliasAnalysis AA, Function F, std::function< const LoopAccessInfo &(Loop &)> GetLAA, LoopInfo LI, OptimizationRemarkEmitter ORE, LoopVectorizationRequirements R, LoopVectorizeHints H, DemandedBits DB, AssumptionCache AC)

bool	canVectorize (bool UseVPlanNativePath)
	Returns true if it is legal to vectorize this loop. More...

bool	canFoldTailByMasking ()
	Return true if we can vectorize this loop while folding its tail by masking. More...

PHINode *	getPrimaryInduction ()
	Returns the primary induction variable. More...

ReductionList *	getReductionVars ()
	Returns the reduction variables found in the loop. More...

InductionList *	getInductionVars ()
	Returns the induction variables found in the loop. More...

RecurrenceSet *	getFirstOrderRecurrences ()
	Return the first-order recurrences found in the loop. More...

DenseMap< Instruction , Instruction > &	getSinkAfter ()
	Return the set of instructions to sink to handle first-order recurrences. More...

Type *	getWidestInductionType ()
	Returns the widest induction type. More...

bool	isInductionPhi (const Value *V)
	Returns True if V is a Phi node of an induction variable in this loop. More...

bool	isCastedInductionVariable (const Value *V)
	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). More...

bool	isInductionVariable (const Value *V)
	Returns True if V can be considered as an induction variable in this loop. More...

bool	isReductionVariable (PHINode *PN)
	Returns True if PN is a reduction variable in this loop. More...

bool	isFirstOrderRecurrence (const PHINode *Phi)
	Returns True if Phi is a first-order recurrence in this loop. More...

bool	blockNeedsPredication (BasicBlock *BB)
	Return true if the block BB needs to be predicated in order for the loop to be vectorized. More...

int	isConsecutivePtr (Value *Ptr)
	Check if this pointer is consecutive when vectorizing. More...

bool	isUniform (Value *V)
	Returns true if the value V is uniform within the loop. More...

const RuntimePointerChecking *	getRuntimePointerChecking () const
	Returns the information that we collected about runtime memory check. More...

const LoopAccessInfo *	getLAI () const

unsigned	getMaxSafeDepDistBytes ()

uint64_t	getMaxSafeRegisterWidth () const

bool	hasStride (Value *V)

bool	isMaskRequired (const Instruction *I)
	Returns true if vector representation of the instruction `I` requires mask. More...

unsigned	getNumStores () const

unsigned	getNumLoads () const

bool	hasFunNoNaNAttr () const

Detailed Description

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:

Memory checks - The code in canVectorizeMemory checks if vectorization will change the order of memory accesses in a way that will change the correctness of the program.
Scalars checks - The code in canVectorizeInstrs and canVectorizeMemory checks for a number of different conditions, such as the availability of a single induction variable, that all types are supported and vectorize-able, etc. This code reflects the capabilities of InnerLoopVectorizer. This class is also used by InnerLoopVectorizer for identifying induction variable and the different reduction variables.

Definition at line 218 of file LoopVectorizationLegality.h.

Member Typedef Documentation

◆ InductionList

using llvm::LoopVectorizationLegality::InductionList = MapVector<PHINode *, InductionDescriptor>

InductionList saves induction variables and maps them to the induction descriptor.

Definition at line 235 of file LoopVectorizationLegality.h.

◆ RecurrenceSet

using llvm::LoopVectorizationLegality::RecurrenceSet = SmallPtrSet<const PHINode *, 8>

RecurrenceSet contains the phi nodes that are recurrences other than inductions and reductions.

Definition at line 239 of file LoopVectorizationLegality.h.

◆ ReductionList

using llvm::LoopVectorizationLegality::ReductionList = DenseMap<PHINode *, RecurrenceDescriptor>

ReductionList contains the reduction descriptors for all of the reductions that were found in the loop.

Definition at line 231 of file LoopVectorizationLegality.h.

Constructor & Destructor Documentation

◆ LoopVectorizationLegality()

llvm::LoopVectorizationLegality::LoopVectorizationLegality	(	Loop *	L,
		PredicatedScalarEvolution &	PSE,
		DominatorTree *	DT,
		TargetLibraryInfo *	TLI,
		AliasAnalysis *	AA,
		Function *	F,
		std::function< const LoopAccessInfo &(Loop &)> *	GetLAA,
		LoopInfo *	LI,
		OptimizationRemarkEmitter *	ORE,
		LoopVectorizationRequirements *	R,
		LoopVectorizeHints *	H,
		DemandedBits *	DB,
		AssumptionCache *	AC
	)

inline

Definition at line 220 of file LoopVectorizationLegality.h.

Member Function Documentation

◆ blockNeedsPredication()

bool llvm::LoopVectorizationLegality::blockNeedsPredication ( BasicBlock * BB )

Return true if the block BB needs to be predicated in order for the loop to be vectorized.

Definition at line 877 of file LoopVectorizationLegality.cpp.

References assert(), llvm::LoopAccessInfo::blockNeedsPredication(), C, llvm::canIfConvertPHINodes(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), DEBUG_TYPE, llvm::dyn_cast(), llvm::LoopBase< BlockT, LoopT >::empty(), EnableIfConversion, llvm::LoopBase< BlockT, LoopT >::getExitingBlock(), llvm::getLoadStorePointerOperand(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::LoopBase< BlockT, LoopT >::getNumBackEdges(), llvm::BasicBlock::getTerminator(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), LLVM_DEBUG, and SI.

Referenced by llvm::LoopVectorizationCostModel::blockNeedsPredication(), llvm::LoopVectorizationCostModel::interleavedAccessCanBeWidened(), and llvm::LoopVectorizationCostModel::setCostBasedWideningDecision().

◆ canFoldTailByMasking()

bool llvm::LoopVectorizationLegality::canFoldTailByMasking ( )

Return true if we can vectorize this loop while folding its tail by masking.

Definition at line 1157 of file LoopVectorizationLegality.cpp.

References llvm::dbgs(), llvm::BasicBlock::getTerminator(), LLVM_DEBUG, and llvm::Value::users().

Referenced by llvm::LoopVectorizationCostModel::computeMaxVF().

◆ canVectorize()

bool llvm::LoopVectorizationLegality::canVectorize ( bool UseVPlanNativePath )

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 1065 of file LoopVectorizationLegality.cpp.

References assert(), llvm::dbgs(), DEBUG_TYPE, llvm::LoopVectorizeHints::FK_Enabled, LLVM_DEBUG, PragmaVectorizeSCEVCheckThreshold, and VectorizeSCEVCheckThreshold.

Referenced by llvm::LoopVectorizePass::processLoop().

◆ getFirstOrderRecurrences()

RecurrenceSet* llvm::LoopVectorizationLegality::getFirstOrderRecurrences ( )

inline

Return the first-order recurrences found in the loop.

Definition at line 264 of file LoopVectorizationLegality.h.

◆ getInductionVars()

InductionList* llvm::LoopVectorizationLegality::getInductionVars ( )

inline

Returns the induction variables found in the loop.

Definition at line 261 of file LoopVectorizationLegality.h.

Referenced by llvm::LoopVectorizationPlanner::collectTriviallyDeadInstructions(), llvm::LoopVectorizationCostModel::collectValuesToIgnore(), llvm::InnerLoopVectorizer::createVectorizedLoopSkeleton(), llvm::InnerLoopVectorizer::fixVectorizedLoop(), llvm::LoopVectorizationCostModel::memoryInstructionCanBeWidened(), llvm::VPRecipeBuilder::tryToCreateRecipe(), llvm::VPRecipeBuilder::tryToOptimizeInduction(), llvm::InnerLoopVectorizer::updateAnalysis(), llvm::InnerLoopVectorizer::widenIntOrFpInduction(), and llvm::InnerLoopVectorizer::widenPHIInstruction().

◆ getLAI()

const LoopAccessInfo* llvm::LoopVectorizationLegality::getLAI ( ) const

inline

Definition at line 315 of file LoopVectorizationLegality.h.

Referenced by llvm::LoopVectorizationCostModel::computeMaxVF(), llvm::InnerLoopVectorizer::emitMemRuntimeChecks(), llvm::LoopVectorizePass::processLoop(), and processLoopInVPlanNativePath().

◆ getMaxSafeDepDistBytes()

unsigned llvm::LoopVectorizationLegality::getMaxSafeDepDistBytes ( )

inline

Definition at line 317 of file LoopVectorizationLegality.h.

Referenced by llvm::LoopVectorizationCostModel::calculateRegisterUsage(), and llvm::LoopVectorizationCostModel::selectInterleaveCount().

◆ getMaxSafeRegisterWidth()

uint64_t llvm::LoopVectorizationLegality::getMaxSafeRegisterWidth ( ) const

inline

Definition at line 319 of file LoopVectorizationLegality.h.

Referenced by llvm::LoopVectorizationCostModel::computeMaxVF().

◆ getNumLoads()

unsigned llvm::LoopVectorizationLegality::getNumLoads ( ) const

inline

Definition at line 330 of file LoopVectorizationLegality.h.

Referenced by llvm::LoopVectorizationCostModel::selectInterleaveCount().

◆ getNumStores()

unsigned llvm::LoopVectorizationLegality::getNumStores ( ) const

inline

Definition at line 329 of file LoopVectorizationLegality.h.

Referenced by llvm::LoopVectorizationCostModel::selectInterleaveCount().

◆ getPrimaryInduction()

PHINode* llvm::LoopVectorizationLegality::getPrimaryInduction ( )

inline

Returns the primary induction variable.

Definition at line 255 of file LoopVectorizationLegality.h.

Referenced by llvm::VPRecipeBuilder::createBlockInMask(), llvm::InnerLoopVectorizer::createVectorizedLoopSkeleton(), llvm::LoopVectorizationCostModel::isOptimizableIVTruncate(), and llvm::VPRecipeBuilder::tryToCreateRecipe().

◆ getReductionVars()

ReductionList* llvm::LoopVectorizationLegality::getReductionVars ( )

inline

Returns the reduction variables found in the loop.

Definition at line 258 of file LoopVectorizationLegality.h.

Referenced by llvm::LoopVectorizationCostModel::collectValuesToIgnore(), llvm::InnerLoopVectorizer::fixReduction(), llvm::LoopVectorizationCostModel::getSmallestAndWidestTypes(), and llvm::LoopVectorizationCostModel::selectInterleaveCount().

◆ getRuntimePointerChecking()

const RuntimePointerChecking* llvm::LoopVectorizationLegality::getRuntimePointerChecking ( ) const

inline

Returns the information that we collected about runtime memory check.

Definition at line 311 of file LoopVectorizationLegality.h.

Referenced by llvm::LoopVectorizationCostModel::computeMaxVF(), and llvm::LoopVectorizationCostModel::selectInterleaveCount().

◆ getSinkAfter()

DenseMap<Instruction *, Instruction *>& llvm::LoopVectorizationLegality::getSinkAfter ( )

inline

Return the set of instructions to sink to handle first-order recurrences.

Definition at line 267 of file LoopVectorizationLegality.h.

Referenced by llvm::VPRecipeBuilder::tryToCreateRecipe().

◆ getWidestInductionType()

Type* llvm::LoopVectorizationLegality::getWidestInductionType ( )

inline

Returns the widest induction type.

Definition at line 270 of file LoopVectorizationLegality.h.

Referenced by llvm::InnerLoopVectorizer::createVectorizedLoopSkeleton(), and llvm::InnerLoopVectorizer::getOrCreateTripCount().

◆ hasFunNoNaNAttr()

bool llvm::LoopVectorizationLegality::hasFunNoNaNAttr ( ) const

inline

Definition at line 333 of file LoopVectorizationLegality.h.

References llvm::createLVMissedAnalysis(), and I.

Referenced by llvm::InnerLoopVectorizer::fixReduction().

◆ hasStride()

bool llvm::LoopVectorizationLegality::hasStride ( Value * V )

inline

Definition at line 323 of file LoopVectorizationLegality.h.

Referenced by llvm::InnerLoopVectorizer::getOrCreateVectorValue(), and isStrideMul().

◆ isCastedInductionVariable()

bool llvm::LoopVectorizationLegality::isCastedInductionVariable ( const Value * V )

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 864 of file LoopVectorizationLegality.cpp.

References llvm::dyn_cast().

◆ isConsecutivePtr()

int llvm::LoopVectorizationLegality::isConsecutivePtr ( Value * Ptr )

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 llvm::getPtrStride().

Referenced by llvm::createLoopVectorizePass(), llvm::LoopVectorizationCostModel::isLegalMaskedLoad(), llvm::LoopVectorizationCostModel::isLegalMaskedStore(), isStrideMul(), llvm::LoopVectorizationCostModel::memoryInstructionCanBeWidened(), and llvm::LoopVectorizationCostModel::setCostBasedWideningDecision().