[LAA/LV] Simplify stride speculation logic [nfc]

[reames]

Summary

The existing code makes it hard to tell that collectStridedAccess is really about identifying some loop invariant SCEV which is *profitable* to speculate is equal to one. The odd dual usage structure of Value and SCEV confuses this point.

We could choose to loosen the profitability analysis if desired. I'm not proposing doing so at this time as it exposes too many cases where the speculation is unprofitable.

[peixin]

Why do you remove the StrideSet? It can be used to check the const stride in cost model very fast. Now, you check if it is constant one in PSE. The question is if all the const one in PSE are the strides?

Also, it seems that removing the StrideSet will cause the const stride of non-one (such as 4) in D147539 hard to check in cost model.

In addition, I don't figure out how this patch help replace the symbolic stride with constants in vectory body. To perform the replacement, we have the following options:

1. Emit the constants when generating the vector body. In this way, we need to check every mul operation, which seems to be expansive.
2. Get all the predicates from PSE and check them, which is done in D147378.
3. Use the StrideSet in LAA and get the predicate using PSE.

Maybe you have better idea and this patch can help?

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

6432

SCEV already has the interface isOne.
https://github.com/llvm/llvm-project/blob/5f036799f4d39c1aa5a6fac0e972050373e9fa78/llvm/lib/Analysis/ScalarEvolution.cpp#L450-L454

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7208

This could be done independent of changing the stride map type I think?

[fhahn]

In D147750#4250830, @peixin wrote:

Why do you remove the StrideSet? It can be used to check the const stride in cost model very fast. Now, you check if it is constant one in PSE. The question is if all the const one in PSE are the strides?

In a way it is slightly more powerful to use PSE directly, as it has info about all predicates (not just about the strides). It should be possible to separate changing the type of the map and replacing stride set. Not sure if there's a big benefit from changing the type of the map; IIUC we will only add SCEVUnknown for the strides anyways.

Also, it seems that removing the StrideSet will cause the const stride of non-one (such as 4) in D147539 hard to check in cost model.

In addition, I don't figure out how this patch help replace the symbolic stride with constants in vectory body. To perform the replacement, we have the following options:

1. Emit the constants when generating the vector body. In this way, we need to check every mul operation, which seems to be expansive.
2. Get all the predicates from PSE and check them, which is done in D147378.
3. Use the StrideSet in LAA and get the predicate using PSE.

Maybe you have better idea and this patch can help?

this is an interesting issue and I experimented with a different approach to solving this. I might be missing something, but it seems like we should be able to directly use the stride map + PSE to add Value->VPValue mappings to the VPlans to get the simplifications on construction: D147783

[reames]

Remove change to StrideSet for now since that triggered a bunch of discussion.

[reames]

In D147750#4250830, @peixin wrote:

Also, it seems that removing the StrideSet will cause the const stride of non-one (such as 4) in D147539 hard to check in cost model.

This really isn't true JFYI. The whole point of adding a predicate to PSE is that PSE will then *simplify using that predicate*. I'm 100% sure it does the canonicalization today, but it definitely should be and doing so is straight forward.

In D147750#4251120, @fhahn wrote:

In a way it is slightly more powerful to use PSE directly, as it has info about all predicates (not just about the strides). It should be possible to separate changing the type of the map and replacing stride set.

I separated the changes since it triggered more discussion than I'd really expected.

Not sure if there's a big benefit from changing the type of the map; IIUC we will only add SCEVUnknown for the strides anyways.

We return only SCEVUnknown today. That's an implementation detail of the *profitability* heuristic in this code. We *could* return any loop invariant SCEV which is useful to speculate on. I added a clarifying comment and restructured the patch description to emphasize this.

[reames]

ping

[fhahn]

LGTM as this simplifies things slightly by avoiding a Value <-> SCEV roundtrip. Please wait a day or so with committing in case other reviewers have additional thoughts.

llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp

3399–3400

nit: could just be auto &, given hat the type is already clear from the object construction.

[Ayal]

LGTM, worth using ValueToSCEVMap = DenseMap<const Value *, const SCEV *> ?

llvm/include/llvm/Analysis/LoopAccessAnalysis.h

700

Documentation here and above still seems fine, right?

716

80 columns?

