#include "llvm/Transforms/Vectorize/LoopVectorize.h"
#include "LoopVectorizationPlanner.h"
#include "VPRecipeBuilder.h"
#include "VPlan.h"
#include "VPlanAnalysis.h"
#include "VPlanCFG.h"
#include "VPlanHelpers.h"
#include "VPlanPatternMatch.h"
#include "VPlanTransforms.h"
#include "VPlanUtils.h"
#include "VPlanVerifier.h"
#include "VectorizeOptions.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/Hashing.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/Twine.h"
#include "llvm/ADT/TypeSwitch.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/BasicAliasAnalysis.h"
#include "llvm/Analysis/BlockFrequencyInfo.h"
#include "llvm/Analysis/BranchProbabilityInfo.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/CodeMetrics.h"
#include "llvm/Analysis/CycleAnalysis.h"
#include "llvm/Analysis/DemandedBits.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/LoopAccessAnalysis.h"
#include "llvm/Analysis/LoopAnalysisManager.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ProfileSummaryInfo.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/ScalarEvolutionPatternMatch.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Analysis/VectorUtils.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DebugInfo.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/ProfDataUtils.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/Verifier.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/InstructionCost.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/NativeFormatting.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/InjectTLIMappings.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopSimplify.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/LoopVersioning.h"
#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
#include "llvm/Transforms/Utils/SizeOpts.h"
#include "llvm/Transforms/Vectorize/LoopVectorizationLegality.h"
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <functional>
#include <iterator>
#include <memory>
#include <string>
#include <tuple>
#include <utility>

Classes
class	llvm::LoopVectorizationCostModel
	LoopVectorizationCostModel - estimates the expected speedups due to vectorization. More...
struct	MainPlanResumeMarkers
	ResumeForEpilogue markers in the main plan, used by the epilogue plan. More...

Namespaces
namespace	llvm
	This is an optimization pass for GlobalISel generic memory operations.

Macros
#define	LV_NAME "loop-vectorize"
#define	DEBUG_TYPE LV_NAME

Enumerations
enum	llvm::EpilogueLowering { llvm::CM_EpilogueAllowed , llvm::CM_EpilogueNotAllowedOptSize , llvm::CM_EpilogueNotAllowedLowTripLoop , llvm::CM_EpilogueNotNeededFoldTail , llvm::CM_EpilogueNotAllowedFoldTail }
enum class	llvm::AliasMaskingStatus { llvm::NotDecided , llvm::Disabled , llvm::Enabled }

Functions
	STATISTIC (LoopsVectorized, "Number of loops vectorized")
	STATISTIC (LoopsAnalyzed, "Number of loops analyzed for vectorization")
	STATISTIC (LoopsEpilogueVectorized, "Number of epilogues vectorized")
	STATISTIC (LoopsEarlyExitVectorized, "Number of early exit loops vectorized")
	STATISTIC (LoopsPartialAliasVectorized, "Number of partial aliasing loops vectorized")
static bool	hasForcedEpilogueVF ()
static ElementCount	getSmallConstantTripCount (ScalarEvolution SE, const Loop L)
	A version of ScalarEvolution::getSmallConstantTripCount that returns an ElementCount to include loops whose trip count is a function of vscale.
static unsigned	getMaxTCFromNonZeroRange (PredicatedScalarEvolution &PSE, Loop *L)
	Get the maximum trip count for `L` from the SCEV unsigned range, excluding zero from the range.
static std::optional< ElementCount >	getSmallBestKnownTC (const VectorizeOptions &Opts, PredicatedScalarEvolution &PSE, Loop *L, bool CanUseConstantMax=true, bool CanExcludeZeroTrips=false, bool ComputeUpperBoundOnly=false)
	Returns "best known" trip count, which is either a valid positive trip count or std::nullopt when an estimate cannot be made (including when the trip count would overflow), for the specified loop `L` as defined by the following procedure: 1) Returns exact trip count if it is known.
static DebugLoc	getDebugLocFromInstOrOperands (Instruction *I)
	Look for a meaningful debug location on the instruction or its operands.
Value *	llvm::getRuntimeVF (IRBuilderBase &B, Type *Ty, ElementCount VF)
	Return the runtime value for VF.
static bool	useActiveLaneMask (TailFoldingStyle Style)
static bool	useActiveLaneMaskForControlFlow (TailFoldingStyle Style)
static bool	isExplicitVecOuterLoop (const VectorizeOptions &Opts, Loop OuterLp, OptimizationRemarkEmitter ORE)
static void	collectSupportedLoops (const VectorizeOptions &Opts, Loop &L, LoopInfo LI, OptimizationRemarkEmitter ORE, SmallVectorImpl< Loop * > &V)
static bool	isIndvarOverflowCheckKnownFalse (const VectorizeOptions &Opts, const LoopVectorizationCostModel *Cost, ElementCount VF, std::optional< unsigned > UF=std::nullopt)
	For the given VF and UF and maximum trip count computed for the loop, return whether the induction variable might overflow in the vectorized loop.
static bool	useMaskedInterleavedAccesses (const VectorizeOptions &Opts, const TargetTransformInfo &TTI)
static VPIRBasicBlock *	replaceVPBBWithIRVPBB (VPBasicBlock VPBB, BasicBlock IRBB, VPlan *Plan=nullptr)
	Replace `VPBB` with a VPIRBasicBlock wrapping `IRBB`.
