[LAA] Keep track of ptr SCEV related to MemAccessInfo (WIP).

[fhahn]

Summary

This patch extends MemAccessInfo and PointerInfo to track the associated
SCEV for the pointer. The SCEV expressions is then used instead of
accessing ScalarEvolution on demand.

This has multiple benefits:

1. We only need to replace symbolic strides once, up front.
2. Allows for more flexibility to have accesses with different SCEV expressions for their pointers.For example, it allows adding 2 MemAccessInfo for a pointer fed by a select.

This is still a bit rough around the edges. In particular the printing
is still missing the SCEV expression.

[Allen]

hi @fhahn, do you have plan to continue this work?

I think the issue on https://github.com/llvm/llvm-project/issues/64292 is similar to  scene, but here is a phi node.

[fhahn]

In D114479#4590518, @Allen wrote:

hi @fhahn, do you have plan to continue this work?

I think the issue on https://github.com/llvm/llvm-project/issues/64292 is similar to  scene, but here is a phi node.

Hmm interesting! I thought it wasn't needed with the recent changes, but I'll try to check the issue out.

[Allen]

thanks for your check in advance.

llvm/include/llvm/Analysis/LoopAccessAnalysis.h

struct VectorizerParams {
   /// True if force-vector-interleave was specified by the user.
   static bool isInterleaveForced();
 
   /// \When performing memory disambiguation checks at runtime do not
   /// make more than this number of comparisons.
   static unsigned RuntimeMemoryCheckThreshold;
 };
 
