[AA] Teach BasicAA to recognize basic GEP range information.

[courbet]

Summary

The information can be implicit (from ValueTracking) or explicit.

This implements the backend part of the following RFC
https://groups.google.com/g/llvm-dev/c/T9o51zB1JY.

We still need to settle on how to best represent the information in the
IR, but this is a separate discussion.

[nikic]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1233

Ranges can be wrapping, you're probably looking for getSignedMin() and getSignedMax() here.

1242

Can't you use the ConstantRange API to perform the multiplication by the scale?

Also, we need to consider overflow here. If the NSW flag is set we can exclude overflow and perform a saturating multiplication, but otherwise we need to take it into account, and this is not just a matter of multiplying the bounds. ConstantRange should do that correctly, though conservatively. We should have tests for this as well.

[courbet]

Use the ConstantRange API for mutiplication and addition. Add more tests.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1242

Thanks for the suggestion. In addition to correctness, that actually makes the code much simpler too.

I've added a bunch of tests that exercise various edge cases.

[nikic]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1231

The Var represents a zext(sext(V)) * Scale, so this sextOrTrunc isn't right if ZExtBits is non-zero. We first need an (optional) sext and then an (optional) zext.

[nikic]

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

130

This doesn't really preserve the spirit of the test. Would it be possible to adjust the range metadata instead, to something like !{ i32 1, i32 0 }, to get a range that only excludes zero?

[courbet]

• Conditionally zext/sext if needed.
• Add test with zero extension.

[courbet]

Thanks

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1231

Done. I've also added a unit test with a zero extension that fails without this change.

[courbet]

revert naming changes in tests

[nikic]

LGTM

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1222

The code added here doesn't really rely on the fact that there is only a single index -- it could be integrated in the GCD/AllNonNegative/AllNonPositive loop above instead and add up the ranges of all indices. I'm okay with landing it in this limited form first though.

1234

It's possible for both SExtBits and ZExtBits to be non-zero, so this should be extending to R.getBitWidth() + Var.SExtBits + Var.ZExtBits.

1235

We probably don't need this sextOrTrunc() anymore?

1265

nit: Braces are unnecessary here.

llvm/test/Analysis/BasicAA/range.ll

7

Seems to be unused?

[courbet]

Thanks a lot for the review.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1234

If that's the case, R has been sign-extended above, so Var.SExtBits is already counted in R.getBitWidth() (which is not the same as on line 1232)

1235

We still need to extend from 32 to 64 bits when --basic-aa-force-at-least-64b=0. This is apparently not taken into account in SExtBits/ZExtBits.

[courbet]

fix last comments

[nikic]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1234

Oh right, that makes sense!

1235

The case where an extend is needed should be represented by SExtBits -- but the reverse case (where a truncate is needed) is currently not represented (which is an open bug). So yeah, you're right and we can't drop this entirely.

[courbet]

This optimization seems to have uncovered a latent bug in LoopIdiom: https://bugs.llvm.org/show_bug.cgi?id=52104.

[xbolva00]

llvm/test/Analysis/BasicAA/assume-index-positive.ll

57

Comments needs to be adjusted.

[courbet]

llvm/test/Analysis/BasicAA/assume-index-positive.ll

57

Fixed in 342d7b654c63cadaa6135913c9582a7272fced58: "Same as @test1, this time the assume just guarantees %skip > -3, which is
enough to derive NoAlias for %ptr and %col.ptr.2 (distance is more than 3 doubles, and we load 1 double), but not %col.ptr.1 and %col.ptr.2 (distance is more than 3 doubles, and we load 6 doubles)."

llvm/lib/Analysis/BasicAliasAnalysis.cpp

 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/MemoryLocation.h"
 #include "llvm/Analysis/PhiValues.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/Constant.h"
+#include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
 #include "llvm/IR/GlobalAlias.h"
 #include "llvm/IR/GlobalVariable.h"