static void	addFullyUnrolledInstructionsToIgnore (Loop L, const LoopVectorizationLegality::InductionList &IL, SmallPtrSetImpl< Instruction > &InstsToIgnore)
	Knowing that loop `L` executes a single vector iteration, add instructions that will get simplified and thus should not have any cost to `InstsToIgnore`.
static void	legacyCSE (BasicBlock *BB)
	FIXME: This legacy common-subexpression-elimination routine is scheduled for removal, in favor of the VPlan-based one.
static unsigned	estimateElementCount (ElementCount VF, std::optional< unsigned > VScale)
	This function attempts to return a value that represents the ElementCount at runtime.
static Function *	getVectorLibraryVariantFor (const CallInst &CI, ElementCount VF, bool MaskRequired, const TargetLibraryInfo *TLI)
	Returns the vector library variant function of `CI` usable at `VF`, respecting `MaskRequired`, or nullptr if none is found: a mapping with matching VF, masked if required, whose vector function is declared in the module.
static bool	hasVectorLibraryVariantFor (const CallInst &CI, ElementCount VF, bool MaskRequired, const TargetLibraryInfo *TLI)
	Returns true iff `CI` has a library vector variant usable at `VF`.
static Type *	maybeVectorizeType (Type *Ty, ElementCount VF)
static Intrinsic::ID	getMaskedDivRemIntrinsic (unsigned Opcode)
static bool	willGenerateVectors (VPlan &Plan, ElementCount VF, const TargetTransformInfo &TTI)
	Check if any recipe of `Plan` will generate a vector value, which will be assigned a vector register.
static bool	hasReplicatorRegion (VPlan &Plan)
static bool	hasFindLastReductionPhi (VPlan &Plan)
	Returns true if the VPlan contains a VPReductionPHIRecipe with FindLast recurrence kind.
static bool	hasConditionalInductionPhi (VPlan &Plan)
	Returns true if the VPlan contains a VPConditionalInductionPHIRecipe.
static EpilogueLowering	getEpilogueTailLowering (const VectorizeOptions &Opts, const LoopVectorizationCostModel &MainCM, const Loop L, OptimizationRemarkEmitter ORE, LoopVectorizationLegality &LVL, const LoopVectorizeHints &Hints, const TargetTransformInfo *TTI)
	Determine how to lower the epilogue for the vector epilogue loop.
static const SCEV *	getAddressAccessSCEV (Value Ptr, PredicatedScalarEvolution &PSE, const Loop TheLoop)
	Gets the address access SCEV for Ptr, if it should be used for cost modeling according to isAddressSCEVForCost.
static std::optional< VPExecutionFrequency >	getRecordedExecutionFrequency (const VPBasicBlock *VPBB)
	Returns the frequency with which `VPBB` executes, as recorded on its recipes.
static void	printOptimizedVPlan (VPlan &)
static bool	verifyExecutionFrequenciesMatchBFI (VPlan &Plan, Loop OrigLoop, LoopInfo LI, LoopVectorizationCostModel &CM)
	Cross-check the execution frequencies recorded in `Plan` against BlockFrequencyInfo for the blocks of `OrigLoop`.
static EpilogueLowering	getEpilogueLowering (const VectorizeOptions &Opts, Function F, Loop L, LoopVectorizeHints &Hints, bool OptForSize, TargetTransformInfo TTI, TargetLibraryInfo TLI, LoopVectorizationLegality &LVL, InterleavedAccessInfo *IAI)
static void	checkMixedPrecision (Loop L, OptimizationRemarkEmitter ORE)
static InstructionCost	calculateEarlyExitCost (VPCostContext &CostCtx, VPlan &Plan, ElementCount VF)
	For loops with uncountable early exits, find the cost of doing work when exiting the loop early, such as calculating the final exit values of variables used outside the loop.
static bool	isOutsideLoopWorkProfitable (GeneratedRTChecks &Checks, VectorizationFactor &VF, Loop *L, PredicatedScalarEvolution &PSE, VPCostContext &CostCtx, VPlan &Plan, EpilogueLowering SEL, std::optional< unsigned > VScale)
	This function determines whether or not it's still profitable to vectorize the loop given the extra work we have to do outside of the loop:
static MainPlanResumeMarkers	preparePlanForMainVectorLoop (VPlan &MainPlan)
	Prepare `MainPlan` for vectorizing the main vector loop during epilogue vectorization.
static void	preparePlanForEpilogueVectorLoop (VPlan &MainPlan, VPlan &Plan, const SCEV2ValueTy &ExpandedSCEVs, ElementCount MainLoopVF, unsigned MainLoopUF, ElementCount EpilogueVF, VFSelectionContext &Config, ScalarEvolution &SE, const MainPlanResumeMarkers &Markers, VPBasicBlock *MainCheck)
	Prepare `Plan` for vectorizing the epilogue loop.

Variables
const char	VerboseDebug [] = DEBUG_TYPE "-verbose"
static cl::opt< ElementCount >	EpilogueVectorizationForceVF ("epilogue-vectorization-force-VF", cl::init(ElementCount::getFixed(1)), cl::Hidden, cl::desc("When epilogue vectorization is enabled, and a value greater than " "1 is specified, forces the given VF for all applicable epilogue " "loops. Note: This allows all scalable VFs >= vscale x 1."))
static constexpr uint32_t	MinItersBypassWeights [] = {1, 127}

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE LV_NAME