+struct MemAccessInfo {
+  PointerIntPair<Value *, 1, bool> ValueAndBool;
+  MemAccessInfo(Value *V, bool B, const SCEV *PtrExpr)
+      : ValueAndBool(V, B), PtrExpr(PtrExpr) {}
+  MemAccessInfo() : ValueAndBool(nullptr) {}
+  MemAccessInfo(PointerIntPair<Value *, 1, bool> V) : ValueAndBool(V) {}
+
+  const SCEV *PtrExpr = nullptr;
+
+  Value *getPointer() { return ValueAndBool.getPointer(); }
+  bool getInt() { return ValueAndBool.getInt(); }
+  Value *getPointer() const { return ValueAndBool.getPointer(); }
+  bool getInt() const { return ValueAndBool.getInt(); }
+  const SCEV *getPtrExpr() const { return PtrExpr; }
+
+  bool operator<(const MemAccessInfo &RHS) const {
+    return ValueAndBool < RHS.ValueAndBool;
+  }
+  bool operator==(const MemAccessInfo &RHS) const {
+    return ValueAndBool == RHS.ValueAndBool && PtrExpr == RHS.PtrExpr;
+  }
+};
+
+template <> struct DenseMapInfo<MemAccessInfo> {
+  using Ty = DenseMapInfo<PointerIntPair<Value *, 1, bool>>;
+
+  static MemAccessInfo getEmptyKey() {
+    return MemAccessInfo(Ty::getEmptyKey());
+  }
+
+  static MemAccessInfo getTombstoneKey() {
+    return MemAccessInfo(Ty::getTombstoneKey());
+  }
+
+  static unsigned getHashValue(MemAccessInfo V) {
+    uintptr_t IV = reinterpret_cast<uintptr_t>(V.ValueAndBool.getOpaqueValue());
+    return unsigned(IV) ^ unsigned(IV >> 9);
+  }
+
+  static bool isEqual(const MemAccessInfo &LHS, const MemAccessInfo &RHS) {
+    return LHS == RHS;
+  }
+};
+
 /// Checks memory dependences among accesses to the same underlying
 /// object to determine whether there vectorization is legal or not (and at
 /// which vectorization factor).
 ///
 /// Note: This class will compute a conservative dependence for access to
 /// different underlying pointers. Clients, such as the loop vectorizer, will
 /// sometimes deal these potential dependencies by emitting runtime checks.
 ///

 ///     a[i+2] = tmp                      y = b[i+2];
 ///
 ///     Safe distance: 2 x sizeof(a[0]), and 2 x sizeof(b[0]), respectively.
 ///
 ///  * Zero distances and all accesses have the same size.
 ///
 class MemoryDepChecker {
 public:
-  typedef PointerIntPair<Value *, 1, bool> MemAccessInfo;
   typedef SmallVector<MemAccessInfo, 8> MemAccessInfoList;
   /// Set of potential dependent memory accesses.
   typedef EquivalenceClasses<MemAccessInfo> DepCandidates;
 
   /// Type to keep track of the status of the dependence check. The order of
   /// the elements is important and has to be from most permissive to least
   /// permissive.
   enum class VectorizationSafetyStatus {
public:
   MemoryDepChecker(PredicatedScalarEvolution &PSE, const Loop *L)
       : PSE(PSE), InnermostLoop(L), AccessIdx(0), MaxSafeDepDistBytes(0),
         MaxSafeVectorWidthInBits(-1U),
         FoundNonConstantDistanceDependence(false),
         Status(VectorizationSafetyStatus::Safe), RecordDependences(true) {}
 
   /// Register the location (instructions are given increasing numbers)
   /// of a write access.
-  void addAccess(StoreInst *SI);
+  void addAccess(StoreInst *SI, const ValueToValueMap &SymbolicStrides);
 
   /// Register the location (instructions are given increasing numbers)
   /// of a write access.
-  void addAccess(LoadInst *LI);
+  void addAccess(LoadInst *LI, const ValueToValueMap &SymbolicStrides);
 
   /// Check whether the dependencies between the accesses are safe.
   ///
   /// Only checks sets with elements in \p CheckDeps.
   bool areDepsSafe(DepCandidates &AccessSets, MemAccessInfoList &CheckDeps,
                    const ValueToValueMap &Strides);
 
   /// No memory dependence was encountered that would inhibit
DenseMap<Instruction *, unsigned> generateInstructionOrderMap() const {
 
     for (unsigned I = 0; I < InstMap.size(); ++I)
       OrderMap[InstMap[I]] = I;
 
     return OrderMap;
   }
 
   /// Find the set of instructions that read or write via \p Ptr.
-  SmallVector<Instruction *, 4> getInstructionsForAccess(Value *Ptr,
-                                                         bool isWrite) const;
+  SmallVector<Instruction *, 4>
+  getInstructionsForAccess(Value *Ptr, bool isWrite,
+                           const ValueToValueMap &SymbolicStrides) const;
 
 private:
   /// A wrapper around ScalarEvolution, used to add runtime SCEV checks, and
   /// applies dynamic knowledge to simplify SCEV expressions and convert them
   /// to a more usable form. We need this in case assumptions about SCEV
   /// expressions need to be made in order to avoid unknown dependences. For
   /// example we might assume a unit stride for a pointer in order to prove
   /// that a memory access is strided and doesn't wrap.
struct PointerInfo {
     /// Holds the id of the set of pointers that could be dependent because of a
     /// shared underlying object.
     unsigned DependencySetId;
     /// Holds the id of the disjoint alias set to which this pointer belongs.
     unsigned AliasSetId;
     /// SCEV for the access.
     const SCEV *Expr;
 
+    /// SCEV for the access.
+    const SCEV *PtrExpr;
+
     PointerInfo(Value *PointerValue, const SCEV *Start, const SCEV *End,
                 bool IsWritePtr, unsigned DependencySetId, unsigned AliasSetId,
-                const SCEV *Expr)
+                const SCEV *Expr, const SCEV *PtrExpr)
         : PointerValue(PointerValue), Start(Start), End(End),
           IsWritePtr(IsWritePtr), DependencySetId(DependencySetId),
-          AliasSetId(AliasSetId), Expr(Expr) {}
+          AliasSetId(AliasSetId), Expr(Expr), PtrExpr(PtrExpr) {}
   };
 
   RuntimePointerChecking(ScalarEvolution *SE) : Need(false), SE(SE) {}
 
   /// Reset the state of the pointer runtime information.
   void reset() {
     Need = false;
     Pointers.clear();
     Checks.clear();
   }
 
   /// Insert a pointer and calculate the start and end SCEVs.
   /// We need \p PSE in order to compute the SCEV expression of the pointer
   /// according to the assumptions that we've made during the analysis.
   /// The method might also version the pointer stride according to \p Strides,
   /// and add new predicates to \p PSE.
-  void insert(Loop *Lp, Value *Ptr, bool WritePtr, unsigned DepSetId,
-              unsigned ASId, const ValueToValueMap &Strides,
+  void insert(Loop *Lp, Value *Ptr, const SCEV *PtrExpr, const SCEV *Sc,
+              bool WritePtr, unsigned DepSetId, unsigned ASId,
               PredicatedScalarEvolution &PSE);
 
   /// No run-time memory checking is necessary.
   bool empty() const { return Pointers.empty(); }
 
   /// Generate the checks and store it.  This also performs the grouping
   /// of pointers to reduce the number of memchecks necessary.
   void generateChecks(MemoryDepChecker::DepCandidates &DepCands,
public:
   const OptimizationRemarkAnalysis *getReport() const { return Report.get(); }
 
   /// the Memory Dependence Checker which can determine the
   /// loop-independent and loop-carried dependences between memory accesses.
   const MemoryDepChecker &getDepChecker() const { return *DepChecker; }
 
   /// Return the list of instructions that use \p Ptr to read or write
   /// memory.
-  SmallVector<Instruction *, 4> getInstructionsForAccess(Value *Ptr,
-                                                         bool isWrite) const {
-    return DepChecker->getInstructionsForAccess(Ptr, isWrite);
+  SmallVector<Instruction *, 4>
+  getInstructionsForAccess(Value *Ptr, bool isWrite,
+                           const ValueToValueMap &SymbolicStrides) const {
+    return DepChecker->getInstructionsForAccess(Ptr, isWrite, SymbolicStrides);
   }
 
   /// If an access has a symbolic strides, this maps the pointer value to
   /// the stride symbol.
   const ValueToValueMap &getSymbolicStrides() const { return SymbolicStrides; }
 
   /// Pointer has a symbolic stride.
   bool hasStride(Value *V) const { return StrideSet.count(V); }

llvm/lib/Analysis/LoopAccessAnalysis.cpp

 /// N is a calculated back-edge taken count:
 ///     N = (TripCount > 0) ? RoundDown(TripCount -1 , VF) : 0
 /// Start and End points are calculated in the following way:
 /// Start = UMIN(A, B) ; End = UMAX(A, B) + SizeOfElt,
 /// where SizeOfElt is the size of single memory access in bytes.
 ///
 /// There is no conflict when the intervals are disjoint:
 /// NoConflict = (P2.Start >= P1.End) || (P1.Start >= P2.End)
-void RuntimePointerChecking::insert(Loop *Lp, Value *Ptr, bool WritePtr,
+void RuntimePointerChecking::insert(Loop *Lp, Value *Ptr, const SCEV *PtrExpr,
+                                    const SCEV *Sc, bool WritePtr,
                                     unsigned DepSetId, unsigned ASId,
-                                    const ValueToValueMap &Strides,
                                     PredicatedScalarEvolution &PSE) {
   // Get the stride replaced scev.
-  const SCEV *Sc = replaceSymbolicStrideSCEV(PSE, Strides, Ptr);
   ScalarEvolution *SE = PSE.getSE();
 
   const SCEV *ScStart;
   const SCEV *ScEnd;
 
   if (SE->isLoopInvariant(Sc, Lp)) {
     ScStart = ScEnd = Sc;
   } else {
void RuntimePointerChecking::insert(Loop *Lp, Value *Ptr, const SCEV *PtrExpr,
   }
   // Add the size of the pointed element to ScEnd.
   auto &DL = Lp->getHeader()->getModule()->getDataLayout();
   Type *IdxTy = DL.getIndexType(Ptr->getType());
   const SCEV *EltSizeSCEV =
       SE->getStoreSizeOfExpr(IdxTy, Ptr->getType()->getPointerElementType());
   ScEnd = SE->getAddExpr(ScEnd, EltSizeSCEV);
 
-  Pointers.emplace_back(Ptr, ScStart, ScEnd, WritePtr, DepSetId, ASId, Sc);
+  Pointers.emplace_back(Ptr, ScStart, ScEnd, WritePtr, DepSetId, ASId, Sc,
+                        PtrExpr);
 }
 
 SmallVector<RuntimePointerCheck, 4>
 RuntimePointerChecking::generateChecks() const {
   SmallVector<RuntimePointerCheck, 4> Checks;
 
   for (unsigned I = 0; I < CheckingGroups.size(); ++I) {
     for (unsigned J = I + 1; J < CheckingGroups.size(); ++J) {
void RuntimePointerChecking::groupChecks(
   if (!UseDependencies) {
     for (unsigned I = 0; I < Pointers.size(); ++I)
       CheckingGroups.push_back(RuntimeCheckingPtrGroup(I, *this));
     return;
   }
 
   unsigned TotalComparisons = 0;
 
-  DenseMap<Value *, unsigned> PositionMap;
+  DenseMap<const SCEV *, unsigned> PositionMap;
   for (unsigned Index = 0; Index < Pointers.size(); ++Index)
-    PositionMap[Pointers[Index].PointerValue] = Index;
+    PositionMap[Pointers[Index].PtrExpr] = Index;
 
   // We need to keep track of what pointers we've already seen so we
   // don't process them twice.
   SmallSet<unsigned, 2> Seen;
 
   // Go through all equivalence classes, get the "pointer check groups"
   // and add them to the overall solution. We use the order in which accesses
   // appear in 'Pointers' to enforce determinism.
   for (unsigned I = 0; I < Pointers.size(); ++I) {
     // We've seen this pointer before, and therefore already processed
     // its equivalence class.
     if (Seen.count(I))
       continue;
 
-    MemoryDepChecker::MemAccessInfo Access(Pointers[I].PointerValue,
-                                           Pointers[I].IsWritePtr);
+    MemAccessInfo Access(Pointers[I].PointerValue, Pointers[I].IsWritePtr,
+                         Pointers[I].PtrExpr);
 
     SmallVector<RuntimeCheckingPtrGroup, 2> Groups;
     auto LeaderI = DepCands.findValue(DepCands.getLeaderValue(Access));
 
     // Because DepCands is constructed by visiting accesses in the order in
     // which they appear in alias sets (which is deterministic) and the
     // iteration order within an equivalence class member is only dependent on
     // the order in which unions and insertions are performed on the
     // equivalence class, the iteration order is deterministic.
     for (auto MI = DepCands.member_begin(LeaderI), ME = DepCands.member_end();
          MI != ME; ++MI) {
-      auto PointerI = PositionMap.find(MI->getPointer());
+      auto PointerI = PositionMap.find(MI->getPtrExpr());
       assert(PointerI != PositionMap.end() &&
              "pointer in equivalence class not found in PositionMap");
       unsigned Pointer = PointerI->second;
       bool Merged = false;
       // Mark this pointer as seen.
       Seen.insert(Pointer);
 
       // Go through all the existing sets and see if we can find one

 
 /// Analyses memory accesses in a loop.
 ///
 /// Checks whether run time pointer checks are needed and builds sets for data
 /// dependence checking.
 class AccessAnalysis {
 public:
   /// Read or write access location.
-  typedef PointerIntPair<Value *, 1, bool> MemAccessInfo;
   typedef SmallVector<MemAccessInfo, 8> MemAccessInfoList;
 
   AccessAnalysis(Loop *TheLoop, AAResults *AA, LoopInfo *LI,
                  MemoryDepChecker::DepCandidates &DA,
                  PredicatedScalarEvolution &PSE)
       : TheLoop(TheLoop), AST(*AA), LI(LI), DepCands(DA),
         IsRTCheckAnalysisNeeded(false), PSE(PSE) {}
 
   /// Register a load  and whether it is only read from.
-  void addLoad(MemoryLocation &Loc, bool IsReadOnly) {
+  void addLoad(MemoryLocation &Loc, bool IsReadOnly, const SCEV *PtrScev) {
     Value *Ptr = const_cast<Value*>(Loc.Ptr);
     AST.add(Ptr, LocationSize::beforeOrAfterPointer(), Loc.AATags);
-    Accesses.insert(MemAccessInfo(Ptr, false));
+    Accesses.insert(MemAccessInfo(Ptr, false, PtrScev));
     if (IsReadOnly)
       ReadOnlyPtr.insert(Ptr);
   }
 
   /// Register a store.
-  void addStore(MemoryLocation &Loc) {
+  void addStore(MemoryLocation &Loc, const SCEV *PtrScev) {
     Value *Ptr = const_cast<Value*>(Loc.Ptr);
     AST.add(Ptr, LocationSize::beforeOrAfterPointer(), Loc.AATags);
-    Accesses.insert(MemAccessInfo(Ptr, true));
+    Accesses.insert(MemAccessInfo(Ptr, true, PtrScev));
   }
 
   /// Check if we can emit a run-time no-alias check for \p Access.
   ///
   /// Returns true if we can emit a run-time no alias check for \p Access.
   /// If we can check this access, this also adds it to a dependence set and
   /// adds a run-time to check for it to \p RtCheck. If \p Assume is true,
   /// we will attempt to use additional run-time checks in order to get
   /// the bounds of the pointer.
   bool createCheckForAccess(RuntimePointerChecking &RtCheck,
                             MemAccessInfo Access,
-                            const ValueToValueMap &Strides,
-                            DenseMap<Value *, unsigned> &DepSetId,
+                            DenseMap<const SCEV *, unsigned> &DepSetId,
                             Loop *TheLoop, unsigned &RunningDepId,
-                            unsigned ASId, bool ShouldCheckStride,
-                            bool Assume);
+                            unsigned ASId, bool ShouldCheckStride, bool Assume);
 
   /// Check whether we can check the pointers at runtime for
   /// non-intersection.
   ///
   /// Returns true if we need no check or if we do and we can generate them
   /// (i.e. the pointers have computable bounds).
   bool canCheckPtrAtRT(RuntimePointerChecking &RtCheck, ScalarEvolution *SE,
                        Loop *TheLoop, const ValueToValueMap &Strides,
                        bool ShouldCheckWrap = false);
 
   /// Goes over all memory accesses, checks whether a RT check is needed
   /// and builds sets of dependent accesses.
-  void buildDependenceSets() {
-    processMemAccesses();
+  void buildDependenceSets(ValueToValueMap &SymbolicStrides) {
+    processMemAccesses(SymbolicStrides);
   }
 
   /// Initial processing of memory accesses determined that we need to
   /// perform dependency checking.
   ///
   /// Note that this can later be cleared if we retry memcheck analysis without
   /// dependency checking (i.e. FoundNonConstantDistanceDependence).
   bool isDependencyCheckNeeded() { return !CheckDeps.empty(); }
 
   /// We decided that no dependence analysis would be used.  Reset the state.
   void resetDepChecks(MemoryDepChecker &DepChecker) {
     CheckDeps.clear();
     DepChecker.clearDependences();
   }
 
   MemAccessInfoList &getDependenciesToCheck() { return CheckDeps; }
 
 private:
   typedef SetVector<MemAccessInfo> PtrAccessSet;
 
   /// Go over all memory access and check whether runtime pointer checks
   /// are needed and build sets of dependency check candidates.
-  void processMemAccesses();
+  void processMemAccesses(ValueToValueMap &SymbolicStrides);
 
   /// Set of all accesses.
   PtrAccessSet Accesses;
 
   /// The loop being checked.
   const Loop *TheLoop;
 
   /// List of accesses that need a further dependence check.
private:
   PredicatedScalarEvolution &PSE;
 };
 
 } // end anonymous namespace
 
 /// Check whether a pointer can participate in a runtime bounds check.
 /// If \p Assume, try harder to prove that we can compute the bounds of \p Ptr
 /// by adding run-time checks (overflow checks) if necessary.
-static bool hasComputableBounds(PredicatedScalarEvolution &PSE,
-                                const ValueToValueMap &Strides, Value *Ptr,
-                                Loop *L, bool Assume) {
-  const SCEV *PtrScev = replaceSymbolicStrideSCEV(PSE, Strides, Ptr);
-
+static const SCEV *hasComputableBounds(PredicatedScalarEvolution &PSE,
+                                       Value *Ptr, const SCEV *PtrScev, Loop *L,
+                                       bool Assume) {
   // The bounds for loop-invariant pointer is trivial.
   if (PSE.getSE()->isLoopInvariant(PtrScev, L))
-    return true;
+    return PtrScev;
 
   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev);
 
   if (!AR && Assume)
     AR = PSE.getAsAddRec(Ptr);
-
-  if (!AR)
-    return false;
-
-  return AR->isAffine();
+  if (AR && AR->isAffine())
+    return AR;
+  return nullptr;
 }
 
+static int64_t getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy,
+                            Value *Ptr, const SCEV *PtrScev, const Loop *Lp,
+                            bool Assume = false, bool ShouldCheckWrap = true);
+
 /// Check whether a pointer address cannot wrap.
-static bool isNoWrap(PredicatedScalarEvolution &PSE,
-                     const ValueToValueMap &Strides, Value *Ptr, Loop *L) {
-  const SCEV *PtrScev = PSE.getSCEV(Ptr);
+static bool isNoWrap(PredicatedScalarEvolution &PSE, Value *Ptr,
+                     const SCEV *PtrScev, Loop *L) {
   if (PSE.getSE()->isLoopInvariant(PtrScev, L))
     return true;
 
   Type *AccessTy = Ptr->getType()->getPointerElementType();
-  int64_t Stride = getPtrStride(PSE, AccessTy, Ptr, L, Strides);
+  int64_t Stride = getPtrStride(PSE, AccessTy, Ptr, PtrScev, L);
   if (Stride == 1 || PSE.hasNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW))
     return true;
 
   return false;
 }
 
-static void visitPointers(Value *StartPtr, const Loop &InnermostLoop,
-                          function_ref<void(Value *)> AddPointer) {
+static void
+visitPointers(Value *StartPtr, const Loop &InnermostLoop,
+              PredicatedScalarEvolution &PSE,
+              const ValueToValueMap &SymbolicStrides,
+              function_ref<void(Value *, const SCEV *)> AddPointer) {
   SmallPtrSet<Value *, 8> Visited;
   SmallVector<Value *> WorkList;
   WorkList.push_back(StartPtr);
 
   while (!WorkList.empty()) {
     Value *Ptr = WorkList.pop_back_val();
     if (!Visited.insert(Ptr).second)
       continue;
     auto *PN = dyn_cast<PHINode>(Ptr);
     // SCEV does not look through non-header PHIs inside the loop. Such phis
     // can be analyzed by adding separate accesses for each incoming pointer
     // value.
     if (PN && InnermostLoop.contains(PN->getParent()) &&
         PN->getParent() != InnermostLoop.getHeader()) {
       for (const Use &Inc : PN->incoming_values())
         WorkList.push_back(Inc);
     } else
-      AddPointer(Ptr);
+      AddPointer(Ptr, replaceSymbolicStrideSCEV(PSE, SymbolicStrides, Ptr));
   }
 }
 
-bool AccessAnalysis::createCheckForAccess(RuntimePointerChecking &RtCheck,
-                                          MemAccessInfo Access,
-                                          const ValueToValueMap &StridesMap,
-                                          DenseMap<Value *, unsigned> &DepSetId,
-                                          Loop *TheLoop, unsigned &RunningDepId,
-                                          unsigned ASId, bool ShouldCheckWrap,
-                                          bool Assume) {
+bool AccessAnalysis::createCheckForAccess(
+    RuntimePointerChecking &RtCheck, MemAccessInfo Access,
+    DenseMap<const SCEV *, unsigned> &DepSetId, Loop *TheLoop,
+    unsigned &RunningDepId, unsigned ASId, bool ShouldCheckWrap, bool Assume) {
   Value *Ptr = Access.getPointer();
-
-  if (!hasComputableBounds(PSE, StridesMap, Ptr, TheLoop, Assume))
+  const SCEV *PtrScev =
+      hasComputableBounds(PSE, Ptr, Access.getPtrExpr(), TheLoop, Assume);
+  if (!PtrScev)
     return false;
 
   // When we run after a failing dependency check we have to make sure
   // we don't have wrapping pointers.
-  if (ShouldCheckWrap && !isNoWrap(PSE, StridesMap, Ptr, TheLoop)) {
-    auto *Expr = PSE.getSCEV(Ptr);
-    if (!Assume || !isa<SCEVAddRecExpr>(Expr))
+  if (ShouldCheckWrap && !isNoWrap(PSE, Ptr, PtrScev, TheLoop)) {
+    if (!Assume || !isa<SCEVAddRecExpr>(PtrScev))
       return false;
+
+    // FIXME: not handled properly.
     PSE.setNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW);
   }
 
   // The id of the dependence set.
   unsigned DepId;
 
   if (isDependencyCheckNeeded()) {
-    Value *Leader = DepCands.getLeaderValue(Access).getPointer();
+    const SCEV *Leader = DepCands.getLeaderValue(Access).getPtrExpr();
     unsigned &LeaderId = DepSetId[Leader];
     if (!LeaderId)
       LeaderId = RunningDepId++;
     DepId = LeaderId;
   } else
     // Each access has its own dependence set.
     DepId = RunningDepId++;
 
   bool IsWrite = Access.getInt();
-  RtCheck.insert(TheLoop, Ptr, IsWrite, DepId, ASId, StridesMap, PSE);
+  RtCheck.insert(TheLoop, Ptr, Access.getPtrExpr(), PtrScev, IsWrite, DepId,
+                 ASId, PSE);
   LLVM_DEBUG(dbgs() << "LAA: Found a runtime check ptr:" << *Ptr << '\n');
 
   return true;
- }
 
 bool AccessAnalysis::canCheckPtrAtRT(RuntimePointerChecking &RtCheck,
                                      ScalarEvolution *SE, Loop *TheLoop,
                                      const ValueToValueMap &StridesMap,
                                      bool ShouldCheckWrap) {
   // Find pointers with computable bounds. We are going to use this information
   // to place a runtime bound check.
   bool CanDoRT = true;
for (auto &AS : AST) {
     int NumReadPtrChecks = 0;
     int NumWritePtrChecks = 0;
     bool CanDoAliasSetRT = true;
     ++ASId;
 
     // We assign consecutive id to access from different dependence sets.
     // Accesses within the same set don't need a runtime check.
     unsigned RunningDepId = 1;
-    DenseMap<Value *, unsigned> DepSetId;
+    DenseMap<const SCEV *, unsigned> DepSetId;
 
     SmallVector<MemAccessInfo, 4> Retries;
 
     // First, count how many write and read accesses are in the alias set. Also
     // collect MemAccessInfos for later.
     SmallVector<MemAccessInfo, 4> AccessInfos;
     for (const auto &A : AS) {
       Value *Ptr = A.getValue();
-      bool IsWrite = Accesses.count(MemAccessInfo(Ptr, true));
+      const SCEV *PtrScev = replaceSymbolicStrideSCEV(PSE, StridesMap, Ptr);
+      bool IsWrite = Accesses.count(MemAccessInfo(Ptr, true, PtrScev));
 
       if (IsWrite)
         ++NumWritePtrChecks;
       else
         ++NumReadPtrChecks;
-      AccessInfos.emplace_back(Ptr, IsWrite);
+      AccessInfos.emplace_back(Ptr, IsWrite, PtrScev);
     }
 
     // We do not need runtime checks for this alias set, if there are no writes
     // or a single write and no reads.
     if (NumWritePtrChecks == 0 ||
         (NumWritePtrChecks == 1 && NumReadPtrChecks == 0)) {
       assert((AS.size() <= 1 ||
               all_of(AS,
-                     [this](auto AC) {
-                       MemAccessInfo AccessWrite(AC.getValue(), true);
+                     [this, &StridesMap](auto AC) {
+                       MemAccessInfo AccessWrite(
+                           AC.getValue(), true,
+                           replaceSymbolicStrideSCEV(PSE, StridesMap,
+                                                     AC.getValue()));
                        return DepCands.findValue(AccessWrite) == DepCands.end();
                      })) &&
              "Can only skip updating CanDoRT below, if all entries in AS "
              "are reads or there is at most 1 entry");
       continue;
     }
 
     for (auto &Access : AccessInfos) {
-      if (!createCheckForAccess(RtCheck, Access, StridesMap, DepSetId, TheLoop,
+      if (!createCheckForAccess(RtCheck, Access, DepSetId, TheLoop,
                                 RunningDepId, ASId, ShouldCheckWrap, false)) {
         LLVM_DEBUG(dbgs() << "LAA: Can't find bounds for ptr:"
                           << *Access.getPointer() << '\n');
         Retries.push_back(Access);
         CanDoAliasSetRT = false;
       }
     }
 
for (auto &AS : AST) {
     // We need to perform run-time alias checks, but some pointers had bounds
     // that couldn't be checked.
     if (NeedsAliasSetRTCheck && !CanDoAliasSetRT) {
       // Reset the CanDoSetRt flag and retry all accesses that have failed.
       // We know that we need these checks, so we can now be more aggressive
       // and add further checks if required (overflow checks).
       CanDoAliasSetRT = true;
       for (auto Access : Retries)
-        if (!createCheckForAccess(RtCheck, Access, StridesMap, DepSetId,
-                                  TheLoop, RunningDepId, ASId,
-                                  ShouldCheckWrap, /*Assume=*/true)) {
+        if (!createCheckForAccess(RtCheck, Access, DepSetId, TheLoop,
+                                  RunningDepId, ASId, ShouldCheckWrap,
+                                  /*Assume=*/true)) {
           CanDoAliasSetRT = false;
           break;
         }
     }
 
     CanDoRT &= CanDoAliasSetRT;
     MayNeedRTCheck |= NeedsAliasSetRTCheck;
     ++ASId;
bool AccessAnalysis::canCheckPtrAtRT(RuntimePointerChecking &RtCheck,
   RtCheck.Need = CanDoRT ? RtCheck.getNumberOfChecks() != 0 : MayNeedRTCheck;
 
   bool CanDoRTIfNeeded = !RtCheck.Need || CanDoRT;
   if (!CanDoRTIfNeeded)
     RtCheck.reset();
   return CanDoRTIfNeeded;
 }
 
-void AccessAnalysis::processMemAccesses() {
+void AccessAnalysis::processMemAccesses(ValueToValueMap &SymbolicStrides) {
   // We process the set twice: first we process read-write pointers, last we
   // process read-only pointers. This allows us to skip dependence tests for
   // read-only pointers.
 
   LLVM_DEBUG(dbgs() << "LAA: Processing memory accesses...\n");
   LLVM_DEBUG(dbgs() << "  AST: "; AST.dump());
   LLVM_DEBUG(dbgs() << "LAA:   Accesses(" << Accesses.size() << "):\n");
   LLVM_DEBUG({
for (int SetIteration = 0; SetIteration < 2; ++SetIteration) {
 
           bool IsWrite = AC.getInt();
 
           // If we're using the deferred access set, then it contains only
           // reads.
           bool IsReadOnlyPtr = ReadOnlyPtr.count(Ptr) && !IsWrite;
           if (UseDeferred && !IsReadOnlyPtr)
             continue;
+
+          const SCEV *PtrExpr =
+              replaceSymbolicStrideSCEV(PSE, SymbolicStrides, Ptr);
           // Otherwise, the pointer must be in the PtrAccessSet, either as a
           // read or a write.
           assert(((IsReadOnlyPtr && UseDeferred) || IsWrite ||
-                  S.count(MemAccessInfo(Ptr, false))) &&
+                  S.count(MemAccessInfo(Ptr, false, PtrExpr))) &&
                  "Alias-set pointer not in the access set?");
 
-          MemAccessInfo Access(Ptr, IsWrite);
+          MemAccessInfo Access(Ptr, IsWrite, PtrExpr);
           DepCands.insert(Access);
 
           // Memorize read-only pointers for later processing and skip them in
           // the first round (they need to be checked after we have seen all
           // write pointers). Note: we also mark pointer that are not
           // consecutive as "read-only" pointers (so that we check
           // "a[b[i]] +="). Hence, we need the second check for "!IsWrite".
           if (!UseDeferred && IsReadOnlyPtr) {
if (OBO->hasNoSignedWrap() &&
       if (auto *OpAR = dyn_cast<SCEVAddRecExpr>(OpScev))
         return OpAR->getLoop() == L && OpAR->getNoWrapFlags(SCEV::FlagNSW);
     }
 
   return false;
 }
 
 /// Check whether the access through \p Ptr has a constant stride.
-int64_t llvm::getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy,
-                           Value *Ptr, const Loop *Lp,
-                           const ValueToValueMap &StridesMap, bool Assume,
-                           bool ShouldCheckWrap) {
+static int64_t getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy,
+                            Value *Ptr, const SCEV *PtrScev, const Loop *Lp,
+                            bool Assume, bool ShouldCheckWrap) {
   Type *Ty = Ptr->getType();
   assert(Ty->isPointerTy() && "Unexpected non-ptr");
   assert(!AccessTy->isAggregateType() && "Bad stride - Not a pointer to a scalar type");
 
-  const SCEV *PtrScev = replaceSymbolicStrideSCEV(PSE, StridesMap, Ptr);
-
   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev);
   if (Assume && !AR)
     AR = PSE.getAsAddRec(Ptr);
 
   if (!AR) {
     LLVM_DEBUG(dbgs() << "LAA: Bad stride - Not an AddRecExpr pointer " << *Ptr
                       << " SCEV: " << *PtrScev << "\n");
     return 0;
static int64_t getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy,
   // inverted.
   // An inbounds getelementptr that is a AddRec with a unit stride
   // cannot wrap per definition. The unit stride requirement is checked later.
   // An getelementptr without an inbounds attribute and unit stride would have
   // to access the pointer value "0" which is undefined behavior in address
   // space 0, therefore we can also vectorize this case.
   unsigned AddrSpace = Ty->getPointerAddressSpace();
   bool IsInBoundsGEP = isInBoundsGep(Ptr);
-  bool IsNoWrapAddRec = !ShouldCheckWrap ||
+  bool IsNoWrapAddRec =
+      !ShouldCheckWrap ||
       PSE.hasNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW) ||
       isNoWrapAddRec(Ptr, AR, PSE, Lp);
   if (!IsNoWrapAddRec && !IsInBoundsGEP &&
       NullPointerIsDefined(Lp->getHeader()->getParent(), AddrSpace)) {
     if (Assume) {
       PSE.setNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW);
       IsNoWrapAddRec = true;
       LLVM_DEBUG(dbgs() << "LAA: Pointer may wrap in the address space:\n"
                         << "LAA:   Pointer: " << *Ptr << "\n"
                         << "LAA:   SCEV: " << *AR << "\n"
static int64_t getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy,
   int64_t Rem = StepVal % Size;
   if (Rem)
     return 0;
 
   // If the SCEV could wrap but we have an inbounds gep with a unit stride we
   // know we can't "wrap around the address space". In case of address space
   // zero we know that this won't happen without triggering undefined behavior.
   if (!IsNoWrapAddRec && Stride != 1 && Stride != -1 &&
-      (IsInBoundsGEP || !NullPointerIsDefined(Lp->getHeader()->getParent(),
-                                              AddrSpace))) {
+      (IsInBoundsGEP ||
+       !NullPointerIsDefined(Lp->getHeader()->getParent(), AddrSpace))) {
     if (Assume) {
       // We can avoid this case by adding a run-time check.
       LLVM_DEBUG(dbgs() << "LAA: Non unit strided pointer which is not either "
                         << "inbounds or in address space 0 may wrap:\n"
                         << "LAA:   Pointer: " << *Ptr << "\n"
                         << "LAA:   SCEV: " << *AR << "\n"
                         << "LAA:   Added an overflow assumption\n");
       PSE.setNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW);
     } else
       return 0;
   }
 
   return Stride;
 }
 
+/// Check whether the access through \p Ptr has a constant stride.
+int64_t llvm::getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy,
+                           Value *Ptr, const Loop *Lp,
+                           const ValueToValueMap &StridesMap, bool Assume,
+                           bool ShouldCheckWrap) {
+  Type *Ty = Ptr->getType();
+  assert(Ty->isPointerTy() && "Unexpected non-ptr");
+  unsigned AddrSpace = Ty->getPointerAddressSpace();
+
+  // Make sure we're not accessing an aggregate type.
+  // TODO: Why? This doesn't make any sense.
+  if (AccessTy->isAggregateType()) {
+    LLVM_DEBUG(dbgs() << "LAA: Bad stride - Not a pointer to a scalar type"
+                      << *Ptr << "\n");
+    return 0;
+  }
+
+  const SCEV *PtrScev = replaceSymbolicStrideSCEV(PSE, StridesMap, Ptr);
+  return ::getPtrStride(PSE, AccessTy, Ptr, PtrScev, Lp, Assume,
+                        ShouldCheckWrap);
+}
+
 Optional<int> llvm::getPointersDiff(Type *ElemTyA, Value *PtrA, Type *ElemTyB,
                                     Value *PtrB, const DataLayout &DL,
                                     ScalarEvolution &SE, bool StrictCheck,
                                     bool CheckType) {
   assert(PtrA && PtrB && "Expected non-nullptr pointers.");
   assert(cast<PointerType>(PtrA->getType())
              ->isOpaqueOrPointeeTypeMatches(ElemTyA) && "Wrong PtrA type");
   assert(cast<PointerType>(PtrB->getType())
if (!PtrA || !PtrB)
     return false;
   Type *ElemTyA = getLoadStoreType(A);
   Type *ElemTyB = getLoadStoreType(B);
   Optional<int> Diff = getPointersDiff(ElemTyA, PtrA, ElemTyB, PtrB, DL, SE,
                                        /*StrictCheck=*/true, CheckType);
   return Diff && *Diff == 1;
 }
 
-void MemoryDepChecker::addAccess(StoreInst *SI) {
-  visitPointers(SI->getPointerOperand(), *InnermostLoop,
-                [this, SI](Value *Ptr) {
-                  Accesses[MemAccessInfo(Ptr, true)].push_back(AccessIdx);
+void MemoryDepChecker::addAccess(StoreInst *SI,
+                                 const ValueToValueMap &SymbolicStrides) {
+  visitPointers(SI->getPointerOperand(), *InnermostLoop, PSE, SymbolicStrides,
+                [this, SI](Value *Ptr, const SCEV *PtrScev) {
+                  Accesses[MemAccessInfo(Ptr, true, PtrScev)].push_back(
+                      AccessIdx);
                   InstMap.push_back(SI);
                   ++AccessIdx;
                 });
 }
 
-void MemoryDepChecker::addAccess(LoadInst *LI) {
-  visitPointers(LI->getPointerOperand(), *InnermostLoop,
-                [this, LI](Value *Ptr) {
-                  Accesses[MemAccessInfo(Ptr, false)].push_back(AccessIdx);
+void MemoryDepChecker::addAccess(LoadInst *LI,
+                                 const ValueToValueMap &SymbolicStrides) {
+  visitPointers(LI->getPointerOperand(), *InnermostLoop, PSE, SymbolicStrides,
+                [this, LI](Value *Ptr, const SCEV *PtrScev) {
+                  Accesses[MemAccessInfo(Ptr, false, PtrScev)].push_back(
+                      AccessIdx);
                   InstMap.push_back(LI);
                   ++AccessIdx;
                 });
 }
 
 MemoryDepChecker::VectorizationSafetyStatus
 MemoryDepChecker::Dependence::isSafeForVectorization(DepType Type) {
   switch (Type) {
MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
   return Dependence::BackwardVectorizable;
 }
 
 bool MemoryDepChecker::areDepsSafe(DepCandidates &AccessSets,
                                    MemAccessInfoList &CheckDeps,
                                    const ValueToValueMap &Strides) {
 
   MaxSafeDepDistBytes = -1;
-  SmallPtrSet<MemAccessInfo, 8> Visited;
+  SmallPtrSet<const MemAccessInfo *, 8> Visited;
   for (MemAccessInfo CurAccess : CheckDeps) {
-    if (Visited.count(CurAccess))
+    if (Visited.count(&CurAccess))
       continue;
 
     // Get the relevant memory access set.
     EquivalenceClasses<MemAccessInfo>::iterator I =
       AccessSets.findValue(AccessSets.getLeaderValue(CurAccess));
 
     // Check accesses within this set.
     EquivalenceClasses<MemAccessInfo>::member_iterator AI =
         AccessSets.member_begin(I);
     EquivalenceClasses<MemAccessInfo>::member_iterator AE =
         AccessSets.member_end();
 
     // Check every access pair.
     while (AI != AE) {
-      Visited.insert(*AI);
+      Visited.insert(&*AI);
       bool AIIsWrite = AI->getInt();
       // Check loads only against next equivalent class, but stores also against
       // other stores in the same equivalence class - to the same address.
       EquivalenceClasses<MemAccessInfo>::member_iterator OI =
           (AIIsWrite ? AI : std::next(AI));
       while (OI != AE) {
         // Check every accessing instruction pair in program order.
         for (std::vector<unsigned>::iterator I1 = Accesses[*AI].begin(),
while (AI != AE) {
       AI++;
     }
   }
 
   LLVM_DEBUG(dbgs() << "Total Dependences: " << Dependences.size() << "\n");
   return isSafeForVectorization();
 }
 
-SmallVector<Instruction *, 4>
-MemoryDepChecker::getInstructionsForAccess(Value *Ptr, bool isWrite) const {
-  MemAccessInfo Access(Ptr, isWrite);
-  auto &IndexVector = Accesses.find(Access)->second;
-
+SmallVector<Instruction *, 4> MemoryDepChecker::getInstructionsForAccess(
+    Value *Ptr, bool isWrite, const ValueToValueMap &SymbolicStrides) const {
   SmallVector<Instruction *, 4> Insts;
-  transform(IndexVector,
-                 std::back_inserter(Insts),
-                 [&](unsigned Idx) { return this->InstMap[Idx]; });
+  for (auto &KV : Accesses) {
+    if (KV.first.getPointer() == Ptr) {
+      auto &IndexVector = KV.second;
+
+      transform(IndexVector, std::back_inserter(Insts),
+    }
+  }
   return Insts;
 }
 
 const char *MemoryDepChecker::Dependence::DepName[] = {
     "NoDep", "Unknown", "Forward", "ForwardButPreventsForwarding", "Backward",
     "BackwardVectorizable", "BackwardVectorizableButPreventsForwarding"};
 
 void MemoryDepChecker::Dependence::print(
for (Instruction &I : *BB) {
           recordAnalysis("NonSimpleLoad", Ld)
               << "read with atomic ordering or volatile read";
           LLVM_DEBUG(dbgs() << "LAA: Found a non-simple load.\n");
           HasComplexMemInst = true;
           continue;
         }
         NumLoads++;
         Loads.push_back(Ld);
-        DepChecker->addAccess(Ld);
         if (EnableMemAccessVersioningOfLoop)
           collectStridedAccess(Ld);
+
+        DepChecker->addAccess(Ld, SymbolicStrides);
         continue;
       }
 
       // Save 'store' instructions. Abort if other instructions write to memory.
       if (I.mayWriteToMemory()) {
         auto *St = dyn_cast<StoreInst>(&I);
         if (!St) {
           recordAnalysis("CantVectorizeInstruction", St)
               << "instruction cannot be vectorized";
           HasComplexMemInst = true;
           continue;
         }
         if (!St->isSimple() && !IsAnnotatedParallel) {
           recordAnalysis("NonSimpleStore", St)
               << "write with atomic ordering or volatile write";
           LLVM_DEBUG(dbgs() << "LAA: Found a non-simple store.\n");
           HasComplexMemInst = true;
           continue;
         }
         NumStores++;
         Stores.push_back(St);
-        DepChecker->addAccess(St);
+
         if (EnableMemAccessVersioningOfLoop)
           collectStridedAccess(St);
+
+        DepChecker->addAccess(St, SymbolicStrides);
       }
     } // Next instr.
   } // Next block.
 
   if (HasComplexMemInst) {
     CanVecMem = false;
     return;
   }
if (Seen.insert(Ptr).second) {
 
       MemoryLocation Loc = MemoryLocation::get(ST);
       // The TBAA metadata could have a control dependency on the predication
       // condition, so we cannot rely on it when determining whether or not we
       // need runtime pointer checks.
       if (blockNeedsPredication(ST->getParent(), TheLoop, DT))
         Loc.AATags.TBAA = nullptr;
 
-      visitPointers(const_cast<Value *>(Loc.Ptr), *TheLoop,
-                    [&Accesses, Loc](Value *Ptr) {
+      visitPointers(const_cast<Value *>(Loc.Ptr), *TheLoop, *PSE,
+                    SymbolicStrides,
+                    [&Accesses, Loc](Value *Ptr, const SCEV *PtrScev) {
                       MemoryLocation NewLoc = Loc.getWithNewPtr(Ptr);
-                      Accesses.addStore(NewLoc);
+                      Accesses.addStore(NewLoc, PtrScev);
                     });
     }
   }
 
   if (IsAnnotatedParallel) {
     LLVM_DEBUG(
         dbgs() << "LAA: A loop annotated parallel, ignore memory dependency "
                << "checks.\n");
for (LoadInst *LD : Loads) {
 
     MemoryLocation Loc = MemoryLocation::get(LD);
     // The TBAA metadata could have a control dependency on the predication
     // condition, so we cannot rely on it when determining whether or not we
     // need runtime pointer checks.
     if (blockNeedsPredication(LD->getParent(), TheLoop, DT))
       Loc.AATags.TBAA = nullptr;
 
-    visitPointers(const_cast<Value *>(Loc.Ptr), *TheLoop,
-                  [&Accesses, Loc, IsReadOnlyPtr](Value *Ptr) {
-                    MemoryLocation NewLoc = Loc.getWithNewPtr(Ptr);
-                    Accesses.addLoad(NewLoc, IsReadOnlyPtr);
-                  });
+    visitPointers(
+        const_cast<Value *>(Loc.Ptr), *TheLoop, *PSE, SymbolicStrides,
+        [&Accesses, Loc, IsReadOnlyPtr](Value *Ptr, const SCEV *PtrScev) {
+          Accesses.addLoad(NewLoc, IsReadOnlyPtr, PtrScev);
   }
 
   // If we write (or read-write) to a single destination and there are no
   // other reads in this loop then is it safe to vectorize.
   if (NumReadWrites == 1 && NumReads == 0) {
     LLVM_DEBUG(dbgs() << "LAA: Found a write-only loop!\n");
     CanVecMem = true;
     return;
   }
 
   // Build dependence sets and check whether we need a runtime pointer bounds
   // check.
-  Accesses.buildDependenceSets();
+  Accesses.buildDependenceSets(SymbolicStrides);
 
   // Find pointers with computable bounds. We are going to use this information
   // to place a runtime bound check.
   bool CanDoRTIfNeeded = Accesses.canCheckPtrAtRT(*PtrRtChecking, PSE->getSE(),
                                                   TheLoop, SymbolicStrides);
   if (!CanDoRTIfNeeded) {
     recordAnalysis("CantIdentifyArrayBounds") << "cannot identify array bounds";
     LLVM_DEBUG(dbgs() << "LAA: We can't vectorize because we can't find "

llvm/lib/Transforms/Scalar/LoopDistribute.cpp

public:
   SmallVector<int, 8>
   computePartitionSetForPointers(const LoopAccessInfo &LAI) {
     const RuntimePointerChecking *RtPtrCheck = LAI.getRuntimePointerChecking();
 
     unsigned N = RtPtrCheck->Pointers.size();
     SmallVector<int, 8> PtrToPartitions(N);
     for (unsigned I = 0; I < N; ++I) {
       Value *Ptr = RtPtrCheck->Pointers[I].PointerValue;
-      auto Instructions =
-          LAI.getInstructionsForAccess(Ptr, RtPtrCheck->Pointers[I].IsWritePtr);
+      auto Instructions = LAI.getInstructionsForAccess(
+          Ptr, RtPtrCheck->Pointers[I].IsWritePtr, LAI.getSymbolicStrides());
 
       int &Partition = PtrToPartitions[I];
       // First set it to uninitialized.
       Partition = -2;
       for (Instruction *Inst : Instructions) {
         // Note that this could be -1 if Inst is duplicated across multiple
         // partitions.
         int ThisPartition = this->InstToPartitionId[Inst];

llvm/test/Analysis/LoopAccessAnalysis/pointer-phis.ll

 ; CHECK-LABEL: 'store_with_pointer_phi_incoming_phi'
 ; CHECK-NEXT:  loop.header:
 ; CHECK-NEXT:    Report: unsafe dependent memory operations in loop. Use #pragma loop distribute(enable) to allow loop distribution to attempt to isolate the offending operations into a separate loop
 ; CHECK-NEXT:    Dependences:
 ; CHECK-NEXT:      Unknown:
 ; CHECK-NEXT:          %v8 = load double, double* %arrayidx, align 8 ->
 ; CHECK-NEXT:          store double %mul16, double* %ptr.2, align 8
 ; CHECK-EMPTY:
+; CHECK-NEXT:      Unknown:
+; CHECK-NEXT:          %v8 = load double, double* %arrayidx, align 8 ->
+; CHECK-NEXT:          store double %mul16, double* %ptr.2, align 8
+; CHECK-EMPTY:
 ; CHECK-NEXT:    Run-time memory checks:
 ; CHECK-NEXT:    Check 0:
 ; CHECK-NEXT:      Comparing group ([[GROUP_C:.+]]):
 ; CHECK-NEXT:      double* %C
 ; CHECK-NEXT:      Against group ([[GROUP_B:.+]]):
 ; CHECK-NEXT:      double* %B
 ; CHECK-NEXT:    Check 1:
 ; CHECK-NEXT:      Comparing group ([[GROUP_C]]):

 ; CHECK-LABEL: 'store_with_pointer_phi_incoming_phi_irreducible_cycle'
 ; CHECK-NEXT:  loop.header:
 ; CHECK-NEXT:    Report: unsafe dependent memory operations in loop. Use #pragma loop distribute(enable) to allow loop distribution to attempt to isolate the offending operations into a separate loop
 ; CHECK-NEXT:    Dependences:
 ; CHECK-NEXT:      Unknown:
 ; CHECK-NEXT:          %v8 = load double, double* %arrayidx, align 8 ->
 ; CHECK-NEXT:          store double %mul16, double* %ptr.3, align 8
 ; CHECK-EMPTY:
+; CHECK-NEXT:      Unknown:
+; CHECK-NEXT:          %v8 = load double, double* %arrayidx, align 8 ->
+; CHECK-NEXT:          store double %mul16, double* %ptr.3, align 8
+; CHECK-EMPTY:
 ; CHECK-NEXT:    Run-time memory checks:
 ; CHECK-NEXT:    Check 0:
 ; CHECK-NEXT:      Comparing group ([[GROUP_C:.+]]):
 ; CHECK-NEXT:      double* %C
 ; CHECK-NEXT:      Against group ([[GROUP_B:.+]]):
 ; CHECK-NEXT:      double* %B
 ; CHECK-NEXT:    Check 1:
 ; CHECK-NEXT:      Comparing group ([[GROUP_C]]):

 ; CHECK-NEXT:      Unknown:
 ; CHECK-NEXT:          %lv = load i16, i16* %A, align 1 ->
 ; CHECK-NEXT:          store i16 %lv, i16* %A, align 1
 ; CHECK-EMPTY:
 ; CHECK-NEXT:      Unknown:
 ; CHECK-NEXT:          store i16 %lv, i16* %A, align 1 ->
 ; CHECK-NEXT:          %lv2 = load i16, i16* %A, align 1
 ; CHECK-EMPTY:
+; CHECK-NEXT:      Unknown:
+; CHECK-NEXT:          %lv3 = load i16, i16* %c.sink, align 2 ->
+; CHECK-NEXT:          store i16 %add, i16* %c.sink, align 1
+; CHECK-EMPTY:
+; CHECK-NEXT:      Unknown:
+; CHECK-NEXT:          %lv3 = load i16, i16* %c.sink, align 2 ->
+; CHECK-NEXT:          store i16 %add, i16* %c.sink, align 1
+; CHECK-EMPTY:
 ; CHECK-NEXT:    Run-time memory checks:
 ; CHECK-NEXT:    Check 0:
 ; CHECK-NEXT:      Comparing group ([[GROUP_A:.+]]):
 ; CHECK-NEXT:      i16* %A
 ; CHECK-NEXT:      i16* %A
 ; CHECK-NEXT:      Against group ([[GROUP_C:.+]]):
 ; CHECK-NEXT:      i16* %C
 ; CHECK-NEXT:      i16* %C

llvm/test/Transforms/LoopLoadElim/symbolic-stride.ll

 ;
 ;   for (unsigned i = 0; i < 100; i++)
 ;     A[Stride2 * (i + 1)] = A[Stride1 * i] + B[i];
 
 ; ALL-LABEL: @two_strides(
 define void @two_strides(i32* noalias nocapture %A, i32* noalias nocapture readonly %B, i64 %N,
                          i64 %stride.1, i64 %stride.2) {
 
-; TWO_STRIDE_SPEC: %ident.check = icmp ne i64 %stride.2, 1
-; TWO_STRIDE_SPEC: %ident.check1 = icmp ne i64 %stride.1, 1
+; TWO_STRIDE_SPEC: %ident.check = icmp ne i64 %stride.1, 1
+; TWO_STRIDE_SPEC: %ident.check1 = icmp ne i64 %stride.2, 1
 ; NO_TWO_STRIDE_SPEC-NOT: %ident.check{{.*}} = icmp ne i64 %stride{{.*}}, 1
 
 entry:
 ; NO_TWO_STRIDE_SPEC-NOT: %load_initial = load i32, i32* %A
 ; TWO_STRIDE_SPEC: %load_initial = load i32, i32* %A
   br label %for.body
 
 for.body:                                         ; preds = %for.body, %entry