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