LLVM 20.0.0git
LoopAccessAnalysis.h
Go to the documentation of this file.
1//===- llvm/Analysis/LoopAccessAnalysis.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// This file defines the interface for the loop memory dependence framework that
10// was originally developed for the Loop Vectorizer.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_ANALYSIS_LOOPACCESSANALYSIS_H
15#define LLVM_ANALYSIS_LOOPACCESSANALYSIS_H
16
21#include <optional>
22#include <variant>
23
24namespace llvm {
25
26class AAResults;
27class DataLayout;
28class Loop;
29class LoopAccessInfo;
30class raw_ostream;
31class SCEV;
32class SCEVUnionPredicate;
33class Value;
34
35/// Collection of parameters shared beetween the Loop Vectorizer and the
36/// Loop Access Analysis.
38 /// Maximum SIMD width.
39 static const unsigned MaxVectorWidth;
40
41 /// VF as overridden by the user.
42 static unsigned VectorizationFactor;
43 /// Interleave factor as overridden by the user.
44 static unsigned VectorizationInterleave;
45 /// True if force-vector-interleave was specified by the user.
46 static bool isInterleaveForced();
47
48 /// \When performing memory disambiguation checks at runtime do not
49 /// make more than this number of comparisons.
51
52 // When creating runtime checks for nested loops, where possible try to
53 // write the checks in a form that allows them to be easily hoisted out of
54 // the outermost loop. For example, we can do this by expanding the range of
55 // addresses considered to include the entire nested loop so that they are
56 // loop invariant.
57 static bool HoistRuntimeChecks;
58};
59
60/// Checks memory dependences among accesses to the same underlying
61/// object to determine whether there vectorization is legal or not (and at
62/// which vectorization factor).
63///
64/// Note: This class will compute a conservative dependence for access to
65/// different underlying pointers. Clients, such as the loop vectorizer, will
66/// sometimes deal these potential dependencies by emitting runtime checks.
67///
68/// We use the ScalarEvolution framework to symbolically evalutate access
69/// functions pairs. Since we currently don't restructure the loop we can rely
70/// on the program order of memory accesses to determine their safety.
71/// At the moment we will only deem accesses as safe for:
72/// * A negative constant distance assuming program order.
73///
74/// Safe: tmp = a[i + 1]; OR a[i + 1] = x;
75/// a[i] = tmp; y = a[i];
76///
77/// The latter case is safe because later checks guarantuee that there can't
78/// be a cycle through a phi node (that is, we check that "x" and "y" is not
79/// the same variable: a header phi can only be an induction or a reduction, a
80/// reduction can't have a memory sink, an induction can't have a memory
81/// source). This is important and must not be violated (or we have to
82/// resort to checking for cycles through memory).
83///
84/// * A positive constant distance assuming program order that is bigger
85/// than the biggest memory access.
86///
87/// tmp = a[i] OR b[i] = x
88/// a[i+2] = tmp y = b[i+2];
89///
90/// Safe distance: 2 x sizeof(a[0]), and 2 x sizeof(b[0]), respectively.
91///
92/// * Zero distances and all accesses have the same size.
93///
95public:
98 /// Set of potential dependent memory accesses.
100
101 /// Type to keep track of the status of the dependence check. The order of
102 /// the elements is important and has to be from most permissive to least
103 /// permissive.
105 // Can vectorize safely without RT checks. All dependences are known to be
106 // safe.
107 Safe,
108 // Can possibly vectorize with RT checks to overcome unknown dependencies.
110 // Cannot vectorize due to known unsafe dependencies.
111 Unsafe,
112 };
113
114 /// Dependece between memory access instructions.
115 struct Dependence {
116 /// The type of the dependence.
117 enum DepType {
118 // No dependence.
120 // We couldn't determine the direction or the distance.
122 // At least one of the memory access instructions may access a loop
123 // varying object, e.g. the address of underlying object is loaded inside
124 // the loop, like A[B[i]]. We cannot determine direction or distance in
125 // those cases, and also are unable to generate any runtime checks.
127
128 // Lexically forward.
129 //
130 // FIXME: If we only have loop-independent forward dependences (e.g. a
131 // read and write of A[i]), LAA will locally deem the dependence "safe"
132 // without querying the MemoryDepChecker. Therefore we can miss
133 // enumerating loop-independent forward dependences in
134 // getDependences. Note that as soon as there are different
135 // indices used to access the same array, the MemoryDepChecker *is*
136 // queried and the dependence list is complete.
138 // Forward, but if vectorized, is likely to prevent store-to-load
139 // forwarding.
141 // Lexically backward.
143 // Backward, but the distance allows a vectorization factor of dependent
144 // on MinDepDistBytes.
146 // Same, but may prevent store-to-load forwarding.
148 };
149
150 /// String version of the types.
151 static const char *DepName[];
152
153 /// Index of the source of the dependence in the InstMap vector.
154 unsigned Source;
155 /// Index of the destination of the dependence in the InstMap vector.
156 unsigned Destination;
157 /// The type of the dependence.
159
162
163 /// Return the source instruction of the dependence.
164 Instruction *getSource(const MemoryDepChecker &DepChecker) const;
165 /// Return the destination instruction of the dependence.
166 Instruction *getDestination(const MemoryDepChecker &DepChecker) const;
167
168 /// Dependence types that don't prevent vectorization.
170
171 /// Lexically forward dependence.
172 bool isForward() const;
173 /// Lexically backward dependence.
174 bool isBackward() const;
175
176 /// May be a lexically backward dependence type (includes Unknown).
177 bool isPossiblyBackward() const;
178
179 /// Print the dependence. \p Instr is used to map the instruction
180 /// indices to instructions.
181 void print(raw_ostream &OS, unsigned Depth,
182 const SmallVectorImpl<Instruction *> &Instrs) const;
183 };
184
186 const DenseMap<Value *, const SCEV *> &SymbolicStrides,
187 unsigned MaxTargetVectorWidthInBits)
188 : PSE(PSE), InnermostLoop(L), SymbolicStrides(SymbolicStrides),
189 MaxTargetVectorWidthInBits(MaxTargetVectorWidthInBits) {}
190
191 /// Register the location (instructions are given increasing numbers)
192 /// of a write access.
193 void addAccess(StoreInst *SI);
194
195 /// Register the location (instructions are given increasing numbers)
196 /// of a write access.
197 void addAccess(LoadInst *LI);
198
199 /// Check whether the dependencies between the accesses are safe.
200 ///
201 /// Only checks sets with elements in \p CheckDeps.
202 bool areDepsSafe(const DepCandidates &AccessSets,
203 const MemAccessInfoList &CheckDeps);
204
205 /// No memory dependence was encountered that would inhibit
206 /// vectorization.
209 }
210
211 /// Return true if the number of elements that are safe to operate on
212 /// simultaneously is not bounded.
214 return MaxSafeVectorWidthInBits == UINT_MAX;
215 }
216
217 /// Return the number of elements that are safe to operate on
218 /// simultaneously, multiplied by the size of the element in bits.
220 return MaxSafeVectorWidthInBits;
221 }
222
223 /// In same cases when the dependency check fails we can still
224 /// vectorize the loop with a dynamic array access check.
226 return FoundNonConstantDistanceDependence &&
228 }
229
230 /// Returns the memory dependences. If null is returned we exceeded
231 /// the MaxDependences threshold and this information is not
232 /// available.
234 return RecordDependences ? &Dependences : nullptr;
235 }
236
237 void clearDependences() { Dependences.clear(); }
238
239 /// The vector of memory access instructions. The indices are used as
240 /// instruction identifiers in the Dependence class.
242 return InstMap;
243 }
244
245 /// Generate a mapping between the memory instructions and their
246 /// indices according to program order.
249
250 for (unsigned I = 0; I < InstMap.size(); ++I)
251 OrderMap[InstMap[I]] = I;
252
253 return OrderMap;
254 }
255
256 /// Find the set of instructions that read or write via \p Ptr.
258 bool isWrite) const;
259
260 /// Return the program order indices for the access location (Ptr, IsWrite).
261 /// Returns an empty ArrayRef if there are no accesses for the location.
263 auto I = Accesses.find({Ptr, IsWrite});
264 if (I != Accesses.end())
265 return I->second;
266 return {};
267 }
268
269 const Loop *getInnermostLoop() const { return InnermostLoop; }
270
272 std::pair<const SCEV *, const SCEV *>> &
274 return PointerBounds;
275 }
276
277private:
278 /// A wrapper around ScalarEvolution, used to add runtime SCEV checks, and
279 /// applies dynamic knowledge to simplify SCEV expressions and convert them
280 /// to a more usable form. We need this in case assumptions about SCEV
281 /// expressions need to be made in order to avoid unknown dependences. For
282 /// example we might assume a unit stride for a pointer in order to prove
283 /// that a memory access is strided and doesn't wrap.
285 const Loop *InnermostLoop;
286
287 /// Reference to map of pointer values to
288 /// their stride symbols, if they have a symbolic stride.
289 const DenseMap<Value *, const SCEV *> &SymbolicStrides;
290
291 /// Maps access locations (ptr, read/write) to program order.
293
294 /// Memory access instructions in program order.
296
297 /// The program order index to be used for the next instruction.
298 unsigned AccessIdx = 0;
299
300 /// The smallest dependence distance in bytes in the loop. This may not be
301 /// the same as the maximum number of bytes that are safe to operate on
302 /// simultaneously.
303 uint64_t MinDepDistBytes = 0;
304
305 /// Number of elements (from consecutive iterations) that are safe to
306 /// operate on simultaneously, multiplied by the size of the element in bits.
307 /// The size of the element is taken from the memory access that is most
308 /// restrictive.
309 uint64_t MaxSafeVectorWidthInBits = -1U;
310
311 /// If we see a non-constant dependence distance we can still try to
312 /// vectorize this loop with runtime checks.
313 bool FoundNonConstantDistanceDependence = false;
314
315 /// Result of the dependence checks, indicating whether the checked
316 /// dependences are safe for vectorization, require RT checks or are known to
317 /// be unsafe.
319
320 //// True if Dependences reflects the dependences in the
321 //// loop. If false we exceeded MaxDependences and
322 //// Dependences is invalid.
323 bool RecordDependences = true;
324
325 /// Memory dependences collected during the analysis. Only valid if
326 /// RecordDependences is true.
327 SmallVector<Dependence, 8> Dependences;
328
329 /// The maximum width of a target's vector registers multiplied by 2 to also
330 /// roughly account for additional interleaving. Is used to decide if a
331 /// backwards dependence with non-constant stride should be classified as
332 /// backwards-vectorizable or unknown (triggering a runtime check).
333 unsigned MaxTargetVectorWidthInBits = 0;
334
335 /// Mapping of SCEV expressions to their expanded pointer bounds (pair of
336 /// start and end pointer expressions).
338 std::pair<const SCEV *, const SCEV *>>
340
341 /// Check whether there is a plausible dependence between the two
342 /// accesses.
343 ///
344 /// Access \p A must happen before \p B in program order. The two indices
345 /// identify the index into the program order map.
346 ///
347 /// This function checks whether there is a plausible dependence (or the
348 /// absence of such can't be proved) between the two accesses. If there is a
349 /// plausible dependence but the dependence distance is bigger than one
350 /// element access it records this distance in \p MinDepDistBytes (if this
351 /// distance is smaller than any other distance encountered so far).
352 /// Otherwise, this function returns true signaling a possible dependence.
353 Dependence::DepType isDependent(const MemAccessInfo &A, unsigned AIdx,
354 const MemAccessInfo &B, unsigned BIdx);
355
356 /// Check whether the data dependence could prevent store-load
357 /// forwarding.
358 ///
359 /// \return false if we shouldn't vectorize at all or avoid larger
360 /// vectorization factors by limiting MinDepDistBytes.
361 bool couldPreventStoreLoadForward(uint64_t Distance, uint64_t TypeByteSize);
362
363 /// Updates the current safety status with \p S. We can go from Safe to
364 /// either PossiblySafeWithRtChecks or Unsafe and from
365 /// PossiblySafeWithRtChecks to Unsafe.
366 void mergeInStatus(VectorizationSafetyStatus S);
367
368 struct DepDistanceStrideAndSizeInfo {
369 const SCEV *Dist;
370 uint64_t StrideA;
371 uint64_t StrideB;
372 uint64_t TypeByteSize;
373 bool AIsWrite;
374 bool BIsWrite;
375
376 DepDistanceStrideAndSizeInfo(const SCEV *Dist, uint64_t StrideA,
377 uint64_t StrideB, uint64_t TypeByteSize,
378 bool AIsWrite, bool BIsWrite)
379 : Dist(Dist), StrideA(StrideA), StrideB(StrideB),
380 TypeByteSize(TypeByteSize), AIsWrite(AIsWrite), BIsWrite(BIsWrite) {}
381 };
382
383 /// Get the dependence distance, strides, type size and whether it is a write
384 /// for the dependence between A and B. Returns a DepType, if we can prove
385 /// there's no dependence or the analysis fails. Outlined to lambda to limit
386 /// he scope of various temporary variables, like A/BPtr, StrideA/BPtr and
387 /// others. Returns either the dependence result, if it could already be
388 /// determined, or a struct containing (Distance, Stride, TypeSize, AIsWrite,
389 /// BIsWrite).
390 std::variant<Dependence::DepType, DepDistanceStrideAndSizeInfo>
391 getDependenceDistanceStrideAndSize(const MemAccessInfo &A, Instruction *AInst,
392 const MemAccessInfo &B,
393 Instruction *BInst);
394};
395
396class RuntimePointerChecking;
397/// A grouping of pointers. A single memcheck is required between
398/// two groups.
400 /// Create a new pointer checking group containing a single
401 /// pointer, with index \p Index in RtCheck.
403 const RuntimePointerChecking &RtCheck);
404
405 /// Tries to add the pointer recorded in RtCheck at index
406 /// \p Index to this pointer checking group. We can only add a pointer
407 /// to a checking group if we will still be able to get
408 /// the upper and lower bounds of the check. Returns true in case
409 /// of success, false otherwise.
410 bool addPointer(unsigned Index, const RuntimePointerChecking &RtCheck);
411 bool addPointer(unsigned Index, const SCEV *Start, const SCEV *End,
412 unsigned AS, bool NeedsFreeze, ScalarEvolution &SE);
413
414 /// The SCEV expression which represents the upper bound of all the
415 /// pointers in this group.
416 const SCEV *High;
417 /// The SCEV expression which represents the lower bound of all the
418 /// pointers in this group.
419 const SCEV *Low;
420 /// Indices of all the pointers that constitute this grouping.
422 /// Address space of the involved pointers.
423 unsigned AddressSpace;
424 /// Whether the pointer needs to be frozen after expansion, e.g. because it
425 /// may be poison outside the loop.
426 bool NeedsFreeze = false;
427};
428
429/// A memcheck which made up of a pair of grouped pointers.
430typedef std::pair<const RuntimeCheckingPtrGroup *,
433
437 unsigned AccessSize;
439
441 unsigned AccessSize, bool NeedsFreeze)
444};
445
446/// Holds information about the memory runtime legality checks to verify
447/// that a group of pointers do not overlap.
450
451public:
452 struct PointerInfo {
453 /// Holds the pointer value that we need to check.
455 /// Holds the smallest byte address accessed by the pointer throughout all
456 /// iterations of the loop.
457 const SCEV *Start;
458 /// Holds the largest byte address accessed by the pointer throughout all
459 /// iterations of the loop, plus 1.
460 const SCEV *End;
461 /// Holds the information if this pointer is used for writing to memory.
463 /// Holds the id of the set of pointers that could be dependent because of a
464 /// shared underlying object.
466 /// Holds the id of the disjoint alias set to which this pointer belongs.
467 unsigned AliasSetId;
468 /// SCEV for the access.
469 const SCEV *Expr;
470 /// True if the pointer expressions needs to be frozen after expansion.
472
474 bool IsWritePtr, unsigned DependencySetId, unsigned AliasSetId,
475 const SCEV *Expr, bool NeedsFreeze)
479 };
480
482 : DC(DC), SE(SE) {}
483
484 /// Reset the state of the pointer runtime information.
485 void reset() {
486 Need = false;
487 Pointers.clear();
488 Checks.clear();
489 DiffChecks.clear();
490 }
491
492 /// Insert a pointer and calculate the start and end SCEVs.
493 /// We need \p PSE in order to compute the SCEV expression of the pointer
494 /// according to the assumptions that we've made during the analysis.
495 /// The method might also version the pointer stride according to \p Strides,
496 /// and add new predicates to \p PSE.
497 void insert(Loop *Lp, Value *Ptr, const SCEV *PtrExpr, Type *AccessTy,
498 bool WritePtr, unsigned DepSetId, unsigned ASId,
499 PredicatedScalarEvolution &PSE, bool NeedsFreeze);
500
501 /// No run-time memory checking is necessary.
502 bool empty() const { return Pointers.empty(); }
503
504 /// Generate the checks and store it. This also performs the grouping
505 /// of pointers to reduce the number of memchecks necessary.
506 void generateChecks(MemoryDepChecker::DepCandidates &DepCands,
507 bool UseDependencies);
508
509 /// Returns the checks that generateChecks created. They can be used to ensure
510 /// no read/write accesses overlap across all loop iterations.
512 return Checks;
513 }
514
515 // Returns an optional list of (pointer-difference expressions, access size)
516 // pairs that can be used to prove that there are no vectorization-preventing
517 // dependencies at runtime. There are is a vectorization-preventing dependency
518 // if any pointer-difference is <u VF * InterleaveCount * access size. Returns
519 // std::nullopt if pointer-difference checks cannot be used.
520 std::optional<ArrayRef<PointerDiffInfo>> getDiffChecks() const {
521 if (!CanUseDiffCheck)
522 return std::nullopt;
523 return {DiffChecks};
524 }
525
526 /// Decide if we need to add a check between two groups of pointers,
527 /// according to needsChecking.
529 const RuntimeCheckingPtrGroup &N) const;
530
531 /// Returns the number of run-time checks required according to
532 /// needsChecking.
533 unsigned getNumberOfChecks() const { return Checks.size(); }
534
535 /// Print the list run-time memory checks necessary.
536 void print(raw_ostream &OS, unsigned Depth = 0) const;
537
538 /// Print \p Checks.
541 unsigned Depth = 0) const;
542
543 /// This flag indicates if we need to add the runtime check.
544 bool Need = false;
545
546 /// Information about the pointers that may require checking.
548
549 /// Holds a partitioning of pointers into "check groups".
551
552 /// Check if pointers are in the same partition
553 ///
554 /// \p PtrToPartition contains the partition number for pointers (-1 if the
555 /// pointer belongs to multiple partitions).
556 static bool
558 unsigned PtrIdx1, unsigned PtrIdx2);
559
560 /// Decide whether we need to issue a run-time check for pointer at
561 /// index \p I and \p J to prove their independence.
562 bool needsChecking(unsigned I, unsigned J) const;
563
564 /// Return PointerInfo for pointer at index \p PtrIdx.
565 const PointerInfo &getPointerInfo(unsigned PtrIdx) const {
566 return Pointers[PtrIdx];
567 }
568
569 ScalarEvolution *getSE() const { return SE; }
570
571private:
572 /// Groups pointers such that a single memcheck is required
573 /// between two different groups. This will clear the CheckingGroups vector
574 /// and re-compute it. We will only group dependecies if \p UseDependencies
575 /// is true, otherwise we will create a separate group for each pointer.
576 void groupChecks(MemoryDepChecker::DepCandidates &DepCands,
577 bool UseDependencies);
578
579 /// Generate the checks and return them.
581
582 /// Try to create add a new (pointer-difference, access size) pair to
583 /// DiffCheck for checking groups \p CGI and \p CGJ. If pointer-difference
584 /// checks cannot be used for the groups, set CanUseDiffCheck to false.
585 bool tryToCreateDiffCheck(const RuntimeCheckingPtrGroup &CGI,
586 const RuntimeCheckingPtrGroup &CGJ);
587
589
590 /// Holds a pointer to the ScalarEvolution analysis.
591 ScalarEvolution *SE;
592
593 /// Set of run-time checks required to establish independence of
594 /// otherwise may-aliasing pointers in the loop.
596
597 /// Flag indicating if pointer-difference checks can be used
598 bool CanUseDiffCheck = true;
599
600 /// A list of (pointer-difference, access size) pairs that can be used to
601 /// prove that there are no vectorization-preventing dependencies.
603};
604
605/// Drive the analysis of memory accesses in the loop
606///
607/// This class is responsible for analyzing the memory accesses of a loop. It
608/// collects the accesses and then its main helper the AccessAnalysis class
609/// finds and categorizes the dependences in buildDependenceSets.
610///
611/// For memory dependences that can be analyzed at compile time, it determines
612/// whether the dependence is part of cycle inhibiting vectorization. This work
613/// is delegated to the MemoryDepChecker class.
614///
615/// For memory dependences that cannot be determined at compile time, it
616/// generates run-time checks to prove independence. This is done by
617/// AccessAnalysis::canCheckPtrAtRT and the checks are maintained by the
618/// RuntimePointerCheck class.
619///
620/// If pointers can wrap or can't be expressed as affine AddRec expressions by
621/// ScalarEvolution, we will generate run-time checks by emitting a
622/// SCEVUnionPredicate.
623///
624/// Checks for both memory dependences and the SCEV predicates contained in the
625/// PSE must be emitted in order for the results of this analysis to be valid.
627public:
629 const TargetLibraryInfo *TLI, AAResults *AA, DominatorTree *DT,
630 LoopInfo *LI);
631
632 /// Return true we can analyze the memory accesses in the loop and there are
633 /// no memory dependence cycles. Note that for dependences between loads &
634 /// stores with uniform addresses,
635 /// hasStoreStoreDependenceInvolvingLoopInvariantAddress and
636 /// hasLoadStoreDependenceInvolvingLoopInvariantAddress also need to be
637 /// checked.
638 bool canVectorizeMemory() const { return CanVecMem; }
639
640 /// Return true if there is a convergent operation in the loop. There may
641 /// still be reported runtime pointer checks that would be required, but it is
642 /// not legal to insert them.
643 bool hasConvergentOp() const { return HasConvergentOp; }
644
646 return PtrRtChecking.get();
647 }
648
649 /// Number of memchecks required to prove independence of otherwise
650 /// may-alias pointers.
651 unsigned getNumRuntimePointerChecks() const {
652 return PtrRtChecking->getNumberOfChecks();
653 }
654
655 /// Return true if the block BB needs to be predicated in order for the loop
656 /// to be vectorized.
657 static bool blockNeedsPredication(BasicBlock *BB, Loop *TheLoop,
658 DominatorTree *DT);
659
660 /// Returns true if value \p V is loop invariant.
661 bool isInvariant(Value *V) const;
662
663 unsigned getNumStores() const { return NumStores; }
664 unsigned getNumLoads() const { return NumLoads;}
665
666 /// The diagnostics report generated for the analysis. E.g. why we
667 /// couldn't analyze the loop.
668 const OptimizationRemarkAnalysis *getReport() const { return Report.get(); }
669
670 /// the Memory Dependence Checker which can determine the
671 /// loop-independent and loop-carried dependences between memory accesses.
672 const MemoryDepChecker &getDepChecker() const { return *DepChecker; }
673
674 /// Return the list of instructions that use \p Ptr to read or write
675 /// memory.
677 bool isWrite) const {
678 return DepChecker->getInstructionsForAccess(Ptr, isWrite);
679 }
680
681 /// If an access has a symbolic strides, this maps the pointer value to
682 /// the stride symbol.
684 return SymbolicStrides;
685 }
686
687 /// Print the information about the memory accesses in the loop.
688 void print(raw_ostream &OS, unsigned Depth = 0) const;
689
690 /// Return true if the loop has memory dependence involving two stores to an
691 /// invariant address, else return false.
693 return HasStoreStoreDependenceInvolvingLoopInvariantAddress;
694 }
695
696 /// Return true if the loop has memory dependence involving a load and a store
697 /// to an invariant address, else return false.
699 return HasLoadStoreDependenceInvolvingLoopInvariantAddress;
700 }
701
702 /// Return the list of stores to invariant addresses.
704 return StoresToInvariantAddresses;
705 }
706
707 /// Used to add runtime SCEV checks. Simplifies SCEV expressions and converts
708 /// them to a more usable form. All SCEV expressions during the analysis
709 /// should be re-written (and therefore simplified) according to PSE.
710 /// A user of LoopAccessAnalysis will need to emit the runtime checks
711 /// associated with this predicate.
712 const PredicatedScalarEvolution &getPSE() const { return *PSE; }
713
714private:
715 /// Analyze the loop. Returns true if all memory access in the loop can be
716 /// vectorized.
717 bool analyzeLoop(AAResults *AA, const LoopInfo *LI,
718 const TargetLibraryInfo *TLI, DominatorTree *DT);
719
720 /// Check if the structure of the loop allows it to be analyzed by this
721 /// pass.
722 bool canAnalyzeLoop();
723
724 /// Save the analysis remark.
725 ///
726 /// LAA does not directly emits the remarks. Instead it stores it which the
727 /// client can retrieve and presents as its own analysis
728 /// (e.g. -Rpass-analysis=loop-vectorize).
730 recordAnalysis(StringRef RemarkName, const Instruction *Instr = nullptr);
731
732 /// Collect memory access with loop invariant strides.
733 ///
734 /// Looks for accesses like "a[i * StrideA]" where "StrideA" is loop
735 /// invariant.
736 void collectStridedAccess(Value *LoadOrStoreInst);
737
738 // Emits the first unsafe memory dependence in a loop.
739 // Emits nothing if there are no unsafe dependences
740 // or if the dependences were not recorded.
741 void emitUnsafeDependenceRemark();
742
743 std::unique_ptr<PredicatedScalarEvolution> PSE;
744
745 /// We need to check that all of the pointers in this list are disjoint
746 /// at runtime. Using std::unique_ptr to make using move ctor simpler.
747 std::unique_ptr<RuntimePointerChecking> PtrRtChecking;
748
749 /// the Memory Dependence Checker which can determine the
750 /// loop-independent and loop-carried dependences between memory accesses.
751 std::unique_ptr<MemoryDepChecker> DepChecker;
752
753 Loop *TheLoop;
754
755 unsigned NumLoads = 0;
756 unsigned NumStores = 0;
757
758 /// Cache the result of analyzeLoop.
759 bool CanVecMem = false;
760 bool HasConvergentOp = false;
761
762 /// Indicator that there are two non vectorizable stores to the same uniform
763 /// address.
764 bool HasStoreStoreDependenceInvolvingLoopInvariantAddress = false;
765 /// Indicator that there is non vectorizable load and store to the same
766 /// uniform address.
767 bool HasLoadStoreDependenceInvolvingLoopInvariantAddress = false;
768
769 /// List of stores to invariant addresses.
770 SmallVector<StoreInst *> StoresToInvariantAddresses;
771
772 /// The diagnostics report generated for the analysis. E.g. why we
773 /// couldn't analyze the loop.
774 std::unique_ptr<OptimizationRemarkAnalysis> Report;
775
776 /// If an access has a symbolic strides, this maps the pointer value to
777 /// the stride symbol.
778 DenseMap<Value *, const SCEV *> SymbolicStrides;
779};
780
781/// Return the SCEV corresponding to a pointer with the symbolic stride
782/// replaced with constant one, assuming the SCEV predicate associated with
783/// \p PSE is true.
784///
785/// If necessary this method will version the stride of the pointer according
786/// to \p PtrToStride and therefore add further predicates to \p PSE.
787///
788/// \p PtrToStride provides the mapping between the pointer value and its
789/// stride as collected by LoopVectorizationLegality::collectStridedAccess.
790const SCEV *
791replaceSymbolicStrideSCEV(PredicatedScalarEvolution &PSE,
792 const DenseMap<Value *, const SCEV *> &PtrToStride,
793 Value *Ptr);
794
795/// If the pointer has a constant stride return it in units of the access type
796/// size. If the pointer is loop-invariant, return 0. Otherwise return
797/// std::nullopt.
798///
799/// Ensure that it does not wrap in the address space, assuming the predicate
800/// associated with \p PSE is true.
801///
802/// If necessary this method will version the stride of the pointer according
803/// to \p PtrToStride and therefore add further predicates to \p PSE.
804/// The \p Assume parameter indicates if we are allowed to make additional
805/// run-time assumptions.
806///
807/// Note that the analysis results are defined if-and-only-if the original
808/// memory access was defined. If that access was dead, or UB, then the
809/// result of this function is undefined.
810std::optional<int64_t>
811getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy, Value *Ptr,
812 const Loop *Lp,
813 const DenseMap<Value *, const SCEV *> &StridesMap = DenseMap<Value *, const SCEV *>(),
814 bool Assume = false, bool ShouldCheckWrap = true);
815
816/// Returns the distance between the pointers \p PtrA and \p PtrB iff they are
817/// compatible and it is possible to calculate the distance between them. This
818/// is a simple API that does not depend on the analysis pass.
819/// \param StrictCheck Ensure that the calculated distance matches the
820/// type-based one after all the bitcasts removal in the provided pointers.
821std::optional<int> getPointersDiff(Type *ElemTyA, Value *PtrA, Type *ElemTyB,
822 Value *PtrB, const DataLayout &DL,
823 ScalarEvolution &SE,
824 bool StrictCheck = false,
825 bool CheckType = true);
826
827/// Attempt to sort the pointers in \p VL and return the sorted indices
828/// in \p SortedIndices, if reordering is required.
829///
830/// Returns 'true' if sorting is legal, otherwise returns 'false'.
831///
832/// For example, for a given \p VL of memory accesses in program order, a[i+4],
833/// a[i+0], a[i+1] and a[i+7], this function will sort the \p VL and save the
834/// sorted indices in \p SortedIndices as a[i+0], a[i+1], a[i+4], a[i+7] and
835/// saves the mask for actual memory accesses in program order in
836/// \p SortedIndices as <1,2,0,3>
837bool sortPtrAccesses(ArrayRef<Value *> VL, Type *ElemTy, const DataLayout &DL,
838 ScalarEvolution &SE,
839 SmallVectorImpl<unsigned> &SortedIndices);
840
841/// Returns true if the memory operations \p A and \p B are consecutive.
842/// This is a simple API that does not depend on the analysis pass.
843bool isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL,
844 ScalarEvolution &SE, bool CheckType = true);
845
847 /// The cache.
849
850 // The used analysis passes.
851 ScalarEvolution &SE;
852 AAResults &AA;
853 DominatorTree &DT;
854 LoopInfo &LI;
856 const TargetLibraryInfo *TLI = nullptr;
857
858public:
861 const TargetLibraryInfo *TLI)
862 : SE(SE), AA(AA), DT(DT), LI(LI), TTI(TTI), TLI(TLI) {}
863
864 const LoopAccessInfo &getInfo(Loop &L);
865
866 void clear();
867
868 bool invalidate(Function &F, const PreservedAnalyses &PA,
870};
871
872/// This analysis provides dependence information for the memory
873/// accesses of a loop.
874///
875/// It runs the analysis for a loop on demand. This can be initiated by
876/// querying the loop access info via AM.getResult<LoopAccessAnalysis>.
877/// getResult return a LoopAccessInfo object. See this class for the
878/// specifics of what information is provided.
880 : public AnalysisInfoMixin<LoopAccessAnalysis> {
882 static AnalysisKey Key;
883
884public:
886
888};
889
891 const MemoryDepChecker &DepChecker) const {
892 return DepChecker.getMemoryInstructions()[Source];
893}
894
896 const MemoryDepChecker &DepChecker) const {
897 return DepChecker.getMemoryInstructions()[Destination];
898}
899
900} // End llvm namespace
901
902#endif
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
MapVector< const Value *, unsigned > OrderMap
Definition: AsmWriter.cpp:99
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
bool End
Definition: ELF_riscv.cpp:480
Generic implementation of equivalence classes through the use Tarjan's efficient union-find algorithm...
This header provides classes for managing per-loop analyses.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
raw_pwrite_stream & OS
static LLVM_ATTRIBUTE_ALWAYS_INLINE bool CheckType(MVT::SimpleValueType VT, SDValue N, const TargetLowering *TLI, const DataLayout &DL)
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:292
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:253
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
EquivalenceClasses - This represents a collection of equivalence classes and supports three efficient...
An instruction for reading from memory.
Definition: Instructions.h:174
This analysis provides dependence information for the memory accesses of a loop.
LoopAccessInfoManager Result
Result run(Function &F, FunctionAnalysisManager &AM)
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
const LoopAccessInfo & getInfo(Loop &L)
LoopAccessInfoManager(ScalarEvolution &SE, AAResults &AA, DominatorTree &DT, LoopInfo &LI, TargetTransformInfo *TTI, const TargetLibraryInfo *TLI)
Drive the analysis of memory accesses in the loop.
const MemoryDepChecker & getDepChecker() const
the Memory Dependence Checker which can determine the loop-independent and loop-carried dependences b...
ArrayRef< StoreInst * > getStoresToInvariantAddresses() const
Return the list of stores to invariant addresses.
const OptimizationRemarkAnalysis * getReport() const
The diagnostics report generated for the analysis.
const RuntimePointerChecking * getRuntimePointerChecking() const
bool canVectorizeMemory() const
Return true we can analyze the memory accesses in the loop and there are no memory dependence cycles.
unsigned getNumLoads() const
unsigned getNumRuntimePointerChecks() const
Number of memchecks required to prove independence of otherwise may-alias pointers.
bool isInvariant(Value *V) const
Returns true if value V is loop invariant.
bool hasLoadStoreDependenceInvolvingLoopInvariantAddress() const
Return true if the loop has memory dependence involving a load and a store to an invariant address,...
void print(raw_ostream &OS, unsigned Depth=0) const
Print the information about the memory accesses in the loop.
const PredicatedScalarEvolution & getPSE() const
Used to add runtime SCEV checks.
unsigned getNumStores() const
static bool blockNeedsPredication(BasicBlock *BB, Loop *TheLoop, DominatorTree *DT)
Return true if the block BB needs to be predicated in order for the loop to be vectorized.
SmallVector< Instruction *, 4 > getInstructionsForAccess(Value *Ptr, bool isWrite) const
Return the list of instructions that use Ptr to read or write memory.
const DenseMap< Value *, const SCEV * > & getSymbolicStrides() const
If an access has a symbolic strides, this maps the pointer value to the stride symbol.
bool hasStoreStoreDependenceInvolvingLoopInvariantAddress() const
Return true if the loop has memory dependence involving two stores to an invariant address,...
bool hasConvergentOp() const
Return true if there is a convergent operation in the loop.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:44
Checks memory dependences among accesses to the same underlying object to determine whether there vec...
ArrayRef< unsigned > getOrderForAccess(Value *Ptr, bool IsWrite) const
Return the program order indices for the access location (Ptr, IsWrite).
bool isSafeForAnyVectorWidth() const
Return true if the number of elements that are safe to operate on simultaneously is not bounded.
bool areDepsSafe(const DepCandidates &AccessSets, const MemAccessInfoList &CheckDeps)
Check whether the dependencies between the accesses are safe.
EquivalenceClasses< MemAccessInfo > DepCandidates
Set of potential dependent memory accesses.
MemoryDepChecker(PredicatedScalarEvolution &PSE, const Loop *L, const DenseMap< Value *, const SCEV * > &SymbolicStrides, unsigned MaxTargetVectorWidthInBits)
const SmallVectorImpl< Instruction * > & getMemoryInstructions() const
The vector of memory access instructions.
const Loop * getInnermostLoop() const
uint64_t getMaxSafeVectorWidthInBits() const
Return the number of elements that are safe to operate on simultaneously, multiplied by the size of t...
bool isSafeForVectorization() const
No memory dependence was encountered that would inhibit vectorization.
const SmallVectorImpl< Dependence > * getDependences() const
Returns the memory dependences.
DenseMap< std::pair< const SCEV *, Type * >, std::pair< const SCEV *, const SCEV * > > & getPointerBounds()
SmallVector< MemAccessInfo, 8 > MemAccessInfoList
SmallVector< Instruction *, 4 > getInstructionsForAccess(Value *Ptr, bool isWrite) const
Find the set of instructions that read or write via Ptr.
VectorizationSafetyStatus
Type to keep track of the status of the dependence check.
bool shouldRetryWithRuntimeCheck() const
In same cases when the dependency check fails we can still vectorize the loop with a dynamic array ac...
void addAccess(StoreInst *SI)
Register the location (instructions are given increasing numbers) of a write access.
PointerIntPair< Value *, 1, bool > MemAccessInfo
DenseMap< Instruction *, unsigned > generateInstructionOrderMap() const
Generate a mapping between the memory instructions and their indices according to program order.
Diagnostic information for optimization analysis remarks.
PointerIntPair - This class implements a pair of a pointer and small integer.
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:111
Holds information about the memory runtime legality checks to verify that a group of pointers do not ...
bool Need
This flag indicates if we need to add the runtime check.
void reset()
Reset the state of the pointer runtime information.
unsigned getNumberOfChecks() const
Returns the number of run-time checks required according to needsChecking.
RuntimePointerChecking(MemoryDepChecker &DC, ScalarEvolution *SE)
void printChecks(raw_ostream &OS, const SmallVectorImpl< RuntimePointerCheck > &Checks, unsigned Depth=0) const
Print Checks.
bool needsChecking(const RuntimeCheckingPtrGroup &M, const RuntimeCheckingPtrGroup &N) const
Decide if we need to add a check between two groups of pointers, according to needsChecking.
void print(raw_ostream &OS, unsigned Depth=0) const
Print the list run-time memory checks necessary.
std::optional< ArrayRef< PointerDiffInfo > > getDiffChecks() const
SmallVector< RuntimeCheckingPtrGroup, 2 > CheckingGroups
Holds a partitioning of pointers into "check groups".
static bool arePointersInSamePartition(const SmallVectorImpl< int > &PtrToPartition, unsigned PtrIdx1, unsigned PtrIdx2)
Check if pointers are in the same partition.
bool empty() const
No run-time memory checking is necessary.
SmallVector< PointerInfo, 2 > Pointers
Information about the pointers that may require checking.
ScalarEvolution * getSE() const
void insert(Loop *Lp, Value *Ptr, const SCEV *PtrExpr, Type *AccessTy, bool WritePtr, unsigned DepSetId, unsigned ASId, PredicatedScalarEvolution &PSE, bool NeedsFreeze)
Insert a pointer and calculate the start and end SCEVs.
const SmallVectorImpl< RuntimePointerCheck > & getChecks() const
Returns the checks that generateChecks created.
const PointerInfo & getPointerInfo(unsigned PtrIdx) const
Return PointerInfo for pointer at index PtrIdx.
This class represents an analyzed expression in the program.
The main scalar evolution driver.
size_t size() const
Definition: SmallVector.h:92
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:587
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1210
An instruction for storing to memory.
Definition: Instructions.h:290
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
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.
Value handle that tracks a Value across RAUW.
Definition: ValueHandle.h:331
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
LLVM Value Representation.
Definition: Value.h:74
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
std::optional< int > getPointersDiff(Type *ElemTyA, Value *PtrA, Type *ElemTyB, Value *PtrB, const DataLayout &DL, ScalarEvolution &SE, bool StrictCheck=false, bool CheckType=true)
Returns the distance between the pointers PtrA and PtrB iff they are compatible and it is possible to...
std::pair< const RuntimeCheckingPtrGroup *, const RuntimeCheckingPtrGroup * > RuntimePointerCheck
A memcheck which made up of a pair of grouped pointers.
std::optional< int64_t > getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy, Value *Ptr, const Loop *Lp, const DenseMap< Value *, const SCEV * > &StridesMap=DenseMap< Value *, const SCEV * >(), bool Assume=false, bool ShouldCheckWrap=true)
If the pointer has a constant stride return it in units of the access type size.
bool sortPtrAccesses(ArrayRef< Value * > VL, Type *ElemTy, const DataLayout &DL, ScalarEvolution &SE, SmallVectorImpl< unsigned > &SortedIndices)
Attempt to sort the pointers in VL and return the sorted indices in SortedIndices,...
const SCEV * replaceSymbolicStrideSCEV(PredicatedScalarEvolution &PSE, const DenseMap< Value *, const SCEV * > &PtrToStride, Value *Ptr)
Return the SCEV corresponding to a pointer with the symbolic stride replaced with constant one,...
bool isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL, ScalarEvolution &SE, bool CheckType=true)
Returns true if the memory operations A and B are consecutive.
#define N
IR Values for the lower and upper bounds of a pointer evolution.
Definition: LoopUtils.cpp:1798
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:92
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: Analysis.h:28
Dependece between memory access instructions.
Instruction * getDestination(const MemoryDepChecker &DepChecker) const
Return the destination instruction of the dependence.
DepType Type
The type of the dependence.
unsigned Destination
Index of the destination of the dependence in the InstMap vector.
Dependence(unsigned Source, unsigned Destination, DepType Type)
bool isPossiblyBackward() const
May be a lexically backward dependence type (includes Unknown).
Instruction * getSource(const MemoryDepChecker &DepChecker) const
Return the source instruction of the dependence.
bool isForward() const
Lexically forward dependence.
bool isBackward() const
Lexically backward dependence.
void print(raw_ostream &OS, unsigned Depth, const SmallVectorImpl< Instruction * > &Instrs) const
Print the dependence.
unsigned Source
Index of the source of the dependence in the InstMap vector.
DepType
The type of the dependence.
static const char * DepName[]
String version of the types.
PointerDiffInfo(const SCEV *SrcStart, const SCEV *SinkStart, unsigned AccessSize, bool NeedsFreeze)
unsigned AddressSpace
Address space of the involved pointers.
bool addPointer(unsigned Index, const RuntimePointerChecking &RtCheck)
Tries to add the pointer recorded in RtCheck at index Index to this pointer checking group.
bool NeedsFreeze
Whether the pointer needs to be frozen after expansion, e.g.
const SCEV * High
The SCEV expression which represents the upper bound of all the pointers in this group.
SmallVector< unsigned, 2 > Members
Indices of all the pointers that constitute this grouping.
const SCEV * Low
The SCEV expression which represents the lower bound of all the pointers in this group.
PointerInfo(Value *PointerValue, const SCEV *Start, const SCEV *End, bool IsWritePtr, unsigned DependencySetId, unsigned AliasSetId, const SCEV *Expr, bool NeedsFreeze)
const SCEV * Start
Holds the smallest byte address accessed by the pointer throughout all iterations of the loop.
const SCEV * Expr
SCEV for the access.
bool NeedsFreeze
True if the pointer expressions needs to be frozen after expansion.
bool IsWritePtr
Holds the information if this pointer is used for writing to memory.
unsigned DependencySetId
Holds the id of the set of pointers that could be dependent because of a shared underlying object.
unsigned AliasSetId
Holds the id of the disjoint alias set to which this pointer belongs.
const SCEV * End
Holds the largest byte address accessed by the pointer throughout all iterations of the loop,...
TrackingVH< Value > PointerValue
Holds the pointer value that we need to check.
Collection of parameters shared beetween the Loop Vectorizer and the Loop Access Analysis.
static const unsigned MaxVectorWidth
Maximum SIMD width.
static unsigned VectorizationFactor
VF as overridden by the user.
static unsigned RuntimeMemoryCheckThreshold
\When performing memory disambiguation checks at runtime do not make more than this number of compari...
static bool isInterleaveForced()
True if force-vector-interleave was specified by the user.
static unsigned VectorizationInterleave
Interleave factor as overridden by the user.