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