Definition at line 166 of file LoopVectorize.cpp.

◆ LV_NAME

#define LV_NAME "loop-vectorize"

Definition at line 165 of file LoopVectorize.cpp.

Function Documentation

◆ addFullyUnrolledInstructionsToIgnore()

void addFullyUnrolledInstructionsToIgnore	(	Loop *	L,
		const LoopVectorizationLegality::InductionList &	IL,
		SmallPtrSetImpl< Instruction * > &	InstsToIgnore )

static

Knowing that loop L executes a single vector iteration, add instructions that will get simplified and thus should not have any cost to InstsToIgnore.

Definition at line 1571 of file LoopVectorize.cpp.

References llvm::all_of(), llvm::cast(), llvm::SmallPtrSetImpl< PtrType >::insert(), IV, llvm::MapVector< KeyT, ValueT, MapType, VectorType, N >::keys(), and llvm::Instruction::users().

◆ calculateEarlyExitCost()

InstructionCost calculateEarlyExitCost	(	VPCostContext &	CostCtx,
		VPlan &	Plan,
		ElementCount	VF )

static

For loops with uncountable early exits, find the cost of doing work when exiting the loop early, such as calculating the final exit values of variables used outside the loop.

TODO: This is currently overly pessimistic because the loop may not take the early exit, but better to keep this conservative for now. In future, it might be possible to relax this by using branch probabilities.

Definition at line 6947 of file LoopVectorize.cpp.

References llvm::dbgs(), llvm::VPlan::getExitBlocks(), llvm::VPlan::getMiddleBlock(), and LLVM_DEBUG.

Referenced by isOutsideLoopWorkProfitable().

◆ checkMixedPrecision()

void checkMixedPrecision	(	Loop *	L,
		OptimizationRemarkEmitter *	ORE )

static

Definition at line 6900 of file LoopVectorize.cpp.

