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