Index: lib/Analysis/BasicAliasAnalysis.cpp =================================================================== --- lib/Analysis/BasicAliasAnalysis.cpp +++ lib/Analysis/BasicAliasAnalysis.cpp @@ -170,11 +170,15 @@ struct VariableGEPIndex { const Value *V; - ExtensionKind Extension; + + // 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) + SmallVector, 6> Extensions; int64_t Scale; bool operator==(const VariableGEPIndex &Other) const { - return V == Other.V && Extension == Other.Extension && + return V == Other.V && Extensions == Other.Extensions && Scale == Other.Scale; } @@ -194,10 +198,12 @@ /// Note that this looks through extends, so the high bits may not be /// represented in the result. static Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset, - ExtensionKind &Extension, + SmallVectorImpl> &Extensions, const DataLayout &DL, unsigned Depth, AssumptionTracker *AT, - DominatorTree *DT) { + DominatorTree *DT, + bool &nsw, + bool &nuw) { assert(V->getType()->isIntegerTy() && "Not an integer value"); // Limit our recursion depth. @@ -210,15 +216,20 @@ if (ConstantInt *Const = dyn_cast(V)) { // if it's a constant, just convert it to an offset // and remove the variable. - Offset += Const->getValue(); + Offset += Const->getValue().zextOrSelf(Offset.getBitWidth()); assert(Scale == 0 && "Constant values don't have a scale"); return V; } - if (BinaryOperator *BOp = dyn_cast(V)) { + if(BinaryOperator *BOp = dyn_cast(V)) { if (ConstantInt *RHSC = dyn_cast(BOp->getOperand(1))) { switch (BOp->getOpcode()) { - default: break; + default: + // We don't understand this instruction, so we can't decompose it any + // further. + Scale = 1; + Offset = 0; + return V; case Instruction::Or: // X|C == X+C if all the bits in C are unset in X. Otherwise we can't // analyze it. @@ -227,45 +238,83 @@ break; // FALL THROUGH. case Instruction::Add: - V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, - DL, Depth+1, AT, DT); - Offset += RHSC->getValue(); - return V; + V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extensions, + DL, Depth+1, AT, DT, nsw, nuw); + Offset += RHSC->getValue().zextOrSelf(Offset.getBitWidth()); + break; + case Instruction::Sub: + V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extensions, + DL, Depth+1, AT, DT, nsw, nuw); + Offset -= RHSC->getValue().zextOrSelf(Offset.getBitWidth()); + break; case Instruction::Mul: - V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, - DL, Depth+1, AT, DT); - Offset *= RHSC->getValue(); - Scale *= RHSC->getValue(); - return V; + V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extensions, + DL, Depth+1, AT, DT, nsw, nuw); + Offset *= RHSC->getValue().zextOrSelf(Offset.getBitWidth()); + Scale *= RHSC->getValue().zextOrSelf(Offset.getBitWidth()); + break; case Instruction::Shl: - V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, - DL, Depth+1, AT, DT); + V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extensions, + DL, Depth+1, AT, DT, nsw, nuw); Offset <<= RHSC->getValue().getLimitedValue(); Scale <<= RHSC->getValue().getLimitedValue(); - return V; + break; + } + + if(isa(BOp)) { + nuw &= BOp->hasNoUnsignedWrap(); + nsw &= BOp->hasNoSignedWrap(); } + return V; } } // Since GEP indices are sign extended anyway, we don't care about the high // bits of a sign or zero extended value - just scales and offsets. The // extensions have to be consistent though. - if ((isa(V) && Extension != EK_ZeroExt) || - (isa(V) && Extension != EK_SignExt)) { + if (isa(V) || + isa(V)) { Value *CastOp = cast(V)->getOperand(0); unsigned OldWidth = Scale.getBitWidth(); unsigned SmallWidth = CastOp->getType()->getPrimitiveSizeInBits(); - Scale = Scale.trunc(SmallWidth); - Offset = Offset.trunc(SmallWidth); - Extension = isa(V) ? EK_SignExt : EK_ZeroExt; - - Value *Result = GetLinearExpression(CastOp, Scale, Offset, Extension, - DL, Depth+1, AT, DT); - Scale = Scale.zext(OldWidth); + APInt SmallScale = Scale, SmallOffset = Offset; + Value *Result = GetLinearExpression(CastOp, SmallScale, SmallOffset, Extensions, + DL, Depth+1, AT, DT, nsw, nuw); + + ExtensionKind ThisExt; + if(isa(V)) { + ThisExt = EK_SignExt; + if(nsw) { + // we haven't sign-wrapped, so it's valid to decompose sext(%x + c) + // into sext(%x) + sext(c). We'll sext the Offset ourselves: + Scale = SmallScale; + Offset = SmallOffset. + trunc(SmallWidth). + sext(Offset.getBitWidth()); + } else { + // We may have signed-wrapped, so don't decompose sext(%x + c) into sext(%x) + sext(c) + Result = CastOp; + } + } else { + ThisExt = EK_ZeroExt; + if(nuw) { + Scale = SmallScale; + // We get the zext for free, as zext(trunc(%x)) == %x + Offset = SmallOffset; + } else { + // We may have unsigned-wrapped, so don't decompose zext(%x + c) into zext(%x) + zext(c) + Result = CastOp; + } + } - // 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); + // zext(zext(%x)) == zext(%x), and similiarly for sext, so we don't need + // to have consective duplicate ExtensionKinds in the Extensions vector. + unsigned ExtendedBy = OldWidth - SmallWidth; + if (Extensions.empty() || Extensions.back().first != ThisExt) { + Extensions.push_back(std::make_pair(ThisExt, ExtendedBy)); + } else { + Extensions.back().second += ExtendedBy; + } return Result; } @@ -376,18 +425,22 @@ } uint64_t Scale = DL->getTypeAllocSize(*GTI); - ExtensionKind Extension = EK_NotExtended; + + // size based on GetLinearExpression's recursion depth. + SmallVector, 6> Extensions; // If the integer type is smaller than the pointer size, it is implicitly // sign extended to pointer size. unsigned Width = Index->getType()->getIntegerBitWidth(); - if (DL->getPointerSizeInBits(AS) > Width) - Extension = EK_SignExt; + unsigned PointerSize = DL->getPointerSizeInBits(AS); + if (PointerSize > Width) + Extensions.push_back(std::make_pair(EK_SignExt, PointerSize - Width)); // Use GetLinearExpression to decompose the index into a C1*V+C2 form. APInt IndexScale(Width, 0), IndexOffset(Width, 0); - Index = GetLinearExpression(Index, IndexScale, IndexOffset, Extension, - *DL, 0, AT, DT); + bool nsw = true, nuw = true; + Index = GetLinearExpression(Index, IndexScale, IndexOffset, Extensions, + *DL, 0, AT, DT, nsw, nuw); // The GEP index scale ("Scale") scales C1*V+C2, yielding (C1*V+C2)*Scale. // This gives us an aggregate computation of (C1*Scale)*V + C2*Scale. @@ -400,7 +453,7 @@ // This also ensures that 'x' only appears in the index list once. for (unsigned i = 0, e = VarIndices.size(); i != e; ++i) { if (VarIndices[i].V == Index && - VarIndices[i].Extension == Extension) { + VarIndices[i].Extensions == Extensions) { Scale += VarIndices[i].Scale; VarIndices.erase(VarIndices.begin()+i); break; @@ -409,13 +462,13 @@ // Make sure that we have a scale that makes sense for this target's // pointer size. - if (unsigned ShiftBits = 64 - DL->getPointerSizeInBits(AS)) { + if (unsigned ShiftBits = 64 - PointerSize) { Scale <<= ShiftBits; Scale = (int64_t)Scale >> ShiftBits; } if (Scale) { - VariableGEPIndex Entry = {Index, Extension, + VariableGEPIndex Entry = {Index, Extensions, static_cast(Scale)}; VarIndices.push_back(Entry); } @@ -1087,7 +1140,8 @@ // Zero-extension widens the variable, and so forces the sign // bit to zero. - bool IsZExt = GEP1VariableIndices[i].Extension == EK_ZeroExt; + auto &Extensions = GEP1VariableIndices[i].Extensions; + bool IsZExt = !Extensions.empty() && Extensions.back().first == EK_ZeroExt; SignKnownZero |= IsZExt; SignKnownOne &= !IsZExt; @@ -1446,14 +1500,14 @@ for (unsigned i = 0, e = Src.size(); i != e; ++i) { const Value *V = Src[i].V; - ExtensionKind Extension = Src[i].Extension; + auto Extensions = Src[i].Extensions; int64_t Scale = Src[i].Scale; // Find V in Dest. This is N^2, but pointer indices almost never have more // than a few variable indexes. for (unsigned j = 0, e = Dest.size(); j != e; ++j) { if (!isValueEqualInPotentialCycles(Dest[j].V, V) || - Dest[j].Extension != Extension) + Dest[j].Extensions != Extensions) continue; // If we found it, subtract off Scale V's from the entry in Dest. If it @@ -1468,7 +1522,7 @@ // If we didn't consume this entry, add it to the end of the Dest list. if (Scale) { - VariableGEPIndex Entry = { V, Extension, -Scale }; + VariableGEPIndex Entry = { V, Extensions, -Scale }; Dest.push_back(Entry); } } Index: test/Analysis/BasicAA/q.bad.ll =================================================================== --- /dev/null +++ test/Analysis/BasicAA/q.bad.ll @@ -0,0 +1,98 @@ +; 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" + +; CHECK-LABEL: test_zext_sext_255 +; CHECK: NoAlias: i8* %a, i8* %b +define void @test_zext_sext_255(i8* %mem) { + %zext.255 = zext i8 255 to i16 ; 0x00FF + %sext.255 = sext i8 255 to i16 ; 0xFFFF + %zext.sext.255 = zext i16 %sext.255 to i32 ; 0x0000FFFF + %sext.zext.255 = sext i16 %zext.255 to i32 ; 0x000000FF + %zext.zext.sext.255 = zext i32 %zext.sext.255 to i64 + %zext.sext.zext.255 = zext i32 %sext.zext.255 to i64 + %a = getelementptr inbounds i8* %mem, i64 %zext.zext.sext.255 + %b = getelementptr inbounds i8* %mem, i64 %zext.sext.zext.255 + ret void +} + +; CHECK-LABEL: test_path_dependence +; CHECK: PartialAlias: i8* %a, i8* %b +; CHECK: MustAlias: 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 unsigned-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, and as nsw %p <= 2147483647 + %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 > 0x10000000 (ie <= 0 as a signed number) then the zext will make this a huge positive number + %p.nsw.64.again = add nsw i64 %p.nsw.minus1.64, 1 ; ...and so 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: test_zext_sext_num +; CHECK: PartialAlias: i8* %a, i8* %b +; %a and %b NoAlias if %num == 255 (see @test_zext_sext_255), but %a and %b NoAlias for other values of %num (e.g. 0) +define void @test_zext_sext_num(i8* %mem, i8 %num) { + %zext.num = zext i8 %num to i16 + %sext.num = sext i8 %num to i16 + %zext.sext.num = zext i16 %sext.num to i32 + %sext.zext.num = sext i16 %zext.num to i32 + %zext.zext.sext.num = zext i32 %zext.sext.num to i64 + %zext.sext.zext.num = zext i32 %sext.zext.num to i64 + %a = getelementptr inbounds i8* %mem, i64 %zext.zext.sext.num + %b = getelementptr inbounds i8* %mem, i64 %zext.sext.zext.num + ret void +} + +; CHECK-LABEL: test_zext_sext_amounts +; CHECK: PartialAlias: i8* %a, i8* %b +; %a and %b only PartialAlias as, although they're both zext(sext(%num)) they'll extend the sign by a different +; number of bits before zext-ing the remainder. +define void @test_zext_sext_amounts(i8* %mem, i8 %num) { + %sext.1 = sext i8 %num to i16 + %sext.zext.1 = zext i16 %sext.1 to i64 + %sext.2 = sext i8 %num to i32 + %sext.zext.2 = zext i32 %sext.2 to i64 + %a = getelementptr inbounds i8* %mem, i64 %sext.zext.1 + %b = getelementptr inbounds i8* %mem, i64 %sext.zext.2 + ret void +} + +; CHECK-LABEL: based_on_pr18068 +; CHECK: NoAlias: i8* %a, i8* %b +; CHECK: NoAlias: i8* %a, i8* %c +define void @based_on_pr18068(i32 %loaded, i8* %mem) { + %loaded.64 = zext i32 %loaded to i64 + %add1 = add i32 %loaded, -1 ; unsigned wraps unless %loaded == 0 + %add1.64 = zext i32 %add1 to i64 ; is zext(%loaded) always != zext(%loaded - 1)? Yes -> NoAlias + %sub1 = sub i32 %loaded, 1 ; unsigned wraps iff %loaded == 0 + %sub1.64 = zext i32 %sub1 to i64 ; is zext(%loaded) always != zext(%loaded - 1)? Yes -> NoAlias + %a = getelementptr inbounds i8* %mem, i64 %loaded.64 + %b = getelementptr inbounds i8* %mem, i64 %add1.64 + %c = getelementptr inbounds i8* %mem, i64 %sub1.64 + ret void +} + +; CHECK-LABEL: uncompressStream +; CHECK: MustAlias: i8* %a, i8* %b +; CHECK: NoAlias: i8* %a, i8* %c +define void @uncompressStream(i8* %mem) { + %zext.255 = zext i8 255 to i32 + %sext.255 = sext i8 255 to i32 + %a = getelementptr inbounds i8* %mem, i32 255 + %b = getelementptr inbounds i8* %mem, i32 %zext.255 + %c = getelementptr inbounds i8* %mem, i32 %sext.255 + ret void +}