diff --git a/llvm/include/llvm/Analysis/LoopAccessAnalysis.h b/llvm/include/llvm/Analysis/LoopAccessAnalysis.h --- a/llvm/include/llvm/Analysis/LoopAccessAnalysis.h +++ b/llvm/include/llvm/Analysis/LoopAccessAnalysis.h @@ -184,7 +184,7 @@ /// /// Only checks sets with elements in \p CheckDeps. bool areDepsSafe(DepCandidates &AccessSets, MemAccessInfoList &CheckDeps, - const ValueToValueMap &Strides); + const DenseMap &Strides); /// No memory dependence was encountered that would inhibit /// vectorization. @@ -316,7 +316,7 @@ /// 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 &Strides); /// Check whether the data dependence could prevent store-load /// forwarding. @@ -612,7 +612,9 @@ /// If an access has a symbolic strides, this maps the pointer value to /// the stride symbol. - const ValueToValueMap &getSymbolicStrides() const { return SymbolicStrides; } + const DenseMap &getSymbolicStrides() const { + return SymbolicStrides; + } /// Pointer has a symbolic stride. bool hasStride(Value *V) const { return StrideSet.count(V); } @@ -699,7 +701,7 @@ /// If an access has a symbolic strides, this maps the pointer value to /// the stride symbol. - ValueToValueMap SymbolicStrides; + DenseMap SymbolicStrides; /// Set of symbolic strides values. SmallPtrSet StrideSet; @@ -716,9 +718,10 @@ /// /// \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, - Value *Ptr); +const SCEV * +replaceSymbolicStrideSCEV(PredicatedScalarEvolution &PSE, + const DenseMap &PtrToStride, + Value *Ptr); /// If the pointer has a constant stride return it in units of the access type /// size. Otherwise return std::nullopt. @@ -737,7 +740,7 @@ std::optional getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy, Value *Ptr, const Loop *Lp, - const ValueToValueMap &StridesMap = ValueToValueMap(), + const DenseMap &StridesMap = DenseMap(), bool Assume = false, bool ShouldCheckWrap = true); /// Returns the distance between the pointers \p PtrA and \p PtrB iff they are diff --git a/llvm/include/llvm/Analysis/VectorUtils.h b/llvm/include/llvm/Analysis/VectorUtils.h --- a/llvm/include/llvm/Analysis/VectorUtils.h +++ b/llvm/include/llvm/Analysis/VectorUtils.h @@ -917,7 +917,7 @@ /// Collect all the accesses with a constant stride in program order. void collectConstStrideAccesses( MapVector &AccessStrideInfo, - const ValueToValueMap &Strides); + const DenseMap &Strides); /// Returns true if \p Stride is allowed in an interleaved group. static bool isStrided(int Stride); diff --git a/llvm/lib/Analysis/LoopAccessAnalysis.cpp b/llvm/lib/Analysis/LoopAccessAnalysis.cpp --- a/llvm/lib/Analysis/LoopAccessAnalysis.cpp +++ b/llvm/lib/Analysis/LoopAccessAnalysis.cpp @@ -154,21 +154,19 @@ } const SCEV *llvm::replaceSymbolicStrideSCEV(PredicatedScalarEvolution &PSE, - const ValueToValueMap &PtrToStride, + const DenseMap &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::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(StrideSCEV) && "shouldn't be in map"); const auto *CT = SE->getOne(StrideSCEV->getType()); @@ -658,7 +656,7 @@ /// the bounds of the pointer. bool createCheckForAccess(RuntimePointerChecking &RtCheck, MemAccessInfo Access, Type *AccessTy, - const ValueToValueMap &Strides, + const DenseMap &Strides, DenseMap &DepSetId, Loop *TheLoop, unsigned &RunningDepId, unsigned ASId, bool ShouldCheckStride, bool Assume); @@ -669,7 +667,7 @@ /// 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 &Strides, Value *&UncomputablePtr, bool ShouldCheckWrap = false); /// Goes over all memory accesses, checks whether a RT check is needed @@ -764,7 +762,7 @@ /// Check whether a pointer address cannot wrap. static bool isNoWrap(PredicatedScalarEvolution &PSE, - const ValueToValueMap &Strides, Value *Ptr, Type *AccessTy, + const DenseMap &Strides, Value *Ptr, Type *AccessTy, Loop *L) { const SCEV *PtrScev = PSE.getSCEV(Ptr); if (PSE.getSE()->isLoopInvariant(PtrScev, L)) @@ -957,7 +955,7 @@ static SmallVector> findForkedPointer(PredicatedScalarEvolution &PSE, - const ValueToValueMap &StridesMap, Value *Ptr, + const DenseMap &StridesMap, Value *Ptr, const Loop *L) { ScalarEvolution *SE = PSE.getSE(); assert(SE->isSCEVable(Ptr->getType()) && "Value is not SCEVable!"); @@ -982,7 +980,7 @@ bool AccessAnalysis::createCheckForAccess(RuntimePointerChecking &RtCheck, MemAccessInfo Access, Type *AccessTy, - const ValueToValueMap &StridesMap, + const DenseMap &StridesMap, DenseMap &DepSetId, Loop *TheLoop, unsigned &RunningDepId, unsigned ASId, bool ShouldCheckWrap, @@ -1043,7 +1041,7 @@ bool AccessAnalysis::canCheckPtrAtRT(RuntimePointerChecking &RtCheck, ScalarEvolution *SE, Loop *TheLoop, - const ValueToValueMap &StridesMap, + const DenseMap &StridesMap, Value *&UncomputablePtr, bool ShouldCheckWrap) { // Find pointers with computable bounds. We are going to use this information // to place a runtime bound check. @@ -1373,7 +1371,7 @@ std::optional llvm::getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy, Value *Ptr, const Loop *Lp, - const ValueToValueMap &StridesMap, + const DenseMap &StridesMap, bool Assume, bool ShouldCheckWrap) { Type *Ty = Ptr->getType(); assert(Ty->isPointerTy() && "Unexpected non-ptr"); @@ -1822,7 +1820,7 @@ MemoryDepChecker::Dependence::DepType MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx, const MemAccessInfo &B, unsigned BIdx, - const ValueToValueMap &Strides) { + const DenseMap &Strides) { assert (AIdx < BIdx && "Must pass arguments in program order"); auto [APtr, AIsWrite] = A; @@ -2016,7 +2014,7 @@ bool MemoryDepChecker::areDepsSafe(DepCandidates &AccessSets, MemAccessInfoList &CheckDeps, - const ValueToValueMap &Strides) { + const DenseMap &Strides) { MaxSafeDepDistBytes = -1; SmallPtrSet Visited; @@ -2691,6 +2689,12 @@ if (!Ptr) return; + // Note: getStrideFromPointer is a *profitability* heuristic. We + // could broaden the scope of values returned here - to anything + // which happens to be loop invariant and contributes to the + // computation of an interesting IV - but we chose not to as we + // don't have a cost model here, and broadening the scope exposes + // far too many unprofitable cases. Value *Stride = getStrideFromPointer(Ptr, PSE->getSE(), TheLoop); if (!Stride) return; @@ -2746,7 +2750,7 @@ } LLVM_DEBUG(dbgs() << "LAA: Found a strided access that we can version.\n"); - SymbolicStrides[Ptr] = Stride; + SymbolicStrides[Ptr] = StrideExpr; StrideSet.insert(Stride); } diff --git a/llvm/lib/Analysis/VectorUtils.cpp b/llvm/lib/Analysis/VectorUtils.cpp --- a/llvm/lib/Analysis/VectorUtils.cpp +++ b/llvm/lib/Analysis/VectorUtils.cpp @@ -1011,7 +1011,7 @@ void InterleavedAccessInfo::collectConstStrideAccesses( MapVector &AccessStrideInfo, - const ValueToValueMap &Strides) { + const DenseMap &Strides) { auto &DL = TheLoop->getHeader()->getModule()->getDataLayout(); // Since it's desired that the load/store instructions be maintained in @@ -1091,7 +1091,7 @@ void InterleavedAccessInfo::analyzeInterleaving( bool EnablePredicatedInterleavedMemAccesses) { LLVM_DEBUG(dbgs() << "LV: Analyzing interleaved accesses...\n"); - const ValueToValueMap &Strides = LAI->getSymbolicStrides(); + const auto &Strides = LAI->getSymbolicStrides(); // Holds all accesses with a constant stride. MapVector AccessStrideInfo; diff --git a/llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp b/llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp --- a/llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp +++ b/llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp @@ -3477,7 +3477,7 @@ static bool containsDecreasingPointers(Loop *TheLoop, PredicatedScalarEvolution *PSE) { - const ValueToValueMap &Strides = ValueToValueMap(); + const auto &Strides = DenseMap(); for (BasicBlock *BB : TheLoop->blocks()) { // Scan the instructions in the block and look for addresses that are // consecutive and decreasing. diff --git a/llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp b/llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp --- a/llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp +++ b/llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp @@ -456,8 +456,8 @@ // 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(); Function *F = TheLoop->getHeader()->getParent(); bool OptForSize = F->hasOptSize() ||