llvm/lib/Analysis/LoopAccessAnalysis.cpp

2697

[reames]

In D147750#4328090, @Ayal wrote:

LGTM, worth using ValueToSCEVMap = DenseMap<const Value *, const SCEV *> ?

I looked at this, but I don't think it helps clarify. We have an existing ValueToSCEVMapTy which differs in constness of the key. We've also got both ValueToValueMap and ValueToValueMapTy (they're different). As a cleanup after this, I'm going to go take a look and see if I can clean these up slightly, but I'm not expecting huge clarity wins in this code.

llvm/include/llvm/Analysis/LoopAccessAnalysis.h

public:
   /// Register the location (instructions are given increasing numbers)
   /// of a write access.
   void addAccess(LoadInst *LI);
 
   /// 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);
+                   const DenseMap<Value *, const SCEV *> &Strides);
 
   /// No memory dependence was encountered that would inhibit
   /// vectorization.
   bool isSafeForVectorization() const {
     return Status == VectorizationSafetyStatus::Safe;
   }
 
   /// Return true if the number of elements that are safe to operate on
private:
   /// This function checks  whether there is a plausible dependence (or the
   /// absence of such can't be proved) between the two accesses. If there is a
   /// plausible dependence but the dependence distance is bigger than one
   /// element access it records this distance in \p MaxSafeDepDistBytes (if this
   /// distance is smaller than any other distance encountered so far).
   /// Otherwise, this function returns true signaling a possible dependence.
   Dependence::DepType isDependent(const MemAccessInfo &A, unsigned AIdx,
                                   const MemAccessInfo &B, unsigned BIdx,
-                                  const ValueToValueMap &Strides);
+                                  const DenseMap<Value *, const SCEV *> &Strides);
 
   /// Check whether the data dependence could prevent store-load
   /// forwarding.
   ///
   /// \return false if we shouldn't vectorize at all or avoid larger
   /// vectorization factors by limiting MaxSafeDepDistBytes.
   bool couldPreventStoreLoadForward(uint64_t Distance, uint64_t TypeByteSize);
 
public:
   /// memory.
   SmallVector<Instruction *, 4> getInstructionsForAccess(Value *Ptr,
                                                          bool isWrite) const {
     return DepChecker->getInstructionsForAccess(Ptr, isWrite);
   }
 
   /// 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); }
+  const DenseMap<Value *, const SCEV *> &getSymbolicStrides() const {
+    return SymbolicStrides;
+  }
 
   /// Print the information about the memory accesses in the loop.
   void print(raw_ostream &OS, unsigned Depth = 0) const;
 
   /// If the loop has memory dependence involving an invariant address, i.e. two
   /// stores or a store and a load, then return true, else return false.
   bool hasDependenceInvolvingLoopInvariantAddress() const {
     return HasDependenceInvolvingLoopInvariantAddress;
private:
   /// List of stores to invariant addresses.
   SmallVector<StoreInst *> StoresToInvariantAddresses;
 
   /// The diagnostics report generated for the analysis.  E.g. why we
   /// couldn't analyze the loop.
   std::unique_ptr<OptimizationRemarkAnalysis> Report;
 
   /// If an access has a symbolic strides, this maps the pointer value to
   /// the stride symbol.
-  ValueToValueMap SymbolicStrides;
-
-  /// Set of symbolic strides values.
-  SmallPtrSet<Value *, 8> StrideSet;
+  DenseMap<Value *, const SCEV *> SymbolicStrides;
 };
 
 Value *stripIntegerCast(Value *V);
 
 /// Return the SCEV corresponding to a pointer with the symbolic stride
 /// replaced with constant one, assuming the SCEV predicate associated with
 /// \p PSE is true.
 ///
 /// If necessary this method will version the stride of the pointer according
 /// to \p PtrToStride and therefore add further predicates to \p PSE.
 ///
 /// \p PtrToStride provides the mapping between the pointer value and its
 /// stride as collected by LoopVectorizationLegality::collectStridedAccess.
 const SCEV *replaceSymbolicStrideSCEV(PredicatedScalarEvolution &PSE,
-                                      const ValueToValueMap &PtrToStride,
+                                      const DenseMap<Value *, const SCEV *> &PtrToStride,
                                       Value *Ptr);
 
 /// If the pointer has a constant stride return it in units of the access type
 /// size.  Otherwise return std::nullopt.
 ///
 /// Ensure that it does not wrap in the address space, assuming the predicate
 /// associated with \p PSE is true.
 ///
 /// If necessary this method will version the stride of the pointer according
 /// 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.
 std::optional<int64_t>
 getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy, Value *Ptr,
              const Loop *Lp,