References llvm::dyn_cast(), llvm::OptimizationRemarkEmitter::emit(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::isa(), LV_NAME, llvm::SmallVectorImpl< T >::pop_back_val(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

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

◆ collectSupportedLoops()

void collectSupportedLoops	(	const VectorizeOptions &	Opts,
		Loop &	L,
		LoopInfo *	LI,
		OptimizationRemarkEmitter *	ORE,
		SmallVectorImpl< Loop * > &	V )

static

Definition at line 1464 of file LoopVectorize.cpp.

References collectSupportedLoops(), llvm::containsIrreducibleCFG(), isExplicitVecOuterLoop(), llvm::LoopBlocksRPO::perform(), and V.

Referenced by collectSupportedLoops(), and llvm::LoopVectorizePass::runImpl().

◆ estimateElementCount()

unsigned estimateElementCount	(	ElementCount	VF,
		std::optional< unsigned >	VScale )

static

This function attempts to return a value that represents the ElementCount at runtime.

For fixed-width VFs we know this precisely at compile time, but for scalable VFs we calculate it based on an estimate of the vscale value.

Definition at line 1637 of file LoopVectorize.cpp.

References assert(), llvm::details::FixedOrScalableQuantity< LeafTy, ValueTy >::getKnownMinValue(), and llvm::details::FixedOrScalableQuantity< LeafTy, ValueTy >::isScalable().

Referenced by llvm::LoopVectorizationPlanner::executePlan(), llvm::VFSelectionContext::isEpilogueVectorizationProfitable(), isOutsideLoopWorkProfitable(), llvm::LoopVectorizationPlanner::selectBestEpiloguePlan(), and llvm::LoopVectorizationPlanner::selectInterleaveCount().

◆ getAddressAccessSCEV()

const SCEV * getAddressAccessSCEV	(	Value *	Ptr,
		PredicatedScalarEvolution &	PSE,
		const Loop *	TheLoop )

static

Gets the address access SCEV for Ptr, if it should be used for cost modeling according to isAddressSCEVForCost.

This SCEV can be sent to the Target in order to estimate the address calculation cost.

Definition at line 3926 of file LoopVectorize.cpp.

References llvm::PredicatedScalarEvolution::getSCEV(), llvm::PredicatedScalarEvolution::getSE(), and llvm::vputils::isAddressSCEVForCost().

Referenced by llvm::VPReplicateRecipe::computeCost().

◆ getDebugLocFromInstOrOperands()

DebugLoc getDebugLocFromInstOrOperands ( Instruction * I )

static

Look for a meaningful debug location on the instruction or its operands.

Definition at line 296 of file LoopVectorize.cpp.

References DenseMapInfo< LocallyHashedType >::Empty, llvm::dyn_cast(), llvm::DebugLoc::getUnknown(), and I.

◆ getEpilogueLowering()

EpilogueLowering getEpilogueLowering	(	const VectorizeOptions &	Opts,
		Function *	F,
		Loop *	L,
		LoopVectorizeHints &	Hints,
		bool	OptForSize,
		TargetTransformInfo *	TTI,
		TargetLibraryInfo *	TLI,
		LoopVectorizationLegality &	LVL,
		InterleavedAccessInfo *	IAI )

static

Definition at line 6857 of file LoopVectorize.cpp.

References llvm::CM_EpilogueAllowed, llvm::CM_EpilogueNotAllowedFoldTail, llvm::CM_EpilogueNotAllowedOptSize, llvm::CM_EpilogueNotNeededFoldTail, F, llvm::LoopVectorizeHints::FK_Disabled, llvm::LoopVectorizeHints::FK_Enabled, llvm::LoopVectorizeHints::getForce(), llvm::LoopVectorizeHints::getPredicate(), llvm::MustFoldTail, llvm::None, llvm::PreferFoldTail, and TLI.

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

◆ getEpilogueTailLowering()

EpilogueLowering getEpilogueTailLowering	(	const VectorizeOptions &	Opts,
		const LoopVectorizationCostModel &	MainCM,
		const Loop *	L,
		OptimizationRemarkEmitter *	ORE,
		LoopVectorizationLegality &	LVL,
		const LoopVectorizeHints &	Hints,
		const TargetTransformInfo *	TTI )

static

Determine how to lower the epilogue for the vector epilogue loop.

Check if there are any conflicts that prevent tail-folding the epilogue.

Returns: CM_EpilogueNotNeededFoldTail if epilogue tail-folding is possible, otherwise CM_EpilogueAllowed.

Definition at line 2992 of file LoopVectorize.cpp.

References llvm::CM_EpilogueAllowed, llvm::CM_EpilogueNotNeededFoldTail, llvm::DataWithEVL, llvm::MapVector< KeyT, ValueT, MapType, VectorType, N >::empty(), llvm::SmallPtrSetImplBase::empty(), EpilogueVectorizationForceVF, llvm::LoopVectorizationLegality::getFixedOrderRecurrences(), llvm::LoopVectorizationLegality::getReductionVars(), llvm::LoopVectorizeHints::getWidth(), hasForcedEpilogueVF(), llvm::InterleavedAccessInfo::hasGroups(), llvm::LoopVectorizationLegality::hasUncountableEarlyExit(), llvm::LoopVectorizationCostModel::InterleaveInfo, llvm::LoopVectorizationCostModel::isEpilogueAllowed(), llvm::details::FixedOrScalableQuantity< ElementCount, unsigned >::isKnownLE(), llvm::PreferFoldTail, llvm::LoopVectorizationUtils::reportVectorizationInfo(), llvm::LoopVectorizationCostModel::requiresScalarEpilogue(), and useMaskedInterleavedAccesses().

◆ getMaskedDivRemIntrinsic()

Intrinsic::ID getMaskedDivRemIntrinsic ( unsigned Opcode )

static

Definition at line 2056 of file LoopVectorize.cpp.

References llvm_unreachable.

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

◆ getMaxTCFromNonZeroRange()

unsigned getMaxTCFromNonZeroRange	(	PredicatedScalarEvolution &	PSE,
		Loop *	L )

static

Get the maximum trip count for L from the SCEV unsigned range, excluding zero from the range.

Only valid when not folding the tail, as the minimum iteration count check guards against a zero trip count. Returns 0 if unknown.

Definition at line 225 of file LoopVectorize.cpp.

References llvm::ScalarEvolution::applyLoopGuards(), llvm::APInt::getActiveBits(), llvm::PredicatedScalarEvolution::getBackedgeTakenCount(), llvm::PredicatedScalarEvolution::getSE(), llvm::ScalarEvolution::getTripCountFromExitCount(), llvm::SCEV::getType(), llvm::ConstantRange::getUnsignedMax(), llvm::ScalarEvolution::getUnsignedRange(), llvm::APInt::getZExtValue(), llvm::isa(), and llvm::APInt::isZero().

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

◆ getRecordedExecutionFrequency()

std::optional< VPExecutionFrequency > getRecordedExecutionFrequency ( const VPBasicBlock * VPBB )

static

Returns the frequency with which VPBB executes, as recorded on its recipes.

All recipes of a block share the same frequency.

Definition at line 5376 of file LoopVectorize.cpp.

References llvm::cast(), llvm::VPBasicBlock::empty(), and llvm::VPBasicBlock::front().

Referenced by verifyExecutionFrequenciesMatchBFI().

◆ getSmallBestKnownTC()

std::optional< ElementCount > getSmallBestKnownTC	(	const VectorizeOptions &	Opts,
		PredicatedScalarEvolution &	PSE,
		Loop *	L,
		bool	CanUseConstantMax = true,
		bool	CanExcludeZeroTrips = false,
		bool	ComputeUpperBoundOnly = false )

static

Returns "best known" trip count, which is either a valid positive trip count or std::nullopt when an estimate cannot be made (including when the trip count would overflow), for the specified loop L as defined by the following procedure: 1) Returns exact trip count if it is known.

2) Returns expected trip count according to profile data if any. 3) Returns upper bound estimate if known, if CanUseConstantMax, and if ComputeUpperBoundOnly is false. 4) Returns the maximum trip count from the SCEV range excluding zero, if CanUseConstantMax and CanExcludeZeroTrips. 5) Returns std::nullopt if all of the above failed.

Definition at line 251 of file LoopVectorize.cpp.

References llvm::ElementCount::getFixed(), llvm::getLoopEstimatedTripCount(), getMaxTCFromNonZeroRange(), llvm::PredicatedScalarEvolution::getSE(), llvm::PredicatedScalarEvolution::getSmallConstantMaxTripCount(), and getSmallConstantTripCount().

