[LAA] Keep track of ptr SCEV related to MemAccessInfo

[Allen]

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, rebase on fhahn's D114479.

co-author: fhahn

[Allen]

hi @fhahn, because D158493 requires this PR precommited, so would you give some suggestion?

llvm/include/llvm/Analysis/LoopAccessAnalysis.h

   /// 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 {

                const SmallVectorImpl<Instruction *> &Instrs) const;
   };
 
   MemoryDepChecker(PredicatedScalarEvolution &PSE, const Loop *L)
       : PSE(PSE), InnermostLoop(L) {}
 
   /// Register the location (instructions are given increasing numbers)
   /// of a write access.
-  void addAccess(StoreInst *SI);
+  void addAccess(StoreInst *SI,
+                 const DenseMap<Value *, const SCEV *> &SymbolicStrides);
 
   /// Register the location (instructions are given increasing numbers)
   /// of a write access.
-  void addAccess(LoadInst *LI);
+  void addAccess(LoadInst *LI,
+                 const DenseMap<Value *, const SCEV *> &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 DenseMap<Value *, const SCEV *> &Strides);
 
   /// No memory dependence was encountered that would inhibit

 
   /// Find the set of instructions that read or write via \p Ptr.
   SmallVector<Instruction *, 4> getInstructionsForAccess(Value *Ptr,
                                                          bool isWrite) const;
 
   /// Return the program order indices for the access location (Ptr, IsWrite).
   /// Returns an empty ArrayRef if there are no accesses for the location.
   ArrayRef<unsigned> getOrderForAccess(Value *Ptr, bool IsWrite) const {
-    auto I = Accesses.find({Ptr, IsWrite});
-    if (I != Accesses.end())
-      return I->second;
+    for (auto &KV : Accesses) {
+      if (KV.first.getPointer() == Ptr && KV.first.getInt() == IsWrite) {
+        return KV.second;
+      }
+    }
     return {};
   }
 
   const Loop *getInnermostLoop() const { return InnermostLoop; }
 
 private:
   /// A wrapper around ScalarEvolution, used to add runtime SCEV checks, and
   /// applies dynamic knowledge to simplify SCEV expressions and convert them

     const SCEV *End;
     /// Holds the information if this pointer is used for writing to memory.
     bool IsWritePtr;
     /// 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.
+    /// SCEV for the computable bounds access
     const SCEV *Expr;
+    /// SCEV for the access.
+    const SCEV *PtrExpr;
     /// True if the pointer expressions needs to be frozen after expansion.
     bool NeedsFreeze;
 
     PointerInfo(Value *PointerValue, const SCEV *Start, const SCEV *End,
                 bool IsWritePtr, unsigned DependencySetId, unsigned AliasSetId,
-                const SCEV *Expr, bool NeedsFreeze)
+                const SCEV *Expr, const SCEV *PtrExpr, bool NeedsFreeze)
         : PointerValue(PointerValue), Start(Start), End(End),
           IsWritePtr(IsWritePtr), DependencySetId(DependencySetId),
-          AliasSetId(AliasSetId), Expr(Expr), NeedsFreeze(NeedsFreeze) {}
+          AliasSetId(AliasSetId), Expr(Expr), PtrExpr(PtrExpr),
+          NeedsFreeze(NeedsFreeze) {}
   };
 
   RuntimePointerChecking(MemoryDepChecker &DC, ScalarEvolution *SE)
       : DC(DC), 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, const SCEV *PtrExpr, Type *AccessTy,
-              bool WritePtr, unsigned DepSetId, unsigned ASId,
+  void insert(Loop *Lp, Value *Ptr, const SCEV *PtrExpr, const SCEV *Sc,
+              Type *AccessTy, bool WritePtr, unsigned DepSetId, unsigned ASId,
               PredicatedScalarEvolution &PSE, bool NeedsFreeze);
 
   /// 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,

 /// to \p PtrToStride and therefore add further predicates to \p PSE.
 /// The \p Assume parameter indicates if we are allowed to make additional
 /// run-time assumptions.
 ///
 /// Note that the analysis results are defined if-and-only-if the original
 /// memory access was defined.  If that access was dead, or UB, then the
 /// result of this function is undefined.
 std::optional<int64_t>
+getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy, Value *Ptr,
+             const SCEV *PtrScev, const Loop *Lp,
+             const DenseMap<Value *, const SCEV *> &StridesMap =
+                 DenseMap<Value *, const SCEV *>(),
+             bool Assume = false, bool ShouldCheckWrap = true);
+std::optional<int64_t>
 getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy, Value *Ptr,
              const Loop *Lp,
