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]

lib/Analysis/BasicAliasAnalysis.cpp

258

Start sentence with a capital w (similar with other comments below).

1067

To note a possible follow-up, we might also be able to determine this by using ComputeSignBit from ValueTracking.h

1084

Add a space in between the if and the (

1231

I think you can remove the ("don't know") next to MayAlias.

More importantly, please also explain in the comment what the loop below actually checks and why that ensures the condition you explain above.

Also, an example of this would be helpful.

1239

Space after the if.

[njw45]

Updating D5514: Improve BasicAA Pass Using zext Information

[njw45]

@hfinkel Thanks for the review - I've updated the patch to fix this issues you mentioned.

[hfinkel]

lib/Analysis/BasicAliasAnalysis.cpp

1242

As you've written the example, %phi and %idx don't alias, because %idx == %phi+1. If you take out the add and store the original value (or don't update*%somewhere at all), then they will alias.

1247

When you see "we can see that", you mean that without this check we'd return NoAlias, right? That does not seem right. Without this patch (current trunk), if I take this function:

define void @test1(i64* noalias %somewhere, i32* noalias %memory) {
entry:
  br label %for.body

for.body:
   %phi = phi i32* [%idx, %for.body], [null, %entry]
   %i = load i64* %somewhere
   %idx = getelementptr inbounds i32* %memory, i64 %i
   %i.plus1 = add nsw nuw i64 %i, 1
   store i64 %i.plus1, i64* %somewhere
   br label %for.body
}

and run it through:

opt < -basicaa -aa-eval -print-all-alias-modref-info -disable-output

I get:

Function: test1: 4 pointers, 0 call sites
  NoAlias:      i32* %memory, i64* %somewhere
  NoAlias:      i32* %phi, i64* %somewhere
  MayAlias:     i32* %memory, i32* %phi
  NoAlias:      i32* %idx, i64* %somewhere
  PartialAlias: i32* %idx, i32* %memory
  MayAlias:     i32* %idx, i32* %phi

which already gives "MayAlias: i32* %idx, i32* %phi".

In short, I'm still not entirely sure I understand the problem you're trying to fix here.

1256

What do you mean by "tightened" here?

1259

Space after the if.

[njw45]

zext

[njw45]

@hfinkel - thanks for your patience, I understand it now. I was basically trying to re-invent isValueEqualInPotentialCycles, so I've cut that bit completely from the patch. I've also added the ComputeSignBit check you suggested, and a test using lshr to demonstrate that it works.

[hfinkel]

LGTM, thanks! Do you have commit access?

[njw45]

No, I don't -

[hfinkel]

r218714.

[njw45]

Thanks!

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) {
       Modulo |= (uint64_t)GEP1VariableIndices[i].Scale;
+
+      // If the variable's been zero-extended, then we know it's positive,
+      // regardless of whether the value is signed or unsigned.
+      //
+      // TODO: We could also use ComputeSignBit here.
+      AllPositive &= GEP1VariableIndices[i].Extension == EK_ZeroExt;
+    }
     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
for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) {
 
     AliasResult ThisAlias = aliasCheck(V2, V2Size, V2AAInfo,
                                        V, PNSize, PNAAInfo);
     Alias = MergeAliasResults(ThisAlias, Alias);
     if (Alias == MayAlias)
       break;
   }
 
+  DominatorTreeWrapperPass *DTWP =
+  getAnalysisIfAvailable<DominatorTreeWrapperPass>();
+  DominatorTree *DT = DTWP ? &DTWP->getDomTree() : nullptr;
+  LoopInfo *LI = getAnalysisIfAvailable<LoopInfo>();
+
+  // The Alias we just calculated only holds if all the Values come from
+  // the same cycle as the Phi-node. If not, subsequent memory stores could
+  // mean these Values no longer alias, or now alias when we reach PN, so
+  // we'll just return MayAlias. Consider:
+  //
+  // for.body:
+  //   %phi = phi i32* [%idx, %for.body], ...
+  //   %i = load i64* %somewhere
+  //   %idx = getelementptr inbounds i32* %memory, i64 %i
+  //   %i.plus1 = add nsw nuw i64 %i, 1
+  //   store i64 %i.plus1, i64* %somewhere
+  //   br label %for.body
+  //
+  // In the loop body, %idx trivially MustAlias to %idx, however we can see
+  // that %phi is NoAlias to %idx. This is because %phi is %idx from a previous
+  // iteration of the loop, and after we calculated %idx we used a 'store' to
+  // changed the memory location where %i lives (%memory).
+  for (unsigned i = 0, e = V1Srcs.size(); i != e; ++i) {
+    const Instruction *Inst = dyn_cast<Instruction>(V1Srcs[i]);
+
+    // We'll be rather conservative here; if there's any loop in the CFG that
+    // includes PN and Inst then we'll give up.
+    //
+    // TODO: this could be tightened to any loop where Inst, or any of the
+    // (transitive) Instructions that generated Inst returns true for
+    // Instruction::mayReadFromMemory
+    if(Inst 
+    && isPotentiallyReachable(PN, Inst, DT, LI)
+    && isPotentiallyReachable(Inst, PN, DT, LI))
+      return MayAlias;
+  }
+
   return Alias;
 }
 
 // aliasCheck - Provide a bunch of ad-hoc rules to disambiguate in common cases,
 // such as array references.
 //
 AliasAnalysis::AliasResult
 BasicAliasAnalysis::aliasCheck(const Value *V1, uint64_t V1Size,

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: MayAlias: i32* %arrayidx5, i32* %phi
+; 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 ]
+  %phi = phi i32* [ %arrayidx13, %for.body ], [ %j, %entry ]
   %targetBlock = call i1 @cond(i32* %jj7)
   br i1 %targetBlock, label %for.body, label %bye
 
 for.body:
-  %1 = load i32* %jj7, align 4
-  %idxprom4 = zext i32 %1 to i64
+  %0 = load i32* %jj7, align 4
+  %idxprom4 = zext i32 %0 to i64
   %arrayidx5 = getelementptr inbounds [100 x i32]* %oa5, i64 0, i64 %idxprom4
-  %2 = load i32* %arrayidx5, align 4
-  %sub6 = sub i32 %2, 6
+  %1 = load i32* %arrayidx5, align 4
+  %sub6 = sub i32 %1, 6
   store i32 %sub6, i32* %arrayidx5, align 4
-  ; %0 and %arrayidx5 can alias! It is not safe to DSE the above store.
-  %3 = load i32* %0, align 4
-  store i32 %3, i32* %arrayidx5, align 4
-  %sub11 = add i32 %1, -1
+  ; %phi and %arrayidx5 can alias! It is not safe to DSE the above store.
+  %2 = load i32* %phi, align 4
+  store i32 %2, i32* %arrayidx5, align 4
+  %sub11 = add i32 %0, -1
   %idxprom12 = zext i32 %sub11 to i64
   %arrayidx13 = getelementptr inbounds [100 x i32]* %oa5, i64 0, i64 %idxprom12
   call void @inc(i32* %jj7)
   br label %codeRepl
 
 bye:
   %.reload = load i32* %jj7, align 4
   ret i32 %.reload
 }
 
 declare i1 @cond(i32*)
 
 declare void @inc(i32*)
 
 

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
+; CHECK:  NoAlias: i8* %a, i8* %b
+
+define void @test() {
+  %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_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
+}
+
+; Function Attrs: nounwind
+declare noalias i8* @malloc(i64)