Improve BasicAA Pass Using zext Information

[njw45]

Summary

1. Fixes a bug when calculating the offset in GetLinearExpression. The code previously used zext to extend the offset, so negative offsets were converted to large positive ones.
2. Enhance aliasGEP to deduce that, if the difference between two GEP allocations is positive and all the variables that govern the offset are also positive (i.e. the offset is strictly after the higher base pointer), then allocations that fit in the gap between the two base pointers are NoAlias.

[hfinkel]

Alright, let's try this again.

[hfinkel]

I added an early exit from the loop to avoid unnecessary, but expensive, functions call. r219135.

lib/Analysis/BasicAliasAnalysis.cpp

if ((isa<SExtInst>(V) && Extension != EK_ZeroExt) ||
     unsigned SmallWidth = CastOp->getType()->getPrimitiveSizeInBits();
     Scale = Scale.trunc(SmallWidth);
     Offset = Offset.trunc(SmallWidth);
     Extension = isa<SExtInst>(V) ? EK_SignExt : EK_ZeroExt;
 
     Value *Result = GetLinearExpression(CastOp, Scale, Offset, Extension,
                                         DL, Depth+1, AT, DT);
     Scale = Scale.zext(OldWidth);
-    Offset = Offset.zext(OldWidth);
+
+    // We have to sign-extend even if Extension == EK_ZeroExt as we can't
+    // decompose a sign extension (i.e. zext(x - 1) != zext(x) - zext(-1)).
+    Offset = Offset.sext(OldWidth);
 
     return Result;
   }
 
   Scale = 1;
   Offset = 0;
   return V;
 }
if (GEP1BaseOffset >= 0) {
       }
     }
   }
 
   // Try to distinguish something like &A[i][1] against &A[42][0].
   // Grab the least significant bit set in any of the scales.
   if (!GEP1VariableIndices.empty()) {
     uint64_t Modulo = 0;
-    for (unsigned i = 0, e = GEP1VariableIndices.size(); i != e; ++i)
+    bool AllPositive = true;
+    for (unsigned i = 0, e = GEP1VariableIndices.size(); i != e; ++i) {
+      const Value *V = GEP1VariableIndices[i].V;
       Modulo |= (uint64_t)GEP1VariableIndices[i].Scale;
+
+      bool SignKnownZero, SignKnownOne;
+      ComputeSignBit(
+        const_cast<Value *>(V),
+        SignKnownZero, SignKnownOne,
+        DL, 0, AT, nullptr, DT);
+
+      // Zero-extension widens the variable, and so forces the sign
+      // bit to zero.
+      bool IsZExt = GEP1VariableIndices[i].Extension == EK_ZeroExt;
+      SignKnownZero |= IsZExt;
+      SignKnownOne &= !IsZExt;
+
+      // If the variable's been begins with a zero then we know it's
+      // positive, regardless of whether the value is signed or
+      // unsigned.
+      int64_t Scale = GEP1VariableIndices[i].Scale;
+      AllPositive &= 
+        (SignKnownZero && Scale >= 0) ||
+        (SignKnownOne && Scale < 0);
+
+      // If the Value is currently positive but could change in a cycle,
+      // then we can't guarantee it'll always br positive.
+      AllPositive &= isValueEqualInPotentialCycles(V, V);
+    }
     Modulo = Modulo ^ (Modulo & (Modulo - 1));
 
     // We can compute the difference between the two addresses
     // mod Modulo. Check whether that difference guarantees that the
     // two locations do not alias.
     uint64_t ModOffset = (uint64_t)GEP1BaseOffset & (Modulo - 1);
     if (V1Size != UnknownSize && V2Size != UnknownSize &&
         ModOffset >= V2Size && V1Size <= Modulo - ModOffset)
       return NoAlias;
+
+    // If we know all the variables are positive, then GEP1 >= GEP1BasePtr.
+    // If GEP1BasePtr > V2 (GEP1BaseOffset > 0) then we know the pointers
+    // don't alias if V2Size can fit in the gap between V2 and GEP1BasePtr.
+    if (AllPositive && GEP1BaseOffset > 0 && V2Size <= (uint64_t) GEP1BaseOffset)
+      return 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
   // little tricks above worked.
   //
   // TODO: Returning PartialAlias instead of MayAlias is a mild hack; the
   // practical effect of this is protecting TBAA in the case of dynamic

test/Analysis/BasicAA/phi-aa.ll

return:
   ret void
 }
 
 ; Pointers can vary in between iterations of loops.
 ; PR18068
 
 ; CHECK-LABEL: pr18068
 ; CHECK: MayAlias: i32* %0, i32* %arrayidx5