Referenced by llvm::LoopVectorizationCostModel::computeMaxVF(), isIndvarOverflowCheckKnownFalse(), isOutsideLoopWorkProfitable(), llvm::LoopVectorizePass::processLoop(), and llvm::LoopVectorizationPlanner::selectInterleaveCount().

◆ getSmallConstantTripCount()

ElementCount getSmallConstantTripCount	(	ScalarEvolution *	SE,
		const Loop *	L )

static

A version of ScalarEvolution::getSmallConstantTripCount that returns an ElementCount to include loops whose trip count is a function of vscale.

Definition at line 199 of file LoopVectorize.cpp.

References llvm::cast(), llvm::APInt::getActiveBits(), llvm::ScalarEvolution::getBackedgeTakenCount(), llvm::ElementCount::getFixed(), llvm::ElementCount::getScalable(), llvm::ScalarEvolution::getSmallConstantTripCount(), llvm::ScalarEvolution::getTripCountFromExitCount(), llvm::SCEV::getType(), llvm::APInt::getZExtValue(), hasNoUnsignedWrap(), llvm::isa(), llvm::SCEVPatternMatch::m_scev_APInt(), llvm::SCEVPatternMatch::m_scev_Mul(), llvm::SCEVPatternMatch::m_SCEVVScale(), and llvm::SCEVPatternMatch::match().

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

◆ getVectorLibraryVariantFor()

Function * getVectorLibraryVariantFor	(	const CallInst &	CI,
		ElementCount	VF,
		bool	MaskRequired,
		const TargetLibraryInfo *	TLI )

static

Returns the vector library variant function of CI usable at VF, respecting MaskRequired, or nullptr if none is found: a mapping with matching VF, masked if required, whose vector function is declared in the module.

Definition at line 1651 of file LoopVectorize.cpp.

References F, llvm::Module::getFunction(), llvm::VFDatabase::getMappings(), llvm::Instruction::getModule(), llvm::CallBase::isNoBuiltin(), and TLI.

Referenced by llvm::LoopVectorizationCostModel::getVectorCallCost(), and hasVectorLibraryVariantFor().

◆ hasConditionalInductionPhi()

bool hasConditionalInductionPhi ( VPlan & Plan )

static

Returns true if the VPlan contains a VPConditionalInductionPHIRecipe.

Definition at line 2983 of file LoopVectorize.cpp.

References llvm::any_of(), llvm::VPBlockBase::getEntryBasicBlock(), llvm::VPlan::getVectorLoopRegion(), llvm::IsaPred, and llvm::VPBasicBlock::phis().

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

◆ hasFindLastReductionPhi()

bool hasFindLastReductionPhi ( VPlan & Plan )

static

Returns true if the VPlan contains a VPReductionPHIRecipe with FindLast recurrence kind.

Definition at line 2973 of file LoopVectorize.cpp.

References llvm::any_of(), llvm::VPBlockBase::getEntryBasicBlock(), llvm::VPlan::getVectorLoopRegion(), llvm::make_isa_range(), and llvm::VPBasicBlock::phis().

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

◆ hasForcedEpilogueVF()

bool hasForcedEpilogueVF ( )

static

Definition at line 188 of file LoopVectorize.cpp.

References EpilogueVectorizationForceVF, and llvm::ElementCount::getFixed().

Referenced by llvm::LoopVectorizationPlanner::computeBestVF(), getEpilogueTailLowering(), and llvm::LoopVectorizationPlanner::selectBestEpiloguePlan().

◆ hasReplicatorRegion()

bool hasReplicatorRegion ( VPlan & Plan )

static

Definition at line 2965 of file LoopVectorize.cpp.

References llvm::any_of(), llvm::VPBlockUtils::blocksOnly(), llvm::VPRegionBlock::getEntry(), llvm::VPlan::getVectorLoopRegion(), and llvm::vp_depth_first_shallow().

Referenced by llvm::LoopVectorizationPlanner::computeBestVF(), and llvm::LoopVectorizationPlanner::selectInterleaveCount().

◆ hasVectorLibraryVariantFor()

bool hasVectorLibraryVariantFor	(	const CallInst &	CI,
		ElementCount	VF,
		bool	MaskRequired,
		const TargetLibraryInfo *	TLI )

static

Returns true iff CI has a library vector variant usable at VF.

Definition at line 1664 of file LoopVectorize.cpp.

References getVectorLibraryVariantFor(), and TLI.

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

◆ isExplicitVecOuterLoop()

bool isExplicitVecOuterLoop	(	const VectorizeOptions &	Opts,
		Loop *	OuterLp,
		OptimizationRemarkEmitter *	ORE )

static

Definition at line 1438 of file LoopVectorize.cpp.

References llvm::LoopVectorizeHints::allowVectorization(), assert(), llvm::dbgs(), llvm::LoopVectorizeHints::emitRemarkWithHints(), llvm::LoopVectorizeHints::FK_Undefined, llvm::LoopVectorizeHints::getForce(), llvm::LoopVectorizeHints::getInterleave(), llvm::LoopBase< BlockT, LoopT >::isInnermost(), and LLVM_DEBUG.

Referenced by collectSupportedLoops().