-             const DenseMap<Value *, const SCEV *> &StridesMap = DenseMap<Value *, const SCEV *>(),
+             const DenseMap<Value *, const SCEV *> &StridesMap =
+                 DenseMap<Value *, const SCEV *>(),
              bool Assume = false, bool ShouldCheckWrap = true);
 
 /// Returns the distance between the pointers \p PtrA and \p PtrB iff they are
 /// compatible and it is possible to calculate the distance between them. This
 /// is a simple API that does not depend on the analysis pass.
 /// \param StrictCheck Ensure that the calculated distance matches the
 /// type-based one after all the bitcasts removal in the provided pointers.
 std::optional<int> getPointersDiff(Type *ElemTyA, Value *PtrA, Type *ElemTyB,

llvm/lib/Analysis/LoopAccessAnalysis.cpp

 ///     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, const SCEV *PtrExpr,
-                                    Type *AccessTy, bool WritePtr,
-                                    unsigned DepSetId, unsigned ASId,
+                                    const SCEV *Sc, Type *AccessTy,
+                                    bool WritePtr, unsigned DepSetId,
+                                    unsigned ASId,
                                     PredicatedScalarEvolution &PSE,
                                     bool NeedsFreeze) {
   ScalarEvolution *SE = PSE.getSE();
 
   const SCEV *ScStart;
   const SCEV *ScEnd;
 
-  if (SE->isLoopInvariant(PtrExpr, Lp)) {
-    ScStart = ScEnd = PtrExpr;
+  if (SE->isLoopInvariant(Sc, Lp)) {
+    ScStart = ScEnd = Sc;
   } else {
-    const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrExpr);
+    const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Sc);
     assert(AR && "Invalid addrec expression");
     const SCEV *Ex = PSE.getBackedgeTakenCount();
 
     ScStart = AR->getStart();
     ScEnd = AR->evaluateAtIteration(Ex, *SE);
     const SCEV *Step = AR->getStepRecurrence(*SE);
 
     // For expressions with negative step, the upper bound is ScStart and the
     // lower bound is ScEnd.
     if (const auto *CStep = dyn_cast<SCEVConstant>(Step)) {
       if (CStep->getValue()->isNegative())
         std::swap(ScStart, ScEnd);
     } else {
       // Fallback case: the step is not constant, but we can still
       // get the upper and lower bounds of the interval by using min/max
       // expressions.
       ScStart = SE->getUMinExpr(ScStart, ScEnd);
       ScEnd = SE->getUMaxExpr(AR->getStart(), ScEnd);
     }
   }
   assert(SE->isLoopInvariant(ScStart, Lp) && "ScStart needs to be invariant");
-  assert(SE->isLoopInvariant(ScEnd, Lp)&& "ScEnd needs to be invariant");
+  assert(SE->isLoopInvariant(ScEnd, Lp) && "ScEnd needs to be invariant");
 
   // 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, AccessTy);
   ScEnd = SE->getAddExpr(ScEnd, EltSizeSCEV);
 
-  Pointers.emplace_back(Ptr, ScStart, ScEnd, WritePtr, DepSetId, ASId, PtrExpr,
-                        NeedsFreeze);
+  Pointers.emplace_back(Ptr, ScStart, ScEnd, WritePtr, DepSetId, ASId, Sc,
+                        PtrExpr, NeedsFreeze);
 }
 
 void RuntimePointerChecking::tryToCreateDiffCheck(
     const RuntimeCheckingPtrGroup &CGI, const RuntimeCheckingPtrGroup &CGJ) {
   if (!CanUseDiffCheck)
     return;
 
   // If either group contains multiple different pointers, bail out.

   SmallVector<Instruction *, 4> SinkInsts =
       DC.getInstructionsForAccess(Sink->PointerValue, Sink->IsWritePtr);
   Type *SrcTy = getLoadStoreType(SrcInsts[0]);
   Type *DstTy = getLoadStoreType(SinkInsts[0]);
   if (isa<ScalableVectorType>(SrcTy) || isa<ScalableVectorType>(DstTy)) {
     CanUseDiffCheck = false;
     return;
   }
+
   const DataLayout &DL =
       SinkAR->getLoop()->getHeader()->getModule()->getDataLayout();
   unsigned AllocSize =
       std::max(DL.getTypeAllocSize(SrcTy), DL.getTypeAllocSize(DstTy));
 
   // Only matching constant steps matching the AllocSize are supported at the
   // moment. This simplifies the difference computation. Can be extended in the
   // future.

   // 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

 
 /// 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), BAA(*AA), AST(BAA), LI(LI), DepCands(DA), PSE(PSE) {
     // We're analyzing dependences across loop iterations.
     BAA.enableCrossIterationMode();
   }
 
   /// Register a load  and whether it is only read from.
