[BasicAA] Handle known non-zero variable index

[nikic]

Summary

BasicAA currently handles cases like Scale*V0 + (-Scale)*V1 where V0 != V1, but does not handle the simpler case of Scale*V with V != 0. Add it based on an isKnownNonZero() call.

I'm not passing a context instruction for now, because the existing approach of always using GEP1 for context could result in symmetry issues.

Compile-time impact is close to zero: https://llvm-compile-time-tracker.com/compare.php?from=5e69e2ebad9db2af44362ebe1755c08af002798f&to=2dffc47368b820c651c34156a503943234ea0252&stat=instructions

[reames]

LGTM.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

if (!DecompGEP1.VarIndices.empty()) {
     // 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.
       Optional<APInt> MinAbsVarIndex;
-      // TODO: Could handle single non-zero index as well.
-      if (DecompGEP1.VarIndices.size() == 2) {
+      if (DecompGEP1.VarIndices.size() == 1) {
+        // VarIndex = Scale*V. If V != 0 then abs(VarIndex) >= abs(Scale).
+        const VariableGEPIndex &Var = DecompGEP1.VarIndices[0];
+        if (isKnownNonZero(Var.V, DL))
+          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.ZExtBits == Var1.ZExtBits &&
             Var0.SExtBits == Var1.SExtBits && VisitedPhiBBs.empty() &&

llvm/test/Analysis/BasicAA/bug.23626.ll

 ; RUN: opt < %s -basic-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-darwin13.4.0"
 
 ; CHECK-LABEL: compute1
 ; CHECK: MayAlias:  i32* %arrayidx8, i32* %out
-; CHECK: MayAlias:  i32* %arrayidx11, i32* %out
+; CHECK: NoAlias: i32* %arrayidx11, i32* %out
 ; CHECK: MayAlias:  i32* %arrayidx11, i32* %arrayidx8
-; CHECK: MayAlias:  i32* %arrayidx14, i32* %out
+; CHECK: NoAlias: i32* %arrayidx14, i32* %out
 ; CHECK: MayAlias:  i32* %arrayidx14, i32* %arrayidx8
 ; CHECK: MayAlias:  i32* %arrayidx11, i32* %arrayidx14
 define void @compute1(i32 %num.0.lcssa, i32* %out) {
   %idxprom = zext i32 %num.0.lcssa to i64
   %arrayidx8 = getelementptr inbounds i32, i32* %out, i64 %idxprom
   %add9 = or i32 %num.0.lcssa, 1
   %idxprom10 = zext i32 %add9 to i64
   %arrayidx11 = getelementptr inbounds i32, i32* %out, i64 %idxprom10

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

define void @add_non_zero_with_offset(i32* %p, i32 %addend, i32* %q) {
   %gep1 = getelementptr i32, i32* %p.off, i32 %addend
   %gep2 = getelementptr i32, i32* %p, i32 %add
   %gep1.16 = bitcast i32* %gep1 to i16*
   %gep2.16 = bitcast i32* %gep2 to i16*
   ret void
 }
 
 ; CHECK-LABEL: non_zero_index_simple
-; CHECK: MayAlias: i32* %gep, i32* %p
-; CHECK: MayAlias: i16* %gep.16, i32* %p
+; CHECK: NoAlias: i32* %gep, i32* %p
+; CHECK: NoAlias: i16* %gep.16, i32* %p
 ; CHECK: MayAlias: i32* %p, i64* %gep.64
-; TODO: First two could be NoAlias.
 define void @non_zero_index_simple(i32* %p, i32* %q) {
   %knownnonzero = load i32, i32* %q, !range !0
   %gep = getelementptr i32, i32* %p, i32 %knownnonzero
   %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: MayAlias: i16* %gep.16, i32* %p
-; TODO: Last could be NoAlias.
+; 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
   %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.16 = bitcast i32* %gep to i16*
   ret void
 }
 
 !0 = !{ i32 1, i32 5 }