Index: lib/Analysis/BasicAliasAnalysis.cpp =================================================================== --- lib/Analysis/BasicAliasAnalysis.cpp +++ lib/Analysis/BasicAliasAnalysis.cpp @@ -254,7 +254,10 @@ 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; } @@ -1051,12 +1054,45 @@ } } - // 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(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 @@ -1066,6 +1102,12 @@ 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 Index: test/Analysis/BasicAA/phi-aa.ll =================================================================== --- test/Analysis/BasicAA/phi-aa.ll +++ test/Analysis/BasicAA/phi-aa.ll @@ -39,6 +39,7 @@ ; CHECK-LABEL: pr18068 ; CHECK: MayAlias: i32* %0, i32* %arrayidx5 +; CHECK: NoAlias: i32* %arrayidx13, i32* %arrayidx5 define i32 @pr18068(i32* %jj7, i32* %j) { entry: Index: test/Analysis/BasicAA/zext.ll =================================================================== --- /dev/null +++ test/Analysis/BasicAA/zext.ll @@ -0,0 +1,189 @@ +; 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 + +;