//===-- VPlanTransforms.cpp - Utility VPlan to VPlan transforms -----------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// /// /// \file /// This file implements a set of utility VPlan to VPlan transformations. /// //===----------------------------------------------------------------------===// #include "VPlanTransforms.h" #include "VPRecipeBuilder.h" #include "VPlan.h" #include "VPlanAnalysis.h" #include "VPlanCFG.h" #include "VPlanDominatorTree.h" #include "VPlanPatternMatch.h" #include "VPlanUtils.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/VectorUtils.h" #include "llvm/IR/Intrinsics.h" #include "llvm/IR/PatternMatch.h" usingnamespacellvm; void VPlanTransforms::VPInstructionsToVPRecipes( VPlanPtr &Plan, function_ref<const InductionDescriptor *(PHINode *)> GetIntOrFpInductionDescriptor, ScalarEvolution &SE, const TargetLibraryInfo &TLI) { … } static bool sinkScalarOperands(VPlan &Plan) { … } /// If \p R is a region with a VPBranchOnMaskRecipe in the entry block, return /// the mask. VPValue *getPredicatedMask(VPRegionBlock *R) { … } /// If \p R is a triangle region, return the 'then' block of the triangle. static VPBasicBlock *getPredicatedThenBlock(VPRegionBlock *R) { … } // Merge replicate regions in their successor region, if a replicate region // is connected to a successor replicate region with the same predicate by a // single, empty VPBasicBlock. static bool mergeReplicateRegionsIntoSuccessors(VPlan &Plan) { … } static VPRegionBlock *createReplicateRegion(VPReplicateRecipe *PredRecipe, VPlan &Plan) { … } static void addReplicateRegions(VPlan &Plan) { … } /// Remove redundant VPBasicBlocks by merging them into their predecessor if /// the predecessor has a single successor. static bool mergeBlocksIntoPredecessors(VPlan &Plan) { … } void VPlanTransforms::createAndOptimizeReplicateRegions(VPlan &Plan) { … } /// 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. static void removeRedundantInductionCasts(VPlan &Plan) { … } /// Try to replace VPWidenCanonicalIVRecipes with a widened canonical IV /// recipe, if it exists. static void removeRedundantCanonicalIVs(VPlan &Plan) { … } /// Returns true if \p R is dead and can be removed. static bool isDeadRecipe(VPRecipeBase &R) { … } static void removeDeadRecipes(VPlan &Plan) { … } static VPScalarIVStepsRecipe * createScalarIVSteps(VPlan &Plan, InductionDescriptor::InductionKind Kind, Instruction::BinaryOps InductionOpcode, FPMathOperator *FPBinOp, Instruction *TruncI, VPValue *StartV, VPValue *Step, VPBuilder &Builder) { … } /// 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. static void legalizeAndOptimizeInductions(VPlan &Plan) { … } /// Remove redundant EpxandSCEVRecipes in \p Plan's entry block by replacing /// them with already existing recipes expanding the same SCEV expression. static void removeRedundantExpandSCEVRecipes(VPlan &Plan) { … } static void recursivelyDeleteDeadRecipes(VPValue *V) { … } void VPlanTransforms::optimizeForVFAndUF(VPlan &Plan, ElementCount BestVF, unsigned BestUF, PredicatedScalarEvolution &PSE) { … } /// Sink users of \p FOR after the recipe defining the previous value \p /// Previous of the recurrence. \returns true if all users of \p FOR could be /// re-arranged as needed or false if it is not possible. static bool sinkRecurrenceUsersAfterPrevious(VPFirstOrderRecurrencePHIRecipe *FOR, VPRecipeBase *Previous, VPDominatorTree &VPDT) { … } bool VPlanTransforms::adjustFixedOrderRecurrences(VPlan &Plan, VPBuilder &LoopBuilder) { … } static SmallVector<VPUser *> collectUsersRecursively(VPValue *V) { … } void VPlanTransforms::clearReductionWrapFlags(VPlan &Plan) { … } /// Try to simplify recipe \p R. static void simplifyRecipe(VPRecipeBase &R, VPTypeAnalysis &TypeInfo) { … } /// Try to simplify the recipes in \p Plan. static void simplifyRecipes(VPlan &Plan) { … } void VPlanTransforms::truncateToMinimalBitwidths( VPlan &Plan, const MapVector<Instruction *, uint64_t> &MinBWs) { … } void VPlanTransforms::optimize(VPlan &Plan) { … } // Add a VPActiveLaneMaskPHIRecipe and related recipes to \p Plan and replace // the loop terminator with a branch-on-cond recipe with the negated // active-lane-mask as operand. Note that this turns the loop into an // uncountable one. Only the existing terminator is replaced, all other existing // recipes/users remain unchanged, except for poison-generating flags being // dropped from the canonical IV increment. Return the created // VPActiveLaneMaskPHIRecipe. // // The function uses the following definitions: // // %TripCount = DataWithControlFlowWithoutRuntimeCheck ? // calculate-trip-count-minus-VF (original TC) : original TC // %IncrementValue = DataWithControlFlowWithoutRuntimeCheck ? // CanonicalIVPhi : CanonicalIVIncrement // %StartV is the canonical induction start value. // // The function adds the following recipes: // // vector.ph: // %TripCount = calculate-trip-count-minus-VF (original TC) // [if DataWithControlFlowWithoutRuntimeCheck] // %EntryInc = canonical-iv-increment-for-part %StartV // %EntryALM = active-lane-mask %EntryInc, %TripCount // // vector.body: // ... // %P = active-lane-mask-phi [ %EntryALM, %vector.ph ], [ %ALM, %vector.body ] // ... // %InLoopInc = canonical-iv-increment-for-part %IncrementValue // %ALM = active-lane-mask %InLoopInc, TripCount // %Negated = Not %ALM // branch-on-cond %Negated // static VPActiveLaneMaskPHIRecipe *addVPLaneMaskPhiAndUpdateExitBranch( VPlan &Plan, bool DataAndControlFlowWithoutRuntimeCheck) { … } /// 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. static SmallVector<VPValue *> collectAllHeaderMasks(VPlan &Plan) { … } void VPlanTransforms::addActiveLaneMask( VPlan &Plan, bool UseActiveLaneMaskForControlFlow, bool DataAndControlFlowWithoutRuntimeCheck) { … } /// Replace recipes with their EVL variants. static void transformRecipestoEVLRecipes(VPlan &Plan, VPValue &EVL) { … } /// Add a VPEVLBasedIVPHIRecipe and related recipes to \p Plan and /// replaces all uses except the canonical IV increment of /// VPCanonicalIVPHIRecipe with a VPEVLBasedIVPHIRecipe. 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 ] /// %VPEVL = EXPLICIT-VECTOR-LENGTH %EVLPhi, original TC /// ... /// %NextEVLIV = add IVSize (cast i32 %VPEVVL to IVSize), %EVLPhi /// ... /// bool VPlanTransforms::tryAddExplicitVectorLength(VPlan &Plan) { … } void VPlanTransforms::dropPoisonGeneratingRecipes( VPlan &Plan, function_ref<bool(BasicBlock *)> BlockNeedsPredication) { … } void VPlanTransforms::createInterleaveGroups( const SmallPtrSetImpl<const InterleaveGroup<Instruction> *> &InterleaveGroups, VPRecipeBuilder &RecipeBuilder, bool ScalarEpilogueAllowed) { … }