LLVM  11.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 OptimizationRemarkEmitter;
30 class raw_ostream;
31 class SCEV;
32 class SCEVUnionPredicate;
33 class Value;
34 
35 /// Collection of parameters shared beetween the Loop Vectorizer and the
36 /// Loop Access Analysis.
38  /// Maximum SIMD width.
39  static const unsigned MaxVectorWidth;
40 
41  /// VF as overridden by the user.
42  static unsigned VectorizationFactor;
43  /// Interleave factor as overridden by the user.
44  static unsigned VectorizationInterleave;
45  /// True if force-vector-interleave was specified by the user.
46  static bool isInterleaveForced();
47 
48  /// \When performing memory disambiguation checks at runtime do not
49  /// make more than this number of comparisons.
50  static unsigned RuntimeMemoryCheckThreshold;
51 };
52 
53 /// Checks memory dependences among accesses to the same underlying
54 /// object to determine whether there vectorization is legal or not (and at
55 /// which vectorization factor).
56 ///
57 /// Note: This class will compute a conservative dependence for access to
58 /// different underlying pointers. Clients, such as the loop vectorizer, will
59 /// sometimes deal these potential dependencies by emitting runtime checks.
60 ///
61 /// We use the ScalarEvolution framework to symbolically evalutate access
62 /// functions pairs. Since we currently don't restructure the loop we can rely
63 /// on the program order of memory accesses to determine their safety.
64 /// At the moment we will only deem accesses as safe for:
65 /// * A negative constant distance assuming program order.
66 ///
67 /// Safe: tmp = a[i + 1]; OR a[i + 1] = x;
68 /// a[i] = tmp; y = a[i];
69 ///
70 /// The latter case is safe because later checks guarantuee that there can't
71 /// be a cycle through a phi node (that is, we check that "x" and "y" is not
72 /// the same variable: a header phi can only be an induction or a reduction, a
73 /// reduction can't have a memory sink, an induction can't have a memory
74 /// source). This is important and must not be violated (or we have to
75 /// resort to checking for cycles through memory).
76 ///
77 /// * A positive constant distance assuming program order that is bigger
78 /// than the biggest memory access.
79 ///
80 /// tmp = a[i] OR b[i] = x
81 /// a[i+2] = tmp y = b[i+2];
82 ///
83 /// Safe distance: 2 x sizeof(a[0]), and 2 x sizeof(b[0]), respectively.
84 ///
85 /// * Zero distances and all accesses have the same size.
86 ///
88 public:
91  /// Set of potential dependent memory accesses.
93 
94  /// Type to keep track of the status of the dependence check. The order of
95  /// the elements is important and has to be from most permissive to least
96  /// permissive.
98  // Can vectorize safely without RT checks. All dependences are known to be
99  // safe.
100  Safe,
101  // Can possibly vectorize with RT checks to overcome unknown dependencies.
102  PossiblySafeWithRtChecks,
103  // Cannot vectorize due to known unsafe dependencies.
104  Unsafe,
105  };
106 
107  /// Dependece between memory access instructions.
108  struct Dependence {
109  /// The type of the dependence.
110  enum DepType {
111  // No dependence.
113  // We couldn't determine the direction or the distance.
115  // Lexically forward.
116  //
117  // FIXME: If we only have loop-independent forward dependences (e.g. a
118  // read and write of A[i]), LAA will locally deem the dependence "safe"
119  // without querying the MemoryDepChecker. Therefore we can miss
120  // enumerating loop-independent forward dependences in
121  // getDependences. Note that as soon as there are different
122  // indices used to access the same array, the MemoryDepChecker *is*
123  // queried and the dependence list is complete.
125  // Forward, but if vectorized, is likely to prevent store-to-load
126  // forwarding.
128  // Lexically backward.
130  // Backward, but the distance allows a vectorization factor of
131  // MaxSafeDepDistBytes.
133  // Same, but may prevent store-to-load forwarding.
134  BackwardVectorizableButPreventsForwarding
135  };
136 
137  /// String version of the types.
138  static const char *DepName[];
139 
140  /// Index of the source of the dependence in the InstMap vector.
141  unsigned Source;
142  /// Index of the destination of the dependence in the InstMap vector.
143  unsigned Destination;
144  /// The type of the dependence.
146 
147  Dependence(unsigned Source, unsigned Destination, DepType Type)
148  : Source(Source), Destination(Destination), Type(Type) {}
149 
150  /// Return the source instruction of the dependence.
151  Instruction *getSource(const LoopAccessInfo &LAI) const;
152  /// Return the destination instruction of the dependence.
153  Instruction *getDestination(const LoopAccessInfo &LAI) const;
154 
155  /// Dependence types that don't prevent vectorization.
156  static VectorizationSafetyStatus isSafeForVectorization(DepType Type);
157 
158  /// Lexically forward dependence.
159  bool isForward() const;
160  /// Lexically backward dependence.
161  bool isBackward() const;
162 
163  /// May be a lexically backward dependence type (includes Unknown).
164  bool isPossiblyBackward() const;
165 
166  /// Print the dependence. \p Instr is used to map the instruction
167  /// indices to instructions.
168  void print(raw_ostream &OS, unsigned Depth,
169  const SmallVectorImpl<Instruction *> &Instrs) const;
170  };
171 
173  : PSE(PSE), InnermostLoop(L), AccessIdx(0), MaxSafeDepDistBytes(0),
174  MaxSafeRegisterWidth(-1U), FoundNonConstantDistanceDependence(false),
175  Status(VectorizationSafetyStatus::Safe), RecordDependences(true) {}
176 
177  /// Register the location (instructions are given increasing numbers)
178  /// of a write access.
180  Value *Ptr = SI->getPointerOperand();
181  Accesses[MemAccessInfo(Ptr, true)].push_back(AccessIdx);
182  InstMap.push_back(SI);
183  ++AccessIdx;
184  }
185 
186  /// Register the location (instructions are given increasing numbers)
187  /// of a write access.
188  void addAccess(LoadInst *LI) {
189  Value *Ptr = LI->getPointerOperand();
190  Accesses[MemAccessInfo(Ptr, false)].push_back(AccessIdx);
191  InstMap.push_back(LI);
192  ++AccessIdx;
193  }
194 
195  /// Check whether the dependencies between the accesses are safe.
196  ///
197  /// Only checks sets with elements in \p CheckDeps.
198  bool areDepsSafe(DepCandidates &AccessSets, MemAccessInfoList &CheckDeps,
199  const ValueToValueMap &Strides);
200 
201  /// No memory dependence was encountered that would inhibit
202  /// vectorization.
203  bool isSafeForVectorization() const {
204  return Status == VectorizationSafetyStatus::Safe;
205  }
206 
207  /// The maximum number of bytes of a vector register we can vectorize
208  /// the accesses safely with.
209  uint64_t getMaxSafeDepDistBytes() { return MaxSafeDepDistBytes; }
210 
211  /// Return the number of elements that are safe to operate on
212  /// simultaneously, multiplied by the size of the element in bits.
213  uint64_t getMaxSafeRegisterWidth() const { return MaxSafeRegisterWidth; }
214 
215  /// In same cases when the dependency check fails we can still
216  /// vectorize the loop with a dynamic array access check.
218  return FoundNonConstantDistanceDependence &&
219  Status == VectorizationSafetyStatus::PossiblySafeWithRtChecks;
220  }
221 
222  /// Returns the memory dependences. If null is returned we exceeded
223  /// the MaxDependences threshold and this information is not
224  /// available.
226  return RecordDependences ? &Dependences : nullptr;
227  }
228 
229  void clearDependences() { Dependences.clear(); }
230 
231  /// The vector of memory access instructions. The indices are used as
232  /// instruction identifiers in the Dependence class.
234  return InstMap;
235  }
236 
237  /// Generate a mapping between the memory instructions and their
238  /// indices according to program order.
241 
242  for (unsigned I = 0; I < InstMap.size(); ++I)
243  OrderMap[InstMap[I]] = I;
244 
245  return OrderMap;
246  }
247 
248  /// Find the set of instructions that read or write via \p Ptr.
249  SmallVector<Instruction *, 4> getInstructionsForAccess(Value *Ptr,
250  bool isWrite) const;
251 
252 private:
253  /// A wrapper around ScalarEvolution, used to add runtime SCEV checks, and
254  /// applies dynamic knowledge to simplify SCEV expressions and convert them
255  /// to a more usable form. We need this in case assumptions about SCEV
256  /// expressions need to be made in order to avoid unknown dependences. For
257  /// example we might assume a unit stride for a pointer in order to prove
258  /// that a memory access is strided and doesn't wrap.
260  const Loop *InnermostLoop;
261 
262  /// Maps access locations (ptr, read/write) to program order.
264 
265  /// Memory access instructions in program order.
267 
268  /// The program order index to be used for the next instruction.
269  unsigned AccessIdx;
270 
271  // We can access this many bytes in parallel safely.
272  uint64_t MaxSafeDepDistBytes;
273 
274  /// Number of elements (from consecutive iterations) that are safe to
275  /// operate on simultaneously, multiplied by the size of the element in bits.
276  /// The size of the element is taken from the memory access that is most
277  /// restrictive.
278  uint64_t MaxSafeRegisterWidth;
279 
280  /// If we see a non-constant dependence distance we can still try to
281  /// vectorize this loop with runtime checks.
282  bool FoundNonConstantDistanceDependence;
283 
284  /// Result of the dependence checks, indicating whether the checked
285  /// dependences are safe for vectorization, require RT checks or are known to
286  /// be unsafe.
288 
289  //// True if Dependences reflects the dependences in the
290  //// loop. If false we exceeded MaxDependences and
291  //// Dependences is invalid.
292  bool RecordDependences;
293 
294  /// Memory dependences collected during the analysis. Only valid if
295  /// RecordDependences is true.
296  SmallVector<Dependence, 8> Dependences;
297 
298  /// Check whether there is a plausible dependence between the two
299  /// accesses.
300  ///
301  /// Access \p A must happen before \p B in program order. The two indices
302  /// identify the index into the program order map.
303  ///
304  /// This function checks whether there is a plausible dependence (or the
305  /// absence of such can't be proved) between the two accesses. If there is a
306  /// plausible dependence but the dependence distance is bigger than one
307  /// element access it records this distance in \p MaxSafeDepDistBytes (if this
308  /// distance is smaller than any other distance encountered so far).
309  /// Otherwise, this function returns true signaling a possible dependence.
310  Dependence::DepType isDependent(const MemAccessInfo &A, unsigned AIdx,
311  const MemAccessInfo &B, unsigned BIdx,
312  const ValueToValueMap &Strides);
313 
314  /// Check whether the data dependence could prevent store-load
315  /// forwarding.
316  ///
317  /// \return false if we shouldn't vectorize at all or avoid larger
318  /// vectorization factors by limiting MaxSafeDepDistBytes.
319  bool couldPreventStoreLoadForward(uint64_t Distance, uint64_t TypeByteSize);
320 
321  /// Updates the current safety status with \p S. We can go from Safe to
322  /// either PossiblySafeWithRtChecks or Unsafe and from
323  /// PossiblySafeWithRtChecks to Unsafe.
324  void mergeInStatus(VectorizationSafetyStatus S);
325 };
326 
328 /// A grouping of pointers. A single memcheck is required between
329 /// two groups.
331  /// Create a new pointer checking group containing a single
332  /// pointer, with index \p Index in RtCheck.
334 
335  /// Tries to add the pointer recorded in RtCheck at index
336  /// \p Index to this pointer checking group. We can only add a pointer
337  /// to a checking group if we will still be able to get
338  /// the upper and lower bounds of the check. Returns true in case
339  /// of success, false otherwise.
340  bool addPointer(unsigned Index);
341 
342  /// Constitutes the context of this pointer checking group. For each
343  /// pointer that is a member of this group we will retain the index
344  /// at which it appears in RtCheck.
346  /// The SCEV expression which represents the upper bound of all the
347  /// pointers in this group.
348  const SCEV *High;
349  /// The SCEV expression which represents the lower bound of all the
350  /// pointers in this group.
351  const SCEV *Low;
352  /// Indices of all the pointers that constitute this grouping.
354 };
355 
356 /// A memcheck which made up of a pair of grouped pointers.
357 typedef std::pair<const RuntimeCheckingPtrGroup *,
358  const RuntimeCheckingPtrGroup *>
360 
361 /// Holds information about the memory runtime legality checks to verify
362 /// that a group of pointers do not overlap.
364  friend struct RuntimeCheckingPtrGroup;
365 
366 public:
367  struct PointerInfo {
368  /// Holds the pointer value that we need to check.
370  /// Holds the smallest byte address accessed by the pointer throughout all
371  /// iterations of the loop.
372  const SCEV *Start;
373  /// Holds the largest byte address accessed by the pointer throughout all
374  /// iterations of the loop, plus 1.
375  const SCEV *End;
376  /// Holds the information if this pointer is used for writing to memory.
378  /// Holds the id of the set of pointers that could be dependent because of a
379  /// shared underlying object.
380  unsigned DependencySetId;
381  /// Holds the id of the disjoint alias set to which this pointer belongs.
382  unsigned AliasSetId;
383  /// SCEV for the access.
384  const SCEV *Expr;
385 
386  PointerInfo(Value *PointerValue, const SCEV *Start, const SCEV *End,
387  bool IsWritePtr, unsigned DependencySetId, unsigned AliasSetId,
388  const SCEV *Expr)
389  : PointerValue(PointerValue), Start(Start), End(End),
390  IsWritePtr(IsWritePtr), DependencySetId(DependencySetId),
391  AliasSetId(AliasSetId), Expr(Expr) {}
392  };
393 
395 
396  /// Reset the state of the pointer runtime information.
397  void reset() {
398  Need = false;
399  Pointers.clear();
400  Checks.clear();
401  }
402 
403  /// Insert a pointer and calculate the start and end SCEVs.
404  /// We need \p PSE in order to compute the SCEV expression of the pointer
405  /// according to the assumptions that we've made during the analysis.
406  /// The method might also version the pointer stride according to \p Strides,
407  /// and add new predicates to \p PSE.
408  void insert(Loop *Lp, Value *Ptr, bool WritePtr, unsigned DepSetId,
409  unsigned ASId, const ValueToValueMap &Strides,
411 
412  /// No run-time memory checking is necessary.
413  bool empty() const { return Pointers.empty(); }
414 
415  /// Generate the checks and store it. This also performs the grouping
416  /// of pointers to reduce the number of memchecks necessary.
417  void generateChecks(MemoryDepChecker::DepCandidates &DepCands,
418  bool UseDependencies);
419 
420  /// Returns the checks that generateChecks created.
422  return Checks;
423  }
424 
425  /// Decide if we need to add a check between two groups of pointers,
426  /// according to needsChecking.
427  bool needsChecking(const RuntimeCheckingPtrGroup &M,
428  const RuntimeCheckingPtrGroup &N) const;
429 
430  /// Returns the number of run-time checks required according to
431  /// needsChecking.
432  unsigned getNumberOfChecks() const { return Checks.size(); }
433 
434  /// Print the list run-time memory checks necessary.
435  void print(raw_ostream &OS, unsigned Depth = 0) const;
436 
437  /// Print \p Checks.
438  void printChecks(raw_ostream &OS,
440  unsigned Depth = 0) const;
441 
442  /// This flag indicates if we need to add the runtime check.
443  bool Need;
444 
445  /// Information about the pointers that may require checking.
447 
448  /// Holds a partitioning of pointers into "check groups".
450 
451  /// Check if pointers are in the same partition
452  ///
453  /// \p PtrToPartition contains the partition number for pointers (-1 if the
454  /// pointer belongs to multiple partitions).
455  static bool
456  arePointersInSamePartition(const SmallVectorImpl<int> &PtrToPartition,
457  unsigned PtrIdx1, unsigned PtrIdx2);
458 
459  /// Decide whether we need to issue a run-time check for pointer at
460  /// index \p I and \p J to prove their independence.
461  bool needsChecking(unsigned I, unsigned J) const;
462 
463  /// Return PointerInfo for pointer at index \p PtrIdx.
464  const PointerInfo &getPointerInfo(unsigned PtrIdx) const {
465  return Pointers[PtrIdx];
466  }
467 
468  ScalarEvolution *getSE() const { return SE; }
469 
470 private:
471  /// Groups pointers such that a single memcheck is required
472  /// between two different groups. This will clear the CheckingGroups vector
473  /// and re-compute it. We will only group dependecies if \p UseDependencies
474  /// is true, otherwise we will create a separate group for each pointer.
475  void groupChecks(MemoryDepChecker::DepCandidates &DepCands,
476  bool UseDependencies);
477 
478  /// Generate the checks and return them.
479  SmallVector<RuntimePointerCheck, 4> generateChecks() const;
480 
481  /// Holds a pointer to the ScalarEvolution analysis.
482  ScalarEvolution *SE;
483 
484  /// Set of run-time checks required to establish independence of
485  /// otherwise may-aliasing pointers in the loop.
487 };
488 
489 /// Drive the analysis of memory accesses in the loop
490 ///
491 /// This class is responsible for analyzing the memory accesses of a loop. It
492 /// collects the accesses and then its main helper the AccessAnalysis class
493 /// finds and categorizes the dependences in buildDependenceSets.
494 ///
495 /// For memory dependences that can be analyzed at compile time, it determines
496 /// whether the dependence is part of cycle inhibiting vectorization. This work
497 /// is delegated to the MemoryDepChecker class.
498 ///
499 /// For memory dependences that cannot be determined at compile time, it
500 /// generates run-time checks to prove independence. This is done by
501 /// AccessAnalysis::canCheckPtrAtRT and the checks are maintained by the
502 /// RuntimePointerCheck class.
503 ///
504 /// If pointers can wrap or can't be expressed as affine AddRec expressions by
505 /// ScalarEvolution, we will generate run-time checks by emitting a
506 /// SCEVUnionPredicate.
507 ///
508 /// Checks for both memory dependences and the SCEV predicates contained in the
509 /// PSE must be emitted in order for the results of this analysis to be valid.
511 public:
513  AAResults *AA, DominatorTree *DT, LoopInfo *LI);
514 
515  /// Return true we can analyze the memory accesses in the loop and there are
516  /// no memory dependence cycles.
517  bool canVectorizeMemory() const { return CanVecMem; }
518 
519  /// Return true if there is a convergent operation in the loop. There may
520  /// still be reported runtime pointer checks that would be required, but it is
521  /// not legal to insert them.
522  bool hasConvergentOp() const { return HasConvergentOp; }
523 
525  return PtrRtChecking.get();
526  }
527 
528  /// Number of memchecks required to prove independence of otherwise
529  /// may-alias pointers.
530  unsigned getNumRuntimePointerChecks() const {
531  return PtrRtChecking->getNumberOfChecks();
532  }
533 
534  /// Return true if the block BB needs to be predicated in order for the loop
535  /// to be vectorized.
536  static bool blockNeedsPredication(BasicBlock *BB, Loop *TheLoop,
537  DominatorTree *DT);
538 
539  /// Returns true if the value V is uniform within the loop.
540  bool isUniform(Value *V) const;
541 
542  uint64_t getMaxSafeDepDistBytes() const { return MaxSafeDepDistBytes; }
543  unsigned getNumStores() const { return NumStores; }
544  unsigned getNumLoads() const { return NumLoads;}
545 
546  /// The diagnostics report generated for the analysis. E.g. why we
547  /// couldn't analyze the loop.
548  const OptimizationRemarkAnalysis *getReport() const { return Report.get(); }
549 
550  /// the Memory Dependence Checker which can determine the
551  /// loop-independent and loop-carried dependences between memory accesses.
552  const MemoryDepChecker &getDepChecker() const { return *DepChecker; }
553 
554  /// Return the list of instructions that use \p Ptr to read or write
555  /// memory.
557  bool isWrite) const {
558  return DepChecker->getInstructionsForAccess(Ptr, isWrite);
559  }
560 
561  /// If an access has a symbolic strides, this maps the pointer value to
562  /// the stride symbol.
563  const ValueToValueMap &getSymbolicStrides() const { return SymbolicStrides; }
564 
565  /// Pointer has a symbolic stride.
566  bool hasStride(Value *V) const { return StrideSet.count(V); }
567 
568  /// Print the information about the memory accesses in the loop.
569  void print(raw_ostream &OS, unsigned Depth = 0) const;
570 
571  /// If the loop has memory dependence involving an invariant address, i.e. two
572  /// stores or a store and a load, then return true, else return false.
574  return HasDependenceInvolvingLoopInvariantAddress;
575  }
576 
577  /// Used to add runtime SCEV checks. Simplifies SCEV expressions and converts
578  /// them to a more usable form. All SCEV expressions during the analysis
579  /// should be re-written (and therefore simplified) according to PSE.
580  /// A user of LoopAccessAnalysis will need to emit the runtime checks
581  /// associated with this predicate.
582  const PredicatedScalarEvolution &getPSE() const { return *PSE; }
583 
584 private:
585  /// Analyze the loop.
586  void analyzeLoop(AAResults *AA, LoopInfo *LI,
587  const TargetLibraryInfo *TLI, DominatorTree *DT);
588 
589  /// Check if the structure of the loop allows it to be analyzed by this
590  /// pass.
591  bool canAnalyzeLoop();
592 
593  /// Save the analysis remark.
594  ///
595  /// LAA does not directly emits the remarks. Instead it stores it which the
596  /// client can retrieve and presents as its own analysis
597  /// (e.g. -Rpass-analysis=loop-vectorize).
598  OptimizationRemarkAnalysis &recordAnalysis(StringRef RemarkName,
599  Instruction *Instr = nullptr);
600 
601  /// Collect memory access with loop invariant strides.
602  ///
603  /// Looks for accesses like "a[i * StrideA]" where "StrideA" is loop
604  /// invariant.
605  void collectStridedAccess(Value *LoadOrStoreInst);
606 
607  std::unique_ptr<PredicatedScalarEvolution> PSE;
608 
609  /// We need to check that all of the pointers in this list are disjoint
610  /// at runtime. Using std::unique_ptr to make using move ctor simpler.
611  std::unique_ptr<RuntimePointerChecking> PtrRtChecking;
612 
613  /// the Memory Dependence Checker which can determine the
614  /// loop-independent and loop-carried dependences between memory accesses.
615  std::unique_ptr<MemoryDepChecker> DepChecker;
616 
617  Loop *TheLoop;
618 
619  unsigned NumLoads;
620  unsigned NumStores;
621 
622  uint64_t MaxSafeDepDistBytes;
623 
624  /// Cache the result of analyzeLoop.
625  bool CanVecMem;
626  bool HasConvergentOp;
627 
628  /// Indicator that there are non vectorizable stores to a uniform address.
629  bool HasDependenceInvolvingLoopInvariantAddress;
630 
631  /// The diagnostics report generated for the analysis. E.g. why we
632  /// couldn't analyze the loop.
633  std::unique_ptr<OptimizationRemarkAnalysis> Report;
634 
635  /// If an access has a symbolic strides, this maps the pointer value to
636  /// the stride symbol.
637  ValueToValueMap SymbolicStrides;
638 
639  /// Set of symbolic strides values.
640  SmallPtrSet<Value *, 8> StrideSet;
641 };
642 
644 
645 /// Return the SCEV corresponding to a pointer with the symbolic stride
646 /// replaced with constant one, assuming the SCEV predicate associated with
647 /// \p PSE is true.
648 ///
649 /// If necessary this method will version the stride of the pointer according
650 /// to \p PtrToStride and therefore add further predicates to \p PSE.
651 ///
652 /// If \p OrigPtr is not null, use it to look up the stride value instead of \p
653 /// Ptr. \p PtrToStride provides the mapping between the pointer value and its
654 /// stride as collected by LoopVectorizationLegality::collectStridedAccess.
656  const ValueToValueMap &PtrToStride,
657  Value *Ptr, Value *OrigPtr = nullptr);
658 
659 /// If the pointer has a constant stride return it in units of its
660 /// element size. Otherwise return zero.
661 ///
662 /// Ensure that it does not wrap in the address space, assuming the predicate
663 /// associated with \p PSE is true.
664 ///
665 /// If necessary this method will version the stride of the pointer according
666 /// to \p PtrToStride and therefore add further predicates to \p PSE.
667 /// The \p Assume parameter indicates if we are allowed to make additional
668 /// run-time assumptions.
669 int64_t getPtrStride(PredicatedScalarEvolution &PSE, Value *Ptr, const Loop *Lp,
670  const ValueToValueMap &StridesMap = ValueToValueMap(),
671  bool Assume = false, bool ShouldCheckWrap = true);
672 
673 /// Attempt to sort the pointers in \p VL and return the sorted indices
674 /// in \p SortedIndices, if reordering is required.
675 ///
676 /// Returns 'true' if sorting is legal, otherwise returns 'false'.
677 ///
678 /// For example, for a given \p VL of memory accesses in program order, a[i+4],
679 /// a[i+0], a[i+1] and a[i+7], this function will sort the \p VL and save the
680 /// sorted indices in \p SortedIndices as a[i+0], a[i+1], a[i+4], a[i+7] and
681 /// saves the mask for actual memory accesses in program order in
682 /// \p SortedIndices as <1,2,0,3>
684  ScalarEvolution &SE,
685  SmallVectorImpl<unsigned> &SortedIndices);
686 
687 /// Returns true if the memory operations \p A and \p B are consecutive.
688 /// This is a simple API that does not depend on the analysis pass.
689 bool isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL,
690  ScalarEvolution &SE, bool CheckType = true);
691 
692 /// This analysis provides dependence information for the memory accesses
693 /// of a loop.
694 ///
695 /// It runs the analysis for a loop on demand. This can be initiated by
696 /// querying the loop access info via LAA::getInfo. getInfo return a
697 /// LoopAccessInfo object. See this class for the specifics of what information
698 /// is provided.
700 public:
701  static char ID;
702 
704 
705  bool runOnFunction(Function &F) override;
706 
707  void getAnalysisUsage(AnalysisUsage &AU) const override;
708 
709  /// Query the result of the loop access information for the loop \p L.
710  ///
711  /// If there is no cached result available run the analysis.
712  const LoopAccessInfo &getInfo(Loop *L);
713 
714  void releaseMemory() override {
715  // Invalidate the cache when the pass is freed.
716  LoopAccessInfoMap.clear();
717  }
718 
719  /// Print the result of the analysis when invoked with -analyze.
720  void print(raw_ostream &OS, const Module *M = nullptr) const override;
721 
722 private:
723  /// The cache.
725 
726  // The used analysis passes.
727  ScalarEvolution *SE = nullptr;
728  const TargetLibraryInfo *TLI = nullptr;
729  AAResults *AA = nullptr;
730  DominatorTree *DT = nullptr;
731  LoopInfo *LI = nullptr;
732 };
733 
734 /// This analysis provides dependence information for the memory
735 /// accesses of a loop.
736 ///
737 /// It runs the analysis for a loop on demand. This can be initiated by
738 /// querying the loop access info via AM.getResult<LoopAccessAnalysis>.
739 /// getResult return a LoopAccessInfo object. See this class for the
740 /// specifics of what information is provided.
742  : public AnalysisInfoMixin<LoopAccessAnalysis> {
744  static AnalysisKey Key;
745 
746 public:
748 
749  Result run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR);
750 };
751 
753  const LoopAccessInfo &LAI) const {
755 }
756 
758  const LoopAccessInfo &LAI) const {
759  return LAI.getDepChecker().getMemoryInstructions()[Destination];
760 }
761 
762 } // End llvm namespace
763 
764 #endif
unsigned getNumLoads() const
bool shouldRetryWithRuntimeCheck() const
In same cases when the dependency check fails we can still vectorize the loop with a dynamic array ac...
static unsigned RuntimeMemoryCheckThreshold
performing memory disambiguation checks at runtime do not make more than this number of comparisons...
TrackingVH< Value > PointerValue
Holds the pointer value that we need to check.
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
const MemoryDepChecker & getDepChecker() const
the Memory Dependence Checker which can determine the loop-independent and loop-carried dependences b...
DenseMap< Instruction *, unsigned > generateInstructionOrderMap() const
Generate a mapping between the memory instructions and their indices according to program order...
const SCEV * High
The SCEV expression which represents the upper bound of all the pointers in this group.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
SmallVector< RuntimeCheckingPtrGroup, 2 > CheckingGroups
Holds a partitioning of pointers into "check groups".
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:67
DepType Type
The type of the dependence.
const RuntimePointerChecking * getRuntimePointerChecking() const
The main scalar evolution driver.
int64_t getPtrStride(PredicatedScalarEvolution &PSE, 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 its element size.
const ValueToValueMap & getSymbolicStrides() const
If an access has a symbolic strides, this maps the pointer value to the stride symbol.
bool IsWritePtr
Holds the information if this pointer is used for writing to memory.
void reset()
Reset the state of the pointer runtime information.
SmallVector< Instruction *, 4 > getInstructionsForAccess(Value *Ptr, bool isWrite) const
Return the list of instructions that use Ptr to read or write memory.
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
F(f)
An instruction for reading from memory.
Definition: Instructions.h:167
Checks memory dependences among accesses to the same underlying object to determine whether there vec...
static unsigned VectorizationFactor
VF as overridden by the user.
std::pair< const RuntimeCheckingPtrGroup *, const RuntimeCheckingPtrGroup * > RuntimePointerCheck
A memcheck which made up of a pair of grouped pointers.
uint64_t getMaxSafeDepDistBytes() const
const SCEV * Low
The SCEV expression which represents the lower bound of all the pointers in this group.
uint64_t getMaxSafeDepDistBytes()
The maximum number of bytes of a vector register we can vectorize the accesses safely with...
const OptimizationRemarkAnalysis * getReport() const
The diagnostics report generated for the analysis.
static const unsigned MaxVectorWidth
Maximum SIMD width.
Diagnostic information for optimization analysis remarks.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
Instruction * getDestination(const LoopAccessInfo &LAI) const
Return the destination instruction of the dependence.
unsigned getNumRuntimePointerChecks() const
Number of memchecks required to prove independence of otherwise may-alias pointers.
unsigned getNumberOfChecks() const
Returns the number of run-time checks required according to needsChecking.
ScalarEvolution * getSE() const
Key
PAL metadata keys.
bool isSafeForVectorization() const
No memory dependence was encountered that would inhibit vectorization.
const SmallVectorImpl< Instruction * > & getMemoryInstructions() const
The vector of memory access instructions.
unsigned getNumStores() const
Instruction * getSource(const LoopAccessInfo &LAI) const
Return the source instruction of the dependence.
unsigned Source
Index of the source of the dependence in the InstMap vector.
RuntimePointerChecking(ScalarEvolution *SE)
This header provides classes for managing per-loop analyses.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
An instruction for storing to memory.
Definition: Instructions.h:291
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
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.
static bool runOnFunction(Function &F, bool PostInlining)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
PointerInfo(Value *PointerValue, const SCEV *Start, const SCEV *End, bool IsWritePtr, unsigned DependencySetId, unsigned AliasSetId, const SCEV *Expr)
This analysis provides dependence information for the memory accesses of a loop.
const SCEV * End
Holds the largest byte address accessed by the pointer throughout all iterations of the loop...
SmallVector< unsigned, 2 > Members
Indices of all the pointers that constitute this grouping.
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:390
EquivalenceClasses - This represents a collection of equivalence classes and supports three efficient...
Represent the analysis usage information of a pass.
VectorizationSafetyStatus
Type to keep track of the status of the dependence check.
void addAccess(StoreInst *SI)
Register the location (instructions are given increasing numbers) of a write access.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
const SCEV * replaceSymbolicStrideSCEV(PredicatedScalarEvolution &PSE, const ValueToValueMap &PtrToStride, Value *Ptr, Value *OrigPtr=nullptr)
Return the SCEV corresponding to a pointer with the symbolic stride replaced with constant one...
Value * getPointerOperand()
Definition: Instructions.h:255
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
const PredicatedScalarEvolution & getPSE() const
Used to add runtime SCEV checks.
Value * stripIntegerCast(Value *V)
unsigned AliasSetId
Holds the id of the disjoint alias set to which this pointer belongs.
DepType
The type of the dependence.
A grouping of pointers.
const SmallVectorImpl< Dependence > * getDependences() const
Returns the memory dependences.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:439
Dependence(unsigned Source, unsigned Destination, DepType Type)
DenseMap< const Value *, Value * > ValueToValueMap
const PointerInfo & getPointerInfo(unsigned PtrIdx) const
Return PointerInfo for pointer at index PtrIdx.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:883
Provides information about what library functions are available for the current target.
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
Drive the analysis of memory accesses in the loop.
Holds information about the memory runtime legality checks to verify that a group of pointers do not ...
SmallVector< MemAccessInfo, 8 > MemAccessInfoList
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
basic Basic Alias true
void addAccess(LoadInst *LI)
Register the location (instructions are given increasing numbers) of a write access.
bool hasStride(Value *V) const
Pointer has a symbolic stride.
This analysis provides dependence information for the memory accesses of a loop.
Dependece between memory access instructions.
const SCEV * Start
Holds the smallest byte address accessed by the pointer throughout all iterations of the loop...
This class represents an analyzed expression in the program.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:516
bool empty() const
No run-time memory checking is necessary.
#define I(x, y, z)
Definition: MD5.cpp:59
#define N
bool hasConvergentOp() const
Return true if there is a convergent operation in the loop.
SmallVector< PointerInfo, 2 > Pointers
Information about the pointers that may require checking.
PointerIntPair< Value *, 1, bool > MemAccessInfo
Collection of parameters shared beetween the Loop Vectorizer and the Loop Access Analysis.
static LLVM_ATTRIBUTE_ALWAYS_INLINE bool CheckType(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N, const TargetLowering *TLI, const DataLayout &DL)
bool hasDependenceInvolvingLoopInvariantAddress() const
If the loop has memory dependence involving an invariant address, i.e.
LLVM Value Representation.
Definition: Value.h:74
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
static unsigned VectorizationInterleave
Interleave factor as overridden by the user.
MemoryDepChecker(PredicatedScalarEvolution &PSE, const Loop *L)
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
A container for analyses that lazily runs them and caches their results.
RuntimePointerChecking & RtCheck
Constitutes the context of this pointer checking group.
static bool isInterleaveForced()
True if force-vector-interleave was specified by the user.
bool sortPtrAccesses(ArrayRef< Value *> VL, const DataLayout &DL, ScalarEvolution &SE, SmallVectorImpl< unsigned > &SortedIndices)
Attempt to sort the pointers in VL and return the sorted indices in SortedIndices, if reordering is required.
Value * getPointerOperand()
Definition: Instructions.h:384
bool canVectorizeMemory() const
Return true we can analyze the memory accesses in the loop and there are no memory dependence cycles...
uint64_t getMaxSafeRegisterWidth() const
Return the number of elements that are safe to operate on simultaneously, multiplied by the size of t...
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:71
EquivalenceClasses< MemAccessInfo > DepCandidates
Set of potential dependent memory accesses.
const SmallVector< RuntimePointerCheck, 4 > & getChecks() const
Returns the checks that generateChecks created.
unsigned DependencySetId
Holds the id of the set of pointers that could be dependent because of a shared underlying object...
const SCEV * Expr
SCEV for the access.
unsigned Destination
Index of the destination of the dependence in the InstMap vector.
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
bool Need
This flag indicates if we need to add the runtime check.