This file implements a set of utility VPlan to VPlan transformations. More...

#include "VPlanTransforms.h"
#include "VPRecipeBuilder.h"
#include "VPlanAnalysis.h"
#include "VPlanCFG.h"
#include "VPlanDominatorTree.h"
#include "VPlanPatternMatch.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/Analysis/IVDescriptors.h"
#include "llvm/Analysis/VectorUtils.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/PatternMatch.h"

Functions
static bool	sinkScalarOperands (VPlan &Plan)

VPValue *	getPredicatedMask (VPRegionBlock *R)
	If `R` is a region with a VPBranchOnMaskRecipe in the entry block, return the mask.

static VPBasicBlock *	getPredicatedThenBlock (VPRegionBlock *R)
	If `R` is a triangle region, return the 'then' block of the triangle.

static bool	mergeReplicateRegionsIntoSuccessors (VPlan &Plan)

static VPRegionBlock *	createReplicateRegion (VPReplicateRecipe *PredRecipe, VPlan &Plan)

static void	addReplicateRegions (VPlan &Plan)

static bool	mergeBlocksIntoPredecessors (VPlan &Plan)
	Remove redundant VPBasicBlocks by merging them into their predecessor if the predecessor has a single successor.

static void	removeRedundantInductionCasts (VPlan &Plan)
	Remove redundant casts of inductions.

static void	removeRedundantCanonicalIVs (VPlan &Plan)
	Try to replace VPWidenCanonicalIVRecipes with a widened canonical IV recipe, if it exists.

static bool	isDeadRecipe (VPRecipeBase &R)
	Returns true if `R` is dead and can be removed.

static void	removeDeadRecipes (VPlan &Plan)

static VPScalarIVStepsRecipe *	createScalarIVSteps (VPlan &Plan, InductionDescriptor::InductionKind Kind, Instruction::BinaryOps InductionOpcode, FPMathOperator FPBinOp, ScalarEvolution &SE, Instruction TruncI, VPValue StartV, VPValue Step, VPBasicBlock::iterator IP)

static void	legalizeAndOptimizeInductions (VPlan &Plan, ScalarEvolution &SE)
	Legalize VPWidenPointerInductionRecipe, by replacing it with a PtrAdd (IndStart, ScalarIVSteps (0, Step)) if only its scalar values are used, as VPWidenPointerInductionRecipe will generate vectors only.

static void	removeRedundantExpandSCEVRecipes (VPlan &Plan)
	Remove redundant EpxandSCEVRecipes in `Plan's` entry block by replacing them with already existing recipes expanding the same SCEV expression.

static void	recursivelyDeleteDeadRecipes (VPValue *V)

static VPRegionBlock *	GetReplicateRegion (VPRecipeBase *R)

static bool	properlyDominates (const VPRecipeBase A, const VPRecipeBase B, VPDominatorTree &VPDT)

static bool	sinkRecurrenceUsersAfterPrevious (VPFirstOrderRecurrencePHIRecipe FOR, VPRecipeBase Previous, VPDominatorTree &VPDT)
	Sink users of `FOR` after the recipe defining the previous value `Previous` of the recurrence.

static SmallVector< VPUser * >	collectUsersRecursively (VPValue *V)

static void	simplifyRecipe (VPRecipeBase &R, VPTypeAnalysis &TypeInfo)
	Try to simplify recipe `R`.

static void	simplifyRecipes (VPlan &Plan, LLVMContext &Ctx)
	Try to simplify the recipes in `Plan`.

static VPActiveLaneMaskPHIRecipe *	addVPLaneMaskPhiAndUpdateExitBranch (VPlan &Plan, bool DataAndControlFlowWithoutRuntimeCheck)

static SmallVector< VPValue * >	collectAllHeaderMasks (VPlan &Plan)
	Collect all VPValues representing a header mask through the (ICMP_ULE, WideCanonicalIV, backedge-taken-count) pattern.

Detailed Description

This file implements a set of utility VPlan to VPlan transformations.

Definition in file VPlanTransforms.cpp.

Function Documentation

◆ addReplicateRegions()