-             const ValueToValueMap &StridesMap = ValueToValueMap(),
+             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/include/llvm/Analysis/VectorUtils.h

void releaseGroup(InterleaveGroup<Instruction> *Group) {
 
     InterleaveGroups.erase(Group);
     delete Group;
   }
 
   /// Collect all the accesses with a constant stride in program order.
   void collectConstStrideAccesses(
       MapVector<Instruction *, StrideDescriptor> &AccessStrideInfo,
-      const ValueToValueMap &Strides);
+      const DenseMap<Value *, const SCEV *> &Strides);
 
   /// Returns true if \p Stride is allowed in an interleaved group.
   static bool isStrided(int Stride);
 
   /// Returns true if \p BB is a predicated block.
   bool isPredicated(BasicBlock *BB) const {
     return LoopAccessInfo::blockNeedsPredication(BB, TheLoop, DT);
   }

llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h

public:
   }
 
   unsigned getMaxSafeDepDistBytes() { return LAI->getMaxSafeDepDistBytes(); }
 
   uint64_t getMaxSafeVectorWidthInBits() const {
     return LAI->getDepChecker().getMaxSafeVectorWidthInBits();
   }
 
-  bool hasStride(Value *V) { return LAI->hasStride(V); }
-
   /// Returns true if vector representation of the instruction \p I
   /// requires mask.
   bool isMaskRequired(const Instruction *I) const {
     return MaskedOp.contains(I);
   }
 
   unsigned getNumStores() const { return LAI->getNumStores(); }
   unsigned getNumLoads() const { return LAI->getNumLoads(); }

llvm/lib/Analysis/LoopAccessAnalysis.cpp

 Value *llvm::stripIntegerCast(Value *V) {
   if (auto *CI = dyn_cast<CastInst>(V))
     if (CI->getOperand(0)->getType()->isIntegerTy())
       return CI->getOperand(0);
   return V;
 }
 
 const SCEV *llvm::replaceSymbolicStrideSCEV(PredicatedScalarEvolution &PSE,
-                                            const ValueToValueMap &PtrToStride,
+                                            const DenseMap<Value *, const SCEV *> &PtrToStride,
                                             Value *Ptr) {
   const SCEV *OrigSCEV = PSE.getSCEV(Ptr);
 
   // If there is an entry in the map return the SCEV of the pointer with the
   // symbolic stride replaced by one.
-  ValueToValueMap::const_iterator SI = PtrToStride.find(Ptr);
+  DenseMap<Value *, const SCEV *>::const_iterator SI = PtrToStride.find(Ptr);
   if (SI == PtrToStride.end())
     // For a non-symbolic stride, just return the original expression.
     return OrigSCEV;
 
-  Value *StrideVal = stripIntegerCast(SI->second);
-
   ScalarEvolution *SE = PSE.getSE();
-  const SCEV *StrideSCEV = SE->getSCEV(StrideVal);
+  const SCEV *StrideSCEV = SI->second;
   assert(isa<SCEVUnknown>(StrideSCEV) && "shouldn't be in map");
 
   const auto *CT = SE->getOne(StrideSCEV->getType());
   PSE.addPredicate(*SE->getEqualPredicate(StrideSCEV, CT));
   auto *Expr = PSE.getSCEV(Ptr);
 
   LLVM_DEBUG(dbgs() << "LAA: Replacing SCEV: " << *OrigSCEV
        << " by: " << *Expr << "\n");
public:
   ///
   /// 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 ValueToValueMap &Strides,
+                            const DenseMap<Value *, const SCEV *> &Strides,
                             DenseMap<Value *, 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 ValueToValueMap &Strides,
+                       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();
   }
 
