[BasicAA] Account for wrapping when using abs(VarIndex) >= abs(Scale).

[fhahn]

Summary

The patch adds an extra check to only set MinAbsVarIndex if
abs(V * Scale) won't wrap. In the absence of IsNSW, try to use the
bitwidths of the original V and Scale to rule out wrapping.

Attempt to model https://alive2.llvm.org/ce/z/HE8ZKj

The code in the else if below probably needs the same treatment, but I
need to come up with a test first.

[asbirlea]

LGTM.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

AliasResult BasicAAResult::aliasGEP(
   // Try to determine the range of values for VarIndex such that
   // VarIndex <= -MinAbsVarIndex || MinAbsVarIndex <= VarIndex.
   Optional<APInt> MinAbsVarIndex;
   if (DecompGEP1.VarIndices.size() == 1) {
     // VarIndex = Scale*V.
     const VariableGEPIndex &Var = DecompGEP1.VarIndices[0];
     if (Var.Val.TruncBits == 0 &&
         isKnownNonZero(Var.Val.V, DL, 0, &AC, Var.CxtI, DT)) {
+      // If V != 0, then abs(VarIndex) > 0.
+      MinAbsVarIndex = APInt(Var.Scale.getBitWidth(), 1);
+
+      // Check if abs(V*Scale) >= abs(Scale) holds in the presence of
+      // potentially wrapping math.
+      auto MultiplyByScaleNoWrap = [](const VariableGEPIndex &Var) {
+        if (Var.IsNSW)
+          return true;
+
+        int ValOrigBW = Var.Val.V->getType()->getPrimitiveSizeInBits();
+        // If Scale is small enough so that abs(V*Scale) >= abs(Scale) holds.
+        // The max value of abs(V) is 2^ValOrigBW - 1. Multiplying with a
+        // constant smaller than 2^(bitwidth(Val) - ValOrigBW) won't wrap.
+        int MaxScaleValueBW = Var.Val.getBitWidth() - ValOrigBW;
+        if (MaxScaleValueBW <= 0)
+          return false;
+        return Var.Scale.ule(
+            APInt::getMaxValue(MaxScaleValueBW).zext(Var.Scale.getBitWidth()));
+      };
+      // Refine MinAbsVarIndex, if abs(Scale*V) >= abs(Scale) holds in the
+      // presence of potentially wrapping math.
+      if (MultiplyByScaleNoWrap(Var)) {
         // If V != 0 then abs(VarIndex) >= abs(Scale).
         MinAbsVarIndex = Var.Scale.abs();
       }
+    }
   } else if (DecompGEP1.VarIndices.size() == 2) {
     // VarIndex = Scale*V0 + (-Scale)*V1.
     // If V0 != V1 then abs(VarIndex) >= abs(Scale).
     // Check that VisitedPhiBBs is empty, to avoid reasoning about
     // inequality of values across loop iterations.
     const VariableGEPIndex &Var0 = DecompGEP1.VarIndices[0];
     const VariableGEPIndex &Var1 = DecompGEP1.VarIndices[1];
     if (Var0.Scale == -Var1.Scale && Var0.Val.TruncBits == 0 &&

llvm/test/Analysis/BasicAA/gep-modulo.ll

;
   %gep.idx = getelementptr [ 200 x [ 6 x i8 ] ], [ 200 x [ 6 x i8 ] ]* %ptr, i64 0, i64 %idx.2, i64 %add
   store i8 0, i8* %gep.idx, align 1
   ret void
 }
 
 ; If %v == 10581764700698480926, %idx == 917, so %gep.917 and %gep.idx may alias.
 define i8 @mul_may_overflow_var_nonzero_minabsvarindex_one_index([2000 x i8]* %arr, i8 %x, i64 %v) {
 ; CHECK-LABEL: Function: mul_may_overflow_var_nonzero_minabsvarindex_one_index: 4 pointers, 0 call sites
-; CHECK-NEXT:  NoAlias: [2000 x i8]* %arr, i8* %gep.idx
+; CHECK-NEXT:  MayAlias: [2000 x i8]* %arr, i8* %gep.idx
 ; CHECK-NEXT:  PartialAlias (off 917): [2000 x i8]* %arr, i8* %gep.917
-; CHECK-NEXT:  NoAlias: i8* %gep.917, i8* %gep.idx
+; CHECK-NEXT:  MayAlias: i8* %gep.917, i8* %gep.idx
 ; CHECK-NEXT:  MustAlias: [2000 x i8]* %arr, i8* %gep.0
 ; CHECK-NEXT:  NoAlias: i8* %gep.0, i8* %gep.idx
 ; CHECK-NEXT:  NoAlias: i8* %gep.0, i8* %gep.917
 ;
   load [2000 x i8], [2000 x i8]* %arr
   %or = or i64 %v, 1
   %idx = mul i64 %or, 1844674407370955
   %gep.idx = getelementptr inbounds [2000 x i8], [2000 x i8]* %arr, i32 0, i64 %idx