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