-  void addLoad(MemoryLocation &Loc, Type *AccessTy, bool IsReadOnly) {
-    Value *Ptr = const_cast<Value*>(Loc.Ptr);
+  void addLoad(MemoryLocation &Loc, Type *AccessTy, bool IsReadOnly,
+               const SCEV *PtrScev) {
+    Value *Ptr = const_cast<Value *>(Loc.Ptr);
     AST.add(Ptr, LocationSize::beforeOrAfterPointer(), Loc.AATags);
-    Accesses[MemAccessInfo(Ptr, false)].insert(AccessTy);
+    Accesses[MemAccessInfo(Ptr, false, PtrScev)].insert(AccessTy);
     if (IsReadOnly)
       ReadOnlyPtr.insert(Ptr);
   }
 
   /// Register a store.
-  void addStore(MemoryLocation &Loc, Type *AccessTy) {
-    Value *Ptr = const_cast<Value*>(Loc.Ptr);
+  void addStore(MemoryLocation &Loc, Type *AccessTy, const SCEV *PtrScev) {
+    Value *Ptr = const_cast<Value *>(Loc.Ptr);
     AST.add(Ptr, LocationSize::beforeOrAfterPointer(), Loc.AATags);
-    Accesses[MemAccessInfo(Ptr, true)].insert(AccessTy);
+    Accesses[MemAccessInfo(Ptr, true, PtrScev)].insert(AccessTy);
   }
 
   /// 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, Type *AccessTy,
                             const DenseMap<Value *, const SCEV *> &Strides,
-                            DenseMap<Value *, unsigned> &DepSetId,
+                            DenseMap<const SCEV *, unsigned> &DepSetId,
                             Loop *TheLoop, unsigned &RunningDepId,
                             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 DenseMap<Value *, const SCEV *> &Strides,
                        Value *&UncomputablePtr, 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(DenseMap<Value *, const SCEV *> &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 MapVector<MemAccessInfo, SmallSetVector<Type *, 1>> PtrAccessMap;
 
   /// Go over all memory access and check whether runtime pointer checks
   /// are needed and build sets of dependency check candidates.
-  void processMemAccesses();
+  void processMemAccesses(DenseMap<Value *, const SCEV *> &SymbolicStrides);
 
   /// Map of all accesses. Values are the types used to access memory pointed to
   /// by the pointer.
   PtrAccessMap Accesses;
 
   /// The loop being checked.
   const Loop *TheLoop;
 

   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, Value *Ptr,
-                                const SCEV *PtrScev, Loop *L, bool Assume) {
+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;
+  if (AR && AR->isAffine())
+    return AR;
 
-  return AR->isAffine();
+  return nullptr;
 }
 
 /// Check whether a pointer address cannot wrap.
-static bool isNoWrap(PredicatedScalarEvolution &PSE,
-                     const DenseMap<Value *, const SCEV *> &Strides, Value *Ptr, Type *AccessTy,
-                     Loop *L) {
-  const SCEV *PtrScev = PSE.getSCEV(Ptr);
+static bool isNoWrap(PredicatedScalarEvolution &PSE, Value *Ptr,
+                     const SCEV *PtrScev, Type *AccessTy, Loop *L) {
+  // const SCEV *PtrScev = PSE.getSCEV(Ptr);
   if (PSE.getSE()->isLoopInvariant(PtrScev, L))
     return true;
 
-  int64_t Stride = getPtrStride(PSE, AccessTy, Ptr, L, Strides).value_or(0);
+  int64_t Stride = getPtrStride(PSE, AccessTy, Ptr, PtrScev, L).value_or(0);
   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 DenseMap<Value *, const SCEV *> &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));
   }
 }
 
 // Walk back through the IR for a pointer, looking for a select like the
 // following:
 //
 //  %offset = select i1 %cmp, i64 %a, i64 %b
 //  %addr = getelementptr double, double* %base, i64 %offset

     LLVM_DEBUG(dbgs() << "\t(1) " << *get<0>(Scevs[0]) << "\n");
     LLVM_DEBUG(dbgs() << "\t(2) " << *get<0>(Scevs[1]) << "\n");
     return Scevs;
   }
 
   return {{replaceSymbolicStrideSCEV(PSE, StridesMap, Ptr), false}};
 }
 