static void addReplicateRegions ( VPlan & Plan )

static

Definition at line 339 of file VPlanTransforms.cpp.

References llvm::VPBlockUtils::connectBlocks(), createReplicateRegion(), llvm::VPBlockUtils::disconnectBlocks(), llvm::VPlan::getEntry(), llvm::Value::getName(), llvm::VPBlockBase::getParent(), llvm::BasicBlock::getParent(), llvm::Value::hasName(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::Value::setName(), llvm::VPBasicBlock::splitAt(), llvm::SplitBlock(), and llvm::vp_depth_first_deep().

Referenced by llvm::VPlanTransforms::createAndOptimizeReplicateRegions().

◆ addVPLaneMaskPhiAndUpdateExitBranch()

static VPActiveLaneMaskPHIRecipe * addVPLaneMaskPhiAndUpdateExitBranch	(	VPlan &	Plan,
		bool	DataAndControlFlowWithoutRuntimeCheck
	)

static

◆ collectAllHeaderMasks()

static SmallVector< VPValue * > collectAllHeaderMasks ( VPlan & Plan )

static

Collect all VPValues representing a header mask through the (ICMP_ULE, WideCanonicalIV, backedge-taken-count) pattern.

TODO: Introduce explicit recipe for header-mask instead of searching for the header-mask pattern manually.

Definition at line 1240 of file VPlanTransforms.cpp.

References assert(), llvm::count_if(), llvm::iterator_range< IteratorT >::end(), llvm::find_if(), llvm::VPlan::getCanonicalIV(), llvm::VPBlockBase::getEntryBasicBlock(), llvm::VPlan::getVectorLoopRegion(), llvm::vputils::isHeaderMask(), llvm::VPBasicBlock::phis(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::VPValue::users().

Referenced by llvm::VPlanTransforms::addActiveLaneMask(), and llvm::VPlanTransforms::tryAddExplicitVectorLength().

◆ collectUsersRecursively()

static SmallVector< VPUser * > collectUsersRecursively ( VPValue * V )

static

Definition at line 865 of file VPlanTransforms.cpp.

References llvm::VPDef::definedValues(), I, and Users.

Referenced by llvm::VPlanTransforms::clearReductionWrapFlags(), and llvm::VPlanTransforms::tryAddExplicitVectorLength().

◆ createReplicateRegion()

static VPRegionBlock * createReplicateRegion	(	VPReplicateRecipe *	PredRecipe,
		VPlan &	Plan
	)

static

Definition at line 303 of file VPlanTransforms.cpp.

References assert(), llvm::VPBlockUtils::connectBlocks(), llvm::VPRecipeBase::eraseFromParent(), llvm::VPReplicateRecipe::getMask(), llvm::VPValue::getNumUsers(), llvm::VPSingleDefRecipe::getUnderlyingInstr(), llvm::VPBlockUtils::insertTwoBlocksAfter(), llvm::VPReplicateRecipe::isUniform(), llvm::make_range(), llvm::VPUser::op_begin(), llvm::VPUser::op_end(), llvm::VPValue::replaceAllUsesWith(), and llvm::VPUser::setOperand().

Referenced by addReplicateRegions().

◆ createScalarIVSteps()

static VPScalarIVStepsRecipe * createScalarIVSteps	(	VPlan &	Plan,
		InductionDescriptor::InductionKind	Kind,
		Instruction::BinaryOps	InductionOpcode,
		FPMathOperator *	FPBinOp,
		ScalarEvolution &	SE,
		Instruction *	TruncI,
		VPValue *	StartV,
		VPValue *	Step,
		VPBasicBlock::iterator	IP
	)

static

Definition at line 523 of file VPlanTransforms.cpp.

References assert(), llvm::VPlan::getCanonicalIV(), llvm::ScalarEvolution::getContext(), llvm::VPValue::getDefiningRecipe(), llvm::VPBlockBase::getEntryBasicBlock(), llvm::FPMathOperator::getFastMathFlags(), llvm::Type::getScalarSizeInBits(), llvm::VPCanonicalIVPHIRecipe::getScalarType(), llvm::VPBlockBase::getSingleHierarchicalPredecessor(), llvm::Value::getType(), llvm::VPlan::getVectorLoopRegion(), llvm::VPTypeAnalysis::inferScalarType(), llvm::VPBasicBlock::insert(), llvm::VPCanonicalIVPHIRecipe::isCanonical(), and llvm::Type::isIntegerTy().

Referenced by legalizeAndOptimizeInductions().

◆ getPredicatedMask()

VPValue * getPredicatedMask ( VPRegionBlock * R )

If R is a region with a VPBranchOnMaskRecipe in the entry block, return the mask.

Definition at line 184 of file VPlanTransforms.cpp.

Referenced by mergeReplicateRegionsIntoSuccessors().

◆ getPredicatedThenBlock()

static VPBasicBlock * getPredicatedThenBlock ( VPRegionBlock * R )

static

If R is a triangle region, return the 'then' block of the triangle.

Definition at line 194 of file VPlanTransforms.cpp.

Referenced by mergeReplicateRegionsIntoSuccessors().

◆ GetReplicateRegion()

static VPRegionBlock * GetReplicateRegion ( VPRecipeBase * R )

static

Definition at line 719 of file VPlanTransforms.cpp.

References assert().

Referenced by properlyDominates().

◆ isDeadRecipe()

static bool isDeadRecipe ( VPRecipeBase & R )

static

Returns true if R is dead and can be removed.

Definition at line 489 of file VPlanTransforms.cpp.

References llvm::all_of(), and llvm::PatternMatch::match().

Referenced by recursivelyDeleteDeadRecipes(), and removeDeadRecipes().

◆ legalizeAndOptimizeInductions()

static void legalizeAndOptimizeInductions	(	VPlan &	Plan,
		ScalarEvolution &	SE
	)

static

Legalize VPWidenPointerInductionRecipe, by replacing it with a PtrAdd (IndStart, ScalarIVSteps (0, Step)) if only its scalar values are used, as VPWidenPointerInductionRecipe will generate vectors only.

If some users require vectors while other require scalars, the scalar uses need to extract the scalars from the generated vectors (Note that this is different to how int/fp inductions are handled). Also optimize VPWidenIntOrFpInductionRecipe, if any of its users needs scalar values, by providing them scalar steps built on the canonical scalar IV and update the original IV's users. This is an optional optimization to reduce the needs of vector extracts.

Definition at line 578 of file VPlanTransforms.cpp.

References createScalarIVSteps(), llvm::VPRecipeBase::getDebugLoc(), llvm::VPBlockBase::getEntryBasicBlock(), llvm::VPBasicBlock::getFirstNonPhi(), llvm::ElementCount::getFixed(), llvm::VPlan::getOrAddLiveIn(), llvm::VPlan::getVectorLoopRegion(), llvm::VPlan::hasScalableVF(), llvm::VPlan::hasVF(), llvm::InductionDescriptor::IK_IntInduction, llvm::none_of(), llvm::VPBasicBlock::phis(), llvm::VPInstruction::PtrAdd, and ToRemove.

Referenced by llvm::VPlanTransforms::optimize().

◆ mergeBlocksIntoPredecessors()

static bool mergeBlocksIntoPredecessors ( VPlan & Plan )

static

Remove redundant VPBasicBlocks by merging them into their predecessor if the predecessor has a single successor.

Definition at line 369 of file VPlanTransforms.cpp.

References llvm::VPBlockUtils::connectBlocks(), llvm::VPBlockUtils::disconnectBlocks(), llvm::SmallVectorBase< Size_T >::empty(), llvm::VPBasicBlock::end(), llvm::VPlan::getEntry(), llvm::make_early_inc_range(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::to_vector(), and llvm::vp_depth_first_deep().

◆ mergeReplicateRegionsIntoSuccessors()

static bool mergeReplicateRegionsIntoSuccessors ( VPlan & Plan )

static

Definition at line 216 of file VPlanTransforms.cpp.

References assert(), llvm::VPBlockUtils::connectBlocks(), llvm::SetVector< T, Vector, Set, N >::contains(), llvm::VPBlockUtils::disconnectBlocks(), llvm::SetVector< T, Vector, Set, N >::empty(), llvm::VPlan::getEntry(), llvm::VPBasicBlock::getFirstNonPhi(), getPredicatedMask(), getPredicatedThenBlock(), llvm::VPBlockBase::getSingleSuccessor(), llvm::SetVector< T, Vector, Set, N >::insert(), llvm::make_early_inc_range(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::VPValue::replaceUsesWithIf(), llvm::reverse(), and llvm::vp_depth_first_deep().

Referenced by llvm::VPlanTransforms::createAndOptimizeReplicateRegions().

◆ properlyDominates()

static bool properlyDominates	(	const VPRecipeBase *	A,
		const VPRecipeBase *	B,
		VPDominatorTree &	VPDT
	)

static

Definition at line 733 of file VPlanTransforms.cpp.

References A, assert(), B, GetReplicateRegion(), llvm_unreachable, and llvm::DominatorTreeBase< NodeT, IsPostDom >::properlyDominates().

Referenced by sinkRecurrenceUsersAfterPrevious().

◆ recursivelyDeleteDeadRecipes()

static void recursivelyDeleteDeadRecipes ( VPValue * V )

static

Definition at line 653 of file VPlanTransforms.cpp.

References llvm::SmallVectorImpl< T >::append(), llvm::SmallVectorBase< Size_T >::empty(), llvm::VPValue::getDefiningRecipe(), llvm::SmallPtrSetImpl< PtrType >::insert(), isDeadRecipe(), llvm::SmallVectorImpl< T >::pop_back_val(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by llvm::VPlanTransforms::optimizeForVFAndUF(), and llvm::VPlanTransforms::tryAddExplicitVectorLength().

◆ removeDeadRecipes()

static void removeDeadRecipes ( VPlan & Plan )

static

Definition at line 508 of file VPlanTransforms.cpp.

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

Referenced by llvm::VPlanTransforms::optimize().

◆ removeRedundantCanonicalIVs()

static void removeRedundantCanonicalIVs ( VPlan & Plan )

static

Try to replace VPWidenCanonicalIVRecipes with a widened canonical IV recipe, if it exists.

Definition at line 453 of file VPlanTransforms.cpp.

References llvm::any_of(), llvm::VPRecipeBase::eraseFromParent(), llvm::VPlan::getCanonicalIV(), llvm::VPBlockBase::getEntryBasicBlock(), llvm::VPlan::getVectorLoopRegion(), llvm::vputils::onlyFirstLaneUsed(), llvm::VPBasicBlock::phis(), llvm::VPValue::replaceAllUsesWith(), and llvm::VPValue::users().

Referenced by llvm::VPlanTransforms::optimize().

◆ removeRedundantExpandSCEVRecipes()

static void removeRedundantExpandSCEVRecipes ( VPlan & Plan )

static

Remove redundant EpxandSCEVRecipes in Plan's entry block by replacing them with already existing recipes expanding the same SCEV expression.

Definition at line 636 of file VPlanTransforms.cpp.

References llvm::VPlan::getEntry(), llvm::VPBlockBase::getEntryBasicBlock(), I, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), and llvm::make_early_inc_range().

Referenced by llvm::VPlanTransforms::optimize().

◆ removeRedundantInductionCasts()

static void removeRedundantInductionCasts ( VPlan & Plan )

static

Remove redundant casts of inductions.

Such redundant casts are casts of induction variables that can be ignored, because we already proved that the casted phi is equal to the uncasted phi in the vectorized loop. There is no need to vectorize the cast - the same value can be used for both the phi and casts in the vector loop.

Definition at line 420 of file VPlanTransforms.cpp.

References llvm::VPBlockBase::getEntryBasicBlock(), llvm::VPlan::getVectorLoopRegion(), IV, llvm::VPBasicBlock::phis(), llvm::VPValue::replaceAllUsesWith(), llvm::reverse(), and llvm::VPValue::users().

Referenced by llvm::VPlanTransforms::optimize().