LLVM  15.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.
249  ArrayRef<unsigned> getOrderForAccess(Value *Ptr, bool IsWrite) const {
250  auto I = Accesses.find({Ptr, IsWrite});
251  if (I != Accesses.end())
252  return I->second;
253  return {};
254  }
255 
256 private:
257  /// A wrapper around ScalarEvolution, used to add runtime SCEV checks, and
258  /// applies dynamic knowledge to simplify SCEV expressions and convert them
259  /// to a more usable form. We need this in case assumptions about SCEV
260  /// expressions need to be made in order to avoid unknown dependences. For
261  /// example we might assume a unit stride for a pointer in order to prove
262  /// that a memory access is strided and doesn't wrap.
264  const Loop *InnermostLoop;
265 
266  /// Maps access locations (ptr, read/write) to program order.
268 
269  /// Memory access instructions in program order.
271 
272  /// The program order index to be used for the next instruction.
273  unsigned AccessIdx = 0;
274 
275  // We can access this many bytes in parallel safely.
276  uint64_t MaxSafeDepDistBytes = 0;
277 
278  /// Number of elements (from consecutive iterations) that are safe to
279  /// operate on simultaneously, multiplied by the size of the element in bits.
280  /// The size of the element is taken from the memory access that is most
281  /// restrictive.
282  uint64_t MaxSafeVectorWidthInBits = -1U;
283 
284  /// If we see a non-constant dependence distance we can still try to
285  /// vectorize this loop with runtime checks.
286  bool FoundNonConstantDistanceDependence = false;
287 
288  /// Result of the dependence checks, indicating whether the checked
289  /// dependences are safe for vectorization, require RT checks or are known to
290  /// be unsafe.
292 
293  //// True if Dependences reflects the dependences in the
294  //// loop. If false we exceeded MaxDependences and
295  //// Dependences is invalid.
296  bool RecordDependences = true;
297 
298  /// Memory dependences collected during the analysis. Only valid if
299  /// RecordDependences is true.
300  SmallVector<Dependence, 8> Dependences;
301 
302  /// Check whether there is a plausible dependence between the two
303  /// accesses.
304  ///
305  /// Access \p A must happen before \p B in program order. The two indices
306  /// identify the index into the program order map.
307  ///
308  /// This function checks whether there is a plausible dependence (or the
309  /// absence of such can't be proved) between the two accesses. If there is a
310  /// plausible dependence but the dependence distance is bigger than one
311  /// element access it records this distance in \p MaxSafeDepDistBytes (if this
312  /// distance is smaller than any other distance encountered so far).
313  /// Otherwise, this function returns true signaling a possible dependence.
314  Dependence::DepType isDependent(const MemAccessInfo &A, unsigned AIdx,
315  const MemAccessInfo &B, unsigned BIdx,
316  const ValueToValueMap &Strides);
317 
318  /// Check whether the data dependence could prevent store-load
319  /// forwarding.
320  ///
321  /// \return false if we shouldn't vectorize at all or avoid larger
322  /// vectorization factors by limiting MaxSafeDepDistBytes.
323  bool couldPreventStoreLoadForward(uint64_t Distance, uint64_t TypeByteSize);
324 
325  /// Updates the current safety status with \p S. We can go from Safe to
326  /// either PossiblySafeWithRtChecks or Unsafe and from
327  /// PossiblySafeWithRtChecks to Unsafe.
328  void mergeInStatus(VectorizationSafetyStatus S);
329 };
330 
331 class RuntimePointerChecking;
332 /// A grouping of pointers. A single memcheck is required between
333 /// two groups.
335  /// Create a new pointer checking group containing a single
336  /// pointer, with index \p Index in RtCheck.
338 
339  /// Tries to add the pointer recorded in RtCheck at index
340  /// \p Index to this pointer checking group. We can only add a pointer
341  /// to a checking group if we will still be able to get
342  /// the upper and lower bounds of the check. Returns true in case
343  /// of success, false otherwise.
344  bool addPointer(unsigned Index, RuntimePointerChecking &RtCheck);
345  bool addPointer(unsigned Index, const SCEV *Start, const SCEV *End,
346  unsigned AS, bool NeedsFreeze, ScalarEvolution &SE);
347 
348  /// The SCEV expression which represents the upper bound of all the
349  /// pointers in this group.
350  const SCEV *High;
351  /// The SCEV expression which represents the lower bound of all the
352  /// pointers in this group.
353  const SCEV *Low;
354  /// Indices of all the pointers that constitute this grouping.
356  /// Address space of the involved pointers.
357  unsigned AddressSpace;
358  /// Whether the pointer needs to be frozen after expansion, e.g. because it
359  /// may be poison outside the loop.
360  bool NeedsFreeze = false;
361 };
362 
363 /// A memcheck which made up of a pair of grouped pointers.
364 typedef std::pair<const RuntimeCheckingPtrGroup *,
365  const RuntimeCheckingPtrGroup *>
367 
369  const SCEV *SrcStart;
370  const SCEV *SinkStart;
371  unsigned AccessSize;
373 
375  unsigned AccessSize, bool NeedsFreeze)
378 };
379 
380 /// Holds information about the memory runtime legality checks to verify
381 /// that a group of pointers do not overlap.
383  friend struct RuntimeCheckingPtrGroup;
384 
385 public:
386  struct PointerInfo {
387  /// Holds the pointer value that we need to check.
389  /// Holds the smallest byte address accessed by the pointer throughout all
390  /// iterations of the loop.
391  const SCEV *Start;
392  /// Holds the largest byte address accessed by the pointer throughout all
393  /// iterations of the loop, plus 1.
394  const SCEV *End;
395  /// Holds the information if this pointer is used for writing to memory.
397  /// Holds the id of the set of pointers that could be dependent because of a
398  /// shared underlying object.
399  unsigned DependencySetId;
400  /// Holds the id of the disjoint alias set to which this pointer belongs.
401  unsigned AliasSetId;
402  /// SCEV for the access.
403  const SCEV *Expr;
404  /// True if the pointer expressions needs to be frozen after expansion.
406 
408  bool IsWritePtr, unsigned DependencySetId, unsigned AliasSetId,
409  const SCEV *Expr, bool NeedsFreeze)
413  };
414 
416  : DC(DC), SE(SE) {}
417 
418  /// Reset the state of the pointer runtime information.
419  void reset() {
420  Need = false;
421  Pointers.clear();
422  Checks.clear();
423  }
424 
425  /// Insert a pointer and calculate the start and end SCEVs.
426  /// We need \p PSE in order to compute the SCEV expression of the pointer
427  /// according to the assumptions that we've made during the analysis.
428  /// The method might also version the pointer stride according to \p Strides,
429  /// and add new predicates to \p PSE.
430  void insert(Loop *Lp, Value *Ptr, const SCEV *PtrExpr, Type *AccessTy,
431  bool WritePtr, unsigned DepSetId, unsigned ASId,
432  PredicatedScalarEvolution &PSE, bool NeedsFreeze);
433 
434  /// No run-time memory checking is necessary.
435  bool empty() const { return Pointers.empty(); }
436 
437  /// Generate the checks and store it. This also performs the grouping
438  /// of pointers to reduce the number of memchecks necessary.
439  void generateChecks(MemoryDepChecker::DepCandidates &DepCands,
440  bool UseDependencies);
441 
442  /// Returns the checks that generateChecks created. They can be used to ensure
443  /// no read/write accesses overlap across all loop iterations.
445  return Checks;
446  }
447 
448  // Returns an optional list of (pointer-difference expressions, access size)
449  // pairs that can be used to prove that there are no vectorization-preventing
450  // dependencies at runtime. There are is a vectorization-preventing dependency
451  // if any pointer-difference is <u VF * InterleaveCount * access size. Returns
452  // None if pointer-difference checks cannot be used.
454  if (!CanUseDiffCheck)
455  return None;
456  return {DiffChecks};
457  }
458 
459  /// Decide if we need to add a check between two groups of pointers,
460  /// according to needsChecking.
462  const RuntimeCheckingPtrGroup &N) const;
463 
464  /// Returns the number of run-time checks required according to
465  /// needsChecking.
466  unsigned getNumberOfChecks() const { return Checks.size(); }
467 
468  /// Print the list run-time memory checks necessary.
469  void print(raw_ostream &OS, unsigned Depth = 0) const;
470 
471  /// Print \p Checks.
472  void printChecks(raw_ostream &OS,
474  unsigned Depth = 0) const;
475 
476  /// This flag indicates if we need to add the runtime check.
477  bool Need = false;
478 
479  /// Information about the pointers that may require checking.
481 
482  /// Holds a partitioning of pointers into "check groups".
484 
485  /// Check if pointers are in the same partition
486  ///
487  /// \p PtrToPartition contains the partition number for pointers (-1 if the
488  /// pointer belongs to multiple partitions).
489  static bool
490  arePointersInSamePartition(const SmallVectorImpl<int> &PtrToPartition,
491  unsigned PtrIdx1, unsigned PtrIdx2);
492 
493  /// Decide whether we need to issue a run-time check for pointer at
494  /// index \p I and \p J to prove their independence.
495  bool needsChecking(unsigned I, unsigned J) const;
496 
497  /// Return PointerInfo for pointer at index \p PtrIdx.
498  const PointerInfo &getPointerInfo(unsigned PtrIdx) const {
499  return Pointers[PtrIdx];
500  }
501 
502  ScalarEvolution *getSE() const { return SE; }
503 
504 private:
505  /// Groups pointers such that a single memcheck is required
506  /// between two different groups. This will clear the CheckingGroups vector
507  /// and re-compute it. We will only group dependecies if \p UseDependencies
508  /// is true, otherwise we will create a separate group for each pointer.
509  void groupChecks(MemoryDepChecker::DepCandidates &DepCands,
510  bool UseDependencies);
511 
512  /// Generate the checks and return them.
513  SmallVector<RuntimePointerCheck, 4> generateChecks();
514 
515  /// Try to create add a new (pointer-difference, access size) pair to
516  /// DiffCheck for checking groups \p CGI and \p CGJ. If pointer-difference
517  /// checks cannot be used for the groups, set CanUseDiffCheck to false.
518  void tryToCreateDiffCheck(const RuntimeCheckingPtrGroup &CGI,
519  const RuntimeCheckingPtrGroup &CGJ);
520 
521  MemoryDepChecker &DC;
522 
523  /// Holds a pointer to the ScalarEvolution analysis.
524  ScalarEvolution *SE;
525 
526  /// Set of run-time checks required to establish independence of
527  /// otherwise may-aliasing pointers in the loop.
529 
530  /// Flag indicating if pointer-difference checks can be used
531  bool CanUseDiffCheck = true;
532 
533  /// A list of (pointer-difference, access size) pairs that can be used to
534  /// prove that there are no vectorization-preventing dependencies.
535  SmallVector<PointerDiffInfo> DiffChecks;
536 };
537 
538 /// Drive the analysis of memory accesses in the loop
539 ///
540 /// This class is responsible for analyzing the memory accesses of a loop. It
541 /// collects the accesses and then its main helper the AccessAnalysis class
542 /// finds and categorizes the dependences in buildDependenceSets.
543 ///
544 /// For memory dependences that can be analyzed at compile time, it determines
545 /// whether the dependence is part of cycle inhibiting vectorization. This work
546 /// is delegated to the MemoryDepChecker class.
547 ///
548 /// For memory dependences that cannot be determined at compile time, it
549 /// generates run-time checks to prove independence. This is done by
550 /// AccessAnalysis::canCheckPtrAtRT and the checks are maintained by the
551 /// RuntimePointerCheck class.
552 ///
553 /// If pointers can wrap or can't be expressed as affine AddRec expressions by
554 /// ScalarEvolution, we will generate run-time checks by emitting a
555 /// SCEVUnionPredicate.
556 ///
557 /// Checks for both memory dependences and the SCEV predicates contained in the
558 /// PSE must be emitted in order for the results of this analysis to be valid.
560 public:
562  AAResults *AA, DominatorTree *DT, LoopInfo *LI);
563 
564  /// Return true we can analyze the memory accesses in the loop and there are
565  /// no memory dependence cycles.
566  bool canVectorizeMemory() const { return CanVecMem; }
567 
568  /// Return true if there is a convergent operation in the loop. There may
569  /// still be reported runtime pointer checks that would be required, but it is
570  /// not legal to insert them.
571  bool hasConvergentOp() const { return HasConvergentOp; }
572 
574  return PtrRtChecking.get();
575  }
576 
577  /// Number of memchecks required to prove independence of otherwise
578  /// may-alias pointers.
579  unsigned getNumRuntimePointerChecks() const {
580  return PtrRtChecking->getNumberOfChecks();
581  }
582 
583  /// Return true if the block BB needs to be predicated in order for the loop
584  /// to be vectorized.
585  static bool blockNeedsPredication(BasicBlock *BB, Loop *TheLoop,
586  DominatorTree *DT);
587 
588  /// Returns true if the value V is uniform within the loop.
589  bool isUniform(Value *V) const;
590 
591  uint64_t getMaxSafeDepDistBytes() const { return MaxSafeDepDistBytes; }
592  unsigned getNumStores() const { return NumStores; }
593  unsigned getNumLoads() const { return NumLoads;}
594 
595  /// The diagnostics report generated for the analysis. E.g. why we
596  /// couldn't analyze the loop.
597  const OptimizationRemarkAnalysis *getReport() const { return Report.get(); }
598 
599  /// the Memory Dependence Checker which can determine the
600  /// loop-independent and loop-carried dependences between memory accesses.
601  const MemoryDepChecker &getDepChecker() const { return *DepChecker; }
602 
603  /// Return the list of instructions that use \p Ptr to read or write
604  /// memory.
606  bool isWrite) const {
607  return DepChecker->getInstructionsForAccess(Ptr, isWrite);
608  }
609 
610  /// If an access has a symbolic strides, this maps the pointer value to
611  /// the stride symbol.
612  const ValueToValueMap &getSymbolicStrides() const { return SymbolicStrides; }
613 
614  /// Pointer has a symbolic stride.
615  bool hasStride(Value *V) const { return StrideSet.count(V); }
616 
617  /// Print the information about the memory accesses in the loop.
618  void print(raw_ostream &OS, unsigned Depth = 0) const;
619 
620  /// If the loop has memory dependence involving an invariant address, i.e. two
621  /// stores or a store and a load, then return true, else return false.
623  return HasDependenceInvolvingLoopInvariantAddress;
624  }
625 
626  /// Return the list of stores to invariant addresses.
628  return StoresToInvariantAddresses;
629  }
630 
631  /// Used to add runtime SCEV checks. Simplifies SCEV expressions and converts
632  /// them to a more usable form. All SCEV expressions during the analysis
633  /// should be re-written (and therefore simplified) according to PSE.
634  /// A user of LoopAccessAnalysis will need to emit the runtime checks
635  /// associated with this predicate.
636  const PredicatedScalarEvolution &getPSE() const { return *PSE; }
637 
638 private:
639  /// Analyze the loop.
640  void analyzeLoop(AAResults *AA, LoopInfo *LI,
641  const TargetLibraryInfo *TLI, DominatorTree *DT);
642 
643  /// Check if the structure of the loop allows it to be analyzed by this
644  /// pass.
645  bool canAnalyzeLoop();
646 
647  /// Save the analysis remark.
648  ///
649  /// LAA does not directly emits the remarks. Instead it stores it which the
650  /// client can retrieve and presents as its own analysis
651  /// (e.g. -Rpass-analysis=loop-vectorize).
652  OptimizationRemarkAnalysis &recordAnalysis(StringRef RemarkName,
653  Instruction *Instr = nullptr);
654 
655  /// Collect memory access with loop invariant strides.
656  ///
657  /// Looks for accesses like "a[i * StrideA]" where "StrideA" is loop
658  /// invariant.
659  void collectStridedAccess(Value *LoadOrStoreInst);
660 
661  // Emits the first unsafe memory dependence in a loop.
662  // Emits nothing if there are no unsafe dependences
663  // or if the dependences were not recorded.
664  void emitUnsafeDependenceRemark();
665 
666  std::unique_ptr<PredicatedScalarEvolution> PSE;
667 
668  /// We need to check that all of the pointers in this list are disjoint
669  /// at runtime. Using std::unique_ptr to make using move ctor simpler.
670  std::unique_ptr<RuntimePointerChecking> PtrRtChecking;
671 
672  /// the Memory Dependence Checker which can determine the
673  /// loop-independent and loop-carried dependences between memory accesses.
674  std::unique_ptr<MemoryDepChecker> DepChecker;
675 
676  Loop *TheLoop;
677 
678  unsigned NumLoads = 0;
679  unsigned NumStores = 0;
680 
681  uint64_t MaxSafeDepDistBytes = -1;
682 
683  /// Cache the result of analyzeLoop.
684  bool CanVecMem = false;
685  bool HasConvergentOp = false;
686 
687  /// Indicator that there are non vectorizable stores to a uniform address.
688  bool HasDependenceInvolvingLoopInvariantAddress = false;
689 
690  /// List of stores to invariant addresses.
691  SmallVector<StoreInst *> StoresToInvariantAddresses;
692 
693  /// The diagnostics report generated for the analysis. E.g. why we
694  /// couldn't analyze the loop.
695  std::unique_ptr<OptimizationRemarkAnalysis> Report;
696 
697  /// If an access has a symbolic strides, this maps the pointer value to
698  /// the stride symbol.
699  ValueToValueMap SymbolicStrides;
700 
701  /// Set of symbolic strides values.
702  SmallPtrSet<Value *, 8> StrideSet;
703 };
704 
706 
707 /// Return the SCEV corresponding to a pointer with the symbolic stride
708 /// replaced with constant one, assuming the SCEV predicate associated with
709 /// \p PSE is true.
710 ///
711 /// If necessary this method will version the stride of the pointer according
712 /// to \p PtrToStride and therefore add further predicates to \p PSE.
713 ///
714 /// \p PtrToStride provides the mapping between the pointer value and its
715 /// stride as collected by LoopVectorizationLegality::collectStridedAccess.
716 const SCEV *replaceSymbolicStrideSCEV(PredicatedScalarEvolution &PSE,
717  const ValueToValueMap &PtrToStride,
718  Value *Ptr);
719 
720 /// If the pointer has a constant stride return it in units of the access type
721 /// size. Otherwise return zero.
722 ///
723 /// Ensure that it does not wrap in the address space, assuming the predicate
724 /// associated with \p PSE is true.
725 ///
726 /// If necessary this method will version the stride of the pointer according
727 /// to \p PtrToStride and therefore add further predicates to \p PSE.
728 /// The \p Assume parameter indicates if we are allowed to make additional
729 /// run-time assumptions.
730 int64_t getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy, Value *Ptr,
731  const Loop *Lp,
732  const ValueToValueMap &StridesMap = ValueToValueMap(),
733  bool Assume = false, bool ShouldCheckWrap = true);
734 
735 /// Returns the distance between the pointers \p PtrA and \p PtrB iff they are
736 /// compatible and it is possible to calculate the distance between them. This
737 /// is a simple API that does not depend on the analysis pass.
738 /// \param StrictCheck Ensure that the calculated distance matches the
739 /// type-based one after all the bitcasts removal in the provided pointers.
740 Optional<int> getPointersDiff(Type *ElemTyA, Value *PtrA, Type *ElemTyB,
741  Value *PtrB, const DataLayout &DL,
742  ScalarEvolution &SE, bool StrictCheck = false,
743  bool CheckType = true);
744 
745 /// Attempt to sort the pointers in \p VL and return the sorted indices
746 /// in \p SortedIndices, if reordering is required.
747 ///
748 /// Returns 'true' if sorting is legal, otherwise returns 'false'.
749 ///
750 /// For example, for a given \p VL of memory accesses in program order, a[i+4],
751 /// a[i+0], a[i+1] and a[i+7], this function will sort the \p VL and save the
752 /// sorted indices in \p SortedIndices as a[i+0], a[i+1], a[i+4], a[i+7] and
753 /// saves the mask for actual memory accesses in program order in
754 /// \p SortedIndices as <1,2,0,3>
755 bool sortPtrAccesses(ArrayRef<Value *> VL, Type *ElemTy, const DataLayout &DL,
756  ScalarEvolution &SE,
757  SmallVectorImpl<unsigned> &SortedIndices);
758 
759 /// Returns true if the memory operations \p A and \p B are consecutive.
760 /// This is a simple API that does not depend on the analysis pass.
761 bool isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL,
762  ScalarEvolution &SE, bool CheckType = true);
763 
764 /// This analysis provides dependence information for the memory accesses
765 /// of a loop.
766 ///
767 /// It runs the analysis for a loop on demand. This can be initiated by
768 /// querying the loop access info via LAA::getInfo. getInfo return a
769 /// LoopAccessInfo object. See this class for the specifics of what information
770 /// is provided.
772 public:
773  static char ID;
774 
776 
777  bool runOnFunction(Function &F) override;
778 
779  void getAnalysisUsage(AnalysisUsage &AU) const override;
780 
781  /// Query the result of the loop access information for the loop \p L.
782  ///
783  /// If there is no cached result available run the analysis.
784  const LoopAccessInfo &getInfo(Loop *L);
785 
786  void releaseMemory() override {
787  // Invalidate the cache when the pass is freed.
788  LoopAccessInfoMap.clear();
789  }
790 
791  /// Print the result of the analysis when invoked with -analyze.
792  void print(raw_ostream &OS, const Module *M = nullptr) const override;
793 
794 private:
795  /// The cache.
797 
798  // The used analysis passes.
799  ScalarEvolution *SE = nullptr;
800  const TargetLibraryInfo *TLI = nullptr;
801  AAResults *AA = nullptr;
802  DominatorTree *DT = nullptr;
803  LoopInfo *LI = nullptr;
804 };
805 
806 /// This analysis provides dependence information for the memory
807 /// accesses of a loop.
808 ///
809 /// It runs the analysis for a loop on demand. This can be initiated by
810 /// querying the loop access info via AM.getResult<LoopAccessAnalysis>.
811 /// getResult return a LoopAccessInfo object. See this class for the
812 /// specifics of what information is provided.
814  : public AnalysisInfoMixin<LoopAccessAnalysis> {
816  static AnalysisKey Key;
817 
818 public:
820 
822 };
823 
825  const LoopAccessInfo &LAI) const {
827 }
828 
830  const LoopAccessInfo &LAI) const {
831  return LAI.getDepChecker().getMemoryInstructions()[Destination];
832 }
833 
834 } // End llvm namespace
835 
836 #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:1362
llvm::MemoryDepChecker::clearDependences
void clearDependences()
Definition: LoopAccessAnalysis.h:224
llvm::LoopAccessLegacyAnalysis::ID
static char ID
Definition: LoopAccessAnalysis.h:773
llvm::MemoryDepChecker::Dependence::isBackward
bool isBackward() const
Lexically backward dependence.
Definition: LoopAccessAnalysis.cpp:1458
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:771
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::RuntimePointerCheck
std::pair< const RuntimeCheckingPtrGroup *, const RuntimeCheckingPtrGroup * > RuntimePointerCheck
A memcheck which made up of a pair of grouped pointers.
Definition: LoopAccessAnalysis.h:366
llvm::MemoryDepChecker::VectorizationSafetyStatus::Safe
@ Safe
llvm::PointerDiffInfo::NeedsFreeze
bool NeedsFreeze
Definition: LoopAccessAnalysis.h:372
llvm::LoopAccessInfo::isUniform
bool isUniform(Value *V) const
Returns true if the value V is uniform within the loop.
Definition: LoopAccessAnalysis.cpp:2363
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:171
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:2176
llvm::MemoryDepChecker::Dependence::getSource
Instruction * getSource(const LoopAccessInfo &LAI) const
Return the source instruction of the dependence.
Definition: LoopAccessAnalysis.h:824
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
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:2485
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:2492
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:1474
llvm::LoopAccessAnalysis
This analysis provides dependence information for the memory accesses of a loop.
Definition: LoopAccessAnalysis.h:813
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::getPtrStride
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:1186
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:348
llvm::LoopStandardAnalysisResults
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Definition: LoopAnalysisManager.h:51
llvm::MemoryDepChecker::areDepsSafe
bool areDepsSafe(DepCandidates &AccessSets, MemAccessInfoList &CheckDeps, const ValueToValueMap &Strides)
Check whether the dependencies between the accesses are safe.
Definition: LoopAccessAnalysis.cpp:1842
llvm::RuntimePointerChecking::getDiffChecks
Optional< ArrayRef< PointerDiffInfo > > getDiffChecks() const
Definition: LoopAccessAnalysis.h:453
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:1409
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:466
llvm::MemoryDepChecker::Dependence::Dependence
Dependence(unsigned Source, unsigned Destination, DepType Type)
Definition: LoopAccessAnalysis.h:146
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:137
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:1478
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:2501
llvm::LoopAccessAnalysis::run
Result run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR)
Definition: LoopAccessAnalysis.cpp:2545
llvm::LoopAccessInfo::hasDependenceInvolvingLoopInvariantAddress
bool hasDependenceInvolvingLoopInvariantAddress() const
If the loop has memory dependence involving an invariant address, i.e.
Definition: LoopAccessAnalysis.h:622
llvm::MemoryDepChecker::VectorizationSafetyStatus
VectorizationSafetyStatus
Type to keep track of the status of the dependence check.
Definition: LoopAccessAnalysis.h:96
llvm::AAResults
Definition: AliasAnalysis.h:511
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:2334
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:593
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:1935
llvm::RuntimeCheckingPtrGroup::AddressSpace
unsigned AddressSpace
Address space of the involved pointers.
Definition: LoopAccessAnalysis.h:357
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:1422
llvm::PointerDiffInfo::SinkStart
const SCEV * SinkStart
Definition: LoopAccessAnalysis.h:370
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:54
llvm::LoopAccessInfo::hasStride
bool hasStride(Value *V) const
Pointer has a symbolic stride.
Definition: LoopAccessAnalysis.h:615
llvm::PointerDiffInfo::AccessSize
unsigned AccessSize
Definition: LoopAccessAnalysis.h:371
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:391
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:1296
llvm::RuntimePointerChecking::RuntimePointerChecking
RuntimePointerChecking(MemoryDepChecker &DC, ScalarEvolution *SE)
Definition: LoopAccessAnalysis.h:415
llvm::RuntimePointerChecking::reset
void reset()
Reset the state of the pointer runtime information.
Definition: LoopAccessAnalysis.h:419
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:401
llvm::LoopAccessInfo::hasConvergentOp
bool hasConvergentOp() const
Return true if there is a convergent operation in the loop.
Definition: LoopAccessAnalysis.h:571
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:1920
llvm::RuntimePointerChecking::PointerInfo
Definition: LoopAccessAnalysis.h:386
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:297
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:612
llvm::RuntimePointerChecking
Holds information about the memory runtime legality checks to verify that a group of pointers do not ...
Definition: LoopAccessAnalysis.h:382
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:477
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:399
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:605
llvm::RuntimePointerChecking::getChecks
const SmallVectorImpl< RuntimePointerCheck > & getChecks() const
Returns the checks that generateChecks created.
Definition: LoopAccessAnalysis.h:444
llvm::RuntimePointerChecking::CheckingGroups
SmallVector< RuntimeCheckingPtrGroup, 2 > CheckingGroups
Holds a partitioning of pointers into "check groups".
Definition: LoopAccessAnalysis.h:483
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:334
llvm::LoopAccessInfo::getRuntimePointerChecking
const RuntimePointerChecking * getRuntimePointerChecking() const
Definition: LoopAccessAnalysis.h:573
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::PointerDiffInfo::SrcStart
const SCEV * SrcStart
Definition: LoopAccessAnalysis.h:369
llvm::LoopAccessInfo
Drive the analysis of memory accesses in the loop.
Definition: LoopAccessAnalysis.h:559
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:597
llvm::TrackingVH< Value >
llvm::LoopAccessInfo::getStoresToInvariantAddresses
const ArrayRef< StoreInst * > getStoresToInvariantAddresses() const
Return the list of stores to invariant addresses.
Definition: LoopAccessAnalysis.h:627
llvm::PointerDiffInfo
Definition: LoopAccessAnalysis.h:368
llvm::LoopAccessAnalysis::Result
LoopAccessInfo Result
Definition: LoopAccessAnalysis.h:819
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:786
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:566
llvm::RuntimePointerChecking::getSE
ScalarEvolution * getSE() const
Definition: LoopAccessAnalysis.h:502
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:350
llvm::RuntimeCheckingPtrGroup::Low
const SCEV * Low
The SCEV expression which represents the lower bound of all the pointers in this group.
Definition: LoopAccessAnalysis.h:353
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:601
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:394
llvm::ArrayRef< unsigned >
llvm::LoopInfo
Definition: LoopInfo.h:1102
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:144
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
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:371
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:405
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:173
llvm::LoopAccessInfo::getMaxSafeDepDistBytes
uint64_t getMaxSafeDepDistBytes() const
Definition: LoopAccessAnalysis.h:591
llvm::VectorizerParams::isInterleaveForced
static bool isInterleaveForced()
True if force-vector-interleave was specified by the user.
Definition: LoopAccessAnalysis.cpp:133
llvm::RuntimePointerChecking::PointerInfo::Expr
const SCEV * Expr
SCEV for the access.
Definition: LoopAccessAnalysis.h:403
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:2523
llvm::MemoryDepChecker::Dependence::Unknown
@ Unknown
Definition: LoopAccessAnalysis.h:113
llvm::RuntimePointerChecking::Pointers
SmallVector< PointerInfo, 2 > Pointers
Information about the pointers that may require checking.
Definition: LoopAccessAnalysis.h:480
llvm::LoopAccessInfo::getNumStores
unsigned getNumStores() const
Definition: LoopAccessAnalysis.h:592
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:536
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:2488
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:388
llvm::RuntimePointerChecking::empty
bool empty() const
No run-time memory checking is necessary.
Definition: LoopAccessAnalysis.h:435
llvm::RuntimePointerChecking::printChecks
void printChecks(raw_ostream &OS, const SmallVectorImpl< RuntimePointerCheck > &Checks, unsigned Depth=0) const
Print Checks.
Definition: LoopAccessAnalysis.cpp:562
DiagnosticInfo.h
llvm::LoopAccessInfo::LoopAccessInfo
LoopAccessInfo(Loop *L, ScalarEvolution *SE, const TargetLibraryInfo *TLI, AAResults *AA, DominatorTree *DT, LoopInfo *LI)
Definition: LoopAccessAnalysis.cpp:2433
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:396
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:591
llvm::LoopAccessInfo::getNumRuntimePointerChecks
unsigned getNumRuntimePointerChecks() const
Number of memchecks required to prove independence of otherwise may-alias pointers.
Definition: LoopAccessAnalysis.h:579
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:194
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:2445
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:498
llvm::PointerDiffInfo::PointerDiffInfo
PointerDiffInfo(const SCEV *SrcStart, const SCEV *SinkStart, unsigned AccessSize, bool NeedsFreeze)
Definition: LoopAccessAnalysis.h:374
llvm::SmallVectorImpl< Instruction * >
llvm::MemoryDepChecker::Dependence::isSafeForVectorization
static VectorizationSafetyStatus isSafeForVectorization(DepType Type)
Dependence types that don't prevent vectorization.
Definition: LoopAccessAnalysis.cpp:1441
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:407
llvm::LoopAccessInfo::getPSE
const PredicatedScalarEvolution & getPSE() const
Used to add runtime SCEV checks.
Definition: LoopAccessAnalysis.h:636
OrderMap
MapVector< const Value *, unsigned > OrderMap
Definition: AsmWriter.cpp:98
llvm::MemoryDepChecker::Dependence::Destination
unsigned Destination
Index of the destination of the dependence in the InstMap vector.
Definition: LoopAccessAnalysis.h:142
llvm::RuntimePointerChecking::print
void print(raw_ostream &OS, unsigned Depth=0) const
Print the list run-time memory checks necessary.
Definition: LoopAccessAnalysis.cpp:581
llvm::RuntimeCheckingPtrGroup::Members
SmallVector< unsigned, 2 > Members
Indices of all the pointers that constitute this grouping.
Definition: LoopAccessAnalysis.h:355
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:360
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:829
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:2512
llvm::MemoryDepChecker::VectorizationSafetyStatus::PossiblySafeWithRtChecks
@ PossiblySafeWithRtChecks