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 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.
180  void addAccess(StoreInst *SI);
181 
182  /// Register the location (instructions are given increasing numbers)
183  /// of a write access.
184  void addAccess(LoadInst *LI);
185 
186  /// Check whether the dependencies between the accesses are safe.
187  ///
188  /// Only checks sets with elements in \p CheckDeps.
189  bool areDepsSafe(DepCandidates &AccessSets, MemAccessInfoList &CheckDeps,
190  const ValueToValueMap &Strides);
191 
192  /// No memory dependence was encountered that would inhibit
193  /// vectorization.
194  bool isSafeForVectorization() const {
196  }
197 
198  /// Return true if the number of elements that are safe to operate on
199  /// simultaneously is not bounded.
200  bool isSafeForAnyVectorWidth() const {
201  return MaxSafeVectorWidthInBits == UINT_MAX;
202  }
203 
204  /// The maximum number of bytes of a vector register we can vectorize
205  /// the accesses safely with.
206  uint64_t getMaxSafeDepDistBytes() { return MaxSafeDepDistBytes; }
207 
208  /// Return the number of elements that are safe to operate on
209  /// simultaneously, multiplied by the size of the element in bits.
211  return MaxSafeVectorWidthInBits;
212  }
213 
214  /// In same cases when the dependency check fails we can still
215  /// vectorize the loop with a dynamic array access check.
217  return FoundNonConstantDistanceDependence &&
219  }
220 
221  /// Returns the memory dependences. If null is returned we exceeded
222  /// the MaxDependences threshold and this information is not
223  /// available.
225  return RecordDependences ? &Dependences : nullptr;
226  }
227 
228  void clearDependences() { Dependences.clear(); }
229 
230  /// The vector of memory access instructions. The indices are used as
231  /// instruction identifiers in the Dependence class.
233  return InstMap;
234  }
235 
236  /// Generate a mapping between the memory instructions and their
237  /// indices according to program order.
240 
241  for (unsigned I = 0; I < InstMap.size(); ++I)
242  OrderMap[InstMap[I]] = I;
243 
244  return OrderMap;
245  }
246 
247  /// Find the set of instructions that read or write via \p Ptr.
249  bool isWrite) const;
250 
251 private:
252  /// A wrapper around ScalarEvolution, used to add runtime SCEV checks, and
253  /// applies dynamic knowledge to simplify SCEV expressions and convert them
254  /// to a more usable form. We need this in case assumptions about SCEV
255  /// expressions need to be made in order to avoid unknown dependences. For
256  /// example we might assume a unit stride for a pointer in order to prove
257  /// that a memory access is strided and doesn't wrap.
259  const Loop *InnermostLoop;
260 
261  /// Maps access locations (ptr, read/write) to program order.
263 
264  /// Memory access instructions in program order.
266 
267  /// The program order index to be used for the next instruction.
268  unsigned AccessIdx;
269 
270  // We can access this many bytes in parallel safely.
271  uint64_t MaxSafeDepDistBytes;
272 
273  /// Number of elements (from consecutive iterations) that are safe to
274  /// operate on simultaneously, multiplied by the size of the element in bits.
275  /// The size of the element is taken from the memory access that is most
276  /// restrictive.
277  uint64_t MaxSafeVectorWidthInBits;
278 
279  /// If we see a non-constant dependence distance we can still try to
280  /// vectorize this loop with runtime checks.
281  bool FoundNonConstantDistanceDependence;
282 
283  /// Result of the dependence checks, indicating whether the checked
284  /// dependences are safe for vectorization, require RT checks or are known to
285  /// be unsafe.
287 
288  //// True if Dependences reflects the dependences in the
289  //// loop. If false we exceeded MaxDependences and
290  //// Dependences is invalid.
291  bool RecordDependences;
292 
293  /// Memory dependences collected during the analysis. Only valid if
294  /// RecordDependences is true.
295  SmallVector<Dependence, 8> Dependences;
296 
297  /// Check whether there is a plausible dependence between the two
298  /// accesses.
299  ///
300  /// Access \p A must happen before \p B in program order. The two indices
301  /// identify the index into the program order map.
302  ///
303  /// This function checks whether there is a plausible dependence (or the
304  /// absence of such can't be proved) between the two accesses. If there is a
305  /// plausible dependence but the dependence distance is bigger than one
306  /// element access it records this distance in \p MaxSafeDepDistBytes (if this
307  /// distance is smaller than any other distance encountered so far).
308  /// Otherwise, this function returns true signaling a possible dependence.
309  Dependence::DepType isDependent(const MemAccessInfo &A, unsigned AIdx,
310  const MemAccessInfo &B, unsigned BIdx,
311  const ValueToValueMap &Strides);
312 
313  /// Check whether the data dependence could prevent store-load
314  /// forwarding.
315  ///
316  /// \return false if we shouldn't vectorize at all or avoid larger
317  /// vectorization factors by limiting MaxSafeDepDistBytes.
318  bool couldPreventStoreLoadForward(uint64_t Distance, uint64_t TypeByteSize);
319 
320  /// Updates the current safety status with \p S. We can go from Safe to
321  /// either PossiblySafeWithRtChecks or Unsafe and from
322  /// PossiblySafeWithRtChecks to Unsafe.
323  void mergeInStatus(VectorizationSafetyStatus S);
324 };
325 
326 class RuntimePointerChecking;
327 /// A grouping of pointers. A single memcheck is required between
328 /// two groups.
330  /// Create a new pointer checking group containing a single
331  /// pointer, with index \p Index in RtCheck.
333 
334  RuntimeCheckingPtrGroup(unsigned Index, const SCEV *Start, const SCEV *End,
335  unsigned AS)
336  : High(End), Low(Start), AddressSpace(AS) {
337  Members.push_back(Index);
338  }
339 
340  /// Tries to add the pointer recorded in RtCheck at index
341  /// \p Index to this pointer checking group. We can only add a pointer
342  /// to a checking group if we will still be able to get
343  /// the upper and lower bounds of the check. Returns true in case
344  /// of success, false otherwise.
345  bool addPointer(unsigned Index, RuntimePointerChecking &RtCheck);
346  bool addPointer(unsigned Index, const SCEV *Start, const SCEV *End,
347  unsigned AS, ScalarEvolution &SE);
348 
349  /// The SCEV expression which represents the upper bound of all the
350  /// pointers in this group.
351  const SCEV *High;
352  /// The SCEV expression which represents the lower bound of all the
353  /// pointers in this group.
354  const SCEV *Low;
355  /// Indices of all the pointers that constitute this grouping.
357  /// Address space of the involved pointers.
358  unsigned AddressSpace;
359 };
360 
361 /// A memcheck which made up of a pair of grouped pointers.
362 typedef std::pair<const RuntimeCheckingPtrGroup *,
363  const RuntimeCheckingPtrGroup *>
365 
366 /// Holds information about the memory runtime legality checks to verify
367 /// that a group of pointers do not overlap.
369  friend struct RuntimeCheckingPtrGroup;
370 
371 public:
372  struct PointerInfo {
373  /// Holds the pointer value that we need to check.
375  /// Holds the smallest byte address accessed by the pointer throughout all
376  /// iterations of the loop.
377  const SCEV *Start;
378  /// Holds the largest byte address accessed by the pointer throughout all
379  /// iterations of the loop, plus 1.
380  const SCEV *End;
381  /// Holds the information if this pointer is used for writing to memory.
383  /// Holds the id of the set of pointers that could be dependent because of a
384  /// shared underlying object.
385  unsigned DependencySetId;
386  /// Holds the id of the disjoint alias set to which this pointer belongs.
387  unsigned AliasSetId;
388  /// SCEV for the access.
389  const SCEV *Expr;
390 
392  bool IsWritePtr, unsigned DependencySetId, unsigned AliasSetId,
393  const SCEV *Expr)
397  };
398 
400 
401  /// Reset the state of the pointer runtime information.
402  void reset() {
403  Need = false;
404  Pointers.clear();
405  Checks.clear();
406  }
407 
408  /// Insert a pointer and calculate the start and end SCEVs.
409  /// We need \p PSE in order to compute the SCEV expression of the pointer
410  /// according to the assumptions that we've made during the analysis.
411  /// The method might also version the pointer stride according to \p Strides,
412  /// and add new predicates to \p PSE.
413  void insert(Loop *Lp, Value *Ptr, bool WritePtr, unsigned DepSetId,
414  unsigned ASId, const ValueToValueMap &Strides,
416 
417  /// No run-time memory checking is necessary.
418  bool empty() const { return Pointers.empty(); }
419 
420  /// Generate the checks and store it. This also performs the grouping
421  /// of pointers to reduce the number of memchecks necessary.
422  void generateChecks(MemoryDepChecker::DepCandidates &DepCands,
423  bool UseDependencies);
424 
425  /// Returns the checks that generateChecks created.
427  return Checks;
428  }
429 
430  /// Decide if we need to add a check between two groups of pointers,
431  /// according to needsChecking.
433  const RuntimeCheckingPtrGroup &N) const;
434 
435  /// Returns the number of run-time checks required according to
436  /// needsChecking.
437  unsigned getNumberOfChecks() const { return Checks.size(); }
438 
439  /// Print the list run-time memory checks necessary.
440  void print(raw_ostream &OS, unsigned Depth = 0) const;
441 
442  /// Print \p Checks.
443  void printChecks(raw_ostream &OS,
445  unsigned Depth = 0) const;
446 
447  /// This flag indicates if we need to add the runtime check.
448  bool Need;
449 
450  /// Information about the pointers that may require checking.
452 
453  /// Holds a partitioning of pointers into "check groups".
455 
456  /// Check if pointers are in the same partition
457  ///
458  /// \p PtrToPartition contains the partition number for pointers (-1 if the
459  /// pointer belongs to multiple partitions).
460  static bool
461  arePointersInSamePartition(const SmallVectorImpl<int> &PtrToPartition,
462  unsigned PtrIdx1, unsigned PtrIdx2);
463 
464  /// Decide whether we need to issue a run-time check for pointer at
465  /// index \p I and \p J to prove their independence.
466  bool needsChecking(unsigned I, unsigned J) const;
467 
468  /// Return PointerInfo for pointer at index \p PtrIdx.
469  const PointerInfo &getPointerInfo(unsigned PtrIdx) const {
470  return Pointers[PtrIdx];
471  }
472 
473  ScalarEvolution *getSE() const { return SE; }
474 
475 private:
476  /// Groups pointers such that a single memcheck is required
477  /// between two different groups. This will clear the CheckingGroups vector
478  /// and re-compute it. We will only group dependecies if \p UseDependencies
479  /// is true, otherwise we will create a separate group for each pointer.
480  void groupChecks(MemoryDepChecker::DepCandidates &DepCands,
481  bool UseDependencies);
482 
483  /// Generate the checks and return them.
484  SmallVector<RuntimePointerCheck, 4> generateChecks() const;
485 
486  /// Holds a pointer to the ScalarEvolution analysis.
487  ScalarEvolution *SE;
488 
489  /// Set of run-time checks required to establish independence of
490  /// otherwise may-aliasing pointers in the loop.
492 };
493 
494 /// Drive the analysis of memory accesses in the loop
495 ///
496 /// This class is responsible for analyzing the memory accesses of a loop. It
497 /// collects the accesses and then its main helper the AccessAnalysis class
498 /// finds and categorizes the dependences in buildDependenceSets.
499 ///
500 /// For memory dependences that can be analyzed at compile time, it determines
501 /// whether the dependence is part of cycle inhibiting vectorization. This work
502 /// is delegated to the MemoryDepChecker class.
503 ///
504 /// For memory dependences that cannot be determined at compile time, it
505 /// generates run-time checks to prove independence. This is done by
506 /// AccessAnalysis::canCheckPtrAtRT and the checks are maintained by the
507 /// RuntimePointerCheck class.
508 ///
509 /// If pointers can wrap or can't be expressed as affine AddRec expressions by
510 /// ScalarEvolution, we will generate run-time checks by emitting a
511 /// SCEVUnionPredicate.
512 ///
513 /// Checks for both memory dependences and the SCEV predicates contained in the
514 /// PSE must be emitted in order for the results of this analysis to be valid.
516 public:
518  AAResults *AA, DominatorTree *DT, LoopInfo *LI);
519 
520  /// Return true we can analyze the memory accesses in the loop and there are
521  /// no memory dependence cycles.
522  bool canVectorizeMemory() const { return CanVecMem; }
523 
524  /// Return true if there is a convergent operation in the loop. There may
525  /// still be reported runtime pointer checks that would be required, but it is
526  /// not legal to insert them.
527  bool hasConvergentOp() const { return HasConvergentOp; }
528 
530  return PtrRtChecking.get();
531  }
532 
533  /// Number of memchecks required to prove independence of otherwise
534  /// may-alias pointers.
535  unsigned getNumRuntimePointerChecks() const {
536  return PtrRtChecking->getNumberOfChecks();
537  }
538 
539  /// Return true if the block BB needs to be predicated in order for the loop
540  /// to be vectorized.
541  static bool blockNeedsPredication(BasicBlock *BB, Loop *TheLoop,
542  DominatorTree *DT);
543 
544  /// Returns true if the value V is uniform within the loop.
545  bool isUniform(Value *V) const;
546 
547  uint64_t getMaxSafeDepDistBytes() const { return MaxSafeDepDistBytes; }
548  unsigned getNumStores() const { return NumStores; }
549  unsigned getNumLoads() const { return NumLoads;}
550 
551  /// The diagnostics report generated for the analysis. E.g. why we
552  /// couldn't analyze the loop.
553  const OptimizationRemarkAnalysis *getReport() const { return Report.get(); }
554 
555  /// the Memory Dependence Checker which can determine the
556  /// loop-independent and loop-carried dependences between memory accesses.
557  const MemoryDepChecker &getDepChecker() const { return *DepChecker; }
558 
559  /// Return the list of instructions that use \p Ptr to read or write
560  /// memory.
562  bool isWrite) const {
563  return DepChecker->getInstructionsForAccess(Ptr, isWrite);
564  }
565 
566  /// If an access has a symbolic strides, this maps the pointer value to
567  /// the stride symbol.
568  const ValueToValueMap &getSymbolicStrides() const { return SymbolicStrides; }
569 
570  /// Pointer has a symbolic stride.
571  bool hasStride(Value *V) const { return StrideSet.count(V); }
572 
573  /// Print the information about the memory accesses in the loop.
574  void print(raw_ostream &OS, unsigned Depth = 0) const;
575 
576  /// If the loop has memory dependence involving an invariant address, i.e. two
577  /// stores or a store and a load, then return true, else return false.
579  return HasDependenceInvolvingLoopInvariantAddress;
580  }
581 
582  /// Used to add runtime SCEV checks. Simplifies SCEV expressions and converts
583  /// them to a more usable form. All SCEV expressions during the analysis
584  /// should be re-written (and therefore simplified) according to PSE.
585  /// A user of LoopAccessAnalysis will need to emit the runtime checks
586  /// associated with this predicate.
587  const PredicatedScalarEvolution &getPSE() const { return *PSE; }
588 
589 private:
590  /// Analyze the loop.
591  void analyzeLoop(AAResults *AA, LoopInfo *LI,
592  const TargetLibraryInfo *TLI, DominatorTree *DT);
593 
594  /// Check if the structure of the loop allows it to be analyzed by this
595  /// pass.
596  bool canAnalyzeLoop();
597 
598  /// Save the analysis remark.
599  ///
600  /// LAA does not directly emits the remarks. Instead it stores it which the
601  /// client can retrieve and presents as its own analysis
602  /// (e.g. -Rpass-analysis=loop-vectorize).
603  OptimizationRemarkAnalysis &recordAnalysis(StringRef RemarkName,
604  Instruction *Instr = nullptr);
605 
606  /// Collect memory access with loop invariant strides.
607  ///
608  /// Looks for accesses like "a[i * StrideA]" where "StrideA" is loop
609  /// invariant.
610  void collectStridedAccess(Value *LoadOrStoreInst);
611 
612  std::unique_ptr<PredicatedScalarEvolution> PSE;
613 
614  /// We need to check that all of the pointers in this list are disjoint
615  /// at runtime. Using std::unique_ptr to make using move ctor simpler.
616  std::unique_ptr<RuntimePointerChecking> PtrRtChecking;
617 
618  /// the Memory Dependence Checker which can determine the
619  /// loop-independent and loop-carried dependences between memory accesses.
620  std::unique_ptr<MemoryDepChecker> DepChecker;
621 
622  Loop *TheLoop;
623 
624  unsigned NumLoads;
625  unsigned NumStores;
626 
627  uint64_t MaxSafeDepDistBytes;
628 
629  /// Cache the result of analyzeLoop.
630  bool CanVecMem;
631  bool HasConvergentOp;
632 
633  /// Indicator that there are non vectorizable stores to a uniform address.
634  bool HasDependenceInvolvingLoopInvariantAddress;
635 
636  /// The diagnostics report generated for the analysis. E.g. why we
637  /// couldn't analyze the loop.
638  std::unique_ptr<OptimizationRemarkAnalysis> Report;
639 
640  /// If an access has a symbolic strides, this maps the pointer value to
641  /// the stride symbol.
642  ValueToValueMap SymbolicStrides;
643 
644  /// Set of symbolic strides values.
645  SmallPtrSet<Value *, 8> StrideSet;
646 };
647 
649 
650 /// Return the SCEV corresponding to a pointer with the symbolic stride
651 /// replaced with constant one, assuming the SCEV predicate associated with
652 /// \p PSE is true.
653 ///
654 /// If necessary this method will version the stride of the pointer according
655 /// to \p PtrToStride and therefore add further predicates to \p PSE.
656 ///
657 /// \p PtrToStride provides the mapping between the pointer value and its
658 /// stride as collected by LoopVectorizationLegality::collectStridedAccess.
659 const SCEV *replaceSymbolicStrideSCEV(PredicatedScalarEvolution &PSE,
660  const ValueToValueMap &PtrToStride,
661  Value *Ptr);
662 
663 /// If the pointer has a constant stride return it in units of the access type
664 /// size. Otherwise return zero.
665 ///
666 /// Ensure that it does not wrap in the address space, assuming the predicate
667 /// associated with \p PSE is true.
668 ///
669 /// If necessary this method will version the stride of the pointer according
670 /// to \p PtrToStride and therefore add further predicates to \p PSE.
671 /// The \p Assume parameter indicates if we are allowed to make additional
672 /// run-time assumptions.
673 int64_t getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy, Value *Ptr,
674  const Loop *Lp,
675  const ValueToValueMap &StridesMap = ValueToValueMap(),
676  bool Assume = false, bool ShouldCheckWrap = true);
677 
678 /// Returns the distance between the pointers \p PtrA and \p PtrB iff they are
679 /// compatible and it is possible to calculate the distance between them. This
680 /// is a simple API that does not depend on the analysis pass.
681 /// \param StrictCheck Ensure that the calculated distance matches the
682 /// type-based one after all the bitcasts removal in the provided pointers.
683 Optional<int> getPointersDiff(Type *ElemTyA, Value *PtrA, Type *ElemTyB,
684  Value *PtrB, const DataLayout &DL,
685  ScalarEvolution &SE, bool StrictCheck = false,
686  bool CheckType = true);
687 
688 /// Attempt to sort the pointers in \p VL and return the sorted indices
689 /// in \p SortedIndices, if reordering is required.
690 ///
691 /// Returns 'true' if sorting is legal, otherwise returns 'false'.
692 ///
693 /// For example, for a given \p VL of memory accesses in program order, a[i+4],
694 /// a[i+0], a[i+1] and a[i+7], this function will sort the \p VL and save the
695 /// sorted indices in \p SortedIndices as a[i+0], a[i+1], a[i+4], a[i+7] and
696 /// saves the mask for actual memory accesses in program order in
697 /// \p SortedIndices as <1,2,0,3>
698 bool sortPtrAccesses(ArrayRef<Value *> VL, Type *ElemTy, const DataLayout &DL,
699  ScalarEvolution &SE,
700  SmallVectorImpl<unsigned> &SortedIndices);
701 
702 /// Returns true if the memory operations \p A and \p B are consecutive.
703 /// This is a simple API that does not depend on the analysis pass.
704 bool isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL,
705  ScalarEvolution &SE, bool CheckType = true);
706 
707 /// This analysis provides dependence information for the memory accesses
708 /// of a loop.
709 ///
710 /// It runs the analysis for a loop on demand. This can be initiated by
711 /// querying the loop access info via LAA::getInfo. getInfo return a
712 /// LoopAccessInfo object. See this class for the specifics of what information
713 /// is provided.
715 public:
716  static char ID;
717 
719 
720  bool runOnFunction(Function &F) override;
721 
722  void getAnalysisUsage(AnalysisUsage &AU) const override;
723 
724  /// Query the result of the loop access information for the loop \p L.
725  ///
726  /// If there is no cached result available run the analysis.
727  const LoopAccessInfo &getInfo(Loop *L);
728 
729  void releaseMemory() override {
730  // Invalidate the cache when the pass is freed.
731  LoopAccessInfoMap.clear();
732  }
733 
734  /// Print the result of the analysis when invoked with -analyze.
735  void print(raw_ostream &OS, const Module *M = nullptr) const override;
736 
737 private:
738  /// The cache.
740 
741  // The used analysis passes.
742  ScalarEvolution *SE = nullptr;
743  const TargetLibraryInfo *TLI = nullptr;
744  AAResults *AA = nullptr;
745  DominatorTree *DT = nullptr;
746  LoopInfo *LI = nullptr;
747 };
748 
749 /// This analysis provides dependence information for the memory
750 /// accesses of a loop.
751 ///
752 /// It runs the analysis for a loop on demand. This can be initiated by
753 /// querying the loop access info via AM.getResult<LoopAccessAnalysis>.
754 /// getResult return a LoopAccessInfo object. See this class for the
755 /// specifics of what information is provided.
757  : public AnalysisInfoMixin<LoopAccessAnalysis> {
759  static AnalysisKey Key;
760 
761 public:
763 
765 };
766 
768  const LoopAccessInfo &LAI) const {
770 }
771 
773  const LoopAccessInfo &LAI) const {
774  return LAI.getDepChecker().getMemoryInstructions()[Destination];
775 }
776 
777 } // End llvm namespace
778 
779 #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:1206
llvm::MemoryDepChecker::clearDependences
void clearDependences()
Definition: LoopAccessAnalysis.h:228
llvm::LoopAccessLegacyAnalysis::ID
static char ID
Definition: LoopAccessAnalysis.h:716
llvm::MemoryDepChecker::Dependence::isBackward
bool isBackward() const
Lexically backward dependence.
Definition: LoopAccessAnalysis.cpp:1325
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:714
llvm
---------------------— PointerInfo ------------------------------------—
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:364
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:2174
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:170
llvm::Function
Definition: Function.h:61
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:2098
llvm::MemoryDepChecker::Dependence::getSource
Instruction * getSource(const LoopAccessInfo &LAI) const
Return the source instruction of the dependence.
Definition: LoopAccessAnalysis.h:767
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
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:2586
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:461
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:2304
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:238
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:1341
llvm::LoopAccessAnalysis
This analysis provides dependence information for the memory accesses of a loop.
Definition: LoopAccessAnalysis.h:756
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:210
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:1029
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:1710
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:1253
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:437
llvm::MemoryDepChecker::Dependence::Dependence
Dependence(unsigned Source, unsigned Destination, DepType Type)
Definition: LoopAccessAnalysis.h:147
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:1345
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:2313
llvm::LoopAccessAnalysis::run
Result run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR)
Definition: LoopAccessAnalysis.cpp:2357
llvm::LoopAccessInfo::hasDependenceInvolvingLoopInvariantAddress
bool hasDependenceInvolvingLoopInvariantAddress() const
If the loop has memory dependence involving an invariant address, i.e.
Definition: LoopAccessAnalysis.h:578
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:2145
llvm::ValueToValueMap
DenseMap< const Value *, Value * > ValueToValueMap
Definition: ScalarEvolutionExpressions.h:857
llvm::MemoryDepChecker::Dependence::BackwardVectorizable
@ BackwardVectorizable
Definition: LoopAccessAnalysis.h:132
llvm::LoopAccessInfo::getNumLoads
unsigned getNumLoads() const
Definition: LoopAccessAnalysis.h:549
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::MemoryDepChecker::Dependence::print
void print(raw_ostream &OS, unsigned Depth, const SmallVectorImpl< Instruction * > &Instrs) const
Print the dependence.
Definition: LoopAccessAnalysis.cpp:1803
llvm::RuntimeCheckingPtrGroup::AddressSpace
unsigned AddressSpace
Address space of the involved pointers.
Definition: LoopAccessAnalysis.h:358
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
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::addAccess
void addAccess(StoreInst *SI)
Register the location (instructions are given increasing numbers) of a write access.
Definition: LoopAccessAnalysis.cpp:1289
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:53
llvm::LoopAccessInfo::hasStride
bool hasStride(Value *V) const
Pointer has a symbolic stride.
Definition: LoopAccessAnalysis.h:571
llvm::MemoryDepChecker::getDependences
const SmallVectorImpl< Dependence > * getDependences() const
Returns the memory dependences.
Definition: LoopAccessAnalysis.h:224
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:377
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:1140
llvm::AddressSpace
AddressSpace
Definition: NVPTXBaseInfo.h:21
llvm::RuntimePointerChecking::reset
void reset()
Reset the state of the pointer runtime information.
Definition: LoopAccessAnalysis.h:402
llvm::RuntimePointerChecking::PointerInfo::AliasSetId
unsigned AliasSetId
Holds the id of the disjoint alias set to which this pointer belongs.
Definition: LoopAccessAnalysis.h:387
llvm::LoopAccessInfo::hasConvergentOp
bool hasConvergentOp() const
Return true if there is a convergent operation in the loop.
Definition: LoopAccessAnalysis.h:527
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:206
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:1788
llvm::RuntimePointerChecking::PointerInfo
Definition: LoopAccessAnalysis.h:372
llvm::RuntimeCheckingPtrGroup::RuntimeCheckingPtrGroup
RuntimeCheckingPtrGroup(unsigned Index, const SCEV *Start, const SCEV *End, unsigned AS)
Definition: LoopAccessAnalysis.h:334
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:304
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:568
llvm::RuntimePointerChecking
Holds information about the memory runtime legality checks to verify that a group of pointers do not ...
Definition: LoopAccessAnalysis.h:368
llvm::VectorizerParams::VectorizationFactor
static unsigned VectorizationFactor
VF as overridden by the user.
Definition: LoopAccessAnalysis.h:42
llvm::RuntimePointerChecking::Need
bool Need
This flag indicates if we need to add the runtime check.
Definition: LoopAccessAnalysis.h:448
Index
uint32_t Index
Definition: ELFObjHandler.cpp:84
uint64_t
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:385
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:561
llvm::RuntimePointerChecking::getChecks
const SmallVectorImpl< RuntimePointerCheck > & getChecks() const
Returns the checks that generateChecks created.
Definition: LoopAccessAnalysis.h:426
llvm::RuntimePointerChecking::CheckingGroups
SmallVector< RuntimeCheckingPtrGroup, 2 > CheckingGroups
Holds a partitioning of pointers into "check groups".
Definition: LoopAccessAnalysis.h:454
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:329
llvm::LoopAccessInfo::getRuntimePointerChecking
const RuntimePointerChecking * getRuntimePointerChecking() const
Definition: LoopAccessAnalysis.h:529
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::LoopAccessInfo
Drive the analysis of memory accesses in the loop.
Definition: LoopAccessAnalysis.h:515
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:553
llvm::TrackingVH< Value >
llvm::LoopAccessAnalysis::Result
LoopAccessInfo Result
Definition: LoopAccessAnalysis.h:762
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:729
llvm::MemoryDepChecker::isSafeForVectorization
bool isSafeForVectorization() const
No memory dependence was encountered that would inhibit vectorization.
Definition: LoopAccessAnalysis.h:194
llvm::MemoryDepChecker::getMemoryInstructions
const SmallVectorImpl< Instruction * > & getMemoryInstructions() const
The vector of memory access instructions.
Definition: LoopAccessAnalysis.h:232
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:522
llvm::RuntimePointerChecking::getSE
ScalarEvolution * getSE() const
Definition: LoopAccessAnalysis.h:473
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: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:351
llvm::RuntimeCheckingPtrGroup::Low
const SCEV * Low
The SCEV expression which represents the lower bound of all the pointers in this group.
Definition: LoopAccessAnalysis.h:354
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:557
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:380
llvm::LoopInfo
Definition: LoopInfo.h:1083
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:89
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:175
llvm::LoopAccessInfo::getMaxSafeDepDistBytes
uint64_t getMaxSafeDepDistBytes() const
Definition: LoopAccessAnalysis.h:547
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:389
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:2335
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:451
llvm::LoopAccessInfo::getNumStores
unsigned getNumStores() const
Definition: LoopAccessAnalysis.h:548
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:216
llvm::LoopAccessLegacyAnalysis::LoopAccessLegacyAnalysis
LoopAccessLegacyAnalysis()
Definition: LoopAccessAnalysis.cpp:2300
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:200
llvm::RuntimePointerChecking::PointerInfo::PointerValue
TrackingVH< Value > PointerValue
Holds the pointer value that we need to check.
Definition: LoopAccessAnalysis.h:374
llvm::RuntimePointerChecking::empty
bool empty() const
No run-time memory checking is necessary.
Definition: LoopAccessAnalysis.h:418
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:399
DiagnosticInfo.h
llvm::LoopAccessInfo::LoopAccessInfo
LoopAccessInfo(Loop *L, ScalarEvolution *SE, const TargetLibraryInfo *TLI, AAResults *AA, DominatorTree *DT, LoopInfo *LI)
Definition: LoopAccessAnalysis.cpp:2244
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:382
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:585
llvm::LoopAccessInfo::getNumRuntimePointerChecks
unsigned getNumRuntimePointerChecks() const
Number of memchecks required to prove independence of otherwise may-alias pointers.
Definition: LoopAccessAnalysis.h:535
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:2257
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:469
llvm::SmallVectorImpl< Instruction * >
llvm::MemoryDepChecker::Dependence::isSafeForVectorization
static VectorizationSafetyStatus isSafeForVectorization(DepType Type)
Dependence types that don't prevent vectorization.
Definition: LoopAccessAnalysis.cpp:1308
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:391
llvm::LoopAccessInfo::getPSE
const PredicatedScalarEvolution & getPSE() const
Used to add runtime SCEV checks.
Definition: LoopAccessAnalysis.h:587
OrderMap
MapVector< const Value *, unsigned > OrderMap
Definition: AsmWriter.cpp:97
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:1815
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:356
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:772
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:2324
llvm::MemoryDepChecker::VectorizationSafetyStatus::PossiblySafeWithRtChecks
@ PossiblySafeWithRtChecks