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/ADT/ScopeExit.h"
20#include "llvm/Analysis/TargetTransformInfo.h"
21#include "llvm/Support/Compiler.h"
22
23namespace llvm {
24
25class BranchProbabilityInfo;
26class InductionDescriptor;
27class Instruction;
28class Loop;
29class LoopVersioning;
30class OptimizationRemarkEmitter;
31class PHINode;
32class ScalarEvolution;
33class PredicatedScalarEvolution;
34class RuntimePointerChecking;
35class TargetLibraryInfo;
36class TargetTransformInfo;
37class VPRecipeBuilder;
38struct VFRange;
39
40struct VPlanTransforms {
41 /// Abort if -vplan-verify-each is set and \p Plan is invalid.
42 LLVM_ABI_FOR_TEST static void verifyIfRequested(VPlan &Plan);
43
44#ifndef NDEBUG
45 LLVM_ABI_FOR_TEST static bool isPrintingRequested(const VPlan &Plan);
46
47 /// Print \p Plan of \p Fn before or after the pass \p NumberedPassName if
48 /// requested.
49 LLVM_ABI_FOR_TEST static void printIfRequested(VPlan &Plan, Function *Fn,
50 StringRef NumberedPassName,
51 bool After);
52#endif
53
54 /// Helper to run a VPlan pass \p Pass on \p VPlan, forwarding extra arguments
55 /// to the pass. Performs verification/printing after each VPlan pass if
56 /// requested via command line options.
57 template <bool EnableVerify = true, typename PassTy, typename... ArgsTy>
58 static decltype(auto) runPass(StringRef PassName, PassTy &&Pass, VPlan &Plan,
59 ArgsTy &&...Args) {
60#ifndef NDEBUG
61 static DenseMap<std::pair<Function *, StringRef /* Pass */>, unsigned>
62 PassCounter;
63 Function *Fn = Plan.getScalarHeader()->getIRBasicBlock()->getParent();
64 // Computing these is expensive, so only do it if any VPlan printing has
65 // been requested.
66 unsigned Instance;
67 std::string NumberedPassName;
68
69 if (isPrintingRequested(Plan)) {
70 Instance = ++PassCounter[{Fn, PassName}];
71
72 NumberedPassName = Instance == 1
73 ? PassName.str()
74 : (PassName + "@" + Twine(Instance)).str();
75 }
76
77 printIfRequested(Plan, Fn, NumberedPassName, /*After=*/false);
78#endif
79
80 scope_exit PostTransformActions{[&]() {
81#ifndef NDEBUG
82 // Make sure to print before verification, so that output is more useful
83 // in case of failures:
84 printIfRequested(Plan, Fn, NumberedPassName, /*After=*/true);
85#endif
86 if (EnableVerify)
87 verifyIfRequested(Plan);
88 }};
89
90 return std::forward<PassTy>(Pass)(Plan, std::forward<ArgsTy>(Args)...);
91 }
92#define RUN_VPLAN_PASS(PASS, ...) \
93 llvm::VPlanTransforms::runPass(#PASS, PASS, __VA_ARGS__)
94#define RUN_VPLAN_PASS_NO_VERIFY(PASS, ...) \
95 llvm::VPlanTransforms::runPass<false>(#PASS, PASS, __VA_ARGS__)
96
97 /// Create a base VPlan0, serving as the common starting point for all later
98 /// candidates. It consists of an initial plain CFG loop with loop blocks from
99 /// \p TheLoop being directly translated to VPBasicBlocks with VPInstruction
100 /// corresponding to the input IR.
101 ///
102 /// The created loop is wrapped in an initial skeleton to facilitate
103 /// vectorization, consisting of a vector pre-header, an exit block for the
104 /// main vector loop (middle.block) and a new block as preheader of the scalar
105 /// loop (scalar.ph). See below for an illustration. It also creates a
106 /// VPValue expression for the original trip count.
107 ///
108 /// [ ] <-- Plan's entry VPIRBasicBlock, wrapping the original loop's
109 /// / \ old preheader. Will contain iteration number check and SCEV
110 /// | | expansions.
111 /// | |
112 /// / v
113 /// | [ ] <-- vector loop bypass (may consist of multiple blocks) will be
114 /// | / | added later.
115 /// | / v
116 /// || [ ] <-- vector pre header.
117 /// |/ |
118 /// | v
119 /// | [ ] \ <-- plain CFG loop wrapping original loop to be vectorized.
120 /// | [ ]_|
121 /// | |
122 /// | v
123 /// | [ ] <--- middle-block with the branch to successors
124 /// | / |
125 /// | / |
126 /// | | v
127 /// \--->[ ] <--- scalar preheader (initial a VPBasicBlock, which will be
128 /// | | replaced later by a VPIRBasicBlock wrapping the scalar
129 /// | | preheader basic block.
130 /// | |
131 /// v <-- edge from middle to exit iff epilogue is not required.
132 /// | [ ] \
133 /// | [ ]_| <-- old scalar loop to handle remainder (scalar epilogue,
134 /// | | header wrapped in VPIRBasicBlock).
135 /// \ |
136 /// \ v
137 /// >[ ] <-- original loop exit block(s), wrapped in VPIRBasicBlocks.
138 LLVM_ABI_FOR_TEST static std::unique_ptr<VPlan>
139 buildVPlan0(Loop *TheLoop, LoopInfo &LI, Type *InductionTy,
140 PredicatedScalarEvolution &PSE, LoopVersioning *LVer = nullptr,
141 function_ref<const BranchProbabilityInfo &()> GetBPI = nullptr);
142
143 /// Add execution frequencies to each recipe in the loop body of \p Plan.
144 /// Frequencies are computed from the branch weights in \p Plan.
145 static void recordExecutionFrequencies(VPlan &Plan);
146
147 /// Replace VPPhi recipes in \p Plan's header with corresponding
148 /// VPHeaderPHIRecipe subclasses for inductions, reductions, and
149 /// fixed-order recurrences. This processes all header phis and creates
150 /// the appropriate widened recipe for each one. For fixed-order
151 /// recurrences, also creates FirstOrderRecurrenceSplice instructions and
152 /// sinks/hoists users as needed. Returns false if any fixed-order
153 /// recurrence cannot be handled.
154 LLVM_ABI_FOR_TEST static bool createHeaderPhiRecipes(
155 VPlan &Plan, PredicatedScalarEvolution &PSE, Loop &OrigLoop,
156 OptimizationRemarkEmitter *ORE, const VPDominatorTree &VPDT,
157 const MapVector<PHINode *, InductionDescriptor> &Inductions,
158 const MapVector<PHINode *, RecurrenceDescriptor> &Reductions,
159 const SmallPtrSetImpl<const PHINode *> &FixedOrderRecurrences,
160 const SmallPtrSetImpl<PHINode *> &InLoopReductions, bool AllowReordering);
161
162 /// Finalize SCEV predicates by adding induction predicates from \p Plan to
163 /// \p PSE and checking constraints. Returns false if predicated IVs have
164 /// outside-loop uses via ExitingIVValue, if SCEV predicate complexity exceeds
165 /// \p SCEVCheckThreshold, or if predicates are needed but \p OptForSize is
166 /// true.
167 static bool
168 finalizeSCEVPredicates(VPlan &Plan, PredicatedScalarEvolution &PSE,
169 bool OptForSize, unsigned SCEVCheckThreshold,
170 OptimizationRemarkEmitter *ORE, Loop *TheLoop);
171
172 /// Create VPReductionRecipes for in-loop reductions. This processes chains
173 /// of operations contributing to in-loop reductions and creates appropriate
174 /// VPReductionRecipe instances.
175 static void createInLoopReductionRecipes(VPlan &Plan, ElementCount MinVF);
176
177 /// If a check is needed to guard executing the scalar epilogue loop, it will
178 /// be added to the middle block.
179 LLVM_ABI_FOR_TEST static void addMiddleCheck(VPlan &Plan);
180
181 // Create a check in \p CheckBlock to see if the vector loop should be
182 // executed. May create VPExpandSCEV recipes in the plan's entry block.
183 static void addMinimumIterationCheck(
184 VPlan &Plan, ElementCount VF, unsigned UF,
185 ElementCount MinProfitableTripCount, bool RequiresScalarEpilogue,
186 bool TailFolded, Loop *OrigLoop, const uint32_t *MinItersBypassWeights,
187 DebugLoc DL, PredicatedScalarEvolution &PSE, VPBasicBlock *CheckBlock);
188
189 /// Add a new check block before the vector preheader to \p Plan to check if
190 /// the main vector loop should be executed (TC >= VF * UF).
191 static void
192 addIterationCountCheckBlock(VPlan &Plan, ElementCount VF, unsigned UF,
193 bool RequiresScalarEpilogue, Loop *OrigLoop,
194 const uint32_t *MinItersBypassWeights,
195 DebugLoc DL, PredicatedScalarEvolution &PSE);
196
197 /// Add a check to \p Plan to see if the epilogue vector loop should be
198 /// executed.
199 static void addMinimumVectorEpilogueIterationCheck(
200 VPlan &Plan, VPValue *MainVectorTripCount, bool RequiresScalarEpilogue,
201 ElementCount EpilogueVF, unsigned MainLoopStep, unsigned EpilogueLoopStep,
202 ScalarEvolution &SE);
203
204 /// Replace loops in \p Plan's flat CFG with VPRegionBlocks, turning \p Plan's
205 /// flat CFG into a hierarchical CFG. For the outermost loop, also create the
206 /// canonical IV's increment and adjust the latch terminator: replace
207 /// BranchOnCond with BranchOnCount, using \p DL for the canonical IV.
208 LLVM_ABI_FOR_TEST static void createLoopRegions(VPlan &Plan, DebugLoc DL);
209
210 /// Connect \p CheckBlock to \p Plan, branching on \p Cond.
211 static void attachVPCheckBlock(VPlan &Plan, VPValue *Cond,
212 VPBasicBlock *CheckBlock,
213 bool AddBranchWeights);
214 static void attachCheckBlock(VPlan &Plan, Value *Cond, BasicBlock *CheckBlock,
215 bool AddBranchWeights);
216
217 /// Generate the memory runtime checks of \p RtPtrChecking as recipes and
218 /// attach the check block to \p Plan. \p VF and \p UF are used to compute
219 /// the thresholds of difference checks.
220 static void attachMemoryChecks(VPlan &Plan,
221 const RuntimePointerChecking &RtPtrChecking,
222 ScalarEvolution &SE, ElementCount VF,
223 unsigned UF, DebugLoc DL,
224 bool AddBranchWeights);
225
226 /// Model the blocks the executed \p MainPlan generated for the main vector
227 /// loop in \p EpiPlan during epilogue vectorization, wrapping each in a
228 /// VPIRBasicBlock, with \p EnteredFrom the block \p EpiPlan is entered from.
229 /// Edges from blocks bypassing both vector loops are redirected to \p
230 /// EpiPlan's scalar preheader, all others are mirrored.
231 static void modelGeneratedMainLoopBlocks(VPlan &EpiPlan, VPlan &MainPlan,
232 VPIRBasicBlock *EnteredFrom);
233
234 /// Replaces the VPInstructions in \p Plan with corresponding
235 /// widen recipes. Returns false if any VPInstructions could not be converted
236 /// to a wide recipe if needed. Uses \p PSE to detect contiguous memory
237 /// accesses w.r.t. the \p OuterLoop induction variable.
238 LLVM_ABI_FOR_TEST static bool tryToConvertVPInstructionsToVPRecipes(
239 VPlan &Plan, const TargetLibraryInfo &TLI, PredicatedScalarEvolution &PSE,
240 Loop *OuterLoop);
241
242 /// Try to legalize reductions with multiple in-loop uses. Currently only
243 /// strict and non-strict min/max reductions used by FindLastIV reductions are
244 /// supported, corresponding to computing the first and last argmin/argmax,
245 /// respectively. Otherwise return false.
246 static bool handleMultiUseReductions(VPlan &Plan,
247 OptimizationRemarkEmitter *ORE,
248 Loop *TheLoop);
249
250 /// Check if \p Plan contains any FMaxNum or FMinNum reductions. If they do,
251 /// try to update the vector loop to exit early if any input is NaN and resume
252 /// executing in the scalar loop to handle the NaNs there. Return false if
253 /// this attempt was unsuccessful.
254 static bool handleMaxMinNumReductions(VPlan &Plan);
255
256 /// Check if \p Plan contains any FindLast reductions. If it does, try to
257 /// update the vector loop to save the appropriate state using selects
258 /// for entire vectors for both the latest mask containing at least one active
259 /// element and the corresponding data vector. Return false if this attempt
260 /// was unsuccessful.
261 static bool handleFindLastReductions(VPlan &Plan);
262
263 /// Clear NSW/NUW flags from reduction instructions if necessary.
264 static void clearReductionWrapFlags(VPlan &Plan);
265
266 /// Explicitly unroll \p Plan by \p UF.
267 static void unrollByUF(VPlan &Plan, unsigned UF);
268
269 /// Replace replicating VPReplicateRecipe, VPScalarIVStepsRecipe and
270 /// VPInstruction in \p Plan with \p VF single-scalar recipes, packed into
271 /// BuildVectors for vector users. Replicate regions are dissolved by
272 /// replicating their blocks and their recipes \p VF times.
273 /// TODO: Also dissolve replicate regions with live outs.
274 static void replicateByVF(VPlan &Plan, ElementCount VF);
275
276 /// Optimize \p Plan based on \p BestVF and \p BestUF. This may restrict the
277 /// resulting plan to \p BestVF and \p BestUF.
278 static void optimizeForVFAndUF(VPlan &Plan, ElementCount BestVF,
279 unsigned BestUF,
280 PredicatedScalarEvolution &PSE);
281
282 /// Try to simplify VPInstruction::ExplicitVectorLength recipes when the AVL
283 /// is known to be <= VF, replacing them with the AVL directly.
284 static bool simplifyKnownEVL(VPlan &Plan, ElementCount VF,
285 PredicatedScalarEvolution &PSE);
286
287 /// Apply VPlan-to-VPlan optimizations to \p Plan, including induction recipe
288 /// optimizations, dead recipe removal, replicate region optimizations and
289 /// block merging.
290 LLVM_ABI_FOR_TEST static void optimize(VPlan &Plan);
291
292 /// Remove redundant VPBasicBlocks by merging them into their single
293 /// predecessor if the latter has a single successor.
294 static bool mergeBlocksIntoPredecessors(VPlan &Plan);
295
296 /// Wrap predicated VPReplicateRecipes with a mask operand in an if-then
297 /// region block and remove the mask operand. Optimize the created regions by
298 /// iteratively sinking scalar operands into the region, followed by merging
299 /// regions until no improvements are remaining.
300 static void createAndOptimizeReplicateRegions(VPlan &Plan);
301
302 /// Materialize the abstract header mask of the loop region into concrete
303 /// recipes: an active-lane-mask if \p UseActiveLaneMask (with a PHI if \p
304 /// UseActiveLaneMaskForControlFlow), else (WideCanonicalIV icmp ule BTC).
305 static void materializeHeaderMask(VPlan &Plan, bool UseActiveLaneMask,
306 bool UseActiveLaneMaskForControlFlow);
307
308 /// Insert truncates and extends for any truncated recipe. Redundant casts
309 /// will be folded later.
310 static void
311 truncateToMinimalBitwidths(VPlan &Plan,
312 const MapVector<Instruction *, uint64_t> &MinBWs);
313
314 /// Check \p Plan's live-ins and replace them with constants, if they can be
315 /// simplified via SCEV.
316 static void simplifyLiveInsWithSCEV(VPlan &Plan,
317 PredicatedScalarEvolution &PSE);
318
319 /// Replace symbolic strides from \p StridesMap in \p Plan with constants when
320 /// possible.
321 static void replaceSymbolicStrides(VPlan &Plan,
322 PredicatedScalarEvolution &PSE,
323 const SymbolicStrideMap &StridesMap,
324 const VPDominatorTree &VPDT);
325
326 /// Drop poison flags from recipes that may generate a poison value that is
327 /// used after vectorization, even when their operands are not poison. Those
328 /// recipes meet the following conditions:
329 /// * Contribute to the address computation of a recipe generating a widen
330 /// memory load/store (VPWidenMemoryInstructionRecipe or
331 /// VPInterleaveRecipe).
332 /// * Such a widen memory load/store is masked, but not with the header mask.
333 static void dropPoisonGeneratingRecipes(VPlan &Plan);
334
335 /// Add a VPCurrentIterationPHIRecipe and related recipes to \p Plan and
336 /// replaces all uses of the canonical IV except for the canonical IV
337 /// increment with a VPCurrentIterationPHIRecipe. The canonical IV is only
338 /// used to control the loop after this transformation.
339 static void
340 addExplicitVectorLength(VPlan &Plan,
341 const std::optional<unsigned> &MaxEVLSafeElements);
342
343 /// Optimize recipes which use an EVL-based header mask to VP intrinsics, for
344 /// example:
345 ///
346 /// %mask = icmp ult step-vector, EVL
347 /// %load = load %ptr, %mask
348 /// -->
349 /// %load = vp.load %ptr, EVL
350 static void optimizeEVLMasks(VPlan &Plan);
351
352 // For each Interleave Group in \p InterleaveGroups replace the Recipes
353 // widening its memory instructions with a single VPInterleaveRecipe at its
354 // insertion point.
355 static void createInterleaveGroups(
356 VPlan &Plan,
357 const SmallPtrSetImpl<const InterleaveGroup<Instruction> *>
358 &InterleaveGroups,
359 const bool &EpilogueAllowed);
360
361 /// Transform widen memory recipes into strided access recipes when legal
362 /// and profitable. Clamps \p Range to maintain consistency with widen
363 /// decisions of \p Plan, and uses \p Ctx to evaluate the cost.
364 static void convertToStridedAccesses(VPlan &Plan,
365 PredicatedScalarEvolution &PSE, Loop &L,
366 VPCostContext &Ctx, VFRange &Range);
367
368 /// Remove dead recipes from \p Plan.
369 static void removeDeadRecipes(VPlan &Plan);
370
371 /// Check if all loads in the loop are dereferenceable. Iterates over the
372 /// loop body blocks reachable from \p HeaderVPBB. Returns false if any
373 /// non-dereferenceable load is found.
374 static bool areAllLoadsDereferenceable(VPBasicBlock *HeaderVPBB,
375 Loop *TheLoop,
376 PredicatedScalarEvolution &PSE,
377 DominatorTree &DT,
378 AssumptionCache *AC);
379
380 /// If a single exit has multiple conditions combined together, split them
381 /// and create new exiting blocks. Currently limited to a single exit in the
382 /// latch block.
383 static bool splitCombinedExits(VPlan &Plan, PredicatedScalarEvolution &PSE,
384 Loop *TheLoop);
385
386 /// Update \p Plan to account for uncountable early exits by introducing
387 /// appropriate branching logic in the latch that handles early exits and the
388 /// latch exit condition. Multiple exits are handled with a dispatch block
389 /// that determines which exit to take based on lane-by-lane semantics.
390 LLVM_ABI_FOR_TEST static bool
391 handleUncountableEarlyExits(VPlan &Plan, OptimizationRemarkEmitter *ORE,
392 Loop *TheLoop, PredicatedScalarEvolution &PSE,
393 DominatorTree &DT, AssumptionCache *AC,
394 UncountableExitStyle Style);
395
396 /// Disconnect countable early exits from the loop.
397 LLVM_ABI_FOR_TEST static void handleCountableEarlyExits(VPlan &Plan);
398
399 /// Replaces the exit condition from
400 /// (branch-on-cond eq CanonicalIVInc, VectorTripCount)
401 /// to
402 /// (branch-on-cond eq AVLNext, 0)
403 static void convertEVLExitCond(VPlan &Plan);
404
405 /// Replace loop regions with explicit CFG.
406 static void dissolveLoopRegions(VPlan &Plan);
407
408 /// Expand BranchOnTwoConds instructions into explicit CFG with
409 /// BranchOnCond instructions. Should be called after dissolveLoopRegions.
410 static void expandBranchOnTwoConds(VPlan &Plan);
411
412 /// Transform loops with variable-length stepping after region
413 /// dissolution.
414 ///
415 /// Once loop regions are replaced with explicit CFG, loops can step with
416 /// variable vector lengths instead of fixed lengths. This transformation:
417 /// * Makes CurrentIteration-Phi concrete.
418 // * Removes CanonicalIV and increment.
419 static void convertToVariableLengthStep(VPlan &Plan);
420
421 /// Lower abstract recipes to concrete ones, that can be codegen'd.
422 static void convertToConcreteRecipes(VPlan &Plan);
423
424 /// This function converts initial recipes to the abstract recipes and clamps
425 /// \p Range based on cost model for following optimizations and cost
426 /// estimations. The converted abstract recipes will lower to concrete
427 /// recipes before codegen.
428 static void convertToAbstractRecipes(VPlan &Plan, VPCostContext &Ctx,
429 VFRange &Range);
430
431 /// Perform instcombine-like simplifications on recipes in \p Plan.
432 static void combineRecipes(VPlan &Plan);
433
434 /// Cancel out redundant reverses in \p Plan, e.g. reverse(reverse(x)) -> x.
435 static void simplifyReverses(VPlan &Plan);
436
437 /// Remove BranchOnCond recipes with true or false conditions together with
438 /// removing dead edges to their successors. If \p OnlyLatches is true, only
439 /// process loop latches. Returns true if incoming values from any phi-like
440 /// recipe have been removed.
441 static bool removeBranchOnConst(VPlan &Plan, bool OnlyLatches = false);
442
443 /// Perform common-subexpression-elimination on \p Plan.
444 static void cse(VPlan &Plan, const VPDominatorTree &VPDT);
445
446 /// Replace each VPExpandSCEVRecipe in \p Plan's entry block with an earlier
447 /// VPExpandSCEVRecipe there expanding the same SCEV, if any.
448 static void removeRedundantExpandSCEVRecipes(VPlan &Plan);
449
450 /// If there's a single exit block, optimize its phi recipes that use exiting
451 /// IV values by feeding them precomputed end values instead, possibly taken
452 /// one step backwards.
453 static void optimizeInductionLiveOutUsers(VPlan &Plan,
454 PredicatedScalarEvolution &PSE,
455 const Loop *L);
456
457 /// Add explicit broadcasts for live-ins and VPValues defined in \p Plan's entry block if they are used as vectors.
458 static void materializeBroadcasts(VPlan &Plan);
459
460 /// Hoist predicated loads from the same address to the loop entry block, if
461 /// they are guaranteed to execute on both paths (i.e., in replicate regions
462 /// with complementary masks P and NOT P).
463 static void hoistPredicatedLoads(VPlan &Plan, PredicatedScalarEvolution &PSE,
464 const Loop *L);
465
466 /// Sink predicated stores to the same address with complementary predicates
467 /// (P and NOT P) to an unconditional store with select recipes for the
468 /// stored values. This eliminates branching overhead when all paths
469 /// unconditionally store to the same location.
470 static void sinkPredicatedStores(VPlan &Plan, PredicatedScalarEvolution &PSE,
471 const Loop *L);
472
473 /// Widens memory operations by a factor of UF based on a target hook.
474 /// This allows targets to use wider memory operations when profitable.
475 static void widenMemoryAccessesByUF(VPlan &Plan, ElementCount VF, unsigned UF,
476 const TargetTransformInfo &TTI);
477
478 // Materialize vector trip counts for constants early if it can simply be
479 // computed as (Original TC / VF * UF) * VF * UF.
480 static void
481 materializeConstantVectorTripCount(VPlan &Plan, ElementCount BestVF,
482 unsigned BestUF,
483 PredicatedScalarEvolution &PSE);
484
485 /// Materialize vector trip count computations to a set of VPInstructions.
486 /// \p Step is used as the step value for the trip count computation.
487 /// \p MaxRuntimeStep is the maximum possible runtime value of Step, used to
488 /// prove the trip count is divisible by the step for scalable VFs.
489 static void materializeVectorTripCount(
490 VPlan &Plan, VPBasicBlock *VectorPHVPBB, bool TailByMasking,
491 bool RequiresScalarEpilogue, VPValue *Step,
492 std::optional<uint64_t> MaxRuntimeStep = std::nullopt);
493
494 /// Materialize the backedge-taken count to be computed explicitly using
495 /// VPInstructions.
496 static void materializeBackedgeTakenCount(VPlan &Plan,
497 VPBasicBlock *VectorPH);
498
499 /// Add explicit Unpack recipes to extract scalars from vectors as needed.
500 static void materializeUnpacks(VPlan &Plan);
501
502 /// Materialize UF, VF and VFxUF to be computed explicitly using
503 /// VPInstructions.
504 static void materializeFactors(VPlan &Plan, VPBasicBlock *VectorPH,
505 ElementCount VF);
506
507 /// Attaches the alias-mask to the existing header-mask.
508 static void attachAliasMaskToHeaderMask(VPlan &Plan);
509
510 /// Materializes within the \p AliasCheckVPBB block. Updates the header mask
511 /// of the loop to use the alias mask. Returns the clamped VF.
512 static VPValue *materializeAliasMask(VPlan &Plan,
513 VPBasicBlock *AliasCheckVPBB,
514 ArrayRef<PointerDiffInfo> DiffChecks);
515
516 /// Materializes the alias mask within a check block before the loop. The
517 /// vector loop will only be entered if the clamped VF from the alias mask
518 /// is not scalar.
519 static void materializeAliasMaskCheckBlock(
520 VPlan &Plan, ArrayRef<PointerDiffInfo> DiffChecks, bool HasBranchWeights);
521
522 /// Expand VPExpandSCEVRecipes in \p Plan's entry block to VPInstructions.
523 /// Recipes wrapping a SCEVAddRecExpr are kept for later IR-level expansion.
524 static void expandSCEVsToVPInstructions(VPlan &Plan, ScalarEvolution &SE);
525
526 /// Expand remaining VPExpandSCEVRecipes in \p Plan's entry block using
527 /// SCEVExpander. Each VPExpandSCEVRecipe is replaced with a live-in wrapping
528 /// the expanded IR value. A mapping from SCEV expressions to their expanded
529 /// IR value is returned.
530 static DenseMap<const SCEV *, Value *> expandSCEVs(VPlan &Plan,
531 ScalarEvolution &SE);
532
533 /// Try to find a single VF among \p Plan's VFs for which all interleave
534 /// groups (with known minimum VF elements) can be replaced by wide loads and
535 /// stores processing VF elements, if all transformed interleave groups access
536 /// the full vector width (checked via the maximum vector register width). If
537 /// the transformation can be applied, the original \p Plan will be split in
538 /// 2:
539 /// 1. The original Plan with the single VF containing the optimized recipes
540 /// using wide loads instead of interleave groups.
541 /// 2. A new clone which contains all VFs of Plan except the optimized VF.
542 ///
543 /// This effectively is a very simple form of loop-aware SLP, where we use
544 /// interleave groups to identify candidates.
545 static std::unique_ptr<VPlan>
546 narrowInterleaveGroups(VPlan &Plan, const TargetTransformInfo &TTI);
547
548 /// Adapts the vector loop region for tail folding by introducing a header
549 /// mask and conditionally executing the content of the region:
550 ///
551 /// Vector loop region before:
552 /// +-------------------------------------------+
553 /// |%iv = ... |
554 /// |... |
555 /// |%iv.next = add %iv, vfxuf |
556 /// |branch-on-count %iv.next, vector-trip-count|
557 /// +-------------------------------------------+
558 ///
559 /// Vector loop region after:
560 /// +-------------------------------------------+
561 /// |%iv = ... |
562 /// |%wide.iv = widen-canonical-iv ... |
563 /// |%header-mask = icmp ule %wide.iv, BTC |
564 /// |branch-on-cond %header-mask |---+
565 /// +-------------------------------------------+ |
566 /// | |
567 /// v |
568 /// +-------------------------------------------+ |
569 /// | ... | |
570 /// +-------------------------------------------+ |
571 /// | |
572 /// v |
573 /// +-------------------------------------------+ |
574 /// |<phis> = phi [..., ...], [poison, header] |
575 /// |%iv.next = add %iv, vfxuf |<--+
576 /// |branch-on-count %iv.next, vector-trip-count|
577 /// +-------------------------------------------+
578 ///
579 /// Any VPInstruction::ExtractLastLanes are also updated to extract from the
580 /// last active lane of the header mask.
581 static void foldTailByMasking(VPlan &Plan);
582
583 /// Predicate and linearize the control-flow in the only loop region of
584 /// \p Plan.
585 static void introduceMasksAndLinearize(VPlan &Plan);
586
587 /// Replace a VPWidenCanonicalIVRecipe if it is present in \p Plan, with a
588 /// VPWidenIntOrFpInductionRecipe, provided it would not cause additional
589 /// spills for \p VF at unroll factor \p UF.
590 static void
591 replaceWideCanonicalIVWithWideIV(VPlan &Plan, ScalarEvolution &SE,
592 const TargetTransformInfo &TTI,
593 TargetTransformInfo::TargetCostKind CostKind,
594 ElementCount VF, unsigned UF);
595
596 /// Add branch weight metadata, if the \p Plan's middle block is terminated by
597 /// a BranchOnCond recipe.
598 static void
599 addBranchWeightToMiddleTerminator(VPlan &Plan, ElementCount VF,
600 std::optional<unsigned> VScaleForTuning);
601
602 /// Adjust first-order recurrence users in the middle block: create
603 /// penultimate element extracts for LCSSA phi users, and handle penultimate
604 /// extracts of the last active lane edge.
605 static void adjustFirstOrderRecurrenceMiddleUsers(VPlan &Plan,
606 VFRange &Range);
607
608 /// Optimize FindLast reductions selecting IVs (or expressions of IVs) by
609 /// converting them to FindIV reductions, if their IV range excludes a
610 /// suitable sentinel value. For expressions of IVs, the expression is sunk
611 /// to the middle block. The decision is based on SCEV expressions for \p L,
612 /// so this must run before any transform that changes the plan's iteration
613 /// space relative to \p L.
614 static void optimizeFindIVReductions(VPlan &Plan,
615 PredicatedScalarEvolution &PSE, Loop &L);
616
617 /// Detect and create partial reduction recipes for scaled or unordered
618 /// reductions in \p Plan. Must be called after recipe construction. If
619 /// partial reductions are only valid for a subset of VFs in Range, Range.End
620 /// is updated.
621 static void createPartialReductions(VPlan &Plan, VPCostContext &CostCtx,
622 VFRange &Range);
623
624 /// Convert load/store VPInstructions in \p Plan into widened or replicate
625 /// recipes. Non load/store input instructions are left unchanged.
626 static void makeMemOpWideningDecisions(VPlan &Plan, VFRange &Range,
627 VPRecipeBuilder &RecipeBuilder,
628 VPCostContext &CostCtx);
629
630 /// Make VPlan-based scalarization decision prior to delegating to the ones
631 /// made by the legacy CM. Only transforms "usesFirstLaneOnly` def-use chains
632 /// enabled by prior widening of consecutive memory operations and calls for
633 /// now.
634 static void makeScalarizationDecisions(VPlan &Plan, VFRange &Range);
635
636 /// Convert call VPInstructions in \p Plan into widened call, vector
637 /// intrinsic or replicate recipes based on a cost comparison via \p CostCtx.
638 /// Returns true if any call was widened.
639 static bool makeCallWideningDecisions(VPlan &Plan, VFRange &Range,
640 VPRecipeBuilder &RecipeBuilder,
641 VPCostContext &CostCtx);
642
643 /// Replace truncates of a wide induction, or of that induction's increment,
644 /// by a VPWidenIntOrFpInductionRecipe producing the truncated type directly.
645 /// The canonical induction is narrowed even when the target reports the
646 /// truncate as free. If narrowing is only profitable for a subset of VFs in
647 /// \p Range, Range.End is updated.
648 static void narrowInductionTruncates(VPlan &Plan, VFRange &Range,
649 const TargetTransformInfo &TTI,
650 PredicatedScalarEvolution &PSE);
651};
652
653} // namespace llvm
654
655#endif // LLVM_TRANSFORMS_VECTORIZE_VPLANTRANSFORMS_H
656