[BasicAA] Make better use of zext and sign 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 locations that fit in the gap between the two base pointers are NoAlias.

The original patch forgot to check if the Scale in VariableGEPIndex flipped the sign of the variable. The BasicAA pass iterates over the instructions in the order they appear in the function, and so BasicAliasAnalysis::aliasGEP is called with the variable it first comes across as parameter GEP1. Adding a %reorder label puts the definition of %a after %b so aliasGEP is called with %b as the first parameter and %a as the second. aliasGEP later calculates that %a == %b + 1 - %idxprom where %idxprom >= 0 (if %a was passed as the first parameter it would calculate %b == %a - 1 + %idxprom where %idxprom >= 0) - ignoring that %idxprom is scaled by -1 here lead the patch to incorrectly conclude that %a > %b.

This patch now ensures that isValueEqualInPotentialCycles is called for the existing modulo-distance check as it too is only valid if the variable doesn't change across cycles. The fix described in (1) makes this codepath execute more frequently, as variables that were within a small negative distance of each other were being interpreted as being a very large positive distance away from each other. The code now correctly identifies more variables as being outside a scale-modulo-distance of each other, and so declares more variables as NoAlias.

Thanks to Lang to isolating the first bug, Rich Barton for isolating the second bug and Hal for improving the patch.

[njw45]

zext

[hfinkel]

lib/Analysis/BasicAliasAnalysis.cpp

1074

If I change this PartialAlias return to MayAlias, all of the regression tests still pass. Is there a test covering this?

[njw45]

zext

[njw45]

You're right - that call doesn't actually affect anything so I've removed it. It seems the actual cause of Rich's bug was using AllPositive to break out of the loop; if the loop break condition i != e is changed to i != e && AllPositive then the test_modulo_analysis_with_global test I've added will fail as the Modulo will be calculated incorrectly (as the last loop iteration is skipped, so Modulo isn't updated with its Scale). I've also added a few more tests and comments for the modulo functionality too, as I spent a bit of time exploring how it works. Thanks -

[hfinkel]

You're right - that call doesn't actually affect anything so I've removed it. It seems the actual cause of Rich's bug was using AllPositive to break out of the loop; if the loop break condition i != e is changed to i != e && AllPositive then the test_modulo_analysis_with_global test I've added will fail as the Modulo will be calculated incorrectly (as the last loop iteration is skipped, so Modulo isn't updated with its Scale). I've also added a few more tests and comments for the modulo functionality too, as I spent a bit of time exploring how it works. Thanks -

Okay, thanks! I'll retest with this version.

[njw45]

Hi @hfinkel - is this change OK? ComputeSignBit is safe to use in loops as it takes into account phi nodes, and the == EK_ZeroEx check is safe in loops as, no matter how the variable changes between iterations, zero-extensions will always guarantee a zero sign bit. The isValueEqualInPotentialCycles check is therefore definitely not needed as all the variable analysis holds no matter how the variables change between loop iterations. Thanks -

Nick

[hfinkel]

I still need to run tests with the patch. I hope to get to this later this week.

-Hal

• Original Message -----

From: "Nick White" <[e-mail]>
To: "n j white" <[e-mail]>, [e-mail]
Cc: [e-mail]
Sent: Wednesday, October 29, 2014 12:42:08 PM
Subject: Re: [PATCH] [BasicAA] Make better use of zext and sign information.

Hi @hfinkel - is this change OK? ComputeSignBit is safe to use in
loops as it takes into account phi nodes, and the == EK_ZeroEx
check is safe in loops as, no matter how the variable changes
between iterations, zero-extensions will always guarantee a zero
sign bit. The isValueEqualInPotentialCycles check is therefore
definitely not needed as all the variable analysis holds no matter
how the variables change between loop iterations. Thanks -

Nick

http://reviews.llvm.org/D5866

[njw45]

zext

[njw45]

Hi @hfinkel - have you had a chance to run your tests on this patch yet? I've added another enhancement to GetLinearExpression - basically to convert ConstantInts to Offsets (see test_const_eval and test_const_eval_scaled for the situations this improves). I've you have I'll submit this change as a separate review, otherwise could you run your tests on this latest version of the patch? Thanks -

Nick

[hfinkel]

• Original Message -----

From: "Nick White" <[e-mail]>
To: "n j white" <[e-mail]>, [e-mail]
Cc: [e-mail]
Sent: Monday, November 10, 2014 11:02:49 AM
Subject: Re: [PATCH] [BasicAA] Make better use of zext and sign information.

