Index: llvm/lib/Analysis/BasicAliasAnalysis.cpp =================================================================== --- llvm/lib/Analysis/BasicAliasAnalysis.cpp +++ llvm/lib/Analysis/BasicAliasAnalysis.cpp @@ -274,41 +274,53 @@ //===----------------------------------------------------------------------===// namespace { -/// Represents zext(sext(V)). +/// Represents zext(sext(trunc(V))). struct ExtendedValue { const Value *V; - unsigned ZExtBits; - unsigned SExtBits; + unsigned ZExtBits = 0; + unsigned SExtBits = 0; + unsigned TruncBits = 0; - explicit ExtendedValue(const Value *V, unsigned ZExtBits = 0, - unsigned SExtBits = 0) - : V(V), ZExtBits(ZExtBits), SExtBits(SExtBits) {} + explicit ExtendedValue(const Value *V) : V(V) {} + ExtendedValue(const Value *V, unsigned ZExtBits, unsigned SExtBits, + unsigned TruncBits) + : V(V), ZExtBits(ZExtBits), SExtBits(SExtBits), TruncBits(TruncBits) {} unsigned getBitWidth() const { - return V->getType()->getPrimitiveSizeInBits() + ZExtBits + SExtBits; + return V->getType()->getPrimitiveSizeInBits() - TruncBits + ZExtBits + + SExtBits; } ExtendedValue withValue(const Value *NewV) const { - return ExtendedValue(NewV, ZExtBits, SExtBits); + return ExtendedValue(NewV, ZExtBits, SExtBits, TruncBits); } ExtendedValue withZExtOfValue(const Value *NewV) const { unsigned ExtendBy = V->getType()->getPrimitiveSizeInBits() - NewV->getType()->getPrimitiveSizeInBits(); + if (ExtendBy <= TruncBits) + return ExtendedValue(NewV, ZExtBits, SExtBits, TruncBits - ExtendBy); + // zext(sext(zext(NewV))) == zext(zext(zext(NewV))) - return ExtendedValue(NewV, ZExtBits + SExtBits + ExtendBy, 0); + ExtendBy -= TruncBits; + return ExtendedValue(NewV, ZExtBits + SExtBits + ExtendBy, 0, 0); } ExtendedValue withSExtOfValue(const Value *NewV) const { unsigned ExtendBy = V->getType()->getPrimitiveSizeInBits() - NewV->getType()->getPrimitiveSizeInBits(); + if (ExtendBy <= TruncBits) + return ExtendedValue(NewV, ZExtBits, SExtBits, TruncBits - ExtendBy); + // zext(sext(sext(NewV))) - return ExtendedValue(NewV, ZExtBits, SExtBits + ExtendBy); + ExtendBy -= TruncBits; + return ExtendedValue(NewV, ZExtBits, SExtBits + ExtendBy, 0); } APInt evaluateWith(APInt N) const { assert(N.getBitWidth() == V->getType()->getPrimitiveSizeInBits() && "Incompatible bit width"); + if (TruncBits) N = N.trunc(N.getBitWidth() - TruncBits); if (SExtBits) N = N.sext(N.getBitWidth() + SExtBits); if (ZExtBits) N = N.zext(N.getBitWidth() + ZExtBits); return N; @@ -317,6 +329,7 @@ KnownBits evaluateWith(KnownBits N) const { assert(N.getBitWidth() == V->getType()->getPrimitiveSizeInBits() && "Incompatible bit width"); + if (TruncBits) N = N.trunc(N.getBitWidth() - TruncBits); if (SExtBits) N = N.sext(N.getBitWidth() + SExtBits); if (ZExtBits) N = N.zext(N.getBitWidth() + ZExtBits); return N; @@ -325,6 +338,7 @@ ConstantRange evaluateWith(ConstantRange N) const { assert(N.getBitWidth() == V->getType()->getPrimitiveSizeInBits() && "Incompatible bit width"); + if (TruncBits) N = N.truncate(N.getBitWidth() - TruncBits); if (SExtBits) N = N.signExtend(N.getBitWidth() + SExtBits); if (ZExtBits) N = N.zeroExtend(N.getBitWidth() + ZExtBits); return N; @@ -333,15 +347,17 @@ bool canDistributeOver(bool NUW, bool NSW) const { // zext(x op y) == zext(x) op zext(y) // sext(x op y) == sext(x) op sext(y) + // trunc(x op y) == trunc(x) op trunc(y) return (!ZExtBits || NUW) && (!SExtBits || NSW); } bool hasSameExtensionsAs(const ExtendedValue &Other) const { - return ZExtBits == Other.ZExtBits && SExtBits == Other.SExtBits; + return ZExtBits == Other.ZExtBits && SExtBits == Other.SExtBits && + TruncBits == Other.TruncBits; } }; -/// Represents zext(sext(V)) * Scale + Offset. +/// Represents zext(sext(trunc(V))) * Scale + Offset. struct LinearExpression { ExtendedValue Val; APInt Scale; @@ -388,6 +404,11 @@ if (!Val.canDistributeOver(NUW, NSW)) return Val; + // While we can distribute over trunc, we cannot preserve nowrap flags + // in that case. + if (Val.TruncBits) + NUW = NSW = false; + LinearExpression E(Val); switch (BOp->getOpcode()) { default: @@ -478,7 +499,7 @@ namespace { // A linear transformation of a Value; this class represents -// ZExt(SExt(V, SExtBits), ZExtBits) * Scale. +// ZExt(SExt(Trunc(V, TruncBits), SExtBits), ZExtBits) * Scale. struct VariableGEPIndex { ExtendedValue Val; APInt Scale; @@ -497,6 +518,7 @@ OS << "(V=" << Val.V->getName() << ", zextbits=" << Val.ZExtBits << ", sextbits=" << Val.SExtBits + << ", truncbits=" << Val.TruncBits << ", scale=" << Scale << ")"; } }; @@ -664,8 +686,9 @@ // sign extended to pointer size. unsigned Width = Index->getType()->getIntegerBitWidth(); unsigned SExtBits = PointerSize > Width ? PointerSize - Width : 0; + unsigned TruncBits = PointerSize < Width ? Width - PointerSize : 0; LinearExpression LE = GetLinearExpression( - ExtendedValue(Index, 0, SExtBits), DL, 0, AC, DT); + ExtendedValue(Index, 0, SExtBits, TruncBits), DL, 0, AC, DT); // 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. @@ -681,7 +704,7 @@ APInt ScaledOffset = LE.Offset.sextOrTrunc(MaxPointerSize) .smul_ov(Scale, Overflow); if (Overflow) { - LE = LinearExpression(ExtendedValue(Index, 0, SExtBits)); + LE = LinearExpression(ExtendedValue(Index, 0, SExtBits, TruncBits)); } else { Decomposed.Offset += ScaledOffset; Scale *= LE.Scale.sextOrTrunc(MaxPointerSize); @@ -1278,7 +1301,6 @@ if (AllNonNegative || AllNonPositive) { KnownBits Known = Index.Val.evaluateWith( computeKnownBits(Index.Val.V, DL, 0, &AC, Index.CxtI, DT)); - // TODO: Account for implicit trunc. bool SignKnownZero = Known.isNonNegative(); bool SignKnownOne = Known.isNegative(); AllNonNegative &= (SignKnownZero && Scale.isNonNegative()) || @@ -1327,7 +1349,8 @@ if (DecompGEP1.VarIndices.size() == 1) { // VarIndex = Scale*V. const VariableGEPIndex &Var = DecompGEP1.VarIndices[0]; - if (isKnownNonZero(Var.Val.V, DL, 0, &AC, Var.CxtI, DT)) { + if (Var.Val.TruncBits == 0 && + isKnownNonZero(Var.Val.V, DL, 0, &AC, Var.CxtI, DT)) { // If V != 0 then abs(VarIndex) >= abs(Scale). MinAbsVarIndex = Var.Scale.abs(); } @@ -1343,7 +1366,7 @@ // inequality of values across loop iterations. const VariableGEPIndex &Var0 = DecompGEP1.VarIndices[0]; const VariableGEPIndex &Var1 = DecompGEP1.VarIndices[1]; - if (Var0.Scale == -Var1.Scale && + if (Var0.Scale == -Var1.Scale && Var0.Val.TruncBits == 0 && Var0.Val.hasSameExtensionsAs(Var1.Val) && VisitedPhiBBs.empty() && isKnownNonEqual(Var0.Val.V, Var1.Val.V, DL, &AC, /* CxtI */ nullptr, DT)) @@ -1868,7 +1891,8 @@ const VariableGEPIndex &Var0 = GEP.VarIndices[0], &Var1 = GEP.VarIndices[1]; - if (!Var0.Val.hasSameExtensionsAs(Var1.Val) || Var0.Scale != -Var1.Scale || + if (Var0.Val.TruncBits != 0 || !Var0.Val.hasSameExtensionsAs(Var1.Val) || + Var0.Scale != -Var1.Scale || Var0.Val.V->getType() != Var1.Val.V->getType()) return false; Index: llvm/test/Analysis/BasicAA/gep-implicit-trunc-32-bit-pointers.ll =================================================================== --- llvm/test/Analysis/BasicAA/gep-implicit-trunc-32-bit-pointers.ll +++ llvm/test/Analysis/BasicAA/gep-implicit-trunc-32-bit-pointers.ll @@ -45,15 +45,14 @@ ret void } -; FIXME: Currently we incorrectly determine NoAlias for %gep.1 and %gep.2. The ; GEP indices get implicitly truncated to 32 bit, so multiples of 2^32 ; (=4294967296) will be 0. ; See https://alive2.llvm.org/ce/z/HHjQgb. define void @mustalias_overflow_in_32_bit_add_mul_gep(i8* %ptr, i64 %i) { ; CHECK-LABEL: Function: mustalias_overflow_in_32_bit_add_mul_gep: 3 pointers, 1 call sites -; CHECK-NEXT: NoAlias: i8* %gep.1, i8* %ptr -; CHECK-NEXT: NoAlias: i8* %gep.2, i8* %ptr -; CHECK-NEXT: NoAlias: i8* %gep.1, i8* %gep.2 +; CHECK-NEXT: MayAlias: i8* %gep.1, i8* %ptr +; CHECK-NEXT: MayAlias: i8* %gep.2, i8* %ptr +; CHECK-NEXT: MayAlias: i8* %gep.1, i8* %gep.2 ; %s.1 = icmp sgt i64 %i, 0 call void @llvm.assume(i1 %s.1) @@ -67,10 +66,9 @@ ret void } -; FIXME: While %n is non-zero, its low 32 bits may not be. define void @mayalias_overflow_in_32_bit_non_zero(i8* %ptr, i64 %n) { ; CHECK-LABEL: Function: mayalias_overflow_in_32_bit_non_zero -; CHECK: NoAlias: i8* %gep, i8* %ptr +; CHECK: MayAlias: i8* %gep, i8* %ptr ; %c = icmp ne i64 %n, 0 call void @llvm.assume(i1 %c) @@ -80,12 +78,11 @@ ret void } -; FIXME: While %n is positive, its low 32 bits may not be. define void @mayalias_overflow_in_32_bit_positive(i8* %ptr, i64 %n) { ; CHECK-LABEL: Function: mayalias_overflow_in_32_bit_positive ; CHECK: NoAlias: i8* %gep.1, i8* %ptr -; CHECK: NoAlias: i8* %gep.2, i8* %ptr -; CHECK: NoAlias: i8* %gep.1, i8* %gep.2 +; CHECK: MayAlias: i8* %gep.2, i8* %ptr +; CHECK: MayAlias: i8* %gep.1, i8* %gep.2 ; %c = icmp sgt i64 %n, 0 call void @llvm.assume(i1 %c)