LLVM 24.0.0git
LoopVectorizationLegality.h
Go to the documentation of this file.
1//===- llvm/Transforms/Vectorize/LoopVectorizationLegality.h ----*- C++ -*-===//
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 defines the LoopVectorizationLegality class. Original code
11/// in Loop Vectorizer has been moved out to its own file for modularity
12/// and reusability.
13///
14/// Currently, it works for innermost loop vectorization. Extending this to
15/// outer loop vectorization is a TODO item.
16///
17/// Also provides:
18/// 1) LoopVectorizeHints class which keeps a number of loop annotations
19/// locally for easy look up. It has the ability to write them back as
20/// loop metadata, upon request.
21/// 2) LoopVectorizationRequirements class for lazy bail out for the purpose
22/// of reporting useful failure to vectorize message.
23//
24//===----------------------------------------------------------------------===//
25
26#ifndef LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONLEGALITY_H
27#define LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONLEGALITY_H
28
29#include "llvm/ADT/DenseMap.h"
30#include "llvm/ADT/MapVector.h"
36
37namespace llvm {
38class AssumptionCache;
39class BasicBlock;
40class DemandedBits;
41class DominatorTree;
42class Function;
43class Loop;
44class LoopInfo;
45class Metadata;
50class Type;
51struct VectorizeOptions;
52
53/// Utility class for getting and setting loop vectorizer hints in the form
54/// of loop metadata.
55/// This class keeps a number of loop annotations locally (as member variables)
56/// and can, upon request, write them back as metadata on the loop. It will
57/// initially scan the loop for existing metadata, and will update the local
58/// values based on information in the loop.
59/// We cannot write all values to metadata, as the mere presence of some info,
60/// for example 'force', means a decision has been made. So, we need to be
61/// careful NOT to add them if the user hasn't specifically asked so.
63public:
64 enum ForceKind {
65 FK_Undefined = -1, ///< Not selected.
66 FK_Disabled = 0, ///< Forcing disabled.
67 FK_Enabled = 1, ///< Forcing enabled.
68 };
69
70private:
71 enum HintKind { HK_WIDTH, HK_INTERLEAVE, HK_ISVECTORIZED };
72
73 /// Hint - associates name and validation with the hint value.
74 struct Hint {
75 const char *Name;
76 unsigned Value; // This may have to change for non-numeric values.
77 HintKind Kind;
78
79 Hint(const char *Name, unsigned Value, HintKind Kind)
80 : Name(Name), Value(Value), Kind(Kind) {}
81
82 LLVM_ABI bool validate(unsigned Val);
83 };
84
85 const VectorizeOptions &Opts;
86
87 /// Vectorization width.
88 Hint Width;
89
90 /// Vectorization interleave factor.
91 Hint Interleave;
92
93 /// Vectorization forced; one of ForceKind. Carried as a plain value because
94 /// the enable/disable pair is a standalone tag with no operand to validate.
95 unsigned Force;
96
97 /// Already Vectorized
98 Hint IsVectorized;
99
100 /// Vector Predicate; one of ForceKind, carried as a plain value like Force.
101 unsigned Predicate;
102
103 /// Scalable vs fixed-width preference; one of ScalableForceKind. Carried as
104 /// a plain value because the enable/disable pair has no operand to validate.
105 unsigned Scalable;
106
107 /// Unsafe FP hint from llvm.loop.vectorize.fp_unsafe.{enable,disable}.
108 /// FK_Undefined : not specified
109 /// FK_Disabled : result-changing FP vectorization suppressed
110 /// FK_Enabled : result-changing FP vectorization allowed
111 ForceKind FPUnsafe;
112
113 /// Return the loop metadata prefix.
114 static StringRef Prefix() { return "llvm.loop."; }
115
116 /// True if there is any unsafe math in the loop.
117 bool PotentiallyUnsafe = false;
118
119public:
121 /// Not selected.
123 /// Disables vectorization with scalable vectors.
125 /// Vectorize loops using scalable vectors or fixed-width vectors, but favor
126 /// scalable vectors when the cost-model is inconclusive. This is the
127 /// default when the scalable.enable hint is enabled through a pragma.
129 /// Always vectorize loops using scalable vectors if feasible (i.e. the plan
130 /// has a valid cost and is not restricted by fixed-length dependence
131 /// distances).
133 };
134
135 LLVM_ABI LoopVectorizeHints(const VectorizeOptions &Opts, const Loop *L,
136 bool InterleaveOnlyWhenForced,
138 const TargetTransformInfo *TTI = nullptr);
139
140 /// Mark the loop L as already vectorized by setting the width to 1.
142
143 LLVM_ABI bool allowVectorization(Loop *L, bool VectorizeOnlyWhenForced) const;
144
145 /// Dumps all the hint information.
146 LLVM_ABI void emitRemarkWithHints() const;
147
149 return ElementCount::get(
150 Width.Value, (ScalableForceKind)Scalable == SK_PreferScalable ||
152 }
153
154 unsigned getInterleave() const {
155 if (Interleave.Value)
156 return Interleave.Value;
157 // If interleaving is not explicitly set, assume that if we do not want
158 // unrolling, we also don't want any interleaving.
160 return 1;
161 return 0;
162 }
163 unsigned getIsVectorized() const { return IsVectorized.Value; }
164 unsigned getPredicate() const { return Predicate; }
165 enum ForceKind getForce() const {
166 if ((ForceKind)Force == FK_Undefined &&
168 return FK_Disabled;
169 return (ForceKind)Force;
170 }
171
172 /// \return true if scalable vectorization has been explicitly disabled.
174 return (ScalableForceKind)Scalable == SK_FixedWidthOnly;
175 }
176
177 /// \return true if scalable vectorization is always preferred over
178 /// fixed-length when feasible, regardless of cost.
182
183 /// When enabling loop hints are provided we allow the vectorizer to change
184 /// the order of operations that is given by the scalar loop. This is not
185 /// enabled by default because can be unsafe or inefficient. For example,
186 /// reordering floating-point operations will change the way round-off
187 /// error accumulates in the loop.
188 LLVM_ABI bool allowReordering() const;
189
190 bool isPotentiallyUnsafe() const {
191 // Avoid FP vectorization if the target is unsure about proper support.
192 // This may be related to the SIMD unit in the target not handling
193 // IEEE 754 FP ops properly, or bad single-to-double promotions.
194 // Otherwise, a sequence of vectorized loops, even without reduction,
195 // could lead to different end results on the destination vectors.
196 //
197 // An explicit fp_unsafe hint takes precedence over the vectorize.enable
198 // default.
199 if (FPUnsafe != FK_Undefined)
200 return FPUnsafe != FK_Enabled && PotentiallyUnsafe;
201
202 return getForce() != LoopVectorizeHints::FK_Enabled && PotentiallyUnsafe;
203 }
204
205 void setPotentiallyUnsafe() { PotentiallyUnsafe = true; }
206
207private:
208 /// Find hints specified in the loop metadata and update local values.
209 void getHintsFromMetadata();
210
211 /// Checks string hint with one operand and set value if valid.
212 void setHint(StringRef Name, Metadata *Arg);
213
214 /// The loop these hints belong to.
215 const Loop *TheLoop;
216
217 /// Interface to emit optimization remarks.
219
220 /// Reports a condition where loop vectorization is disallowed: prints
221 /// \p DebugMsg for debugging purposes along with the corresponding
222 /// optimization remark \p RemarkName, with \p RemarkMsg as the user-facing
223 /// message. The loop \p L is used for the location of the remark.
224 void reportDisallowedVectorization(const StringRef DebugMsg,
225 const StringRef RemarkName,
226 const StringRef RemarkMsg,
227 const Loop *L) const;
228};
229
230/// This holds vectorization requirements that must be verified late in
231/// the process. The requirements are set by legalize and costmodel. Once
232/// vectorization has been determined to be possible and profitable the
233/// requirements can be verified by looking for metadata or compiler options.
234/// For example, some loops require FP commutativity which is only allowed if
235/// vectorization is explicitly specified or if the fast-math compiler option
236/// has been provided.
237/// Late evaluation of these requirements allows helpful diagnostics to be
238/// composed that tells the user what need to be done to vectorize the loop. For
239/// example, by specifying #pragma clang loop vectorize or -ffast-math. Late
240/// evaluation should be used only when diagnostics can generated that can be
241/// followed by a non-expert user.
243public:
244 /// Track the 1st floating-point instruction that can not be reassociated.
246 if (I && !ExactFPMathInst)
247 ExactFPMathInst = I;
248 }
249
250 Instruction *getExactFPInst() { return ExactFPMathInst; }
251
252private:
253 Instruction *ExactFPMathInst = nullptr;
254};
255
256/// This holds details about a histogram operation -- a load -> update -> store
257/// sequence where each lane in a vector might be updating the same element as
258/// another lane.
270
271/// Holds details about a "compressed" pointer: the conditional induction PHI
272/// used to derive the pointer and the SCEV expression for the pointer.
277
278/// Indicates the characteristics of a loop with an uncountable exit.
279/// * None -- No uncountable exit present.
280/// * ReadOnly -- At least one uncountable exit in a readonly loop.
281/// * ReadWrite -- At least one uncountable exit in a loop with side effects
282/// that may require masking.
284
285/// LoopVectorizationLegality checks if it is legal to vectorize a loop, and
286/// to what vectorization factor.
287/// This class does not look at the profitability of vectorization, only the
288/// legality. This class has two main kinds of checks:
289/// * Memory checks - The code in canVectorizeMemory checks if vectorization
290/// will change the order of memory accesses in a way that will change the
291/// correctness of the program.
292/// * Scalars checks - The code in canVectorizeInstrs and canVectorizeMemory
293/// checks for a number of different conditions, such as the availability of a
294/// single induction variable, that all types are supported and vectorize-able,
295/// etc. It also identifies the induction and reduction variables of the loop.
297public:
298 LoopVectorizationLegality(const VectorizeOptions &Opts, Loop *L,
305 AssumptionCache *AC, bool AllowRuntimeSCEVChecks,
306 AAResults *AA)
307 : Opts(Opts), TheLoop(L), LI(LI), PSE(PSE), TTI(TTI), TLI(TLI), DT(DT),
308 LAIs(LAIs), ORE(ORE), Requirements(R), Hints(H), DB(DB), AC(AC),
309 AllowRuntimeSCEVChecks(AllowRuntimeSCEVChecks), AA(AA) {}
310
311 /// ReductionList contains the reduction descriptors for all
312 /// of the reductions that were found in the loop.
314
315 /// InductionList saves induction variables and maps them to the
316 /// induction descriptor.
318
319 /// ConditionalInductionList saves conditional inductions and maps them to
320 /// their descriptors.
323
324 /// RecurrenceSet contains the phi nodes that are recurrences other than
325 /// inductions and reductions.
327
328 /// Returns true if it is legal to vectorize this loop.
329 /// This does not mean that it is profitable to vectorize this
330 /// loop, only that it is legal to do so.
331 /// Temporarily taking UseVPlanNativePath parameter. If true, take
332 /// the new code path being implemented for outer loop vectorization
333 /// (should be functional for inner loop vectorization) based on VPlan.
334 /// If false, good old LV code.
335 LLVM_ABI bool canVectorize(bool UseVPlanNativePath);
336
337 /// Returns true if it is legal to vectorize the FP math operations in this
338 /// loop. Vectorizing is legal if we allow reordering of FP operations, or if
339 /// we can use in-order reductions.
340 LLVM_ABI bool canVectorizeFPMath(bool EnableStrictReductions);
341
342 /// Return true if we can vectorize this loop while folding its tail by
343 /// masking.
344 LLVM_ABI bool canFoldTailByMasking() const;
345
346 /// Mark all respective loads/stores for masking. Must only be called when
347 /// tail-folding is possible.
349
350 /// Returns the primary induction variable.
351 PHINode *getPrimaryInduction() { return PrimaryInduction; }
352
353 /// Returns the reduction variables found in the loop.
354 const ReductionList &getReductionVars() const { return Reductions; }
355
356 /// Returns the recurrence descriptor associated with a given phi node \p PN,
357 /// expecting one to exist.
360 "only reductions have recurrence descriptors");
361 return Reductions.find(PN)->second;
362 }
363
364 /// Returns the induction variables found in the loop.
365 const InductionList &getInductionVars() const { return Inductions; }
366
367 /// Returns the conditional inductions found in the loop.
369 return ConditionalInductions;
370 }
371
373 return !ConditionalInductions.empty();
374 }
375
376 /// Return the fixed-order recurrences found in the loop.
377 RecurrenceSet &getFixedOrderRecurrences() { return FixedOrderRecurrences; }
378
379 /// Returns the widest induction type.
380 IntegerType *getWidestInductionType() { return WidestIndTy; }
381
382 /// Returns True if given store is a final invariant store of one of the
383 /// reductions found in the loop.
385
386 /// Returns True if given address is invariant and is used to store recurrent
387 /// expression
389
390 /// Returns True if V is a Phi node of an induction variable in this loop.
391 LLVM_ABI bool isInductionPhi(const Value *V) const;
392
393 /// Returns True if PN is a reduction variable in this loop.
394 bool isReductionVariable(PHINode *PN) const { return Reductions.count(PN); }
395
396 /// Returns True if Phi is a fixed-order recurrence in this loop.
397 LLVM_ABI bool isFixedOrderRecurrence(const PHINode *Phi) const;
398
399 /// Return true if the block BB needs to be predicated in order for the loop
400 /// to be vectorized.
401 LLVM_ABI bool blockNeedsPredication(const BasicBlock *BB) const;
402
403 /// Add unit stride predicates for memory accesses to PSE, if runtime checks
404 /// are allowed and an inner loop is vectorized.
406
407 /// Check if this pointer is consecutive when vectorizing. This happens
408 /// when the last index of the GEP is the induction variable, or that the
409 /// pointer itself is an induction variable.
410 /// This check allows us to vectorize A[idx] into a wide load/store.
411 /// Returns:
412 /// 0 - Stride is unknown or non-consecutive.
413 /// 1 - Address is consecutive.
414 /// -1 - Address is consecutive, and decreasing.
415 /// NOTE: This method must only be used before modifying the original scalar
416 /// loop. Do not use after executing a VPlan (PR34965).
417 LLVM_ABI int isConsecutivePtr(Type *AccessTy, Value *Ptr) const;
418
419 /// Returns true if \p V is invariant across all loop iterations according to
420 /// SCEV.
421 LLVM_ABI bool isInvariant(Value *V) const;
422
423 /// Returns true if value V is uniform across \p VF lanes, when \p VF is
424 /// provided, and otherwise if \p V is invariant across all loop iterations.
425 LLVM_ABI bool isUniform(Value *V, std::optional<ElementCount> VF) const;
426
427 /// A uniform memory op is a load or store which accesses the same memory
428 /// location on all \p VF lanes, if \p VF is provided and otherwise if the
429 /// memory location is invariant.
431 std::optional<ElementCount> VF) const;
432
433 /// Returns the information that we collected about runtime memory check.
435 return LAI->getRuntimePointerChecking();
436 }
437
438 const LoopAccessInfo *getLAI() const { return LAI; }
439
441 return LAI->getDepChecker().isSafeForAnyVectorWidth() &&
442 LAI->getDepChecker().isSafeForAnyStoreLoadForwardDistances();
443 }
444
446 return LAI->getDepChecker().getMaxSafeVectorWidthInBits();
447 }
448
449 /// Returns information about whether this loop contains at least one
450 /// uncountable early exit, and if so, if it also contains instructions (such
451 /// as stores) that cause side-effects.
453 return UncountableExitType;
454 }
455
456 /// Returns true if the loop has uncountable early exits, i.e. uncountable
457 /// exits that aren't the latch block.
461
462 /// Returns true if this is an early exit loop with state-changing or
463 /// potentially-faulting operations and the condition for the uncountable
464 /// exit must be determined before any of the state changes or potentially
465 /// faulting operations take place.
469
470 /// If Cond is a combined exit condition featuring uncountable and countable
471 /// comparisons, returns the countable comparison. Otherwise returns nullptr.
474
475 /// Return true if there is store-load forwarding dependencies.
477 return LAI->getDepChecker().isSafeForAnyStoreLoadForwardDistances();
478 }
479
480 /// Return safe power-of-2 number of elements, which do not prevent store-load
481 /// forwarding and safe to operate simultaneously.
483 return LAI->getDepChecker().getStoreLoadForwardSafeDistanceInBits();
484 }
485
486 /// Returns true if instruction \p I requires a mask for vectorization.
487 /// This accounts for both control flow masking (conditionally executed
488 /// blocks) and tail-folding masking (predicated loop vectorization).
489 bool isMaskRequired(const Instruction *I, bool TailFolded) const {
490 if (TailFolded)
491 return TailFoldedMaskedOp.contains(I);
492 return ConditionallyExecutedOps.contains(I);
493 }
494
495 /// Returns true if there is at least one function call in the loop which
496 /// has a vectorized variant available.
497 bool hasVectorCallVariants() const { return VecCallVariantsFound; }
498
499 /// Returns a HistogramInfo* for the given instruction if it was determined
500 /// to be part of a load -> update -> store sequence where multiple lanes
501 /// may be working on the same memory address.
503 for (const HistogramInfo &HGram : Histograms)
504 if (HGram.Load == I || HGram.Update == I || HGram.Store == I)
505 return &HGram;
506
507 return nullptr;
508 }
509
510 /// Returns a list of all known histogram operations in the loop.
511 bool hasHistograms() const { return !Histograms.empty(); }
512
513 /// Returns the CompressedPtrInfo for \p Ptr if the pointer is defined via
514 /// a conditional induction PHI, otherwise std::nullopt.
515 std::optional<CompressedPtrInfo> getCompressedPtrInfo(Value *Ptr) const {
516 auto It = CompressedPtrs.find(Ptr);
517 if (It != CompressedPtrs.end())
518 return It->second;
519 return std::nullopt;
520 }
521
522 /// Returns true for \p I if it corresponds to a compressed load or store
523 /// (which can map to an llvm.masked.expandload or llvm.masked.compressstore).
528
532
533 Loop *getLoop() const { return TheLoop; }
534
535 LoopInfo *getLoopInfo() const { return LI; }
536
537 AssumptionCache *getAssumptionCache() const { return AC; }
538
539 ScalarEvolution *getScalarEvolution() const { return PSE.getSE(); }
540
541 DominatorTree *getDominatorTree() const { return DT; }
542
543 AAResults *getAA() const { return AA; }
544
545 /// Returns all exiting blocks with a countable exit, i.e. the
546 /// exit-not-taken count is known exactly at compile time.
548 return CountableExitingBlocks;
549 }
550
551private:
552 /// Return true if the pre-header, exiting and latch blocks of \p Lp and all
553 /// its nested loops are considered legal for vectorization. These legal
554 /// checks are common for inner and outer loop vectorization.
555 /// Temporarily taking UseVPlanNativePath parameter. If true, take
556 /// the new code path being implemented for outer loop vectorization
557 /// (should be functional for inner loop vectorization) based on VPlan.
558 /// If false, good old LV code.
559 bool canVectorizeLoopNestCFG(Loop *Lp, bool UseVPlanNativePath);
560
561 /// Set up outer loop inductions by checking Phis in outer loop header for
562 /// supported inductions (int and pointer inductions). Return false if any of
563 /// these Phis is not a supported induction or if we fail to find any
564 /// induction.
565 bool setupOuterLoopInductions();
566
567 /// Return true if the widest induction type, used for the canonical IV and
568 /// trip count, can be determined, i.e. there is at least one integer or
569 /// pointer induction. Otherwise report the reason and return false.
570 bool canDetermineWidestInductionType();
571
572 /// Return true if the pre-header, exiting and latch blocks of \p Lp
573 /// (non-recursive) are considered legal for vectorization.
574 /// Temporarily taking UseVPlanNativePath parameter. If true, take
575 /// the new code path being implemented for outer loop vectorization
576 /// (should be functional for inner loop vectorization) based on VPlan.
577 /// If false, good old LV code.
578 bool canVectorizeLoopCFG(Loop *Lp, bool UseVPlanNativePath) const;
579
580 /// Check if a single basic block loop is vectorizable.
581 /// At this point we know that this is a loop with a constant trip count
582 /// and we only need to check individual instructions.
583 bool canVectorizeInstrs();
584
585 /// Check if an individual instruction is vectorizable.
586 bool canVectorizeInstr(Instruction &I);
587
588 /// When we vectorize loops we may change the order in which
589 /// we read and write from memory. This method checks if it is
590 /// legal to vectorize the code, considering only memory constrains.
591 /// Returns true if the loop is vectorizable
592 bool canVectorizeMemory();
593
594 /// If LAA cannot determine whether all dependences are safe, we may be able
595 /// to further analyse some IndirectUnsafe dependences and if they match a
596 /// certain pattern (like a histogram) then we may still be able to vectorize.
597 bool canVectorizeIndirectUnsafeDependences();
598
599 /// Return true if we can vectorize this loop using the IF-conversion
600 /// transformation.
601 bool canVectorizeWithIfConvert();
602
603 /// Return true if we can vectorize this outer loop. The method performs
604 /// specific checks for outer loop vectorization.
605 bool canVectorizeOuterLoop();
606
607 /// Returns true if this is an early exit loop that can be vectorized.
608 /// Currently, a loop with an uncountable early exit is considered
609 /// vectorizable if:
610 /// 1. Writes to memory will access different underlying objects than
611 /// any load used as part of the uncountable exit condition.
612 /// 2. The loop has only one early uncountable exit
613 /// 3. The early exit block dominates the latch block.
614 /// 4. The latch block has an exact exit count.
615 /// 5. The loop does not contain fixed-order recurrences or reductions where
616 /// the live-out value is used from a non-latch exit..
617 /// 6. We can prove at compile-time that loops will not contain faulting
618 /// loads, or that any faulting loads would also occur in a purely
619 /// scalar loop.
620 /// 7. It is safe to speculatively execute instructions such as divide or
621 /// call instructions.
622 /// The list above is not based on theoretical limitations of vectorization,
623 /// but simply a statement that more work is needed to support these
624 /// additional cases safely.
625 bool isVectorizableEarlyExitLoop();
626
627 /// When vectorizing an early exit loop containing side effects, we need to
628 /// determine whether an uncounted exit will be taken before any operation
629 /// that has side effects.
630 ///
631 /// Consider a loop like the following:
632 /// for (int i = 0; i < N; ++i) {
633 /// a[i] = b[i];
634 /// if (c[i] == 0)
635 /// break;
636 /// }
637 ///
638 /// We have both a load and a store operation occurring before the condition
639 /// is checked for early termination. We could potentially restrict
640 /// vectorization to cases where we know all addresses are guaranteed to be
641 /// dereferenceable, which would allow the load before the condition check to
642 /// be vectorized.
643 ///
644 /// The store, however, should not execute across all lanes if early
645 /// termination occurs before the end of the vector. We must only store to the
646 /// locations that would have been stored to by a scalar loop. So we need to
647 /// know what the result of 'c[i] == 0' is before performing the vector store,
648 /// with or without masking.
649 ///
650 /// We can either do this by moving the condition load to the top of the
651 /// vector body and using the comparison to create masks for other operations
652 /// in the loop, or by looking ahead one vector iteration and bailing out to
653 /// the scalar loop if an exit would occur.
654 ///
655 /// Using the latter approach (applicable to more targets), we need to hoist
656 /// the first load (of c[0]) out of the loop then rotate the load within the
657 /// loop to the next iteration, remembering to adjust the vector trip count.
658 /// Something like the following:
659 ///
660 /// vec.ph:
661 /// %ci.0 = load <4 x i32>, ptr %c
662 /// %cmp.0 = icmp eq <4 x i32> %ci.0, zeroinitializer
663 /// %any.of.0 = call i1 @llvm.vector.reduce.or.v4i1(<4 x i1> %cmp.0)
664 /// br i1 %any.of.0, label %scalar.ph, label %vec.body
665 /// vec.body:
666 /// %iv = phi...
667 /// phi for c[i] if used elsewhere in the loop...
668 /// other operations in the loop...
669 /// %iv.next = add i64 %iv, 4
670 /// %addr.next = getelementptr i32, ptr %c, i64 %iv.next
671 /// %ci.next = load <4 x i32>, ptr %addr.next
672 /// %cmp.next = icmp eq <4 x i32> %ci.next, zeroinitializer
673 /// %any.of.next = call i1 @llvm.vector.reduce.or.v4i1(<4 x i1> %cmp.next)
674 /// iv.next compared with shortened vector tripcount...
675 /// uncountable condition combined with counted condition...
676 /// br...
677 ///
678 /// Doing this means the last few iterations will always be performed by a
679 /// scalar loop regardless of which exit is taken, and so vector iterations
680 /// will never execute a memory operation to a location that the scalar loop
681 /// would not have.
682 ///
683 /// This means we must ensure that it is safe to move the load for 'c[i]'
684 /// before other memory operations (or any other observable side effects) in
685 /// the loop.
686 ///
687 /// Currently, c[i] must have only one user (the comparison used for the
688 /// uncountable exit) since we would otherwise need to introduce a PHI node
689 /// for it.
690 bool canUncountableExitConditionLoadBeMoved(BasicBlock *ExitingBlock);
691
692 struct SafeAccessInfo {
693 uint64_t MaxSizeInBytes = 0;
694 Align MaxAlign = Align(1);
695 };
696
697 /// Maps a pointer to its maximum fixed access size and safe alignment.
698 using SafeAccessesTy = SmallDenseMap<Value *, SafeAccessInfo, 8>;
699
700 /// Return true if all of the instructions in the block can be speculatively
701 /// executed, and record the loads/stores that require masking.
702 /// \p SafeAccesses records pointers that can be accessed unconditionally,
703 /// together with the fixed access sizes and alignments justified for each
704 /// pointer.
705 /// \p MaskedOp is a list of instructions that have to be transformed into
706 /// calls to the appropriate masked intrinsic when the loop is vectorized
707 /// or dropped if the instruction is a conditional assume intrinsic.
708 bool
709 blockCanBePredicated(BasicBlock *BB, SafeAccessesTy &SafeAccesses,
710 SmallPtrSetImpl<const Instruction *> &MaskedOp) const;
711
712 /// Updates the vectorization state by adding \p Phi to the inductions list.
713 /// This can set \p Phi as the main induction of the loop if \p Phi is a
714 /// better choice for the main induction than the existing one.
715 void addInductionPhi(PHINode *Phi, const InductionDescriptor &ID);
716
717 /// Adds \p Phi to the conditional induction list and collects load/store
718 /// users of the PHI. Returns true if all users of \p Phi are legal for
719 /// vectorization.
720 bool addConditionalInduction(PHINode *Phi,
721 const ConditionalInductionDescriptor &CondID);
722
723 const VectorizeOptions &Opts;
724
725 /// The loop that we evaluate.
726 Loop *TheLoop;
727
728 /// Loop Info analysis.
729 LoopInfo *LI;
730
731 /// A wrapper around ScalarEvolution used to add runtime SCEV checks.
732 /// Applies dynamic knowledge to simplify SCEV expressions in the context
733 /// of existing SCEV assumptions. The analysis will also add a minimal set
734 /// of new predicates if this is required to enable vectorization and
735 /// unrolling.
736 PredicatedScalarEvolution &PSE;
737
738 /// Target Transform Info.
739 TargetTransformInfo *TTI;
740
741 /// Target Library Info.
742 TargetLibraryInfo *TLI;
743
744 /// Dominator Tree.
745 DominatorTree *DT;
746
747 // LoopAccess analysis.
748 LoopAccessInfoManager &LAIs;
749
750 const LoopAccessInfo *LAI = nullptr;
751
752 /// Interface to emit optimization remarks.
753 OptimizationRemarkEmitter *ORE;
754
755 // --- vectorization state --- //
756
757 /// Holds the primary induction variable. This is the counter of the
758 /// loop.
759 PHINode *PrimaryInduction = nullptr;
760
761 /// Holds the reduction variables.
763
764 /// Holds all of the induction variables that we found in the loop.
765 /// Notice that inductions don't need to start at zero and that induction
766 /// variables can be pointers.
767 InductionList Inductions;
768
769 /// Holds all of the conditional inductions found in the loop.
770 ConditionalInductionList ConditionalInductions;
771
772 /// Holds the phi nodes that are fixed-order recurrences.
773 RecurrenceSet FixedOrderRecurrences;
774
775 /// Holds the widest induction type encountered.
776 IntegerType *WidestIndTy = nullptr;
777
778 /// Vectorization requirements that will go through late-evaluation.
779 LoopVectorizationRequirements *Requirements;
780
781 /// Used to emit an analysis of any legality issues.
782 LoopVectorizeHints *Hints;
783
784 /// The demanded bits analysis is used to compute the minimum type size in
785 /// which a reduction can be computed.
786 DemandedBits *DB;
787
788 /// The assumption cache analysis is used to compute the minimum type size in
789 /// which a reduction can be computed.
790 AssumptionCache *AC;
791
792 /// Instructions that require masking because they are in source-level
793 /// conditionally executed blocks.
794 SmallPtrSet<const Instruction *, 8> ConditionallyExecutedOps;
795 /// Instructions that require masking only due to tail-folding predication.
796 SmallPtrSet<const Instruction *, 8> TailFoldedMaskedOp;
797
798 /// Contains all identified histogram operations, which are sequences of
799 /// load -> update -> store instructions where multiple lanes in a vector
800 /// may work on the same memory location.
802
803 /// Contains all pointers used in the loop that are defined using an index
804 /// derived from a conditional induction PHI. Loads/stores to these pointers
805 /// map to expandloads or compressstores.
806 SmallDenseMap<const Value *, CompressedPtrInfo> CompressedPtrs;
807
808 /// Whether or not creating SCEV predicates is allowed.
809 bool AllowRuntimeSCEVChecks;
810
811 // Alias Analysis results used to check for possible aliasing with loads
812 // used in uncountable exit conditions.
813 AAResults *AA;
814
815 /// If we discover function calls within the loop which have a valid
816 /// vectorized variant, record that fact so that LoopVectorize can
817 /// (potentially) make a better decision on the maximum VF and enable
818 /// the use of those function variants.
819 bool VecCallVariantsFound = false;
820
821 /// Keep track of all the countable and uncountable exiting blocks if
822 /// the exact backedge taken count is not computable.
823 SmallVector<BasicBlock *, 4> CountableExitingBlocks;
824
825 /// Records whether we have an uncountable early exit in a loop that's
826 /// either read-only or read-write.
827 UncountableExitTrait UncountableExitType = UncountableExitTrait::None;
828};
829
830} // namespace llvm
831
832#endif // LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONLEGALITY_H
const TargetLowering & TLI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
uint64_t uint64_t
#define LLVM_ABI
Definition Compiler.h:211
This file defines the DenseMap class.
#define F(x, y, z)
Definition MD5.cpp:54
#define I(x, y, z)
Definition MD5.cpp:57
#define H(x, y, z)
Definition MD5.cpp:56
This file implements a map that provides insertion order iteration.
SmallVector< MachineOperand, 4 > Cond
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition BasicBlock.h:62
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition Dominators.h:122
static constexpr ElementCount get(ScalarTy MinVal, bool Scalable)
Definition TypeSize.h:312
Class to represent integer types.
An instruction for reading from memory.
Drive the analysis of memory accesses in the loop.
bool isCompressedLoadOrStore(Instruction *I)
Returns true for I if it corresponds to a compressed load or store (which can map to an llvm....
MapVector< PHINode *, InductionDescriptor > InductionList
InductionList saves induction variables and maps them to the induction descriptor.
LLVM_ABI bool isInvariantStoreOfReduction(StoreInst *SI)
Returns True if given store is a final invariant store of one of the reductions found in the loop.
bool hasVectorCallVariants() const
Returns true if there is at least one function call in the loop which has a vectorized variant availa...
LLVM_ABI void collectUnitStridePredicates() const
Add unit stride predicates for memory accesses to PSE, if runtime checks are allowed and an inner loo...
const ConditionalInductionList & getConditionalInductions() const
Returns the conditional inductions found in the loop.
const RecurrenceDescriptor & getRecurrenceDescriptor(PHINode *PN) const
Returns the recurrence descriptor associated with a given phi node PN, expecting one to exist.
RecurrenceSet & getFixedOrderRecurrences()
Return the fixed-order recurrences found in the loop.
uint64_t getMaxStoreLoadForwardSafeDistanceInBits() const
Return safe power-of-2 number of elements, which do not prevent store-load forwarding and safe to ope...
LLVM_ABI bool isInvariantAddressOfReduction(Value *V)
Returns True if given address is invariant and is used to store recurrent expression.
LLVM_ABI bool canVectorize(bool UseVPlanNativePath)
Returns true if it is legal to vectorize this loop.
PredicatedScalarEvolution * getPredicatedScalarEvolution() const
LLVM_ABI bool blockNeedsPredication(const BasicBlock *BB) const
Return true if the block BB needs to be predicated in order for the loop to be vectorized.
LLVM_ABI int isConsecutivePtr(Type *AccessTy, Value *Ptr) const
Check if this pointer is consecutive when vectorizing.
AssumptionCache * getAssumptionCache() const
SmallPtrSet< const PHINode *, 8 > RecurrenceSet
RecurrenceSet contains the phi nodes that are recurrences other than inductions and reductions.
std::optional< CompressedPtrInfo > getCompressedPtrInfo(Value *Ptr) const
Returns the CompressedPtrInfo for Ptr if the pointer is defined via a conditional induction PHI,...
bool hasUncountableExitWithSideEffects() const
Returns true if this is an early exit loop with state-changing or potentially-faulting operations and...
LLVM_ABI bool canVectorizeFPMath(bool EnableStrictReductions)
Returns true if it is legal to vectorize the FP math operations in this loop.
bool isReductionVariable(PHINode *PN) const
Returns True if PN is a reduction variable in this loop.
LLVM_ABI bool isFixedOrderRecurrence(const PHINode *Phi) const
Returns True if Phi is a fixed-order recurrence in this loop.
IntegerType * getWidestInductionType()
Returns the widest induction type.
LLVM_ABI bool isInductionPhi(const Value *V) const
Returns True if V is a Phi node of an induction variable in this loop.
PHINode * getPrimaryInduction()
Returns the primary induction variable.
UncountableExitTrait getUncountableExitTrait() const
Returns information about whether this loop contains at least one uncountable early exit,...
const SmallVector< BasicBlock *, 4 > & getCountableExitingBlocks() const
Returns all exiting blocks with a countable exit, i.e.
LLVM_ABI Instruction * findCountableComparisonInCombinedCondition(Value *Cond) const
If Cond is a combined exit condition featuring uncountable and countable comparisons,...
const HistogramInfo * getHistogramInfo(Instruction *I) const
Returns a HistogramInfo* for the given instruction if it was determined to be part of a load -> updat...
const InductionList & getInductionVars() const
Returns the induction variables found in the loop.
LLVM_ABI bool isInvariant(Value *V) const
Returns true if V is invariant across all loop iterations according to SCEV.
const ReductionList & getReductionVars() const
Returns the reduction variables found in the loop.
bool isSafeForAnyStoreLoadForwardDistances() const
Return true if there is store-load forwarding dependencies.
LLVM_ABI bool canFoldTailByMasking() const
Return true if we can vectorize this loop while folding its tail by masking.
LLVM_ABI void prepareToFoldTailByMasking()
Mark all respective loads/stores for masking.
bool hasUncountableEarlyExit() const
Returns true if the loop has uncountable early exits, i.e.
LLVM_ABI bool isUniformMemOp(Instruction &I, std::optional< ElementCount > VF) const
A uniform memory op is a load or store which accesses the same memory location on all VF lanes,...
bool hasHistograms() const
Returns a list of all known histogram operations in the loop.
const LoopAccessInfo * getLAI() const
MapVector< PHINode *, RecurrenceDescriptor > ReductionList
ReductionList contains the reduction descriptors for all of the reductions that were found in the loo...
ScalarEvolution * getScalarEvolution() const
MapVector< PHINode *, ConditionalInductionDescriptor > ConditionalInductionList
ConditionalInductionList saves conditional inductions and maps them to their descriptors.
bool isMaskRequired(const Instruction *I, bool TailFolded) const
Returns true if instruction I requires a mask for vectorization.
LoopVectorizationLegality(const VectorizeOptions &Opts, Loop *L, PredicatedScalarEvolution &PSE, DominatorTree *DT, TargetTransformInfo *TTI, TargetLibraryInfo *TLI, Function *F, LoopAccessInfoManager &LAIs, LoopInfo *LI, OptimizationRemarkEmitter *ORE, LoopVectorizationRequirements *R, LoopVectorizeHints *H, DemandedBits *DB, AssumptionCache *AC, bool AllowRuntimeSCEVChecks, AAResults *AA)
LLVM_ABI bool isUniform(Value *V, std::optional< ElementCount > VF) const
Returns true if value V is uniform across VF lanes, when VF is provided, and otherwise if V is invari...
const RuntimePointerChecking * getRuntimePointerChecking() const
Returns the information that we collected about runtime memory check.
This holds vectorization requirements that must be verified late in the process.
void addExactFPMathInst(Instruction *I)
Track the 1st floating-point instruction that can not be reassociated.
Utility class for getting and setting loop vectorizer hints in the form of loop metadata.
@ SK_PreferScalable
Vectorize loops using scalable vectors or fixed-width vectors, but favor scalable vectors when the co...
@ SK_AlwaysScalable
Always vectorize loops using scalable vectors if feasible (i.e.
@ SK_FixedWidthOnly
Disables vectorization with scalable vectors.
LLVM_ABI bool allowReordering() const
When enabling loop hints are provided we allow the vectorizer to change the order of operations that ...
LLVM_ABI LoopVectorizeHints(const VectorizeOptions &Opts, const Loop *L, bool InterleaveOnlyWhenForced, OptimizationRemarkEmitter &ORE, const TargetTransformInfo *TTI=nullptr)
LLVM_ABI void emitRemarkWithHints() const
Dumps all the hint information.
LLVM_ABI bool allowVectorization(Loop *L, bool VectorizeOnlyWhenForced) const
LLVM_ABI void setAlreadyVectorized()
Mark the loop L as already vectorized by setting the width to 1.
Represents a single loop in the control flow graph.
Definition LoopInfo.h:40
This class implements a map that also provides access to all stored values in a deterministic order.
Definition MapVector.h:39
Root of the metadata hierarchy.
Definition Metadata.h:65
The optimization diagnostic interface.
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
The RecurrenceDescriptor is used to identify recurrences variables in a loop.
Holds information about the memory runtime legality checks to verify that a group of pointers do not ...
This node represents a polynomial recurrence on the trip count of the specified loop.
The main scalar evolution driver.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Represent a constant reference to a string, i.e.
Definition StringRef.h:56
Provides information about what library functions are available for the current target.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition Type.h:46
LLVM Value Representation.
Definition Value.h:75
This is an optimization pass for GlobalISel generic memory operations.
const Value * getLoadStorePointerOperand(const Value *V)
A helper function that returns the pointer operand of a load or store instruction.
HistogramUpdateKind
The kind of update operation performed on the buckets of a histogram, i.e.
UncountableExitTrait
Indicates the characteristics of a loop with an uncountable exit.
LLVM_ABI bool hasDisableAllTransformsHint(const Loop *L)
Look for the loop attribute that disables all transformation heuristic.
LLVM_ABI TransformationMode hasUnrollTransformation(const Loop *L)
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition Casting.h:547
TargetTransformInfo TTI
@ TM_Disable
The transformation should not be applied.
Definition LoopUtils.h:301
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition Alignment.h:39
Holds details about a "compressed" pointer: the conditional induction PHI used to derive the pointer ...
This holds details about a histogram operation – a load -> update -> store sequence where each lane i...
HistogramInfo(LoadInst *Load, Instruction *Update, StoreInst *Store, HistogramUpdateKind UpdateKind)
HistogramUpdateKind UpdateKind
The update operation applied to the histogram buckets.