if (!DecompGEP1.VarIndices.empty()) {
     // 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 (V1Size.hasValue() && V2Size.hasValue()) {
-      // Try to determine whether abs(VarIndex) > 0.
+      // Try to determine the range of values for VarIndex.
+      // VarIndexRange is such that:
+      //    (VarIndex <= -MinAbsVarIndex || MinAbsVarIndex <= VarIndex) &&
+      //    VarIndexRange.contains(VarIndex)
       Optional<APInt> MinAbsVarIndex;
+      Optional<ConstantRange> VarIndexRange;
       if (DecompGEP1.VarIndices.size() == 1) {
-        // VarIndex = Scale*V. If V != 0 then abs(VarIndex) >= abs(Scale).
+        // VarIndex = Scale*V.
         const VariableGEPIndex &Var = DecompGEP1.VarIndices[0];
-        if (isKnownNonZero(Var.V, DL, 0, &AC, Var.CxtI, DT))
+        if (isKnownNonZero(Var.V, DL, 0, &AC, Var.CxtI, DT)) {
+          // If V != 0 then abs(VarIndex) >= abs(Scale).
           MinAbsVarIndex = Var.Scale.abs();
+        }
+        ConstantRange R = computeConstantRange(Var.V, true, &AC, Var.CxtI);
+        if (!R.isFullSet() && !R.isEmptySet()) {
+          VarIndexRange = R.sextOrTrunc(Var.Scale.getBitWidth())
+                              .multiply(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.ZExtBits == Var1.ZExtBits &&
             Var0.SExtBits == Var1.SExtBits && VisitedPhiBBs.empty() &&
             isKnownNonEqual(Var0.V, Var1.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;
-        // Check that an access at OffsetLo or lower, and an access at OffsetHi
-        // or higher both do not alias.
+        // 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.VarIndices, V1Size, V2Size,
                                 DecompGEP1.Offset, &AC, DT))
       return AliasResult::NoAlias;
   }
 
   // Statically, we can see that the base objects are the same, but the

llvm/test/Analysis/BasicAA/assume-index-positive.ll

;
   %lv.2 = load <6 x double>, <6 x double>* %col.ptr.2.cast, align 8
   %res.1 = fadd <6 x double> %lv.1, %lv.1
   %res.2 = fadd <6 x double> %lv.2, %lv.2
   store <6 x double> %res.1, <6 x double>* %col.ptr.1, align 8
   store <6 x double> %res.2, <6 x double>* %col.ptr.2.cast, align 8
   ret void
 }
 
 ; Same as @test1, but the assume just guarantees %skip > -3, which is not
 ; enough to derive NoAlias
 define void @test3(double* %ptr, i32 %skip) {
 ; CHECK-LABEL: Function: test3: 4 pointers, 1 call sites
 ; CHECK-NEXT:  MustAlias:   <6 x double>* %col.ptr.1, double* %ptr
-; CHECK-NEXT:  MayAlias:    double* %col.ptr.2, double* %ptr
+; CHECK-NEXT:  NoAlias:     double* %col.ptr.2, double* %ptr
 ; CHECK-NEXT:  MayAlias:    <6 x double>* %col.ptr.1, double* %col.ptr.2
-; CHECK-NEXT:  MayAlias:    <6 x double>* %col.ptr.2.cast, double* %ptr
+; CHECK-NEXT:  NoAlias:     <6 x double>* %col.ptr.2.cast, double* %ptr
 ; CHECK-NEXT:  MayAlias:    <6 x double>* %col.ptr.1, <6 x double>* %col.ptr.2.cast
 ; CHECK-NEXT:  MustAlias:   <6 x double>* %col.ptr.2.cast, double* %col.ptr.2
 ; CHECK-NEXT:  NoModRef:  Ptr: double* %ptr <->  call void @llvm.assume(i1 %gt)
 ; CHECK-NEXT:  NoModRef:  Ptr: <6 x double>* %col.ptr.1 <->  call void @llvm.assume(i1 %gt)
 ; CHECK-NEXT:  NoModRef:  Ptr: double* %col.ptr.2   <->  call void @llvm.assume(i1 %gt)
 ; CHECK-NEXT:  NoModRef:  Ptr: <6 x double>* %col.ptr.2.cast    <->  call void @llvm.assume(i1 %gt)
 ;
   %gt = icmp sgt i32 %skip, -3

llvm/test/Analysis/BasicAA/range.ll

+; RUN: opt < %s -basic-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+%struct.S = type { i32, [2 x i32], i32 }
+%struct.S2 = type { i32, [4 x i32], [4 x i32] }
+
+declare i32 @llvm.annotation.i32(i32, i8*, i8*, i32)
+
+
+; CHECK: Function: t1
+; CHECK: NoAlias: i32* %gep1, i32* %gep2
+define void @t1(%struct.S* %s) {
+  %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 1
+  %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 0
+  ret void
+}
+
+; CHECK: Function: t2_fwd
+; CHECK: MayAlias: i32* %gep1, i32* %gep2
+define void @t2_fwd(%struct.S* %s, i32* %q) {
+  %in_array = load i32, i32* %q, !range !0
+  %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 %in_array
+  %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 0
+  ret void
+}
+
+; CHECK: Function: t2_rev
+; CHECK: MayAlias: i32* %gep1, i32* %gep2
+define void @t2_rev(%struct.S* %s, i32* %q) {
+  %in_array = load i32, i32* %q, !range !0
+  %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 0
+  %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 %in_array
+  ret void
+}
+
+; CHECK: Function: t3_fwd
+; CHECK: NoAlias: i32* %gep1, i32* %gep2
+define void @t3_fwd(%struct.S* %s, i32* %q) {
+  %knownzero = load i32, i32* %q, !range !1
+  %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 %knownzero
+  %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 1
+  ret void
+}
+
+; CHECK: Function: t3_rev
+; CHECK: NoAlias: i32* %gep1, i32* %gep2
+define void @t3_rev(%struct.S* %s, i32* %q) {
+  %knownzero = load i32, i32* %q, !range !1
+  %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 1
+  %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 %knownzero
+  ret void
+}
+
+; CHECK: Function: member_after
+; CHECK: NoAlias: i32* %gep1, i32* %gep2
+define void @member_after(%struct.S* %s, i32* %q) {
+  %in_array = load i32, i32* %q, !range !0
+  %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 %in_array
+  %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 2
+  ret void
+}
+
+; CHECK: Function: member_after_rev
+; CHECK: NoAlias: i32* %gep1, i32* %gep2
+define void @member_after_rev(%struct.S* %s, i32* %q) {
+  %in_array = load i32, i32* %q, !range !0
+  %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 2
+  %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 %in_array
+  ret void
+}
+
+; CHECK: Function: member_before
+; CHECK: NoAlias: i32* %gep1, i32* %gep2
+define void @member_before(%struct.S* %s, i32* %q) {
+  %in_array = load i32, i32* %q, !range !0
+  %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 %in_array
+  %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 0
+  ret void
+}
+
+; CHECK: Function: member_before_rev
+; CHECK: NoAlias: i32* %gep1, i32* %gep2
+define void @member_before_rev(%struct.S* %s, i32* %q) {
+  %in_array = load i32, i32* %q, !range !0
+  %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 0
+  %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 %in_array
+  ret void
+}
+
+; CHECK: Function: t5
+; CHECK-NEXT: MayAlias: %struct.S2* %s, i32* %q
+; CHECK-NEXT: MayAlias: %struct.S2* %s, i32* %gep1
+; CHECK-NEXT: MayAlias: i32* %gep1, i32* %q
+; CHECK-NEXT: PartialAlias (off 4): %struct.S2* %s, i32* %gep2
+; CHECK-NEXT: MayAlias: i32* %gep2, i32* %q
+; CHECK-NEXT: NoAlias: i32* %gep1, i32* %gep2
+define void @t5(%struct.S2* %s, i32* %q) {
+  %in_array = load i32, i32* %q, !range !3
+  %gep1 = getelementptr inbounds %struct.S2, %struct.S2* %s, i64 0, i32 2, i32 %in_array
+  %gep2 = getelementptr inbounds %struct.S2, %struct.S2* %s, i64 0, i32 1, i32 0
+  ret void
+}
+
+; CHECK: Function: t6
+; CHECK-NEXT: MayAlias: %struct.S2* %s, i32* %q
+; CHECK-NEXT: MayAlias: %struct.S2* %s, i32* %gep1
+; CHECK-NEXT: MayAlias: i32* %gep1, i32* %q
+; CHECK-NEXT: PartialAlias (off 16): %struct.S2* %s, i32* %gep2
+; CHECK-NEXT: MayAlias: i32* %gep2, i32* %q
+; CHECK-NEXT: MayAlias: i32* %gep1, i32* %gep2
+define void @t6(%struct.S2* %s, i32* %q) {
+  %in_array = load i32, i32* %q, !range !3
+  %gep1 = getelementptr inbounds %struct.S2, %struct.S2* %s, i64 0, i32 2, i32 %in_array
+  %gep2 = getelementptr inbounds %struct.S2, %struct.S2* %s, i64 0, i32 1, i32 3
+  ret void
+}
+
+; CHECK: Function: t7
+; CHECK-NEXT: MayAlias: %struct.S2* %s, i32* %q
+; CHECK-NEXT: MayAlias: %struct.S2* %s, i32* %gep1
+; CHECK-NEXT: MayAlias: i32* %gep1, i32* %q
+; CHECK-NEXT: PartialAlias (off 20): %struct.S2* %s, i32* %gep2
+; CHECK-NEXT: MayAlias: i32* %gep2, i32* %q
+; CHECK-NEXT: NoAlias: i32* %gep1, i32* %gep2
+define void @t7(%struct.S2* %s, i32* %q) {
+  %in_array = load i32, i32* %q, !range !4
+  %gep1 = getelementptr inbounds %struct.S2, %struct.S2* %s, i64 0, i32 2, i32 %in_array
+  %gep2 = getelementptr inbounds %struct.S2, %struct.S2* %s, i64 0, i32 2, i32 0
+  ret void
+}
+
+; CHECK: Function: t8
+; CHECK-NEXT: MayAlias: %struct.S2* %s, i32* %q
+; CHECK-NEXT: MayAlias: %struct.S2* %s, i32* %gep1
+; CHECK-NEXT: MayAlias: i32* %gep1, i32* %q
+; CHECK-NEXT: PartialAlias (off 24): %struct.S2* %s, i32* %gep2
+; CHECK-NEXT: MayAlias: i32* %gep2, i32* %q
+; CHECK-NEXT: MayAlias: i32* %gep1, i32* %gep2
+define void @t8(%struct.S2* %s, i32* %q) {
+  %in_array = load i32, i32* %q, !range !4
+  %gep1 = getelementptr inbounds %struct.S2, %struct.S2* %s, i64 0, i32 2, i32 %in_array
+  %gep2 = getelementptr inbounds %struct.S2, %struct.S2* %s, i64 0, i32 2, i32 1
+  ret void
+}
+
+; CHECK: Function: t9
+; CHECK-NEXT: MayAlias: %struct.S2* %s, i32* %q
+; CHECK-NEXT: MayAlias: %struct.S2* %s, i32* %gep1
+; CHECK-NEXT: MayAlias: i32* %gep1, i32* %q
+; CHECK-NEXT: PartialAlias (off 20): %struct.S2* %s, i32* %gep2
+; CHECK-NEXT: MayAlias: i32* %gep2, i32* %q
+; CHECK-NEXT: NoAlias: i32* %gep1, i32* %gep2
+define void @t9(%struct.S2* %s, i32* %q) {
+  %in_array = load i32, i32* %q, !range !5
+  %gep1 = getelementptr inbounds %struct.S2, %struct.S2* %s, i64 0, i32 1, i32 %in_array
+  %gep2 = getelementptr inbounds %struct.S2, %struct.S2* %s, i64 0, i32 2, i32 0
+  ret void
+}
+
+; CHECK: Function: t10
+; CHECK-NEXT: MayAlias: %struct.S2* %s, i32* %q
+; CHECK-NEXT: MayAlias: %struct.S2* %s, i32* %gep1
+; CHECK-NEXT: MayAlias: i32* %gep1, i32* %q
+; CHECK-NEXT: PartialAlias (off 4): %struct.S2* %s, i32* %gep2
+; CHECK-NEXT: MayAlias: i32* %gep2, i32* %q
+; CHECK-NEXT: MayAlias: i32* %gep1, i32* %gep2
+define void @t10(%struct.S2* %s, i32* %q) {
+  %in_array = load i32, i32* %q, !range !5
+  %gep1 = getelementptr inbounds %struct.S2, %struct.S2* %s, i64 0, i32 2, i32 %in_array
+  %gep2 = getelementptr inbounds %struct.S2, %struct.S2* %s, i64 0, i32 1, i32 0
+  ret void
+}
+
+!0 = !{ i32 0, i32 2 }
+!1 = !{ i32 0, i32 1 }
+!2 = !{ i32 1, i32 2 }
+!3 = !{ i32 -2, i32 0 }
+!4 = !{ i32 1, i32 536870911 }
+!5 = !{ i32 -536870911, i32 4 }

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

define void @add_non_zero_assume(i32* %p, i32 %addend, i32 %knownnonzero) {
   %gep1 = getelementptr i32, i32* %p, i32 %addend
   %gep2 = getelementptr i32, i32* %p, i32 %add
   ret void
 }
 
 ; CHECK-LABEL: non_zero_index_simple
 ; CHECK: NoAlias: i32* %gep, i32* %p
 ; CHECK: NoAlias: i16* %gep.16, i32* %p
-; CHECK: MayAlias: i32* %p, i64* %gep.64
+; CHECK: NoAlias: i32* %p, i64* %gep.64
 define void @non_zero_index_simple(i32* %p, i32* %q) {
-  %knownnonzero = load i32, i32* %q, !range !0
-  %gep = getelementptr i32, i32* %p, i32 %knownnonzero
+  %known_in_1_5 = load i32, i32* %q, !range !0
+  %gep = getelementptr i32, i32* %p, i32 %known_in_1_5
   %gep.16 = bitcast i32* %gep to i16*
   %gep.64 = bitcast i32* %gep to i64*
   ret void
 }
 
 ; CHECK-LABEL: non_zero_index_with_offset
-; CHECK: MayAlias: i32* %gep, i32* %p
+; CHECK: NoAlias: i32* %gep, i32* %p
 ; CHECK: NoAlias: i16* %gep.16, i32* %p
 define void @non_zero_index_with_offset(i32* %p, i32* %q) {
-  %knownnonzero = load i32, i32* %q, !range !0
+  %known_in_1_5 = load i32, i32* %q, !range !0
   %p.8 = bitcast i32* %p to i8*
   %p.off.8 = getelementptr i8, i8* %p.8, i32 2
   %p.off = bitcast i8* %p.off.8 to i32*
-  %gep = getelementptr i32, i32* %p.off, i32 %knownnonzero
+  %gep = getelementptr i32, i32* %p.off, i32 %known_in_1_5
   %gep.16 = bitcast i32* %gep to i16*
   ret void
 }
 
 ; CHECK-LABEL: non_zero_index_assume
 ; CHECK: NoAlias: i32* %gep, i32* %p
 define void @non_zero_index_assume(i32* %p, i32 %knownnonzero) {
   %cmp = icmp ne i32 %knownnonzero, 0
   call void @llvm.assume(i1 %cmp)
   %gep = getelementptr i32, i32* %p, i32 %knownnonzero
   ret void
 }
 
 declare void @llvm.assume(i1)
 
 !0 = !{ i32 1, i32 5 }