403 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8///9/// \file10/// This file provides utility VPlan to VPlan transformations.11//===----------------------------------------------------------------------===//12 13#ifndef LLVM_TRANSFORMS_VECTORIZE_VPLANTRANSFORMS_H14#define LLVM_TRANSFORMS_VECTORIZE_VPLANTRANSFORMS_H15 16#include "VPlan.h"17#include "VPlanVerifier.h"18#include "llvm/ADT/STLFunctionalExtras.h"19#include "llvm/Support/CommandLine.h"20#include "llvm/Support/Compiler.h"21 22namespace llvm {23 24class InductionDescriptor;25class Instruction;26class LoopVersioning;27class PHINode;28class ScalarEvolution;29class PredicatedScalarEvolution;30class TargetLibraryInfo;31class VPBuilder;32class VPRecipeBuilder;33struct VFRange;34 35LLVM_ABI_FOR_TEST extern cl::opt<bool> VerifyEachVPlan;36LLVM_ABI_FOR_TEST extern cl::opt<bool> EnableWideActiveLaneMask;37 38struct VPlanTransforms {39 /// Helper to run a VPlan transform \p Transform on \p VPlan, forwarding extra40 /// arguments to the transform. Returns the boolean returned by the transform.41 template <typename... ArgsTy>42 static bool runPass(bool (*Transform)(VPlan &, ArgsTy...), VPlan &Plan,43 typename std::remove_reference<ArgsTy>::type &...Args) {44 bool Res = Transform(Plan, Args...);45 if (VerifyEachVPlan)46 verifyVPlanIsValid(Plan);47 return Res;48 }49 /// Helper to run a VPlan transform \p Transform on \p VPlan, forwarding extra50 /// arguments to the transform.51 template <typename... ArgsTy>52 static void runPass(void (*Fn)(VPlan &, ArgsTy...), VPlan &Plan,53 typename std::remove_reference<ArgsTy>::type &...Args) {54 Fn(Plan, Args...);55 if (VerifyEachVPlan)56 verifyVPlanIsValid(Plan);57 }58 59 /// Create a base VPlan0, serving as the common starting point for all later60 /// candidates. It consists of an initial plain CFG loop with loop blocks from61 /// \p TheLoop being directly translated to VPBasicBlocks with VPInstruction62 /// corresponding to the input IR.63 ///64 /// The created loop is wrapped in an initial skeleton to facilitate65 /// vectorization, consisting of a vector pre-header, an exit block for the66 /// main vector loop (middle.block) and a new block as preheader of the scalar67 /// loop (scalar.ph). See below for an illustration. It also adds a canonical68 /// IV and its increment, using \p InductionTy and \p IVDL, and creates a69 /// VPValue expression for the original trip count.70 ///71 /// [ ] <-- Plan's entry VPIRBasicBlock, wrapping the original loop's72 /// / \ old preheader. Will contain iteration number check and SCEV73 /// | | expansions.74 /// | |75 /// / v76 /// | [ ] <-- vector loop bypass (may consist of multiple blocks) will be77 /// | / | added later.78 /// | / v79 /// || [ ] <-- vector pre header.80 /// |/ |81 /// | v82 /// | [ ] \ <-- plain CFG loop wrapping original loop to be vectorized.83 /// | [ ]_|84 /// | |85 /// | v86 /// | [ ] <--- middle-block with the branch to successors87 /// | / |88 /// | / |89 /// | | v90 /// \--->[ ] <--- scalar preheader (initial a VPBasicBlock, which will be91 /// | | replaced later by a VPIRBasicBlock wrapping the scalar92 /// | | preheader basic block.93 /// | |94 /// v <-- edge from middle to exit iff epilogue is not required.95 /// | [ ] \96 /// | [ ]_| <-- old scalar loop to handle remainder (scalar epilogue,97 /// | | header wrapped in VPIRBasicBlock).98 /// \ |99 /// \ v100 /// >[ ] <-- original loop exit block(s), wrapped in VPIRBasicBlocks.101 LLVM_ABI_FOR_TEST static std::unique_ptr<VPlan>102 buildVPlan0(Loop *TheLoop, LoopInfo &LI, Type *InductionTy, DebugLoc IVDL,103 PredicatedScalarEvolution &PSE, LoopVersioning *LVer = nullptr);104 105 /// Update \p Plan to account for all early exits.106 LLVM_ABI_FOR_TEST static void handleEarlyExits(VPlan &Plan,107 bool HasUncountableExit);108 109 /// If a check is needed to guard executing the scalar epilogue loop, it will110 /// be added to the middle block.111 LLVM_ABI_FOR_TEST static void addMiddleCheck(VPlan &Plan,112 bool RequiresScalarEpilogueCheck,113 bool TailFolded);114 115 // Create a check to \p Plan to see if the vector loop should be executed.116 static void addMinimumIterationCheck(117 VPlan &Plan, ElementCount VF, unsigned UF,118 ElementCount MinProfitableTripCount, bool RequiresScalarEpilogue,119 bool TailFolded, bool CheckNeededWithTailFolding, Loop *OrigLoop,120 const uint32_t *MinItersBypassWeights, DebugLoc DL, ScalarEvolution &SE);121 122 /// Add a check to \p Plan to see if the epilogue vector loop should be123 /// executed.124 static void addMinimumVectorEpilogueIterationCheck(125 VPlan &Plan, Value *TripCount, Value *VectorTripCount,126 bool RequiresScalarEpilogue, ElementCount EpilogueVF, unsigned EpilogueUF,127 unsigned MainLoopStep, unsigned EpilogueLoopStep, ScalarEvolution &SE);128 129 /// Replace loops in \p Plan's flat CFG with VPRegionBlocks, turning \p Plan's130 /// flat CFG into a hierarchical CFG.131 LLVM_ABI_FOR_TEST static void createLoopRegions(VPlan &Plan);132 133 /// Wrap runtime check block \p CheckBlock in a VPIRBB and \p Cond in a134 /// VPValue and connect the block to \p Plan, using the VPValue as branch135 /// condition.136 static void attachCheckBlock(VPlan &Plan, Value *Cond, BasicBlock *CheckBlock,137 bool AddBranchWeights);138 139 /// Replaces the VPInstructions in \p Plan with corresponding140 /// widen recipes. Returns false if any VPInstructions could not be converted141 /// to a wide recipe if needed.142 LLVM_ABI_FOR_TEST static bool tryToConvertVPInstructionsToVPRecipes(143 VPlan &Plan,144 function_ref<const InductionDescriptor *(PHINode *)>145 GetIntOrFpInductionDescriptor,146 const TargetLibraryInfo &TLI);147 148 /// Try to legalize reductions with multiple in-loop uses. Currently only149 /// min/max reductions used by FindLastIV reductions are supported. Otherwise150 /// return false.151 static bool handleMultiUseReductions(VPlan &Plan);152 153 /// Try to have all users of fixed-order recurrences appear after the recipe154 /// defining their previous value, by either sinking users or hoisting recipes155 /// defining their previous value (and its operands). Then introduce156 /// FirstOrderRecurrenceSplice VPInstructions to combine the value from the157 /// recurrence phis and previous values.158 /// \returns true if all users of fixed-order recurrences could be re-arranged159 /// as needed or false if it is not possible. In the latter case, \p Plan is160 /// not valid.161 static bool adjustFixedOrderRecurrences(VPlan &Plan, VPBuilder &Builder);162 163 /// Check if \p Plan contains any FMaxNum or FMinNum reductions. If they do,164 /// try to update the vector loop to exit early if any input is NaN and resume165 /// executing in the scalar loop to handle the NaNs there. Return false if166 /// this attempt was unsuccessful.167 static bool handleMaxMinNumReductions(VPlan &Plan);168 169 /// Clear NSW/NUW flags from reduction instructions if necessary.170 static void clearReductionWrapFlags(VPlan &Plan);171 172 /// Explicitly unroll \p Plan by \p UF.173 static void unrollByUF(VPlan &Plan, unsigned UF);174 175 /// Replace each replicating VPReplicateRecipe and VPInstruction outside of176 /// any replicate region in \p Plan with \p VF single-scalar recipes.177 /// TODO: Also replicate VPScalarIVSteps and VPReplicateRecipes inside178 /// replicate regions, thereby dissolving the latter.179 static void replicateByVF(VPlan &Plan, ElementCount VF);180 181 /// Optimize \p Plan based on \p BestVF and \p BestUF. This may restrict the182 /// resulting plan to \p BestVF and \p BestUF.183 static void optimizeForVFAndUF(VPlan &Plan, ElementCount BestVF,184 unsigned BestUF,185 PredicatedScalarEvolution &PSE);186 187 /// Apply VPlan-to-VPlan optimizations to \p Plan, including induction recipe188 /// optimizations, dead recipe removal, replicate region optimizations and189 /// block merging.190 LLVM_ABI_FOR_TEST static void optimize(VPlan &Plan);191 192 /// Wrap predicated VPReplicateRecipes with a mask operand in an if-then193 /// region block and remove the mask operand. Optimize the created regions by194 /// iteratively sinking scalar operands into the region, followed by merging195 /// regions until no improvements are remaining.196 static void createAndOptimizeReplicateRegions(VPlan &Plan);197 198 /// Replace (ICMP_ULE, wide canonical IV, backedge-taken-count) checks with an199 /// (active-lane-mask recipe, wide canonical IV, trip-count). If \p200 /// UseActiveLaneMaskForControlFlow is true, introduce an201 /// VPActiveLaneMaskPHIRecipe. If \p DataAndControlFlowWithoutRuntimeCheck is202 /// true, no minimum-iteration runtime check will be created (during skeleton203 /// creation) and instead it is handled using active-lane-mask. \p204 /// DataAndControlFlowWithoutRuntimeCheck implies \p205 /// UseActiveLaneMaskForControlFlow.206 static void addActiveLaneMask(VPlan &Plan,207 bool UseActiveLaneMaskForControlFlow,208 bool DataAndControlFlowWithoutRuntimeCheck);209 210 /// Insert truncates and extends for any truncated recipe. Redundant casts211 /// will be folded later.212 static void213 truncateToMinimalBitwidths(VPlan &Plan,214 const MapVector<Instruction *, uint64_t> &MinBWs);215 216 /// Replace symbolic strides from \p StridesMap in \p Plan with constants when217 /// possible.218 static void219 replaceSymbolicStrides(VPlan &Plan, PredicatedScalarEvolution &PSE,220 const DenseMap<Value *, const SCEV *> &StridesMap);221 222 /// Drop poison flags from recipes that may generate a poison value that is223 /// used after vectorization, even when their operands are not poison. Those224 /// recipes meet the following conditions:225 /// * Contribute to the address computation of a recipe generating a widen226 /// memory load/store (VPWidenMemoryInstructionRecipe or227 /// VPInterleaveRecipe).228 /// * Such a widen memory load/store has at least one underlying Instruction229 /// that is in a basic block that needs predication and after vectorization230 /// the generated instruction won't be predicated.231 /// Uses \p BlockNeedsPredication to check if a block needs predicating.232 /// TODO: Replace BlockNeedsPredication callback with retrieving info from233 /// VPlan directly.234 static void dropPoisonGeneratingRecipes(235 VPlan &Plan,236 const std::function<bool(BasicBlock *)> &BlockNeedsPredication);237 238 /// Add a VPEVLBasedIVPHIRecipe and related recipes to \p Plan and239 /// replaces all uses except the canonical IV increment of240 /// VPCanonicalIVPHIRecipe with a VPEVLBasedIVPHIRecipe.241 /// VPCanonicalIVPHIRecipe is only used to control the loop after242 /// this transformation.243 static void244 addExplicitVectorLength(VPlan &Plan,245 const std::optional<unsigned> &MaxEVLSafeElements);246 247 // For each Interleave Group in \p InterleaveGroups replace the Recipes248 // widening its memory instructions with a single VPInterleaveRecipe at its249 // insertion point.250 static void createInterleaveGroups(251 VPlan &Plan,252 const SmallPtrSetImpl<const InterleaveGroup<Instruction> *>253 &InterleaveGroups,254 VPRecipeBuilder &RecipeBuilder, const bool &ScalarEpilogueAllowed);255 256 /// Remove dead recipes from \p Plan.257 static void removeDeadRecipes(VPlan &Plan);258 259 /// Update \p Plan to account for the uncountable early exit from \p260 /// EarlyExitingVPBB to \p EarlyExitVPBB by261 /// * updating the condition exiting the loop via the latch to include the262 /// early exit condition,263 /// * splitting the original middle block to branch to the early exit block264 /// conditionally - according to the early exit condition.265 static void handleUncountableEarlyExit(VPBasicBlock *EarlyExitingVPBB,266 VPBasicBlock *EarlyExitVPBB,267 VPlan &Plan, VPBasicBlock *HeaderVPBB,268 VPBasicBlock *LatchVPBB);269 270 /// Replace loop regions with explicit CFG.271 static void dissolveLoopRegions(VPlan &Plan);272 273 /// Transform EVL loops to use variable-length stepping after region274 /// dissolution.275 ///276 /// Once loop regions are replaced with explicit CFG, EVL loops can step with277 /// variable vector lengths instead of fixed lengths. This transformation:278 /// * Makes EVL-Phi concrete.279 // * Removes CanonicalIV and increment.280 /// * Replaces the exit condition from281 /// (branch-on-count CanonicalIVInc, VectorTripCount)282 /// to283 /// (branch-on-cond eq AVLNext, 0)284 static void canonicalizeEVLLoops(VPlan &Plan);285 286 /// Lower abstract recipes to concrete ones, that can be codegen'd.287 static void convertToConcreteRecipes(VPlan &Plan);288 289 /// This function converts initial recipes to the abstract recipes and clamps290 /// \p Range based on cost model for following optimizations and cost291 /// estimations. The converted abstract recipes will lower to concrete292 /// recipes before codegen.293 static void convertToAbstractRecipes(VPlan &Plan, VPCostContext &Ctx,294 VFRange &Range);295 296 /// Perform instcombine-like simplifications on recipes in \p Plan.297 static void simplifyRecipes(VPlan &Plan);298 299 /// Remove BranchOnCond recipes with true or false conditions together with300 /// removing dead edges to their successors.301 static void removeBranchOnConst(VPlan &Plan);302 303 /// Perform common-subexpression-elimination on \p Plan.304 static void cse(VPlan &Plan);305 306 /// If there's a single exit block, optimize its phi recipes that use exiting307 /// IV values by feeding them precomputed end values instead, possibly taken308 /// one step backwards.309 static void310 optimizeInductionExitUsers(VPlan &Plan,311 DenseMap<VPValue *, VPValue *> &EndValues,312 ScalarEvolution &SE);313 314 /// Add explicit broadcasts for live-ins and VPValues defined in \p Plan's entry block if they are used as vectors.315 static void materializeBroadcasts(VPlan &Plan);316 317 /// Hoist single-scalar loads with invariant addresses out of the vector loop318 /// to the preheader, if they are proven not to alias with any stores in the319 /// plan using noalias metadata.320 static void hoistInvariantLoads(VPlan &Plan);321 322 /// Hoist predicated loads from the same address to the loop entry block, if323 /// they are guaranteed to execute on both paths (i.e., in replicate regions324 /// with complementary masks P and NOT P).325 static void hoistPredicatedLoads(VPlan &Plan, ScalarEvolution &SE,326 const Loop *L);327 328 // Materialize vector trip counts for constants early if it can simply be329 // computed as (Original TC / VF * UF) * VF * UF.330 static void331 materializeConstantVectorTripCount(VPlan &Plan, ElementCount BestVF,332 unsigned BestUF,333 PredicatedScalarEvolution &PSE);334 335 /// Materialize vector trip count computations to a set of VPInstructions.336 static void materializeVectorTripCount(VPlan &Plan,337 VPBasicBlock *VectorPHVPBB,338 bool TailByMasking,339 bool RequiresScalarEpilogue);340 341 /// Materialize the backedge-taken count to be computed explicitly using342 /// VPInstructions.343 static void materializeBackedgeTakenCount(VPlan &Plan,344 VPBasicBlock *VectorPH);345 346 /// Add explicit Build[Struct]Vector recipes to Pack multiple scalar values347 /// into vectors and Unpack recipes to extract scalars from vectors as348 /// needed.349 static void materializePacksAndUnpacks(VPlan &Plan);350 351 /// Materialize VF and VFxUF to be computed explicitly using VPInstructions.352 static void materializeVFAndVFxUF(VPlan &Plan, VPBasicBlock *VectorPH,353 ElementCount VF);354 355 /// Expand VPExpandSCEVRecipes in \p Plan's entry block. Each356 /// VPExpandSCEVRecipe is replaced with a live-in wrapping the expanded IR357 /// value. A mapping from SCEV expressions to their expanded IR value is358 /// returned.359 static DenseMap<const SCEV *, Value *> expandSCEVs(VPlan &Plan,360 ScalarEvolution &SE);361 362 /// Try to convert a plan with interleave groups with VF elements to a plan363 /// with the interleave groups replaced by wide loads and stores processing VF364 /// elements, if all transformed interleave groups access the full vector365 /// width (checked via \o VectorRegWidth). This effectively is a very simple366 /// form of loop-aware SLP, where we use interleave groups to identify367 /// candidates.368 static void narrowInterleaveGroups(VPlan &Plan, ElementCount VF,369 TypeSize VectorRegWidth);370 371 /// Predicate and linearize the control-flow in the only loop region of372 /// \p Plan. If \p FoldTail is true, create a mask guarding the loop373 /// header, otherwise use all-true for the header mask. Masks for blocks are374 /// added to a block-to-mask map which is returned in order to be used later375 /// for wide recipe construction. This argument is temporary and will be376 /// removed in the future.377 static DenseMap<VPBasicBlock *, VPValue *>378 introduceMasksAndLinearize(VPlan &Plan, bool FoldTail);379 380 /// Add branch weight metadata, if the \p Plan's middle block is terminated by381 /// a BranchOnCond recipe.382 static void383 addBranchWeightToMiddleTerminator(VPlan &Plan, ElementCount VF,384 std::optional<unsigned> VScaleForTuning);385 386 /// Update the resume phis in the scalar preheader after creating wide recipes387 /// for first-order recurrences, reductions and inductions. End values for388 /// inductions are added to \p IVEndValues.389 static void390 updateScalarResumePhis(VPlan &Plan,391 DenseMap<VPValue *, VPValue *> &IVEndValues);392 393 /// Handle users in the exit block for first order reductions in the original394 /// exit block. The penultimate value of recurrences is fed to their LCSSA phi395 /// users in the original exit block using the VPIRInstruction wrapping to the396 /// LCSSA phi.397 static void addExitUsersForFirstOrderRecurrences(VPlan &Plan, VFRange &Range);398};399 400} // namespace llvm401 402#endif // LLVM_TRANSFORMS_VECTORIZE_VPLANTRANSFORMS_H403