#include "Transforms/Vectorize/VPlanTransforms.h"

Static Public Member Functions
static void	VPInstructionsToVPRecipes (VPlanPtr &Plan, function_ref< const InductionDescriptor (PHINode )> GetIntOrFpInductionDescriptor, ScalarEvolution &SE, const TargetLibraryInfo &TLI)
	Replaces the VPInstructions in `Plan` with corresponding widen recipes.

static bool	adjustFixedOrderRecurrences (VPlan &Plan, VPBuilder &Builder)
	Try to have all users of fixed-order recurrences appear after the recipe defining their previous value, by either sinking users or hoisting recipes defining their previous value (and its operands).

static void	clearReductionWrapFlags (VPlan &Plan)
	Clear NSW/NUW flags from reduction instructions if necessary.

static void	unrollByUF (VPlan &Plan, unsigned UF, LLVMContext &Ctx)
	Explicitly unroll `Plan` by `UF`.

static void	optimizeForVFAndUF (VPlan &Plan, ElementCount BestVF, unsigned BestUF, PredicatedScalarEvolution &PSE)
	Optimize `Plan` based on `BestVF` and `BestUF`.

static void	optimize (VPlan &Plan)
	Apply VPlan-to-VPlan optimizations to `Plan`, including induction recipe optimizations, dead recipe removal, replicate region optimizations and block merging.

static void	createAndOptimizeReplicateRegions (VPlan &Plan)
	Wrap predicated VPReplicateRecipes with a mask operand in an if-then region block and remove the mask operand.

static void	addActiveLaneMask (VPlan &Plan, bool UseActiveLaneMaskForControlFlow, bool DataAndControlFlowWithoutRuntimeCheck)
	Replace (ICMP_ULE, wide canonical IV, backedge-taken-count) checks with an (active-lane-mask recipe, wide canonical IV, trip-count).

static void	truncateToMinimalBitwidths (VPlan &Plan, const MapVector< Instruction *, uint64_t > &MinBWs)
	Insert truncates and extends for any truncated recipe.

static void	dropPoisonGeneratingRecipes (VPlan &Plan, function_ref< bool(BasicBlock *)> BlockNeedsPredication)
	Drop poison flags from recipes that may generate a poison value that is used after vectorization, even when their operands are not poison.

static bool	tryAddExplicitVectorLength (VPlan &Plan, const std::optional< unsigned > &MaxEVLSafeElements)
	Add a VPEVLBasedIVPHIRecipe and related recipes to `Plan` and replaces all uses except the canonical IV increment of VPCanonicalIVPHIRecipe with a VPEVLBasedIVPHIRecipe.

static void	createInterleaveGroups (VPlan &Plan, const SmallPtrSetImpl< const InterleaveGroup< Instruction > * > &InterleaveGroups, VPRecipeBuilder &RecipeBuilder, bool ScalarEpilogueAllowed)

static void	removeDeadRecipes (VPlan &Plan)
	Remove dead recipes from `Plan`.

static bool	handleUncountableEarlyExit (VPlan &Plan, ScalarEvolution &SE, Loop OrigLoop, BasicBlock UncountableExitingBlock, VPRecipeBuilder &RecipeBuilder)
	Update `Plan` to account for the uncountable early exit block in `UncountableExitingBlock` by.

static void	convertToConcreteRecipes (VPlan &Plan)
	Lower abstract recipes to concrete ones, that can be codegen'd.

static void	optimizeInductionExitUsers (VPlan &Plan, DenseMap< VPValue , VPValue > &EndValues)
	If there's a single exit block, optimize its phi recipes that use exiting IV values by feeding them precomputed end values instead, possibly taken one step backwards.

Detailed Description

Definition at line 30 of file VPlanTransforms.h.

Member Function Documentation

◆ addActiveLaneMask()

void VPlanTransforms::addActiveLaneMask	(	VPlan &	Plan,
		bool	UseActiveLaneMaskForControlFlow,
		bool	DataAndControlFlowWithoutRuntimeCheck
	)

static

Replace (ICMP_ULE, wide canonical IV, backedge-taken-count) checks with an (active-lane-mask recipe, wide canonical IV, trip-count).

If UseActiveLaneMaskForControlFlow is true, introduce an VPActiveLaneMaskPHIRecipe. If DataAndControlFlowWithoutRuntimeCheck is true, no minimum-iteration runtime check will be created (during skeleton creation) and instead it is handled using active-lane-mask. DataAndControlFlowWithoutRuntimeCheck implies UseActiveLaneMaskForControlFlow.

