LLVM 22.0.0git
|
This file implements a set of utility VPlan to VPlan transformations. More...
#include "VPlanTransforms.h"
#include "VPRecipeBuilder.h"
#include "VPlan.h"
#include "VPlanAnalysis.h"
#include "VPlanCFG.h"
#include "VPlanDominatorTree.h"
#include "VPlanHelpers.h"
#include "VPlanPatternMatch.h"
#include "VPlanUtils.h"
#include "VPlanVerifier.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/TypeSwitch.h"
#include "llvm/Analysis/IVDescriptors.h"
#include "llvm/Analysis/InstSimplifyFolder.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/VectorUtils.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/TypeSize.h"
#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
Go to the source code of this file.
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 VPScalarIVStepsRecipe * | createScalarIVSteps (VPlan &Plan, InductionDescriptor::InductionKind Kind, Instruction::BinaryOps InductionOpcode, FPMathOperator *FPBinOp, Instruction *TruncI, VPValue *StartV, VPValue *Step, DebugLoc DL, VPBuilder &Builder) |
static SmallVector< VPUser * > | collectUsersRecursively (VPValue *V) |
static void | legalizeAndOptimizeInductions (VPlan &Plan) |
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 VPWidenInductionRecipe * | getOptimizableIVOf (VPValue *VPV, ScalarEvolution &SE) |
Check if VPV is an untruncated wide induction, either before or after the increment. | |
static VPValue * | optimizeEarlyExitInductionUser (VPlan &Plan, VPTypeAnalysis &TypeInfo, VPBlockBase *PredVPBB, VPValue *Op, ScalarEvolution &SE) |
Attempts to optimize the induction variable exit values for users in the early exit block. | |
static VPValue * | optimizeLatchExitInductionUser (VPlan &Plan, VPTypeAnalysis &TypeInfo, VPBlockBase *PredVPBB, VPValue *Op, DenseMap< VPValue *, VPValue * > &EndValues, ScalarEvolution &SE) |
Attempts to optimize the induction variable exit values for users in the exit block coming from the latch in the original scalar loop. | |
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 Value * | tryToFoldLiveIns (const VPRecipeBase &R, unsigned Opcode, ArrayRef< VPValue * > Operands, const DataLayout &DL, VPTypeAnalysis &TypeInfo) |
Try to fold R using InstSimplifyFolder. | |
static void | simplifyRecipe (VPRecipeBase &R, VPTypeAnalysis &TypeInfo) |
Try to simplify recipe R . | |
static void | narrowToSingleScalarRecipes (VPlan &Plan) |
static void | simplifyBlends (VPlan &Plan) |
Normalize and simplify VPBlendRecipes. | |
static bool | optimizeVectorInductionWidthForTCAndVFUF (VPlan &Plan, ElementCount BestVF, unsigned BestUF) |
Optimize the width of vector induction variables in Plan based on a known constant Trip Count, BestVF and BestUF . | |
static bool | isConditionTrueViaVFAndUF (VPValue *Cond, VPlan &Plan, ElementCount BestVF, unsigned BestUF, ScalarEvolution &SE) |
Return true if Cond is known to be true for given BestVF and BestUF . | |
static bool | simplifyBranchConditionForVFAndUF (VPlan &Plan, ElementCount BestVF, unsigned BestUF, PredicatedScalarEvolution &PSE) |
Try to simplify the branch condition of Plan . | |
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 bool | hoistPreviousBeforeFORUsers (VPFirstOrderRecurrencePHIRecipe *FOR, VPRecipeBase *Previous, VPDominatorTree &VPDT) |
Try to hoist Previous and its operands before all users of FOR . | |
static void | licm (VPlan &Plan) |
Move loop-invariant recipes out of the vector loop region in Plan . | |
static VPActiveLaneMaskPHIRecipe * | addVPLaneMaskPhiAndUpdateExitBranch (VPlan &Plan, bool DataAndControlFlowWithoutRuntimeCheck) |
static VPSingleDefRecipe * | findHeaderMask (VPlan &Plan) |
Collect the header mask with the pattern: (ICMP_ULE, WideCanonicalIV, backedge-taken-count) TODO: Introduce explicit recipe for header-mask instead of searching for the header-mask pattern manually. | |
static VPRecipeBase * | optimizeMaskToEVL (VPValue *HeaderMask, VPRecipeBase &CurRecipe, VPTypeAnalysis &TypeInfo, VPValue &AllOneMask, VPValue &EVL) |
Try to optimize a CurRecipe masked by HeaderMask to a corresponding EVL-based recipe without the header mask. | |
static void | transformRecipestoEVLRecipes (VPlan &Plan, VPValue &EVL) |
Replace recipes with their EVL variants. | |
static void | expandVPWidenIntOrFpInduction (VPWidenIntOrFpInductionRecipe *WidenIVR, VPTypeAnalysis &TypeInfo) |
Expand a VPWidenIntOrFpInduction into executable recipes, for the initial value, phi and backedge value. | |
static void | expandVPWidenPointerInduction (VPWidenPointerInductionRecipe *R, VPTypeAnalysis &TypeInfo) |
Expand a VPWidenPointerInductionRecipe into executable recipes, for the initial value, phi and backedge value. | |
static VPExpressionRecipe * | tryToMatchAndCreateExtendedReduction (VPReductionRecipe *Red, VPCostContext &Ctx, VFRange &Range) |
This function tries convert extended in-loop reductions to VPExpressionRecipe and clamp the Range if it is beneficial and valid. | |
static VPExpressionRecipe * | tryToMatchAndCreateMulAccumulateReduction (VPReductionRecipe *Red, VPCostContext &Ctx, VFRange &Range) |
This function tries convert extended in-loop reductions to VPExpressionRecipe and clamp the Range if it is beneficial and valid. | |
static void | tryToCreateAbstractReductionRecipe (VPReductionRecipe *Red, VPCostContext &Ctx, VFRange &Range) |
This function tries to create abstract recipes from the reduction recipe for following optimizations and cost estimation. | |
static bool | canNarrowLoad (VPWidenRecipe *WideMember0, unsigned OpIdx, VPValue *OpV, unsigned Idx) |
Returns true if V is VPWidenLoadRecipe or VPInterleaveRecipe that can be converted to a narrower recipe. | |
static bool | isConsecutiveInterleaveGroup (VPInterleaveRecipe *InterleaveR, unsigned VF, VPTypeAnalysis &TypeInfo, unsigned VectorRegWidth) |
Returns true if IR is a full interleave group with factor and number of members both equal to VF . | |
static bool | isAlreadyNarrow (VPValue *VPV) |
Returns true if VPValue is a narrow VPValue. | |
This file implements a set of utility VPlan to VPlan transformations.
Definition in file VPlanTransforms.cpp.
|
static |
Definition at line 381 of file VPlanTransforms.cpp.
References createReplicateRegion(), llvm::VPlan::getEntry(), llvm::VPRegionBlock::getExiting(), llvm::Value::getName(), llvm::VPBlockBase::getParent(), llvm::RegionBase< Tr >::getParent(), llvm::BasicBlock::getParent(), llvm::Value::hasName(), llvm::VPBlockUtils::insertOnEdge(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::VPRegionBlock::setExiting(), llvm::Value::setName(), llvm::VPBasicBlock::splitAt(), llvm::SplitBlock(), and llvm::vp_depth_first_deep().
Referenced by llvm::VPlanTransforms::createAndOptimizeReplicateRegions().
|
static |
Definition at line 2010 of file VPlanTransforms.cpp.
References llvm::VPInstruction::ActiveLaneMask, llvm::VPUser::addOperand(), llvm::VPInstruction::BranchOnCond, llvm::VPInstruction::CalculateTripCountMinusVF, llvm::VPInstruction::CanonicalIVIncrementForPart, llvm::VPBuilder::createNaryOp(), llvm::VPBuilder::createNot(), llvm::VPBuilder::createOverflowingOp(), llvm::DataAndControlFlowWithoutRuntimeCheck, DL, llvm::VPRecipeBase::eraseFromParent(), llvm::VPlan::getCanonicalIV(), llvm::VPBlockBase::getExitingBasicBlock(), llvm::VPBasicBlock::getTerminator(), llvm::VPlan::getTripCount(), llvm::VPlan::getVectorLoopRegion(), llvm::VPlan::getVectorPreheader(), and llvm::VPBuilder::setInsertPoint().
Referenced by llvm::VPlanTransforms::addActiveLaneMask().
|
static |
Returns true if V
is VPWidenLoadRecipe or VPInterleaveRecipe that can be converted to a narrower recipe.
V
is used by a wide recipe that feeds a store interleave group at index Idx
, WideMember0
is the recipe feeding the same interleave group at index 0. A VPWidenLoadRecipe can be narrowed to an index-independent load if it feeds all wide ops at all indices (OpV
must be the operand at index OpIdx
for both the recipe at lane 0, WideMember0
). A VPInterleaveRecipe can be narrowed to a wide load, if V
is defined at Idx
of a load interleave group.
Definition at line 3561 of file VPlanTransforms.cpp.
References llvm::VPValue::getDefiningRecipe(), llvm::VPUser::getOperand(), Idx, IR, and OpIdx.
|
static |
Definition at line 613 of file VPlanTransforms.cpp.
References llvm::VPDef::definedValues(), llvm::from_range, I, and Users.
Referenced by llvm::VPlanTransforms::clearReductionWrapFlags(), legalizeAndOptimizeInductions(), and transformRecipestoEVLRecipes().
|
static |
Definition at line 338 of file VPlanTransforms.cpp.
References assert(), llvm::VPBlockUtils::connectBlocks(), llvm::VPlan::createVPBasicBlock(), llvm::VPlan::createVPRegionBlock(), llvm::VPRecipeBase::eraseFromParent(), llvm::VPValue::getDefiningRecipe(), llvm::VPReplicateRecipe::getMask(), llvm::VPValue::getNumUsers(), llvm::VPSingleDefRecipe::getUnderlyingInstr(), llvm::VPBlockUtils::insertTwoBlocksAfter(), llvm::VPReplicateRecipe::isSingleScalar(), llvm::make_range(), llvm::VPUser::op_begin(), llvm::VPUser::op_end(), llvm::VPValue::replaceAllUsesWith(), and llvm::VPUser::setOperand().
Referenced by addReplicateRegions().
|
static |
Definition at line 575 of file VPlanTransforms.cpp.
References assert(), llvm::VPBuilder::createDerivedIV(), llvm::VPBuilder::createScalarCast(), llvm::VPBuilder::createScalarIVSteps(), DL, llvm::VPlan::getCanonicalIV(), llvm::VPBlockBase::getEntryBasicBlock(), llvm::Type::getScalarSizeInBits(), llvm::VPBlockBase::getSingleHierarchicalPredecessor(), llvm::Value::getType(), llvm::VPlan::getVectorLoopRegion(), llvm::VPlan::getVF(), llvm::VPTypeAnalysis::inferScalarType(), llvm::Type::isIntegerTy(), and llvm::VPBuilder::setInsertPoint().
Referenced by legalizeAndOptimizeInductions().
|
static |
Expand a VPWidenIntOrFpInduction into executable recipes, for the initial value, phi and backedge value.
In the following example:
vector.ph: Successor(s): vector loop
<x1> vector loop: { vector.body: WIDEN-INDUCTION i = phi start, step, vf ... EMIT branch-on-count ... No successors }
WIDEN-INDUCTION will get expanded to:
vector.ph: ... vp<induction.start> = ... vp<induction.increment> = ...
Successor(s): vector loop
<x1> vector loop: { vector.body: ir<i> = WIDEN-PHI vp<induction.start>, vp<vec.ind.next> ... vp<vec.ind.next> = add ir<i>, vp<induction.increment> EMIT branch-on-count ... No successors }
Definition at line 2770 of file VPlanTransforms.cpp.
References llvm::VPUser::addOperand(), assert(), llvm::VPInstruction::Broadcast, llvm::VPBuilder::createNaryOp(), llvm::VPBuilder::createScalarCast(), llvm::VPBuilder::createScalarZExtOrTrunc(), llvm::VPBuilder::createWidenCast(), DL, llvm::IntegerType::get(), llvm::VPlan::getContext(), llvm::VPRecipeBase::getDebugLoc(), llvm::VPValue::getDefiningRecipe(), llvm::VPBlockBase::getExitingBasicBlock(), llvm::VPWidenInductionRecipe::getInductionDescriptor(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::VPWidenIntOrFpInductionRecipe::getLastUnrolledPartOperand(), llvm::VPRecipeBase::getParent(), llvm::VPWidenInductionRecipe::getPHINode(), llvm::VPBlockBase::getPlan(), llvm::Type::getScalarSizeInBits(), llvm::VPWidenIntOrFpInductionRecipe::getSplatVFValue(), llvm::VPHeaderPHIRecipe::getStartValue(), llvm::VPWidenInductionRecipe::getStepValue(), llvm::VPBasicBlock::getTerminator(), llvm::VPlan::getVectorLoopRegion(), llvm::VPlan::getVectorPreheader(), llvm::VPWidenInductionRecipe::getVFValue(), llvm::InductionDescriptor::IK_IntInduction, llvm::VPTypeAnalysis::inferScalarType(), llvm::Type::isFloatingPointTy(), llvm::Type::isIntegerTy(), llvm::VPValue::replaceAllUsesWith(), llvm::VPBuilder::setInsertPoint(), and llvm::VPInstruction::StepVector.
Referenced by llvm::VPlanTransforms::convertToConcreteRecipes().
|
static |
Expand a VPWidenPointerInductionRecipe into executable recipes, for the initial value, phi and backedge value.
In the following example:
<x1> vector loop: { vector.body: EMIT ir<ptr.iv> = WIDEN-POINTER-INDUCTION start, step, vf ... EMIT branch-on-count ... }
WIDEN-POINTER-INDUCTION will get expanded to:
<x1> vector loop: { vector.body: EMIT-SCALAR pointer.phi = phi start, ptr.ind EMIT mul = mul stepvector, step EMIT vector.gep = wide-ptradd pointer.phi, mul ... EMIT ptr.ind = ptradd pointer.phi, vf EMIT branch-on-count ... }
Definition at line 2882 of file VPlanTransforms.cpp.
References llvm::VPUser::addOperand(), assert(), llvm::VPBuilder::createNaryOp(), llvm::VPBuilder::createPtrAdd(), llvm::VPBuilder::createScalarPhi(), llvm::VPBuilder::createScalarZExtOrTrunc(), DL, llvm::VPBlockBase::getExitingBasicBlock(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::VPBasicBlock::getTerminator(), llvm::VPlan::getVectorLoopRegion(), llvm::VPlan::hasScalableVF(), llvm::InductionDescriptor::IK_PtrInduction, llvm::VPTypeAnalysis::inferScalarType(), llvm::Type::isPointerTy(), llvm::Offset, llvm::VPBuilder::setInsertPoint(), llvm::VPInstruction::StepVector, and llvm::VPInstruction::WidePtrAdd.
Referenced by llvm::VPlanTransforms::convertToConcreteRecipes().
|
static |
Collect the header mask with the pattern: (ICMP_ULE, WideCanonicalIV, backedge-taken-count) TODO: Introduce explicit recipe for header-mask instead of searching for the header-mask pattern manually.
Definition at line 2085 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 transformRecipestoEVLRecipes().
|
static |
Check if VPV
is an untruncated wide induction, either before or after the increment.
If so return the header IV (before the increment), otherwise return null.
Definition at line 719 of file VPlanTransforms.cpp.
References llvm::VPValue::getDefiningRecipe(), llvm::ScalarEvolution::getNegativeSCEV(), llvm::vputils::getSCEVExprForVPValue(), llvm::InductionDescriptor::IK_PtrInduction, llvm_unreachable, llvm::PatternMatch::m_c_Add(), llvm::VPlanPatternMatch::m_GetElementPtr(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Sub(), llvm::VPlanPatternMatch::m_VPValue(), and llvm::PatternMatch::match().
Referenced by optimizeEarlyExitInductionUser(), and optimizeLatchExitInductionUser().
VPValue * getPredicatedMask | ( | VPRegionBlock * | R | ) |
If R
is a region with a VPBranchOnMaskRecipe in the entry block, return the mask.
Definition at line 217 of file VPlanTransforms.cpp.
Referenced by mergeReplicateRegionsIntoSuccessors().
|
static |
If R
is a triangle region, return the 'then' block of the triangle.
Definition at line 227 of file VPlanTransforms.cpp.
Referenced by mergeReplicateRegionsIntoSuccessors().
|
static |
Try to hoist Previous
and its operands before all users of FOR
.
Definition at line 1640 of file VPlanTransforms.cpp.
References A, llvm::all_of(), assert(), B, llvm::VPBasicBlock::getEnclosingLoopRegion(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::VPDef::getNumDefinedValues(), llvm::VPBlockBase::getParent(), llvm::VPRecipeBase::getParent(), llvm::VPDef::getVPSingleValue(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::VPRecipeBase::mayHaveSideEffects(), llvm::VPRecipeBase::mayReadFromMemory(), llvm::VPUser::operands(), llvm::VPDominatorTree::properlyDominates(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SmallVectorBase< Size_T >::size(), and llvm::sort().
Referenced by llvm::VPlanTransforms::adjustFixedOrderRecurrences().
Returns true if VPValue
is a narrow VPValue.
Definition at line 3608 of file VPlanTransforms.cpp.
References llvm::VPValue::isLiveIn().
Referenced by llvm::VPlanTransforms::narrowInterleaveGroups().
|
static |
Return true if Cond
is known to be true for given BestVF
and BestUF
.
Definition at line 1447 of file VPlanTransforms.cpp.
References llvm::any_of(), assert(), llvm::CallingConv::C, Cond, llvm::VPlan::getCanonicalIV(), llvm::ScalarEvolution::getElementCount(), llvm::vputils::getSCEVExprForVPValue(), llvm::VPlan::getTripCount(), llvm::SCEV::getType(), llvm::VPlan::getVectorTripCount(), llvm::CmpInst::ICMP_EQ, llvm::ScalarEvolution::isKnownPredicate(), llvm::VPlanPatternMatch::m_BinaryOr(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_SpecificICmp(), llvm::VPlanPatternMatch::m_VPValue(), llvm::PatternMatch::match(), and llvm::details::FixedOrScalableQuantity< LeafTy, ValueTy >::multiplyCoefficientBy().
Referenced by simplifyBranchConditionForVFAndUF().
|
static |
Returns true if IR
is a full interleave group with factor and number of members both equal to VF
.
The interleave group must also access the full vector width VectorRegWidth
.
Definition at line 3577 of file VPlanTransforms.cpp.
References llvm::all_of(), llvm::VPDef::definedValues(), llvm::VPInterleaveRecipe::getInterleaveGroup(), llvm::Type::getScalarSizeInBits(), llvm::VPInterleaveRecipe::getStoredValues(), llvm::VPDef::getVPValue(), and llvm::VPTypeAnalysis::inferScalarType().
Referenced by llvm::VPlanTransforms::narrowInterleaveGroups().
|
static |
Returns true if R
is dead and can be removed.
Definition at line 531 of file VPlanTransforms.cpp.
References llvm::all_of(), and llvm::PatternMatch::match().
Referenced by recursivelyDeleteDeadRecipes(), and llvm::VPlanTransforms::removeDeadRecipes().
|
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). Legalize extract-from-ends using uniform VPReplicateRecipe of wide inductions to use regular VPReplicateRecipe, so the correct end value is available. 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 637 of file VPlanTransforms.cpp.
References collectUsersRecursively(), llvm::VPBuilder::createPtrAdd(), createScalarIVSteps(), llvm::VPRecipeBase::getDebugLoc(), llvm::VPBlockBase::getEntryBasicBlock(), llvm::VPBasicBlock::getFirstNonPhi(), llvm::VPlan::getOrAddLiveIn(), llvm::VPlan::getVectorLoopRegion(), llvm::VPlan::hasScalableVF(), llvm::VPlan::hasScalarVFOnly(), llvm::InductionDescriptor::IK_IntInduction, llvm::vputils::isSingleScalar(), llvm::none_of(), llvm::vputils::onlyFirstLaneUsed(), llvm::VPBasicBlock::phis(), llvm::VPValue::replaceAllUsesWith(), llvm::reverse(), and Users.
Referenced by llvm::VPlanTransforms::optimize().
|
static |
Move loop-invariant recipes out of the vector loop region in Plan
.
Definition at line 1803 of file VPlanTransforms.cpp.
References llvm::any_of(), llvm::VPBasicBlock::end(), llvm::VPRegionBlock::getEntry(), llvm::VPlan::getVectorLoopRegion(), llvm::VPlan::getVectorPreheader(), llvm::make_early_inc_range(), and llvm::vp_depth_first_shallow().
Remove redundant VPBasicBlocks by merging them into their predecessor if the predecessor has a single successor.
Definition at line 413 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().
Definition at line 249 of file VPlanTransforms.cpp.
References assert(), llvm::VPBlockUtils::connectBlocks(), llvm::SmallPtrSetImpl< PtrType >::contains(), llvm::VPBlockUtils::disconnectBlocks(), llvm::SmallPtrSetImplBase::empty(), llvm::VPlan::getEntry(), llvm::VPBasicBlock::getFirstNonPhi(), getPredicatedMask(), getPredicatedThenBlock(), llvm::VPBlockBase::getSingleSuccessor(), llvm::SmallPtrSetImpl< PtrType >::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().
|
static |
Definition at line 1261 of file VPlanTransforms.cpp.
References llvm::VPRegionBlock::getEntry(), llvm::VPlan::getVectorLoopRegion(), llvm::VPlan::hasScalarVFOnly(), llvm::vputils::isSingleScalar(), llvm::make_early_inc_range(), llvm::vputils::onlyScalarValuesUsed(), llvm::reverse(), and llvm::vp_depth_first_shallow().
Referenced by llvm::VPlanTransforms::optimize().
|
static |
Attempts to optimize the induction variable exit values for users in the early exit block.
Definition at line 777 of file VPlanTransforms.cpp.
References B, DL, llvm::VPInstruction::FirstActiveLane, llvm::VPlan::getCanonicalIV(), getOptimizableIVOf(), llvm::VPlan::getOrAddLiveIn(), llvm::VPCanonicalIVPHIRecipe::getScalarType(), llvm::VPTypeAnalysis::inferScalarType(), llvm::VPlanPatternMatch::m_VPValue(), and llvm::PatternMatch::match().
Referenced by llvm::VPlanTransforms::optimizeInductionExitUsers().
|
static |
Attempts to optimize the induction variable exit values for users in the exit block coming from the latch in the original scalar loop.
Definition at line 832 of file VPlanTransforms.cpp.
References assert(), B, getOptimizableIVOf(), llvm::VPlan::getOrAddLiveIn(), llvm::VPTypeAnalysis::inferScalarType(), llvm::Type::isFloatingPointTy(), llvm::Type::isIntegerTy(), llvm::Type::isPointerTy(), llvm_unreachable, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::lookup(), llvm::VPlanPatternMatch::m_ExtractLastElement(), llvm::VPlanPatternMatch::m_VPValue(), and llvm::PatternMatch::match().
Referenced by llvm::VPlanTransforms::optimizeInductionExitUsers().
|
static |
Try to optimize a CurRecipe
masked by HeaderMask
to a corresponding EVL-based recipe without the header mask.
Returns nullptr if no EVL-based recipe could be created. HeaderMask
Header Mask. CurRecipe
Recipe to be transform. TypeInfo
VPlan-based type analysis. AllOneMask
The vector mask parameter of vector-predication intrinsics. EVL
The explicit vector length parameter of vector-predication intrinsics.
Adjust any end pointers so that they point to the end of EVL lanes not VF.
Definition at line 2170 of file VPlanTransforms.cpp.
References Addr, llvm::all_of(), assert(), llvm::TypeSwitch< T, ResultT >::Case(), llvm::VPVectorEndPointerRecipe::clone(), llvm::Default, llvm::VPWidenMemoryRecipe::getAddr(), llvm::VPRecipeBase::getDebugLoc(), llvm::VPWidenMemoryRecipe::getMask(), llvm::VPTypeAnalysis::inferScalarType(), llvm::VPRecipeBase::insertBefore(), LHS, llvm::PatternMatch::m_LogicalAnd(), llvm::PatternMatch::m_Select(), llvm::PatternMatch::m_Specific(), llvm::VPlanPatternMatch::m_VPValue(), llvm::PatternMatch::match(), RHS, and llvm::VPUser::setOperand().
Referenced by transformRecipestoEVLRecipes().
|
static |
Optimize the width of vector induction variables in Plan
based on a known constant Trip Count, BestVF
and BestUF
.
Definition at line 1376 of file VPlanTransforms.cpp.
References llvm::VPBasicBlock::appendRecipe(), llvm::IntegerType::get(), llvm::APInt::getActiveBits(), llvm::APInt::getBitWidth(), llvm::VPlan::getContext(), llvm::VPBlockBase::getEntryBasicBlock(), llvm::details::FixedOrScalableQuantity< LeafTy, ValueTy >::getKnownMinValue(), llvm::VPlan::getOrAddLiveIn(), llvm::VPlan::getOrCreateBackedgeTakenCount(), llvm::VPlan::getTripCount(), llvm::VPValue::getUnderlyingValue(), llvm::VPlan::getVectorLoopRegion(), llvm::VPlan::getVectorPreheader(), llvm::details::FixedOrScalableQuantity< LeafTy, ValueTy >::isFixed(), llvm::VPValue::isLiveIn(), llvm::VPlanPatternMatch::m_Broadcast(), llvm::PatternMatch::m_ICmp(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::match(), llvm::VPBasicBlock::phis(), llvm::PowerOf2Ceil(), llvm::APIntOps::RoundingUDiv(), and llvm::APInt::UP.
Referenced by llvm::VPlanTransforms::optimizeForVFAndUF().
|
static |
Definition at line 921 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 simplifyBlends(), and transformRecipestoEVLRecipes().
|
static |
Try to replace VPWidenCanonicalIVRecipes with a widened canonical IV recipe, if it exists.
Definition at line 498 of file VPlanTransforms.cpp.
References llvm::VPRecipeBase::eraseFromParent(), llvm::VPlan::getCanonicalIV(), llvm::VPBlockBase::getEntryBasicBlock(), llvm::VPlan::getVectorLoopRegion(), llvm::vputils::onlyFirstLaneUsed(), llvm::vputils::onlyScalarValuesUsed(), llvm::VPBasicBlock::phis(), llvm::VPValue::replaceAllUsesWith(), and llvm::VPValue::users().
Referenced by llvm::VPlanTransforms::optimize().
|
static |
Remove redundant EpxandSCEVRecipes in Plan's
entry block by replacing them with already existing recipes expanding the same SCEV expression.
Definition at line 904 of file VPlanTransforms.cpp.
References llvm::VPlan::getEntry(), llvm::VPBlockBase::getEntryBasicBlock(), llvm::make_early_inc_range(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::try_emplace().
Referenced by llvm::VPlanTransforms::optimize().
|
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 465 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().
|
static |
Normalize and simplify VPBlendRecipes.
Should be run after simplifyRecipes to make sure the masks are simplified.
Simplify BLEND a, b, Not(mask) -> BLEND b, a, mask.
Definition at line 1297 of file VPlanTransforms.cpp.
References llvm::SmallPtrSetImpl< PtrType >::begin(), llvm::VPRegionBlock::getEntry(), llvm::VPValue::getNumUsers(), llvm::VPlan::getVectorLoopRegion(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::VPlanPatternMatch::m_False(), llvm::MIPatternMatch::m_Not(), llvm::VPlanPatternMatch::m_VPValue(), llvm::make_early_inc_range(), llvm::PatternMatch::match(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), recursivelyDeleteDeadRecipes(), llvm::VPValue::replaceAllUsesWith(), llvm::SmallPtrSetImplBase::size(), and llvm::vp_depth_first_shallow().
Referenced by llvm::VPlanTransforms::optimize().
|
static |
Try to simplify the branch condition of Plan
.
This may restrict the resulting plan to BestVF
and BestUF
.
Definition at line 1479 of file VPlanTransforms.cpp.
References llvm::all_of(), llvm::VPBasicBlock::appendRecipe(), assert(), B, llvm::VPBasicBlock::back(), llvm::VPInstruction::BranchOnCond, llvm::CallingConv::C, Cond, llvm::VPBlockUtils::connectBlocks(), llvm::VPBuilder::createNaryOp(), llvm::VPBlockUtils::disconnectBlocks(), llvm::ScalarEvolution::getElementCount(), llvm::VPRegionBlock::getEntry(), llvm::VPBlockBase::getExitingBasicBlock(), llvm::vputils::getSCEVExprForVPValue(), llvm::PredicatedScalarEvolution::getSE(), llvm::VPBlockBase::getSinglePredecessor(), llvm::VPBlockBase::getSingleSuccessor(), llvm::VPlan::getTripCount(), llvm::VPlan::getTrue(), llvm::SCEV::getType(), llvm::VPlan::getVectorLoopRegion(), llvm::VPlan::getVectorPreheader(), llvm::VPDef::getVPSingleValue(), llvm::CmpInst::ICMP_ULE, isConditionTrueViaVFAndUF(), llvm::ScalarEvolution::isKnownPredicate(), llvm::SCEV::isZero(), llvm::VPlanPatternMatch::m_ActiveLaneMask(), llvm::VPlanPatternMatch::m_BranchOnCond(), llvm::VPlanPatternMatch::m_BranchOnCount(), llvm::MIPatternMatch::m_Not(), llvm::VPlanPatternMatch::m_VPValue(), llvm::make_early_inc_range(), llvm::PatternMatch::match(), llvm::details::FixedOrScalableQuantity< LeafTy, ValueTy >::multiplyCoefficientBy(), llvm::VPValue::replaceAllUsesWith(), llvm::VPlanTransforms::simplifyRecipes(), llvm::VPInstruction::StepVector, and llvm::vp_depth_first_shallow().
Referenced by llvm::VPlanTransforms::optimizeForVFAndUF().
|
static |
Try to simplify recipe R
.
Definition at line 994 of file VPlanTransforms.cpp.
References A, llvm::all_of(), assert(), llvm::CallingConv::C, llvm::VPBuilder::createWidenCast(), llvm::Default, DL, llvm::CmpInst::getInversePredicate(), llvm::VPlan::getOrAddLiveIn(), llvm::VPlan::getScalarHeader(), llvm::Type::getScalarSizeInBits(), I, Idx, llvm::VPTypeAnalysis::inferScalarType(), llvm::Type::isIntegerTy(), llvm::VPlan::isUnrolled(), llvm::VPInstruction::isVectorToScalar(), llvm::PatternMatch::m_AllOnes(), llvm::VPlanPatternMatch::m_Broadcast(), llvm::VPlanPatternMatch::m_BuildVector(), llvm::VPlanPatternMatch::m_c_BinaryAnd(), llvm::VPlanPatternMatch::m_c_BinaryOr(), llvm::PatternMatch::m_c_Mul(), llvm::PatternMatch::m_Cmp(), llvm::PatternMatch::m_Deferred(), llvm::VPlanPatternMatch::m_DerivedIV(), llvm::VPlanPatternMatch::m_ExtractLastElement(), llvm::PatternMatch::m_LogicalAnd(), llvm::MIPatternMatch::m_Not(), llvm::PatternMatch::m_Select(), llvm::PatternMatch::m_SExt(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_SpecificInt(), llvm::VPlanPatternMatch::m_True(), llvm::PatternMatch::m_Trunc(), llvm::VPlanPatternMatch::m_VPInstruction(), llvm::VPlanPatternMatch::m_VPValue(), llvm::MIPatternMatch::m_ZeroInt(), llvm::PatternMatch::m_ZExtOrSExt(), llvm::PatternMatch::match(), llvm::vputils::onlyFirstLaneUsed(), llvm::to_vector(), tryToFoldLiveIns(), X, and Y.
Referenced by llvm::VPlanTransforms::simplifyRecipes().
|
static |
Sink users of FOR
after the recipe defining the previous value Previous
of the recurrence.
FOR
could be re-arranged as needed or false if it is not possible. Definition at line 1585 of file VPlanTransforms.cpp.
References A, assert(), B, llvm::VPDef::getNumDefinedValues(), llvm::VPDef::getVPSingleValue(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::VPDominatorTree::properlyDominates(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SmallVectorBase< Size_T >::size(), llvm::sort(), and llvm::VPValue::users().
Referenced by llvm::VPlanTransforms::adjustFixedOrderRecurrences().
Definition at line 128 of file VPlanTransforms.cpp.
References llvm::all_of(), llvm::VPSingleDefRecipe::clone(), llvm::VPlan::getEntry(), llvm::VPBlockBase::getEntryBasicBlock(), llvm::VPBlockBase::getExitingBasicBlock(), llvm::VPBasicBlock::getFirstNonPhi(), llvm::VPRecipeBase::getParent(), llvm::VPBlockBase::getSingleSuccessor(), llvm::VPBlockBase::getSuccessors(), llvm::VPSingleDefRecipe::getUnderlyingInstr(), llvm::VPlan::hasScalarVFOnly(), I, llvm::SetVector< T, Vector, Set, N >::insert(), llvm::VPRecipeBase::insertBefore(), llvm::VPRecipeBase::mayHaveSideEffects(), llvm::VPRecipeBase::mayReadOrWriteMemory(), llvm::VPRecipeBase::moveBefore(), llvm::VPUser::operands(), llvm::VPValue::replaceUsesWithIf(), llvm::SetVector< T, Vector, Set, N >::size(), llvm::SmallVectorBase< Size_T >::size(), llvm::VPValue::users(), and llvm::vp_depth_first_deep().
Referenced by llvm::VPlanTransforms::createAndOptimizeReplicateRegions().
Replace recipes with their EVL variants.
Definition at line 2238 of file VPlanTransforms.cpp.
References llvm::all_of(), llvm::any_of(), assert(), collectUsersRecursively(), llvm::VPBuilder::createICmp(), llvm::VPBuilder::createNaryOp(), llvm::VPBuilder::createScalarPhi(), llvm::VPBuilder::createScalarZExtOrTrunc(), findHeaderMask(), llvm::VPlan::getContext(), llvm::VPValue::getDefiningRecipe(), llvm::VPRegionBlock::getEntry(), llvm::VPBlockBase::getEntryBasicBlock(), llvm::Type::getInt32Ty(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::VPDef::getNumDefinedValues(), llvm::VPValue::getNumUsers(), llvm::VPlan::getOrAddLiveIn(), llvm::VPRecipeBase::getParent(), llvm::VPRegionBlock::getPreheaderVPBB(), llvm::ConstantInt::getSigned(), llvm::VPlan::getTrue(), llvm::VPlan::getVectorLoopRegion(), llvm::VPlan::getVF(), llvm::VPlan::getVFxUF(), llvm::VPDef::getVPSingleValue(), llvm::CmpInst::ICMP_ULT, Idx, llvm::VPTypeAnalysis::inferScalarType(), llvm::VPRecipeBase::insertBefore(), llvm::IsaPred, llvm::VPlanPatternMatch::m_VPValue(), llvm::PatternMatch::match(), optimizeMaskToEVL(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), recursivelyDeleteDeadRecipes(), llvm::VPValue::replaceAllUsesWith(), llvm::VPValue::replaceUsesWithIf(), llvm::reverse(), llvm::VPBuilder::setInsertPoint(), llvm::VPInstruction::StepVector, llvm::VPValue::users(), and llvm::vp_depth_first_deep().
Referenced by llvm::VPlanTransforms::addExplicitVectorLength().
|
static |
This function tries to create abstract recipes from the reduction recipe for following optimizations and cost estimation.
Definition at line 3250 of file VPlanTransforms.cpp.
References llvm::VPRecipeBase::insertBefore(), Range, tryToMatchAndCreateExtendedReduction(), and tryToMatchAndCreateMulAccumulateReduction().
Referenced by llvm::VPlanTransforms::convertToAbstractRecipes().
|
static |
Try to fold R
using InstSimplifyFolder.
Will succeed and return a non-nullptr Value for a handled Opcode
if corresponding Operands
are foldable live-ins.
Definition at line 943 of file VPlanTransforms.cpp.
References assert(), DL, llvm::drop_begin(), llvm::InstSimplifyFolder::FoldBinOp(), llvm::InstSimplifyFolder::FoldCast(), llvm::InstSimplifyFolder::FoldCmp(), llvm::InstSimplifyFolder::FoldGEP(), llvm::InstSimplifyFolder::FoldSelect(), GEP, llvm::Constant::getAllOnesValue(), llvm::VPTypeAnalysis::getContext(), llvm::Type::getInt8Ty(), llvm::Constant::getNullValue(), getType(), llvm::VPTypeAnalysis::inferScalarType(), llvm::Instruction::isBinaryOp(), llvm::Instruction::isCast(), llvm::VPInstruction::LogicalAnd, llvm::VPInstruction::Not, Operands, llvm::VPInstruction::PtrAdd, llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::VPInstruction::WidePtrAdd.
Referenced by simplifyRecipe().
|
static |
This function tries convert extended in-loop reductions to VPExpressionRecipe and clamp the Range
if it is beneficial and valid.
The created recipe must be decomposed to its constituent recipes before execution.
Definition at line 3106 of file VPlanTransforms.cpp.
References A, CostKind, llvm::LoopVectorizationPlanner::getDecisionAndClampRange(), llvm::TargetTransformInfo::getExtendedReductionCost(), llvm::RecurrenceDescriptor::getOpcode(), llvm::VPTypeAnalysis::inferScalarType(), llvm::InstructionCost::isValid(), llvm::VPlanPatternMatch::m_VPValue(), llvm::PatternMatch::m_ZExtOrSExt(), llvm::PatternMatch::match(), Range, llvm::TargetTransformInfo::TCK_RecipThroughput, llvm::toVectorTy(), llvm::VPCostContext::TTI, and llvm::VPCostContext::Types.
Referenced by tryToCreateAbstractReductionRecipe().
|
static |
This function tries convert extended in-loop reductions to VPExpressionRecipe and clamp the Range
if it is beneficial and valid.
The created VPExpressionRecipe must be decomposed to its constituent recipes before execution. Patterns of the VPExpressionRecipe: reduce.add(mul(...)), reduce.add(mul(ext(A), ext(B))), reduce.add(ext(mul(ext(A), ext(B)))).
Definition at line 3151 of file VPlanTransforms.cpp.
References A, B, CostKind, llvm::LoopVectorizationPlanner::getDecisionAndClampRange(), llvm::VPValue::getDefiningRecipe(), llvm::TargetTransformInfo::getMulAccReductionCost(), llvm::RecurrenceDescriptor::getOpcode(), if(), llvm::VPTypeAnalysis::inferScalarType(), llvm::VPRecipeBase::insertBefore(), llvm::InstructionCost::isValid(), llvm::PatternMatch::m_Mul(), llvm::VPlanPatternMatch::m_VPValue(), llvm::PatternMatch::m_ZExtOrSExt(), llvm::PatternMatch::match(), llvm::Mul, Range, llvm::TargetTransformInfo::TCK_RecipThroughput, llvm::toVectorTy(), llvm::VPCostContext::TTI, and llvm::VPCostContext::Types.
Referenced by tryToCreateAbstractReductionRecipe().