LLVM 19.0.0git
|
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"
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 void | removeDeadRecipes (VPlan &Plan) |
static VPValue * | 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. | |
This file implements a set of utility VPlan to VPlan transformations.
Definition in file VPlanTransforms.cpp.
|
static |
Definition at line 331 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().
|
static |
Definition at line 1139 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::VPBlockBase::getSinglePredecessor(), llvm::VPBasicBlock::getTerminator(), llvm::VPlan::getTripCount(), llvm::VPlan::getVectorLoopRegion(), and llvm::VPBuilder::setInsertPoint().
Referenced by llvm::VPlanTransforms::addActiveLaneMask().
|
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 1214 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::getOrCreateBackedgeTakenCount(), llvm::VPlan::getVectorLoopRegion(), llvm::CmpInst::ICMP_ULE, llvm::VPBasicBlock::phis(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::VPValue::users().
Referenced by llvm::VPlanTransforms::addActiveLaneMask(), and llvm::VPlanTransforms::addExplicitVectorLength().
|
static |
Definition at line 855 of file VPlanTransforms.cpp.
References llvm::VPDef::definedValues(), I, and Users.
Referenced by llvm::VPlanTransforms::addExplicitVectorLength(), and llvm::VPlanTransforms::clearReductionWrapFlags().
|
static |
Definition at line 295 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().
|
static |
Definition at line 509 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().
VPValue * getPredicatedMask | ( | VPRegionBlock * | R | ) |
If R
is a region with a VPBranchOnMaskRecipe in the entry block, return the mask.
Definition at line 181 of file VPlanTransforms.cpp.
Referenced by mergeReplicateRegionsIntoSuccessors().
|
static |
If R
is a triangle region, return the 'then' block of the triangle.
Definition at line 191 of file VPlanTransforms.cpp.
Referenced by mergeReplicateRegionsIntoSuccessors().
|
static |
Definition at line 710 of file VPlanTransforms.cpp.
References assert().
Referenced by properlyDominates().
|
static |
Returns true if R
is dead and can be removed.
Definition at line 476 of file VPlanTransforms.cpp.
References llvm::all_of(), and llvm::PatternMatch::match().
Referenced by recursivelyDeleteDeadRecipes(), and 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). 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 566 of file VPlanTransforms.cpp.
References createScalarIVSteps(), llvm::VPValue::getDefiningRecipe(), llvm::VPBlockBase::getEntryBasicBlock(), llvm::VPBasicBlock::getFirstNonPhi(), llvm::ElementCount::getFixed(), llvm::VPlan::getOrAddLiveIn(), llvm::VPlan::getVectorLoopRegion(), llvm::VPDef::getVPSingleValue(), 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().
Remove redundant VPBasicBlocks by merging them into their predecessor if the predecessor has a single successor.
Definition at line 361 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 213 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().
|
static |
Definition at line 724 of file VPlanTransforms.cpp.
References A, assert(), B, GetReplicateRegion(), llvm_unreachable, and llvm::DominatorTreeBase< NodeT, IsPostDom >::properlyDominates().
Referenced by sinkRecurrenceUsersAfterPrevious().
|
static |
Definition at line 644 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::addExplicitVectorLength(), and llvm::VPlanTransforms::optimizeForVFAndUF().
|
static |
Definition at line 495 of file VPlanTransforms.cpp.
References llvm::VPlan::getEntry(), isDeadRecipe(), llvm::make_early_inc_range(), and llvm::reverse().
Referenced by llvm::VPlanTransforms::optimize().
|
static |
Try to replace VPWidenCanonicalIVRecipes with a widened canonical IV recipe, if it exists.
Definition at line 439 of file VPlanTransforms.cpp.
References llvm::any_of(), llvm::VPRecipeBase::eraseFromParent(), llvm::VPlan::getCanonicalIV(), llvm::VPBlockBase::getEntryBasicBlock(), llvm::VPWidenCanonicalIVRecipe::getScalarType(), llvm::VPlan::getVectorLoopRegion(), llvm::vputils::onlyFirstLaneUsed(), 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 627 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().
|
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 406 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 |
Try to simplify recipe R
.
Definition at line 886 of file VPlanTransforms.cpp.
References A, assert(), llvm::VPTypeAnalysis::getContext(), llvm::Type::getScalarSizeInBits(), I, llvm::VPTypeAnalysis::inferScalarType(), llvm::PatternMatch::m_CombineOr(), llvm::PatternMatch::m_Mul(), llvm::PatternMatch::m_SExt(), llvm::PatternMatch::m_SpecificInt(), llvm::PatternMatch::m_Trunc(), llvm::PatternMatch::m_ZExtOrSExt(), llvm::PatternMatch::match(), and llvm::VPValue::replaceAllUsesWith().
Referenced by simplifyRecipes().
|
static |
Try to simplify the recipes in Plan
.
Definition at line 949 of file VPlanTransforms.cpp.
References llvm::VPlan::getCanonicalIV(), llvm::VPlan::getEntry(), llvm::VPCanonicalIVPHIRecipe::getScalarType(), llvm::make_early_inc_range(), and simplifyRecipe().
Referenced by llvm::VPlanTransforms::optimize().
|
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 754 of file VPlanTransforms.cpp.
References A, assert(), B, llvm::VPDef::getNumDefinedValues(), llvm::VPDef::getVPSingleValue(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), 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 101 of file VPlanTransforms.cpp.
References llvm::all_of(), 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::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().