LLVM  16.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 
20 #include "llvm/IR/DiagnosticInfo.h"
21 #include "llvm/Pass.h"
22 #include <optional>
23 
24 namespace llvm {
25 
26 class AAResults;
27 class DataLayout;
28 class Loop;
29 class LoopAccessInfo;
30 class raw_ostream;
31 class SCEV;
32 class SCEVUnionPredicate;
33 class 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.
50  static unsigned RuntimeMemoryCheckThreshold;
51 };
52 
53 /// Checks memory dependences among accesses to the same underlying
54 /// object to determine whether there vectorization is legal or not (and at
55 /// which vectorization factor).
56 ///
57 /// Note: This class will compute a conservative dependence for access to
58 /// different underlying pointers. Clients, such as the loop vectorizer, will
59 /// sometimes deal these potential dependencies by emitting runtime checks.
60 ///
61 /// We use the ScalarEvolution framework to symbolically evalutate access
62 /// functions pairs. Since we currently don't restructure the loop we can rely
63 /// on the program order of memory accesses to determine their safety.
64 /// At the moment we will only deem accesses as safe for:
65 /// * A negative constant distance assuming program order.
66 ///
67 /// Safe: tmp = a[i + 1]; OR a[i + 1] = x;
68 /// a[i] = tmp; y = a[i];
69 ///
70 /// The latter case is safe because later checks guarantuee that there can't
71 /// be a cycle through a phi node (that is, we check that "x" and "y" is not
72 /// the same variable: a header phi can only be an induction or a reduction, a
73 /// reduction can't have a memory sink, an induction can't have a memory
74 /// source). This is important and must not be violated (or we have to
75 /// resort to checking for cycles through memory).
76 ///
77 /// * A positive constant distance assuming program order that is bigger
78 /// than the biggest memory access.
79 ///
80 /// tmp = a[i] OR b[i] = x
81 /// a[i+2] = tmp y = b[i+2];
82 ///
83 /// Safe distance: 2 x sizeof(a[0]), and 2 x sizeof(b[0]), respectively.
84 ///
85 /// * Zero distances and all accesses have the same size.
86 ///
88 public:
91  /// Set of potential dependent memory accesses.
93 
94  /// Type to keep track of the status of the dependence check. The order of
95  /// the elements is important and has to be from most permissive to least
96  /// permissive.
98  // Can vectorize safely without RT checks. All dependences are known to be
99  // safe.
100  Safe,
101  // Can possibly vectorize with RT checks to overcome unknown dependencies.
103  // Cannot vectorize due to known unsafe dependencies.
104  Unsafe,
105  };
106 
107  /// Dependece between memory access instructions.
108  struct Dependence {
109  /// The type of the dependence.
110  enum DepType {
111  // No dependence.
113  // We couldn't determine the direction or the distance.
115  // Lexically forward.
116  //
117  // FIXME: If we only have loop-independent forward dependences (e.g. a
118  // read and write of A[i]), LAA will locally deem the dependence "safe"
119  // without querying the MemoryDepChecker. Therefore we can miss
120  // enumerating loop-independent forward dependences in
121  // getDependences. Note that as soon as there are different
122  // indices used to access the same array, the MemoryDepChecker *is*
123  // queried and the dependence list is complete.
125  // Forward, but if vectorized, is likely to prevent store-to-load
126  // forwarding.
128  // Lexically backward.
130  // Backward, but the distance allows a vectorization factor of
131  // MaxSafeDepDistBytes.
133  // Same, but may prevent store-to-load forwarding.
135  };
136 
137  /// String version of the types.
138  static const char *DepName[];
139 
140  /// Index of the source of the dependence in the InstMap vector.
141  unsigned Source;
142  /// Index of the destination of the dependence in the InstMap vector.
143  unsigned Destination;
144  /// The type of the dependence.
146 
147  Dependence(unsigned Source, unsigned Destination, DepType Type)
149 
150  /// Return the source instruction of the dependence.
151  Instruction *getSource(const LoopAccessInfo &LAI) const;
152  /// Return the destination instruction of the dependence.
153  Instruction *getDestination(const LoopAccessInfo &LAI) const;
154 
155  /// Dependence types that don't prevent vectorization.
157 
158  /// Lexically forward dependence.
159  bool isForward() const;
160  /// Lexically backward dependence.
161  bool isBackward() const;
162 
163  /// May be a lexically backward dependence type (includes Unknown).
164  bool isPossiblyBackward() const;
165 
166  /// Print the dependence. \p Instr is used to map the instruction
167  /// indices to instructions.
168  void print(raw_ostream &OS, unsigned Depth,
169  const SmallVectorImpl<Instruction *> &Instrs) const;
170  };
171 
173  : PSE(PSE), InnermostLoop(L) {}
174 
175  /// Register the location (instructions are given increasing numbers)
176  /// of a write access.
177  void addAccess(StoreInst *SI);
178 
179  /// Register the location (instructions are given increasing numbers)
180  /// of a write access.
181  void addAccess(LoadInst *LI);
182 
183  /// Check whether the dependencies between the accesses are safe.
184  ///
185  /// Only checks sets with elements in \p CheckDeps.
186  bool areDepsSafe(DepCandidates &AccessSets, MemAccessInfoList &CheckDeps,
187  const ValueToValueMap &Strides);
188 
189  /// No memory dependence was encountered that would inhibit
190  /// vectorization.
191  bool isSafeForVectorization() const {
193  }
194 
195  /// Return true if the number of elements that are safe to operate on
196  /// simultaneously is not bounded.
197  bool isSafeForAnyVectorWidth() const {
198  return MaxSafeVectorWidthInBits == UINT_MAX;
199  }
200 
201  /// The maximum number of bytes of a vector register we can vectorize
202  /// the accesses safely with.
203  uint64_t getMaxSafeDepDistBytes() { return MaxSafeDepDistBytes; }
204 
205  /// Return the number of elements that are safe to operate on
206  /// simultaneously, multiplied by the size of the element in bits.
208  return MaxSafeVectorWidthInBits;
209  }
210 
211  /// In same cases when the dependency check fails we can still
212  /// vectorize the loop with a dynamic array access check.
214  return FoundNonConstantDistanceDependence &&
216  }
217 
218  /// Returns the memory dependences. If null is returned we exceeded
219  /// the MaxDependences threshold and this information is not
220  /// available.
222  return RecordDependences ? &Dependences : nullptr;
223  }
224 
225  void clearDependences() { Dependences.clear(); }
226 
227  /// The vector of memory access instructions. The indices are used as
228  /// instruction identifiers in the Dependence class.
230  return InstMap;
231  }
232 
233  /// Generate a mapping between the memory instructions and their
234  /// indices according to program order.
237 
238  for (unsigned I = 0; I < InstMap.size(); ++I)
239  OrderMap[InstMap[I]] = I;
240 
241  return OrderMap;
242  }
243 
244  /// Find the set of instructions that read or write via \p Ptr.
246  bool isWrite) const;
247 
248  /// Return the program order indices for the access location (Ptr, IsWrite).
249  /// Returns an empty ArrayRef if there are no accesses for the location.
251  auto I = Accesses.find({Ptr, IsWrite});
252  if (I != Accesses.end())
253  return I->second;
254  return {};
255  }
256 
257  const Loop *getInnermostLoop() const { return InnermostLoop; }
258 
259 private:
260  /// A wrapper around ScalarEvolution, used to add runtime SCEV checks, and
261  /// applies dynamic knowledge to simplify SCEV expressions and convert them
262  /// to a more usable form. We need this in case assumptions about SCEV
263  /// expressions need to be made in order to avoid unknown dependences. For
264  /// example we might assume a unit stride for a pointer in order to prove
265  /// that a memory access is strided and doesn't wrap.
267  const Loop *InnermostLoop;
268 
269  /// Maps access locations (ptr, read/write) to program order.
271 
272  /// Memory access instructions in program order.
274 
275  /// The program order index to be used for the next instruction.
276  unsigned AccessIdx = 0;
277 
278  // We can access this many bytes in parallel safely.
279  uint64_t MaxSafeDepDistBytes = 0;
280 
281  /// Number of elements (from consecutive iterations) that are safe to
282  /// operate on simultaneously, multiplied by the size of the element in bits.
283  /// The size of the element is taken from the memory access that is most
284  /// restrictive.
285  uint64_t MaxSafeVectorWidthInBits = -1U;
286 
287  /// If we see a non-constant dependence distance we can still try to
288  /// vectorize this loop with runtime checks.
289  bool FoundNonConstantDistanceDependence = false;
290 
291  /// Result of the dependence checks, indicating whether the checked
292  /// dependences are safe for vectorization, require RT checks or are known to
293  /// be unsafe.
295 
296  //// True if Dependences reflects the dependences in the
297  //// loop. If false we exceeded MaxDependences and
298  //// Dependences is invalid.
299  bool RecordDependences = true;
300 
301  /// Memory dependences collected during the analysis. Only valid if
302  /// RecordDependences is true.
303  SmallVector<Dependence, 8> Dependences;
304 
305  /// Check whether there is a plausible dependence between the two
306  /// accesses.
307  ///
308  /// Access \p A must happen before \p B in program order. The two indices
309  /// identify the index into the program order map.
310  ///
311  /// This function checks whether there is a plausible dependence (or the
312  /// absence of such can't be proved) between the two accesses. If there is a
313  /// plausible dependence but the dependence distance is bigger than one
314  /// element access it records this distance in \p MaxSafeDepDistBytes (if this
315  /// distance is smaller than any other distance encountered so far).
316  /// Otherwise, this function returns true signaling a possible dependence.
317  Dependence::DepType isDependent(const MemAccessInfo &A, unsigned AIdx,
318  const MemAccessInfo &B, unsigned BIdx,
319  const ValueToValueMap &Strides);
320 
321  /// Check whether the data dependence could prevent store-load
322  /// forwarding.
323  ///
324  /// \return false if we shouldn't vectorize at all or avoid larger
325  /// vectorization factors by limiting MaxSafeDepDistBytes.
326  bool couldPreventStoreLoadForward(uint64_t Distance, uint64_t TypeByteSize);
327 
328  /// Updates the current safety status with \p S. We can go from Safe to
329  /// either PossiblySafeWithRtChecks or Unsafe and from
330  /// PossiblySafeWithRtChecks to Unsafe.
331  void mergeInStatus(VectorizationSafetyStatus S);
332 };
333 
334 class RuntimePointerChecking;
335 /// A grouping of pointers. A single memcheck is required between
336 /// two groups.
338  /// Create a new pointer checking group containing a single
339  /// pointer, with index \p Index in RtCheck.
341 
342  /// Tries to add the pointer recorded in RtCheck at index
343  /// \p Index to this pointer checking group. We can only add a pointer
344  /// to a checking group if we will still be able to get
345  /// the upper and lower bounds of the check. Returns true in case
346  /// of success, false otherwise.
347  bool addPointer(unsigned Index, RuntimePointerChecking &RtCheck);
348  bool addPointer(unsigned Index, const SCEV *Start, const SCEV *End,
349  unsigned AS, bool NeedsFreeze, ScalarEvolution &SE);
350 
351  /// The SCEV expression which represents the upper bound of all the
352  /// pointers in this group.
353  const SCEV *High;
354  /// The SCEV expression which represents the lower bound of all the
355  /// pointers in this group.
356  const SCEV *Low;
357  /// Indices of all the pointers that constitute this grouping.
359  /// Address space of the involved pointers.
360  unsigned AddressSpace;
361  /// Whether the pointer needs to be frozen after expansion, e.g. because it
362  /// may be poison outside the loop.
363  bool NeedsFreeze = false;
364 };
365 
366 /// A memcheck which made up of a pair of grouped pointers.
367 typedef std::pair<const RuntimeCheckingPtrGroup *,
368  const RuntimeCheckingPtrGroup *>
370 
372  const SCEV *SrcStart;
373  const SCEV *SinkStart;
374  unsigned AccessSize;
376 
378  unsigned AccessSize, bool NeedsFreeze)
381 };
382 
383 /// Holds information about the memory runtime legality checks to verify
384 /// that a group of pointers do not overlap.
386  friend struct RuntimeCheckingPtrGroup;
387 
388 public:
389  struct PointerInfo {
390  /// Holds the pointer value that we need to check.
392  /// Holds the smallest byte address accessed by the pointer throughout all
393  /// iterations of the loop.
394  const SCEV *Start;
395  /// Holds the largest byte address accessed by the pointer throughout all
396  /// iterations of the loop, plus 1.
397  const SCEV *End;
398  /// Holds the information if this pointer is used for writing to memory.
400  /// Holds the id of the set of pointers that could be dependent because of a
401  /// shared underlying object.
402  unsigned DependencySetId;
403  /// Holds the id of the disjoint alias set to which this pointer belongs.
404  unsigned AliasSetId;
405  /// SCEV for the access.
406  const SCEV *Expr;
407  /// True if the pointer expressions needs to be frozen after expansion.
409 
411  bool IsWritePtr, unsigned DependencySetId, unsigned AliasSetId,
412  const SCEV *Expr, bool NeedsFreeze)
416  };
417 
419  : DC(DC), SE(SE) {}
420 
421  /// Reset the state of the pointer runtime information.
422  void reset() {
423  Need = false;
424  Pointers.clear();
425  Checks.clear();
426  }
427 
428  /// Insert a pointer and calculate the start and end SCEVs.
429  /// We need \p PSE in order to compute the SCEV expression of the pointer
430  /// according to the assumptions that we've made during the analysis.
431  /// The method might also version the pointer stride according to \p Strides,
432  /// and add new predicates to \p PSE.
433  void insert(Loop *Lp, Value *Ptr, const SCEV *PtrExpr, Type *AccessTy,
434  bool WritePtr, unsigned DepSetId, unsigned ASId,
435  PredicatedScalarEvolution &PSE, bool NeedsFreeze);
436 
437  /// No run-time memory checking is necessary.
438  bool empty() const { return Pointers.empty(); }
439 
440  /// Generate the checks and store it. This also performs the grouping
441  /// of pointers to reduce the number of memchecks necessary.
442  void generateChecks(MemoryDepChecker::DepCandidates &DepCands,
443  bool UseDependencies);
444 
445  /// Returns the checks that generateChecks created. They can be used to ensure
446  /// no read/write accesses overlap across all loop iterations.
448  return Checks;
449  }
450 
451  // Returns an optional list of (pointer-difference expressions, access size)
452  // pairs that can be used to prove that there are no vectorization-preventing
453  // dependencies at runtime. There are is a vectorization-preventing dependency
454  // if any pointer-difference is <u VF * InterleaveCount * access size. Returns
455  // None if pointer-difference checks cannot be used.
456  std::optional<ArrayRef<PointerDiffInfo>> getDiffChecks() const {
457  if (!CanUseDiffCheck)
458  return None;
459  return {DiffChecks};
460  }
461 
462  /// Decide if we need to add a check between two groups of pointers,
463  /// according to needsChecking.
465  const RuntimeCheckingPtrGroup &N) const;
466 
467  /// Returns the number of run-time checks required according to
468  /// needsChecking.
469  unsigned getNumberOfChecks() const { return Checks.size(); }
470 
471  /// Print the list run-time memory checks necessary.
472  void print(raw_ostream &OS, unsigned Depth = 0) const;
473 
474  /// Print \p Checks.
475  void printChecks(raw_ostream &OS,
477  unsigned Depth = 0) const;
478 
479  /// This flag indicates if we need to add the runtime check.
480  bool Need = false;
481 
482  /// Information about the pointers that may require checking.
484 
485  /// Holds a partitioning of pointers into "check groups".
487 
488  /// Check if pointers are in the same partition
489  ///
490  /// \p PtrToPartition contains the partition number for pointers (-1 if the
491  /// pointer belongs to multiple partitions).
492  static bool
493  arePointersInSamePartition(const SmallVectorImpl<int> &PtrToPartition,
494  unsigned PtrIdx1, unsigned PtrIdx2);
495 
496  /// Decide whether we need to issue a run-time check for pointer at
497  /// index \p I and \p J to prove their independence.
498  bool needsChecking(unsigned I, unsigned J) const;
499 
500  /// Return PointerInfo for pointer at index \p PtrIdx.
501  const PointerInfo &getPointerInfo(unsigned PtrIdx) const {
502  return Pointers[PtrIdx];
503  }
504 
505  ScalarEvolution *getSE() const { return SE; }
506 
507 private:
508  /// Groups pointers such that a single memcheck is required
509  /// between two different groups. This will clear the CheckingGroups vector
510  /// and re-compute it. We will only group dependecies if \p UseDependencies
511  /// is true, otherwise we will create a separate group for each pointer.
512  void groupChecks(MemoryDepChecker::DepCandidates &DepCands,
513  bool UseDependencies);
514 
515  /// Generate the checks and return them.
516  SmallVector<RuntimePointerCheck, 4> generateChecks();
517 
518  /// Try to create add a new (pointer-difference, access size) pair to
519  /// DiffCheck for checking groups \p CGI and \p CGJ. If pointer-difference
520  /// checks cannot be used for the groups, set CanUseDiffCheck to false.
521  void tryToCreateDiffCheck(const RuntimeCheckingPtrGroup &CGI,
522  const RuntimeCheckingPtrGroup &CGJ);
523 
524  MemoryDepChecker &DC;
525 
526  /// Holds a pointer to the ScalarEvolution analysis.
527  ScalarEvolution *SE;
528 
529  /// Set of run-time checks required to establish independence of
530  /// otherwise may-aliasing pointers in the loop.
532 
533  /// Flag indicating if pointer-difference checks can be used
534  bool CanUseDiffCheck = true;
535 
536  /// A list of (pointer-difference, access size) pairs that can be used to
537  /// prove that there are no vectorization-preventing dependencies.
538  SmallVector<PointerDiffInfo> DiffChecks;
539 };
540 
541 /// Drive the analysis of memory accesses in the loop
542 ///
543 /// This class is responsible for analyzing the memory accesses of a loop. It
544 /// collects the accesses and then its main helper the AccessAnalysis class
545 /// finds and categorizes the dependences in buildDependenceSets.
546 ///
547 /// For memory dependences that can be analyzed at compile time, it determines
548 /// whether the dependence is part of cycle inhibiting vectorization. This work
549 /// is delegated to the MemoryDepChecker class.
550 ///
551 /// For memory dependences that cannot be determined at compile time, it
552 /// generates run-time checks to prove independence. This is done by
553 /// AccessAnalysis::canCheckPtrAtRT and the checks are maintained by the
554 /// RuntimePointerCheck class.
555 ///
556 /// If pointers can wrap or can't be expressed as affine AddRec expressions by
557 /// ScalarEvolution, we will generate run-time checks by emitting a
558 /// SCEVUnionPredicate.
559 ///
560 /// Checks for both memory dependences and the SCEV predicates contained in the
561 /// PSE must be emitted in order for the results of this analysis to be valid.
563 public:
565  AAResults *AA, DominatorTree *DT, LoopInfo *LI);
566 
567  /// Return true we can analyze the memory accesses in the loop and there are
568  /// no memory dependence cycles.
569  bool canVectorizeMemory() const { return CanVecMem; }
570 
571  /// Return true if there is a convergent operation in the loop. There may
572  /// still be reported runtime pointer checks that would be required, but it is
573  /// not legal to insert them.
574  bool hasConvergentOp() const { return HasConvergentOp; }
575 
577  return PtrRtChecking.get();
578  }
579 
580  /// Number of memchecks required to prove independence of otherwise
581  /// may-alias pointers.
582  unsigned getNumRuntimePointerChecks() const {
583  return PtrRtChecking->getNumberOfChecks();
584  }
585 
586  /// Return true if the block BB needs to be predicated in order for the loop
587  /// to be vectorized.
588  static bool blockNeedsPredication(BasicBlock *BB, Loop *TheLoop,
589  DominatorTree *DT);
590 
591  /// Returns true if the value V is uniform within the loop.
592  bool isUniform(Value *V) const;
593 
594  uint64_t getMaxSafeDepDistBytes() const { return MaxSafeDepDistBytes; }
595  unsigned getNumStores() const { return NumStores; }
596  unsigned getNumLoads() const { return NumLoads;}
597 
598  /// The diagnostics report generated for the analysis. E.g. why we
599  /// couldn't analyze the loop.
600  const OptimizationRemarkAnalysis *getReport() const { return Report.get(); }
601 
602  /// the Memory Dependence Checker which can determine the
603  /// loop-independent and loop-carried dependences between memory accesses.
604  const MemoryDepChecker &getDepChecker() const { return *DepChecker; }
605 
606  /// Return the list of instructions that use \p Ptr to read or write
607  /// memory.
609  bool isWrite) const {
610  return DepChecker->getInstructionsForAccess(Ptr, isWrite);
611  }
612 
613  /// If an access has a symbolic strides, this maps the pointer value to
614  /// the stride symbol.
615  const ValueToValueMap &getSymbolicStrides() const { return SymbolicStrides; }
616 
617  /// Pointer has a symbolic stride.
618  bool hasStride(Value *V) const { return StrideSet.count(V); }
619 
620  /// Print the information about the memory accesses in the loop.
621  void print(raw_ostream &OS, unsigned Depth = 0) const;
622 
623  /// If the loop has memory dependence involving an invariant address, i.e. two
624  /// stores or a store and a load, then return true, else return false.
626  return HasDependenceInvolvingLoopInvariantAddress;
627  }
628 
629  /// Return the list of stores to invariant addresses.
631  return StoresToInvariantAddresses;
632  }
633 
634  /// Used to add runtime SCEV checks. Simplifies SCEV expressions and converts
635  /// them to a more usable form. All SCEV expressions during the analysis
636  /// should be re-written (and therefore simplified) according to PSE.
637  /// A user of LoopAccessAnalysis will need to emit the runtime checks
638  /// associated with this predicate.
639  const PredicatedScalarEvolution &getPSE() const { return *PSE; }
640 
641 private:
642  /// Analyze the loop.
643  void analyzeLoop(AAResults *AA, LoopInfo *LI,
644  const TargetLibraryInfo *TLI, DominatorTree *DT);
645 
646  /// Check if the structure of the loop allows it to be analyzed by this
647  /// pass.
648  bool canAnalyzeLoop();
649 
650  /// Save the analysis remark.
651  ///
652  /// LAA does not directly emits the remarks. Instead it stores it which the
653  /// client can retrieve and presents as its own analysis
654  /// (e.g. -Rpass-analysis=loop-vectorize).
655  OptimizationRemarkAnalysis &recordAnalysis(StringRef RemarkName,
656  Instruction *Instr = nullptr);
657 
658  /// Collect memory access with loop invariant strides.
659  ///
660  /// Looks for accesses like "a[i * StrideA]" where "StrideA" is loop
661  /// invariant.
662  void collectStridedAccess(Value *LoadOrStoreInst);
663 
664  // Emits the first unsafe memory dependence in a loop.
665  // Emits nothing if there are no unsafe dependences
666  // or if the dependences were not recorded.
667  void emitUnsafeDependenceRemark();
668 
669  std::unique_ptr<PredicatedScalarEvolution> PSE;
670 
671  /// We need to check that all of the pointers in this list are disjoint
672  /// at runtime. Using std::unique_ptr to make using move ctor simpler.
673  std::unique_ptr<RuntimePointerChecking> PtrRtChecking;
674 
675  /// the Memory Dependence Checker which can determine the
676  /// loop-independent and loop-carried dependences between memory accesses.
677  std::unique_ptr<MemoryDepChecker> DepChecker;
678 
679  Loop *TheLoop;
680 
681  unsigned NumLoads = 0;
682  unsigned NumStores = 0;
683 
684  uint64_t MaxSafeDepDistBytes = -1;
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  ValueToValueMap SymbolicStrides;
703 
704  /// Set of symbolic strides values.
705  SmallPtrSet<Value *, 8> StrideSet;
706 };
707 
709 
710 /// Return the SCEV corresponding to a pointer with the symbolic stride
711 /// replaced with constant one, assuming the SCEV predicate associated with
712 /// \p PSE is true.
713 ///
714 /// If necessary this method will version the stride of the pointer according
715 /// to \p PtrToStride and therefore add further predicates to \p PSE.
716 ///
717 /// \p PtrToStride provides the mapping between the pointer value and its
718 /// stride as collected by LoopVectorizationLegality::collectStridedAccess.
719 const SCEV *replaceSymbolicStrideSCEV(PredicatedScalarEvolution &PSE,
720  const ValueToValueMap &PtrToStride,
721  Value *Ptr);
722 
723 /// If the pointer has a constant stride return it in units of the access type
724 /// size. Otherwise return None.
725 ///
726 /// Ensure that it does not wrap in the address space, assuming the predicate
727 /// associated with \p PSE is true.
728 ///
729 /// If necessary this method will version the stride of the pointer according
730 /// to \p PtrToStride and therefore add further predicates to \p PSE.
731 /// The \p Assume parameter indicates if we are allowed to make additional
732 /// run-time assumptions.
733 Optional<int64_t>
734 getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy, Value *Ptr,
735  const Loop *Lp,
736  const ValueToValueMap &StridesMap = ValueToValueMap(),
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.
744 Optional<int> getPointersDiff(Type *ElemTyA, Value *PtrA, Type *ElemTyB,
745  Value *PtrB, const DataLayout &DL,
746  ScalarEvolution &SE, bool StrictCheck = false,
747  bool CheckType = true);
748 
749 /// Attempt to sort the pointers in \p VL and return the sorted indices
750 /// in \p SortedIndices, if reordering is required.
751 ///
752 /// Returns 'true' if sorting is legal, otherwise returns 'false'.
753 ///
754 /// For example, for a given \p VL of memory accesses in program order, a[i+4],
755 /// a[i+0], a[i+1] and a[i+7], this function will sort the \p VL and save the
756 /// sorted indices in \p SortedIndices as a[i+0], a[i+1], a[i+4], a[i+7] and
757 /// saves the mask for actual memory accesses in program order in
758 /// \p SortedIndices as <1,2,0,3>
759 bool sortPtrAccesses(ArrayRef<Value *> VL, Type *ElemTy, const DataLayout &DL,
760  ScalarEvolution &SE,
761  SmallVectorImpl<unsigned> &SortedIndices);
762 
763 /// Returns true if the memory operations \p A and \p B are consecutive.
764 /// This is a simple API that does not depend on the analysis pass.
765 bool isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL,
766  ScalarEvolution &SE, bool CheckType = true);
767 
769  /// The cache.
771 
772  // The used analysis passes.
773  ScalarEvolution &SE;
774  AAResults &AA;
775  DominatorTree &DT;
776  LoopInfo &LI;
777  const TargetLibraryInfo *TLI = nullptr;
778 
779 public:
781  LoopInfo &LI, const TargetLibraryInfo *TLI)
782  : SE(SE), AA(AA), DT(DT), LI(LI), TLI(TLI) {}
783 
784  const LoopAccessInfo &getInfo(Loop &L);
785 
786  void clear() { LoopAccessInfoMap.clear(); }
787 };
788 
789 /// This analysis provides dependence information for the memory accesses
790 /// of a loop.
791 ///
792 /// It runs the analysis for a loop on demand. This can be initiated by
793 /// querying the loop access info via LAA::getInfo. getInfo return a
794 /// LoopAccessInfo object. See this class for the specifics of what information
795 /// is provided.
797 public:
798  static char ID;
799 
801 
802  bool runOnFunction(Function &F) override;
803 
804  void getAnalysisUsage(AnalysisUsage &AU) const override;
805 
806  /// Return the proxy object for retrieving LoopAccessInfo for individual
807  /// loops.
808  ///
809  /// If there is no cached result available run the analysis.
810  LoopAccessInfoManager &getLAIs() { return *LAIs; }
811 
812  void releaseMemory() override {
813  // Invalidate the cache when the pass is freed.
814  LAIs->clear();
815  }
816 
817 private:
818  std::unique_ptr<LoopAccessInfoManager> LAIs;
819 };
820 
821 /// This analysis provides dependence information for the memory
822 /// accesses of a loop.
823 ///
824 /// It runs the analysis for a loop on demand. This can be initiated by
825 /// querying the loop access info via AM.getResult<LoopAccessAnalysis>.
826 /// getResult return a LoopAccessInfo object. See this class for the
827 /// specifics of what information is provided.
829  : public AnalysisInfoMixin<LoopAccessAnalysis> {
831  static AnalysisKey Key;
832 
833 public:
835 
837 };
838 
840  const LoopAccessInfo &LAI) const {
842 }
843 
845  const LoopAccessInfo &LAI) const {
846  return LAI.getDepChecker().getMemoryInstructions()[Destination];
847 }
848 
849 } // End llvm namespace
850 
851 #endif
llvm::sortPtrAccesses
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,...
Definition: LoopAccessAnalysis.cpp:1545
llvm::MemoryDepChecker::clearDependences
void clearDependences()
Definition: LoopAccessAnalysis.h:225
llvm::LoopAccessLegacyAnalysis::ID
static char ID
Definition: LoopAccessAnalysis.h:798
llvm::MemoryDepChecker::Dependence::isBackward
bool isBackward() const
Lexically backward dependence.
Definition: LoopAccessAnalysis.cpp:1639
llvm::MemoryDepChecker
Checks memory dependences among accesses to the same underlying object to determine whether there vec...
Definition: LoopAccessAnalysis.h:87
llvm::LoopAccessLegacyAnalysis
This analysis provides dependence information for the memory accesses of a loop.
Definition: LoopAccessAnalysis.h:796
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::RuntimePointerCheck
std::pair< const RuntimeCheckingPtrGroup *, const RuntimeCheckingPtrGroup * > RuntimePointerCheck
A memcheck which made up of a pair of grouped pointers.
Definition: LoopAccessAnalysis.h:369
llvm::MemoryDepChecker::VectorizationSafetyStatus::Safe
@ Safe
llvm::PointerDiffInfo::NeedsFreeze
bool NeedsFreeze
Definition: LoopAccessAnalysis.h:375
llvm::LoopAccessInfoManager
Definition: LoopAccessAnalysis.h:768
llvm::LoopAccessInfo::isUniform
bool isUniform(Value *V) const
Returns true if the value V is uniform within the loop.
Definition: LoopAccessAnalysis.cpp:2547
llvm::MemoryDepChecker::MemoryDepChecker
MemoryDepChecker(PredicatedScalarEvolution &PSE, const Loop *L)
Definition: LoopAccessAnalysis.h:172
llvm::RuntimeCheckingPtrGroup::RuntimeCheckingPtrGroup
RuntimeCheckingPtrGroup(unsigned Index, RuntimePointerChecking &RtCheck)
Create a new pointer checking group containing a single pointer, with index Index in RtCheck.
Definition: LoopAccessAnalysis.cpp:177
llvm::Function
Definition: Function.h:60
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
Pass.h
llvm::PredicatedScalarEvolution
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
Definition: ScalarEvolution.h:2219
llvm::MemoryDepChecker::Dependence::getSource
Instruction * getSource(const LoopAccessInfo &LAI) const
Return the source instruction of the dependence.
Definition: LoopAccessAnalysis.h:839
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
CheckType
static LLVM_ATTRIBUTE_ALWAYS_INLINE bool CheckType(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N, const TargetLowering *TLI, const DataLayout &DL)
Definition: SelectionDAGISel.cpp:2552
llvm::EquivalenceClasses
EquivalenceClasses - This represents a collection of equivalence classes and supports three efficient...
Definition: EquivalenceClasses.h:60
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:449
llvm::VectorizerParams::VectorizationInterleave
static unsigned VectorizationInterleave
Interleave factor as overridden by the user.
Definition: LoopAccessAnalysis.h:44
llvm::MemoryDepChecker::generateInstructionOrderMap
DenseMap< Instruction *, unsigned > generateInstructionOrderMap() const
Generate a mapping between the memory instructions and their indices according to program order.
Definition: LoopAccessAnalysis.h:235
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::MemoryDepChecker::Dependence::isPossiblyBackward
bool isPossiblyBackward() const
May be a lexically backward dependence type (includes Unknown).
Definition: LoopAccessAnalysis.cpp:1655
llvm::LoopAccessAnalysis
This analysis provides dependence information for the memory accesses of a loop.
Definition: LoopAccessAnalysis.h:828
llvm::MemoryDepChecker::getMaxSafeVectorWidthInBits
uint64_t getMaxSafeVectorWidthInBits() const
Return the number of elements that are safe to operate on simultaneously, multiplied by the size of t...
Definition: LoopAccessAnalysis.h:207
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:36
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::RuntimePointerChecking::needsChecking
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.
Definition: LoopAccessAnalysis.cpp:358
llvm::MemoryDepChecker::areDepsSafe
bool areDepsSafe(DepCandidates &AccessSets, MemAccessInfoList &CheckDeps, const ValueToValueMap &Strides)
Check whether the dependencies between the accesses are safe.
Definition: LoopAccessAnalysis.cpp:2024
llvm::isConsecutiveAccess
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.
Definition: LoopAccessAnalysis.cpp:1590
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::RuntimePointerChecking::getNumberOfChecks
unsigned getNumberOfChecks() const
Returns the number of run-time checks required according to needsChecking.
Definition: LoopAccessAnalysis.h:469
llvm::MemoryDepChecker::Dependence::Dependence
Dependence(unsigned Source, unsigned Destination, DepType Type)
Definition: LoopAccessAnalysis.h:147
llvm::MemoryDepChecker::getInnermostLoop
const Loop * getInnermostLoop() const
Definition: LoopAccessAnalysis.h:257
llvm::MemoryDepChecker::DepCandidates
EquivalenceClasses< MemAccessInfo > DepCandidates
Set of potential dependent memory accesses.
Definition: LoopAccessAnalysis.h:92
llvm::MemoryDepChecker::Dependence::NoDep
@ NoDep
Definition: LoopAccessAnalysis.h:112
llvm::stripIntegerCast
Value * stripIntegerCast(Value *V)
Definition: LoopAccessAnalysis.cpp:143
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::MemoryDepChecker::Dependence::DepType
DepType
The type of the dependence.
Definition: LoopAccessAnalysis.h:110
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
LoopAnalysisManager.h
llvm::MemoryDepChecker::Dependence::isForward
bool isForward() const
Lexically forward dependence.
Definition: LoopAccessAnalysis.cpp:1659
llvm::LoopAccessInfo::hasDependenceInvolvingLoopInvariantAddress
bool hasDependenceInvolvingLoopInvariantAddress() const
If the loop has memory dependence involving an invariant address, i.e.
Definition: LoopAccessAnalysis.h:625
llvm::MemoryDepChecker::VectorizationSafetyStatus
VectorizationSafetyStatus
Type to keep track of the status of the dependence check.
Definition: LoopAccessAnalysis.h:97
llvm::AAResults
Definition: AliasAnalysis.h:294
llvm::LoopAccessInfo::blockNeedsPredication
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.
Definition: LoopAccessAnalysis.cpp:2518
llvm::ValueToValueMap
DenseMap< const Value *, Value * > ValueToValueMap
Definition: ScalarEvolutionExpressions.h:906
llvm::MemoryDepChecker::Dependence::BackwardVectorizable
@ BackwardVectorizable
Definition: LoopAccessAnalysis.h:132
llvm::MemoryDepChecker::getOrderForAccess
ArrayRef< unsigned > getOrderForAccess(Value *Ptr, bool IsWrite) const
Return the program order indices for the access location (Ptr, IsWrite).
Definition: LoopAccessAnalysis.h:250
llvm::LoopAccessInfo::getNumLoads
unsigned getNumLoads() const
Definition: LoopAccessAnalysis.h:596
llvm::MemoryDepChecker::Dependence::Source
unsigned Source
Index of the source of the dependence in the InstMap vector.
Definition: LoopAccessAnalysis.h:141
SI
@ SI
Definition: SIInstrInfo.cpp:7966
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::MemoryDepChecker::Dependence::print
void print(raw_ostream &OS, unsigned Depth, const SmallVectorImpl< Instruction * > &Instrs) const
Print the dependence.
Definition: LoopAccessAnalysis.cpp:2117
llvm::RuntimeCheckingPtrGroup::AddressSpace
unsigned AddressSpace
Address space of the involved pointers.
Definition: LoopAccessAnalysis.h:360
llvm::dwarf::Index
Index
Definition: Dwarf.h:472
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::LoopAccessLegacyAnalysis::getLAIs
LoopAccessInfoManager & getLAIs()
Return the proxy object for retrieving LoopAccessInfo for individual loops.
Definition: LoopAccessAnalysis.h:810
llvm::Instruction
Definition: Instruction.h:42
llvm::MemoryDepChecker::addAccess
void addAccess(StoreInst *SI)
Register the location (instructions are given increasing numbers) of a write access.
Definition: LoopAccessAnalysis.cpp:1603
llvm::PointerDiffInfo::SinkStart
const SCEV * SinkStart
Definition: LoopAccessAnalysis.h:373
llvm::MemoryDepChecker::Dependence::BackwardVectorizableButPreventsForwarding
@ BackwardVectorizableButPreventsForwarding
Definition: LoopAccessAnalysis.h:134
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::LoopAccessInfo::hasStride
bool hasStride(Value *V) const
Pointer has a symbolic stride.
Definition: LoopAccessAnalysis.h:618
llvm::PointerDiffInfo::AccessSize
unsigned AccessSize
Definition: LoopAccessAnalysis.h:374
llvm::MemoryDepChecker::getDependences
const SmallVectorImpl< Dependence > * getDependences() const
Returns the memory dependences.
Definition: LoopAccessAnalysis.h:221
llvm::RuntimePointerChecking::PointerInfo::Start
const SCEV * Start
Holds the smallest byte address accessed by the pointer throughout all iterations of the loop.
Definition: LoopAccessAnalysis.h:394
llvm::getPointersDiff
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...
Definition: LoopAccessAnalysis.cpp:1479
llvm::RuntimePointerChecking::RuntimePointerChecking
RuntimePointerChecking(MemoryDepChecker &DC, ScalarEvolution *SE)
Definition: LoopAccessAnalysis.h:418
llvm::RuntimePointerChecking::reset
void reset()
Reset the state of the pointer runtime information.
Definition: LoopAccessAnalysis.h:422
llvm::RuntimePointerChecking::PointerInfo::AliasSetId
unsigned AliasSetId
Holds the id of the disjoint alias set to which this pointer belongs.
Definition: LoopAccessAnalysis.h:404
llvm::LoopAccessInfo::hasConvergentOp
bool hasConvergentOp() const
Return true if there is a convergent operation in the loop.
Definition: LoopAccessAnalysis.h:574
llvm::MemoryDepChecker::getMaxSafeDepDistBytes
uint64_t getMaxSafeDepDistBytes()
The maximum number of bytes of a vector register we can vectorize the accesses safely with.
Definition: LoopAccessAnalysis.h:203
llvm::LoopAccessInfoManager::clear
void clear()
Definition: LoopAccessAnalysis.h:786
llvm::MemoryDepChecker::getInstructionsForAccess
SmallVector< Instruction *, 4 > getInstructionsForAccess(Value *Ptr, bool isWrite) const
Find the set of instructions that read or write via Ptr.
Definition: LoopAccessAnalysis.cpp:2102
llvm::RuntimePointerChecking::PointerInfo
Definition: LoopAccessAnalysis.h:389
llvm::MemoryDepChecker::VectorizationSafetyStatus::Unsafe
@ Unsafe
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:75
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:298
llvm::LoopAccessInfo::getSymbolicStrides
const ValueToValueMap & getSymbolicStrides() const
If an access has a symbolic strides, this maps the pointer value to the stride symbol.
Definition: LoopAccessAnalysis.h:615
llvm::RuntimePointerChecking
Holds information about the memory runtime legality checks to verify that a group of pointers do not ...
Definition: LoopAccessAnalysis.h:385
llvm::VectorizerParams::VectorizationFactor
static unsigned VectorizationFactor
VF as overridden by the user.
Definition: LoopAccessAnalysis.h:42
llvm::RuntimePointerChecking::Need
bool Need
This flag indicates if we need to add the runtime check.
Definition: LoopAccessAnalysis.h:480
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::clear
void clear()
Definition: DenseMap.h:110
uint64_t
llvm::MemoryDepChecker::Dependence
Dependece between memory access instructions.
Definition: LoopAccessAnalysis.h:108
llvm::MemoryDepChecker::Dependence::Backward
@ Backward
Definition: LoopAccessAnalysis.h:129
llvm::RuntimePointerChecking::PointerInfo::DependencySetId
unsigned DependencySetId
Holds the id of the set of pointers that could be dependent because of a shared underlying object.
Definition: LoopAccessAnalysis.h:402
llvm::LoopAccessInfo::getInstructionsForAccess
SmallVector< Instruction *, 4 > getInstructionsForAccess(Value *Ptr, bool isWrite) const
Return the list of instructions that use Ptr to read or write memory.
Definition: LoopAccessAnalysis.h:608
llvm::RuntimePointerChecking::getChecks
const SmallVectorImpl< RuntimePointerCheck > & getChecks() const
Returns the checks that generateChecks created.
Definition: LoopAccessAnalysis.h:447
llvm::RuntimePointerChecking::CheckingGroups
SmallVector< RuntimeCheckingPtrGroup, 2 > CheckingGroups
Holds a partitioning of pointers into "check groups".
Definition: LoopAccessAnalysis.h:486
llvm::getPtrStride
Optional< int64_t > getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy, Value *Ptr, const Loop *Lp, const ValueToValueMap &StridesMap=ValueToValueMap(), bool Assume=false, bool ShouldCheckWrap=true)
If the pointer has a constant stride return it in units of the access type size.
Definition: LoopAccessAnalysis.cpp:1369
llvm::DenseMap< const Value *, Value * >
llvm::MemoryDepChecker::MemAccessInfoList
SmallVector< MemAccessInfo, 8 > MemAccessInfoList
Definition: LoopAccessAnalysis.h:90
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
llvm::RuntimeCheckingPtrGroup
A grouping of pointers.
Definition: LoopAccessAnalysis.h:337
llvm::LoopAccessInfo::getRuntimePointerChecking
const RuntimePointerChecking * getRuntimePointerChecking() const
Definition: LoopAccessAnalysis.h:576
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::PointerDiffInfo::SrcStart
const SCEV * SrcStart
Definition: LoopAccessAnalysis.h:372
llvm::LoopAccessInfo
Drive the analysis of memory accesses in the loop.
Definition: LoopAccessAnalysis.h:562
llvm::VectorizerParams::MaxVectorWidth
static const unsigned MaxVectorWidth
Maximum SIMD width.
Definition: LoopAccessAnalysis.h:39
llvm::LoopAccessInfo::getReport
const OptimizationRemarkAnalysis * getReport() const
The diagnostics report generated for the analysis.
Definition: LoopAccessAnalysis.h:600
llvm::TrackingVH< Value >
llvm::PointerDiffInfo
Definition: LoopAccessAnalysis.h:371
llvm::LoopAccessInfo::getStoresToInvariantAddresses
ArrayRef< StoreInst * > getStoresToInvariantAddresses() const
Return the list of stores to invariant addresses.
Definition: LoopAccessAnalysis.h:630
llvm::LoopAccessLegacyAnalysis::releaseMemory
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
Definition: LoopAccessAnalysis.h:812
llvm::MemoryDepChecker::isSafeForVectorization
bool isSafeForVectorization() const
No memory dependence was encountered that would inhibit vectorization.
Definition: LoopAccessAnalysis.h:191
llvm::MemoryDepChecker::getMemoryInstructions
const SmallVectorImpl< Instruction * > & getMemoryInstructions() const
The vector of memory access instructions.
Definition: LoopAccessAnalysis.h:229
llvm::VectorizerParams::RuntimeMemoryCheckThreshold
static unsigned RuntimeMemoryCheckThreshold
\When performing memory disambiguation checks at runtime do not make more than this number of compari...
Definition: LoopAccessAnalysis.h:50
llvm::LoopAccessInfo::canVectorizeMemory
bool canVectorizeMemory() const
Return true we can analyze the memory accesses in the loop and there are no memory dependence cycles.
Definition: LoopAccessAnalysis.h:569
Ptr
@ Ptr
Definition: TargetLibraryInfo.cpp:60
llvm::RuntimePointerChecking::getSE
ScalarEvolution * getSE() const
Definition: LoopAccessAnalysis.h:505
llvm::AnalysisInfoMixin
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:394
llvm::RuntimeCheckingPtrGroup::High
const SCEV * High
The SCEV expression which represents the upper bound of all the pointers in this group.
Definition: LoopAccessAnalysis.h:353
llvm::RuntimeCheckingPtrGroup::Low
const SCEV * Low
The SCEV expression which represents the lower bound of all the pointers in this group.
Definition: LoopAccessAnalysis.h:356
Status
Definition: SIModeRegister.cpp:29
llvm::LoopAccessInfo::getDepChecker
const MemoryDepChecker & getDepChecker() const
the Memory Dependence Checker which can determine the loop-independent and loop-carried dependences b...
Definition: LoopAccessAnalysis.h:604
llvm::RuntimePointerChecking::PointerInfo::End
const SCEV * End
Holds the largest byte address accessed by the pointer throughout all iterations of the loop,...
Definition: LoopAccessAnalysis.h:397
llvm::ArrayRef< unsigned >
llvm::LoopInfo
Definition: LoopInfo.h:1108
llvm::replaceSymbolicStrideSCEV
const SCEV * replaceSymbolicStrideSCEV(PredicatedScalarEvolution &PSE, const ValueToValueMap &PtrToStride, Value *Ptr)
Return the SCEV corresponding to a pointer with the symbolic stride replaced with constant one,...
Definition: LoopAccessAnalysis.cpp:150
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
llvm::MemoryDepChecker::MemAccessInfo
PointerIntPair< Value *, 1, bool > MemAccessInfo
Definition: LoopAccessAnalysis.h:89
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::RuntimeCheckingPtrGroup::addPointer
bool addPointer(unsigned Index, RuntimePointerChecking &RtCheck)
Tries to add the pointer recorded in RtCheck at index Index to this pointer checking group.
Definition: LoopAccessAnalysis.cpp:381
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::OptimizationRemarkAnalysis
Diagnostic information for optimization analysis remarks.
Definition: DiagnosticInfo.h:780
llvm::RuntimePointerChecking::PointerInfo::NeedsFreeze
bool NeedsFreeze
True if the pointer expressions needs to be frozen after expansion.
Definition: LoopAccessAnalysis.h:408
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:174
llvm::LoopAccessInfo::getMaxSafeDepDistBytes
uint64_t getMaxSafeDepDistBytes() const
Definition: LoopAccessAnalysis.h:594
llvm::VectorizerParams::isInterleaveForced
static bool isInterleaveForced()
True if force-vector-interleave was specified by the user.
Definition: LoopAccessAnalysis.cpp:139
llvm::RuntimePointerChecking::PointerInfo::Expr
const SCEV * Expr
SCEV for the access.
Definition: LoopAccessAnalysis.h:406
llvm::LoopAccessLegacyAnalysis::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: LoopAccessAnalysis.cpp:2697
llvm::MemoryDepChecker::Dependence::Unknown
@ Unknown
Definition: LoopAccessAnalysis.h:114
llvm::LoopAccessAnalysis::Result
LoopAccessInfoManager Result
Definition: LoopAccessAnalysis.h:834
llvm::RuntimePointerChecking::Pointers
SmallVector< PointerInfo, 2 > Pointers
Information about the pointers that may require checking.
Definition: LoopAccessAnalysis.h:483
llvm::LoopAccessInfo::getNumStores
unsigned getNumStores() const
Definition: LoopAccessAnalysis.h:595
llvm::RuntimePointerChecking::arePointersInSamePartition
static bool arePointersInSamePartition(const SmallVectorImpl< int > &PtrToPartition, unsigned PtrIdx1, unsigned PtrIdx2)
Check if pointers are in the same partition.
Definition: LoopAccessAnalysis.cpp:546
llvm::MemoryDepChecker::shouldRetryWithRuntimeCheck
bool shouldRetryWithRuntimeCheck() const
In same cases when the dependency check fails we can still vectorize the loop with a dynamic array ac...
Definition: LoopAccessAnalysis.h:213
llvm::LoopAccessLegacyAnalysis::LoopAccessLegacyAnalysis
LoopAccessLegacyAnalysis()
Definition: LoopAccessAnalysis.cpp:2682
llvm::MemoryDepChecker::isSafeForAnyVectorWidth
bool isSafeForAnyVectorWidth() const
Return true if the number of elements that are safe to operate on simultaneously is not bounded.
Definition: LoopAccessAnalysis.h:197
llvm::None
constexpr std::nullopt_t None
Definition: None.h:27
llvm::RuntimePointerChecking::PointerInfo::PointerValue
TrackingVH< Value > PointerValue
Holds the pointer value that we need to check.
Definition: LoopAccessAnalysis.h:391
llvm::RuntimePointerChecking::empty
bool empty() const
No run-time memory checking is necessary.
Definition: LoopAccessAnalysis.h:438
llvm::RuntimePointerChecking::printChecks
void printChecks(raw_ostream &OS, const SmallVectorImpl< RuntimePointerCheck > &Checks, unsigned Depth=0) const
Print Checks.
Definition: LoopAccessAnalysis.cpp:572
DiagnosticInfo.h
llvm::LoopAccessInfo::LoopAccessInfo
LoopAccessInfo(Loop *L, ScalarEvolution *SE, const TargetLibraryInfo *TLI, AAResults *AA, DominatorTree *DT, LoopInfo *LI)
Definition: LoopAccessAnalysis.cpp:2617
llvm::MemoryDepChecker::Dependence::DepName
static const char * DepName[]
String version of the types.
Definition: LoopAccessAnalysis.h:138
llvm::RuntimePointerChecking::PointerInfo::IsWritePtr
bool IsWritePtr
Holds the information if this pointer is used for writing to memory.
Definition: LoopAccessAnalysis.h:399
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:226
EquivalenceClasses.h
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:614
llvm::LoopAccessInfo::getNumRuntimePointerChecks
unsigned getNumRuntimePointerChecks() const
Number of memchecks required to prove independence of otherwise may-alias pointers.
Definition: LoopAccessAnalysis.h:582
llvm::LoopAccessInfoManager::LoopAccessInfoManager
LoopAccessInfoManager(ScalarEvolution &SE, AAResults &AA, DominatorTree &DT, LoopInfo &LI, const TargetLibraryInfo *TLI)
Definition: LoopAccessAnalysis.h:780
llvm::MemoryDepChecker::Dependence::Forward
@ Forward
Definition: LoopAccessAnalysis.h:124
ScalarEvolutionExpressions.h
llvm::RuntimePointerChecking::getDiffChecks
std::optional< ArrayRef< PointerDiffInfo > > getDiffChecks() const
Definition: LoopAccessAnalysis.h:456
llvm::PointerIntPair< Value *, 1, bool >
llvm::RuntimePointerChecking::insert
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.
Definition: LoopAccessAnalysis.cpp:200
llvm::MemoryDepChecker::Dependence::Type
DepType Type
The type of the dependence.
Definition: LoopAccessAnalysis.h:145
N
#define N
llvm::LoopAccessInfo::print
void print(raw_ostream &OS, unsigned Depth=0) const
Print the information about the memory accesses in the loop.
Definition: LoopAccessAnalysis.cpp:2629
llvm::VectorizerParams
Collection of parameters shared beetween the Loop Vectorizer and the Loop Access Analysis.
Definition: LoopAccessAnalysis.h:37
llvm::RuntimePointerChecking::getPointerInfo
const PointerInfo & getPointerInfo(unsigned PtrIdx) const
Return PointerInfo for pointer at index PtrIdx.
Definition: LoopAccessAnalysis.h:501
llvm::PointerDiffInfo::PointerDiffInfo
PointerDiffInfo(const SCEV *SrcStart, const SCEV *SinkStart, unsigned AccessSize, bool NeedsFreeze)
Definition: LoopAccessAnalysis.h:377
llvm::SmallVectorImpl< Instruction * >
llvm::MemoryDepChecker::Dependence::isSafeForVectorization
static VectorizationSafetyStatus isSafeForVectorization(DepType Type)
Dependence types that don't prevent vectorization.
Definition: LoopAccessAnalysis.cpp:1622
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::RuntimePointerChecking::PointerInfo::PointerInfo
PointerInfo(Value *PointerValue, const SCEV *Start, const SCEV *End, bool IsWritePtr, unsigned DependencySetId, unsigned AliasSetId, const SCEV *Expr, bool NeedsFreeze)
Definition: LoopAccessAnalysis.h:410
llvm::LoopAccessInfo::getPSE
const PredicatedScalarEvolution & getPSE() const
Used to add runtime SCEV checks.
Definition: LoopAccessAnalysis.h:639
OrderMap
MapVector< const Value *, unsigned > OrderMap
Definition: AsmWriter.cpp:100
llvm::MemoryDepChecker::Dependence::Destination
unsigned Destination
Index of the destination of the dependence in the InstMap vector.
Definition: LoopAccessAnalysis.h:143
llvm::LoopAccessInfoManager::getInfo
const LoopAccessInfo & getInfo(Loop &L)
Definition: LoopAccessAnalysis.cpp:2672
llvm::LoopAccessAnalysis::run
Result run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopAccessAnalysis.cpp:2706
llvm::RuntimePointerChecking::print
void print(raw_ostream &OS, unsigned Depth=0) const
Print the list run-time memory checks necessary.
Definition: LoopAccessAnalysis.cpp:591
llvm::RuntimeCheckingPtrGroup::Members
SmallVector< unsigned, 2 > Members
Indices of all the pointers that constitute this grouping.
Definition: LoopAccessAnalysis.h:358
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::RuntimeCheckingPtrGroup::NeedsFreeze
bool NeedsFreeze
Whether the pointer needs to be frozen after expansion, e.g.
Definition: LoopAccessAnalysis.h:363
llvm::MemoryDepChecker::Dependence::ForwardButPreventsForwarding
@ ForwardButPreventsForwarding
Definition: LoopAccessAnalysis.h:127
llvm::MemoryDepChecker::Dependence::getDestination
Instruction * getDestination(const LoopAccessInfo &LAI) const
Return the destination instruction of the dependence.
Definition: LoopAccessAnalysis.h:844
llvm::LoopAccessLegacyAnalysis::runOnFunction
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition: LoopAccessAnalysis.cpp:2686
llvm::MemoryDepChecker::VectorizationSafetyStatus::PossiblySafeWithRtChecks
@ PossiblySafeWithRtChecks