Hi @hfinkel - have you had a chance to run your tests on this patch
yet? I've added another enhancement to GetLinearExpression -
basically to convert ConstantInts to Offsets (see
test_const_eval and test_const_eval_scaled for the
situations this improves). I've you have I'll submit this change as
a separate review, otherwise could you run your tests on this latest
version of the patch? Thanks -

I'll do that.

-Hal

Nick

http://reviews.llvm.org/D5866

[hfinkel]

r221876.

lib/Analysis/BasicAliasAnalysis.cpp

static Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset,
 
   // Limit our recursion depth.
   if (Depth == 6) {
     Scale = 1;
     Offset = 0;
     return V;
   }
 
+  if (ConstantInt *Const = dyn_cast<ConstantInt>(V)) {
+    // if it's a constant, just convert it to an offset
+    // and remove the variable.
+    Offset += Const->getValue();
+    assert(Scale == 0 && "Constant values don't have a scale");
+    return V;
+  }
+
   if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(V)) {
     if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) {
       switch (BOp->getOpcode()) {
       default: break;
       case Instruction::Or:
         // X|C == X+C if all the bits in C are unset in X.  Otherwise we can't
         // analyze it.
         if (!MaskedValueIsZero(BOp->getOperand(0), RHSC->getValue(), &DL, 0,
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) {
       if (V1Size != UnknownSize && V2Size != UnknownSize) {
         if (-(uint64_t)GEP1BaseOffset < V1Size)
           return PartialAlias;
         return NoAlias;
       }
     }
   }
 
-  // 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)
-      Modulo |= (uint64_t)GEP1VariableIndices[i].Scale;
+    bool AllPositive = true;
+    for (unsigned i = 0, e = GEP1VariableIndices.size(); i != e; ++i) {
+
+      // Try to distinguish something like &A[i][1] against &A[42][0].
+      // Grab the least significant bit set in any of the scales. We
+      // don't need std::abs here (even if the scale's negative) as we'll
+      // be ^'ing Modulo with itself later.
+      Modulo |= (uint64_t) GEP1VariableIndices[i].Scale;
+
+      if (AllPositive) {
+        // If the Value could change between cycles, then any reasoning about
+        // the Value this cycle may not hold in the next cycle. We'll just
+        // give up if we can't determine conditions that hold for every cycle:
+        const Value *V = GEP1VariableIndices[i].V;
+
+        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 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);
+      }
+    }
+
     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(i8* %mem) {
+  br label %for.loop
+
+for.loop:
+  %i = phi i32 [ 0, %0 ], [ %i.plus1, %for.loop ]
+  %a = getelementptr inbounds i8* %mem, i64 8
+  %a.plus1 = getelementptr inbounds i8* %mem, i64 16
+  %i.64 = zext i32 %i to i64
+  %b = getelementptr inbounds i8* %a.plus1, i64 %i.64
+  %i.plus1 = add nuw nsw i32 %i, 1
+  %cmp = icmp eq i32 %i.plus1, 10
+  br i1 %cmp, label %for.loop.exit, label %for.loop
+
+for.loop.exit:
+  ret void
+}
+
+; CHECK-LABEL: test_with_varying_base_pointer_in_loop
+; CHECK:  NoAlias: i8* %a, i8* %b
+
+define void @test_with_varying_base_pointer_in_loop(i8* %mem.orig) {
+  br label %for.loop
+
+for.loop:
+  %mem = phi i8* [ %mem.orig, %0 ], [ %mem.plus1, %for.loop ]
+  %i = phi i32 [ 0, %0 ], [ %i.plus1, %for.loop ]
+  %a = getelementptr inbounds i8* %mem, i64 8
+  %a.plus1 = getelementptr inbounds i8* %mem, i64 16
+  %i.64 = zext i32 %i to i64
+  %b = getelementptr inbounds i8* %a.plus1, i64 %i.64
+  %i.plus1 = add nuw nsw i32 %i, 1
+  %mem.plus1 = getelementptr inbounds i8* %mem, i64 8
+  %cmp = icmp eq i32 %i.plus1, 10
+  br i1 %cmp, 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
+}
+
+@b = global i32 0, align 4
+@d = global i32 0, align 4
+
+; CHECK-LABEL: test_spec2006
+; CHECK:  PartialAlias: i32** %x, i32** %y
+
+define void @test_spec2006() {
+  %h = alloca [1 x [2 x i32*]], align 16
+  %d.val = load i32* @d, align 4
+  %d.promoted = sext i32 %d.val to i64
+  %1 = icmp slt i32 %d.val, 2
+  br i1 %1, label %.lr.ph, label %3
+
+.lr.ph:                                           ; preds = %0
+  br label %2
+
+; <label>:2                                       ; preds = %.lr.ph, %2
+  %i = phi i32 [ %d.val, %.lr.ph ], [ %i.plus1, %2 ]
+  %i.promoted = sext i32 %i to i64
+  %x = getelementptr inbounds [1 x [2 x i32*]]* %h, i64 0, i64 %d.promoted, i64 %i.promoted
+  %i.plus1 = add nsw i32 %i, 1
+  %cmp = icmp slt i32 %i.plus1, 2
+  br i1 %cmp, label %2, label %3
+
+; <label>:3                                      ; preds = %._crit_edge, %0
+  %y = getelementptr inbounds [1 x [2 x i32*]]* %h, i64 0, i64 0, i64 1
+  ret void
+}
+
+; CHECK-LABEL: test_modulo_analysis_easy_case
+; CHECK:  NoAlias: i32** %x, i32** %y
+
+define void @test_modulo_analysis_easy_case(i64 %i) {
+  %h = alloca [1 x [2 x i32*]], align 16
+  %x = getelementptr inbounds [1 x [2 x i32*]]* %h, i64 0, i64 %i, i64 0
+  %y = getelementptr inbounds [1 x [2 x i32*]]* %h, i64 0, i64 0, i64 1
+  ret void
+}
+
+; CHECK-LABEL: test_modulo_analysis_in_loop
+; CHECK:  NoAlias: i32** %x, i32** %y
+
+define void @test_modulo_analysis_in_loop() {
+  %h = alloca [1 x [2 x i32*]], align 16
+  br label %for.loop
+
+for.loop:
+  %i = phi i32 [ 0, %0 ], [ %i.plus1, %for.loop ]
+  %i.promoted = sext i32 %i to i64
+  %x = getelementptr inbounds [1 x [2 x i32*]]* %h, i64 0, i64 %i.promoted, i64 0
+  %y = getelementptr inbounds [1 x [2 x i32*]]* %h, i64 0, i64 0, i64 1
+  %i.plus1 = add nsw i32 %i, 1
+  %cmp = icmp slt i32 %i.plus1, 2
+  br i1 %cmp, label %for.loop, label %for.loop.exit
+
+for.loop.exit:
+  ret void
+}
+
+; CHECK-LABEL: test_modulo_analysis_with_global
+; CHECK:  PartialAlias: i32** %x, i32** %y
+
+define void @test_modulo_analysis_with_global() {
+  %h = alloca [1 x [2 x i32*]], align 16
+  %b = load i32* @b, align 4
+  %b.promoted = sext i32 %b to i64
+  br label %for.loop
+
+for.loop:
+  %i = phi i32 [ 0, %0 ], [ %i.plus1, %for.loop ]
+  %i.promoted = sext i32 %i to i64
+  %x = getelementptr inbounds [1 x [2 x i32*]]* %h, i64 0, i64 %i.promoted, i64 %b.promoted
+  %y = getelementptr inbounds [1 x [2 x i32*]]* %h, i64 0, i64 0, i64 1
+  %i.plus1 = add nsw i32 %i, 1
+  %cmp = icmp slt i32 %i.plus1, 2
+  br i1 %cmp, label %for.loop, label %for.loop.exit
+
+for.loop.exit:
+  ret void
+}
+
+; CHECK-LABEL: test_const_eval
+; CHECK: NoAlias: i8* %a, i8* %b
+define void @test_const_eval(i8* %ptr, i64 %offset) {
+  %a = getelementptr inbounds i8* %ptr, i64 %offset
+  %a.dup = getelementptr inbounds i8* %ptr, i64 %offset
+  %three = zext i32 3 to i64
+  %b = getelementptr inbounds i8* %a.dup, i64 %three
+  ret void
+}
+
+; CHECK-LABEL: test_const_eval_scaled
+; CHECK: MustAlias: i8* %a, i8* %b
+define void @test_const_eval_scaled(i8* %ptr) {
+  %three = zext i32 3 to i64
+  %six = mul i64 %three, 2
+  %a = getelementptr inbounds i8* %ptr, i64 %six
+  %b = getelementptr inbounds i8* %ptr, i64 6
+  ret void
+}
+
+; Function Attrs: nounwind
+declare noalias i8* @malloc(i64)