#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::InnerLoopVectorizer
	InnerLoopVectorizer vectorizes loops which contain only one basic block to a specified vectorization factor (VF). More...
class	llvm::EpilogueVectorizerEpilogueLoop
	A specialized derived class of inner loop vectorizer that performs vectorization of epilogue loops in the process of vectorizing loops and their epilogues. More...
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 EpilogueLowering	getEpilogueTailLowering (const VectorizeOptions &Opts, const LoopVectorizationCostModel &MainCM, const Loop L, OptimizationRemarkEmitter ORE, LoopVectorizationLegality &LVL, const LoopVectorizeHints &Hints, 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, Loop *L, const SCEV2ValueTy &ExpandedSCEVs, ElementCount MainLoopVF, unsigned MainLoopUF, ElementCount EpilogueVF, LoopVectorizationPlanner &LVP, VFSelectionContext &Config, ScalarEvolution &SE, const MainPlanResumeMarkers &Markers)
	Prepare `Plan` for vectorizing the epilogue loop.
static void	fixScalarResumeValuesFromBypass (BasicBlock BypassBlock, VPlan &BestEpiPlan, ArrayRef< VPInstruction > ResumeValues)
static void	connectEpilogueVectorLoop (VPlan &EpiPlan, DominatorTree DT, VPIRBasicBlock VecEpilogueIterCheckVPBB, ArrayRef< VPInstruction * > ResumeValues)
	Connect the epilogue vector loop generated for `EpiPlan` to the main vector loop, after both plans have executed, updating the branch from the iteration count check of the main loop, as well as updating various phis.

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 165 of file LoopVectorize.cpp.

◆ LV_NAME

#define LV_NAME "loop-vectorize"

Definition at line 164 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 1711 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 6899 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 6852 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 1591 of file LoopVectorize.cpp.

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

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

◆ connectEpilogueVectorLoop()

void connectEpilogueVectorLoop	(	VPlan &	EpiPlan,
		DominatorTree *	DT,
		VPIRBasicBlock *	VecEpilogueIterCheckVPBB,
		ArrayRef< VPInstruction * >	ResumeValues )

static

Connect the epilogue vector loop generated for EpiPlan to the main vector loop, after both plans have executed, updating the branch from the iteration count check of the main loop, as well as updating various phis.

Definition at line 7356 of file LoopVectorize.cpp.

References llvm::GenericDomTreeUpdater< DerivedT, DomTreeT, PostDomTreeT >::applyUpdates(), llvm::cast(), llvm::DominatorTreeBase< BasicBlock, false >::Delete, fixScalarResumeValuesFromBypass(), llvm::ArrayRef< T >::front(), llvm::BasicBlock::getFirstNonPHIIt(), llvm::VPIRBasicBlock::getIRBasicBlock(), llvm::VPBlockBase::getPredecessors(), llvm::BasicBlock::getSinglePredecessor(), llvm::BasicBlock::getTerminator(), llvm::DominatorTreeBase< BasicBlock, false >::Insert, llvm::make_early_inc_range(), llvm::make_pointer_range(), llvm::BasicBlock::phis(), and llvm::Instruction::replaceSuccessorWith().

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

◆ 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 1783 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().

◆ fixScalarResumeValuesFromBypass()

void fixScalarResumeValuesFromBypass	(	BasicBlock *	BypassBlock,
		VPlan &	BestEpiPlan,
		ArrayRef< VPInstruction * >	ResumeValues )

static

Definition at line 7331 of file LoopVectorize.cpp.

References llvm::cast(), llvm::VPlan::getScalarHeader(), llvm::VPlan::getScalarPreheader(), llvm::VPBasicBlock::phis(), and llvm::zip().

Referenced by connectEpilogueVectorLoop().

◆ 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 3997 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 413 of file LoopVectorize.cpp.

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

Referenced by getDebugLocFromInstOrOperands().

◆ 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 6809 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, and llvm::PreferFoldTail.

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

◆ getEpilogueTailLowering()

