[BasicAA] Make range check more precise

[nikic]

Summary

Make the range check more precise by calculating the range of potentially accessed bytes for both accesses and checking whether their intersection is empty. In that case there can be no overlap between the accesses and the result is NoAlias.

This is more powerful than the previous approach, because it can deal with sign-wrapped ranges. In the test case the original range is [-1, INT_MAX] but becomes [0, INT_MIN] after applying the offset. This is a wrapping range, so getSignedMin/getSignedMax will treat it as a full range. However, the range excludes the elements [INT_MIN+1, -1], which is enough to prove NoAlias with an access at offset -1.

[reames]

LGTM w/minor change suggested.

It looks like this structure might subsume some of the nearby checks as well, but that can be explored in a follow up.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1323

Rather than mutating an existing variable (which might be used later), I'd just use a new variable name here. e.g. AccessRange

llvm/lib/Analysis/BasicAliasAnalysis.cpp

if (VLeftSize.hasValue()) {
       return AliasResult::NoAlias;
     }
   }
 
   if (!DecompGEP1.VarIndices.empty()) {
     APInt GCD;
     bool AllNonNegative = DecompGEP1.Offset.isNonNegative();
     bool AllNonPositive = DecompGEP1.Offset.isNonPositive();
-    ConstantRange Range = ConstantRange(DecompGEP1.Offset);
+    ConstantRange OffsetRange = ConstantRange(DecompGEP1.Offset);
     for (unsigned i = 0, e = DecompGEP1.VarIndices.size(); i != e; ++i) {
       const VariableGEPIndex &Index = DecompGEP1.VarIndices[i];
       const APInt &Scale = Index.Scale;
       APInt ScaleForGCD = Scale;
       if (!Index.IsNSW)
         ScaleForGCD = APInt::getOneBitSet(Scale.getBitWidth(),
                                           Scale.countTrailingZeros());
 
       if (i == 0)
         GCD = ScaleForGCD.abs();
       else
         GCD = APIntOps::GreatestCommonDivisor(GCD, ScaleForGCD.abs());
 
       if (AllNonNegative || AllNonPositive) {
         KnownBits Known = Index.Val.evaluateWith(
             computeKnownBits(Index.Val.V, DL, 0, &AC, Index.CxtI, DT));
         bool SignKnownZero = Known.isNonNegative();
         bool SignKnownOne = Known.isNegative();
         AllNonNegative &= (SignKnownZero && Scale.isNonNegative()) ||
                           (SignKnownOne && Scale.isNonPositive());
         AllNonPositive &= (SignKnownZero && Scale.isNonPositive()) ||
                           (SignKnownOne && Scale.isNonNegative());
       }
 
-      assert(Range.getBitWidth() == Scale.getBitWidth() &&
+      assert(OffsetRange.getBitWidth() == Scale.getBitWidth() &&
              "Bit widths are normalized to MaxPointerSize");
-      Range = Range.add(Index.Val
+      OffsetRange = OffsetRange.add(Index.Val
                             .evaluateWith(computeConstantRange(
                                 Index.Val.V, true, &AC, Index.CxtI))
-                            .sextOrTrunc(Range.getBitWidth())
+                            .sextOrTrunc(OffsetRange.getBitWidth())
                             .smul_fast(ConstantRange(Scale)));
     }
 
     // We now have accesses at two offsets from the same base:
     //  1. (...)*GCD + DecompGEP1.Offset with size V1Size
     //  2. 0 with size V2Size
     // Using arithmetic modulo GCD, the accesses are at
     // [ModOffset..ModOffset+V1Size) and [0..V2Size). If the first access fits
if (!DecompGEP1.VarIndices.empty()) {
     // Similarly, if the variables are non-positive, then the total offset is
     // also non-positive and <= DecompGEP1.Offset. We have the following layout:
     // [TotalOffset, TotalOffset+V1Size) ... [0, V2Size)
     // If -DecompGEP1.Offset >= V1Size, the accesses don't alias.
     if (AllNonPositive && V1Size.hasValue() &&
         (-DecompGEP1.Offset).uge(V1Size.getValue()))
       return AliasResult::NoAlias;
 
-    if (!Range.isEmptySet()) {
-      // We know that Offset >= MinOffset.
-      // (MinOffset >= V2Size) => (Offset >= V2Size) => NoAlias.
-      if (V2Size.hasValue() && Range.getSignedMin().sge(V2Size.getValue()))
-        return AliasResult::NoAlias;
-
-      // We know that Offset <= MaxOffset.
-      // (MaxOffset <= -V1Size) => (Offset <= -V1Size) => NoAlias.
-      if (V1Size.hasValue() && Range.getSignedMax().sle(-V1Size.getValue()))
+    if (V1Size.hasValue() && V2Size.hasValue()) {
+      // Compute ranges of potentially accessed bytes for both accesses. If the
+      // interseciton is empty, there can be no overlap.
+      unsigned BW = OffsetRange.getBitWidth();
+      ConstantRange Range1 = OffsetRange.add(
+          ConstantRange(APInt(BW, 0), APInt(BW, V1Size.getValue())));
+      ConstantRange Range2 =
+          ConstantRange(APInt(BW, 0), APInt(BW, V2Size.getValue()));
+      if (Range1.intersectWith(Range2).isEmptySet())
         return AliasResult::NoAlias;
     }
 
     if (V1Size.hasValue() && V2Size.hasValue()) {
       // Try to determine the range of values for VarIndex such that
       // VarIndex <= -MinAbsVarIndex || MinAbsVarIndex <= VarIndex.
       Optional<APInt> MinAbsVarIndex;
       if (DecompGEP1.VarIndices.size() == 1) {

llvm/test/Analysis/BasicAA/range.ll

define void @multiple(i32* %p, i32* %o1_ptr, i32* %o2_ptr) {
   %o2 = load i32, i32* %o2_ptr, !range !0
   %p.01 = getelementptr i32, i32* %p, i32 %o1  ; p + [0, 1]
   %p.02 = getelementptr i32, i32* %p.01, i32 %o2 ; p + [0, 2]
   %p.2 = getelementptr i32, i32* %p, i32 2
   %p.3 = getelementptr i32, i32* %p, i32 3
   ret void
 }
 
-; TODO: p.neg1 and p.o.1 don't alias, even though the addition o+1 may overflow.
+; p.neg1 and p.o.1 don't alias, even though the addition o+1 may overflow.
 ; While it makes INT_MIN a possible offset, offset -1 is not possible.
 ; CHECK-LABEL: Function: benign_overflow
 ; CHECK: MayAlias: i8* %p, i8* %p.o
 ; CHECK: MayAlias: i8* %p.neg1, i8* %p.o
 ; CHECK: MayAlias: i8* %p, i8* %p.o.1
-; CHECK: MayAlias: i8* %p.neg1, i8* %p.o.1
+; CHECK: NoAlias: i8* %p.neg1, i8* %p.o.1
 ; CHECK: NoAlias:  i8* %p.o, i8* %p.o.1
 define void @benign_overflow(i8* %p, i64 %o) {
   %c = icmp sge i64 %o, -1
   call void @llvm.assume(i1 %c)
   %p.neg1 = getelementptr i8, i8* %p, i64 -1
   %p.o = getelementptr i8, i8* %p, i64 %o
   %p.o.1 = getelementptr i8, i8* %p.o, i64 1
   ret void