+; CHECK: NoAlias: i32* %arrayidx13, i32* %arrayidx5
 
 define i32 @pr18068(i32* %jj7, i32* %j) {
 entry:
   %oa5 = alloca [100 x i32], align 16
   br label %codeRepl
 
 codeRepl:
   %0 = phi i32* [ %arrayidx13, %for.body ], [ %j, %entry ]

test/Analysis/BasicAA/zext.ll

+; RUN: opt < %s -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; CHECK-LABEL: test_with_zext
+; CHECK:  NoAlias: i8* %a, i8* %b
+
+define void @test_with_zext() {
+  %1 = tail call i8* @malloc(i64 120)
+  %a = getelementptr inbounds i8* %1, i64 8
+  %2 = getelementptr inbounds i8* %1, i64 16
+  %3 = zext i32 3 to i64
+  %b = getelementptr inbounds i8* %2, i64 %3
+  ret void
+}
+
+; CHECK-LABEL: test_with_lshr
+; CHECK:  NoAlias: i8* %a, i8* %b
+
+define void @test_with_lshr(i64 %i) {
+  %1 = tail call i8* @malloc(i64 120)
+  %a = getelementptr inbounds i8* %1, i64 8
+  %2 = getelementptr inbounds i8* %1, i64 16
+  %3 = lshr i64 %i, 2
+  %b = getelementptr inbounds i8* %2, i64 %3
+  ret void
+}
+
+; CHECK-LABEL: test_with_a_loop
+; CHECK:  NoAlias: i8* %a, i8* %b
+
+define void @test_with_a_loop() {
+  %1 = tail call i8* @malloc(i64 120)
+  %a = getelementptr inbounds i8* %1, i64 8
+  %2 = getelementptr inbounds i8* %1, i64 16
+  br label %for.loop
+
+for.loop:
+  %i = phi i32 [ 0, %0 ], [ %i.next, %for.loop ]
+  %3 = zext i32 %i to i64
+  %b = getelementptr inbounds i8* %2, i64 %3
+  %i.next = add nuw nsw i32 %i, 1
+  %4 = icmp eq i32 %i.next, 10
+  br i1 %4, label %for.loop.exit, label %for.loop
+
+for.loop.exit:
+  ret void
+}
+
+; CHECK-LABEL: test_sign_extension
+; CHECK:  PartialAlias: i64* %b.i64, i8* %a
+
+define void @test_sign_extension(i32 %p) {
+  %1 = tail call i8* @malloc(i64 120)
+  %p.64 = zext i32 %p to i64
+  %a = getelementptr inbounds i8* %1, i64 %p.64
+  %p.minus1 = add i32 %p, -1
+  %p.minus1.64 = zext i32 %p.minus1 to i64
+  %b.i8 = getelementptr inbounds i8* %1, i64 %p.minus1.64
+  %b.i64 = bitcast i8* %b.i8 to i64*
+  ret void
+}
+
+; CHECK-LABEL: test_fe_tools
+; CHECK:  PartialAlias: i32* %a, i32* %b
+
+define void @test_fe_tools([8 x i32]* %values) {
+  br label %reorder
+
+for.loop:
+  %i = phi i32 [ 0, %reorder ], [ %i.next, %for.loop ]
+  %idxprom = zext i32 %i to i64
+  %b = getelementptr inbounds [8 x i32]* %values, i64 0, i64 %idxprom
+  %i.next = add nuw nsw i32 %i, 1
+  %1 = icmp eq i32 %i.next, 10
+  br i1 %1, label %for.loop.exit, label %for.loop
+
+reorder:
+  %a = getelementptr inbounds [8 x i32]* %values, i64 0, i64 1
+  br label %for.loop
+
+for.loop.exit:
+  ret void
+}
+
+; Function Attrs: nounwind
+declare noalias i8* @malloc(i64)