LLVM 18.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
23namespace llvm {
24
25class AAResults;
26class DataLayout;
27class Loop;
28class LoopAccessInfo;
29class raw_ostream;
30class SCEV;
31class SCEVUnionPredicate;
32class Value;
33
34/// Collection of parameters shared beetween the Loop Vectorizer and the
35/// Loop Access Analysis.
37 /// Maximum SIMD width.
38 static const unsigned MaxVectorWidth;
39
40 /// VF as overridden by the user.
41 static unsigned VectorizationFactor;
42 /// Interleave factor as overridden by the user.
43 static unsigned VectorizationInterleave;
44 /// True if force-vector-interleave was specified by the user.
45 static bool isInterleaveForced();
46
47 /// \When performing memory disambiguation checks at runtime do not
48 /// make more than this number of comparisons.
50
51 // When creating runtime checks for nested loops, where possible try to
52 // write the checks in a form that allows them to be easily hoisted out of
53 // the outermost loop. For example, we can do this by expanding the range of
54 // addresses considered to include the entire nested loop so that they are
55 // loop invariant.
56 static bool HoistRuntimeChecks;
57};
58
59/// Checks memory dependences among accesses to the same underlying
60/// object to determine whether there vectorization is legal or not (and at
61/// which vectorization factor).
62///
63/// Note: This class will compute a conservative dependence for access to
64/// different underlying pointers. Clients, such as the loop vectorizer, will
65/// sometimes deal these potential dependencies by emitting runtime checks.
66///
67/// We use the ScalarEvolution framework to symbolically evalutate access
68/// functions pairs. Since we currently don't restructure the loop we can rely
69/// on the program order of memory accesses to determine their safety.
70/// At the moment we will only deem accesses as safe for:
71/// * A negative constant distance assuming program order.
72///
73/// Safe: tmp = a[i + 1]; OR a[i + 1] = x;
74/// a[i] = tmp; y = a[i];
75///
76/// The latter case is safe because later checks guarantuee that there can't
77/// be a cycle through a phi node (that is, we check that "x" and "y" is not
78/// the same variable: a header phi can only be an induction or a reduction, a
79/// reduction can't have a memory sink, an induction can't have a memory
80/// source). This is important and must not be violated (or we have to
81/// resort to checking for cycles through memory).
82///
83/// * A positive constant distance assuming program order that is bigger
84/// than the biggest memory access.
85///
86/// tmp = a[i] OR b[i] = x
87/// a[i+2] = tmp y = b[i+2];
88///
89/// Safe distance: 2 x sizeof(a[0]), and 2 x sizeof(b[0]), respectively.
90///
91/// * Zero distances and all accesses have the same size.
92///
94public:
97 /// Set of potential dependent memory accesses.
99
100 /// Type to keep track of the status of the dependence check. The order of
101 /// the elements is important and has to be from most permissive to least
102 /// permissive.
104 // Can vectorize safely without RT checks. All dependences are known to be
105 // safe.
106 Safe,
107 // Can possibly vectorize with RT checks to overcome unknown dependencies.
109 // Cannot vectorize due to known unsafe dependencies.
110 Unsafe,
111 };
112
113 /// Dependece between memory access instructions.
114 struct Dependence {
115 /// The type of the dependence.
116 enum DepType {
117 // No dependence.
119 // We couldn't determine the direction or the distance.
121 // Lexically forward.
122 //
123 // FIXME: If we only have loop-independent forward dependences (e.g. a
124 // read and write of A[i]), LAA will locally deem the dependence "safe"
125 // without querying the MemoryDepChecker. Therefore we can miss
126 // enumerating loop-independent forward dependences in
127 // getDependences. Note that as soon as there are different
128 // indices used to access the same array, the MemoryDepChecker *is*
129 // queried and the dependence list is complete.
131 // Forward, but if vectorized, is likely to prevent store-to-load
132 // forwarding.
134 // Lexically backward.
136 // Backward, but the distance allows a vectorization factor of dependent
137 // on MinDepDistBytes.
139 // Same, but may prevent store-to-load forwarding.
141 };
142
143 /// String version of the types.
144 static const char *DepName[];
145
146 /// Index of the source of the dependence in the InstMap vector.
147 unsigned Source;
148 /// Index of the destination of the dependence in the InstMap vector.
149 unsigned Destination;
150 /// The type of the dependence.
152
155
156 /// Return the source instruction of the dependence.
157 Instruction *getSource(const LoopAccessInfo &LAI) const;
158 /// Return the destination instruction of the dependence.
159 Instruction *getDestination(const LoopAccessInfo &LAI) const;
160
161 /// Dependence types that don't prevent vectorization.
163
164 /// Lexically forward dependence.
165 bool isForward() const;
166 /// Lexically backward dependence.
167 bool isBackward() const;
168
169 /// May be a lexically backward dependence type (includes Unknown).
170 bool isPossiblyBackward() const;
171
172 /// Print the dependence. \p Instr is used to map the instruction
173 /// indices to instructions.
174 void print(raw_ostream &OS, unsigned Depth,
175 const SmallVectorImpl<Instruction *> &Instrs) const;
176 };
177
179 : PSE(PSE), InnermostLoop(L) {}
180
181 /// Register the location (instructions are given increasing numbers)
182 /// of a write access.
183 void addAccess(StoreInst *SI);
184
185 /// Register the location (instructions are given increasing numbers)
186 /// of a write access.
187 void addAccess(LoadInst *LI);
188
189 /// Check whether the dependencies between the accesses are safe.
190 ///
191 /// Only checks sets with elements in \p CheckDeps.
192 bool areDepsSafe(DepCandidates &AccessSets, MemAccessInfoList &CheckDeps,
193 const DenseMap<Value *, const SCEV *> &Strides);
194
195 /// No memory dependence was encountered that would inhibit
196 /// vectorization.
199 }
200
201 /// Return true if the number of elements that are safe to operate on
202 /// simultaneously is not bounded.
204 return MaxSafeVectorWidthInBits == UINT_MAX;
205 }
206
207 /// Return the number of elements that are safe to operate on
208 /// simultaneously, multiplied by the size of the element in bits.
210 return MaxSafeVectorWidthInBits;
211 }
212
213 /// In same cases when the dependency check fails we can still
214 /// vectorize the loop with a dynamic array access check.
216 return FoundNonConstantDistanceDependence &&
218 }
219
220 /// Returns the memory dependences. If null is returned we exceeded
221 /// the MaxDependences threshold and this information is not
222 /// available.
224 return RecordDependences ? &Dependences : nullptr;
225 }
226
227 void clearDependences() { Dependences.clear(); }
228
229 /// The vector of memory access instructions. The indices are used as
230 /// instruction identifiers in the Dependence class.
232 return InstMap;
233 }
234
235 /// Generate a mapping between the memory instructions and their
236 /// indices according to program order.
239
240 for (unsigned I = 0; I < InstMap.size(); ++I)
241 OrderMap[InstMap[I]] = I;
242
243 return OrderMap;
244 }
245
246 /// Find the set of instructions that read or write via \p Ptr.
248 bool isWrite) const;
249
250 /// Return the program order indices for the access location (Ptr, IsWrite).
251 /// Returns an empty ArrayRef if there are no accesses for the location.
253 auto I = Accesses.find({Ptr, IsWrite});
254 if (I != Accesses.end())
255 return I->second;
256 return {};
257 }
258
259 const Loop *getInnermostLoop() const { return InnermostLoop; }
260
261private:
262 /// A wrapper around ScalarEvolution, used to add runtime SCEV checks, and
263 /// applies dynamic knowledge to simplify SCEV expressions and convert them
264 /// to a more usable form. We need this in case assumptions about SCEV
265 /// expressions need to be made in order to avoid unknown dependences. For
266 /// example we might assume a unit stride for a pointer in order to prove
267 /// that a memory access is strided and doesn't wrap.
269 const Loop *InnermostLoop;
270
271 /// Maps access locations (ptr, read/write) to program order.
273
274 /// Memory access instructions in program order.
276
277 /// The program order index to be used for the next instruction.
278 unsigned AccessIdx = 0;
279
280 /// The smallest dependence distance in bytes in the loop. This may not be
281 /// the same as the maximum number of bytes that are safe to operate on
282 /// simultaneously.
283 uint64_t MinDepDistBytes = 0;
284
285 /// Number of elements (from consecutive iterations) that are safe to
286 /// operate on simultaneously, multiplied by the size of the element in bits.
287 /// The size of the element is taken from the memory access that is most
288 /// restrictive.
289 uint64_t MaxSafeVectorWidthInBits = -1U;
290
291 /// If we see a non-constant dependence distance we can still try to
292 /// vectorize this loop with runtime checks.
293 bool FoundNonConstantDistanceDependence = false;
294
295 /// Result of the dependence checks, indicating whether the checked
296 /// dependences are safe for vectorization, require RT checks or are known to
297 /// be unsafe.
299
300 //// True if Dependences reflects the dependences in the
301 //// loop. If false we exceeded MaxDependences and
302 //// Dependences is invalid.
303 bool RecordDependences = true;
304
305 /// Memory dependences collected during the analysis. Only valid if
306 /// RecordDependences is true.
307 SmallVector<Dependence, 8> Dependences;
308
309 /// Check whether there is a plausible dependence between the two
310 /// accesses.
311 ///
312 /// Access \p A must happen before \p B in program order. The two indices
313 /// identify the index into the program order map.
314 ///
315 /// This function checks whether there is a plausible dependence (or the
316 /// absence of such can't be proved) between the two accesses. If there is a
317 /// plausible dependence but the dependence distance is bigger than one
318 /// element access it records this distance in \p MinDepDistBytes (if this
319 /// distance is smaller than any other distance encountered so far).
320 /// Otherwise, this function returns true signaling a possible dependence.
321 Dependence::DepType isDependent(const MemAccessInfo &A, unsigned AIdx,
322 const MemAccessInfo &B, unsigned BIdx,
323 const DenseMap<Value *, const SCEV *> &Strides);
324
325 /// Check whether the data dependence could prevent store-load
326 /// forwarding.
327 ///
328 /// \return false if we shouldn't vectorize at all or avoid larger
329 /// vectorization factors by limiting MinDepDistBytes.
330 bool couldPreventStoreLoadForward(uint64_t Distance, uint64_t TypeByteSize);
331
332 /// Updates the current safety status with \p S. We can go from Safe to
333 /// either PossiblySafeWithRtChecks or Unsafe and from
334 /// PossiblySafeWithRtChecks to Unsafe.
335 void mergeInStatus(VectorizationSafetyStatus S);
336};
337
338class RuntimePointerChecking;
339/// A grouping of pointers. A single memcheck is required between
340/// two groups.
342 /// Create a new pointer checking group containing a single
343 /// pointer, with index \p Index in RtCheck.
345
346 /// Tries to add the pointer recorded in RtCheck at index
347 /// \p Index to this pointer checking group. We can only add a pointer
348 /// to a checking group if we will still be able to get
349 /// the upper and lower bounds of the check. Returns true in case
350 /// of success, false otherwise.
351 bool addPointer(unsigned Index, RuntimePointerChecking &RtCheck);
352 bool addPointer(unsigned Index, const SCEV *Start, const SCEV *End,
353 unsigned AS, bool NeedsFreeze, ScalarEvolution &SE);
354
355 /// The SCEV expression which represents the upper bound of all the
356 /// pointers in this group.
357 const SCEV *High;
358 /// The SCEV expression which represents the lower bound of all the
359 /// pointers in this group.
360 const SCEV *Low;
361 /// Indices of all the pointers that constitute this grouping.
363 /// Address space of the involved pointers.
364 unsigned AddressSpace;
365 /// Whether the pointer needs to be frozen after expansion, e.g. because it
366 /// may be poison outside the loop.
367 bool NeedsFreeze = false;
368};
369
370/// A memcheck which made up of a pair of grouped pointers.
371typedef std::pair<const RuntimeCheckingPtrGroup *,
374
378 unsigned AccessSize;
380
382 unsigned AccessSize, bool NeedsFreeze)
385};
386
387/// Holds information about the memory runtime legality checks to verify
388/// that a group of pointers do not overlap.
391
392public:
393 struct PointerInfo {
394 /// Holds the pointer value that we need to check.
396 /// Holds the smallest byte address accessed by the pointer throughout all
397 /// iterations of the loop.
398 const SCEV *Start;
399 /// Holds the largest byte address accessed by the pointer throughout all
400 /// iterations of the loop, plus 1.
401 const SCEV *End;
402 /// Holds the information if this pointer is used for writing to memory.
404 /// Holds the id of the set of pointers that could be dependent because of a
405 /// shared underlying object.
407 /// Holds the id of the disjoint alias set to which this pointer belongs.
408 unsigned AliasSetId;
409 /// SCEV for the access.
410 const SCEV *Expr;
411 /// True if the pointer expressions needs to be frozen after expansion.
413
415 bool IsWritePtr, unsigned DependencySetId, unsigned AliasSetId,
416 const SCEV *Expr, bool NeedsFreeze)
420 };
421
423 : DC(DC), SE(SE) {}
424
425 /// Reset the state of the pointer runtime information.
426 void reset() {
427 Need = false;
428 Pointers.clear();
429 Checks.clear();
430 }
431
432 /// Insert a pointer and calculate the start and end SCEVs.
433 /// We need \p PSE in order to compute the SCEV expression of the pointer
434 /// according to the assumptions that we've made during the analysis.
435 /// The method might also version the pointer stride according to \p Strides,
436 /// and add new predicates to \p PSE.
437 void insert(Loop *Lp, Value *Ptr, const SCEV *PtrExpr, Type *AccessTy,
438 bool WritePtr, unsigned DepSetId, unsigned ASId,
439 PredicatedScalarEvolution &PSE, bool NeedsFreeze);
440
441 /// No run-time memory checking is necessary.
442 bool empty() const { return Pointers.empty(); }
443
444 /// Generate the checks and store it. This also performs the grouping
445 /// of pointers to reduce the number of memchecks necessary.
446 void generateChecks(MemoryDepChecker::DepCandidates &DepCands,
447 bool UseDependencies);
448
449 /// Returns the checks that generateChecks created. They can be used to ensure
450 /// no read/write accesses overlap across all loop iterations.
452 return Checks;
453 }
454
455 // Returns an optional list of (pointer-difference expressions, access size)
456 // pairs that can be used to prove that there are no vectorization-preventing
457 // dependencies at runtime. There are is a vectorization-preventing dependency
458 // if any pointer-difference is <u VF * InterleaveCount * access size. Returns
459 // std::nullopt if pointer-difference checks cannot be used.
460 std::optional<ArrayRef<PointerDiffInfo>> getDiffChecks() const {
461 if (!CanUseDiffCheck)
462 return std::nullopt;
463 return {DiffChecks};
464 }
465
466 /// Decide if we need to add a check between two groups of pointers,
467 /// according to needsChecking.
469 const RuntimeCheckingPtrGroup &N) const;
470
471 /// Returns the number of run-time checks required according to
472 /// needsChecking.
473 unsigned getNumberOfChecks() const { return Checks.size(); }
474
475 /// Print the list run-time memory checks necessary.
476 void print(raw_ostream &OS, unsigned Depth = 0) const;
477
478 /// Print \p Checks.
481 unsigned Depth = 0) const;
482
483 /// This flag indicates if we need to add the runtime check.
484 bool Need = false;
485
486 /// Information about the pointers that may require checking.
488
489 /// Holds a partitioning of pointers into "check groups".
491
492 /// Check if pointers are in the same partition
493 ///
494 /// \p PtrToPartition contains the partition number for pointers (-1 if the
495 /// pointer belongs to multiple partitions).
496 static bool
498 unsigned PtrIdx1, unsigned PtrIdx2);
499
500 /// Decide whether we need to issue a run-time check for pointer at
501 /// index \p I and \p J to prove their independence.
502 bool needsChecking(unsigned I, unsigned J) const;
503
504 /// Return PointerInfo for pointer at index \p PtrIdx.
505 const PointerInfo &getPointerInfo(unsigned PtrIdx) const {
506 return Pointers[PtrIdx];
507 }
508
509 ScalarEvolution *getSE() const { return SE; }
510
511private:
512 /// Groups pointers such that a single memcheck is required
513 /// between two different groups. This will clear the CheckingGroups vector
514 /// and re-compute it. We will only group dependecies if \p UseDependencies
515 /// is true, otherwise we will create a separate group for each pointer.
516 void groupChecks(MemoryDepChecker::DepCandidates &DepCands,
517 bool UseDependencies);
518
519 /// Generate the checks and return them.
521
522 /// Try to create add a new (pointer-difference, access size) pair to
523 /// DiffCheck for checking groups \p CGI and \p CGJ. If pointer-difference
524 /// checks cannot be used for the groups, set CanUseDiffCheck to false.
525 void tryToCreateDiffCheck(const RuntimeCheckingPtrGroup &CGI,
526 const RuntimeCheckingPtrGroup &CGJ);
527
529
530 /// Holds a pointer to the ScalarEvolution analysis.
531 ScalarEvolution *SE;
532
533 /// Set of run-time checks required to establish independence of
534 /// otherwise may-aliasing pointers in the loop.
536
537 /// Flag indicating if pointer-difference checks can be used
538 bool CanUseDiffCheck = true;
539
540 /// A list of (pointer-difference, access size) pairs that can be used to
541 /// prove that there are no vectorization-preventing dependencies.
543};
544
545/// Drive the analysis of memory accesses in the loop
546///
547/// This class is responsible for analyzing the memory accesses of a loop. It
548/// collects the accesses and then its main helper the AccessAnalysis class
549/// finds and categorizes the dependences in buildDependenceSets.
550///
551/// For memory dependences that can be analyzed at compile time, it determines
552/// whether the dependence is part of cycle inhibiting vectorization. This work
553/// is delegated to the MemoryDepChecker class.
554///
555/// For memory dependences that cannot be determined at compile time, it
556/// generates run-time checks to prove independence. This is done by
557/// AccessAnalysis::canCheckPtrAtRT and the checks are maintained by the
558/// RuntimePointerCheck class.
559///
560/// If pointers can wrap or can't be expressed as affine AddRec expressions by
561/// ScalarEvolution, we will generate run-time checks by emitting a
562/// SCEVUnionPredicate.
563///
564/// Checks for both memory dependences and the SCEV predicates contained in the
565/// PSE must be emitted in order for the results of this analysis to be valid.
567public:
569 AAResults *AA, DominatorTree *DT, LoopInfo *LI);
570
571 /// Return true we can analyze the memory accesses in the loop and there are
572 /// no memory dependence cycles.
573 bool canVectorizeMemory() const { return CanVecMem; }
574
575 /// Return true if there is a convergent operation in the loop. There may
576 /// still be reported runtime pointer checks that would be required, but it is
577 /// not legal to insert them.
578 bool hasConvergentOp() const { return HasConvergentOp; }
579
581 return PtrRtChecking.get();
582 }
583
584 /// Number of memchecks required to prove independence of otherwise
585 /// may-alias pointers.
586 unsigned getNumRuntimePointerChecks() const {
587 return PtrRtChecking->getNumberOfChecks();
588 }
589
590 /// Return true if the block BB needs to be predicated in order for the loop
591 /// to be vectorized.
592 static bool blockNeedsPredication(BasicBlock *BB, Loop *TheLoop,
593 DominatorTree *DT);
594
595 /// Returns true if value \p V is loop invariant.
596 bool isInvariant(Value *V) const;
597
598 unsigned getNumStores() const { return NumStores; }
599 unsigned getNumLoads() const { return NumLoads;}
600
601 /// The diagnostics report generated for the analysis. E.g. why we
602 /// couldn't analyze the loop.
603 const OptimizationRemarkAnalysis *getReport() const { return Report.get(); }
604
605 /// the Memory Dependence Checker which can determine the
606 /// loop-independent and loop-carried dependences between memory accesses.
607 const MemoryDepChecker &getDepChecker() const { return *DepChecker; }
608
609 /// Return the list of instructions that use \p Ptr to read or write
610 /// memory.
612 bool isWrite) const {
613 return DepChecker->getInstructionsForAccess(Ptr, isWrite);
614 }
615
616 /// If an access has a symbolic strides, this maps the pointer value to
617 /// the stride symbol.
619 return SymbolicStrides;
620 }
621
622 /// Print the information about the memory accesses in the loop.
623 void print(raw_ostream &OS, unsigned Depth = 0) const;
624
625 /// If the loop has memory dependence involving an invariant address, i.e. two
626 /// stores or a store and a load, then return true, else return false.
628 return HasDependenceInvolvingLoopInvariantAddress;
629 }
630
631 /// Return the list of stores to invariant addresses.
633 return StoresToInvariantAddresses;
634 }
635
636 /// Used to add runtime SCEV checks. Simplifies SCEV expressions and converts
637 /// them to a more usable form. All SCEV expressions during the analysis
638 /// should be re-written (and therefore simplified) according to PSE.
639 /// A user of LoopAccessAnalysis will need to emit the runtime checks
640 /// associated with this predicate.
641 const PredicatedScalarEvolution &getPSE() const { return *PSE; }
642
643private:
644 /// Analyze the loop.
645 void analyzeLoop(AAResults *AA, LoopInfo *LI,
646 const TargetLibraryInfo *TLI, DominatorTree *DT);
647
648 /// Check if the structure of the loop allows it to be analyzed by this
649 /// pass.
650 bool canAnalyzeLoop();
651
652 /// Save the analysis remark.
653 ///
654 /// LAA does not directly emits the remarks. Instead it stores it which the
655 /// client can retrieve and presents as its own analysis
656 /// (e.g. -Rpass-analysis=loop-vectorize).
657 OptimizationRemarkAnalysis &recordAnalysis(StringRef RemarkName,
658 Instruction *Instr = nullptr);
659
660 /// Collect memory access with loop invariant strides.
661 ///
662 /// Looks for accesses like "a[i * StrideA]" where "StrideA" is loop
663 /// invariant.
664 void collectStridedAccess(Value *LoadOrStoreInst);
665
666 // Emits the first unsafe memory dependence in a loop.
667 // Emits nothing if there are no unsafe dependences
668 // or if the dependences were not recorded.
669 void emitUnsafeDependenceRemark();
670
671 std::unique_ptr<PredicatedScalarEvolution> PSE;
672
673 /// We need to check that all of the pointers in this list are disjoint
674 /// at runtime. Using std::unique_ptr to make using move ctor simpler.
675 std::unique_ptr<RuntimePointerChecking> PtrRtChecking;
676
677 /// the Memory Dependence Checker which can determine the
678 /// loop-independent and loop-carried dependences between memory accesses.
679 std::unique_ptr<MemoryDepChecker> DepChecker;
680
681 Loop *TheLoop;
682
683 unsigned NumLoads = 0;
684 unsigned NumStores = 0;
685
686 /// Cache the result of analyzeLoop.
687 bool CanVecMem = false;
688 bool HasConvergentOp = false;
689
690 /// Indicator that there are non vectorizable stores to a uniform address.
691 bool HasDependenceInvolvingLoopInvariantAddress = false;
692
693 /// List of stores to invariant addresses.
694 SmallVector<StoreInst *> StoresToInvariantAddresses;
695
696 /// The diagnostics report generated for the analysis. E.g. why we
697 /// couldn't analyze the loop.
698 std::unique_ptr<OptimizationRemarkAnalysis> Report;
699
700 /// If an access has a symbolic strides, this maps the pointer value to
701 /// the stride symbol.
702 DenseMap<Value *, const SCEV *> SymbolicStrides;
703};
704
705/// Return the SCEV corresponding to a pointer with the symbolic stride
706/// replaced with constant one, assuming the SCEV predicate associated with
707/// \p PSE is true.
708///
709/// If necessary this method will version the stride of the pointer according
710/// to \p PtrToStride and therefore add further predicates to \p PSE.
711///
712/// \p PtrToStride provides the mapping between the pointer value and its
713/// stride as collected by LoopVectorizationLegality::collectStridedAccess.
714const SCEV *
715replaceSymbolicStrideSCEV(PredicatedScalarEvolution &PSE,
716 const DenseMap<Value *, const SCEV *> &PtrToStride,
717 Value *Ptr);
718
719/// If the pointer has a constant stride return it in units of the access type
720/// size. Otherwise return std::nullopt.
721///
722/// Ensure that it does not wrap in the address space, assuming the predicate
723/// associated with \p PSE is true.
724///
725/// If necessary this method will version the stride of the pointer according
726/// to \p PtrToStride and therefore add further predicates to \p PSE.
727/// The \p Assume parameter indicates if we are allowed to make additional
728/// run-time assumptions.
729///
730/// Note that the analysis results are defined if-and-only-if the original
731/// memory access was defined. If that access was dead, or UB, then the
732/// result of this function is undefined.
733std::optional<int64_t>
734getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy, Value *Ptr,
735 const Loop *Lp,
736 const DenseMap<Value *, const SCEV *> &StridesMap = DenseMap<Value *, const SCEV *>(),
737 bool Assume = false, bool ShouldCheckWrap = true);
738
739/// Returns the distance between the pointers \p PtrA and \p PtrB iff they are
740/// compatible and it is possible to calculate the distance between them. This
741/// is a simple API that does not depend on the analysis pass.
742/// \param StrictCheck Ensure that the calculated distance matches the
743/// type-based one after all the bitcasts removal in the provided pointers.
744std::optional<int> getPointersDiff(Type *ElemTyA, Value *PtrA, Type *ElemTyB,
745 Value *PtrB, const DataLayout &DL,
746 ScalarEvolution &SE,
747 bool StrictCheck = false,
748 bool CheckType = true);
749
750/// Attempt to sort the pointers in \p VL and return the sorted indices
751/// in \p SortedIndices, if reordering is required.
752///
753/// Returns 'true' if sorting is legal, otherwise returns 'false'.
754///
755/// For example, for a given \p VL of memory accesses in program order, a[i+4],
756/// a[i+0], a[i+1] and a[i+7], this function will sort the \p VL and save the
757/// sorted indices in \p SortedIndices as a[i+0], a[i+1], a[i+4], a[i+7] and
758/// saves the mask for actual memory accesses in program order in
759/// \p SortedIndices as <1,2,0,3>
760bool sortPtrAccesses(ArrayRef<Value *> VL, Type *ElemTy, const DataLayout &DL,
761 ScalarEvolution &SE,
762 SmallVectorImpl<unsigned> &SortedIndices);
763
764/// Returns true if the memory operations \p A and \p B are consecutive.
765/// This is a simple API that does not depend on the analysis pass.
766bool isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL,
767 ScalarEvolution &SE, bool CheckType = true);
768
770 /// The cache.
772
773 // The used analysis passes.
774 ScalarEvolution &SE;
775 AAResults &AA;
776 DominatorTree &DT;
777 LoopInfo &LI;
778 const TargetLibraryInfo *TLI = nullptr;
779
780public:
782 LoopInfo &LI, const TargetLibraryInfo *TLI)
783 : SE(SE), AA(AA), DT(DT), LI(LI), TLI(TLI) {}
784
785 const LoopAccessInfo &getInfo(Loop &L);
786
787 void clear() { LoopAccessInfoMap.clear(); }
788
789 bool invalidate(Function &F, const PreservedAnalyses &PA,
791};
792
793/// This analysis provides dependence information for the memory
794/// accesses of a loop.
795///
796/// It runs the analysis for a loop on demand. This can be initiated by
797/// querying the loop access info via AM.getResult<LoopAccessAnalysis>.
798/// getResult return a LoopAccessInfo object. See this class for the
799/// specifics of what information is provided.
801 : public AnalysisInfoMixin<LoopAccessAnalysis> {
803 static AnalysisKey Key;
804
805public:
807
809};
810
812 const LoopAccessInfo &LAI) const {
814}
815
817 const LoopAccessInfo &LAI) const {
818 return LAI.getDepChecker().getMemoryInstructions()[Destination];
819}
820
821} // End llvm namespace
822
823#endif
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
MapVector< const Value *, unsigned > OrderMap
Definition: AsmWriter.cpp:98
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:469
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(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N, const TargetLowering *TLI, const DataLayout &DL)
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:661
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
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:56
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
EquivalenceClasses - This represents a collection of equivalence classes and supports three efficient...
An instruction for reading from memory.
Definition: Instructions.h:177
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, 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...
bool hasDependenceInvolvingLoopInvariantAddress() const
If the loop has memory dependence involving an invariant address, i.e.
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.
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 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:47
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.
EquivalenceClasses< MemAccessInfo > DepCandidates
Set of potential dependent memory accesses.
MemoryDepChecker(PredicatedScalarEvolution &PSE, const Loop *L)
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.
bool areDepsSafe(DepCandidates &AccessSets, MemAccessInfoList &CheckDeps, const DenseMap< Value *, const SCEV * > &Strides)
Check whether the dependencies between the accesses are safe.
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: PassManager.h:152
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:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
An instruction for storing to memory.
Definition: Instructions.h:301
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.
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
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:394
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
Dependece between memory access instructions.
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).
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.
Instruction * getDestination(const LoopAccessInfo &LAI) const
Return the destination instruction of the dependence.
Instruction * getSource(const LoopAccessInfo &LAI) const
Return the source instruction of 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, 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.