[BasicAA] Teach BasicAA about GEP variable index ranges.

[courbet]

Summary

Note that this is not as complete as what SCEV can do, but it's fast,
and it's enough for the common case, which is clang setting !range
metadata on array subscript indices.

[courbet]

Add more proposals for representing the range data.

[nikic]

Abandon this as D109746 landed?

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 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) &&
+      //    MinVarIndex <= VarIndex && VarIndex <= MaxVarIndex
       Optional<APInt> MinAbsVarIndex;
+      Optional<APInt> MinVarIndex;
+      Optional<APInt> MaxVarIndex;
       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()) {
+          // Close the open range.
+          APInt MinV = R.getLower();
+          APInt MaxV = R.getUpper() - 1;
+          // If Scale < 0, inverse the range so that Scale >= 0.
+          if (Var.Scale.isNegative()) {
+            MinV = -MaxV;
+            MaxV = -MinV;
+          }
+          MinVarIndex =
+              Var.Scale.abs() * MinV.sextOrTrunc(Var.Scale.getBitWidth());
+          MaxVarIndex =
+              Var.Scale.abs() * MaxV.sextOrTrunc(Var.Scale.getBitWidth());
+        }
       } 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 NoAlias;
       }
+
+      if (MinVarIndex) {
+        APInt MinOffset = DecompGEP1.Offset + *MinVarIndex;
+        // We know that Offset >= MinOffset.
+        // (MinOffset >= V2Size) => (Offset >= V2Size) => NoAlias.
+        if (MinOffset.sge(V2Size.getValue())) {
+          return NoAlias;
+        }
+      }
+
+      if (MaxVarIndex) {
+        APInt MaxOffset = DecompGEP1.Offset + *MaxVarIndex;
+        // We know that Offset <= MaxOffset.
+        // (MaxOffset <= -V1Size) => (Offset <= -V1Size) => NoAlias.
+        if (MaxOffset.sle(-V1Size.getValue())) {
+          return NoAlias;
+        }
+      }
     }
 
     if (constantOffsetHeuristic(DecompGEP1.VarIndices, V1Size, V2Size,
                                 DecompGEP1.Offset, &AC, DT))
       return NoAlias;
   }
 
   // Statically, we can see that the base objects are the same, but the

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

;
   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 }
+
+declare i32 @llvm.annotation.i32(i32, i8*, i8*, i32)
+declare void @llvm.assume(i1)
+
+; 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: member_before_with_assume
+; CHECK: NoAlias: i32* %gep1, i32* %gep2
+define void @member_before_with_assume(%struct.S* %s, i32 %in_array) {
+  %cmp1 = icmp sge i32 %in_array, 0
+  %cmp2 = icmp slt i32 %in_array, 2
+  %cmp = and i1 %cmp1, %cmp2
+  call void @llvm.assume(i1 %cmp)
+  %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_with_inrange
+; CHECK: NoAlias: i32* %gep1, i32* %gep2
+define void @member_before_with_inrange(%struct.S* %s, i32 %in_array) {
+  %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, inrange i32 %in_array
+  %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 0
+  ret void
+}
+
+; CHECK: Function: member_before_with_assume_bundle
+; CHECK: NoAlias: i32* %gep1, i32* %gep2
+define void @member_before_with_assume_bundle(%struct.S* %s, i32 %in_array) {
+  call void @llvm.assume(i1 true) ["range"(i32 %in_array, i32 0, i32 2)]
+  %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
+}
+
+!0 = !{ i32 0, i32 2 }
+!1 = !{ i32 0, i32 1 }
+!2 = !{ i32 1, i32 2 }

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 }