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