1 //===- VPlanTransforms.h - Utility VPlan to VPlan transforms --------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 /// 9 /// \file 10 /// This file provides utility VPlan to VPlan transformations. 11 //===----------------------------------------------------------------------===// 12 13 #ifndef LLVM_TRANSFORMS_VECTORIZE_VPLANTRANSFORMS_H 14 #define LLVM_TRANSFORMS_VECTORIZE_VPLANTRANSFORMS_H 15 16 #include "VPlan.h" 17 #include "VPlanVerifier.h" 18 #include "llvm/ADT/STLFunctionalExtras.h" 19 #include "llvm/Support/CommandLine.h" 20 21 namespace llvm { 22 23 class InductionDescriptor; 24 class Instruction; 25 class PHINode; 26 class ScalarEvolution; 27 class PredicatedScalarEvolution; 28 class TargetLibraryInfo; 29 class VPBuilder; 30 class VPRecipeBuilder; 31 32 extern cl::opt<bool> VerifyEachVPlan; 33 34 struct VPlanTransforms { 35 /// Helper to run a VPlan transform \p Transform on \p VPlan, forwarding extra 36 /// arguments to the transform. Returns the boolean returned by the transform. 37 template <typename... ArgsTy> 38 static bool runPass(bool (*Transform)(VPlan &, ArgsTy...), VPlan &Plan, 39 typename std::remove_reference<ArgsTy>::type &...Args) { 40 bool Res = Transform(Plan, Args...); 41 if (VerifyEachVPlan) 42 verifyVPlanIsValid(Plan); 43 return Res; 44 } 45 /// Helper to run a VPlan transform \p Transform on \p VPlan, forwarding extra 46 /// arguments to the transform. 47 template <typename... ArgsTy> 48 static void runPass(void (*Fn)(VPlan &, ArgsTy...), VPlan &Plan, 49 typename std::remove_reference<ArgsTy>::type &...Args) { 50 Fn(Plan, Args...); 51 if (VerifyEachVPlan) 52 verifyVPlanIsValid(Plan); 53 } 54 55 /// Replaces the VPInstructions in \p Plan with corresponding 56 /// widen recipes. 57 static void 58 VPInstructionsToVPRecipes(VPlanPtr &Plan, 59 function_ref<const InductionDescriptor *(PHINode *)> 60 GetIntOrFpInductionDescriptor, 61 ScalarEvolution &SE, const TargetLibraryInfo &TLI); 62 63 /// Try to have all users of fixed-order recurrences appear after the recipe 64 /// defining their previous value, by either sinking users or hoisting recipes 65 /// defining their previous value (and its operands). Then introduce 66 /// FirstOrderRecurrenceSplice VPInstructions to combine the value from the 67 /// recurrence phis and previous values. 68 /// \returns true if all users of fixed-order recurrences could be re-arranged 69 /// as needed or false if it is not possible. In the latter case, \p Plan is 70 /// not valid. 71 static bool adjustFixedOrderRecurrences(VPlan &Plan, VPBuilder &Builder); 72 73 /// Clear NSW/NUW flags from reduction instructions if necessary. 74 static void clearReductionWrapFlags(VPlan &Plan); 75 76 /// Explicitly unroll \p Plan by \p UF. 77 static void unrollByUF(VPlan &Plan, unsigned UF, LLVMContext &Ctx); 78 79 /// Optimize \p Plan based on \p BestVF and \p BestUF. This may restrict the 80 /// resulting plan to \p BestVF and \p BestUF. 81 static void optimizeForVFAndUF(VPlan &Plan, ElementCount BestVF, 82 unsigned BestUF, 83 PredicatedScalarEvolution &PSE); 84 85 /// Apply VPlan-to-VPlan optimizations to \p Plan, including induction recipe 86 /// optimizations, dead recipe removal, replicate region optimizations and 87 /// block merging. 88 static void optimize(VPlan &Plan); 89 90 /// Wrap predicated VPReplicateRecipes with a mask operand in an if-then 91 /// region block and remove the mask operand. Optimize the created regions by 92 /// iteratively sinking scalar operands into the region, followed by merging 93 /// regions until no improvements are remaining. 94 static void createAndOptimizeReplicateRegions(VPlan &Plan); 95 96 /// Replace (ICMP_ULE, wide canonical IV, backedge-taken-count) checks with an 97 /// (active-lane-mask recipe, wide canonical IV, trip-count). If \p 98 /// UseActiveLaneMaskForControlFlow is true, introduce an 99 /// VPActiveLaneMaskPHIRecipe. If \p DataAndControlFlowWithoutRuntimeCheck is 100 /// true, no minimum-iteration runtime check will be created (during skeleton 101 /// creation) and instead it is handled using active-lane-mask. \p 102 /// DataAndControlFlowWithoutRuntimeCheck implies \p 103 /// UseActiveLaneMaskForControlFlow. 104 static void addActiveLaneMask(VPlan &Plan, 105 bool UseActiveLaneMaskForControlFlow, 106 bool DataAndControlFlowWithoutRuntimeCheck); 107 108 /// Insert truncates and extends for any truncated recipe. Redundant casts 109 /// will be folded later. 110 static void 111 truncateToMinimalBitwidths(VPlan &Plan, 112 const MapVector<Instruction *, uint64_t> &MinBWs); 113 114 /// Drop poison flags from recipes that may generate a poison value that is 115 /// used after vectorization, even when their operands are not poison. Those 116 /// recipes meet the following conditions: 117 /// * Contribute to the address computation of a recipe generating a widen 118 /// memory load/store (VPWidenMemoryInstructionRecipe or 119 /// VPInterleaveRecipe). 120 /// * Such a widen memory load/store has at least one underlying Instruction 121 /// that is in a basic block that needs predication and after vectorization 122 /// the generated instruction won't be predicated. 123 /// Uses \p BlockNeedsPredication to check if a block needs predicating. 124 /// TODO: Replace BlockNeedsPredication callback with retrieving info from 125 /// VPlan directly. 126 static void dropPoisonGeneratingRecipes( 127 VPlan &Plan, 128 const std::function<bool(BasicBlock *)> &BlockNeedsPredication); 129 130 /// Add a VPEVLBasedIVPHIRecipe and related recipes to \p Plan and 131 /// replaces all uses except the canonical IV increment of 132 /// VPCanonicalIVPHIRecipe with a VPEVLBasedIVPHIRecipe. 133 /// VPCanonicalIVPHIRecipe is only used to control the loop after 134 /// this transformation. 135 /// \returns true if the transformation succeeds, or false if it doesn't. 136 static bool 137 tryAddExplicitVectorLength(VPlan &Plan, 138 const std::optional<unsigned> &MaxEVLSafeElements); 139 140 // For each Interleave Group in \p InterleaveGroups replace the Recipes 141 // widening its memory instructions with a single VPInterleaveRecipe at its 142 // insertion point. 143 static void createInterleaveGroups( 144 VPlan &Plan, 145 const SmallPtrSetImpl<const InterleaveGroup<Instruction> *> 146 &InterleaveGroups, 147 VPRecipeBuilder &RecipeBuilder, const bool &ScalarEpilogueAllowed); 148 149 /// Remove dead recipes from \p Plan. 150 static void removeDeadRecipes(VPlan &Plan); 151 152 /// Update \p Plan to account for the uncountable early exit block in \p 153 /// UncountableExitingBlock by 154 /// * updating the condition exiting the vector loop to include the early 155 /// exit conditions 156 /// * splitting the original middle block to branch to the early exit block 157 /// if taken. 158 static bool handleUncountableEarlyExit(VPlan &Plan, ScalarEvolution &SE, 159 Loop *OrigLoop, 160 BasicBlock *UncountableExitingBlock, 161 VPRecipeBuilder &RecipeBuilder); 162 163 /// Lower abstract recipes to concrete ones, that can be codegen'd. 164 static void convertToConcreteRecipes(VPlan &Plan); 165 166 /// If there's a single exit block, optimize its phi recipes that use exiting 167 /// IV values by feeding them precomputed end values instead, possibly taken 168 /// one step backwards. 169 static void 170 optimizeInductionExitUsers(VPlan &Plan, 171 DenseMap<VPValue *, VPValue *> &EndValues); 172 }; 173 174 } // namespace llvm 175 176 #endif // LLVM_TRANSFORMS_VECTORIZE_VPLANTRANSFORMS_H 177