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 MapVector<PHINode *, ConditionalInductionDescriptor>
160 &ConditionalInductions,
161 const SmallPtrSetImpl<const PHINode *> &FixedOrderRecurrences,
162 const SmallPtrSetImpl<PHINode *> &InLoopReductions, bool AllowReordering);
163
164 /// Finalize SCEV predicates by adding induction predicates from \p Plan to
165 /// \p PSE and checking constraints. Returns false if predicated IVs have
166 /// outside-loop uses via ExitingIVValue, if SCEV predicate complexity exceeds
167 /// \p SCEVCheckThreshold, or if predicates are needed but \p OptForSize is
168 /// true.
169 static bool
170 finalizeSCEVPredicates(VPlan &Plan, PredicatedScalarEvolution &PSE,
171 bool OptForSize, unsigned SCEVCheckThreshold,
172 OptimizationRemarkEmitter *ORE, Loop *TheLoop);
173
174 /// Create VPReductionRecipes for in-loop reductions. This processes chains
175 /// of operations contributing to in-loop reductions and creates appropriate
176 /// VPReductionRecipe instances.
177 static void createInLoopReductionRecipes(VPlan &Plan, ElementCount MinVF);
178
179 /// If a check is needed to guard executing the scalar epilogue loop, it will
180 /// be added to the middle block.
181 LLVM_ABI_FOR_TEST static void addMiddleCheck(VPlan &Plan);
182
183 // Create a check in \p CheckBlock to see if the vector loop should be
184 // executed. May create VPExpandSCEV recipes in the plan's entry block.
185 static void addMinimumIterationCheck(
186 VPlan &Plan, ElementCount VF, unsigned UF,
187 ElementCount MinProfitableTripCount, bool RequiresScalarEpilogue,
188 bool TailFolded, Loop *OrigLoop, const uint32_t *MinItersBypassWeights,
189 DebugLoc DL, PredicatedScalarEvolution &PSE, VPBasicBlock *CheckBlock);
190
191 /// Add a new check block before the vector preheader to \p Plan to check if
192 /// the main vector loop should be executed (TC >= VF * UF).
193 static void
194 addIterationCountCheckBlock(VPlan &Plan, ElementCount VF, unsigned UF,
195 bool RequiresScalarEpilogue, Loop *OrigLoop,
196 const uint32_t *MinItersBypassWeights,
197 DebugLoc DL, PredicatedScalarEvolution &PSE);
198
199 /// Add a check to \p Plan to see if the epilogue vector loop should be
200 /// executed.
201 static void addMinimumVectorEpilogueIterationCheck(
202 VPlan &Plan, VPValue *MainVectorTripCount, bool RequiresScalarEpilogue,
203 ElementCount EpilogueVF, unsigned MainLoopStep, unsigned EpilogueLoopStep,
204 ScalarEvolution &SE);
205
206 /// Replace loops in \p Plan's flat CFG with VPRegionBlocks, turning \p Plan's
207 /// flat CFG into a hierarchical CFG. For the outermost loop, also create the
208 /// canonical IV's increment and adjust the latch terminator: replace
209 /// BranchOnCond with BranchOnCount, using \p DL for the canonical IV.
210 LLVM_ABI_FOR_TEST static void createLoopRegions(VPlan &Plan, DebugLoc DL);
211
212 /// Connect \p CheckBlock to \p Plan, branching on \p Cond.
213 static void attachVPCheckBlock(VPlan &Plan, VPValue *Cond,
214 VPBasicBlock *CheckBlock,
215 bool AddBranchWeights);
216 static void attachCheckBlock(VPlan &Plan, Value *Cond, BasicBlock *CheckBlock,
217 bool AddBranchWeights);
218
219 /// Generate the memory runtime checks of \p RtPtrChecking for \p TheLoop as
220 /// recipes and attach the check block to \p Plan. \p VF and \p UF are used
221 /// to compute the thresholds of difference checks.
222 static void attachMemoryChecks(VPlan &Plan,
223 const RuntimePointerChecking &RtPtrChecking,
224 const Loop *TheLoop, ScalarEvolution &SE,
225 ElementCount VF, unsigned UF,
226 bool AddBranchWeights);
227
228 /// Model the blocks the executed \p MainPlan generated for the main vector
229 /// loop in \p EpiPlan during epilogue vectorization, wrapping each in a
230 /// VPIRBasicBlock. Bypass edges are redirected to \p EpiPlan's scalar
231 /// preheader, or its vector preheader for \p MainCheck, which only bypasses
232 /// the main vector loop. The main vector loop's back-edge is not modeled.
233 /// Returns the block wrapping \p MainPlan's scalar
234 /// preheader, which becomes the epilogue iteration check.
235 static VPIRBasicBlock *modelGeneratedMainLoopBlocks(VPlan &EpiPlan,
236 VPlan &MainPlan,
237 VPBasicBlock *MainCheck);
238
239 /// Replaces the VPInstructions in \p Plan with corresponding
240 /// widen recipes. Returns false if any VPInstructions could not be converted
241 /// to a wide recipe if needed. Uses \p PSE to detect contiguous memory
242 /// accesses w.r.t. the \p OuterLoop induction variable.
243 LLVM_ABI_FOR_TEST static bool tryToConvertVPInstructionsToVPRecipes(
244 VPlan &Plan, const TargetLibraryInfo &TLI, PredicatedScalarEvolution &PSE,
245 Loop *OuterLoop);
246
247 /// Try to legalize reductions with multiple in-loop uses. Currently only
248 /// strict and non-strict min/max reductions used by FindLastIV reductions are
249 /// supported, corresponding to computing the first and last argmin/argmax,
250 /// respectively. Otherwise return false.
251 static bool handleMultiUseReductions(VPlan &Plan,
252 OptimizationRemarkEmitter *ORE,
253 Loop *TheLoop);
254
255 /// Check if \p Plan contains any FMaxNum or FMinNum reductions. If they do,
256 /// try to update the vector loop to exit early if any input is NaN and resume
257 /// executing in the scalar loop to handle the NaNs there. Return false if
258 /// this attempt was unsuccessful.
259 static bool handleMaxMinNumReductions(VPlan &Plan);
260
261 /// Check if \p Plan contains any FindLast reductions. If it does, try to
262 /// update the vector loop to save the appropriate state using selects
263 /// for entire vectors for both the latest mask containing at least one active
264 /// element and the corresponding data vector. Return false if this attempt
265 /// was unsuccessful.
266 static bool handleFindLastReductions(VPlan &Plan);
267
268 /// Widens compressing memory loads/stores. Loads/stores where the pointer is
269 /// derived from a conditional induction PHI are replaced with expandloads or
270 /// compressstores respectively. The backedge value of the conditional
271 /// induction PHI is updated to increment by the number of active lanes of
272 /// the block mask.
273 /// Returns false if any memory operation could not be updated (e.g., due to
274 /// having a mask that does not match the PHI).
275 static bool widenCompressingPatterns(VPlan &Plan,
276 VPRecipeBuilder &RecipeBuilder,
277 ScalarEvolution &SE);
278
279 /// Clear NSW/NUW flags from reduction instructions if necessary.
280 static void clearReductionWrapFlags(VPlan &Plan);
281
282 /// Explicitly unroll \p Plan by \p UF.
283 static void unrollByUF(VPlan &Plan, unsigned UF);
284
285 /// Replace replicating VPReplicateRecipe, VPScalarIVStepsRecipe and
286 /// VPInstruction in \p Plan with \p VF single-scalar recipes, packed into
287 /// BuildVectors for vector users. Replicate regions are dissolved by
288 /// replicating their blocks and their recipes \p VF times.
289 /// TODO: Also dissolve replicate regions with live outs.
290 static void replicateByVF(VPlan &Plan, ElementCount VF);
291
292 /// Optimize \p Plan based on \p BestVF and \p BestUF. This may restrict the
293 /// resulting plan to \p BestVF and \p BestUF.
294 static void optimizeForVFAndUF(VPlan &Plan, ElementCount BestVF,
295 unsigned BestUF,
296 PredicatedScalarEvolution &PSE);
297
298 /// Try to simplify VPInstruction::ExplicitVectorLength recipes when the AVL
299 /// is known to be <= VF, replacing them with the AVL directly.
300 static bool simplifyKnownEVL(VPlan &Plan, ElementCount VF,
301 PredicatedScalarEvolution &PSE);
302
303 /// Apply VPlan-to-VPlan optimizations to \p Plan, including induction recipe
304 /// optimizations, dead recipe removal, replicate region optimizations and
305 /// block merging.
306 LLVM_ABI_FOR_TEST static void optimize(VPlan &Plan);
307
308 /// Remove redundant VPBasicBlocks by merging them into their single
309 /// predecessor if the latter has a single successor.
310 static bool mergeBlocksIntoPredecessors(VPlan &Plan);
311
312 /// Wrap predicated VPReplicateRecipes with a mask operand in an if-then
313 /// region block and remove the mask operand. Optimize the created regions by
314 /// iteratively sinking scalar operands into the region, followed by merging
315 /// regions until no improvements are remaining.
316 static void createAndOptimizeReplicateRegions(VPlan &Plan);
317
318 /// Materialize the abstract header mask of the loop region into concrete
319 /// recipes: an active-lane-mask if \p UseActiveLaneMask (with a PHI if \p
320 /// UseActiveLaneMaskForControlFlow), else (WideCanonicalIV icmp ule BTC).
321 static void materializeHeaderMask(VPlan &Plan, bool UseActiveLaneMask,
322 bool UseActiveLaneMaskForControlFlow);
323
324 /// Insert truncates and extends for any truncated recipe. Redundant casts
325 /// will be folded later.
326 static void
327 truncateToMinimalBitwidths(VPlan &Plan,
328 const MapVector<Instruction *, uint64_t> &MinBWs);
329
330 /// Check \p Plan's live-ins and replace them with constants, if they can be
331 /// simplified via SCEV.
332 static void simplifyLiveInsWithSCEV(VPlan &Plan,
333 PredicatedScalarEvolution &PSE);
334
335 /// Replace symbolic strides from \p StridesMap in \p Plan with constants when
336 /// possible.
337 static void replaceSymbolicStrides(VPlan &Plan,
338 PredicatedScalarEvolution &PSE,
339 const SymbolicStrideMap &StridesMap,
340 const VPDominatorTree &VPDT);
341
342 /// Drop poison flags from recipes that may generate a poison value that is
343 /// used after vectorization, even when their operands are not poison. Those
344 /// recipes meet the following conditions:
345 /// * Contribute to the address computation of a recipe generating a widen
346 /// memory load/store (VPWidenMemoryInstructionRecipe or
347 /// VPInterleaveRecipe).
348 /// * Such a widen memory load/store is masked, but not with the header mask.
349 static void dropPoisonGeneratingRecipes(VPlan &Plan);
350
351 /// Add a VPCurrentIterationPHIRecipe and related recipes to \p Plan and
352 /// replaces all uses of the canonical IV except for the canonical IV
353 /// increment with a VPCurrentIterationPHIRecipe. The canonical IV is only
354 /// used to control the loop after this transformation.
355 static void
356 addExplicitVectorLength(VPlan &Plan,
357 const std::optional<unsigned> &MaxEVLSafeElements);
358
359 /// Optimize recipes which use an EVL-based header mask to VP intrinsics, for
360 /// example:
361 ///
362 /// %mask = icmp ult step-vector, EVL
363 /// %load = load %ptr, %mask
364 /// -->
365 /// %load = vp.load %ptr, EVL
366 static void optimizeEVLMasks(VPlan &Plan);
367
368 // For each Interleave Group in \p InterleaveGroups replace the Recipes
369 // widening its memory instructions with a single VPInterleaveRecipe at its
370 // insertion point.
371 static void createInterleaveGroups(
372 VPlan &Plan,
373 const SmallPtrSetImpl<const InterleaveGroup<Instruction> *>
374 &InterleaveGroups,
375 const bool &EpilogueAllowed);
376
377 /// Transform widen memory recipes into strided access recipes when legal
378 /// and profitable. Clamps \p Range to maintain consistency with widen
379 /// decisions of \p Plan, and uses \p Ctx to evaluate the cost.
380 static void convertToStridedAccesses(VPlan &Plan,
381 PredicatedScalarEvolution &PSE, Loop &L,
382 VPCostContext &Ctx, VFRange &Range);
383
384 /// Expand mask.beforefirst into an active-lane-mask of its first active lane
385 /// for the VFs in \p Range where it is expensive, clamping \p Range so the
386 /// decision is the same for all of its VFs.
387 static void expandMaskBeforeFirst(VPlan &Plan, VPCostContext &Ctx,
388 VFRange &Range);
389
390 /// Remove dead recipes from \p Plan.
391 static void removeDeadRecipes(VPlan &Plan);
392
393 /// Check if all loads in the loop are dereferenceable. Iterates over the
394 /// loop body blocks reachable from \p HeaderVPBB. Returns false if any
395 /// non-dereferenceable load is found.
396 static bool areAllLoadsDereferenceable(VPBasicBlock *HeaderVPBB,
397 Loop *TheLoop,
398 PredicatedScalarEvolution &PSE,
399 DominatorTree &DT,
400 AssumptionCache *AC);
401
402 /// If a single exit has multiple conditions combined together, split them
403 /// and create new exiting blocks. Currently limited to a single exit in the
404 /// latch block.
405 static bool splitCombinedExits(VPlan &Plan, PredicatedScalarEvolution &PSE,
406 Loop *TheLoop);
407
408 /// Update \p Plan to account for uncountable early exits by introducing
409 /// appropriate branching logic in the latch that handles early exits and the
410 /// latch exit condition. Multiple exits are handled with a dispatch block
411 /// that determines which exit to take based on lane-by-lane semantics.
412 LLVM_ABI_FOR_TEST static bool
413 handleUncountableEarlyExits(VPlan &Plan, OptimizationRemarkEmitter *ORE,
414 Loop *TheLoop, PredicatedScalarEvolution &PSE,
415 DominatorTree &DT, AssumptionCache *AC,
416 UncountableExitStyle Style);
417
418 /// Disconnect countable early exits from the loop.
419 LLVM_ABI_FOR_TEST static void handleCountableEarlyExits(VPlan &Plan);
420
421 /// Replaces the exit condition from
422 /// (branch-on-cond eq CanonicalIVInc, VectorTripCount)
423 /// to
424 /// (branch-on-cond eq AVLNext, 0)
425 static void convertEVLExitCond(VPlan &Plan);
426
427 /// Replace loop regions with explicit CFG.
428 static void dissolveLoopRegions(VPlan &Plan);
429
430 /// Expand BranchOnTwoConds instructions into explicit CFG with
431 /// BranchOnCond instructions. Should be called after dissolveLoopRegions.
432 static void expandBranchOnTwoConds(VPlan &Plan);
433
434 /// Transform loops with variable-length stepping after region
435 /// dissolution.
436 ///
437 /// Once loop regions are replaced with explicit CFG, loops can step with
438 /// variable vector lengths instead of fixed lengths. This transformation:
439 /// * Makes CurrentIteration-Phi concrete.
440 // * Removes CanonicalIV and increment.
441 static void convertToVariableLengthStep(VPlan &Plan);
442
443 /// Lower abstract recipes to concrete ones, that can be codegen'd.
444 static void convertToConcreteRecipes(VPlan &Plan);
445
446 /// This function converts initial recipes to the abstract recipes and clamps
447 /// \p Range based on cost model for following optimizations and cost
448 /// estimations. The converted abstract recipes will lower to concrete
449 /// recipes before codegen.
450 static void convertToAbstractRecipes(VPlan &Plan, VPCostContext &Ctx,
451 VFRange &Range);
452
453 /// Perform instcombine-like simplifications on recipes in \p Plan.
454 static void combineRecipes(VPlan &Plan);
455
456 /// Cancel out redundant reverses in \p Plan, e.g. reverse(reverse(x)) -> x.
457 static void simplifyReverses(VPlan &Plan);
458
459 /// Remove BranchOnCond recipes with true or false conditions together with
460 /// removing dead edges to their successors. If \p OnlyLatches is true, only
461 /// process loop latches. Returns true if incoming values from any phi-like
462 /// recipe have been removed.
463 static bool removeBranchOnConst(VPlan &Plan, bool OnlyLatches = false);
464
465 /// Perform common-subexpression-elimination on \p Plan.
466 static void cse(VPlan &Plan, const VPDominatorTree &VPDT);
467
468 /// If there's a single exit block, optimize its phi recipes that use exiting
469 /// IV values by feeding them precomputed end values instead, possibly taken
470 /// one step backwards.
471 static void optimizeInductionLiveOutUsers(VPlan &Plan,
472 PredicatedScalarEvolution &PSE,
473 const Loop *L);
474
475 /// Add explicit broadcasts for live-ins and VPValues defined in \p Plan's entry block if they are used as vectors.
476 static void materializeBroadcasts(VPlan &Plan);
477
478 /// Hoist predicated loads from the same address to the loop entry block, if
479 /// they are guaranteed to execute on both paths (i.e., in replicate regions
480 /// with complementary masks P and NOT P).
481 static void hoistPredicatedLoads(VPlan &Plan, PredicatedScalarEvolution &PSE,
482 const Loop *L);
483
484 /// Sink predicated stores to the same address with complementary predicates
485 /// (P and NOT P) to an unconditional store with select recipes for the
486 /// stored values. This eliminates branching overhead when all paths
487 /// unconditionally store to the same location.
488 static void sinkPredicatedStores(VPlan &Plan, PredicatedScalarEvolution &PSE,
489 const Loop *L);
490
491 /// Widens memory operations by a factor of UF based on a target hook.
492 /// This allows targets to use wider memory operations when profitable.
493 static void widenMemoryAccessesByUF(VPlan &Plan, ElementCount VF, unsigned UF,
494 const TargetTransformInfo &TTI);
495
496 // Materialize vector trip counts for constants early if it can simply be
497 // computed as (Original TC / VF * UF) * VF * UF.
498 static void
499 materializeConstantVectorTripCount(VPlan &Plan, ElementCount BestVF,
500 unsigned BestUF,
501 PredicatedScalarEvolution &PSE);
502
503 /// Materialize vector trip count computations to a set of VPInstructions.
504 /// \p Step is used as the step value for the trip count computation.
505 /// \p MaxRuntimeStep is the maximum possible runtime value of Step, used to
506 /// prove the trip count is divisible by the step for scalable VFs.
507 static void materializeVectorTripCount(
508 VPlan &Plan, VPBasicBlock *VectorPHVPBB, bool TailByMasking,
509 bool RequiresScalarEpilogue, VPValue *Step,
510 std::optional<uint64_t> MaxRuntimeStep = std::nullopt);
511
512 /// Add explicit Unpack recipes to extract scalars from vectors as needed.
513 static void materializeUnpacks(VPlan &Plan);
514
515 /// Materialize UF, VF and VFxUF to be computed explicitly using
516 /// VPInstructions.
517 static void materializeFactors(VPlan &Plan, VPBasicBlock *VectorPH,
518 ElementCount VF);
519
520 /// Attaches the alias-mask to the existing header-mask.
521 static void attachAliasMaskToHeaderMask(VPlan &Plan);
522
523 /// Materializes the alias mask within \p AliasCheckVPBB, which must be
524 /// dominated by the SCEV checks, as the pointer bounds of \p DiffChecks are
525 /// only valid if the SCEV predicates hold. Updates the header mask of the
526 /// loop to use the alias mask. Returns the clamped VF.
527 static VPValue *materializeAliasMask(VPlan &Plan,
528 VPBasicBlock *AliasCheckVPBB,
529 ArrayRef<PointerDiffInfo> DiffChecks,
530 ScalarEvolution &SE);
531
532 /// Materializes the alias mask within a check block before the loop. The
533 /// vector loop will only be entered if the clamped VF from the alias mask
534 /// is not scalar.
535 static void
536 materializeAliasMaskCheckBlock(VPlan &Plan,
537 ArrayRef<PointerDiffInfo> DiffChecks,
538 ScalarEvolution &SE, bool HasBranchWeights);
539
540 /// Expand VPExpandSCEVRecipes in \p Plan's entry block to VPInstructions.
541 /// Recipes wrapping a SCEVAddRecExpr are kept for later IR-level expansion.
542 static void expandSCEVsToVPInstructions(VPlan &Plan, ScalarEvolution &SE);
543
544 /// Expand remaining VPExpandSCEVRecipes in \p Plan's entry block using
545 /// SCEVExpander. Each VPExpandSCEVRecipe is replaced with a live-in wrapping
546 /// the expanded IR value. A mapping from SCEV expressions to their expanded
547 /// IR value is returned.
548 static DenseMap<const SCEV *, Value *> expandSCEVs(VPlan &Plan,
549 ScalarEvolution &SE);
550
551 /// Try to find a single VF among \p Plan's VFs for which all interleave
552 /// groups (with known minimum VF elements) can be replaced by wide loads and
553 /// stores processing VF elements, if all transformed interleave groups access
554 /// the full vector width (checked via the maximum vector register width). If
555 /// the transformation can be applied, the original \p Plan will be split in
556 /// 2:
557 /// 1. The original Plan with the single VF containing the optimized recipes
558 /// using wide loads instead of interleave groups.
559 /// 2. A new clone which contains all VFs of Plan except the optimized VF.
560 ///
561 /// This effectively is a very simple form of loop-aware SLP, where we use
562 /// interleave groups to identify candidates.
563 static std::unique_ptr<VPlan>
564 narrowInterleaveGroups(VPlan &Plan, const TargetTransformInfo &TTI);
565
566 /// Adapts the vector loop region for tail folding by introducing a header
567 /// mask and conditionally executing the content of the region:
568 ///
569 /// Vector loop region before:
570 /// +-------------------------------------------+
571 /// |%iv = ... |
572 /// |... |
573 /// |%iv.next = add %iv, vfxuf |
574 /// |branch-on-count %iv.next, vector-trip-count|
575 /// +-------------------------------------------+
576 ///
577 /// Vector loop region after:
578 /// +-------------------------------------------+
579 /// |%iv = ... |
580 /// |%wide.iv = widen-canonical-iv ... |
581 /// |%header-mask = icmp ule %wide.iv, BTC |
582 /// |branch-on-cond %header-mask |---+
583 /// +-------------------------------------------+ |
584 /// | |
585 /// v |
586 /// +-------------------------------------------+ |
587 /// | ... | |
588 /// +-------------------------------------------+ |
589 /// | |
590 /// v |
591 /// +-------------------------------------------+ |
592 /// |<phis> = phi [..., ...], [poison, header] |
593 /// |%iv.next = add %iv, vfxuf |<--+
594 /// |branch-on-count %iv.next, vector-trip-count|
595 /// +-------------------------------------------+
596 ///
597 /// Any VPInstruction::ExtractLastLanes are also updated to extract from the
598 /// last active lane of the header mask.
599 static void foldTailByMasking(VPlan &Plan);
600
601 /// Predicate and linearize the control-flow in the only loop region of
602 /// \p Plan.
603 static void introduceMasksAndLinearize(VPlan &Plan);
604
605 /// Replace a VPWidenCanonicalIVRecipe if it is present in \p Plan, with a
606 /// VPWidenIntOrFpInductionRecipe, provided it would not cause additional
607 /// spills for \p VF at unroll factor \p UF.
608 static void
609 replaceWideCanonicalIVWithWideIV(VPlan &Plan, ScalarEvolution &SE,
610 const TargetTransformInfo &TTI,
611 TargetTransformInfo::TargetCostKind CostKind,
612 ElementCount VF, unsigned UF);
613
614 /// Add branch weight metadata, if the \p Plan's middle block is terminated by
615 /// a BranchOnCond recipe.
616 static void
617 addBranchWeightToMiddleTerminator(VPlan &Plan, ElementCount VF,
618 std::optional<unsigned> VScaleForTuning);
619
620 /// Adjust first-order recurrence users in the middle block: create
621 /// penultimate element extracts for LCSSA phi users, and handle penultimate
622 /// extracts of the last active lane edge.
623 static void adjustFirstOrderRecurrenceMiddleUsers(VPlan &Plan,
624 VFRange &Range);
625
626 /// Optimize FindLast reductions selecting IVs (or expressions of IVs) by
627 /// converting them to FindIV reductions, if their IV range excludes a
628 /// suitable sentinel value. For expressions of IVs, the expression is sunk
629 /// to the middle block. The decision is based on SCEV expressions for \p L,
630 /// so this must run before any transform that changes the plan's iteration
631 /// space relative to \p L.
632 static void optimizeFindIVReductions(VPlan &Plan,
633 PredicatedScalarEvolution &PSE, Loop &L);
634
635 /// Detect and create partial reduction recipes for scaled or unordered
636 /// reductions in \p Plan. Must be called after recipe construction. If
637 /// partial reductions are only valid for a subset of VFs in Range, Range.End
638 /// is updated.
639 static void createPartialReductions(VPlan &Plan, VPCostContext &CostCtx,
640 VFRange &Range);
641
642 /// Convert load/store VPInstructions in \p Plan into widened or replicate
643 /// recipes. Non load/store input instructions are left unchanged.
644 static void makeMemOpWideningDecisions(VPlan &Plan, VFRange &Range,
645 VPRecipeBuilder &RecipeBuilder,
646 VPCostContext &CostCtx);
647
648 /// Make VPlan-based scalarization decision prior to delegating to the ones
649 /// made by the legacy CM. Only transforms "usesFirstLaneOnly` def-use chains
650 /// enabled by prior widening of consecutive memory operations and calls for
651 /// now.
652 static void makeScalarizationDecisions(VPlan &Plan, VFRange &Range);
653
654 /// Convert call VPInstructions in \p Plan into widened call, vector
655 /// intrinsic or replicate recipes based on a cost comparison via \p CostCtx.
656 /// Returns true if any call was widened.
657 static bool makeCallWideningDecisions(VPlan &Plan, VFRange &Range,
658 VPRecipeBuilder &RecipeBuilder,
659 VPCostContext &CostCtx);
660
661 /// Replace truncates of a wide induction, or of that induction's increment,
662 /// by a VPWidenIntOrFpInductionRecipe producing the truncated type directly.
663 /// The canonical induction is narrowed even when the target reports the
664 /// truncate as free. If narrowing is only profitable for a subset of VFs in
665 /// \p Range, Range.End is updated.
666 static void narrowInductionTruncates(VPlan &Plan, VFRange &Range,
667 const TargetTransformInfo &TTI,
668 PredicatedScalarEvolution &PSE);
669
670 /// Wrap reduction operations and their vp.merge in expression recipes when
671 /// the merge is expected to be folded, to better model the cost and register
672 /// pressure of the \p Plan.
673 static void foldPredicateMerge(VPlan &Plan, VPCostContext &CostCtx);
674};
675
676} // namespace llvm
677
678#endif // LLVM_TRANSFORMS_VECTORIZE_VPLANTRANSFORMS_H
679