EpilogueLowering getEpilogueTailLowering	(	const VectorizeOptions &	Opts,
		const LoopVectorizationCostModel &	MainCM,
		const Loop *	L,
		OptimizationRemarkEmitter *	ORE,
		LoopVectorizationLegality &	LVL,
		const LoopVectorizeHints &	Hints,
		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 3118 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().

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

◆ getMaskedDivRemIntrinsic()

Intrinsic::ID getMaskedDivRemIntrinsic ( unsigned Opcode )

static

Definition at line 2213 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 224 of file LoopVectorize.cpp.

References 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 5344 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 249 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 198 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 1797 of file LoopVectorize.cpp.

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

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

◆ hasFindLastReductionPhi()

bool hasFindLastReductionPhi ( VPlan & Plan )

static

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

Definition at line 3105 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 187 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 3097 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().

◆ 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 1810 of file LoopVectorize.cpp.

References getVectorLibraryVariantFor().

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

◆ isExplicitVecOuterLoop()

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

static

Definition at line 1563 of file LoopVectorize.cpp.

References llvm::LoopVectorizeHints::allowVectorization(), assert(), llvm::dbgs(), llvm::LoopVectorizeHints::emitRemarkWithHints(), llvm::LoopVectorizeHints::FK_Undefined, llvm::LoopVectorizeHints::getForce(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopVectorizeHints::getInterleave(), llvm::BasicBlock::getParent(), 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 1626 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 6925 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 1760 of file LoopVectorize.cpp.

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

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

◆ maybeVectorizeType()

Type * maybeVectorizeType	(	Type *	Ty,
		ElementCount	VF )

static

Definition at line 1849 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,
		Loop *	L,
		const SCEV2ValueTy &	ExpandedSCEVs,
		ElementCount	MainLoopVF,
		unsigned	MainLoopUF,
		ElementCount	EpilogueVF,
		LoopVectorizationPlanner &	LVP,
		VFSelectionContext &	Config,
		ScalarEvolution &	SE,
		const MainPlanResumeMarkers &	Markers )

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 7129 of file LoopVectorize.cpp.

References llvm::all_of(), assert(), llvm::cast(), llvm::VPRegionBlock::getCanonicalIV(), llvm::VPBlockBase::getEntryBasicBlock(), llvm::VPInstruction::getOpcode(), llvm::VPlan::getOrAddLiveIn(), llvm::VPlan::getScalarHeader(), llvm::VPlan::getVectorLoopRegion(), IV, Markers, llvm::VPBasicBlock::phis(), llvm::VPBlockBase::setName(), 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 7046 of file LoopVectorize.cpp.

References assert(), llvm::VPBasicBlock::begin(), llvm::cast(), llvm::VPBuilderBase< InserterTy >::createNaryOp(), llvm::VPBuilderBase< InserterTy >::createScalarPhi(), llvm::iterator_range< IteratorT >::end(), llvm::find_if(), llvm::VPBasicBlock::front(), llvm::VPRegionBlock::getCanonicalIV(), llvm::VPlan::getEntry(), llvm::VPBlockBase::getExitingBasicBlock(), llvm::VPBasicBlock::getFirstNonPhi(), llvm::VPValue::getLiveInIRValue(), llvm::VPlan::getMiddleBlock(), llvm::VPUser::getOperand(), 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_isa_range(), llvm::map_range(), llvm::PatternMatch::match(), llvm::VPlanPatternMatch::matchFindIVResult(), llvm::VPRecipeBase::moveBefore(), llvm::VPBasicBlock::phis(), llvm::VPValue::replaceUsesWithIf(), llvm::VPInstruction::ResumeForEpilogue, llvm::VPInstruction::setName(), llvm::VPUser::setOperand(), and llvm::to_vector().

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

◆ printOptimizedVPlan()

void printOptimizedVPlan ( VPlan & )

static

Definition at line 6077 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 1677 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 1540 of file LoopVectorize.cpp.

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

◆ useActiveLaneMaskForControlFlow()

bool useActiveLaneMaskForControlFlow ( TailFoldingStyle Style )

static

Definition at line 1545 of file LoopVectorize.cpp.

References llvm::DataAndControlFlow.

◆ useMaskedInterleavedAccesses()

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

static

Definition at line 1666 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 6083 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 3003 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 194 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 168 of file LoopVectorize.cpp.

Classes

Namespaces

Macros

Enumerations

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

◆ LV_NAME

Function Documentation

◆ addFullyUnrolledInstructionsToIgnore()

◆ calculateEarlyExitCost()

◆ checkMixedPrecision()

◆ collectSupportedLoops()

◆ connectEpilogueVectorLoop()

◆ estimateElementCount()

◆ fixScalarResumeValuesFromBypass()

◆ getAddressAccessSCEV()

◆ getDebugLocFromInstOrOperands()

◆ getEpilogueLowering()

◆ getEpilogueTailLowering()

◆ getMaskedDivRemIntrinsic()

◆ getMaxTCFromNonZeroRange()

◆ getRecordedExecutionFrequency()

◆ getSmallBestKnownTC()

◆ getSmallConstantTripCount()

◆ getVectorLibraryVariantFor()

◆ 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