[BasicAA] Use ranges for more than one index

[nikic]

Summary

D109746 made BasicAA use range information to determine the minimum/maximum GEP offset. However, it was limited to the case of a single variable index. This patch extends support to multiple indices by adding all the ranges together.

[courbet]

Nice !

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1283

this works because Scale and Offset (and therefore, Range) have the same bit width (MaxPointerSize). Maybe add an assert((Range.getBitWidth() == Scale.getBitWidth()) && "why this is guaranteed") ?

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);
     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() &&
+             "Bit widths are normalized to MaxPointerSize");
+      Range = Range.add(Index.Val
+                            .evaluateWith(computeConstantRange(
+                                Index.Val.V, true, &AC, Index.CxtI))
+                            .sextOrTrunc(Range.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
     // into the range [V2Size..GCD), then we know they cannot overlap.
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()))
+        return AliasResult::NoAlias;
+    }
+
     if (V1Size.hasValue() && V2Size.hasValue()) {
-      // Try to determine the range of values for VarIndex.
-      // VarIndexRange is such that:
-      //    (VarIndex <= -MinAbsVarIndex || MinAbsVarIndex <= VarIndex) &&
-      //    VarIndexRange.contains(VarIndex)
+      // Try to determine the range of values for VarIndex such that
+      // VarIndex <= -MinAbsVarIndex || MinAbsVarIndex <= VarIndex.
       Optional<APInt> MinAbsVarIndex;
-      Optional<ConstantRange> VarIndexRange;
       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) >= abs(Scale).
           MinAbsVarIndex = Var.Scale.abs();
         }
-        ConstantRange R = Var.Val.evaluateWith(
-            computeConstantRange(Var.Val.V, true, &AC, Var.CxtI));
-        if (!R.isFullSet() && !R.isEmptySet())
-          VarIndexRange = R.sextOrTrunc(Var.Scale.getBitWidth())
-                              .smul_fast(ConstantRange(Var.Scale));
       } 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 &&
             Var0.Val.hasSameCastsAs(Var1.Val) && VisitedPhiBBs.empty() &&
             isKnownNonEqual(Var0.Val.V, Var1.Val.V, DL, &AC, /* CxtI */ nullptr,
                             DT))
           MinAbsVarIndex = Var0.Scale.abs();
       }
 
       if (MinAbsVarIndex) {
         // The constant offset will have added at least +/-MinAbsVarIndex to it.
         APInt OffsetLo = DecompGEP1.Offset - *MinAbsVarIndex;
         APInt OffsetHi = DecompGEP1.Offset + *MinAbsVarIndex;
         // We know that Offset <= OffsetLo || Offset >= OffsetHi
         if (OffsetLo.isNegative() && (-OffsetLo).uge(V1Size.getValue()) &&
             OffsetHi.isNonNegative() && OffsetHi.uge(V2Size.getValue()))
           return AliasResult::NoAlias;
       }
-
-      if (VarIndexRange) {
-        ConstantRange OffsetRange =
-            VarIndexRange->add(ConstantRange(DecompGEP1.Offset));
-
-        // We know that Offset >= MinOffset.
-        // (MinOffset >= V2Size) => (Offset >= V2Size) => NoAlias.
-        if (OffsetRange.getSignedMin().sge(V2Size.getValue()))
-          return AliasResult::NoAlias;
-
-        // We know that Offset <= MaxOffset.
-        // (MaxOffset <= -V1Size) => (Offset <= -V1Size) => NoAlias.
-        if (OffsetRange.getSignedMax().sle(-V1Size.getValue()))
-          return AliasResult::NoAlias;
-      }
     }
 
     if (constantOffsetHeuristic(DecompGEP1, V1Size, V2Size, &AC, DT))
       return AliasResult::NoAlias;
   }
 
   // Statically, we can see that the base objects are the same, but the
   // pointers have dynamic offsets which we can't resolve. And none of our

llvm/test/Analysis/BasicAA/range.ll

 
 ; CHECK-LABEL: Function: multiple
 ; CHECK: MayAlias: i32* %p, i32* %p.01
 ; CHECK: MayAlias: i32* %p, i32* %p.02
 ; CHECK: MayAlias: i32* %p.01, i32* %p.02
 ; CHECK: NoAlias:  i32* %p.01, i32* %p.2
 ; CHECK: MayAlias: i32* %p.02, i32* %p.2
 ; CHECK: NoAlias:  i32* %p.01, i32* %p.3
-; TODO: This can be NoAlias.
-; CHECK: MayAlias: i32* %p.02, i32* %p.3
+; CHECK: NoAlias:  i32* %p.02, i32* %p.3
 define void @multiple(i32* %p, i32* %o1_ptr, i32* %o2_ptr) {
   %o1 = load i32, i32* %o1_ptr, !range !0
   %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