static bool hasComputableBounds(PredicatedScalarEvolution &PSE, Value *Ptr,
   if (!AR)
     return false;
 
   return AR->isAffine();
 }
 
 /// Check whether a pointer address cannot wrap.
 static bool isNoWrap(PredicatedScalarEvolution &PSE,
-                     const ValueToValueMap &Strides, Value *Ptr, Type *AccessTy,
+                     const DenseMap<Value *, const SCEV *> &Strides, Value *Ptr, 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);
   if (Stride == 1 || PSE.hasNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW))
     return true;
default:
     LLVM_DEBUG(dbgs() << "ForkedPtr unhandled instruction: " << *I << "\n");
     ScevList.emplace_back(Scev, !isGuaranteedNotToBeUndefOrPoison(Ptr));
     break;
   }
 }
 
 static SmallVector<PointerIntPair<const SCEV *, 1, bool>>
 findForkedPointer(PredicatedScalarEvolution &PSE,
-                  const ValueToValueMap &StridesMap, Value *Ptr,
+                  const DenseMap<Value *, const SCEV *> &StridesMap, Value *Ptr,
                   const Loop *L) {
   ScalarEvolution *SE = PSE.getSE();
   assert(SE->isSCEVable(Ptr->getType()) && "Value is not SCEVable!");
   SmallVector<PointerIntPair<const SCEV *, 1, bool>> Scevs;
   findForkedSCEVs(SE, L, Ptr, Scevs, MaxForkedSCEVDepth);
 
   // For now, we will only accept a forked pointer with two possible SCEVs
   // that are either SCEVAddRecExprs or loop invariant.
   if (Scevs.size() == 2 &&
       (isa<SCEVAddRecExpr>(get<0>(Scevs[0])) ||
        SE->isLoopInvariant(get<0>(Scevs[0]), L)) &&
       (isa<SCEVAddRecExpr>(get<0>(Scevs[1])) ||
        SE->isLoopInvariant(get<0>(Scevs[1]), L))) {
     LLVM_DEBUG(dbgs() << "LAA: Found forked pointer: " << *Ptr << "\n");
     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 ValueToValueMap &StridesMap,
+                                          const DenseMap<Value *, const SCEV *> &StridesMap,
                                           DenseMap<Value *, 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 [PtrExpr, NeedsFreeze] : TranslatedPtrs) {
     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,
+                                     const DenseMap<Value *, const SCEV *> &StridesMap,
                                      Value *&UncomputablePtr, bool ShouldCheckWrap) {
   // Find pointers with computable bounds. We are going to use this information
   // to place a runtime bound check.
   bool CanDoRT = true;
 
   bool MayNeedRTCheck = false;
   if (!IsRTCheckAnalysisNeeded) return true;
 
static bool isNoWrapAddRec(Value *Ptr, const SCEVAddRecExpr *AR,
 
   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 ValueToValueMap &StridesMap,
+                                          const DenseMap<Value *, const SCEV *> &StridesMap,
                                           bool Assume, bool ShouldCheckWrap) {
   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;
static bool areStridedAccessesIndependent(uint64_t Distance, uint64_t Stride,
   //     | A[0] |      |      | A[3] |      |      | A[6] |      |      |
   //     |      |      |      |      | A[4] |      |      | A[7] |      |
   return ScaledDist % Stride;
 }
 
 MemoryDepChecker::Dependence::DepType
 MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
                               const MemAccessInfo &B, unsigned BIdx,
-                              const ValueToValueMap &Strides) {
+                              const DenseMap<Value *, const SCEV *> &Strides) {
   assert (AIdx < BIdx && "Must pass arguments in program order");
 
   auto [APtr, AIsWrite] = A;
   auto [BPtr, BIsWrite] = B;
   Type *ATy = getLoadStoreType(InstMap[AIdx]);
   Type *BTy = getLoadStoreType(InstMap[BIdx]);
 
   // Two reads are independent.
LLVM_DEBUG(dbgs() << "LAA: Positive distance " << Val.getSExtValue()
                     << " with max VF = " << MaxVF << '\n');
   uint64_t MaxVFInBits = MaxVF * TypeByteSize * 8;
   MaxSafeVectorWidthInBits = std::min(MaxSafeVectorWidthInBits, MaxVFInBits);
   return Dependence::BackwardVectorizable;
 }
 
 bool MemoryDepChecker::areDepsSafe(DepCandidates &AccessSets,
                                    MemAccessInfoList &CheckDeps,
-                                   const ValueToValueMap &Strides) {
+                                   const DenseMap<Value *, const SCEV *> &Strides) {
 
   MaxSafeDepDistBytes = -1;
   SmallPtrSet<MemAccessInfo, 8> Visited;
   for (MemAccessInfo CurAccess : CheckDeps) {
     if (Visited.count(CurAccess))
       continue;
 
     // Get the relevant memory access set.

 }
 
 void LoopAccessInfo::collectStridedAccess(Value *MemAccess) {
   Value *Ptr = getLoadStorePointerOperand(MemAccess);
   if (!Ptr)
     return;
 
   Value *Stride = getStrideFromPointer(Ptr, PSE->getSE(), TheLoop);
   if (!Stride)
     return;
 
   LLVM_DEBUG(dbgs() << "LAA: Found a strided access that is a candidate for "
                        "versioning:");
   LLVM_DEBUG(dbgs() << "  Ptr: " << *Ptr << " Stride: " << *Stride << "\n");
 
   // Avoid adding the "Stride == 1" predicate when we know that
   // Stride >= Trip-Count. Such a predicate will effectively optimize a single
if (SE->isKnownPositive(StrideMinusBETaken)) {
     LLVM_DEBUG(
         dbgs() << "LAA: Stride>=TripCount; No point in versioning as the "
                   "Stride==1 predicate will imply that the loop executes "
                   "at most once.\n");
     return;
   }
   LLVM_DEBUG(dbgs() << "LAA: Found a strided access that we can version.\n");
 
-  SymbolicStrides[Ptr] = Stride;
-  StrideSet.insert(Stride);
+  SymbolicStrides[Ptr] = StrideExpr;
 }
 
 LoopAccessInfo::LoopAccessInfo(Loop *L, ScalarEvolution *SE,
                                const TargetLibraryInfo *TLI, AAResults *AA,
                                DominatorTree *DT, LoopInfo *LI)
     : PSE(std::make_unique<PredicatedScalarEvolution>(*SE, *L)),
       PtrRtChecking(nullptr),
       DepChecker(std::make_unique<MemoryDepChecker>(*PSE, L)), TheLoop(L) {

llvm/lib/Analysis/VectorUtils.cpp

 
 bool InterleavedAccessInfo::isStrided(int Stride) {
   unsigned Factor = std::abs(Stride);
   return Factor >= 2 && Factor <= MaxInterleaveGroupFactor;
 }
 
 void InterleavedAccessInfo::collectConstStrideAccesses(
     MapVector<Instruction *, StrideDescriptor> &AccessStrideInfo,
-    const ValueToValueMap &Strides) {
+    const DenseMap<Value*, const SCEV*> &Strides) {
   auto &DL = TheLoop->getHeader()->getModule()->getDataLayout();
 
   // Since it's desired that the load/store instructions be maintained in
   // "program order" for the interleaved access analysis, we have to visit the
   // blocks in the loop in reverse postorder (i.e., in a topological order).
   // Such an ordering will ensure that any load/store that may be executed
   // before a second load/store will precede the second load/store in
   // AccessStrideInfo.

 //
 // We will first create a store group with (3) and (2). (1) can't be added to
 // this group because it and (2) are dependent. However, (1) can be grouped
 // with other accesses that may precede it in program order. Note that a
 // bottom-up order does not imply that WAW dependences should not be checked.
 void InterleavedAccessInfo::analyzeInterleaving(
                                  bool EnablePredicatedInterleavedMemAccesses) {
   LLVM_DEBUG(dbgs() << "LV: Analyzing interleaved accesses...\n");
-  const ValueToValueMap &Strides = LAI->getSymbolicStrides();
+  const DenseMap<Value*, const SCEV*> &Strides = LAI->getSymbolicStrides();
 
   // Holds all accesses with a constant stride.
   MapVector<Instruction *, StrideDescriptor> AccessStrideInfo;
   collectConstStrideAccesses(AccessStrideInfo, Strides);
 
   if (AccessStrideInfo.empty())
     return;
 

llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp

if (Kind == TTI::SK_InsertSubvector && LT.second.isFixedLengthVector() &&
     }
   }
 
   return BaseT::getShuffleCost(Kind, Tp, Mask, CostKind, Index, SubTp);
 }
 
 static bool containsDecreasingPointers(Loop *TheLoop,
                                        PredicatedScalarEvolution *PSE) {
-  const ValueToValueMap &Strides = ValueToValueMap();
+  const DenseMap<Value *, const SCEV *> &Strides =
+    DenseMap<Value *, const SCEV *>();
   for (BasicBlock *BB : TheLoop->blocks()) {
     // Scan the instructions in the block and look for addresses that are
     // consecutive and decreasing.
     for (Instruction &I : *BB) {
       if (isa<LoadInst>(&I) || isa<StoreInst>(&I)) {
         Value *Ptr = getLoadStorePointerOperand(&I);
         Type *AccessTy = getLoadStoreType(&I);
         if (getPtrStride(*PSE, AccessTy, Ptr, TheLoop, Strides, /*Assume=*/true,

llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp

 }
 
 int LoopVectorizationLegality::isConsecutivePtr(Type *AccessTy,
                                                 Value *Ptr) const {
   // FIXME: Currently, the set of symbolic strides is sometimes queried before
   // it's collected.  This happens from canVectorizeWithIfConvert, when the
   // pointer is checked to reference consecutive elements suitable for a
   // masked access.
-  const ValueToValueMap &Strides =
-    LAI ? LAI->getSymbolicStrides() : ValueToValueMap();
+  const auto &Strides =
+    LAI ? LAI->getSymbolicStrides() : DenseMap<Value *, const SCEV *>();
 
   Function *F = TheLoop->getHeader()->getParent();
   bool OptForSize = F->hasOptSize() ||
                     llvm::shouldOptimizeForSize(TheLoop->getHeader(), PSI, BFI,
                                                 PGSOQueryType::IRPass);
   bool CanAddPredicate = !OptForSize;
   int Stride = getPtrStride(PSE, AccessTy, Ptr, TheLoop, Strides,
                             CanAddPredicate, false).value_or(0);

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

if (!SE->isLoopInvariant(SE->getSCEV(Opd), TheLoop) &&
         !Legal->isInductionVariable(Opd))
       return nullptr;
   }
 
   // Now we know we have a GEP ptr, %inv, %ind, %inv. return the Ptr SCEV.
   return PSE.getSCEV(Ptr);
 }
 
-static bool isStrideMul(Instruction *I, LoopVectorizationLegality *Legal) {
-  return Legal->hasStride(I->getOperand(0)) ||
-         Legal->hasStride(I->getOperand(1));
+static bool isOne(const SCEV *S) {
+  auto *C = dyn_cast<SCEVConstant>(S);
+  return C && C->getAPInt().isOne();
 }
 
 InstructionCost
 LoopVectorizationCostModel::getMemInstScalarizationCost(Instruction *I,
                                                         ElementCount VF) {
   assert(VF.isVector() &&
          "Scalarization cost of instruction implies vectorization.");
   if (VF.isScalable())
LoopVectorizationCostModel::getInstructionCost(Instruction *I, ElementCount VF,
   case Instruction::FDiv:
   case Instruction::FRem:
   case Instruction::Shl:
   case Instruction::LShr:
   case Instruction::AShr:
   case Instruction::And:
   case Instruction::Or:
   case Instruction::Xor: {
-    // Since we will replace the stride by 1 the multiplication should go away.
-    if (I->getOpcode() == Instruction::Mul && isStrideMul(I, Legal))
+    // If we're speculating on the stride being 1, the multiplication may
+    // fold away.  We can generalize this for all operations using the notion
+    // of neutral elements.  (TODO)
+    if (I->getOpcode() == Instruction::Mul &&
+        (isOne(PSE.getSCEV(I->getOperand(0))) ||
+         isOne(PSE.getSCEV(I->getOperand(1)))))
       return 0;
 
     // Detect reduction patterns
     if (auto RedCost = getReductionPatternCost(I, VF, VectorTy, CostKind))
       return *RedCost;
 
     // Certain instructions can be cheaper to vectorize if they have a constant
     // second vector operand. One example of this are shifts on x86.