xref: /freebsd/contrib/llvm-project/llvm/lib/Analysis/LoopAccessAnalysis.cpp (revision e6bfd18d21b225af6a0ed67ceeaf1293b7b9eba5)
1 //===- LoopAccessAnalysis.cpp - Loop Access Analysis Implementation --------==//
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 // The implementation for the loop memory dependence that was originally
10 // developed for the loop vectorizer.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "llvm/Analysis/LoopAccessAnalysis.h"
15 #include "llvm/ADT/APInt.h"
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/DepthFirstIterator.h"
18 #include "llvm/ADT/EquivalenceClasses.h"
19 #include "llvm/ADT/PointerIntPair.h"
20 #include "llvm/ADT/STLExtras.h"
21 #include "llvm/ADT/SetVector.h"
22 #include "llvm/ADT/SmallPtrSet.h"
23 #include "llvm/ADT/SmallSet.h"
24 #include "llvm/ADT/SmallVector.h"
25 #include "llvm/ADT/iterator_range.h"
26 #include "llvm/Analysis/AliasAnalysis.h"
27 #include "llvm/Analysis/AliasSetTracker.h"
28 #include "llvm/Analysis/LoopAnalysisManager.h"
29 #include "llvm/Analysis/LoopInfo.h"
30 #include "llvm/Analysis/MemoryLocation.h"
31 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
32 #include "llvm/Analysis/ScalarEvolution.h"
33 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
34 #include "llvm/Analysis/TargetLibraryInfo.h"
35 #include "llvm/Analysis/ValueTracking.h"
36 #include "llvm/Analysis/VectorUtils.h"
37 #include "llvm/IR/BasicBlock.h"
38 #include "llvm/IR/Constants.h"
39 #include "llvm/IR/DataLayout.h"
40 #include "llvm/IR/DebugLoc.h"
41 #include "llvm/IR/DerivedTypes.h"
42 #include "llvm/IR/DiagnosticInfo.h"
43 #include "llvm/IR/Dominators.h"
44 #include "llvm/IR/Function.h"
45 #include "llvm/IR/InstrTypes.h"
46 #include "llvm/IR/Instruction.h"
47 #include "llvm/IR/Instructions.h"
48 #include "llvm/IR/Operator.h"
49 #include "llvm/IR/PassManager.h"
50 #include "llvm/IR/PatternMatch.h"
51 #include "llvm/IR/Type.h"
52 #include "llvm/IR/Value.h"
53 #include "llvm/IR/ValueHandle.h"
54 #include "llvm/InitializePasses.h"
55 #include "llvm/Pass.h"
56 #include "llvm/Support/Casting.h"
57 #include "llvm/Support/CommandLine.h"
58 #include "llvm/Support/Debug.h"
59 #include "llvm/Support/ErrorHandling.h"
60 #include "llvm/Support/raw_ostream.h"
61 #include <algorithm>
62 #include <cassert>
63 #include <cstdint>
64 #include <iterator>
65 #include <utility>
66 #include <vector>
67 
68 using namespace llvm;
69 using namespace llvm::PatternMatch;
70 
71 #define DEBUG_TYPE "loop-accesses"
72 
73 static cl::opt<unsigned, true>
74 VectorizationFactor("force-vector-width", cl::Hidden,
75                     cl::desc("Sets the SIMD width. Zero is autoselect."),
76                     cl::location(VectorizerParams::VectorizationFactor));
77 unsigned VectorizerParams::VectorizationFactor;
78 
79 static cl::opt<unsigned, true>
80 VectorizationInterleave("force-vector-interleave", cl::Hidden,
81                         cl::desc("Sets the vectorization interleave count. "
82                                  "Zero is autoselect."),
83                         cl::location(
84                             VectorizerParams::VectorizationInterleave));
85 unsigned VectorizerParams::VectorizationInterleave;
86 
87 static cl::opt<unsigned, true> RuntimeMemoryCheckThreshold(
88     "runtime-memory-check-threshold", cl::Hidden,
89     cl::desc("When performing memory disambiguation checks at runtime do not "
90              "generate more than this number of comparisons (default = 8)."),
91     cl::location(VectorizerParams::RuntimeMemoryCheckThreshold), cl::init(8));
92 unsigned VectorizerParams::RuntimeMemoryCheckThreshold;
93 
94 /// The maximum iterations used to merge memory checks
95 static cl::opt<unsigned> MemoryCheckMergeThreshold(
96     "memory-check-merge-threshold", cl::Hidden,
97     cl::desc("Maximum number of comparisons done when trying to merge "
98              "runtime memory checks. (default = 100)"),
99     cl::init(100));
100 
101 /// Maximum SIMD width.
102 const unsigned VectorizerParams::MaxVectorWidth = 64;
103 
104 /// We collect dependences up to this threshold.
105 static cl::opt<unsigned>
106     MaxDependences("max-dependences", cl::Hidden,
107                    cl::desc("Maximum number of dependences collected by "
108                             "loop-access analysis (default = 100)"),
109                    cl::init(100));
110 
111 /// This enables versioning on the strides of symbolically striding memory
112 /// accesses in code like the following.
113 ///   for (i = 0; i < N; ++i)
114 ///     A[i * Stride1] += B[i * Stride2] ...
115 ///
116 /// Will be roughly translated to
117 ///    if (Stride1 == 1 && Stride2 == 1) {
118 ///      for (i = 0; i < N; i+=4)
119 ///       A[i:i+3] += ...
120 ///    } else
121 ///      ...
122 static cl::opt<bool> EnableMemAccessVersioning(
123     "enable-mem-access-versioning", cl::init(true), cl::Hidden,
124     cl::desc("Enable symbolic stride memory access versioning"));
125 
126 /// Enable store-to-load forwarding conflict detection. This option can
127 /// be disabled for correctness testing.
128 static cl::opt<bool> EnableForwardingConflictDetection(
129     "store-to-load-forwarding-conflict-detection", cl::Hidden,
130     cl::desc("Enable conflict detection in loop-access analysis"),
131     cl::init(true));
132 
133 static cl::opt<unsigned> MaxForkedSCEVDepth(
134     "max-forked-scev-depth", cl::Hidden,
135     cl::desc("Maximum recursion depth when finding forked SCEVs (default = 5)"),
136     cl::init(5));
137 
138 bool VectorizerParams::isInterleaveForced() {
139   return ::VectorizationInterleave.getNumOccurrences() > 0;
140 }
141 
142 Value *llvm::stripIntegerCast(Value *V) {
143   if (auto *CI = dyn_cast<CastInst>(V))
144     if (CI->getOperand(0)->getType()->isIntegerTy())
145       return CI->getOperand(0);
146   return V;
147 }
148 
149 const SCEV *llvm::replaceSymbolicStrideSCEV(PredicatedScalarEvolution &PSE,
150                                             const ValueToValueMap &PtrToStride,
151                                             Value *Ptr) {
152   const SCEV *OrigSCEV = PSE.getSCEV(Ptr);
153 
154   // If there is an entry in the map return the SCEV of the pointer with the
155   // symbolic stride replaced by one.
156   ValueToValueMap::const_iterator SI = PtrToStride.find(Ptr);
157   if (SI == PtrToStride.end())
158     // For a non-symbolic stride, just return the original expression.
159     return OrigSCEV;
160 
161   Value *StrideVal = stripIntegerCast(SI->second);
162 
163   ScalarEvolution *SE = PSE.getSE();
164   const auto *U = cast<SCEVUnknown>(SE->getSCEV(StrideVal));
165   const auto *CT =
166     static_cast<const SCEVConstant *>(SE->getOne(StrideVal->getType()));
167 
168   PSE.addPredicate(*SE->getEqualPredicate(U, CT));
169   auto *Expr = PSE.getSCEV(Ptr);
170 
171   LLVM_DEBUG(dbgs() << "LAA: Replacing SCEV: " << *OrigSCEV
172 	     << " by: " << *Expr << "\n");
173   return Expr;
174 }
175 
176 RuntimeCheckingPtrGroup::RuntimeCheckingPtrGroup(
177     unsigned Index, RuntimePointerChecking &RtCheck)
178     : High(RtCheck.Pointers[Index].End), Low(RtCheck.Pointers[Index].Start),
179       AddressSpace(RtCheck.Pointers[Index]
180                        .PointerValue->getType()
181                        ->getPointerAddressSpace()),
182       NeedsFreeze(RtCheck.Pointers[Index].NeedsFreeze) {
183   Members.push_back(Index);
184 }
185 
186 /// Calculate Start and End points of memory access.
187 /// Let's assume A is the first access and B is a memory access on N-th loop
188 /// iteration. Then B is calculated as:
189 ///   B = A + Step*N .
190 /// Step value may be positive or negative.
191 /// N is a calculated back-edge taken count:
192 ///     N = (TripCount > 0) ? RoundDown(TripCount -1 , VF) : 0
193 /// Start and End points are calculated in the following way:
194 /// Start = UMIN(A, B) ; End = UMAX(A, B) + SizeOfElt,
195 /// where SizeOfElt is the size of single memory access in bytes.
196 ///
197 /// There is no conflict when the intervals are disjoint:
198 /// NoConflict = (P2.Start >= P1.End) || (P1.Start >= P2.End)
199 void RuntimePointerChecking::insert(Loop *Lp, Value *Ptr, const SCEV *PtrExpr,
200                                     Type *AccessTy, bool WritePtr,
201                                     unsigned DepSetId, unsigned ASId,
202                                     PredicatedScalarEvolution &PSE,
203                                     bool NeedsFreeze) {
204   ScalarEvolution *SE = PSE.getSE();
205 
206   const SCEV *ScStart;
207   const SCEV *ScEnd;
208 
209   if (SE->isLoopInvariant(PtrExpr, Lp)) {
210     ScStart = ScEnd = PtrExpr;
211   } else {
212     const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrExpr);
213     assert(AR && "Invalid addrec expression");
214     const SCEV *Ex = PSE.getBackedgeTakenCount();
215 
216     ScStart = AR->getStart();
217     ScEnd = AR->evaluateAtIteration(Ex, *SE);
218     const SCEV *Step = AR->getStepRecurrence(*SE);
219 
220     // For expressions with negative step, the upper bound is ScStart and the
221     // lower bound is ScEnd.
222     if (const auto *CStep = dyn_cast<SCEVConstant>(Step)) {
223       if (CStep->getValue()->isNegative())
224         std::swap(ScStart, ScEnd);
225     } else {
226       // Fallback case: the step is not constant, but we can still
227       // get the upper and lower bounds of the interval by using min/max
228       // expressions.
229       ScStart = SE->getUMinExpr(ScStart, ScEnd);
230       ScEnd = SE->getUMaxExpr(AR->getStart(), ScEnd);
231     }
232   }
233   // Add the size of the pointed element to ScEnd.
234   auto &DL = Lp->getHeader()->getModule()->getDataLayout();
235   Type *IdxTy = DL.getIndexType(Ptr->getType());
236   const SCEV *EltSizeSCEV = SE->getStoreSizeOfExpr(IdxTy, AccessTy);
237   ScEnd = SE->getAddExpr(ScEnd, EltSizeSCEV);
238 
239   Pointers.emplace_back(Ptr, ScStart, ScEnd, WritePtr, DepSetId, ASId, PtrExpr,
240                         NeedsFreeze);
241 }
242 
243 void RuntimePointerChecking::tryToCreateDiffCheck(
244     const RuntimeCheckingPtrGroup &CGI, const RuntimeCheckingPtrGroup &CGJ) {
245   if (!CanUseDiffCheck)
246     return;
247 
248   // If either group contains multiple different pointers, bail out.
249   // TODO: Support multiple pointers by using the minimum or maximum pointer,
250   // depending on src & sink.
251   if (CGI.Members.size() != 1 || CGJ.Members.size() != 1) {
252     CanUseDiffCheck = false;
253     return;
254   }
255 
256   PointerInfo *Src = &Pointers[CGI.Members[0]];
257   PointerInfo *Sink = &Pointers[CGJ.Members[0]];
258 
259   // If either pointer is read and written, multiple checks may be needed. Bail
260   // out.
261   if (!DC.getOrderForAccess(Src->PointerValue, !Src->IsWritePtr).empty() ||
262       !DC.getOrderForAccess(Sink->PointerValue, !Sink->IsWritePtr).empty()) {
263     CanUseDiffCheck = false;
264     return;
265   }
266 
267   ArrayRef<unsigned> AccSrc =
268       DC.getOrderForAccess(Src->PointerValue, Src->IsWritePtr);
269   ArrayRef<unsigned> AccSink =
270       DC.getOrderForAccess(Sink->PointerValue, Sink->IsWritePtr);
271   // If either pointer is accessed multiple times, there may not be a clear
272   // src/sink relation. Bail out for now.
273   if (AccSrc.size() != 1 || AccSink.size() != 1) {
274     CanUseDiffCheck = false;
275     return;
276   }
277   // If the sink is accessed before src, swap src/sink.
278   if (AccSink[0] < AccSrc[0])
279     std::swap(Src, Sink);
280 
281   auto *SrcAR = dyn_cast<SCEVAddRecExpr>(Src->Expr);
282   auto *SinkAR = dyn_cast<SCEVAddRecExpr>(Sink->Expr);
283   if (!SrcAR || !SinkAR || SrcAR->getLoop() != DC.getInnermostLoop() ||
284       SinkAR->getLoop() != DC.getInnermostLoop()) {
285     CanUseDiffCheck = false;
286     return;
287   }
288 
289   const DataLayout &DL =
290       SinkAR->getLoop()->getHeader()->getModule()->getDataLayout();
291   SmallVector<Instruction *, 4> SrcInsts =
292       DC.getInstructionsForAccess(Src->PointerValue, Src->IsWritePtr);
293   SmallVector<Instruction *, 4> SinkInsts =
294       DC.getInstructionsForAccess(Sink->PointerValue, Sink->IsWritePtr);
295   Type *SrcTy = getLoadStoreType(SrcInsts[0]);
296   Type *DstTy = getLoadStoreType(SinkInsts[0]);
297   if (isa<ScalableVectorType>(SrcTy) || isa<ScalableVectorType>(DstTy)) {
298     CanUseDiffCheck = false;
299     return;
300   }
301   unsigned AllocSize =
302       std::max(DL.getTypeAllocSize(SrcTy), DL.getTypeAllocSize(DstTy));
303   IntegerType *IntTy =
304       IntegerType::get(Src->PointerValue->getContext(),
305                        DL.getPointerSizeInBits(CGI.AddressSpace));
306 
307   // Only matching constant steps matching the AllocSize are supported at the
308   // moment. This simplifies the difference computation. Can be extended in the
309   // future.
310   auto *Step = dyn_cast<SCEVConstant>(SinkAR->getStepRecurrence(*SE));
311   if (!Step || Step != SrcAR->getStepRecurrence(*SE) ||
312       Step->getAPInt().abs() != AllocSize) {
313     CanUseDiffCheck = false;
314     return;
315   }
316 
317   // When counting down, the dependence distance needs to be swapped.
318   if (Step->getValue()->isNegative())
319     std::swap(SinkAR, SrcAR);
320 
321   const SCEV *SinkStartInt = SE->getPtrToIntExpr(SinkAR->getStart(), IntTy);
322   const SCEV *SrcStartInt = SE->getPtrToIntExpr(SrcAR->getStart(), IntTy);
323   if (isa<SCEVCouldNotCompute>(SinkStartInt) ||
324       isa<SCEVCouldNotCompute>(SrcStartInt)) {
325     CanUseDiffCheck = false;
326     return;
327   }
328   DiffChecks.emplace_back(SrcStartInt, SinkStartInt, AllocSize,
329                           Src->NeedsFreeze || Sink->NeedsFreeze);
330 }
331 
332 SmallVector<RuntimePointerCheck, 4> RuntimePointerChecking::generateChecks() {
333   SmallVector<RuntimePointerCheck, 4> Checks;
334 
335   for (unsigned I = 0; I < CheckingGroups.size(); ++I) {
336     for (unsigned J = I + 1; J < CheckingGroups.size(); ++J) {
337       const RuntimeCheckingPtrGroup &CGI = CheckingGroups[I];
338       const RuntimeCheckingPtrGroup &CGJ = CheckingGroups[J];
339 
340       if (needsChecking(CGI, CGJ)) {
341         tryToCreateDiffCheck(CGI, CGJ);
342         Checks.push_back(std::make_pair(&CGI, &CGJ));
343       }
344     }
345   }
346   return Checks;
347 }
348 
349 void RuntimePointerChecking::generateChecks(
350     MemoryDepChecker::DepCandidates &DepCands, bool UseDependencies) {
351   assert(Checks.empty() && "Checks is not empty");
352   groupChecks(DepCands, UseDependencies);
353   Checks = generateChecks();
354 }
355 
356 bool RuntimePointerChecking::needsChecking(
357     const RuntimeCheckingPtrGroup &M, const RuntimeCheckingPtrGroup &N) const {
358   for (unsigned I = 0, EI = M.Members.size(); EI != I; ++I)
359     for (unsigned J = 0, EJ = N.Members.size(); EJ != J; ++J)
360       if (needsChecking(M.Members[I], N.Members[J]))
361         return true;
362   return false;
363 }
364 
365 /// Compare \p I and \p J and return the minimum.
366 /// Return nullptr in case we couldn't find an answer.
367 static const SCEV *getMinFromExprs(const SCEV *I, const SCEV *J,
368                                    ScalarEvolution *SE) {
369   const SCEV *Diff = SE->getMinusSCEV(J, I);
370   const SCEVConstant *C = dyn_cast<const SCEVConstant>(Diff);
371 
372   if (!C)
373     return nullptr;
374   if (C->getValue()->isNegative())
375     return J;
376   return I;
377 }
378 
379 bool RuntimeCheckingPtrGroup::addPointer(unsigned Index,
380                                          RuntimePointerChecking &RtCheck) {
381   return addPointer(
382       Index, RtCheck.Pointers[Index].Start, RtCheck.Pointers[Index].End,
383       RtCheck.Pointers[Index].PointerValue->getType()->getPointerAddressSpace(),
384       RtCheck.Pointers[Index].NeedsFreeze, *RtCheck.SE);
385 }
386 
387 bool RuntimeCheckingPtrGroup::addPointer(unsigned Index, const SCEV *Start,
388                                          const SCEV *End, unsigned AS,
389                                          bool NeedsFreeze,
390                                          ScalarEvolution &SE) {
391   assert(AddressSpace == AS &&
392          "all pointers in a checking group must be in the same address space");
393 
394   // Compare the starts and ends with the known minimum and maximum
395   // of this set. We need to know how we compare against the min/max
396   // of the set in order to be able to emit memchecks.
397   const SCEV *Min0 = getMinFromExprs(Start, Low, &SE);
398   if (!Min0)
399     return false;
400 
401   const SCEV *Min1 = getMinFromExprs(End, High, &SE);
402   if (!Min1)
403     return false;
404 
405   // Update the low bound  expression if we've found a new min value.
406   if (Min0 == Start)
407     Low = Start;
408 
409   // Update the high bound expression if we've found a new max value.
410   if (Min1 != End)
411     High = End;
412 
413   Members.push_back(Index);
414   this->NeedsFreeze |= NeedsFreeze;
415   return true;
416 }
417 
418 void RuntimePointerChecking::groupChecks(
419     MemoryDepChecker::DepCandidates &DepCands, bool UseDependencies) {
420   // We build the groups from dependency candidates equivalence classes
421   // because:
422   //    - We know that pointers in the same equivalence class share
423   //      the same underlying object and therefore there is a chance
424   //      that we can compare pointers
425   //    - We wouldn't be able to merge two pointers for which we need
426   //      to emit a memcheck. The classes in DepCands are already
427   //      conveniently built such that no two pointers in the same
428   //      class need checking against each other.
429 
430   // We use the following (greedy) algorithm to construct the groups
431   // For every pointer in the equivalence class:
432   //   For each existing group:
433   //   - if the difference between this pointer and the min/max bounds
434   //     of the group is a constant, then make the pointer part of the
435   //     group and update the min/max bounds of that group as required.
436 
437   CheckingGroups.clear();
438 
439   // If we need to check two pointers to the same underlying object
440   // with a non-constant difference, we shouldn't perform any pointer
441   // grouping with those pointers. This is because we can easily get
442   // into cases where the resulting check would return false, even when
443   // the accesses are safe.
444   //
445   // The following example shows this:
446   // for (i = 0; i < 1000; ++i)
447   //   a[5000 + i * m] = a[i] + a[i + 9000]
448   //
449   // Here grouping gives a check of (5000, 5000 + 1000 * m) against
450   // (0, 10000) which is always false. However, if m is 1, there is no
451   // dependence. Not grouping the checks for a[i] and a[i + 9000] allows
452   // us to perform an accurate check in this case.
453   //
454   // The above case requires that we have an UnknownDependence between
455   // accesses to the same underlying object. This cannot happen unless
456   // FoundNonConstantDistanceDependence is set, and therefore UseDependencies
457   // is also false. In this case we will use the fallback path and create
458   // separate checking groups for all pointers.
459 
460   // If we don't have the dependency partitions, construct a new
461   // checking pointer group for each pointer. This is also required
462   // for correctness, because in this case we can have checking between
463   // pointers to the same underlying object.
464   if (!UseDependencies) {
465     for (unsigned I = 0; I < Pointers.size(); ++I)
466       CheckingGroups.push_back(RuntimeCheckingPtrGroup(I, *this));
467     return;
468   }
469 
470   unsigned TotalComparisons = 0;
471 
472   DenseMap<Value *, SmallVector<unsigned>> PositionMap;
473   for (unsigned Index = 0; Index < Pointers.size(); ++Index) {
474     auto Iter = PositionMap.insert({Pointers[Index].PointerValue, {}});
475     Iter.first->second.push_back(Index);
476   }
477 
478   // We need to keep track of what pointers we've already seen so we
479   // don't process them twice.
480   SmallSet<unsigned, 2> Seen;
481 
482   // Go through all equivalence classes, get the "pointer check groups"
483   // and add them to the overall solution. We use the order in which accesses
484   // appear in 'Pointers' to enforce determinism.
485   for (unsigned I = 0; I < Pointers.size(); ++I) {
486     // We've seen this pointer before, and therefore already processed
487     // its equivalence class.
488     if (Seen.count(I))
489       continue;
490 
491     MemoryDepChecker::MemAccessInfo Access(Pointers[I].PointerValue,
492                                            Pointers[I].IsWritePtr);
493 
494     SmallVector<RuntimeCheckingPtrGroup, 2> Groups;
495     auto LeaderI = DepCands.findValue(DepCands.getLeaderValue(Access));
496 
497     // Because DepCands is constructed by visiting accesses in the order in
498     // which they appear in alias sets (which is deterministic) and the
499     // iteration order within an equivalence class member is only dependent on
500     // the order in which unions and insertions are performed on the
501     // equivalence class, the iteration order is deterministic.
502     for (auto MI = DepCands.member_begin(LeaderI), ME = DepCands.member_end();
503          MI != ME; ++MI) {
504       auto PointerI = PositionMap.find(MI->getPointer());
505       assert(PointerI != PositionMap.end() &&
506              "pointer in equivalence class not found in PositionMap");
507       for (unsigned Pointer : PointerI->second) {
508         bool Merged = false;
509         // Mark this pointer as seen.
510         Seen.insert(Pointer);
511 
512         // Go through all the existing sets and see if we can find one
513         // which can include this pointer.
514         for (RuntimeCheckingPtrGroup &Group : Groups) {
515           // Don't perform more than a certain amount of comparisons.
516           // This should limit the cost of grouping the pointers to something
517           // reasonable.  If we do end up hitting this threshold, the algorithm
518           // will create separate groups for all remaining pointers.
519           if (TotalComparisons > MemoryCheckMergeThreshold)
520             break;
521 
522           TotalComparisons++;
523 
524           if (Group.addPointer(Pointer, *this)) {
525             Merged = true;
526             break;
527           }
528         }
529 
530         if (!Merged)
531           // We couldn't add this pointer to any existing set or the threshold
532           // for the number of comparisons has been reached. Create a new group
533           // to hold the current pointer.
534           Groups.push_back(RuntimeCheckingPtrGroup(Pointer, *this));
535       }
536     }
537 
538     // We've computed the grouped checks for this partition.
539     // Save the results and continue with the next one.
540     llvm::copy(Groups, std::back_inserter(CheckingGroups));
541   }
542 }
543 
544 bool RuntimePointerChecking::arePointersInSamePartition(
545     const SmallVectorImpl<int> &PtrToPartition, unsigned PtrIdx1,
546     unsigned PtrIdx2) {
547   return (PtrToPartition[PtrIdx1] != -1 &&
548           PtrToPartition[PtrIdx1] == PtrToPartition[PtrIdx2]);
549 }
550 
551 bool RuntimePointerChecking::needsChecking(unsigned I, unsigned J) const {
552   const PointerInfo &PointerI = Pointers[I];
553   const PointerInfo &PointerJ = Pointers[J];
554 
555   // No need to check if two readonly pointers intersect.
556   if (!PointerI.IsWritePtr && !PointerJ.IsWritePtr)
557     return false;
558 
559   // Only need to check pointers between two different dependency sets.
560   if (PointerI.DependencySetId == PointerJ.DependencySetId)
561     return false;
562 
563   // Only need to check pointers in the same alias set.
564   if (PointerI.AliasSetId != PointerJ.AliasSetId)
565     return false;
566 
567   return true;
568 }
569 
570 void RuntimePointerChecking::printChecks(
571     raw_ostream &OS, const SmallVectorImpl<RuntimePointerCheck> &Checks,
572     unsigned Depth) const {
573   unsigned N = 0;
574   for (const auto &Check : Checks) {
575     const auto &First = Check.first->Members, &Second = Check.second->Members;
576 
577     OS.indent(Depth) << "Check " << N++ << ":\n";
578 
579     OS.indent(Depth + 2) << "Comparing group (" << Check.first << "):\n";
580     for (unsigned K = 0; K < First.size(); ++K)
581       OS.indent(Depth + 2) << *Pointers[First[K]].PointerValue << "\n";
582 
583     OS.indent(Depth + 2) << "Against group (" << Check.second << "):\n";
584     for (unsigned K = 0; K < Second.size(); ++K)
585       OS.indent(Depth + 2) << *Pointers[Second[K]].PointerValue << "\n";
586   }
587 }
588 
589 void RuntimePointerChecking::print(raw_ostream &OS, unsigned Depth) const {
590 
591   OS.indent(Depth) << "Run-time memory checks:\n";
592   printChecks(OS, Checks, Depth);
593 
594   OS.indent(Depth) << "Grouped accesses:\n";
595   for (unsigned I = 0; I < CheckingGroups.size(); ++I) {
596     const auto &CG = CheckingGroups[I];
597 
598     OS.indent(Depth + 2) << "Group " << &CG << ":\n";
599     OS.indent(Depth + 4) << "(Low: " << *CG.Low << " High: " << *CG.High
600                          << ")\n";
601     for (unsigned J = 0; J < CG.Members.size(); ++J) {
602       OS.indent(Depth + 6) << "Member: " << *Pointers[CG.Members[J]].Expr
603                            << "\n";
604     }
605   }
606 }
607 
608 namespace {
609 
610 /// Analyses memory accesses in a loop.
611 ///
612 /// Checks whether run time pointer checks are needed and builds sets for data
613 /// dependence checking.
614 class AccessAnalysis {
615 public:
616   /// Read or write access location.
617   typedef PointerIntPair<Value *, 1, bool> MemAccessInfo;
618   typedef SmallVector<MemAccessInfo, 8> MemAccessInfoList;
619 
620   AccessAnalysis(Loop *TheLoop, AAResults *AA, LoopInfo *LI,
621                  MemoryDepChecker::DepCandidates &DA,
622                  PredicatedScalarEvolution &PSE)
623       : TheLoop(TheLoop), AST(*AA), LI(LI), DepCands(DA), PSE(PSE) {}
624 
625   /// Register a load  and whether it is only read from.
626   void addLoad(MemoryLocation &Loc, Type *AccessTy, bool IsReadOnly) {
627     Value *Ptr = const_cast<Value*>(Loc.Ptr);
628     AST.add(Ptr, LocationSize::beforeOrAfterPointer(), Loc.AATags);
629     Accesses[MemAccessInfo(Ptr, false)].insert(AccessTy);
630     if (IsReadOnly)
631       ReadOnlyPtr.insert(Ptr);
632   }
633 
634   /// Register a store.
635   void addStore(MemoryLocation &Loc, Type *AccessTy) {
636     Value *Ptr = const_cast<Value*>(Loc.Ptr);
637     AST.add(Ptr, LocationSize::beforeOrAfterPointer(), Loc.AATags);
638     Accesses[MemAccessInfo(Ptr, true)].insert(AccessTy);
639   }
640 
641   /// Check if we can emit a run-time no-alias check for \p Access.
642   ///
643   /// Returns true if we can emit a run-time no alias check for \p Access.
644   /// If we can check this access, this also adds it to a dependence set and
645   /// adds a run-time to check for it to \p RtCheck. If \p Assume is true,
646   /// we will attempt to use additional run-time checks in order to get
647   /// the bounds of the pointer.
648   bool createCheckForAccess(RuntimePointerChecking &RtCheck,
649                             MemAccessInfo Access, Type *AccessTy,
650                             const ValueToValueMap &Strides,
651                             DenseMap<Value *, unsigned> &DepSetId,
652                             Loop *TheLoop, unsigned &RunningDepId,
653                             unsigned ASId, bool ShouldCheckStride, bool Assume);
654 
655   /// Check whether we can check the pointers at runtime for
656   /// non-intersection.
657   ///
658   /// Returns true if we need no check or if we do and we can generate them
659   /// (i.e. the pointers have computable bounds).
660   bool canCheckPtrAtRT(RuntimePointerChecking &RtCheck, ScalarEvolution *SE,
661                        Loop *TheLoop, const ValueToValueMap &Strides,
662                        Value *&UncomputablePtr, bool ShouldCheckWrap = false);
663 
664   /// Goes over all memory accesses, checks whether a RT check is needed
665   /// and builds sets of dependent accesses.
666   void buildDependenceSets() {
667     processMemAccesses();
668   }
669 
670   /// Initial processing of memory accesses determined that we need to
671   /// perform dependency checking.
672   ///
673   /// Note that this can later be cleared if we retry memcheck analysis without
674   /// dependency checking (i.e. FoundNonConstantDistanceDependence).
675   bool isDependencyCheckNeeded() { return !CheckDeps.empty(); }
676 
677   /// We decided that no dependence analysis would be used.  Reset the state.
678   void resetDepChecks(MemoryDepChecker &DepChecker) {
679     CheckDeps.clear();
680     DepChecker.clearDependences();
681   }
682 
683   MemAccessInfoList &getDependenciesToCheck() { return CheckDeps; }
684 
685 private:
686   typedef MapVector<MemAccessInfo, SmallSetVector<Type *, 1>> PtrAccessMap;
687 
688   /// Go over all memory access and check whether runtime pointer checks
689   /// are needed and build sets of dependency check candidates.
690   void processMemAccesses();
691 
692   /// Map of all accesses. Values are the types used to access memory pointed to
693   /// by the pointer.
694   PtrAccessMap Accesses;
695 
696   /// The loop being checked.
697   const Loop *TheLoop;
698 
699   /// List of accesses that need a further dependence check.
700   MemAccessInfoList CheckDeps;
701 
702   /// Set of pointers that are read only.
703   SmallPtrSet<Value*, 16> ReadOnlyPtr;
704 
705   /// An alias set tracker to partition the access set by underlying object and
706   //intrinsic property (such as TBAA metadata).
707   AliasSetTracker AST;
708 
709   LoopInfo *LI;
710 
711   /// Sets of potentially dependent accesses - members of one set share an
712   /// underlying pointer. The set "CheckDeps" identfies which sets really need a
713   /// dependence check.
714   MemoryDepChecker::DepCandidates &DepCands;
715 
716   /// Initial processing of memory accesses determined that we may need
717   /// to add memchecks.  Perform the analysis to determine the necessary checks.
718   ///
719   /// Note that, this is different from isDependencyCheckNeeded.  When we retry
720   /// memcheck analysis without dependency checking
721   /// (i.e. FoundNonConstantDistanceDependence), isDependencyCheckNeeded is
722   /// cleared while this remains set if we have potentially dependent accesses.
723   bool IsRTCheckAnalysisNeeded = false;
724 
725   /// The SCEV predicate containing all the SCEV-related assumptions.
726   PredicatedScalarEvolution &PSE;
727 };
728 
729 } // end anonymous namespace
730 
731 /// Check whether a pointer can participate in a runtime bounds check.
732 /// If \p Assume, try harder to prove that we can compute the bounds of \p Ptr
733 /// by adding run-time checks (overflow checks) if necessary.
734 static bool hasComputableBounds(PredicatedScalarEvolution &PSE, Value *Ptr,
735                                 const SCEV *PtrScev, Loop *L, bool Assume) {
736   // The bounds for loop-invariant pointer is trivial.
737   if (PSE.getSE()->isLoopInvariant(PtrScev, L))
738     return true;
739 
740   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev);
741 
742   if (!AR && Assume)
743     AR = PSE.getAsAddRec(Ptr);
744 
745   if (!AR)
746     return false;
747 
748   return AR->isAffine();
749 }
750 
751 /// Check whether a pointer address cannot wrap.
752 static bool isNoWrap(PredicatedScalarEvolution &PSE,
753                      const ValueToValueMap &Strides, Value *Ptr, Type *AccessTy,
754                      Loop *L) {
755   const SCEV *PtrScev = PSE.getSCEV(Ptr);
756   if (PSE.getSE()->isLoopInvariant(PtrScev, L))
757     return true;
758 
759   int64_t Stride = getPtrStride(PSE, AccessTy, Ptr, L, Strides);
760   if (Stride == 1 || PSE.hasNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW))
761     return true;
762 
763   return false;
764 }
765 
766 static void visitPointers(Value *StartPtr, const Loop &InnermostLoop,
767                           function_ref<void(Value *)> AddPointer) {
768   SmallPtrSet<Value *, 8> Visited;
769   SmallVector<Value *> WorkList;
770   WorkList.push_back(StartPtr);
771 
772   while (!WorkList.empty()) {
773     Value *Ptr = WorkList.pop_back_val();
774     if (!Visited.insert(Ptr).second)
775       continue;
776     auto *PN = dyn_cast<PHINode>(Ptr);
777     // SCEV does not look through non-header PHIs inside the loop. Such phis
778     // can be analyzed by adding separate accesses for each incoming pointer
779     // value.
780     if (PN && InnermostLoop.contains(PN->getParent()) &&
781         PN->getParent() != InnermostLoop.getHeader()) {
782       for (const Use &Inc : PN->incoming_values())
783         WorkList.push_back(Inc);
784     } else
785       AddPointer(Ptr);
786   }
787 }
788 
789 // Walk back through the IR for a pointer, looking for a select like the
790 // following:
791 //
792 //  %offset = select i1 %cmp, i64 %a, i64 %b
793 //  %addr = getelementptr double, double* %base, i64 %offset
794 //  %ld = load double, double* %addr, align 8
795 //
796 // We won't be able to form a single SCEVAddRecExpr from this since the
797 // address for each loop iteration depends on %cmp. We could potentially
798 // produce multiple valid SCEVAddRecExprs, though, and check all of them for
799 // memory safety/aliasing if needed.
800 //
801 // If we encounter some IR we don't yet handle, or something obviously fine
802 // like a constant, then we just add the SCEV for that term to the list passed
803 // in by the caller. If we have a node that may potentially yield a valid
804 // SCEVAddRecExpr then we decompose it into parts and build the SCEV terms
805 // ourselves before adding to the list.
806 static void
807 findForkedSCEVs(ScalarEvolution *SE, const Loop *L, Value *Ptr,
808                 SmallVectorImpl<std::pair<const SCEV *, bool>> &ScevList,
809                 unsigned Depth) {
810   // If our Value is a SCEVAddRecExpr, loop invariant, not an instruction, or
811   // we've exceeded our limit on recursion, just return whatever we have
812   // regardless of whether it can be used for a forked pointer or not, along
813   // with an indication of whether it might be a poison or undef value.
814   const SCEV *Scev = SE->getSCEV(Ptr);
815   if (isa<SCEVAddRecExpr>(Scev) || L->isLoopInvariant(Ptr) ||
816       !isa<Instruction>(Ptr) || Depth == 0) {
817     ScevList.push_back(
818         std::make_pair(Scev, !isGuaranteedNotToBeUndefOrPoison(Ptr)));
819     return;
820   }
821 
822   Depth--;
823 
824   auto UndefPoisonCheck = [](std::pair<const SCEV *, bool> S) -> bool {
825     return S.second;
826   };
827 
828   Instruction *I = cast<Instruction>(Ptr);
829   unsigned Opcode = I->getOpcode();
830   switch (Opcode) {
831   case Instruction::GetElementPtr: {
832     GetElementPtrInst *GEP = cast<GetElementPtrInst>(I);
833     Type *SourceTy = GEP->getSourceElementType();
834     // We only handle base + single offset GEPs here for now.
835     // Not dealing with preexisting gathers yet, so no vectors.
836     if (I->getNumOperands() != 2 || SourceTy->isVectorTy()) {
837       ScevList.push_back(
838           std::make_pair(Scev, !isGuaranteedNotToBeUndefOrPoison(GEP)));
839       break;
840     }
841     SmallVector<std::pair<const SCEV *, bool>, 2> BaseScevs;
842     SmallVector<std::pair<const SCEV *, bool>, 2> OffsetScevs;
843     findForkedSCEVs(SE, L, I->getOperand(0), BaseScevs, Depth);
844     findForkedSCEVs(SE, L, I->getOperand(1), OffsetScevs, Depth);
845 
846     // See if we need to freeze our fork...
847     bool NeedsFreeze = any_of(BaseScevs, UndefPoisonCheck) ||
848                        any_of(OffsetScevs, UndefPoisonCheck);
849 
850     // Check that we only have a single fork, on either the base or the offset.
851     // Copy the SCEV across for the one without a fork in order to generate
852     // the full SCEV for both sides of the GEP.
853     if (OffsetScevs.size() == 2 && BaseScevs.size() == 1)
854       BaseScevs.push_back(BaseScevs[0]);
855     else if (BaseScevs.size() == 2 && OffsetScevs.size() == 1)
856       OffsetScevs.push_back(OffsetScevs[0]);
857     else {
858       ScevList.push_back(std::make_pair(Scev, NeedsFreeze));
859       break;
860     }
861 
862     // Find the pointer type we need to extend to.
863     Type *IntPtrTy = SE->getEffectiveSCEVType(
864         SE->getSCEV(GEP->getPointerOperand())->getType());
865 
866     // Find the size of the type being pointed to. We only have a single
867     // index term (guarded above) so we don't need to index into arrays or
868     // structures, just get the size of the scalar value.
869     const SCEV *Size = SE->getSizeOfExpr(IntPtrTy, SourceTy);
870 
871     // Scale up the offsets by the size of the type, then add to the bases.
872     const SCEV *Scaled1 = SE->getMulExpr(
873         Size, SE->getTruncateOrSignExtend(OffsetScevs[0].first, IntPtrTy));
874     const SCEV *Scaled2 = SE->getMulExpr(
875         Size, SE->getTruncateOrSignExtend(OffsetScevs[1].first, IntPtrTy));
876     ScevList.push_back(std::make_pair(
877         SE->getAddExpr(BaseScevs[0].first, Scaled1), NeedsFreeze));
878     ScevList.push_back(std::make_pair(
879         SE->getAddExpr(BaseScevs[1].first, Scaled2), NeedsFreeze));
880     break;
881   }
882   case Instruction::Select: {
883     SmallVector<std::pair<const SCEV *, bool>, 2> ChildScevs;
884     // A select means we've found a forked pointer, but we currently only
885     // support a single select per pointer so if there's another behind this
886     // then we just bail out and return the generic SCEV.
887     findForkedSCEVs(SE, L, I->getOperand(1), ChildScevs, Depth);
888     findForkedSCEVs(SE, L, I->getOperand(2), ChildScevs, Depth);
889     if (ChildScevs.size() == 2) {
890       ScevList.push_back(ChildScevs[0]);
891       ScevList.push_back(ChildScevs[1]);
892     } else
893       ScevList.push_back(
894           std::make_pair(Scev, !isGuaranteedNotToBeUndefOrPoison(Ptr)));
895     break;
896   }
897   default:
898     // Just return the current SCEV if we haven't handled the instruction yet.
899     LLVM_DEBUG(dbgs() << "ForkedPtr unhandled instruction: " << *I << "\n");
900     ScevList.push_back(
901         std::make_pair(Scev, !isGuaranteedNotToBeUndefOrPoison(Ptr)));
902     break;
903   }
904 }
905 
906 static SmallVector<std::pair<const SCEV *, bool>>
907 findForkedPointer(PredicatedScalarEvolution &PSE,
908                   const ValueToValueMap &StridesMap, Value *Ptr,
909                   const Loop *L) {
910   ScalarEvolution *SE = PSE.getSE();
911   assert(SE->isSCEVable(Ptr->getType()) && "Value is not SCEVable!");
912   SmallVector<std::pair<const SCEV *, bool>> Scevs;
913   findForkedSCEVs(SE, L, Ptr, Scevs, MaxForkedSCEVDepth);
914 
915   // For now, we will only accept a forked pointer with two possible SCEVs.
916   if (Scevs.size() == 2)
917     return Scevs;
918 
919   return {
920       std::make_pair(replaceSymbolicStrideSCEV(PSE, StridesMap, Ptr), false)};
921 }
922 
923 bool AccessAnalysis::createCheckForAccess(RuntimePointerChecking &RtCheck,
924                                           MemAccessInfo Access, Type *AccessTy,
925                                           const ValueToValueMap &StridesMap,
926                                           DenseMap<Value *, unsigned> &DepSetId,
927                                           Loop *TheLoop, unsigned &RunningDepId,
928                                           unsigned ASId, bool ShouldCheckWrap,
929                                           bool Assume) {
930   Value *Ptr = Access.getPointer();
931 
932   SmallVector<std::pair<const SCEV *, bool>> TranslatedPtrs =
933       findForkedPointer(PSE, StridesMap, Ptr, TheLoop);
934 
935   for (auto &P : TranslatedPtrs) {
936     const SCEV *PtrExpr = P.first;
937     if (!hasComputableBounds(PSE, Ptr, PtrExpr, TheLoop, Assume))
938       return false;
939 
940     // When we run after a failing dependency check we have to make sure
941     // we don't have wrapping pointers.
942     if (ShouldCheckWrap) {
943       // Skip wrap checking when translating pointers.
944       if (TranslatedPtrs.size() > 1)
945         return false;
946 
947       if (!isNoWrap(PSE, StridesMap, Ptr, AccessTy, TheLoop)) {
948         auto *Expr = PSE.getSCEV(Ptr);
949         if (!Assume || !isa<SCEVAddRecExpr>(Expr))
950           return false;
951         PSE.setNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW);
952       }
953     }
954     // If there's only one option for Ptr, look it up after bounds and wrap
955     // checking, because assumptions might have been added to PSE.
956     if (TranslatedPtrs.size() == 1)
957       TranslatedPtrs[0] = std::make_pair(
958           replaceSymbolicStrideSCEV(PSE, StridesMap, Ptr), false);
959   }
960 
961   for (auto &P : TranslatedPtrs) {
962     const SCEV *PtrExpr = P.first;
963 
964     // The id of the dependence set.
965     unsigned DepId;
966 
967     if (isDependencyCheckNeeded()) {
968       Value *Leader = DepCands.getLeaderValue(Access).getPointer();
969       unsigned &LeaderId = DepSetId[Leader];
970       if (!LeaderId)
971         LeaderId = RunningDepId++;
972       DepId = LeaderId;
973     } else
974       // Each access has its own dependence set.
975       DepId = RunningDepId++;
976 
977     bool IsWrite = Access.getInt();
978     RtCheck.insert(TheLoop, Ptr, PtrExpr, AccessTy, IsWrite, DepId, ASId, PSE,
979                    P.second);
980     LLVM_DEBUG(dbgs() << "LAA: Found a runtime check ptr:" << *Ptr << '\n');
981   }
982 
983   return true;
984 }
985 
986 bool AccessAnalysis::canCheckPtrAtRT(RuntimePointerChecking &RtCheck,
987                                      ScalarEvolution *SE, Loop *TheLoop,
988                                      const ValueToValueMap &StridesMap,
989                                      Value *&UncomputablePtr, bool ShouldCheckWrap) {
990   // Find pointers with computable bounds. We are going to use this information
991   // to place a runtime bound check.
992   bool CanDoRT = true;
993 
994   bool MayNeedRTCheck = false;
995   if (!IsRTCheckAnalysisNeeded) return true;
996 
997   bool IsDepCheckNeeded = isDependencyCheckNeeded();
998 
999   // We assign a consecutive id to access from different alias sets.
1000   // Accesses between different groups doesn't need to be checked.
1001   unsigned ASId = 0;
1002   for (auto &AS : AST) {
1003     int NumReadPtrChecks = 0;
1004     int NumWritePtrChecks = 0;
1005     bool CanDoAliasSetRT = true;
1006     ++ASId;
1007 
1008     // We assign consecutive id to access from different dependence sets.
1009     // Accesses within the same set don't need a runtime check.
1010     unsigned RunningDepId = 1;
1011     DenseMap<Value *, unsigned> DepSetId;
1012 
1013     SmallVector<std::pair<MemAccessInfo, Type *>, 4> Retries;
1014 
1015     // First, count how many write and read accesses are in the alias set. Also
1016     // collect MemAccessInfos for later.
1017     SmallVector<MemAccessInfo, 4> AccessInfos;
1018     for (const auto &A : AS) {
1019       Value *Ptr = A.getValue();
1020       bool IsWrite = Accesses.count(MemAccessInfo(Ptr, true));
1021 
1022       if (IsWrite)
1023         ++NumWritePtrChecks;
1024       else
1025         ++NumReadPtrChecks;
1026       AccessInfos.emplace_back(Ptr, IsWrite);
1027     }
1028 
1029     // We do not need runtime checks for this alias set, if there are no writes
1030     // or a single write and no reads.
1031     if (NumWritePtrChecks == 0 ||
1032         (NumWritePtrChecks == 1 && NumReadPtrChecks == 0)) {
1033       assert((AS.size() <= 1 ||
1034               all_of(AS,
1035                      [this](auto AC) {
1036                        MemAccessInfo AccessWrite(AC.getValue(), true);
1037                        return DepCands.findValue(AccessWrite) == DepCands.end();
1038                      })) &&
1039              "Can only skip updating CanDoRT below, if all entries in AS "
1040              "are reads or there is at most 1 entry");
1041       continue;
1042     }
1043 
1044     for (auto &Access : AccessInfos) {
1045       for (const auto &AccessTy : Accesses[Access]) {
1046         if (!createCheckForAccess(RtCheck, Access, AccessTy, StridesMap,
1047                                   DepSetId, TheLoop, RunningDepId, ASId,
1048                                   ShouldCheckWrap, false)) {
1049           LLVM_DEBUG(dbgs() << "LAA: Can't find bounds for ptr:"
1050                             << *Access.getPointer() << '\n');
1051           Retries.push_back({Access, AccessTy});
1052           CanDoAliasSetRT = false;
1053         }
1054       }
1055     }
1056 
1057     // Note that this function computes CanDoRT and MayNeedRTCheck
1058     // independently. For example CanDoRT=false, MayNeedRTCheck=false means that
1059     // we have a pointer for which we couldn't find the bounds but we don't
1060     // actually need to emit any checks so it does not matter.
1061     //
1062     // We need runtime checks for this alias set, if there are at least 2
1063     // dependence sets (in which case RunningDepId > 2) or if we need to re-try
1064     // any bound checks (because in that case the number of dependence sets is
1065     // incomplete).
1066     bool NeedsAliasSetRTCheck = RunningDepId > 2 || !Retries.empty();
1067 
1068     // We need to perform run-time alias checks, but some pointers had bounds
1069     // that couldn't be checked.
1070     if (NeedsAliasSetRTCheck && !CanDoAliasSetRT) {
1071       // Reset the CanDoSetRt flag and retry all accesses that have failed.
1072       // We know that we need these checks, so we can now be more aggressive
1073       // and add further checks if required (overflow checks).
1074       CanDoAliasSetRT = true;
1075       for (auto Retry : Retries) {
1076         MemAccessInfo Access = Retry.first;
1077         Type *AccessTy = Retry.second;
1078         if (!createCheckForAccess(RtCheck, Access, AccessTy, StridesMap,
1079                                   DepSetId, TheLoop, RunningDepId, ASId,
1080                                   ShouldCheckWrap, /*Assume=*/true)) {
1081           CanDoAliasSetRT = false;
1082           UncomputablePtr = Access.getPointer();
1083           break;
1084         }
1085       }
1086     }
1087 
1088     CanDoRT &= CanDoAliasSetRT;
1089     MayNeedRTCheck |= NeedsAliasSetRTCheck;
1090     ++ASId;
1091   }
1092 
1093   // If the pointers that we would use for the bounds comparison have different
1094   // address spaces, assume the values aren't directly comparable, so we can't
1095   // use them for the runtime check. We also have to assume they could
1096   // overlap. In the future there should be metadata for whether address spaces
1097   // are disjoint.
1098   unsigned NumPointers = RtCheck.Pointers.size();
1099   for (unsigned i = 0; i < NumPointers; ++i) {
1100     for (unsigned j = i + 1; j < NumPointers; ++j) {
1101       // Only need to check pointers between two different dependency sets.
1102       if (RtCheck.Pointers[i].DependencySetId ==
1103           RtCheck.Pointers[j].DependencySetId)
1104        continue;
1105       // Only need to check pointers in the same alias set.
1106       if (RtCheck.Pointers[i].AliasSetId != RtCheck.Pointers[j].AliasSetId)
1107         continue;
1108 
1109       Value *PtrI = RtCheck.Pointers[i].PointerValue;
1110       Value *PtrJ = RtCheck.Pointers[j].PointerValue;
1111 
1112       unsigned ASi = PtrI->getType()->getPointerAddressSpace();
1113       unsigned ASj = PtrJ->getType()->getPointerAddressSpace();
1114       if (ASi != ASj) {
1115         LLVM_DEBUG(
1116             dbgs() << "LAA: Runtime check would require comparison between"
1117                       " different address spaces\n");
1118         return false;
1119       }
1120     }
1121   }
1122 
1123   if (MayNeedRTCheck && CanDoRT)
1124     RtCheck.generateChecks(DepCands, IsDepCheckNeeded);
1125 
1126   LLVM_DEBUG(dbgs() << "LAA: We need to do " << RtCheck.getNumberOfChecks()
1127                     << " pointer comparisons.\n");
1128 
1129   // If we can do run-time checks, but there are no checks, no runtime checks
1130   // are needed. This can happen when all pointers point to the same underlying
1131   // object for example.
1132   RtCheck.Need = CanDoRT ? RtCheck.getNumberOfChecks() != 0 : MayNeedRTCheck;
1133 
1134   bool CanDoRTIfNeeded = !RtCheck.Need || CanDoRT;
1135   if (!CanDoRTIfNeeded)
1136     RtCheck.reset();
1137   return CanDoRTIfNeeded;
1138 }
1139 
1140 void AccessAnalysis::processMemAccesses() {
1141   // We process the set twice: first we process read-write pointers, last we
1142   // process read-only pointers. This allows us to skip dependence tests for
1143   // read-only pointers.
1144 
1145   LLVM_DEBUG(dbgs() << "LAA: Processing memory accesses...\n");
1146   LLVM_DEBUG(dbgs() << "  AST: "; AST.dump());
1147   LLVM_DEBUG(dbgs() << "LAA:   Accesses(" << Accesses.size() << "):\n");
1148   LLVM_DEBUG({
1149     for (auto A : Accesses)
1150       dbgs() << "\t" << *A.first.getPointer() << " ("
1151              << (A.first.getInt()
1152                      ? "write"
1153                      : (ReadOnlyPtr.count(A.first.getPointer()) ? "read-only"
1154                                                                 : "read"))
1155              << ")\n";
1156   });
1157 
1158   // The AliasSetTracker has nicely partitioned our pointers by metadata
1159   // compatibility and potential for underlying-object overlap. As a result, we
1160   // only need to check for potential pointer dependencies within each alias
1161   // set.
1162   for (const auto &AS : AST) {
1163     // Note that both the alias-set tracker and the alias sets themselves used
1164     // linked lists internally and so the iteration order here is deterministic
1165     // (matching the original instruction order within each set).
1166 
1167     bool SetHasWrite = false;
1168 
1169     // Map of pointers to last access encountered.
1170     typedef DenseMap<const Value*, MemAccessInfo> UnderlyingObjToAccessMap;
1171     UnderlyingObjToAccessMap ObjToLastAccess;
1172 
1173     // Set of access to check after all writes have been processed.
1174     PtrAccessMap DeferredAccesses;
1175 
1176     // Iterate over each alias set twice, once to process read/write pointers,
1177     // and then to process read-only pointers.
1178     for (int SetIteration = 0; SetIteration < 2; ++SetIteration) {
1179       bool UseDeferred = SetIteration > 0;
1180       PtrAccessMap &S = UseDeferred ? DeferredAccesses : Accesses;
1181 
1182       for (const auto &AV : AS) {
1183         Value *Ptr = AV.getValue();
1184 
1185         // For a single memory access in AliasSetTracker, Accesses may contain
1186         // both read and write, and they both need to be handled for CheckDeps.
1187         for (const auto &AC : S) {
1188           if (AC.first.getPointer() != Ptr)
1189             continue;
1190 
1191           bool IsWrite = AC.first.getInt();
1192 
1193           // If we're using the deferred access set, then it contains only
1194           // reads.
1195           bool IsReadOnlyPtr = ReadOnlyPtr.count(Ptr) && !IsWrite;
1196           if (UseDeferred && !IsReadOnlyPtr)
1197             continue;
1198           // Otherwise, the pointer must be in the PtrAccessSet, either as a
1199           // read or a write.
1200           assert(((IsReadOnlyPtr && UseDeferred) || IsWrite ||
1201                   S.count(MemAccessInfo(Ptr, false))) &&
1202                  "Alias-set pointer not in the access set?");
1203 
1204           MemAccessInfo Access(Ptr, IsWrite);
1205           DepCands.insert(Access);
1206 
1207           // Memorize read-only pointers for later processing and skip them in
1208           // the first round (they need to be checked after we have seen all
1209           // write pointers). Note: we also mark pointer that are not
1210           // consecutive as "read-only" pointers (so that we check
1211           // "a[b[i]] +="). Hence, we need the second check for "!IsWrite".
1212           if (!UseDeferred && IsReadOnlyPtr) {
1213             // We only use the pointer keys, the types vector values don't
1214             // matter.
1215             DeferredAccesses.insert({Access, {}});
1216             continue;
1217           }
1218 
1219           // If this is a write - check other reads and writes for conflicts. If
1220           // this is a read only check other writes for conflicts (but only if
1221           // there is no other write to the ptr - this is an optimization to
1222           // catch "a[i] = a[i] + " without having to do a dependence check).
1223           if ((IsWrite || IsReadOnlyPtr) && SetHasWrite) {
1224             CheckDeps.push_back(Access);
1225             IsRTCheckAnalysisNeeded = true;
1226           }
1227 
1228           if (IsWrite)
1229             SetHasWrite = true;
1230 
1231           // Create sets of pointers connected by a shared alias set and
1232           // underlying object.
1233           typedef SmallVector<const Value *, 16> ValueVector;
1234           ValueVector TempObjects;
1235 
1236           getUnderlyingObjects(Ptr, TempObjects, LI);
1237           LLVM_DEBUG(dbgs()
1238                      << "Underlying objects for pointer " << *Ptr << "\n");
1239           for (const Value *UnderlyingObj : TempObjects) {
1240             // nullptr never alias, don't join sets for pointer that have "null"
1241             // in their UnderlyingObjects list.
1242             if (isa<ConstantPointerNull>(UnderlyingObj) &&
1243                 !NullPointerIsDefined(
1244                     TheLoop->getHeader()->getParent(),
1245                     UnderlyingObj->getType()->getPointerAddressSpace()))
1246               continue;
1247 
1248             UnderlyingObjToAccessMap::iterator Prev =
1249                 ObjToLastAccess.find(UnderlyingObj);
1250             if (Prev != ObjToLastAccess.end())
1251               DepCands.unionSets(Access, Prev->second);
1252 
1253             ObjToLastAccess[UnderlyingObj] = Access;
1254             LLVM_DEBUG(dbgs() << "  " << *UnderlyingObj << "\n");
1255           }
1256         }
1257       }
1258     }
1259   }
1260 }
1261 
1262 static bool isInBoundsGep(Value *Ptr) {
1263   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr))
1264     return GEP->isInBounds();
1265   return false;
1266 }
1267 
1268 /// Return true if an AddRec pointer \p Ptr is unsigned non-wrapping,
1269 /// i.e. monotonically increasing/decreasing.
1270 static bool isNoWrapAddRec(Value *Ptr, const SCEVAddRecExpr *AR,
1271                            PredicatedScalarEvolution &PSE, const Loop *L) {
1272   // FIXME: This should probably only return true for NUW.
1273   if (AR->getNoWrapFlags(SCEV::NoWrapMask))
1274     return true;
1275 
1276   // Scalar evolution does not propagate the non-wrapping flags to values that
1277   // are derived from a non-wrapping induction variable because non-wrapping
1278   // could be flow-sensitive.
1279   //
1280   // Look through the potentially overflowing instruction to try to prove
1281   // non-wrapping for the *specific* value of Ptr.
1282 
1283   // The arithmetic implied by an inbounds GEP can't overflow.
1284   auto *GEP = dyn_cast<GetElementPtrInst>(Ptr);
1285   if (!GEP || !GEP->isInBounds())
1286     return false;
1287 
1288   // Make sure there is only one non-const index and analyze that.
1289   Value *NonConstIndex = nullptr;
1290   for (Value *Index : GEP->indices())
1291     if (!isa<ConstantInt>(Index)) {
1292       if (NonConstIndex)
1293         return false;
1294       NonConstIndex = Index;
1295     }
1296   if (!NonConstIndex)
1297     // The recurrence is on the pointer, ignore for now.
1298     return false;
1299 
1300   // The index in GEP is signed.  It is non-wrapping if it's derived from a NSW
1301   // AddRec using a NSW operation.
1302   if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(NonConstIndex))
1303     if (OBO->hasNoSignedWrap() &&
1304         // Assume constant for other the operand so that the AddRec can be
1305         // easily found.
1306         isa<ConstantInt>(OBO->getOperand(1))) {
1307       auto *OpScev = PSE.getSCEV(OBO->getOperand(0));
1308 
1309       if (auto *OpAR = dyn_cast<SCEVAddRecExpr>(OpScev))
1310         return OpAR->getLoop() == L && OpAR->getNoWrapFlags(SCEV::FlagNSW);
1311     }
1312 
1313   return false;
1314 }
1315 
1316 /// Check whether the access through \p Ptr has a constant stride.
1317 int64_t llvm::getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy,
1318                            Value *Ptr, const Loop *Lp,
1319                            const ValueToValueMap &StridesMap, bool Assume,
1320                            bool ShouldCheckWrap) {
1321   Type *Ty = Ptr->getType();
1322   assert(Ty->isPointerTy() && "Unexpected non-ptr");
1323 
1324   if (isa<ScalableVectorType>(AccessTy)) {
1325     LLVM_DEBUG(dbgs() << "LAA: Bad stride - Scalable object: " << *AccessTy
1326                       << "\n");
1327     return 0;
1328   }
1329 
1330   const SCEV *PtrScev = replaceSymbolicStrideSCEV(PSE, StridesMap, Ptr);
1331 
1332   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev);
1333   if (Assume && !AR)
1334     AR = PSE.getAsAddRec(Ptr);
1335 
1336   if (!AR) {
1337     LLVM_DEBUG(dbgs() << "LAA: Bad stride - Not an AddRecExpr pointer " << *Ptr
1338                       << " SCEV: " << *PtrScev << "\n");
1339     return 0;
1340   }
1341 
1342   // The access function must stride over the innermost loop.
1343   if (Lp != AR->getLoop()) {
1344     LLVM_DEBUG(dbgs() << "LAA: Bad stride - Not striding over innermost loop "
1345                       << *Ptr << " SCEV: " << *AR << "\n");
1346     return 0;
1347   }
1348 
1349   // The address calculation must not wrap. Otherwise, a dependence could be
1350   // inverted.
1351   // An inbounds getelementptr that is a AddRec with a unit stride
1352   // cannot wrap per definition. The unit stride requirement is checked later.
1353   // An getelementptr without an inbounds attribute and unit stride would have
1354   // to access the pointer value "0" which is undefined behavior in address
1355   // space 0, therefore we can also vectorize this case.
1356   unsigned AddrSpace = Ty->getPointerAddressSpace();
1357   bool IsInBoundsGEP = isInBoundsGep(Ptr);
1358   bool IsNoWrapAddRec = !ShouldCheckWrap ||
1359     PSE.hasNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW) ||
1360     isNoWrapAddRec(Ptr, AR, PSE, Lp);
1361   if (!IsNoWrapAddRec && !IsInBoundsGEP &&
1362       NullPointerIsDefined(Lp->getHeader()->getParent(), AddrSpace)) {
1363     if (Assume) {
1364       PSE.setNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW);
1365       IsNoWrapAddRec = true;
1366       LLVM_DEBUG(dbgs() << "LAA: Pointer may wrap in the address space:\n"
1367                         << "LAA:   Pointer: " << *Ptr << "\n"
1368                         << "LAA:   SCEV: " << *AR << "\n"
1369                         << "LAA:   Added an overflow assumption\n");
1370     } else {
1371       LLVM_DEBUG(
1372           dbgs() << "LAA: Bad stride - Pointer may wrap in the address space "
1373                  << *Ptr << " SCEV: " << *AR << "\n");
1374       return 0;
1375     }
1376   }
1377 
1378   // Check the step is constant.
1379   const SCEV *Step = AR->getStepRecurrence(*PSE.getSE());
1380 
1381   // Calculate the pointer stride and check if it is constant.
1382   const SCEVConstant *C = dyn_cast<SCEVConstant>(Step);
1383   if (!C) {
1384     LLVM_DEBUG(dbgs() << "LAA: Bad stride - Not a constant strided " << *Ptr
1385                       << " SCEV: " << *AR << "\n");
1386     return 0;
1387   }
1388 
1389   auto &DL = Lp->getHeader()->getModule()->getDataLayout();
1390   TypeSize AllocSize = DL.getTypeAllocSize(AccessTy);
1391   int64_t Size = AllocSize.getFixedSize();
1392   const APInt &APStepVal = C->getAPInt();
1393 
1394   // Huge step value - give up.
1395   if (APStepVal.getBitWidth() > 64)
1396     return 0;
1397 
1398   int64_t StepVal = APStepVal.getSExtValue();
1399 
1400   // Strided access.
1401   int64_t Stride = StepVal / Size;
1402   int64_t Rem = StepVal % Size;
1403   if (Rem)
1404     return 0;
1405 
1406   // If the SCEV could wrap but we have an inbounds gep with a unit stride we
1407   // know we can't "wrap around the address space". In case of address space
1408   // zero we know that this won't happen without triggering undefined behavior.
1409   if (!IsNoWrapAddRec && Stride != 1 && Stride != -1 &&
1410       (IsInBoundsGEP || !NullPointerIsDefined(Lp->getHeader()->getParent(),
1411                                               AddrSpace))) {
1412     if (Assume) {
1413       // We can avoid this case by adding a run-time check.
1414       LLVM_DEBUG(dbgs() << "LAA: Non unit strided pointer which is not either "
1415                         << "inbounds or in address space 0 may wrap:\n"
1416                         << "LAA:   Pointer: " << *Ptr << "\n"
1417                         << "LAA:   SCEV: " << *AR << "\n"
1418                         << "LAA:   Added an overflow assumption\n");
1419       PSE.setNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW);
1420     } else
1421       return 0;
1422   }
1423 
1424   return Stride;
1425 }
1426 
1427 Optional<int> llvm::getPointersDiff(Type *ElemTyA, Value *PtrA, Type *ElemTyB,
1428                                     Value *PtrB, const DataLayout &DL,
1429                                     ScalarEvolution &SE, bool StrictCheck,
1430                                     bool CheckType) {
1431   assert(PtrA && PtrB && "Expected non-nullptr pointers.");
1432   assert(cast<PointerType>(PtrA->getType())
1433              ->isOpaqueOrPointeeTypeMatches(ElemTyA) && "Wrong PtrA type");
1434   assert(cast<PointerType>(PtrB->getType())
1435              ->isOpaqueOrPointeeTypeMatches(ElemTyB) && "Wrong PtrB type");
1436 
1437   // Make sure that A and B are different pointers.
1438   if (PtrA == PtrB)
1439     return 0;
1440 
1441   // Make sure that the element types are the same if required.
1442   if (CheckType && ElemTyA != ElemTyB)
1443     return None;
1444 
1445   unsigned ASA = PtrA->getType()->getPointerAddressSpace();
1446   unsigned ASB = PtrB->getType()->getPointerAddressSpace();
1447 
1448   // Check that the address spaces match.
1449   if (ASA != ASB)
1450     return None;
1451   unsigned IdxWidth = DL.getIndexSizeInBits(ASA);
1452 
1453   APInt OffsetA(IdxWidth, 0), OffsetB(IdxWidth, 0);
1454   Value *PtrA1 = PtrA->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetA);
1455   Value *PtrB1 = PtrB->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetB);
1456 
1457   int Val;
1458   if (PtrA1 == PtrB1) {
1459     // Retrieve the address space again as pointer stripping now tracks through
1460     // `addrspacecast`.
1461     ASA = cast<PointerType>(PtrA1->getType())->getAddressSpace();
1462     ASB = cast<PointerType>(PtrB1->getType())->getAddressSpace();
1463     // Check that the address spaces match and that the pointers are valid.
1464     if (ASA != ASB)
1465       return None;
1466 
1467     IdxWidth = DL.getIndexSizeInBits(ASA);
1468     OffsetA = OffsetA.sextOrTrunc(IdxWidth);
1469     OffsetB = OffsetB.sextOrTrunc(IdxWidth);
1470 
1471     OffsetB -= OffsetA;
1472     Val = OffsetB.getSExtValue();
1473   } else {
1474     // Otherwise compute the distance with SCEV between the base pointers.
1475     const SCEV *PtrSCEVA = SE.getSCEV(PtrA);
1476     const SCEV *PtrSCEVB = SE.getSCEV(PtrB);
1477     const auto *Diff =
1478         dyn_cast<SCEVConstant>(SE.getMinusSCEV(PtrSCEVB, PtrSCEVA));
1479     if (!Diff)
1480       return None;
1481     Val = Diff->getAPInt().getSExtValue();
1482   }
1483   int Size = DL.getTypeStoreSize(ElemTyA);
1484   int Dist = Val / Size;
1485 
1486   // Ensure that the calculated distance matches the type-based one after all
1487   // the bitcasts removal in the provided pointers.
1488   if (!StrictCheck || Dist * Size == Val)
1489     return Dist;
1490   return None;
1491 }
1492 
1493 bool llvm::sortPtrAccesses(ArrayRef<Value *> VL, Type *ElemTy,
1494                            const DataLayout &DL, ScalarEvolution &SE,
1495                            SmallVectorImpl<unsigned> &SortedIndices) {
1496   assert(llvm::all_of(
1497              VL, [](const Value *V) { return V->getType()->isPointerTy(); }) &&
1498          "Expected list of pointer operands.");
1499   // Walk over the pointers, and map each of them to an offset relative to
1500   // first pointer in the array.
1501   Value *Ptr0 = VL[0];
1502 
1503   using DistOrdPair = std::pair<int64_t, int>;
1504   auto Compare = llvm::less_first();
1505   std::set<DistOrdPair, decltype(Compare)> Offsets(Compare);
1506   Offsets.emplace(0, 0);
1507   int Cnt = 1;
1508   bool IsConsecutive = true;
1509   for (auto *Ptr : VL.drop_front()) {
1510     Optional<int> Diff = getPointersDiff(ElemTy, Ptr0, ElemTy, Ptr, DL, SE,
1511                                          /*StrictCheck=*/true);
1512     if (!Diff)
1513       return false;
1514 
1515     // Check if the pointer with the same offset is found.
1516     int64_t Offset = *Diff;
1517     auto Res = Offsets.emplace(Offset, Cnt);
1518     if (!Res.second)
1519       return false;
1520     // Consecutive order if the inserted element is the last one.
1521     IsConsecutive = IsConsecutive && std::next(Res.first) == Offsets.end();
1522     ++Cnt;
1523   }
1524   SortedIndices.clear();
1525   if (!IsConsecutive) {
1526     // Fill SortedIndices array only if it is non-consecutive.
1527     SortedIndices.resize(VL.size());
1528     Cnt = 0;
1529     for (const std::pair<int64_t, int> &Pair : Offsets) {
1530       SortedIndices[Cnt] = Pair.second;
1531       ++Cnt;
1532     }
1533   }
1534   return true;
1535 }
1536 
1537 /// Returns true if the memory operations \p A and \p B are consecutive.
1538 bool llvm::isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL,
1539                                ScalarEvolution &SE, bool CheckType) {
1540   Value *PtrA = getLoadStorePointerOperand(A);
1541   Value *PtrB = getLoadStorePointerOperand(B);
1542   if (!PtrA || !PtrB)
1543     return false;
1544   Type *ElemTyA = getLoadStoreType(A);
1545   Type *ElemTyB = getLoadStoreType(B);
1546   Optional<int> Diff = getPointersDiff(ElemTyA, PtrA, ElemTyB, PtrB, DL, SE,
1547                                        /*StrictCheck=*/true, CheckType);
1548   return Diff && *Diff == 1;
1549 }
1550 
1551 void MemoryDepChecker::addAccess(StoreInst *SI) {
1552   visitPointers(SI->getPointerOperand(), *InnermostLoop,
1553                 [this, SI](Value *Ptr) {
1554                   Accesses[MemAccessInfo(Ptr, true)].push_back(AccessIdx);
1555                   InstMap.push_back(SI);
1556                   ++AccessIdx;
1557                 });
1558 }
1559 
1560 void MemoryDepChecker::addAccess(LoadInst *LI) {
1561   visitPointers(LI->getPointerOperand(), *InnermostLoop,
1562                 [this, LI](Value *Ptr) {
1563                   Accesses[MemAccessInfo(Ptr, false)].push_back(AccessIdx);
1564                   InstMap.push_back(LI);
1565                   ++AccessIdx;
1566                 });
1567 }
1568 
1569 MemoryDepChecker::VectorizationSafetyStatus
1570 MemoryDepChecker::Dependence::isSafeForVectorization(DepType Type) {
1571   switch (Type) {
1572   case NoDep:
1573   case Forward:
1574   case BackwardVectorizable:
1575     return VectorizationSafetyStatus::Safe;
1576 
1577   case Unknown:
1578     return VectorizationSafetyStatus::PossiblySafeWithRtChecks;
1579   case ForwardButPreventsForwarding:
1580   case Backward:
1581   case BackwardVectorizableButPreventsForwarding:
1582     return VectorizationSafetyStatus::Unsafe;
1583   }
1584   llvm_unreachable("unexpected DepType!");
1585 }
1586 
1587 bool MemoryDepChecker::Dependence::isBackward() const {
1588   switch (Type) {
1589   case NoDep:
1590   case Forward:
1591   case ForwardButPreventsForwarding:
1592   case Unknown:
1593     return false;
1594 
1595   case BackwardVectorizable:
1596   case Backward:
1597   case BackwardVectorizableButPreventsForwarding:
1598     return true;
1599   }
1600   llvm_unreachable("unexpected DepType!");
1601 }
1602 
1603 bool MemoryDepChecker::Dependence::isPossiblyBackward() const {
1604   return isBackward() || Type == Unknown;
1605 }
1606 
1607 bool MemoryDepChecker::Dependence::isForward() const {
1608   switch (Type) {
1609   case Forward:
1610   case ForwardButPreventsForwarding:
1611     return true;
1612 
1613   case NoDep:
1614   case Unknown:
1615   case BackwardVectorizable:
1616   case Backward:
1617   case BackwardVectorizableButPreventsForwarding:
1618     return false;
1619   }
1620   llvm_unreachable("unexpected DepType!");
1621 }
1622 
1623 bool MemoryDepChecker::couldPreventStoreLoadForward(uint64_t Distance,
1624                                                     uint64_t TypeByteSize) {
1625   // If loads occur at a distance that is not a multiple of a feasible vector
1626   // factor store-load forwarding does not take place.
1627   // Positive dependences might cause troubles because vectorizing them might
1628   // prevent store-load forwarding making vectorized code run a lot slower.
1629   //   a[i] = a[i-3] ^ a[i-8];
1630   //   The stores to a[i:i+1] don't align with the stores to a[i-3:i-2] and
1631   //   hence on your typical architecture store-load forwarding does not take
1632   //   place. Vectorizing in such cases does not make sense.
1633   // Store-load forwarding distance.
1634 
1635   // After this many iterations store-to-load forwarding conflicts should not
1636   // cause any slowdowns.
1637   const uint64_t NumItersForStoreLoadThroughMemory = 8 * TypeByteSize;
1638   // Maximum vector factor.
1639   uint64_t MaxVFWithoutSLForwardIssues = std::min(
1640       VectorizerParams::MaxVectorWidth * TypeByteSize, MaxSafeDepDistBytes);
1641 
1642   // Compute the smallest VF at which the store and load would be misaligned.
1643   for (uint64_t VF = 2 * TypeByteSize; VF <= MaxVFWithoutSLForwardIssues;
1644        VF *= 2) {
1645     // If the number of vector iteration between the store and the load are
1646     // small we could incur conflicts.
1647     if (Distance % VF && Distance / VF < NumItersForStoreLoadThroughMemory) {
1648       MaxVFWithoutSLForwardIssues = (VF >> 1);
1649       break;
1650     }
1651   }
1652 
1653   if (MaxVFWithoutSLForwardIssues < 2 * TypeByteSize) {
1654     LLVM_DEBUG(
1655         dbgs() << "LAA: Distance " << Distance
1656                << " that could cause a store-load forwarding conflict\n");
1657     return true;
1658   }
1659 
1660   if (MaxVFWithoutSLForwardIssues < MaxSafeDepDistBytes &&
1661       MaxVFWithoutSLForwardIssues !=
1662           VectorizerParams::MaxVectorWidth * TypeByteSize)
1663     MaxSafeDepDistBytes = MaxVFWithoutSLForwardIssues;
1664   return false;
1665 }
1666 
1667 void MemoryDepChecker::mergeInStatus(VectorizationSafetyStatus S) {
1668   if (Status < S)
1669     Status = S;
1670 }
1671 
1672 /// Given a non-constant (unknown) dependence-distance \p Dist between two
1673 /// memory accesses, that have the same stride whose absolute value is given
1674 /// in \p Stride, and that have the same type size \p TypeByteSize,
1675 /// in a loop whose takenCount is \p BackedgeTakenCount, check if it is
1676 /// possible to prove statically that the dependence distance is larger
1677 /// than the range that the accesses will travel through the execution of
1678 /// the loop. If so, return true; false otherwise. This is useful for
1679 /// example in loops such as the following (PR31098):
1680 ///     for (i = 0; i < D; ++i) {
1681 ///                = out[i];
1682 ///       out[i+D] =
1683 ///     }
1684 static bool isSafeDependenceDistance(const DataLayout &DL, ScalarEvolution &SE,
1685                                      const SCEV &BackedgeTakenCount,
1686                                      const SCEV &Dist, uint64_t Stride,
1687                                      uint64_t TypeByteSize) {
1688 
1689   // If we can prove that
1690   //      (**) |Dist| > BackedgeTakenCount * Step
1691   // where Step is the absolute stride of the memory accesses in bytes,
1692   // then there is no dependence.
1693   //
1694   // Rationale:
1695   // We basically want to check if the absolute distance (|Dist/Step|)
1696   // is >= the loop iteration count (or > BackedgeTakenCount).
1697   // This is equivalent to the Strong SIV Test (Practical Dependence Testing,
1698   // Section 4.2.1); Note, that for vectorization it is sufficient to prove
1699   // that the dependence distance is >= VF; This is checked elsewhere.
1700   // But in some cases we can prune unknown dependence distances early, and
1701   // even before selecting the VF, and without a runtime test, by comparing
1702   // the distance against the loop iteration count. Since the vectorized code
1703   // will be executed only if LoopCount >= VF, proving distance >= LoopCount
1704   // also guarantees that distance >= VF.
1705   //
1706   const uint64_t ByteStride = Stride * TypeByteSize;
1707   const SCEV *Step = SE.getConstant(BackedgeTakenCount.getType(), ByteStride);
1708   const SCEV *Product = SE.getMulExpr(&BackedgeTakenCount, Step);
1709 
1710   const SCEV *CastedDist = &Dist;
1711   const SCEV *CastedProduct = Product;
1712   uint64_t DistTypeSizeBits = DL.getTypeSizeInBits(Dist.getType());
1713   uint64_t ProductTypeSizeBits = DL.getTypeSizeInBits(Product->getType());
1714 
1715   // The dependence distance can be positive/negative, so we sign extend Dist;
1716   // The multiplication of the absolute stride in bytes and the
1717   // backedgeTakenCount is non-negative, so we zero extend Product.
1718   if (DistTypeSizeBits > ProductTypeSizeBits)
1719     CastedProduct = SE.getZeroExtendExpr(Product, Dist.getType());
1720   else
1721     CastedDist = SE.getNoopOrSignExtend(&Dist, Product->getType());
1722 
1723   // Is  Dist - (BackedgeTakenCount * Step) > 0 ?
1724   // (If so, then we have proven (**) because |Dist| >= Dist)
1725   const SCEV *Minus = SE.getMinusSCEV(CastedDist, CastedProduct);
1726   if (SE.isKnownPositive(Minus))
1727     return true;
1728 
1729   // Second try: Is  -Dist - (BackedgeTakenCount * Step) > 0 ?
1730   // (If so, then we have proven (**) because |Dist| >= -1*Dist)
1731   const SCEV *NegDist = SE.getNegativeSCEV(CastedDist);
1732   Minus = SE.getMinusSCEV(NegDist, CastedProduct);
1733   if (SE.isKnownPositive(Minus))
1734     return true;
1735 
1736   return false;
1737 }
1738 
1739 /// Check the dependence for two accesses with the same stride \p Stride.
1740 /// \p Distance is the positive distance and \p TypeByteSize is type size in
1741 /// bytes.
1742 ///
1743 /// \returns true if they are independent.
1744 static bool areStridedAccessesIndependent(uint64_t Distance, uint64_t Stride,
1745                                           uint64_t TypeByteSize) {
1746   assert(Stride > 1 && "The stride must be greater than 1");
1747   assert(TypeByteSize > 0 && "The type size in byte must be non-zero");
1748   assert(Distance > 0 && "The distance must be non-zero");
1749 
1750   // Skip if the distance is not multiple of type byte size.
1751   if (Distance % TypeByteSize)
1752     return false;
1753 
1754   uint64_t ScaledDist = Distance / TypeByteSize;
1755 
1756   // No dependence if the scaled distance is not multiple of the stride.
1757   // E.g.
1758   //      for (i = 0; i < 1024 ; i += 4)
1759   //        A[i+2] = A[i] + 1;
1760   //
1761   // Two accesses in memory (scaled distance is 2, stride is 4):
1762   //     | A[0] |      |      |      | A[4] |      |      |      |
1763   //     |      |      | A[2] |      |      |      | A[6] |      |
1764   //
1765   // E.g.
1766   //      for (i = 0; i < 1024 ; i += 3)
1767   //        A[i+4] = A[i] + 1;
1768   //
1769   // Two accesses in memory (scaled distance is 4, stride is 3):
1770   //     | A[0] |      |      | A[3] |      |      | A[6] |      |      |
1771   //     |      |      |      |      | A[4] |      |      | A[7] |      |
1772   return ScaledDist % Stride;
1773 }
1774 
1775 MemoryDepChecker::Dependence::DepType
1776 MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
1777                               const MemAccessInfo &B, unsigned BIdx,
1778                               const ValueToValueMap &Strides) {
1779   assert (AIdx < BIdx && "Must pass arguments in program order");
1780 
1781   Value *APtr = A.getPointer();
1782   Value *BPtr = B.getPointer();
1783   bool AIsWrite = A.getInt();
1784   bool BIsWrite = B.getInt();
1785   Type *ATy = getLoadStoreType(InstMap[AIdx]);
1786   Type *BTy = getLoadStoreType(InstMap[BIdx]);
1787 
1788   // Two reads are independent.
1789   if (!AIsWrite && !BIsWrite)
1790     return Dependence::NoDep;
1791 
1792   // We cannot check pointers in different address spaces.
1793   if (APtr->getType()->getPointerAddressSpace() !=
1794       BPtr->getType()->getPointerAddressSpace())
1795     return Dependence::Unknown;
1796 
1797   int64_t StrideAPtr =
1798       getPtrStride(PSE, ATy, APtr, InnermostLoop, Strides, true);
1799   int64_t StrideBPtr =
1800       getPtrStride(PSE, BTy, BPtr, InnermostLoop, Strides, true);
1801 
1802   const SCEV *Src = PSE.getSCEV(APtr);
1803   const SCEV *Sink = PSE.getSCEV(BPtr);
1804 
1805   // If the induction step is negative we have to invert source and sink of the
1806   // dependence.
1807   if (StrideAPtr < 0) {
1808     std::swap(APtr, BPtr);
1809     std::swap(ATy, BTy);
1810     std::swap(Src, Sink);
1811     std::swap(AIsWrite, BIsWrite);
1812     std::swap(AIdx, BIdx);
1813     std::swap(StrideAPtr, StrideBPtr);
1814   }
1815 
1816   const SCEV *Dist = PSE.getSE()->getMinusSCEV(Sink, Src);
1817 
1818   LLVM_DEBUG(dbgs() << "LAA: Src Scev: " << *Src << "Sink Scev: " << *Sink
1819                     << "(Induction step: " << StrideAPtr << ")\n");
1820   LLVM_DEBUG(dbgs() << "LAA: Distance for " << *InstMap[AIdx] << " to "
1821                     << *InstMap[BIdx] << ": " << *Dist << "\n");
1822 
1823   // Need accesses with constant stride. We don't want to vectorize
1824   // "A[B[i]] += ..." and similar code or pointer arithmetic that could wrap in
1825   // the address space.
1826   if (!StrideAPtr || !StrideBPtr || StrideAPtr != StrideBPtr){
1827     LLVM_DEBUG(dbgs() << "Pointer access with non-constant stride\n");
1828     return Dependence::Unknown;
1829   }
1830 
1831   auto &DL = InnermostLoop->getHeader()->getModule()->getDataLayout();
1832   uint64_t TypeByteSize = DL.getTypeAllocSize(ATy);
1833   bool HasSameSize =
1834       DL.getTypeStoreSizeInBits(ATy) == DL.getTypeStoreSizeInBits(BTy);
1835   uint64_t Stride = std::abs(StrideAPtr);
1836   const SCEVConstant *C = dyn_cast<SCEVConstant>(Dist);
1837   if (!C) {
1838     if (!isa<SCEVCouldNotCompute>(Dist) && HasSameSize &&
1839         isSafeDependenceDistance(DL, *(PSE.getSE()),
1840                                  *(PSE.getBackedgeTakenCount()), *Dist, Stride,
1841                                  TypeByteSize))
1842       return Dependence::NoDep;
1843 
1844     LLVM_DEBUG(dbgs() << "LAA: Dependence because of non-constant distance\n");
1845     FoundNonConstantDistanceDependence = true;
1846     return Dependence::Unknown;
1847   }
1848 
1849   const APInt &Val = C->getAPInt();
1850   int64_t Distance = Val.getSExtValue();
1851 
1852   // Attempt to prove strided accesses independent.
1853   if (std::abs(Distance) > 0 && Stride > 1 && HasSameSize &&
1854       areStridedAccessesIndependent(std::abs(Distance), Stride, TypeByteSize)) {
1855     LLVM_DEBUG(dbgs() << "LAA: Strided accesses are independent\n");
1856     return Dependence::NoDep;
1857   }
1858 
1859   // Negative distances are not plausible dependencies.
1860   if (Val.isNegative()) {
1861     bool IsTrueDataDependence = (AIsWrite && !BIsWrite);
1862     if (IsTrueDataDependence && EnableForwardingConflictDetection &&
1863         (couldPreventStoreLoadForward(Val.abs().getZExtValue(), TypeByteSize) ||
1864          !HasSameSize)) {
1865       LLVM_DEBUG(dbgs() << "LAA: Forward but may prevent st->ld forwarding\n");
1866       return Dependence::ForwardButPreventsForwarding;
1867     }
1868 
1869     LLVM_DEBUG(dbgs() << "LAA: Dependence is negative\n");
1870     return Dependence::Forward;
1871   }
1872 
1873   // Write to the same location with the same size.
1874   if (Val == 0) {
1875     if (HasSameSize)
1876       return Dependence::Forward;
1877     LLVM_DEBUG(
1878         dbgs() << "LAA: Zero dependence difference but different type sizes\n");
1879     return Dependence::Unknown;
1880   }
1881 
1882   assert(Val.isStrictlyPositive() && "Expect a positive value");
1883 
1884   if (!HasSameSize) {
1885     LLVM_DEBUG(dbgs() << "LAA: ReadWrite-Write positive dependency with "
1886                          "different type sizes\n");
1887     return Dependence::Unknown;
1888   }
1889 
1890   // Bail out early if passed-in parameters make vectorization not feasible.
1891   unsigned ForcedFactor = (VectorizerParams::VectorizationFactor ?
1892                            VectorizerParams::VectorizationFactor : 1);
1893   unsigned ForcedUnroll = (VectorizerParams::VectorizationInterleave ?
1894                            VectorizerParams::VectorizationInterleave : 1);
1895   // The minimum number of iterations for a vectorized/unrolled version.
1896   unsigned MinNumIter = std::max(ForcedFactor * ForcedUnroll, 2U);
1897 
1898   // It's not vectorizable if the distance is smaller than the minimum distance
1899   // needed for a vectroized/unrolled version. Vectorizing one iteration in
1900   // front needs TypeByteSize * Stride. Vectorizing the last iteration needs
1901   // TypeByteSize (No need to plus the last gap distance).
1902   //
1903   // E.g. Assume one char is 1 byte in memory and one int is 4 bytes.
1904   //      foo(int *A) {
1905   //        int *B = (int *)((char *)A + 14);
1906   //        for (i = 0 ; i < 1024 ; i += 2)
1907   //          B[i] = A[i] + 1;
1908   //      }
1909   //
1910   // Two accesses in memory (stride is 2):
1911   //     | A[0] |      | A[2] |      | A[4] |      | A[6] |      |
1912   //                              | B[0] |      | B[2] |      | B[4] |
1913   //
1914   // Distance needs for vectorizing iterations except the last iteration:
1915   // 4 * 2 * (MinNumIter - 1). Distance needs for the last iteration: 4.
1916   // So the minimum distance needed is: 4 * 2 * (MinNumIter - 1) + 4.
1917   //
1918   // If MinNumIter is 2, it is vectorizable as the minimum distance needed is
1919   // 12, which is less than distance.
1920   //
1921   // If MinNumIter is 4 (Say if a user forces the vectorization factor to be 4),
1922   // the minimum distance needed is 28, which is greater than distance. It is
1923   // not safe to do vectorization.
1924   uint64_t MinDistanceNeeded =
1925       TypeByteSize * Stride * (MinNumIter - 1) + TypeByteSize;
1926   if (MinDistanceNeeded > static_cast<uint64_t>(Distance)) {
1927     LLVM_DEBUG(dbgs() << "LAA: Failure because of positive distance "
1928                       << Distance << '\n');
1929     return Dependence::Backward;
1930   }
1931 
1932   // Unsafe if the minimum distance needed is greater than max safe distance.
1933   if (MinDistanceNeeded > MaxSafeDepDistBytes) {
1934     LLVM_DEBUG(dbgs() << "LAA: Failure because it needs at least "
1935                       << MinDistanceNeeded << " size in bytes");
1936     return Dependence::Backward;
1937   }
1938 
1939   // Positive distance bigger than max vectorization factor.
1940   // FIXME: Should use max factor instead of max distance in bytes, which could
1941   // not handle different types.
1942   // E.g. Assume one char is 1 byte in memory and one int is 4 bytes.
1943   //      void foo (int *A, char *B) {
1944   //        for (unsigned i = 0; i < 1024; i++) {
1945   //          A[i+2] = A[i] + 1;
1946   //          B[i+2] = B[i] + 1;
1947   //        }
1948   //      }
1949   //
1950   // This case is currently unsafe according to the max safe distance. If we
1951   // analyze the two accesses on array B, the max safe dependence distance
1952   // is 2. Then we analyze the accesses on array A, the minimum distance needed
1953   // is 8, which is less than 2 and forbidden vectorization, But actually
1954   // both A and B could be vectorized by 2 iterations.
1955   MaxSafeDepDistBytes =
1956       std::min(static_cast<uint64_t>(Distance), MaxSafeDepDistBytes);
1957 
1958   bool IsTrueDataDependence = (!AIsWrite && BIsWrite);
1959   if (IsTrueDataDependence && EnableForwardingConflictDetection &&
1960       couldPreventStoreLoadForward(Distance, TypeByteSize))
1961     return Dependence::BackwardVectorizableButPreventsForwarding;
1962 
1963   uint64_t MaxVF = MaxSafeDepDistBytes / (TypeByteSize * Stride);
1964   LLVM_DEBUG(dbgs() << "LAA: Positive distance " << Val.getSExtValue()
1965                     << " with max VF = " << MaxVF << '\n');
1966   uint64_t MaxVFInBits = MaxVF * TypeByteSize * 8;
1967   MaxSafeVectorWidthInBits = std::min(MaxSafeVectorWidthInBits, MaxVFInBits);
1968   return Dependence::BackwardVectorizable;
1969 }
1970 
1971 bool MemoryDepChecker::areDepsSafe(DepCandidates &AccessSets,
1972                                    MemAccessInfoList &CheckDeps,
1973                                    const ValueToValueMap &Strides) {
1974 
1975   MaxSafeDepDistBytes = -1;
1976   SmallPtrSet<MemAccessInfo, 8> Visited;
1977   for (MemAccessInfo CurAccess : CheckDeps) {
1978     if (Visited.count(CurAccess))
1979       continue;
1980 
1981     // Get the relevant memory access set.
1982     EquivalenceClasses<MemAccessInfo>::iterator I =
1983       AccessSets.findValue(AccessSets.getLeaderValue(CurAccess));
1984 
1985     // Check accesses within this set.
1986     EquivalenceClasses<MemAccessInfo>::member_iterator AI =
1987         AccessSets.member_begin(I);
1988     EquivalenceClasses<MemAccessInfo>::member_iterator AE =
1989         AccessSets.member_end();
1990 
1991     // Check every access pair.
1992     while (AI != AE) {
1993       Visited.insert(*AI);
1994       bool AIIsWrite = AI->getInt();
1995       // Check loads only against next equivalent class, but stores also against
1996       // other stores in the same equivalence class - to the same address.
1997       EquivalenceClasses<MemAccessInfo>::member_iterator OI =
1998           (AIIsWrite ? AI : std::next(AI));
1999       while (OI != AE) {
2000         // Check every accessing instruction pair in program order.
2001         for (std::vector<unsigned>::iterator I1 = Accesses[*AI].begin(),
2002              I1E = Accesses[*AI].end(); I1 != I1E; ++I1)
2003           // Scan all accesses of another equivalence class, but only the next
2004           // accesses of the same equivalent class.
2005           for (std::vector<unsigned>::iterator
2006                    I2 = (OI == AI ? std::next(I1) : Accesses[*OI].begin()),
2007                    I2E = (OI == AI ? I1E : Accesses[*OI].end());
2008                I2 != I2E; ++I2) {
2009             auto A = std::make_pair(&*AI, *I1);
2010             auto B = std::make_pair(&*OI, *I2);
2011 
2012             assert(*I1 != *I2);
2013             if (*I1 > *I2)
2014               std::swap(A, B);
2015 
2016             Dependence::DepType Type =
2017                 isDependent(*A.first, A.second, *B.first, B.second, Strides);
2018             mergeInStatus(Dependence::isSafeForVectorization(Type));
2019 
2020             // Gather dependences unless we accumulated MaxDependences
2021             // dependences.  In that case return as soon as we find the first
2022             // unsafe dependence.  This puts a limit on this quadratic
2023             // algorithm.
2024             if (RecordDependences) {
2025               if (Type != Dependence::NoDep)
2026                 Dependences.push_back(Dependence(A.second, B.second, Type));
2027 
2028               if (Dependences.size() >= MaxDependences) {
2029                 RecordDependences = false;
2030                 Dependences.clear();
2031                 LLVM_DEBUG(dbgs()
2032                            << "Too many dependences, stopped recording\n");
2033               }
2034             }
2035             if (!RecordDependences && !isSafeForVectorization())
2036               return false;
2037           }
2038         ++OI;
2039       }
2040       AI++;
2041     }
2042   }
2043 
2044   LLVM_DEBUG(dbgs() << "Total Dependences: " << Dependences.size() << "\n");
2045   return isSafeForVectorization();
2046 }
2047 
2048 SmallVector<Instruction *, 4>
2049 MemoryDepChecker::getInstructionsForAccess(Value *Ptr, bool isWrite) const {
2050   MemAccessInfo Access(Ptr, isWrite);
2051   auto &IndexVector = Accesses.find(Access)->second;
2052 
2053   SmallVector<Instruction *, 4> Insts;
2054   transform(IndexVector,
2055                  std::back_inserter(Insts),
2056                  [&](unsigned Idx) { return this->InstMap[Idx]; });
2057   return Insts;
2058 }
2059 
2060 const char *MemoryDepChecker::Dependence::DepName[] = {
2061     "NoDep", "Unknown", "Forward", "ForwardButPreventsForwarding", "Backward",
2062     "BackwardVectorizable", "BackwardVectorizableButPreventsForwarding"};
2063 
2064 void MemoryDepChecker::Dependence::print(
2065     raw_ostream &OS, unsigned Depth,
2066     const SmallVectorImpl<Instruction *> &Instrs) const {
2067   OS.indent(Depth) << DepName[Type] << ":\n";
2068   OS.indent(Depth + 2) << *Instrs[Source] << " -> \n";
2069   OS.indent(Depth + 2) << *Instrs[Destination] << "\n";
2070 }
2071 
2072 bool LoopAccessInfo::canAnalyzeLoop() {
2073   // We need to have a loop header.
2074   LLVM_DEBUG(dbgs() << "LAA: Found a loop in "
2075                     << TheLoop->getHeader()->getParent()->getName() << ": "
2076                     << TheLoop->getHeader()->getName() << '\n');
2077 
2078   // We can only analyze innermost loops.
2079   if (!TheLoop->isInnermost()) {
2080     LLVM_DEBUG(dbgs() << "LAA: loop is not the innermost loop\n");
2081     recordAnalysis("NotInnerMostLoop") << "loop is not the innermost loop";
2082     return false;
2083   }
2084 
2085   // We must have a single backedge.
2086   if (TheLoop->getNumBackEdges() != 1) {
2087     LLVM_DEBUG(
2088         dbgs() << "LAA: loop control flow is not understood by analyzer\n");
2089     recordAnalysis("CFGNotUnderstood")
2090         << "loop control flow is not understood by analyzer";
2091     return false;
2092   }
2093 
2094   // ScalarEvolution needs to be able to find the exit count.
2095   const SCEV *ExitCount = PSE->getBackedgeTakenCount();
2096   if (isa<SCEVCouldNotCompute>(ExitCount)) {
2097     recordAnalysis("CantComputeNumberOfIterations")
2098         << "could not determine number of loop iterations";
2099     LLVM_DEBUG(dbgs() << "LAA: SCEV could not compute the loop exit count.\n");
2100     return false;
2101   }
2102 
2103   return true;
2104 }
2105 
2106 void LoopAccessInfo::analyzeLoop(AAResults *AA, LoopInfo *LI,
2107                                  const TargetLibraryInfo *TLI,
2108                                  DominatorTree *DT) {
2109   // Holds the Load and Store instructions.
2110   SmallVector<LoadInst *, 16> Loads;
2111   SmallVector<StoreInst *, 16> Stores;
2112 
2113   // Holds all the different accesses in the loop.
2114   unsigned NumReads = 0;
2115   unsigned NumReadWrites = 0;
2116 
2117   bool HasComplexMemInst = false;
2118 
2119   // A runtime check is only legal to insert if there are no convergent calls.
2120   HasConvergentOp = false;
2121 
2122   PtrRtChecking->Pointers.clear();
2123   PtrRtChecking->Need = false;
2124 
2125   const bool IsAnnotatedParallel = TheLoop->isAnnotatedParallel();
2126 
2127   const bool EnableMemAccessVersioningOfLoop =
2128       EnableMemAccessVersioning &&
2129       !TheLoop->getHeader()->getParent()->hasOptSize();
2130 
2131   // For each block.
2132   for (BasicBlock *BB : TheLoop->blocks()) {
2133     // Scan the BB and collect legal loads and stores. Also detect any
2134     // convergent instructions.
2135     for (Instruction &I : *BB) {
2136       if (auto *Call = dyn_cast<CallBase>(&I)) {
2137         if (Call->isConvergent())
2138           HasConvergentOp = true;
2139       }
2140 
2141       // With both a non-vectorizable memory instruction and a convergent
2142       // operation, found in this loop, no reason to continue the search.
2143       if (HasComplexMemInst && HasConvergentOp) {
2144         CanVecMem = false;
2145         return;
2146       }
2147 
2148       // Avoid hitting recordAnalysis multiple times.
2149       if (HasComplexMemInst)
2150         continue;
2151 
2152       // If this is a load, save it. If this instruction can read from memory
2153       // but is not a load, then we quit. Notice that we don't handle function
2154       // calls that read or write.
2155       if (I.mayReadFromMemory()) {
2156         // Many math library functions read the rounding mode. We will only
2157         // vectorize a loop if it contains known function calls that don't set
2158         // the flag. Therefore, it is safe to ignore this read from memory.
2159         auto *Call = dyn_cast<CallInst>(&I);
2160         if (Call && getVectorIntrinsicIDForCall(Call, TLI))
2161           continue;
2162 
2163         // If the function has an explicit vectorized counterpart, we can safely
2164         // assume that it can be vectorized.
2165         if (Call && !Call->isNoBuiltin() && Call->getCalledFunction() &&
2166             !VFDatabase::getMappings(*Call).empty())
2167           continue;
2168 
2169         auto *Ld = dyn_cast<LoadInst>(&I);
2170         if (!Ld) {
2171           recordAnalysis("CantVectorizeInstruction", Ld)
2172             << "instruction cannot be vectorized";
2173           HasComplexMemInst = true;
2174           continue;
2175         }
2176         if (!Ld->isSimple() && !IsAnnotatedParallel) {
2177           recordAnalysis("NonSimpleLoad", Ld)
2178               << "read with atomic ordering or volatile read";
2179           LLVM_DEBUG(dbgs() << "LAA: Found a non-simple load.\n");
2180           HasComplexMemInst = true;
2181           continue;
2182         }
2183         NumLoads++;
2184         Loads.push_back(Ld);
2185         DepChecker->addAccess(Ld);
2186         if (EnableMemAccessVersioningOfLoop)
2187           collectStridedAccess(Ld);
2188         continue;
2189       }
2190 
2191       // Save 'store' instructions. Abort if other instructions write to memory.
2192       if (I.mayWriteToMemory()) {
2193         auto *St = dyn_cast<StoreInst>(&I);
2194         if (!St) {
2195           recordAnalysis("CantVectorizeInstruction", St)
2196               << "instruction cannot be vectorized";
2197           HasComplexMemInst = true;
2198           continue;
2199         }
2200         if (!St->isSimple() && !IsAnnotatedParallel) {
2201           recordAnalysis("NonSimpleStore", St)
2202               << "write with atomic ordering or volatile write";
2203           LLVM_DEBUG(dbgs() << "LAA: Found a non-simple store.\n");
2204           HasComplexMemInst = true;
2205           continue;
2206         }
2207         NumStores++;
2208         Stores.push_back(St);
2209         DepChecker->addAccess(St);
2210         if (EnableMemAccessVersioningOfLoop)
2211           collectStridedAccess(St);
2212       }
2213     } // Next instr.
2214   } // Next block.
2215 
2216   if (HasComplexMemInst) {
2217     CanVecMem = false;
2218     return;
2219   }
2220 
2221   // Now we have two lists that hold the loads and the stores.
2222   // Next, we find the pointers that they use.
2223 
2224   // Check if we see any stores. If there are no stores, then we don't
2225   // care if the pointers are *restrict*.
2226   if (!Stores.size()) {
2227     LLVM_DEBUG(dbgs() << "LAA: Found a read-only loop!\n");
2228     CanVecMem = true;
2229     return;
2230   }
2231 
2232   MemoryDepChecker::DepCandidates DependentAccesses;
2233   AccessAnalysis Accesses(TheLoop, AA, LI, DependentAccesses, *PSE);
2234 
2235   // Holds the analyzed pointers. We don't want to call getUnderlyingObjects
2236   // multiple times on the same object. If the ptr is accessed twice, once
2237   // for read and once for write, it will only appear once (on the write
2238   // list). This is okay, since we are going to check for conflicts between
2239   // writes and between reads and writes, but not between reads and reads.
2240   SmallSet<std::pair<Value *, Type *>, 16> Seen;
2241 
2242   // Record uniform store addresses to identify if we have multiple stores
2243   // to the same address.
2244   SmallPtrSet<Value *, 16> UniformStores;
2245 
2246   for (StoreInst *ST : Stores) {
2247     Value *Ptr = ST->getPointerOperand();
2248 
2249     if (isUniform(Ptr)) {
2250       // Record store instructions to loop invariant addresses
2251       StoresToInvariantAddresses.push_back(ST);
2252       HasDependenceInvolvingLoopInvariantAddress |=
2253           !UniformStores.insert(Ptr).second;
2254     }
2255 
2256     // If we did *not* see this pointer before, insert it to  the read-write
2257     // list. At this phase it is only a 'write' list.
2258     Type *AccessTy = getLoadStoreType(ST);
2259     if (Seen.insert({Ptr, AccessTy}).second) {
2260       ++NumReadWrites;
2261 
2262       MemoryLocation Loc = MemoryLocation::get(ST);
2263       // The TBAA metadata could have a control dependency on the predication
2264       // condition, so we cannot rely on it when determining whether or not we
2265       // need runtime pointer checks.
2266       if (blockNeedsPredication(ST->getParent(), TheLoop, DT))
2267         Loc.AATags.TBAA = nullptr;
2268 
2269       visitPointers(const_cast<Value *>(Loc.Ptr), *TheLoop,
2270                     [&Accesses, AccessTy, Loc](Value *Ptr) {
2271                       MemoryLocation NewLoc = Loc.getWithNewPtr(Ptr);
2272                       Accesses.addStore(NewLoc, AccessTy);
2273                     });
2274     }
2275   }
2276 
2277   if (IsAnnotatedParallel) {
2278     LLVM_DEBUG(
2279         dbgs() << "LAA: A loop annotated parallel, ignore memory dependency "
2280                << "checks.\n");
2281     CanVecMem = true;
2282     return;
2283   }
2284 
2285   for (LoadInst *LD : Loads) {
2286     Value *Ptr = LD->getPointerOperand();
2287     // If we did *not* see this pointer before, insert it to the
2288     // read list. If we *did* see it before, then it is already in
2289     // the read-write list. This allows us to vectorize expressions
2290     // such as A[i] += x;  Because the address of A[i] is a read-write
2291     // pointer. This only works if the index of A[i] is consecutive.
2292     // If the address of i is unknown (for example A[B[i]]) then we may
2293     // read a few words, modify, and write a few words, and some of the
2294     // words may be written to the same address.
2295     bool IsReadOnlyPtr = false;
2296     Type *AccessTy = getLoadStoreType(LD);
2297     if (Seen.insert({Ptr, AccessTy}).second ||
2298         !getPtrStride(*PSE, LD->getType(), Ptr, TheLoop, SymbolicStrides)) {
2299       ++NumReads;
2300       IsReadOnlyPtr = true;
2301     }
2302 
2303     // See if there is an unsafe dependency between a load to a uniform address and
2304     // store to the same uniform address.
2305     if (UniformStores.count(Ptr)) {
2306       LLVM_DEBUG(dbgs() << "LAA: Found an unsafe dependency between a uniform "
2307                            "load and uniform store to the same address!\n");
2308       HasDependenceInvolvingLoopInvariantAddress = true;
2309     }
2310 
2311     MemoryLocation Loc = MemoryLocation::get(LD);
2312     // The TBAA metadata could have a control dependency on the predication
2313     // condition, so we cannot rely on it when determining whether or not we
2314     // need runtime pointer checks.
2315     if (blockNeedsPredication(LD->getParent(), TheLoop, DT))
2316       Loc.AATags.TBAA = nullptr;
2317 
2318     visitPointers(const_cast<Value *>(Loc.Ptr), *TheLoop,
2319                   [&Accesses, AccessTy, Loc, IsReadOnlyPtr](Value *Ptr) {
2320                     MemoryLocation NewLoc = Loc.getWithNewPtr(Ptr);
2321                     Accesses.addLoad(NewLoc, AccessTy, IsReadOnlyPtr);
2322                   });
2323   }
2324 
2325   // If we write (or read-write) to a single destination and there are no
2326   // other reads in this loop then is it safe to vectorize.
2327   if (NumReadWrites == 1 && NumReads == 0) {
2328     LLVM_DEBUG(dbgs() << "LAA: Found a write-only loop!\n");
2329     CanVecMem = true;
2330     return;
2331   }
2332 
2333   // Build dependence sets and check whether we need a runtime pointer bounds
2334   // check.
2335   Accesses.buildDependenceSets();
2336 
2337   // Find pointers with computable bounds. We are going to use this information
2338   // to place a runtime bound check.
2339   Value *UncomputablePtr = nullptr;
2340   bool CanDoRTIfNeeded =
2341       Accesses.canCheckPtrAtRT(*PtrRtChecking, PSE->getSE(), TheLoop,
2342                                SymbolicStrides, UncomputablePtr, false);
2343   if (!CanDoRTIfNeeded) {
2344     auto *I = dyn_cast_or_null<Instruction>(UncomputablePtr);
2345     recordAnalysis("CantIdentifyArrayBounds", I)
2346         << "cannot identify array bounds";
2347     LLVM_DEBUG(dbgs() << "LAA: We can't vectorize because we can't find "
2348                       << "the array bounds.\n");
2349     CanVecMem = false;
2350     return;
2351   }
2352 
2353   LLVM_DEBUG(
2354     dbgs() << "LAA: May be able to perform a memory runtime check if needed.\n");
2355 
2356   CanVecMem = true;
2357   if (Accesses.isDependencyCheckNeeded()) {
2358     LLVM_DEBUG(dbgs() << "LAA: Checking memory dependencies\n");
2359     CanVecMem = DepChecker->areDepsSafe(
2360         DependentAccesses, Accesses.getDependenciesToCheck(), SymbolicStrides);
2361     MaxSafeDepDistBytes = DepChecker->getMaxSafeDepDistBytes();
2362 
2363     if (!CanVecMem && DepChecker->shouldRetryWithRuntimeCheck()) {
2364       LLVM_DEBUG(dbgs() << "LAA: Retrying with memory checks\n");
2365 
2366       // Clear the dependency checks. We assume they are not needed.
2367       Accesses.resetDepChecks(*DepChecker);
2368 
2369       PtrRtChecking->reset();
2370       PtrRtChecking->Need = true;
2371 
2372       auto *SE = PSE->getSE();
2373       UncomputablePtr = nullptr;
2374       CanDoRTIfNeeded = Accesses.canCheckPtrAtRT(
2375           *PtrRtChecking, SE, TheLoop, SymbolicStrides, UncomputablePtr, true);
2376 
2377       // Check that we found the bounds for the pointer.
2378       if (!CanDoRTIfNeeded) {
2379         auto *I = dyn_cast_or_null<Instruction>(UncomputablePtr);
2380         recordAnalysis("CantCheckMemDepsAtRunTime", I)
2381             << "cannot check memory dependencies at runtime";
2382         LLVM_DEBUG(dbgs() << "LAA: Can't vectorize with memory checks\n");
2383         CanVecMem = false;
2384         return;
2385       }
2386 
2387       CanVecMem = true;
2388     }
2389   }
2390 
2391   if (HasConvergentOp) {
2392     recordAnalysis("CantInsertRuntimeCheckWithConvergent")
2393       << "cannot add control dependency to convergent operation";
2394     LLVM_DEBUG(dbgs() << "LAA: We can't vectorize because a runtime check "
2395                          "would be needed with a convergent operation\n");
2396     CanVecMem = false;
2397     return;
2398   }
2399 
2400   if (CanVecMem)
2401     LLVM_DEBUG(
2402         dbgs() << "LAA: No unsafe dependent memory operations in loop.  We"
2403                << (PtrRtChecking->Need ? "" : " don't")
2404                << " need runtime memory checks.\n");
2405   else
2406     emitUnsafeDependenceRemark();
2407 }
2408 
2409 void LoopAccessInfo::emitUnsafeDependenceRemark() {
2410   auto Deps = getDepChecker().getDependences();
2411   if (!Deps)
2412     return;
2413   auto Found = std::find_if(
2414       Deps->begin(), Deps->end(), [](const MemoryDepChecker::Dependence &D) {
2415         return MemoryDepChecker::Dependence::isSafeForVectorization(D.Type) !=
2416                MemoryDepChecker::VectorizationSafetyStatus::Safe;
2417       });
2418   if (Found == Deps->end())
2419     return;
2420   MemoryDepChecker::Dependence Dep = *Found;
2421 
2422   LLVM_DEBUG(dbgs() << "LAA: unsafe dependent memory operations in loop\n");
2423 
2424   // Emit remark for first unsafe dependence
2425   OptimizationRemarkAnalysis &R =
2426       recordAnalysis("UnsafeDep", Dep.getDestination(*this))
2427       << "unsafe dependent memory operations in loop. Use "
2428          "#pragma loop distribute(enable) to allow loop distribution "
2429          "to attempt to isolate the offending operations into a separate "
2430          "loop";
2431 
2432   switch (Dep.Type) {
2433   case MemoryDepChecker::Dependence::NoDep:
2434   case MemoryDepChecker::Dependence::Forward:
2435   case MemoryDepChecker::Dependence::BackwardVectorizable:
2436     llvm_unreachable("Unexpected dependence");
2437   case MemoryDepChecker::Dependence::Backward:
2438     R << "\nBackward loop carried data dependence.";
2439     break;
2440   case MemoryDepChecker::Dependence::ForwardButPreventsForwarding:
2441     R << "\nForward loop carried data dependence that prevents "
2442          "store-to-load forwarding.";
2443     break;
2444   case MemoryDepChecker::Dependence::BackwardVectorizableButPreventsForwarding:
2445     R << "\nBackward loop carried data dependence that prevents "
2446          "store-to-load forwarding.";
2447     break;
2448   case MemoryDepChecker::Dependence::Unknown:
2449     R << "\nUnknown data dependence.";
2450     break;
2451   }
2452 
2453   if (Instruction *I = Dep.getSource(*this)) {
2454     DebugLoc SourceLoc = I->getDebugLoc();
2455     if (auto *DD = dyn_cast_or_null<Instruction>(getPointerOperand(I)))
2456       SourceLoc = DD->getDebugLoc();
2457     if (SourceLoc)
2458       R << " Memory location is the same as accessed at "
2459         << ore::NV("Location", SourceLoc);
2460   }
2461 }
2462 
2463 bool LoopAccessInfo::blockNeedsPredication(BasicBlock *BB, Loop *TheLoop,
2464                                            DominatorTree *DT)  {
2465   assert(TheLoop->contains(BB) && "Unknown block used");
2466 
2467   // Blocks that do not dominate the latch need predication.
2468   BasicBlock* Latch = TheLoop->getLoopLatch();
2469   return !DT->dominates(BB, Latch);
2470 }
2471 
2472 OptimizationRemarkAnalysis &LoopAccessInfo::recordAnalysis(StringRef RemarkName,
2473                                                            Instruction *I) {
2474   assert(!Report && "Multiple reports generated");
2475 
2476   Value *CodeRegion = TheLoop->getHeader();
2477   DebugLoc DL = TheLoop->getStartLoc();
2478 
2479   if (I) {
2480     CodeRegion = I->getParent();
2481     // If there is no debug location attached to the instruction, revert back to
2482     // using the loop's.
2483     if (I->getDebugLoc())
2484       DL = I->getDebugLoc();
2485   }
2486 
2487   Report = std::make_unique<OptimizationRemarkAnalysis>(DEBUG_TYPE, RemarkName, DL,
2488                                                    CodeRegion);
2489   return *Report;
2490 }
2491 
2492 bool LoopAccessInfo::isUniform(Value *V) const {
2493   auto *SE = PSE->getSE();
2494   // Since we rely on SCEV for uniformity, if the type is not SCEVable, it is
2495   // never considered uniform.
2496   // TODO: Is this really what we want? Even without FP SCEV, we may want some
2497   // trivially loop-invariant FP values to be considered uniform.
2498   if (!SE->isSCEVable(V->getType()))
2499     return false;
2500   return (SE->isLoopInvariant(SE->getSCEV(V), TheLoop));
2501 }
2502 
2503 void LoopAccessInfo::collectStridedAccess(Value *MemAccess) {
2504   Value *Ptr = getLoadStorePointerOperand(MemAccess);
2505   if (!Ptr)
2506     return;
2507 
2508   Value *Stride = getStrideFromPointer(Ptr, PSE->getSE(), TheLoop);
2509   if (!Stride)
2510     return;
2511 
2512   LLVM_DEBUG(dbgs() << "LAA: Found a strided access that is a candidate for "
2513                        "versioning:");
2514   LLVM_DEBUG(dbgs() << "  Ptr: " << *Ptr << " Stride: " << *Stride << "\n");
2515 
2516   // Avoid adding the "Stride == 1" predicate when we know that
2517   // Stride >= Trip-Count. Such a predicate will effectively optimize a single
2518   // or zero iteration loop, as Trip-Count <= Stride == 1.
2519   //
2520   // TODO: We are currently not making a very informed decision on when it is
2521   // beneficial to apply stride versioning. It might make more sense that the
2522   // users of this analysis (such as the vectorizer) will trigger it, based on
2523   // their specific cost considerations; For example, in cases where stride
2524   // versioning does  not help resolving memory accesses/dependences, the
2525   // vectorizer should evaluate the cost of the runtime test, and the benefit
2526   // of various possible stride specializations, considering the alternatives
2527   // of using gather/scatters (if available).
2528 
2529   const SCEV *StrideExpr = PSE->getSCEV(Stride);
2530   const SCEV *BETakenCount = PSE->getBackedgeTakenCount();
2531 
2532   // Match the types so we can compare the stride and the BETakenCount.
2533   // The Stride can be positive/negative, so we sign extend Stride;
2534   // The backedgeTakenCount is non-negative, so we zero extend BETakenCount.
2535   const DataLayout &DL = TheLoop->getHeader()->getModule()->getDataLayout();
2536   uint64_t StrideTypeSizeBits = DL.getTypeSizeInBits(StrideExpr->getType());
2537   uint64_t BETypeSizeBits = DL.getTypeSizeInBits(BETakenCount->getType());
2538   const SCEV *CastedStride = StrideExpr;
2539   const SCEV *CastedBECount = BETakenCount;
2540   ScalarEvolution *SE = PSE->getSE();
2541   if (BETypeSizeBits >= StrideTypeSizeBits)
2542     CastedStride = SE->getNoopOrSignExtend(StrideExpr, BETakenCount->getType());
2543   else
2544     CastedBECount = SE->getZeroExtendExpr(BETakenCount, StrideExpr->getType());
2545   const SCEV *StrideMinusBETaken = SE->getMinusSCEV(CastedStride, CastedBECount);
2546   // Since TripCount == BackEdgeTakenCount + 1, checking:
2547   // "Stride >= TripCount" is equivalent to checking:
2548   // Stride - BETakenCount > 0
2549   if (SE->isKnownPositive(StrideMinusBETaken)) {
2550     LLVM_DEBUG(
2551         dbgs() << "LAA: Stride>=TripCount; No point in versioning as the "
2552                   "Stride==1 predicate will imply that the loop executes "
2553                   "at most once.\n");
2554     return;
2555   }
2556   LLVM_DEBUG(dbgs() << "LAA: Found a strided access that we can version.\n");
2557 
2558   SymbolicStrides[Ptr] = Stride;
2559   StrideSet.insert(Stride);
2560 }
2561 
2562 LoopAccessInfo::LoopAccessInfo(Loop *L, ScalarEvolution *SE,
2563                                const TargetLibraryInfo *TLI, AAResults *AA,
2564                                DominatorTree *DT, LoopInfo *LI)
2565     : PSE(std::make_unique<PredicatedScalarEvolution>(*SE, *L)),
2566       PtrRtChecking(nullptr),
2567       DepChecker(std::make_unique<MemoryDepChecker>(*PSE, L)), TheLoop(L) {
2568   PtrRtChecking = std::make_unique<RuntimePointerChecking>(*DepChecker, SE);
2569   if (canAnalyzeLoop()) {
2570     analyzeLoop(AA, LI, TLI, DT);
2571   }
2572 }
2573 
2574 void LoopAccessInfo::print(raw_ostream &OS, unsigned Depth) const {
2575   if (CanVecMem) {
2576     OS.indent(Depth) << "Memory dependences are safe";
2577     if (MaxSafeDepDistBytes != -1ULL)
2578       OS << " with a maximum dependence distance of " << MaxSafeDepDistBytes
2579          << " bytes";
2580     if (PtrRtChecking->Need)
2581       OS << " with run-time checks";
2582     OS << "\n";
2583   }
2584 
2585   if (HasConvergentOp)
2586     OS.indent(Depth) << "Has convergent operation in loop\n";
2587 
2588   if (Report)
2589     OS.indent(Depth) << "Report: " << Report->getMsg() << "\n";
2590 
2591   if (auto *Dependences = DepChecker->getDependences()) {
2592     OS.indent(Depth) << "Dependences:\n";
2593     for (const auto &Dep : *Dependences) {
2594       Dep.print(OS, Depth + 2, DepChecker->getMemoryInstructions());
2595       OS << "\n";
2596     }
2597   } else
2598     OS.indent(Depth) << "Too many dependences, not recorded\n";
2599 
2600   // List the pair of accesses need run-time checks to prove independence.
2601   PtrRtChecking->print(OS, Depth);
2602   OS << "\n";
2603 
2604   OS.indent(Depth) << "Non vectorizable stores to invariant address were "
2605                    << (HasDependenceInvolvingLoopInvariantAddress ? "" : "not ")
2606                    << "found in loop.\n";
2607 
2608   OS.indent(Depth) << "SCEV assumptions:\n";
2609   PSE->getPredicate().print(OS, Depth);
2610 
2611   OS << "\n";
2612 
2613   OS.indent(Depth) << "Expressions re-written:\n";
2614   PSE->print(OS, Depth);
2615 }
2616 
2617 LoopAccessLegacyAnalysis::LoopAccessLegacyAnalysis() : FunctionPass(ID) {
2618   initializeLoopAccessLegacyAnalysisPass(*PassRegistry::getPassRegistry());
2619 }
2620 
2621 const LoopAccessInfo &LoopAccessLegacyAnalysis::getInfo(Loop *L) {
2622   auto &LAI = LoopAccessInfoMap[L];
2623 
2624   if (!LAI)
2625     LAI = std::make_unique<LoopAccessInfo>(L, SE, TLI, AA, DT, LI);
2626 
2627   return *LAI;
2628 }
2629 
2630 void LoopAccessLegacyAnalysis::print(raw_ostream &OS, const Module *M) const {
2631   LoopAccessLegacyAnalysis &LAA = *const_cast<LoopAccessLegacyAnalysis *>(this);
2632 
2633   for (Loop *TopLevelLoop : *LI)
2634     for (Loop *L : depth_first(TopLevelLoop)) {
2635       OS.indent(2) << L->getHeader()->getName() << ":\n";
2636       auto &LAI = LAA.getInfo(L);
2637       LAI.print(OS, 4);
2638     }
2639 }
2640 
2641 bool LoopAccessLegacyAnalysis::runOnFunction(Function &F) {
2642   SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
2643   auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
2644   TLI = TLIP ? &TLIP->getTLI(F) : nullptr;
2645   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
2646   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2647   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
2648 
2649   return false;
2650 }
2651 
2652 void LoopAccessLegacyAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
2653   AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
2654   AU.addRequiredTransitive<AAResultsWrapperPass>();
2655   AU.addRequiredTransitive<DominatorTreeWrapperPass>();
2656   AU.addRequiredTransitive<LoopInfoWrapperPass>();
2657 
2658   AU.setPreservesAll();
2659 }
2660 
2661 char LoopAccessLegacyAnalysis::ID = 0;
2662 static const char laa_name[] = "Loop Access Analysis";
2663 #define LAA_NAME "loop-accesses"
2664 
2665 INITIALIZE_PASS_BEGIN(LoopAccessLegacyAnalysis, LAA_NAME, laa_name, false, true)
2666 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
2667 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
2668 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
2669 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
2670 INITIALIZE_PASS_END(LoopAccessLegacyAnalysis, LAA_NAME, laa_name, false, true)
2671 
2672 AnalysisKey LoopAccessAnalysis::Key;
2673 
2674 LoopAccessInfo LoopAccessAnalysis::run(Loop &L, LoopAnalysisManager &AM,
2675                                        LoopStandardAnalysisResults &AR) {
2676   return LoopAccessInfo(&L, &AR.SE, &AR.TLI, &AR.AA, &AR.DT, &AR.LI);
2677 }
2678 
2679 namespace llvm {
2680 
2681   Pass *createLAAPass() {
2682     return new LoopAccessLegacyAnalysis();
2683   }
2684 
2685 } // end namespace llvm
2686