◆ isIndvarOverflowCheckKnownFalse()

bool isIndvarOverflowCheckKnownFalse	(	const VectorizeOptions &	Opts,
		const LoopVectorizationCostModel *	Cost,
		ElementCount	VF,
		std::optional< unsigned >	UF = std::nullopt )

static

For the given VF and UF and maximum trip count computed for the loop, return whether the induction variable might overflow in the vectorized loop.

If not, then we know a runtime overflow check always evaluates to false and can be removed.

Definition at line 1498 of file LoopVectorize.cpp.

References llvm::IntegerType::getMask(), llvm::getMaxRuntimeElementCount(), getSmallBestKnownTC(), uint64_t, and llvm::APInt::ult().

◆ isOutsideLoopWorkProfitable()

bool isOutsideLoopWorkProfitable	(	GeneratedRTChecks &	Checks,
		VectorizationFactor &	VF,
		Loop *	L,
		PredicatedScalarEvolution &	PSE,
		VPCostContext &	CostCtx,
		VPlan &	Plan,
		EpilogueLowering	SEL,
		std::optional< unsigned >	VScale )

static

This function determines whether or not it's still profitable to vectorize the loop given the extra work we have to do outside of the loop:

Perform the runtime checks before entering the loop to ensure it's safe to vectorize.
In the case of loops with uncountable early exits, we may have to do extra work when exiting the loop early, such as calculating the final exit values of variables used outside the loop.
The middle block.

Definition at line 6973 of file LoopVectorize.cpp.

References llvm::alignTo(), calculateEarlyExitCost(), llvm::CM_EpilogueAllowed, llvm::VectorizationFactor::Cost, llvm::VPBasicBlock::cost(), llvm::dbgs(), llvm::divideCeil(), estimateElementCount(), llvm::ElementCount::getFixed(), llvm::VPlan::getMiddleBlock(), getSmallBestKnownTC(), llvm::InstructionCost::getValue(), llvm::details::FixedOrScalableQuantity< ElementCount, unsigned >::isKnownLT(), llvm::ElementCount::isScalar(), llvm::InstructionCost::isValid(), LLVM_DEBUG, llvm::VectorizationFactor::MinProfitableTripCount, llvm::VPCostContext::Opts, llvm::VectorizationFactor::ScalarCost, uint64_t, llvm::VectorizerParams::VectorizeMemoryCheckThreshold, and llvm::VectorizationFactor::Width.

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

◆ legacyCSE()

void legacyCSE ( BasicBlock * BB )

static

FIXME: This legacy common-subexpression-elimination routine is scheduled for removal, in favor of the VPlan-based one.

Definition at line 1614 of file LoopVectorize.cpp.

References llvm::DenseMapBase< StorageT, KeyT, ValueT, KeyInfoT, BucketT >::lookup(), llvm::make_early_inc_range(), and V.

Referenced by llvm::LoopVectorizationPlanner::executePlan().

◆ maybeVectorizeType()

Type * maybeVectorizeType	(	Type *	Ty,
		ElementCount	VF )

static

Definition at line 1703 of file LoopVectorize.cpp.

References llvm::canVectorizeTy(), llvm::ElementCount::isScalar(), and llvm::toVectorizedTy().

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

◆ preparePlanForEpilogueVectorLoop()

void preparePlanForEpilogueVectorLoop	(	VPlan &	MainPlan,
		VPlan &	Plan,
		const SCEV2ValueTy &	ExpandedSCEVs,
		ElementCount	MainLoopVF,
		unsigned	MainLoopUF,
		ElementCount	EpilogueVF,
		VFSelectionContext &	Config,
		ScalarEvolution &	SE,
		const MainPlanResumeMarkers &	Markers,
		VPBasicBlock *	MainCheck )

static

Prepare Plan for vectorizing the epilogue loop.

That is, re-use expanded SCEVs from ExpandedSCEVs and set resume values for header recipes.

Definition at line 7155 of file LoopVectorize.cpp.

References llvm::all_of(), assert(), llvm::cast(), llvm::VPBuilderBase< InserterTy >::createScalarPhi(), llvm::dyn_cast(), llvm::VPRegionBlock::getCanonicalIV(), llvm::VPBlockBase::getEntryBasicBlock(), llvm::VPBasicBlock::getFirstNonPhi(), llvm::VPBlockBase::getNumPredecessors(), llvm::VPUser::getOperand(), llvm::VPlan::getOrAddLiveIn(), llvm::VPBlockBase::getPredecessors(), llvm::VPlan::getScalarHeader(), llvm::VPValue::getUnderlyingValue(), llvm::VPlan::getVectorLoopRegion(), llvm::VPlan::getVectorPreheader(), llvm::VPlan::hasTailFolded(), IV, Markers, llvm::VPlanTransforms::modelGeneratedMainLoopBlocks(), Opc, llvm::VPBasicBlock::phis(), RUN_VPLAN_PASS, llvm::VPBlockBase::setName(), llvm::VPInstruction::WideActiveLaneMask, and llvm::zip_equal().

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

◆ preparePlanForMainVectorLoop()

MainPlanResumeMarkers preparePlanForMainVectorLoop ( VPlan & MainPlan )

static

Prepare MainPlan for vectorizing the main vector loop during epilogue vectorization.

Definition at line 7093 of file LoopVectorize.cpp.