Definition at line 1606 of file VPlanTransforms.cpp.

References llvm::VPInstruction::ActiveLaneMask, addVPLaneMaskPhiAndUpdateExitBranch(), assert(), B, collectAllHeaderMasks(), llvm::DataAndControlFlowWithoutRuntimeCheck, llvm::find_if(), llvm::VPlan::getCanonicalIV(), llvm::VPBuilder::getToInsertAfter(), llvm::VPlan::getTripCount(), and llvm::VPValue::users().

◆ adjustFixedOrderRecurrences()

bool VPlanTransforms::adjustFixedOrderRecurrences	(	VPlan &	Plan,
		VPBuilder &	Builder
	)

static

Try to have all users of fixed-order recurrences appear after the recipe defining their previous value, by either sinking users or hoisting recipes defining their previous value (and its operands).

Then introduce FirstOrderRecurrenceSplice VPInstructions to combine the value from the recurrence phis and previous values.

Returns: true if all users of fixed-order recurrences could be re-arranged as needed or false if it is not possible. In the latter case, Plan is not valid.

Definition at line 1208 of file VPlanTransforms.cpp.

References assert(), llvm::VPBuilder::createNaryOp(), llvm::VPInstruction::FirstOrderRecurrenceSplice, llvm::VPRegionBlock::getEntry(), llvm::VPBlockBase::getEntryBasicBlock(), llvm::VPBasicBlock::getFirstNonPhi(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::VPRecipeBase::getParent(), llvm::VPlan::getVectorLoopRegion(), hoistPreviousBeforeFORUsers(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::VPBasicBlock::phis(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::DominatorTreeBase< NodeT, IsPostDom >::recalculate(), llvm::VPBuilder::setInsertPoint(), and sinkRecurrenceUsersAfterPrevious().

◆ clearReductionWrapFlags()

void VPlanTransforms::clearReductionWrapFlags ( VPlan & Plan )

static

Clear NSW/NUW flags from reduction instructions if necessary.

Definition at line 1256 of file VPlanTransforms.cpp.

References llvm::Add, collectUsersRecursively(), llvm::VPBlockBase::getEntryBasicBlock(), llvm::RecurrenceDescriptor::getRecurrenceKind(), llvm::VPlan::getVectorLoopRegion(), llvm::Mul, and llvm::VPBasicBlock::phis().

◆ convertToConcreteRecipes()

void VPlanTransforms::convertToConcreteRecipes ( VPlan & Plan )

static

Lower abstract recipes to concrete ones, that can be codegen'd.

Definition at line 2046 of file VPlanTransforms.cpp.

References llvm::VPlan::getEntry(), llvm::make_early_inc_range(), Name, and llvm::vp_depth_first_deep().

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

◆ createAndOptimizeReplicateRegions()

void VPlanTransforms::createAndOptimizeReplicateRegions ( VPlan & Plan )

static

Wrap predicated VPReplicateRecipes with a mask operand in an if-then region block and remove the mask operand.

Optimize the created regions by iteratively sinking scalar operands into the region, followed by merging regions until no improvements are remaining.

Definition at line 406 of file VPlanTransforms.cpp.

References addReplicateRegions(), mergeBlocksIntoPredecessors(), mergeReplicateRegionsIntoSuccessors(), and sinkScalarOperands().

Referenced by optimize().

◆ createInterleaveGroups()

void VPlanTransforms::createInterleaveGroups	(	VPlan &	Plan,
		const SmallPtrSetImpl< const InterleaveGroup< Instruction > * > &	InterleaveGroups,
		VPRecipeBuilder &	RecipeBuilder,
		bool	ScalarEpilogueAllowed
	)

static

Definition at line 1970 of file VPlanTransforms.cpp.

References Addr, assert(), B, DL, llvm::VPRecipeBase::eraseFromParent(), llvm::Instruction::getDataLayout(), llvm::getLoadStorePointerOperand(), llvm::getLoadStoreType(), llvm::VPlan::getOrAddLiveIn(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::VPRecipeBuilder::getRecipe(), llvm::VPDef::getVPSingleValue(), llvm::Offset, llvm::VPDominatorTree::properlyDominates(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::DominatorTreeBase< NodeT, IsPostDom >::recalculate(), and llvm::VPValue::replaceAllUsesWith().

◆ dropPoisonGeneratingRecipes()

void VPlanTransforms::dropPoisonGeneratingRecipes	(	VPlan &	Plan,
		function_ref< bool(BasicBlock *)>	BlockNeedsPredication
	)

static

Drop poison flags from recipes that may generate a poison value that is used after vectorization, even when their operands are not poison.

Those recipes meet the following conditions:

Contribute to the address computation of a recipe generating a widen memory load/store (VPWidenMemoryInstructionRecipe or VPInterleaveRecipe).
Such a widen memory load/store has at least one underlying Instruction that is in a basic block that needs predication and after vectorization the generated instruction won't be predicated. Uses BlockNeedsPredication to check if a block needs predicating. TODO: Replace BlockNeedsPredication callback with retrieving info from VPlan directly.

Definition at line 1873 of file VPlanTransforms.cpp.

References llvm::SmallVectorBase< Size_T >::empty(), for(), if(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

◆ handleUncountableEarlyExit()

bool VPlanTransforms::handleUncountableEarlyExit	(	VPlan &	Plan,
		ScalarEvolution &	SE,
		Loop *	OrigLoop,
		BasicBlock *	UncountableExitingBlock,
		VPRecipeBuilder &	RecipeBuilder
	)

static

Update Plan to account for the uncountable early exit block in UncountableExitingBlock by.

updating the condition exiting the vector loop to include the early exit conditions
splitting the original middle block to branch to the early exit block if taken.

Definition at line 2065 of file VPlanTransforms.cpp.

References llvm::VPInstruction::AnyOf, assert(), llvm::VPInstruction::BranchOnCond, llvm::VPInstruction::BranchOnCount, llvm::VPBlockUtils::connectBlocks(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::VPBuilder::createICmp(), llvm::VPBuilder::createNaryOp(), llvm::VPBuilder::createNot(), llvm::VPlan::createVPBasicBlock(), llvm::VPlan::createVPIRBasicBlock(), llvm::VPRecipeBase::eraseFromParent(), llvm::VPRecipeBuilder::getBlockInMask(), llvm::VPRegionBlock::getExiting(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::VPlan::getMiddleBlock(), llvm::BasicBlock::getTerminator(), llvm::LoopBase< BlockT, LoopT >::getUniqueExitBlock(), llvm::VPlan::getVectorLoopRegion(), llvm::VPRecipeBuilder::getVPValueOrAddLiveIn(), llvm::CmpInst::ICMP_EQ, llvm::VPBlockUtils::insertOnEdge(), llvm::VPValue::isLiveIn(), and llvm::VPBlockBase::swapSuccessors().

◆ optimize()

void VPlanTransforms::optimize ( VPlan & Plan )

static

Apply VPlan-to-VPlan optimizations to Plan, including induction recipe optimizations, dead recipe removal, replicate region optimizations and block merging.

Definition at line 1441 of file VPlanTransforms.cpp.

References createAndOptimizeReplicateRegions(), llvm::VPlan::getCanonicalIV(), llvm::VPCanonicalIVPHIRecipe::getScalarType(), legalizeAndOptimizeInductions(), licm, mergeBlocksIntoPredecessors(), removeDeadRecipes(), removeRedundantCanonicalIVs(), removeRedundantExpandSCEVRecipes(), removeRedundantInductionCasts(), and simplifyRecipes().

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

◆ optimizeForVFAndUF()

void VPlanTransforms::optimizeForVFAndUF	(	VPlan &	Plan,
		ElementCount	BestVF,
		unsigned	BestUF,
		PredicatedScalarEvolution &	PSE
	)

static

Optimize Plan based on BestVF and BestUF.

This may restrict the resulting plan to BestVF and BestUF.

Definition at line 978 of file VPlanTransforms.cpp.

References llvm::all_of(), llvm::VPBasicBlock::appendRecipe(), assert(), B, llvm::VPBasicBlock::back(), llvm::VPInstruction::BranchOnCond, llvm::CallingConv::C, llvm::VPBlockUtils::connectBlocks(), llvm::VPBlockUtils::disconnectBlocks(), llvm::VPlan::getCanonicalIV(), llvm::ScalarEvolution::getContext(), llvm::ScalarEvolution::getElementCount(), llvm::VPRegionBlock::getEntry(), llvm::VPBlockBase::getExitingBasicBlock(), llvm::VPlan::getOrAddLiveIn(), llvm::VPCanonicalIVPHIRecipe::getScalarType(), llvm::vputils::getSCEVExprForVPValue(), llvm::PredicatedScalarEvolution::getSE(), llvm::VPBlockBase::getSinglePredecessor(), llvm::VPBlockBase::getSingleSuccessor(), llvm::VPlan::getTripCount(), llvm::ConstantInt::getTrue(), llvm::SCEV::getType(), llvm::VPlan::getVectorLoopRegion(), llvm::VPlan::hasUF(), llvm::VPlan::hasVF(), llvm::CmpInst::ICMP_ULE, llvm::ScalarEvolution::isKnownPredicate(), llvm::SCEV::isZero(), llvm::PatternMatch::m_Not(), llvm::make_early_inc_range(), llvm::PatternMatch::match(), llvm::details::FixedOrScalableQuantity< LeafTy, ValueTy >::multiplyCoefficientBy(), removeDeadRecipes(), llvm::VPlan::setUF(), llvm::VPlan::setVF(), simplifyRecipes(), and llvm::vp_depth_first_shallow().

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

◆ optimizeInductionExitUsers()

void VPlanTransforms::optimizeInductionExitUsers	(	VPlan &	Plan,
		DenseMap< VPValue , VPValue > &	EndValues
	)

static

If there's a single exit block, optimize its phi recipes that use exiting IV values by feeding them precomputed end values instead, possibly taken one step backwards.

Definition at line 731 of file VPlanTransforms.cpp.

References assert(), B, llvm::VPlan::getCanonicalIV(), llvm::VPlan::getExitBlocks(), llvm::VPValue::getLiveInIRValue(), llvm::VPlan::getMiddleBlock(), getOptimizableIVOf(), llvm::VPlan::getOrAddLiveIn(), llvm::VPCanonicalIVPHIRecipe::getScalarType(), llvm::VPBlockBase::getSinglePredecessor(), llvm::VPBasicBlock::getTerminator(), llvm::Value::getType(), llvm::VPTypeAnalysis::inferScalarType(), llvm::Type::isFloatingPointTy(), llvm::Type::isIntegerTy(), llvm::Type::isPointerTy(), llvm_unreachable, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::lookup(), llvm::PatternMatch::m_SpecificInt(), llvm::PatternMatch::match(), and llvm::SmallVectorBase< Size_T >::size().

◆ removeDeadRecipes()

void VPlanTransforms::removeDeadRecipes ( VPlan & Plan )

static

Remove dead recipes from Plan.

Definition at line 512 of file VPlanTransforms.cpp.

References llvm::VPlan::getEntry(), isDeadRecipe(), llvm::make_early_inc_range(), and llvm::reverse().

Referenced by llvm::LoopVectorizationPlanner::executePlan(), optimize(), optimizeForVFAndUF(), preparePlanForMainVectorLoop(), and unrollByUF().

◆ truncateToMinimalBitwidths()

void VPlanTransforms::truncateToMinimalBitwidths	(	VPlan &	Plan,
		const MapVector< Instruction *, uint64_t > &	MinBWs
	)

static

Insert truncates and extends for any truncated recipe.

Redundant casts will be folded later.

Definition at line 1308 of file VPlanTransforms.cpp.

References llvm::VPBasicBlock::appendRecipe(), assert(), llvm::MapVector< KeyT, ValueT, MapType, VectorType >::contains(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::contains(), llvm::IntegerType::get(), llvm::VPlan::getCanonicalIV(), llvm::Type::getContext(), llvm::Type::getScalarSizeInBits(), llvm::VPCanonicalIVPHIRecipe::getScalarType(), llvm::VPValue::getUnderlyingValue(), llvm::VPlan::getVectorLoopRegion(), llvm::VPlan::getVectorPreheader(), Idx, llvm::VPTypeAnalysis::inferScalarType(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::VPRecipeBase::insertBefore(), llvm::isa(), llvm::Type::isIntegerTy(), llvm::MapVector< KeyT, ValueT, MapType, VectorType >::lookup(), llvm::make_early_inc_range(), llvm::PatternMatch::match(), llvm::none_of(), llvm::VPValue::replaceAllUsesWith(), llvm::MapVector< KeyT, ValueT, MapType, VectorType >::size(), and llvm::vp_depth_first_deep().

◆ tryAddExplicitVectorLength()

bool VPlanTransforms::tryAddExplicitVectorLength	(	VPlan &	Plan,
		const std::optional< unsigned > &	MaxSafeElements
	)

static

Add a VPEVLBasedIVPHIRecipe and related recipes to Plan and replaces all uses except the canonical IV increment of VPCanonicalIVPHIRecipe with a VPEVLBasedIVPHIRecipe.

VPCanonicalIVPHIRecipe is only used to control the loop after this transformation.

Returns: true if the transformation succeeds, or false if it doesn't.

VPCanonicalIVPHIRecipe is used only for loop iterations counting after this transformation.

The function uses the following definitions: StartV is the canonical induction start value.

The function adds the following recipes:

vector.ph: ...

vector.body: ... EVLPhi = EXPLICIT-VECTOR-LENGTH-BASED-IV-PHI [ StartV, vector.ph ], [ NextEVLIV, vector.body ] AVL = sub original TC, EVLPhi VPEVL = EXPLICIT-VECTOR-LENGTH AVL ... NextEVLIV = add IVSize (cast i32 VPEVVL to IVSize), EVLPhi ...

If MaxSafeElements is provided, the function adds the following recipes: vector.ph: ...

vector.body: ... EVLPhi = EXPLICIT-VECTOR-LENGTH-BASED-IV-PHI [ StartV, vector.ph ], [ NextEVLIV, vector.body ] AVL = sub original TC, EVLPhi cmp = cmp ult AVL, MaxSafeElements SAFE_AVL = select cmp, AVL, MaxSafeElements VPEVL = EXPLICIT-VECTOR-LENGTH SAFE_AVL ... NextEVLIV = add IVSize (cast i32 VPEVL to IVSize), EVLPhi ...

Definition at line 1812 of file VPlanTransforms.cpp.

References llvm::any_of(), llvm::VPBuilder::createICmp(), llvm::VPBuilder::createNaryOp(), llvm::VPBuilder::createSelect(), llvm::VPInstruction::ExplicitVectorLength, llvm::VPlan::getCanonicalIV(), llvm::VPRecipeBase::getDebugLoc(), llvm::VPBlockBase::getEntryBasicBlock(), llvm::VPlan::getOrAddLiveIn(), llvm::VPlan::getTripCount(), llvm::VPlan::getVectorLoopRegion(), llvm::CmpInst::ICMP_ULT, llvm::VPRecipeBase::insertBefore(), llvm::VPlan::setUF(), and transformRecipestoEVLRecipes().

◆ unrollByUF()

void VPlanTransforms::unrollByUF	(	VPlan &	Plan,
		unsigned	UF,
		LLVMContext &	Ctx
	)

static

Explicitly unroll Plan by UF.

Definition at line 391 of file VPlanUnroll.cpp.

References assert(), llvm::VPInstruction::CanonicalIVIncrementForPart, Cleanup, llvm::VPlan::getEntry(), llvm::VPBlockBase::getEntryBasicBlock(), llvm::VPlan::getVectorLoopRegion(), H, llvm::make_early_inc_range(), llvm::make_scope_exit(), llvm::VPBasicBlock::phis(), removeDeadRecipes(), llvm::VPlan::setUF(), and llvm::vp_depth_first_deep().

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

◆ VPInstructionsToVPRecipes()

void VPlanTransforms::VPInstructionsToVPRecipes	(	VPlanPtr &	Plan,
		function_ref< const InductionDescriptor (PHINode )>	GetIntOrFpInductionDescriptor,
		ScalarEvolution &	SE,
		const TargetLibraryInfo &	TLI
	)

static

Replaces the VPInstructions in Plan with corresponding widen recipes.

Definition at line 33 of file VPlanTransforms.cpp.

References assert(), GEP, llvm::VPDef::getNumDefinedValues(), llvm::vputils::getOrCreateVPValueForSCEVExpr(), llvm::VPValue::getUnderlyingValue(), llvm::getVectorIntrinsicIDForCall(), llvm::VPDef::getVPSingleValue(), II, llvm::VPRecipeBase::insertBefore(), llvm::make_early_inc_range(), llvm::make_range(), llvm::User::operands(), and llvm::VPValue::replaceAllUsesWith().

The documentation for this struct was generated from the following files:

lib/Transforms/Vectorize/VPlanTransforms.h
lib/Transforms/Vectorize/VPlanTransforms.cpp
lib/Transforms/Vectorize/VPlanUnroll.cpp

Static Public Member Functions

Detailed Description

Member Function Documentation

◆ addActiveLaneMask()

◆ adjustFixedOrderRecurrences()

◆ clearReductionWrapFlags()

◆ convertToConcreteRecipes()

◆ createAndOptimizeReplicateRegions()

◆ createInterleaveGroups()

◆ dropPoisonGeneratingRecipes()

◆ handleUncountableEarlyExit()

◆ optimize()

◆ optimizeForVFAndUF()

◆ optimizeInductionExitUsers()

◆ removeDeadRecipes()

◆ truncateToMinimalBitwidths()

◆ tryAddExplicitVectorLength()

◆ unrollByUF()

◆ VPInstructionsToVPRecipes()