Index: lib/Analysis/BasicAliasAnalysis.cpp =================================================================== --- lib/Analysis/BasicAliasAnalysis.cpp +++ lib/Analysis/BasicAliasAnalysis.cpp @@ -170,6 +170,10 @@ struct VariableGEPIndex { const Value *V; + + // We need to track what extensions we've done as we consider the same Value + // with different extensions as different variables in a GEP's linear expression; + // e.g.: if V == -1, then sext(x) != zext(x) ExtensionKind Extension; int64_t Scale; @@ -215,34 +219,41 @@ return V; } - if (BinaryOperator *BOp = dyn_cast(V)) { - if (ConstantInt *RHSC = dyn_cast(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, - AT, BOp, DT)) - break; - // FALL THROUGH. - case Instruction::Add: - V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, - DL, Depth+1, AT, DT); - Offset += RHSC->getValue(); - return V; - case Instruction::Mul: - V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, - DL, Depth+1, AT, DT); - Offset *= RHSC->getValue(); - Scale *= RHSC->getValue(); - return V; - case Instruction::Shl: - V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, - DL, Depth+1, AT, DT); - Offset <<= RHSC->getValue().getLimitedValue(); - Scale <<= RHSC->getValue().getLimitedValue(); - return V; + if (Extension == EK_NotExtended) { + if(BinaryOperator *BOp = dyn_cast(V)) { + if (ConstantInt *RHSC = dyn_cast(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, + AT, BOp, DT)) + break; + // FALL THROUGH. + case Instruction::Add: + V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, + DL, Depth+1, AT, DT); + Offset += RHSC->getValue(); + return V; + case Instruction::Sub: + V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, + DL, Depth+1, AT, DT); + Offset -= RHSC->getValue(); + return V; + case Instruction::Mul: + V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, + DL, Depth+1, AT, DT); + Offset *= RHSC->getValue(); + Scale *= RHSC->getValue(); + return V; + case Instruction::Shl: + V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, + DL, Depth+1, AT, DT); + Offset <<= RHSC->getValue().getLimitedValue(); + Scale <<= RHSC->getValue().getLimitedValue(); + return V; + } } } } @@ -263,9 +274,12 @@ DL, Depth+1, AT, DT); Scale = Scale.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); + // We have to be careful if Extension == EK_ZeroExt as we can't + // decompose a sign extension, e.g. zext(x - 1) != zext(x) - zext(-1). + // This isn't true in all cases though, as zext(-1) != sext(-1). + Offset = isa(V) + ? Offset.sext(OldWidth) + : Offset.zext(OldWidth); return Result; } Index: test/Analysis/BasicAA/q.bad.ll =================================================================== --- /dev/null +++ test/Analysis/BasicAA/q.bad.ll @@ -0,0 +1,45 @@ +; RUN: opt < %s -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64" +target triple = "thumbv7--linux-gnueabi" + +%struct.spec_fd_t = type { i32, i32, i32, i32, i32 } +@spec_fd = common global [280 x %struct.spec_fd_t] zeroinitializer, align 4 + +; CHECK-LABEL: test_path_dependence +; CHECK: PartialAlias: i8* %a, i8* %b +; CHECK: PartialAlias: i8* %a, i8* %c +; CHECK: PartialAlias: i8* %a, i8* %d +define void @test_path_dependence(i32 %p, i8* %mem) { + %p.minus1 = add i32 %p, -1 ; this will always wrap, unless %p == 0 + %p.minus1.64 = zext i32 %p.minus1 to i64 + %p.64.again = add i64 %p.minus1.64, 1 ; either %p (if we wrapped) or 4294967296 (if we didn't) + + %p.nsw.nuw.minus1 = sub nsw nuw i32 %p, 1 ; as nuw we know %p >= 1 + %p.nsw.nuw.minus1.64 = zext i32 %p.nsw.nuw.minus1 to i64 + %p.nsw.nuw.64.again = add nsw nuw i64 %p.nsw.nuw.minus1.64, 1 ; ...so always exactly %p + + %p.nsw.minus1 = sub nsw i32 %p, 1 ; only nsw, so can only guarantee %p != 0x10000000 + %p.nsw.minus1.64 = zext i32 %p.nsw.minus1 to i64 ; when %p <= 0 then the zext will make this a huge positive number + %p.nsw.64.again = add nsw i64 %p.nsw.minus1.64, 1 ; ...and so when %p <= 0 this is very much != %p + + %p.64 = zext i32 %p to i64 + %a = getelementptr inbounds i8* %mem, i64 %p.64 + %b = getelementptr inbounds i8* %mem, i64 %p.64.again + %c = getelementptr inbounds i8* %mem, i64 %p.nsw.nuw.64.again + %d = getelementptr inbounds i8* %mem, i64 %p.nsw.64.again + ret void +} + +; CHECK-LABEL: uncompressStream +; CHECK: MustAlias: i32* %offset.a, i32* %offset.b +; CHECK: PartialAlias: [280 x %struct.spec_fd_t]* @spec_fd, i32* %offset.b +; CHECK: NoAlias: [280 x %struct.spec_fd_t]* @spec_fd, i32* %offset.c +; CHECK: NoAlias: i32* %offset.b, i32* %offset.c +define void @uncompressStream() { + %offset.a = getelementptr inbounds [280 x %struct.spec_fd_t]* @spec_fd, i32 0, i32 255, i32 2 + %literal.255 = zext i8 255 to i32 + %offset.b = getelementptr inbounds [280 x %struct.spec_fd_t]* @spec_fd, i32 0, i32 %literal.255, i32 2 + %literal.minus1 = sext i8 255 to i32 + %offset.c = getelementptr inbounds [280 x %struct.spec_fd_t]* @spec_fd, i32 0, i32 %literal.minus1, i32 2 + ret void +}