References assert(), llvm::cast(), llvm::VPBuilderBase< InserterTy >::createNaryOp(), llvm::VPBasicBlock::end(), llvm::VPlan::getEntry(), llvm::VPBlockBase::getExitingBasicBlock(), llvm::VPBasicBlock::getFirstNonPhi(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::VPValue::getLiveInIRValue(), llvm::VPlan::getMiddleBlock(), llvm::VPlan::getScalarHeader(), llvm::VPlan::getScalarPreheader(), llvm::VPValue::getScalarType(), llvm::VPBasicBlock::getTerminator(), llvm::VPlan::getVectorLoopRegion(), llvm::VPlan::getZero(), llvm::IsaPred, llvm::isGuaranteedNotToBeUndefOrPoison(), llvm::VPlanPatternMatch::m_BranchOnCount(), llvm::VPlanPatternMatch::m_VPValue(), llvm::make_early_inc_range(), llvm::make_isa_range(), llvm::map_range(), llvm::PatternMatch::match(), llvm::VPlanPatternMatch::matchFindIVResult(), llvm::VPBasicBlock::phis(), llvm::VPValue::replaceUsesWithIf(), llvm::VPInstruction::ResumeForEpilogue, llvm::VPBuilderBase< InserterTy >::setInsertPoint(), llvm::VPUser::setOperand(), and llvm::to_vector().

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

◆ printOptimizedVPlan()

void printOptimizedVPlan ( VPlan & )

static

Definition at line 6120 of file LoopVectorize.cpp.

◆ replaceVPBBWithIRVPBB()

VPIRBasicBlock * replaceVPBBWithIRVPBB	(	VPBasicBlock *	VPBB,
		BasicBlock *	IRBB,
		VPlan *	Plan = nullptr )

static

Replace VPBB with a VPIRBasicBlock wrapping IRBB.

All recipes from VPBB are moved to the end of the newly created VPIRBasicBlock. All predecessors and successors of VPBB, if any, are rewired to the new VPIRBasicBlock. If VPBB may be unreachable, Plan must be passed.

Definition at line 1549 of file LoopVectorize.cpp.

References llvm::VPBasicBlock::begin(), llvm::VPBasicBlock::end(), llvm::VPBasicBlock::getFirstNonPhi(), llvm::VPBlockBase::getPlan(), llvm::make_early_inc_range(), llvm::make_range(), llvm::VPBasicBlock::phis(), and llvm::VPBlockUtils::reassociateBlocks().

Referenced by llvm::LoopVectorizationPlanner::executePlan().

◆ STATISTIC() [1/5]

STATISTIC	(	LoopsAnalyzed	,
		"Number of loops analyzed for vectorization"	)

◆ STATISTIC() [2/5]

STATISTIC	(	LoopsEarlyExitVectorized	,
		"Number of early exit loops vectorized"	)

◆ STATISTIC() [3/5]

STATISTIC	(	LoopsEpilogueVectorized	,
		"Number of epilogues vectorized"	)

◆ STATISTIC() [4/5]

STATISTIC	(	LoopsPartialAliasVectorized	,
		"Number of partial aliasing loops vectorized"	)

◆ STATISTIC() [5/5]

STATISTIC	(	LoopsVectorized	,
		"Number of loops vectorized"	)

◆ useActiveLaneMask()

bool useActiveLaneMask ( TailFoldingStyle Style )

static

Definition at line 1415 of file LoopVectorize.cpp.

References llvm::Data, and llvm::DataAndControlFlow.

◆ useActiveLaneMaskForControlFlow()

bool useActiveLaneMaskForControlFlow ( TailFoldingStyle Style )

static

Definition at line 1420 of file LoopVectorize.cpp.

References llvm::DataAndControlFlow.

◆ useMaskedInterleavedAccesses()

bool useMaskedInterleavedAccesses	(	const VectorizeOptions &	Opts,
		const TargetTransformInfo &	TTI )

static

Definition at line 1538 of file LoopVectorize.cpp.

References llvm::valueOr().

Referenced by llvm::LoopVectorizationCostModel::computeMaxVF(), getEpilogueTailLowering(), llvm::LoopVectorizationCostModel::interleavedAccessCanBeWidened(), llvm::LoopVectorizationPlanner::plan(), and llvm::LoopVectorizePass::processLoop().

◆ verifyExecutionFrequenciesMatchBFI()

bool verifyExecutionFrequenciesMatchBFI	(	VPlan &	Plan,
		Loop *	OrigLoop,
		LoopInfo *	LI,
		LoopVectorizationCostModel &	CM )

static

Cross-check the execution frequencies recorded in Plan against BlockFrequencyInfo for the blocks of OrigLoop.

FIXME: Temporary verification aid, to be removed.

Definition at line 6126 of file LoopVectorize.cpp.

References llvm::AbsoluteDifference(), assert(), BBFreq, llvm::drop_begin(), llvm::errs(), llvm::LoopVectorizationCostModel::getBFI(), llvm::BlockFrequencyInfo::getBlockFreq(), llvm::BranchProbability::getBranchProbability(), llvm::BranchProbability::getDenominator(), llvm::vputils::getExecutionProbability(), llvm::LoopBase< BlockT, LoopT >::getExitingBlock(), llvm::BlockFrequency::getFrequency(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getNumBlocks(), llvm::BranchProbability::getNumerator(), llvm::VPBlockUtils::getPlainCFGHeaderAndLatch(), getRecordedExecutionFrequency(), llvm::LoopBlocksRPO::perform(), llvm::SmallVectorTemplateCommon< T, typename >::size(), uint64_t, llvm::vp_rpo_plain_cfg_loop_body(), and llvm::zip_equal().

◆ willGenerateVectors()

bool willGenerateVectors	(	VPlan &	Plan,
		ElementCount	VF,
		const TargetTransformInfo &	TTI )

static

Check if any recipe of Plan will generate a vector value, which will be assigned a vector register.

Definition at line 2870 of file LoopVectorize.cpp.

References llvm::any_of(), assert(), llvm::VPBlockUtils::blocksOnly(), llvm::collectEphemeralRecipesForVPlan(), llvm::detail::DenseSetImpl< ValueT, MapTy >::contains(), llvm::getContainedTypes(), llvm::VPRegionBlock::getEntry(), llvm::details::FixedOrScalableQuantity< LeafTy, ValueTy >::getFixedValue(), llvm::details::FixedOrScalableQuantity< LeafTy, ValueTy >::getKnownMinValue(), llvm::VPValue::getScalarType(), llvm::VPlan::getVectorLoopRegion(), llvm::detail::DenseSetImpl< ValueT, MapTy >::insert(), llvm::isa(), llvm::details::FixedOrScalableQuantity< LeafTy, ValueTy >::isScalable(), llvm::ElementCount::isVector(), llvm_unreachable, llvm::toVectorizedTy(), and llvm::vp_depth_first_shallow().

Referenced by llvm::LoopVectorizationPlanner::computeBestVF().

Variable Documentation

◆ EpilogueVectorizationForceVF

cl::opt< ElementCount > EpilogueVectorizationForceVF("epilogue-vectorization-force-VF", cl::init(ElementCount::getFixed(1)), cl::Hidden, cl::desc("When epilogue vectorization is enabled, and a value greater than " "1 is specified, forces the given VF for all applicable epilogue " "loops. Note: This allows all scalable VFs >= vscale x 1."))	(	"epilogue-vectorization-force-VF"	,
		cl::init(ElementCount::getFixed(1))	,
		cl::Hidden	,
		cl::desc("When epilogue vectorization is enabled, and a value greater than " "1 is specified, forces the given VF for all applicable epilogue " "loops. Note: This allows all scalable VFs >= vscale x 1.")	)

static

Referenced by llvm::LoopVectorizationPlanner::computeBestVF(), getEpilogueTailLowering(), hasForcedEpilogueVF(), llvm::LoopVectorizationPlanner::plan(), and llvm::LoopVectorizationPlanner::selectBestEpiloguePlan().

◆ MinItersBypassWeights

uint32_t MinItersBypassWeights[] = {1, 127}

staticconstexpr

Definition at line 195 of file LoopVectorize.cpp.

Referenced by llvm::VPlanTransforms::addIterationCountCheckBlock(), llvm::LoopVectorizationPlanner::addMinimumIterationCheck(), llvm::VPlanTransforms::addMinimumIterationCheck(), and llvm::LoopVectorizePass::processLoop().

◆ VerboseDebug

const char VerboseDebug[] = DEBUG_TYPE "-verbose"

Definition at line 169 of file LoopVectorize.cpp.

Classes

Namespaces

Macros

Enumerations

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

◆ LV_NAME

Function Documentation

◆ addFullyUnrolledInstructionsToIgnore()

◆ calculateEarlyExitCost()

◆ checkMixedPrecision()

◆ collectSupportedLoops()

◆ estimateElementCount()

◆ getAddressAccessSCEV()

◆ getDebugLocFromInstOrOperands()

◆ getEpilogueLowering()

◆ getEpilogueTailLowering()

◆ getMaskedDivRemIntrinsic()

◆ getMaxTCFromNonZeroRange()

◆ getRecordedExecutionFrequency()

◆ getSmallBestKnownTC()

◆ getSmallConstantTripCount()

◆ getVectorLibraryVariantFor()

◆ hasConditionalInductionPhi()

◆ hasFindLastReductionPhi()

◆ hasForcedEpilogueVF()

◆ hasReplicatorRegion()

◆ hasVectorLibraryVariantFor()

◆ isExplicitVecOuterLoop()

◆ isIndvarOverflowCheckKnownFalse()

◆ isOutsideLoopWorkProfitable()

◆ legacyCSE()

◆ maybeVectorizeType()

◆ preparePlanForEpilogueVectorLoop()

◆ preparePlanForMainVectorLoop()

◆ printOptimizedVPlan()

◆ replaceVPBBWithIRVPBB()

◆ STATISTIC() [1/5]

◆ STATISTIC() [2/5]

◆ STATISTIC() [3/5]

◆ STATISTIC() [4/5]

◆ STATISTIC() [5/5]

◆ useActiveLaneMask()

◆ useActiveLaneMaskForControlFlow()

◆ useMaskedInterleavedAccesses()

◆ verifyExecutionFrequenciesMatchBFI()

◆ willGenerateVectors()

Variable Documentation

◆ EpilogueVectorizationForceVF

◆ MinItersBypassWeights

◆ VerboseDebug