[BasicAA] Check for Overflow using vscale_range (#81144)

This extends #80818 when IsNSW is lost (possibly due to looking through
multiple GEPs), to check the vscale_range for an access that will not
overflow even with the maximum range.

1 files changed, 17 insertions, 7 deletions

diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/llvm/lib/Analysis/BasicAliasAnalysis.cpp
index 682b0a2..2ea2917 100644
--- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp
+++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp
@@ -1173,7 +1173,7 @@ AliasResult BasicAAResult::aliasGEP(
   // VScale Alias Analysis - Given one scalable offset between accesses and a
   // scalable typesize, we can divide each side by vscale, treating both values
   // as a constant. We prove that Offset/vscale >= TypeSize/vscale.
-  if (DecompGEP1.VarIndices.size() == 1 && DecompGEP1.VarIndices[0].IsNSW &&
+  if (DecompGEP1.VarIndices.size() == 1 &&
       DecompGEP1.VarIndices[0].Val.TruncBits == 0 &&
       DecompGEP1.Offset.isZero() &&
       PatternMatch::match(DecompGEP1.VarIndices[0].Val.V,
@@ -1183,12 +1183,22 @@ AliasResult BasicAAResult::aliasGEP(
         ScalableVar.IsNegated ? -ScalableVar.Scale : ScalableVar.Scale;
     LocationSize VLeftSize = Scale.isNegative() ? V1Size : V2Size;
 
-    // Note that we do not check that the typesize is scalable, as vscale >= 1
-    // so noalias still holds so long as the dependency distance is at least as
-    // big as the typesize.
-    if (VLeftSize.hasValue() &&
-        Scale.abs().uge(VLeftSize.getValue().getKnownMinValue()))
-      return AliasResult::NoAlias;
+    // Check if the offset is known to not overflow, if it does then attempt to
+    // prove it with the known values of vscale_range.
+    bool Overflows = !DecompGEP1.VarIndices[0].IsNSW;
+    if (Overflows) {
+      ConstantRange CR = getVScaleRange(&F, Scale.getBitWidth());
+      (void)CR.getSignedMax().smul_ov(Scale, Overflows);
+    }
+
+    if (!Overflows) {
+      // Note that we do not check that the typesize is scalable, as vscale >= 1
+      // so noalias still holds so long as the dependency distance is at least
+      // as big as the typesize.
+      if (VLeftSize.hasValue() &&
+          Scale.abs().uge(VLeftSize.getValue().getKnownMinValue()))
+        return AliasResult::NoAlias;
+    }
   }
 
   // Bail on analysing scalable LocationSize