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