-bool AccessAnalysis::createCheckForAccess(RuntimePointerChecking &RtCheck,
-                                          MemAccessInfo Access, Type *AccessTy,
-                                          const DenseMap<Value *, const SCEV *> &StridesMap,
-                                          DenseMap<Value *, unsigned> &DepSetId,
-                                          Loop *TheLoop, unsigned &RunningDepId,
-                                          unsigned ASId, bool ShouldCheckWrap,
-                                          bool Assume) {
+bool AccessAnalysis::createCheckForAccess(
+    RuntimePointerChecking &RtCheck, MemAccessInfo Access, Type *AccessTy,
+    DenseMap<const SCEV *, unsigned> &DepSetId, Loop *TheLoop,
+    unsigned &RunningDepId, unsigned ASId, bool ShouldCheckWrap, bool Assume) {
   Value *Ptr = Access.getPointer();
 
   SmallVector<PointerIntPair<const SCEV *, 1, bool>> TranslatedPtrs =
       findForkedPointer(PSE, StridesMap, Ptr, TheLoop);
 
-  for (auto &P : TranslatedPtrs) {
-    const SCEV *PtrExpr = get<0>(P);
-    if (!hasComputableBounds(PSE, Ptr, PtrExpr, TheLoop, Assume))
+  for (auto [PtrExpr, NeedsFreeze] : TranslatedPtrs) {
+    const SCEV *PtrScev =
+        hasComputableBounds(PSE, Ptr, PtrExpr, 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) {
       // Skip wrap checking when translating pointers.
       if (TranslatedPtrs.size() > 1)
         return false;
 
-      if (!isNoWrap(PSE, StridesMap, Ptr, AccessTy, TheLoop)) {
-        auto *Expr = PSE.getSCEV(Ptr);
-        if (!Assume || !isa<SCEVAddRecExpr>(Expr))
+      if (!isNoWrap(PSE, Ptr, PtrScev, AccessTy, TheLoop)) {
+        // auto *Expr = PSE.getSCEV(Ptr);
+        if (!Assume || !isa<SCEVAddRecExpr>(PtrScev))
           return false;
         PSE.setNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW);
       }
     }
     // If there's only one option for Ptr, look it up after bounds and wrap
     // checking, because assumptions might have been added to PSE.
     if (TranslatedPtrs.size() == 1)
       TranslatedPtrs[0] = {replaceSymbolicStrideSCEV(PSE, StridesMap, Ptr),
                            false};
-  }
 
-  for (auto [PtrExpr, NeedsFreeze] : TranslatedPtrs) {
     // 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, PtrExpr, AccessTy, IsWrite, DepId, ASId, PSE,
-                   NeedsFreeze);
+    RtCheck.insert(TheLoop, Ptr, PtrExpr, PtrScev, AccessTy, IsWrite, DepId,
+                   ASId, PSE, NeedsFreeze);
     LLVM_DEBUG(dbgs() << "LAA: Found a runtime check ptr:" << *Ptr << '\n');
   }
 
   return true;
 }
 
 bool AccessAnalysis::canCheckPtrAtRT(RuntimePointerChecking &RtCheck,
                                      ScalarEvolution *SE, Loop *TheLoop,

     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<std::pair<MemAccessInfo, Type *>, 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) {

   RtCheck.Need = CanDoRT ? RtCheck.getNumberOfChecks() != 0 : MayNeedRTCheck;
 
   bool CanDoRTIfNeeded = !RtCheck.Need || CanDoRT;
   if (!CanDoRTIfNeeded)
     RtCheck.reset();
   return CanDoRTIfNeeded;
 }
 
-void AccessAnalysis::processMemAccesses() {
+void AccessAnalysis::processMemAccesses(
+    DenseMap<Value *, const SCEV *> &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({

 
           bool IsWrite = AC.first.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 (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.
-std::optional<int64_t> llvm::getPtrStride(PredicatedScalarEvolution &PSE,
-                                          Type *AccessTy, Value *Ptr,
-                                          const Loop *Lp,
-                                          const DenseMap<Value *, const SCEV *> &StridesMap,
-                                          bool Assume, bool ShouldCheckWrap) {
+std::optional<int64_t>
+llvm::getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy, Value *Ptr,
+                   const SCEV *PtrScev, const Loop *Lp,
   Type *Ty = Ptr->getType();
   assert(Ty->isPointerTy() && "Unexpected non-ptr");
 
   if (isa<ScalableVectorType>(AccessTy)) {
     LLVM_DEBUG(dbgs() << "LAA: Bad stride - Scalable object: " << *AccessTy
                       << "\n");
     return std::nullopt;
   }
 
-  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 std::nullopt;

     return Stride;
   }
   LLVM_DEBUG(
       dbgs() << "LAA: Bad stride - Pointer may wrap in the address space "
              << *Ptr << " SCEV: " << *AR << "\n");
   return std::nullopt;
 }
 
+/// Check whether the access through \p Ptr has a constant stride.
+std::optional<int64_t>
+llvm::getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy, Value *Ptr,
+                   const Loop *Lp,
+                   const DenseMap<Value *, const SCEV *> &StridesMap,
+                   bool Assume, bool ShouldCheckWrap) {
+  Type *Ty = Ptr->getType();
+  assert(Ty->isPointerTy() && "Unexpected non-ptr");
+
+  const SCEV *PtrScev = replaceSymbolicStrideSCEV(PSE, StridesMap, Ptr);
+  return ::getPtrStride(PSE, AccessTy, Ptr, PtrScev, Lp, StridesMap, Assume,
+                        ShouldCheckWrap);
+}
+
 std::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.");
 
   // Make sure that A and B are different pointers.

   Type *ElemTyA = getLoadStoreType(A);
   Type *ElemTyB = getLoadStoreType(B);
   std::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 DenseMap<Value *, const SCEV *> &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 DenseMap<Value *, const SCEV *> &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::Dependence::DepType
 MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
                               const MemAccessInfo &B, unsigned BIdx,
                               const DenseMap<Value *, const SCEV *> &Strides) {
   assert (AIdx < BIdx && "Must pass arguments in program order");
 
-  auto [APtr, AIsWrite] = A;
-  auto [BPtr, BIsWrite] = B;
+  auto [AAccess, APtrExpr] = A;
+  auto [BAccess, BPtrExpr] = B;
   Type *ATy = getLoadStoreType(InstMap[AIdx]);
   Type *BTy = getLoadStoreType(InstMap[BIdx]);
+  auto APtr = AAccess.getPointer();
+  auto BPtr = BAccess.getPointer();
+  auto AIsWrite = AAccess.getInt();
+  auto BIsWrite = BAccess.getInt();
 
   // Two reads are independent.
   if (!AIsWrite && !BIsWrite)
     return Dependence::NoDep;
 
   // We cannot check pointers in different address spaces.
   if (APtr->getType()->getPointerAddressSpace() !=
       BPtr->getType()->getPointerAddressSpace())

   uint64_t MaxVFInBits = MaxVF * TypeByteSize * 8;
   MaxSafeVectorWidthInBits = std::min(MaxSafeVectorWidthInBits, MaxVFInBits);
   return Dependence::BackwardVectorizable;
 }
 
 bool MemoryDepChecker::areDepsSafe(DepCandidates &AccessSets,
                                    MemAccessInfoList &CheckDeps,
                                    const DenseMap<Value *, const SCEV *> &Strides) {
-
   MinDepDistBytes = -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(),

   }
 
   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> 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),
+                [&](unsigned Idx) { return this->InstMap[Idx]; });
+    }
+  }
   return Insts;
 }
 
 const char *MemoryDepChecker::Dependence::DepName[] = {
     "NoDep", "Unknown", "Forward", "ForwardButPreventsForwarding", "Backward",
     "BackwardVectorizable", "BackwardVectorizableButPreventsForwarding"};
 
 void MemoryDepChecker::Dependence::print(

           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;
   }

 
       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, AccessTy, Loc](Value *Ptr) {
-                      MemoryLocation NewLoc = Loc.getWithNewPtr(Ptr);
-                      Accesses.addStore(NewLoc, AccessTy);
-                    });
+      visitPointers(
+          const_cast<Value *>(Loc.Ptr), *TheLoop, *PSE, SymbolicStrides,
+          [&Accesses, AccessTy, Loc](Value *Ptr, const SCEV *PtrScev) {
+            MemoryLocation NewLoc = Loc.getWithNewPtr(Ptr);
+            Accesses.addStore(NewLoc, AccessTy, PtrScev);
+          });
     }
   }
 
   if (IsAnnotatedParallel) {
     LLVM_DEBUG(
         dbgs() << "LAA: A loop annotated parallel, ignore memory dependency "
                << "checks.\n");
     CanVecMem = true;

 
     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, AccessTy, Loc, IsReadOnlyPtr](Value *Ptr) {
+    visitPointers(const_cast<Value *>(Loc.Ptr), *TheLoop,  *PSE, SymbolicStrides,
+                  [&Accesses, AccessTy, Loc, IsReadOnlyPtr](Value *Ptr, const SCEV *PtrScev) {
                     MemoryLocation NewLoc = Loc.getWithNewPtr(Ptr);
-                    Accesses.addLoad(NewLoc, AccessTy, IsReadOnlyPtr);
+                    Accesses.addLoad(NewLoc, AccessTy, 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.
   Value *UncomputablePtr = nullptr;
   bool CanDoRTIfNeeded =
       Accesses.canCheckPtrAtRT(*PtrRtChecking, PSE->getSE(), TheLoop,
                                SymbolicStrides, UncomputablePtr, false);
   if (!CanDoRTIfNeeded) {

llvm/test/Analysis/LoopAccessAnalysis/depend_diff_types.ll

 ; CHECK-NEXT:        Forward:
 ; CHECK-NEXT:            %ld.f32 = load float, ptr %gep.iv, align 8 ->
 ; CHECK-NEXT:            store float %val, ptr %gep.iv.min.100, align 8
 ; CHECK-EMPTY:
 ; CHECK-NEXT:        BackwardVectorizable:
 ; CHECK-NEXT:            store float %val, ptr %gep.iv.min.100, align 8 ->
 ; CHECK-NEXT:            store i32 %indvars.iv.i32, ptr %gep.iv, align 8
 ; CHECK-EMPTY:
+; CHECK-NEXT:        Forward:
+; CHECK-NEXT:            %ld.f32 = load float, ptr %gep.iv, align 8 ->
+; CHECK-NEXT:            store i32 %indvars.iv.i32, ptr %gep.iv, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:        Forward:
+; CHECK-NEXT:            %ld.f32 = load float, ptr %gep.iv, align 8 ->
+; CHECK-NEXT:            store float %val, ptr %gep.iv.min.100, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:        BackwardVectorizable:
+; CHECK-NEXT:            store float %val, ptr %gep.iv.min.100, align 8 ->
+; CHECK-NEXT:            store i32 %indvars.iv.i32, ptr %gep.iv, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:        Forward:
+; CHECK-NEXT:            %ld.f32 = load float, ptr %gep.iv, align 8 ->
+; CHECK-NEXT:            store i32 %indvars.iv.i32, ptr %gep.iv, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:        Forward:
+; CHECK-NEXT:            %ld.f32 = load float, ptr %gep.iv, align 8 ->
+; CHECK-NEXT:            store float %val, ptr %gep.iv.min.100, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:        BackwardVectorizable:
+; CHECK-NEXT:            store float %val, ptr %gep.iv.min.100, align 8 ->
+; CHECK-NEXT:            store i32 %indvars.iv.i32, ptr %gep.iv, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:        Forward:
+; CHECK-NEXT:            %ld.f32 = load float, ptr %gep.iv, align 8 ->
+; CHECK-NEXT:            store i32 %indvars.iv.i32, ptr %gep.iv, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:        Forward:
+; CHECK-NEXT:            %ld.f32 = load float, ptr %gep.iv, align 8 ->
+; CHECK-NEXT:            store float %val, ptr %gep.iv.min.100, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:        BackwardVectorizable:
+; CHECK-NEXT:            store float %val, ptr %gep.iv.min.100, align 8 ->
+; CHECK-NEXT:            store i32 %indvars.iv.i32, ptr %gep.iv, align 8
+; CHECK-EMPTY:
 ; CHECK-NEXT:        Run-time memory checks:
 ; CHECK-NEXT:        Grouped accesses:
 
 define void @backdep_type_size_equivalence(ptr nocapture %vec, i64 %n) {
 entry:
   br label %loop
 
 loop:

 ; CHECK-NEXT:        ForwardButPreventsForwarding:
 ; CHECK-NEXT:            store double %val, ptr %gep.iv.101.i64, align 8 ->
 ; CHECK-NEXT:            %ld.i64 = load i64, ptr %gep.iv, align 8
 ; CHECK-EMPTY:
 ; CHECK-NEXT:        Unknown:
 ; CHECK-NEXT:            store double %val, ptr %gep.iv.101.i64, align 8 ->
 ; CHECK-NEXT:            store i32 %ld.i64.i32, ptr %gep.iv.n.i64, align 8
 ; CHECK-EMPTY:
+; CHECK-NEXT:        Unknown:
+; CHECK-NEXT:            %ld.f64 = load double, ptr %gep.iv, align 8 ->
+; CHECK-NEXT:                    store i32 %ld.i64.i32, ptr %gep.iv.n.i64, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:        Unknown:
+; CHECK-NEXT:            %ld.i64 = load i64, ptr %gep.iv, align 8 ->
+; CHECK-NEXT:                    store i32 %ld.i64.i32, ptr %gep.iv.n.i64, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:        BackwardVectorizableButPreventsForwarding:
+; CHECK-NEXT:            %ld.f64 = load double, ptr %gep.iv, align 8 ->
+; CHECK-NEXT:            store double %val, ptr %gep.iv.101.i64, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:        ForwardButPreventsForwarding:
+; CHECK-NEXT:            store double %val, ptr %gep.iv.101.i64, align 8 ->
+; CHECK-NEXT:            %ld.i64 = load i64, ptr %gep.iv, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:        Unknown:
+; CHECK-NEXT:            store double %val, ptr %gep.iv.101.i64, align 8 ->
+; CHECK-NEXT:                    store i32 %ld.i64.i32, ptr %gep.iv.n.i64, align 8
+; CHECK-EMPTY:
 ; CHECK-NEXT:      Run-time memory checks:
 ; CHECK-NEXT:      Grouped accesses:
 
 define void @neg_dist_dep_type_size_equivalence(ptr nocapture %vec, i64 %n) {
 entry:
   br label %loop
 
 loop:

llvm/test/Analysis/LoopAccessAnalysis/depend_diff_types_opaque_ptr.ll

 ; CHECK-NEXT:        Forward:
 ; CHECK-NEXT:            %ld.f32 = load float, ptr %gep.iv, align 8 ->
 ; CHECK-NEXT:            store float %val, ptr %gep.iv.min.100, align 8
 ; CHECK-EMPTY:
 ; CHECK-NEXT:        BackwardVectorizable:
 ; CHECK-NEXT:            store float %val, ptr %gep.iv.min.100, align 8 ->
 ; CHECK-NEXT:            store i32 %indvars.iv.i32, ptr %gep.iv, align 8
 ; CHECK-EMPTY:
+; CHECK-NEXT:    Forward:
+; CHECK-NEXT:        %ld.f32 = load float, ptr %gep.iv, align 8 ->
+; CHECK-NEXT:        store i32 %indvars.iv.i32, ptr %gep.iv, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:    Forward:
+; CHECK-NEXT:        %ld.f32 = load float, ptr %gep.iv, align 8 ->
+; CHECK-NEXT:        store float %val, ptr %gep.iv.min.100, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:    BackwardVectorizable:
+; CHECK-NEXT:        store float %val, ptr %gep.iv.min.100, align 8 ->
+; CHECK-NEXT:        store i32 %indvars.iv.i32, ptr %gep.iv, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:    Forward:
+; CHECK-NEXT:        %ld.f32 = load float, ptr %gep.iv, align 8 ->
+; CHECK-NEXT:        store i32 %indvars.iv.i32, ptr %gep.iv, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:    Forward:
+; CHECK-NEXT:        %ld.f32 = load float, ptr %gep.iv, align 8 ->
+; CHECK-NEXT:        store float %val, ptr %gep.iv.min.100, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:    BackwardVectorizable:
+; CHECK-NEXT:        store float %val, ptr %gep.iv.min.100, align 8 ->
+; CHECK-NEXT:        store i32 %indvars.iv.i32, ptr %gep.iv, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:    Forward:
+; CHECK-NEXT:        %ld.f32 = load float, ptr %gep.iv, align 8 ->
+; CHECK-NEXT:        store i32 %indvars.iv.i32, ptr %gep.iv, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:    Forward:
+; CHECK-NEXT:        %ld.f32 = load float, ptr %gep.iv, align 8 ->
+; CHECK-NEXT:        store float %val, ptr %gep.iv.min.100, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:    BackwardVectorizable:
+; CHECK-NEXT:        store float %val, ptr %gep.iv.min.100, align 8 ->
+; CHECK-NEXT:        store i32 %indvars.iv.i32, ptr %gep.iv, align 8
+; CHECK-EMPTY:
 ; CHECK-NEXT:        Run-time memory checks:
 ; CHECK-NEXT:        Grouped accesses:
 
 define void @backdep_type_size_equivalence(ptr nocapture %vec, i64 %n) {
 entry:
   br label %loop
 
 loop:

 ; CHECK-NEXT:        ForwardButPreventsForwarding:
 ; CHECK-NEXT:            store double %val, ptr %gep.iv.101, align 8 ->
 ; CHECK-NEXT:            %ld.i64 = load i64, ptr %gep.iv, align 8
 ; CHECK-EMPTY:
 ; CHECK-NEXT:        Unknown:
 ; CHECK-NEXT:            store double %val, ptr %gep.iv.101, align 8 ->
 ; CHECK-NEXT:            store i32 %ld.i64.i32, ptr %gep.iv.n, align 8
 ; CHECK-EMPTY:
+; CHECK-NEXT:        Unknown:
+; CHECK-NEXT:            %ld.f64 = load double, ptr %gep.iv, align 8 ->
+; CHECK-NEXT:                    store i32 %ld.i64.i32, ptr %gep.iv.n, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:        Unknown:
+; CHECK-NEXT:            %ld.i64 = load i64, ptr %gep.iv, align 8 ->
+; CHECK-NEXT:                    store i32 %ld.i64.i32, ptr %gep.iv.n, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:        BackwardVectorizableButPreventsForwarding:
+; CHECK-NEXT:            %ld.f64 = load double, ptr %gep.iv, align 8 ->
+; CHECK-NEXT:            store double %val, ptr %gep.iv.101, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:        ForwardButPreventsForwarding:
+; CHECK-NEXT:            store double %val, ptr %gep.iv.101, align 8 ->
+; CHECK-NEXT:            %ld.i64 = load i64, ptr %gep.iv, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:        Unknown:
+; CHECK-NEXT:            store double %val, ptr %gep.iv.101, align 8 ->
+; CHECK-NEXT:                    store i32 %ld.i64.i32, ptr %gep.iv.n, align 8
+; CHECK-EMPTY:
 ; CHECK-NEXT:      Run-time memory checks:
 ; CHECK-NEXT:      Grouped accesses:
 
 define void @neg_dist_dep_type_size_equivalence(ptr nocapture %vec, i64 %n) {
 entry:
   br label %loop
 
 loop:

llvm/test/Analysis/LoopAccessAnalysis/max_safe_dep_dist_non_unit_stride.ll

 ; CHECK-LABEL: Loop access info in function 'foo':
 ; CHECK-NEXT:  loop:
 ; CHECK-NEXT:   Memory dependences are safe with a maximum safe vector width of 64 bits
 ; CHECK-NEXT:    Dependences:
 ; CHECK-NEXT:      BackwardVectorizable:
 ; CHECK-NEXT:          store i32 %0, ptr %arrayidx2, align 4 ->
 ; CHECK-NEXT:          %1 = load i32, ptr %arrayidx5, align 4
 ; CHECK-EMPTY:
+; CHECK-NEXT:    BackwardVectorizable:
+; CHECK-NEXT:        store i32 %0, ptr %arrayidx2, align 4 ->
+; CHECK-NEXT:        %1 = load i32, ptr %arrayidx5, align 4
+; CHECK-EMPTY:
+; CHECK-NEXT:    BackwardVectorizable:
+; CHECK-NEXT:        store i32 %0, ptr %arrayidx2, align 4 ->
+; CHECK-NEXT:        %1 = load i32, ptr %arrayidx5, align 4
+; CHECK-EMPTY:
 ; CHECK-NEXT:    Run-time memory checks:
 ; CHECK-NEXT:    Grouped accesses:
 ; CHECK-EMPTY:
 ; CHECK-NEXT:    Non vectorizable stores to invariant address were not found in loop.
 ; CHECK-NEXT:    SCEV assumptions:
 ; CHECK-EMPTY:
 ; CHECK-NEXT:    Expressions re-written:
 ;

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

 ; 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:    Unknown data dependence.
 ; CHECK-NEXT:    Dependences:
 ; CHECK-NEXT:      Unknown:
 ; CHECK-NEXT:          %v8 = load double, ptr %arrayidx, align 8 ->
 ; CHECK-NEXT:          store double %mul16, ptr %ptr.2, align 8
 ; CHECK-EMPTY:
+; CHECK-NEXT:      Unknown:
+; CHECK-NEXT:          %v8 = load double, ptr %arrayidx, align 8 ->
+; CHECK-NEXT:          store double %mul16, ptr %ptr.2, align 8
+; CHECK-EMPTY:
 ; CHECK-NEXT:    Run-time memory checks:
 ; CHECK-NEXT:    Check 0:
 ; CHECK-NEXT:      Comparing group ([[GROUP_C:.+]]):
 ; CHECK-NEXT:      ptr %C
 ; CHECK-NEXT:      Against group ([[GROUP_B:.+]]):
 ; CHECK-NEXT:      ptr %B
 ; CHECK-NEXT:    Check 1:
 ; CHECK-NEXT:      Comparing group ([[GROUP_C]]):

 ; 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:    Unknown data dependence.
 ; CHECK-NEXT:    Dependences:
 ; CHECK-NEXT:      Unknown:
 ; CHECK-NEXT:          %v8 = load double, ptr %arrayidx, align 8 ->
 ; CHECK-NEXT:          store double %mul16, ptr %ptr.3, align 8
 ; CHECK-EMPTY:
+; CHECK-NEXT:      Unknown:
+; CHECK-NEXT:          %v8 = load double, ptr %arrayidx, align 8 ->
+; CHECK-NEXT:          store double %mul16, ptr %ptr.3, align 8
+; CHECK-EMPTY:
 ; CHECK-NEXT:    Run-time memory checks:
 ; CHECK-NEXT:    Check 0:
 ; CHECK-NEXT:      Comparing group ([[GROUP_C:.+]]):
 ; CHECK-NEXT:      ptr %C
 ; CHECK-NEXT:      Against group ([[GROUP_B:.+]]):
 ; CHECK-NEXT:      ptr %B
 ; CHECK-NEXT:    Check 1:
 ; CHECK-NEXT:      Comparing group ([[GROUP_C]]):

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

llvm/test/Analysis/LoopAccessAnalysis/symbolic-stride.ll

 ; CHECK-NEXT:          %load = load i32, ptr %gep.A, align 4 ->
 ; CHECK-NEXT:          store i32 %add, ptr %gep.A.next, align 4
 ; CHECK-EMPTY:
 ; CHECK-NEXT:    Run-time memory checks:
 ; CHECK-NEXT:    Grouped accesses:
 ; CHECK-EMPTY:
 ; CHECK-NEXT:    Non vectorizable stores to invariant address were not found in loop.
 ; CHECK-NEXT:    SCEV assumptions:
-; CHECK-NEXT:    Equal predicate: %stride.2 == 1
 ; CHECK-NEXT:    Equal predicate: %stride.1 == 1
+; CHECK-NEXT:    Equal predicate: %stride.2 == 1
 ; CHECK-EMPTY:
 ; CHECK-NEXT:    Expressions re-written:
 ; CHECK-NEXT:    [PSE]  %gep.A = getelementptr inbounds i32, ptr %A, i64 %mul:
 ; CHECK-NEXT:      {%A,+,(4 * %stride.1)}<%loop>
 ; CHECK-NEXT:      --> {%A,+,4}<%loop>
 ; CHECK-NEXT:    [PSE]  %gep.A.next = getelementptr inbounds i32, ptr %A, i64 %mul.2:
 ; CHECK-NEXT:      {((4 * %stride.2) + %A),+,(4 * %stride.2)}<%loop>
 ; CHECK-NEXT:      --> {(4 + %A),+,4}<%loop>

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

 ;
 ;
 ;
 ;
 ;
 ;
 ; DEFAULT-LABEL: @two_strides(
 ; DEFAULT-NEXT:  for.body.lver.check:
-; DEFAULT-NEXT:    [[IDENT_CHECK:%.*]] = icmp ne i64 [[STRIDE_2:%.*]], 1
-; DEFAULT-NEXT:    [[IDENT_CHECK1:%.*]] = icmp ne i64 [[STRIDE_1:%.*]], 1
+; DEFAULT-NEXT:    [[IDENT_CHECK:%.*]] = icmp ne i64 [[STRIDE_1:%.*]], 1
+; DEFAULT-NEXT:    [[IDENT_CHECK1:%.*]] = icmp ne i64 [[STRIDE_2:%.*]], 1
 ; DEFAULT-NEXT:    [[TMP0:%.*]] = or i1 [[IDENT_CHECK]], [[IDENT_CHECK1]]
 ; DEFAULT-NEXT:    br i1 [[TMP0]], label [[FOR_BODY_PH_LVER_ORIG:%.*]], label [[FOR_BODY_PH:%.*]]
 ; DEFAULT:       for.body.ph.lver.orig:
 ; DEFAULT-NEXT:    br label [[FOR_BODY_LVER_ORIG:%.*]]
 ; DEFAULT:       for.body.lver.orig:
 ; DEFAULT-NEXT:    [[INDVARS_IV_LVER_ORIG:%.*]] = phi i64 [ 0, [[FOR_BODY_PH_LVER_ORIG]] ], [ [[INDVARS_IV_NEXT_LVER_ORIG:%.*]], [[FOR_BODY_LVER_ORIG]] ]
 ; DEFAULT-NEXT:    [[MUL_LVER_ORIG:%.*]] = mul i64 [[INDVARS_IV_LVER_ORIG]], [[STRIDE_1]]
 ; DEFAULT-NEXT:    [[ARRAYIDX_LVER_ORIG:%.*]] = getelementptr inbounds i32, ptr [[A:%.*]], i64 [[MUL_LVER_ORIG]]

llvm/test/Transforms/LoopVectorize/runtime-check-pointer-element-type.ll

 ; RUN: opt -passes='loop-vectorize' -force-vector-width=2 %s -S -debug 2>&1 | FileCheck %s
 
 ; REQUIRES: asserts
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 
 ; FIXME
 ; Test case for PR47751. Make sure the runtime check includes a required
 ; addition of the size of the element type (a pointer) for the end bound.
 
 define void @test(i64 %arg, i32 %arg1, ptr %base) {
-; CHECK:      LAA: Adding RT check for range:
-; CHECK-NEXT:  Start: ((8 * (zext i32 (-1 + %arg1)<nsw> to i64))<nuw><nsw> + (8 * (1 smin %arg)) + (-8 * %arg) + %base)
-; CHECK-SAME:  End: (8 + (8 * (zext i32 (-1 + %arg1)<nsw> to i64))<nuw><nsw> + %base)
-; CHECK-NEXT: LAA: Adding RT check for range:
-; CHECK-NEXT:  Start: ((8 * (1 smin %arg)) + %base)
-; CHECK-SAME:  End: (8 + (8 * %arg) + %base)
+; CHECK:      LV: Interleaving to reduce branch cost.
+; CHECK-NEXT: Calculating cost of runtime checks:
 
 ; CHECK: vector.body
 
 entry:
   br label %loop
 
 loop:
   %iv.1 = phi i64 [ %arg, %entry ], [ %iv.1.next, %loop ]

llvm/test/Transforms/LoopVectorize/strided-accesses-interleave-only.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
 ; RUN: opt -passes=loop-vectorize -force-vector-width=1 -force-vector-interleave=2 -S %s | FileCheck %s
 
 define void @test_variable_stride(ptr %dst, i32 %scale) {
 ; CHECK-LABEL: define void @test_variable_stride
 ; CHECK-SAME: (ptr [[DST:%.*]], i32 [[SCALE:%.*]]) {
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br i1 false, label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]]
+; CHECK-NEXT:    br i1 false, label [[SCALAR_PH:%.*]], label [[VECTOR_SCEVCHECK:%.*]]
+; CHECK:       vector.scevcheck:
+; CHECK-NEXT:    [[IDENT_CHECK:%.*]] = icmp ne i32 [[SCALE]], 1
+; CHECK-NEXT:    br i1 [[IDENT_CHECK]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]]
 ; CHECK:       vector.ph:
 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
 ; CHECK:       vector.body:
 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i32 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[INDEX]], 0
 ; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[INDEX]], 1
-; CHECK-NEXT:    [[TMP2:%.*]] = mul i32 [[TMP0]], [[SCALE]]
-; CHECK-NEXT:    [[TMP3:%.*]] = mul i32 [[TMP1]], [[SCALE]]
+; CHECK-NEXT:    [[TMP2:%.*]] = mul i32 [[TMP0]], 1
+; CHECK-NEXT:    [[TMP3:%.*]] = mul i32 [[TMP1]], 1
 ; CHECK-NEXT:    [[TMP4:%.*]] = getelementptr i16, ptr [[DST]], i32 [[TMP2]]
 ; CHECK-NEXT:    [[TMP5:%.*]] = getelementptr i16, ptr [[DST]], i32 [[TMP3]]
 ; CHECK-NEXT:    store i32 [[TMP0]], ptr [[TMP4]], align 2
 ; CHECK-NEXT:    store i32 [[TMP1]], ptr [[TMP5]], align 2
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i32 [[INDEX]], 2
 ; CHECK-NEXT:    [[TMP6:%.*]] = icmp eq i32 [[INDEX_NEXT]], 1000
 ; CHECK-NEXT:    br i1 [[TMP6]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP0:![0-9]+]]
 ; CHECK:       middle.block:
 ; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i32 1000, 1000
 ; CHECK-NEXT:    br i1 [[CMP_N]], label [[EXIT:%.*]], label [[SCALAR_PH]]
 ; CHECK:       scalar.ph:
-; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i32 [ 1000, [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i32 [ 1000, [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ], [ 0, [[VECTOR_SCEVCHECK]] ]
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[IDX:%.*]] = mul i32 [[IV]], [[SCALE]]
 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr i16, ptr [[DST]], i32 [[IDX]]
 ; CHECK-NEXT:    store i32 [[IV]], ptr [[GEP]], align 2
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    [[EC:%.*]] = icmp eq i32 [[IV_NEXT]], 1000