[LV] Use speculatability within entire loop to avoid strided load predication

[anna]

Summary

Use existing functionality for identifying total access size by strided
loads. If we can speculate the load across all vector iterations, we can
avoid predication for these strided loads (or masked gathers in
architectures which support it).

[anna]

updated tests

[anna]

AFAICT, the only thing which prevented us from figuring out dereferencability for strided loads (i.e. accesses with gaps) was identifying the correct AccessSize. So, that's basically the patch.

llvm/test/Transforms/LoopVectorize/X86/load-deref-pred.ll

1023 ↗

(On Diff #503790)

One thing I noticed is that we drop the inbounds on GEPs when we converted the masked loads to unmasked versions (perhaps because we cannot prove if the inbounds is correct without the predication?). We do not do the same "dropping of inbounds" when we removed predication for the strided case. Any idea why is that? It looks like we should be dropping on the strided case, but I don't know the LV code well enough to see where this is done and what is missing.

[reames]

llvm/lib/Analysis/Loads.cpp

294–304

Ignore is confusing here. "ignore" sounds like we might have a latent correctness issue here. What I think you mean is that we're being conservative on overlapping accesses.

Also, your TODO doesn't sound right to me. You'd want something along the lines of TC * Step + EltSize - Step.

[anna]

llvm/lib/Analysis/Loads.cpp

294–304

Good catch. TC * max(Step, EltSize) gets extra bytes without accounting for overlapping access.

[anna]

updated comment.

[reames]

LGTM w/minor comment

llvm/test/Transforms/LoopVectorize/X86/load-deref-pred.ll

1158 ↗

(On Diff #505486)

Remove TODO

[fhahn]

LGTM with the TODO in the test removed, thanks!

[anna]

llvm/test/Transforms/LoopVectorize/X86/load-deref-pred.ll

1023 ↗

(On Diff #503790)

Just to loop back on this:
I did some digging into history of where this inbounds drop was introduced. It was here: https://reviews.llvm.org/D111846. Also, there is a specific comment stating we do not need to drop inbounds (and other poison generating flags) when the original instructions are gather/scatter. If backends convert the gather/scatter into use "base + offsets", those backends need fixing (just paraphrasing from the comment here: https://reviews.llvm.org/D111846#3098547).

So, I'll go ahead and land this change.

[anna]

removed todo

llvm/lib/Analysis/Loads.cpp

bool llvm::isDereferenceableAndAlignedInLoop(LoadInst *LI, Loop *L,
   // Otherwise, check to see if we have a repeating access pattern where we can
   // prove that all accesses are well aligned and dereferenceable.
   auto *AddRec = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(Ptr));
   if (!AddRec || AddRec->getLoop() != L || !AddRec->isAffine())
     return false;
   auto* Step = dyn_cast<SCEVConstant>(AddRec->getStepRecurrence(SE));
   if (!Step)
     return false;
-  // TODO: generalize to access patterns which have gaps
-  if (Step->getAPInt() != EltSize)
-    return false;
 
   auto TC = SE.getSmallConstantMaxTripCount(L);
   if (!TC)
     return false;
 
-  const APInt AccessSize = TC * EltSize;
+  // For now, just ignore overlapping accesses.
+  // TODO: We should be taking max(Step,EltSize) for computing AccessSize
+  // below.
+  if (EltSize.sgt(Step->getAPInt()))
+    return false;
+  // Compute the total access size for access patterns with unit stride and
+  // patterns with gaps. For patterns with unit stride, Step and EltSize are the
+  // same.
+  // For patterns with gaps (i.e. non unit stride), we are
+  // accessing EltSize bytes at every Step.
+  const APInt AccessSize = TC * Step->getAPInt();
 
   auto *StartS = dyn_cast<SCEVUnknown>(AddRec->getStart());
   if (!StartS)
     return false;
   assert(SE.isLoopInvariant(StartS, L) && "implied by addrec definition");
   Value *Base = StartS->getValue();
 
   // For the moment, restrict ourselves to the case where the access size is a