[LoopLoadElimination] Add support for stride equal to -1

[igor.kirillov]

Summary

This patch allows us to gain all the benefits provided by
LoopLoadElimination pass to descending loops.

[igor.kirillov]

This patch aids in eliminating load within a complex loop in the benchmark. The GVN LoadPRE is unable to accomplish as the case is too difficult for it. A simplified example demonstrating this loop in the benchmark would be as follows:

void f(double *U, long long i, long long n) {
  #pragma clang loop vectorize(disable) unroll(disable)
  for (long long k = n; k > 0; --k)
    U[i * n + k] = U[i * n + k + 1];
}

[nikic]

Looks sensible to me, but I'm not very familiar with LAA.

[fhahn]

LGTM, thanks!

llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp

91–93

nit: maybe absolute distance of one?

[igor.kirillov]

Fix comment

llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp

 /// Represent a store-to-forwarding candidate.
 struct StoreToLoadForwardingCandidate {
   LoadInst *Load;
   StoreInst *Store;
 
   StoreToLoadForwardingCandidate(LoadInst *Load, StoreInst *Store)
       : Load(Load), Store(Store) {}
 
-  /// Return true if the dependence from the store to the load has a
-  /// distance of one.  E.g. A[i+1] = A[i]
+  /// Return true if the dependence from the store to the load has an
+  /// absolute distance of one.
+  /// E.g. A[i+1] = A[i] (or A[i-1] = A[i] for descending loop)
   bool isDependenceDistanceOfOne(PredicatedScalarEvolution &PSE,
                                  Loop *L) const {
     Value *LoadPtr = Load->getPointerOperand();
     Value *StorePtr = Store->getPointerOperand();
     Type *LoadType = getLoadStoreType(Load);
     auto &DL = Load->getParent()->getModule()->getDataLayout();
 
     assert(LoadPtr->getType()->getPointerAddressSpace() ==
                StorePtr->getType()->getPointerAddressSpace() &&
            DL.getTypeSizeInBits(LoadType) ==
                DL.getTypeSizeInBits(getLoadStoreType(Store)) &&
            "Should be a known dependence");
 
-    // Currently we only support accesses with unit stride.  FIXME: we should be
-    // able to handle non unit stirde as well as long as the stride is equal to
-    // the dependence distance.
-    if (getPtrStride(PSE, LoadType, LoadPtr, L).value_or(0) != 1 ||
-        getPtrStride(PSE, LoadType, StorePtr, L).value_or(0) != 1)
+    int64_t StrideLoad = getPtrStride(PSE, LoadType, LoadPtr, L).value_or(0);
+    int64_t StrideStore = getPtrStride(PSE, LoadType, StorePtr, L).value_or(0);
+    if (!StrideLoad || !StrideStore || StrideLoad != StrideStore)
+      return false;
+
+    // TODO: This check for stride values other than 1 and -1 can be eliminated.
+    // However, doing so may cause the LoopAccessAnalysis to overcompensate,
+    // generating numerous non-wrap runtime checks that may undermine the
+    // benefits of load elimination. To safely implement support for non-unit
+    // strides, we would need to ensure either that the processed case does not
+    // require these additional checks, or improve the LAA to handle them more
+    // efficiently, or potentially both.
+    if (std::abs(StrideLoad) != 1)
       return false;
 
     unsigned TypeByteSize = DL.getTypeAllocSize(const_cast<Type *>(LoadType));
 
     auto *LoadPtrSCEV = cast<SCEVAddRecExpr>(PSE.getSCEV(LoadPtr));
     auto *StorePtrSCEV = cast<SCEVAddRecExpr>(PSE.getSCEV(StorePtr));
 
     // We don't need to check non-wrapping here because forward/backward
     // dependence wouldn't be valid if these weren't monotonic accesses.
     auto *Dist = cast<SCEVConstant>(
         PSE.getSE()->getMinusSCEV(StorePtrSCEV, LoadPtrSCEV));
     const APInt &Val = Dist->getAPInt();
-    return Val == TypeByteSize;
+    return Val == TypeByteSize * StrideLoad;
   }
 
   Value *getLoadPtr() const { return Load->getPointerOperand(); }
 
 #ifndef NDEBUG
   friend raw_ostream &operator<<(raw_ostream &OS,
                                  const StoreToLoadForwardingCandidate &Cand) {
     OS << *Cand.Store << " -->\n";

llvm/test/Transforms/LoopLoadElim/backward.ll

; CHECK: %add = add i32 %load_1, %store_forwarded
   %arrayidx_next = getelementptr inbounds i32, ptr %A, i64 %indvars.iv.next
   store i32 %add, ptr %arrayidx_next, align 4
   %exitcond = icmp eq i64 %indvars.iv.next, %N
   br i1 %exitcond, label %for.end, label %for.body
 
 for.end:                                          ; preds = %for.body
   ret void
 }
+
+; Same but loop is descending.
+;
+;   for (unsigned i = N; i > 0; i--)
+;     A[i-1] = A[i] + B[i];
+define void @g(ptr noalias nocapture %A, ptr noalias nocapture readonly %B, i64 %N) {
+entry:
+; CHECK: %0 = shl i64 %N, 2
+; CHECK: %scevgep = getelementptr i8, ptr %A, i64 %0
+; CHECK: %load_initial = load i32, ptr %scevgep, align 4
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+; CHECK: %store_forwarded = phi i32 [ %load_initial, %entry ], [ %add, %for.body ]
+  %i.09 = phi i64 [ %sub, %for.body ], [ %N, %entry ]
+  %arrayidx = getelementptr inbounds i32, ptr %A, i64 %i.09
+  %load = load i32, ptr %arrayidx, align 4
+  %arrayidx1 = getelementptr inbounds i32, ptr %B, i64 %i.09
+  %load_1 = load i32, ptr %arrayidx1, align 4
+; CHECK: %add = add i32 %load_1, %store_forwarded
+  %add = add i32 %load_1, %load
+  %sub = add i64 %i.09, -1
+  %arrayidx2 = getelementptr inbounds i32, ptr %A, i64 %sub
+  store i32 %add, ptr %arrayidx2, align 4
+  %cmp.not = icmp eq i64 %sub, 0
+  br i1 %cmp.not, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  ret void
+}
+