diff --git a/clang/lib/Sema/SemaChecking.cpp b/clang/lib/Sema/SemaChecking.cpp --- a/clang/lib/Sema/SemaChecking.cpp +++ b/clang/lib/Sema/SemaChecking.cpp @@ -10162,15 +10162,23 @@ /// Structure recording the 'active' range of an integer-valued /// expression. struct IntRange { - /// The number of bits active in the int. + /// The number of bits active in the int. Note that this includes exactly one + /// sign bit if !NoNegative. unsigned Width; - /// True if the int is known not to have negative values. + /// True if the int is known not to have negative values. If so, all leading + /// bits before Width are known zero, otherwise they are known to be the + /// same as the MSB within Width. bool NonNegative; IntRange(unsigned Width, bool NonNegative) : Width(Width), NonNegative(NonNegative) {} + /// Number of bits excluding the sign bit. + unsigned valueBits() const { + return NonNegative ? Width : Width - 1; + } + /// Returns the range of the bool type. static IntRange forBoolType() { return IntRange(1, true); @@ -10254,14 +10262,63 @@ /// Returns the supremum of two ranges: i.e. their conservative merge. static IntRange join(IntRange L, IntRange R) { - return IntRange(std::max(L.Width, R.Width), + bool Unsigned = L.NonNegative && R.NonNegative; + return IntRange(std::max(L.valueBits(), R.valueBits()) + !Unsigned, L.NonNegative && R.NonNegative); } - /// Returns the infinum of two ranges: i.e. their aggressive merge. - static IntRange meet(IntRange L, IntRange R) { - return IntRange(std::min(L.Width, R.Width), - L.NonNegative || R.NonNegative); + /// Return the range of a bitwise-AND of the two ranges. + static IntRange bit_and(IntRange L, IntRange R) { + unsigned Bits = std::max(L.Width, R.Width); + bool NonNegative = false; + if (L.NonNegative) { + Bits = std::min(Bits, L.Width); + NonNegative = true; + } + if (R.NonNegative) { + Bits = std::min(Bits, R.Width); + NonNegative = true; + } + return IntRange(Bits, NonNegative); + } + + /// Return the range of a sum of the two ranges. + static IntRange sum(IntRange L, IntRange R) { + bool Unsigned = L.NonNegative || R.NonNegative; + return IntRange(std::max(L.valueBits(), R.valueBits()) + 1 + !Unsigned, + Unsigned); + } + + /// Return the range of a difference of the two ranges. + static IntRange difference(IntRange L, IntRange R) { + // We need a 1-bit-wider range if: + // 1) LHS can be negative: least value can be reduced. + // 2) RHS can be negative: greatest value can be increased. + bool CanWiden = !L.NonNegative || !R.NonNegative; + bool Unsigned = L.NonNegative && R.Width == 0; + return IntRange(std::max(L.valueBits(), R.valueBits()) + CanWiden + + !Unsigned, + Unsigned); + } + + /// Return the range of a product of the two ranges. + static IntRange product(IntRange L, IntRange R) { + // If both LHS and RHS can be negative, we can form + // -2^L * -2^R = 2^(L + R) + // which requires L + R + 1 value bits to represent. + bool CanWiden = !L.NonNegative && !R.NonNegative; + bool Unsigned = L.NonNegative && R.NonNegative; + return IntRange(L.valueBits() + R.valueBits() + CanWiden + !Unsigned, + Unsigned); + } + + /// Return the range of a remainder operation between the two ranges. + static IntRange rem(IntRange L, IntRange R) { + // The result of a remainder can't be larger than the result of + // either side. The sign of the result is the sign of the LHS. + bool Unsigned = L.NonNegative; + return IntRange(std::min(L.valueBits(), R.valueBits()) + !Unsigned, + Unsigned); } }; @@ -10319,9 +10376,13 @@ /// Pseudo-evaluate the given integer expression, estimating the /// range of values it might take. /// -/// \param MaxWidth - the width to which the value will be truncated +/// \param MaxWidth The width to which the value will be truncated. +/// \param Approximate If \c true, return a likely range for the result: in +/// particular, assume that aritmetic on narrower types doesn't leave +/// those types. If \c false, return a range including all possible +/// result values. static IntRange GetExprRange(ASTContext &C, const Expr *E, unsigned MaxWidth, - bool InConstantContext) { + bool InConstantContext, bool Approximate) { E = E->IgnoreParens(); // Try a full evaluation first. @@ -10334,7 +10395,8 @@ // being of the new, wider type. if (const auto *CE = dyn_cast(E)) { if (CE->getCastKind() == CK_NoOp || CE->getCastKind() == CK_LValueToRValue) - return GetExprRange(C, CE->getSubExpr(), MaxWidth, InConstantContext); + return GetExprRange(C, CE->getSubExpr(), MaxWidth, InConstantContext, + Approximate); IntRange OutputTypeRange = IntRange::forValueOfType(C, GetExprType(CE)); @@ -10347,7 +10409,7 @@ IntRange SubRange = GetExprRange(C, CE->getSubExpr(), std::min(MaxWidth, OutputTypeRange.Width), - InConstantContext); + InConstantContext, Approximate); // Bail out if the subexpr's range is as wide as the cast type. if (SubRange.Width >= OutputTypeRange.Width) @@ -10365,17 +10427,19 @@ if (CO->getCond()->EvaluateAsBooleanCondition(CondResult, C)) return GetExprRange(C, CondResult ? CO->getTrueExpr() : CO->getFalseExpr(), - MaxWidth, InConstantContext); + MaxWidth, InConstantContext, Approximate); // Otherwise, conservatively merge. - IntRange L = - GetExprRange(C, CO->getTrueExpr(), MaxWidth, InConstantContext); - IntRange R = - GetExprRange(C, CO->getFalseExpr(), MaxWidth, InConstantContext); + IntRange L = GetExprRange(C, CO->getTrueExpr(), MaxWidth, InConstantContext, + Approximate); + IntRange R = GetExprRange(C, CO->getFalseExpr(), MaxWidth, + InConstantContext, Approximate); return IntRange::join(L, R); } if (const auto *BO = dyn_cast(E)) { + IntRange (*Combine)(IntRange, IntRange) = IntRange::join; + switch (BO->getOpcode()) { case BO_Cmp: llvm_unreachable("builtin <=> should have class type"); @@ -10407,7 +10471,8 @@ // been coerced to the LHS type. case BO_Assign: // TODO: bitfields? - return GetExprRange(C, BO->getRHS(), MaxWidth, InConstantContext); + return GetExprRange(C, BO->getRHS(), MaxWidth, InConstantContext, + Approximate); // Operations with opaque sources are black-listed. case BO_PtrMemD: @@ -10417,9 +10482,8 @@ // Bitwise-and uses the *infinum* of the two source ranges. case BO_And: case BO_AndAssign: - return IntRange::meet( - GetExprRange(C, BO->getLHS(), MaxWidth, InConstantContext), - GetExprRange(C, BO->getRHS(), MaxWidth, InConstantContext)); + Combine = IntRange::bit_and; + break; // Left shift gets black-listed based on a judgement call. case BO_Shl: @@ -10440,7 +10504,8 @@ // Right shift by a constant can narrow its left argument. case BO_Shr: case BO_ShrAssign: { - IntRange L = GetExprRange(C, BO->getLHS(), MaxWidth, InConstantContext); + IntRange L = GetExprRange(C, BO->getLHS(), MaxWidth, InConstantContext, + Approximate); // If the shift amount is a positive constant, drop the width by // that much. @@ -10460,12 +10525,24 @@ // Comma acts as its right operand. case BO_Comma: - return GetExprRange(C, BO->getRHS(), MaxWidth, InConstantContext); + return GetExprRange(C, BO->getRHS(), MaxWidth, InConstantContext, + Approximate); + + case BO_Add: + if (!Approximate) + Combine = IntRange::sum; + break; - // Black-list pointer subtractions. case BO_Sub: if (BO->getLHS()->getType()->isPointerType()) return IntRange::forValueOfType(C, GetExprType(E)); + if (!Approximate) + Combine = IntRange::difference; + break; + + case BO_Mul: + if (!Approximate) + Combine = IntRange::product; break; // The width of a division result is mostly determined by the size @@ -10473,7 +10550,8 @@ case BO_Div: { // Don't 'pre-truncate' the operands. unsigned opWidth = C.getIntWidth(GetExprType(E)); - IntRange L = GetExprRange(C, BO->getLHS(), opWidth, InConstantContext); + IntRange L = GetExprRange(C, BO->getLHS(), opWidth, InConstantContext, + Approximate); // If the divisor is constant, use that. if (Optional divisor = @@ -10487,36 +10565,35 @@ } // Otherwise, just use the LHS's width. - IntRange R = GetExprRange(C, BO->getRHS(), opWidth, InConstantContext); + // FIXME: This is wrong if the LHS could be its minimal value and the RHS + // could be -1. + IntRange R = GetExprRange(C, BO->getRHS(), opWidth, InConstantContext, + Approximate); return IntRange(L.Width, L.NonNegative && R.NonNegative); } - // The result of a remainder can't be larger than the result of - // either side. - case BO_Rem: { - // Don't 'pre-truncate' the operands. - unsigned opWidth = C.getIntWidth(GetExprType(E)); - IntRange L = GetExprRange(C, BO->getLHS(), opWidth, InConstantContext); - IntRange R = GetExprRange(C, BO->getRHS(), opWidth, InConstantContext); - - IntRange meet = IntRange::meet(L, R); - meet.Width = std::min(meet.Width, MaxWidth); - return meet; - } + case BO_Rem: + Combine = IntRange::rem; + break; // The default behavior is okay for these. - case BO_Mul: - case BO_Add: case BO_Xor: case BO_Or: break; } - // The default case is to treat the operation as if it were closed - // on the narrowest type that encompasses both operands. - IntRange L = GetExprRange(C, BO->getLHS(), MaxWidth, InConstantContext); - IntRange R = GetExprRange(C, BO->getRHS(), MaxWidth, InConstantContext); - return IntRange::join(L, R); + // Combine the two ranges, but limit the result to the type in which we + // performed the computation. + QualType T = GetExprType(E); + unsigned opWidth = C.getIntWidth(T); + IntRange L = + GetExprRange(C, BO->getLHS(), opWidth, InConstantContext, Approximate); + IntRange R = + GetExprRange(C, BO->getRHS(), opWidth, InConstantContext, Approximate); + IntRange C = Combine(L, R); + C.NonNegative |= T->isUnsignedIntegerOrEnumerationType(); + C.Width = std::min(C.Width, MaxWidth); + return C; } if (const auto *UO = dyn_cast(E)) { @@ -10531,12 +10608,14 @@ return IntRange::forValueOfType(C, GetExprType(E)); default: - return GetExprRange(C, UO->getSubExpr(), MaxWidth, InConstantContext); + return GetExprRange(C, UO->getSubExpr(), MaxWidth, InConstantContext, + Approximate); } } if (const auto *OVE = dyn_cast(E)) - return GetExprRange(C, OVE->getSourceExpr(), MaxWidth, InConstantContext); + return GetExprRange(C, OVE->getSourceExpr(), MaxWidth, InConstantContext, + Approximate); if (const auto *BitField = E->getSourceBitField()) return IntRange(BitField->getBitWidthValue(C), @@ -10546,8 +10625,9 @@ } static IntRange GetExprRange(ASTContext &C, const Expr *E, - bool InConstantContext) { - return GetExprRange(C, E, C.getIntWidth(GetExprType(E)), InConstantContext); + bool InConstantContext, bool Approximate) { + return GetExprRange(C, E, C.getIntWidth(GetExprType(E)), InConstantContext, + Approximate); } /// Checks whether the given value, which currently has the given @@ -10792,8 +10872,8 @@ S.Context.hasSameUnqualifiedType(Constant->getType(), Other->getType())) return false; - IntRange OtherValueRange = - GetExprRange(S.Context, Other, S.isConstantEvaluated()); + IntRange OtherValueRange = GetExprRange( + S.Context, Other, S.isConstantEvaluated(), /*Approximate*/ false); QualType OtherT = Other->getType(); if (const auto *AT = OtherT->getAs()) @@ -10992,8 +11072,8 @@ } // Otherwise, calculate the effective range of the signed operand. - IntRange signedRange = - GetExprRange(S.Context, signedOperand, S.isConstantEvaluated()); + IntRange signedRange = GetExprRange( + S.Context, signedOperand, S.isConstantEvaluated(), /*Approximate*/ true); // Go ahead and analyze implicit conversions in the operands. Note // that we skip the implicit conversions on both sides. @@ -11011,7 +11091,8 @@ if (E->isEqualityOp()) { unsigned comparisonWidth = S.Context.getIntWidth(T); IntRange unsignedRange = - GetExprRange(S.Context, unsignedOperand, S.isConstantEvaluated()); + GetExprRange(S.Context, unsignedOperand, S.isConstantEvaluated(), + /*Approximate*/ true); // We should never be unable to prove that the unsigned operand is // non-negative. @@ -11894,7 +11975,8 @@ if (SourceBT && TargetBT && SourceBT->isIntegerType() && TargetBT->isFloatingType() && !IsListInit) { // Determine the number of precision bits in the source integer type. - IntRange SourceRange = GetExprRange(S.Context, E, S.isConstantEvaluated()); + IntRange SourceRange = GetExprRange(S.Context, E, S.isConstantEvaluated(), + /*Approximate*/ true); unsigned int SourcePrecision = SourceRange.Width; // Determine the number of precision bits in the @@ -11959,10 +12041,13 @@ << E->getType()); } - IntRange SourceRange = GetExprRange(S.Context, E, S.isConstantEvaluated()); + IntRange MinSourceRange = + GetExprRange(S.Context, E, S.isConstantEvaluated(), /*Approximate*/ true); + IntRange MaxSourceRange = + GetExprRange(S.Context, E, S.isConstantEvaluated(), /*Approximate*/ false); IntRange TargetRange = IntRange::forTargetOfCanonicalType(S.Context, Target); - if (SourceRange.Width > TargetRange.Width) { + if (MinSourceRange.Width > TargetRange.Width) { // If the source is a constant, use a default-on diagnostic. // TODO: this should happen for bitfield stores, too. Expr::EvalResult Result; @@ -11981,7 +12066,7 @@ E->getExprLoc(), E, S.PDiag(diag::warn_impcast_integer_precision_constant) << PrettySourceValue << PrettyTargetValue << E->getType() << T - << E->getSourceRange() << clang::SourceRange(CC)); + << E->getSourceRange() << SourceRange(CC)); return; } @@ -11995,7 +12080,9 @@ return DiagnoseImpCast(S, E, T, CC, diag::warn_impcast_integer_precision); } - if (TargetRange.Width > SourceRange.Width) { + // Only warn here if E can't possibly reach the target range, not only if + // it's not likely to be in that range. + if (TargetRange.Width > MaxSourceRange.Width) { if (auto *UO = dyn_cast(E)) if (UO->getOpcode() == UO_Minus) if (Source->isUnsignedIntegerType()) { @@ -12008,8 +12095,8 @@ } } - if (TargetRange.Width == SourceRange.Width && !TargetRange.NonNegative && - SourceRange.NonNegative && Source->isSignedIntegerType()) { + if (TargetRange.Width == MinSourceRange.Width && !TargetRange.NonNegative && + MinSourceRange.NonNegative && Source->isSignedIntegerType()) { // Warn when doing a signed to signed conversion, warn if the positive // source value is exactly the width of the target type, which will // cause a negative value to be stored. @@ -12026,7 +12113,7 @@ E->getExprLoc(), E, S.PDiag(diag::warn_impcast_integer_precision_constant) << PrettySourceValue << PrettyTargetValue << E->getType() << T - << E->getSourceRange() << clang::SourceRange(CC)); + << E->getSourceRange() << SourceRange(CC)); return; } } @@ -12034,9 +12121,9 @@ // Fall through for non-constants to give a sign conversion warning. } - if ((TargetRange.NonNegative && !SourceRange.NonNegative) || - (!TargetRange.NonNegative && SourceRange.NonNegative && - SourceRange.Width == TargetRange.Width)) { + if ((TargetRange.NonNegative && !MinSourceRange.NonNegative) || + (!TargetRange.NonNegative && MinSourceRange.NonNegative && + MinSourceRange.Width == TargetRange.Width)) { if (S.SourceMgr.isInSystemMacro(CC)) return; diff --git a/clang/test/Sema/tautological-constant-compare.c b/clang/test/Sema/tautological-constant-compare.c --- a/clang/test/Sema/tautological-constant-compare.c +++ b/clang/test/Sema/tautological-constant-compare.c @@ -4,12 +4,16 @@ // RUN: %clang_cc1 -triple x86_64-linux-gnu -fsyntax-only -Wtautological-type-limit-compare -DTEST -verify -x c++ %s // RUN: %clang_cc1 -triple x86_64-linux-gnu -fsyntax-only -Wtype-limits -DTEST -verify %s // RUN: %clang_cc1 -triple x86_64-linux-gnu -fsyntax-only -Wtype-limits -DTEST -verify -x c++ %s -// RUN: %clang_cc1 -triple x86_64-linux-gnu -fsyntax-only -Wextra -Wno-sign-compare -verify %s -// RUN: %clang_cc1 -triple x86_64-linux-gnu -fsyntax-only -Wextra -Wno-sign-compare -verify -x c++ %s -// RUN: %clang_cc1 -triple x86_64-linux-gnu -fsyntax-only -Wall -verify %s -// RUN: %clang_cc1 -triple x86_64-linux-gnu -fsyntax-only -Wall -verify -x c++ %s -// RUN: %clang_cc1 -triple x86_64-linux-gnu -fsyntax-only -verify %s -// RUN: %clang_cc1 -triple x86_64-linux-gnu -fsyntax-only -verify -x c++ %s +// RUN: %clang_cc1 -triple x86_64-linux-gnu -fsyntax-only -Wextra -Wno-sign-compare -verify=silent %s +// RUN: %clang_cc1 -triple x86_64-linux-gnu -fsyntax-only -Wextra -Wno-sign-compare -verify=silent -x c++ %s +// RUN: %clang_cc1 -triple x86_64-linux-gnu -fsyntax-only -Wall -verify=silent %s +// RUN: %clang_cc1 -triple x86_64-linux-gnu -fsyntax-only -Wall -verify=silent -x c++ %s +// RUN: %clang_cc1 -triple x86_64-linux-gnu -fsyntax-only -verify=silent %s +// RUN: %clang_cc1 -triple x86_64-linux-gnu -fsyntax-only -verify=silent -x c++ %s + +#ifndef TEST +// silent-no-diagnostics +#endif int value(void); @@ -184,7 +188,6 @@ if (-32768L >= s) return 0; #else - // expected-no-diagnostics if (s == 32767) return 0; if (s != 32767) @@ -373,7 +376,6 @@ if (65535UL >= us) // expected-warning {{comparison 65535 >= 'unsigned short' is always true}} return 0; #else - // expected-no-diagnostics if (us == 65535) return 0; if (us != 65535) @@ -571,19 +573,93 @@ if ((s & 0xff) < 0) {} // #valuerange1 if ((s & 0xff) < 1) {} - if ((s & -3) < -4) {} // #valuerange2 + if ((s & -3) < -4) {} if ((s & -3) < -3) {} - if ((s & -3) < 4u) {} // (true if s non-negative) - if ((s & -3) > 4u) {} // (true if s negative) - if ((s & -3) == 4u) {} // #valuerange3 (never true) - if ((s & -3) == 3u) {} - if ((s & -3) == -5u) {} // #valuerange4 + if ((s & -3) < 4u) {} + if ((s & -3) > 4u) {} + if ((s & -3) == 4u) {} + if ((s & -3) == 3u) {} // FIXME: Impossible. + if ((s & -3) == -5u) {} if ((s & -3) == -4u) {} #if TEST == 2 // expected-warning@#valuerange1 {{comparison of 8-bit unsigned value < 0 is always false}} - // expected-warning@#valuerange2 {{comparison of 3-bit signed value < -4 is always false}} - // expected-warning@#valuerange3 {{comparison of 3-bit signed value == 4 is always false}} - // expected-warning@#valuerange4 {{comparison of 3-bit signed value == 4294967291 is always false}} +#endif + + // FIXME: Our bit-level width tracking comes unstuck here: the second of the + // conditions below is also tautological, but we can't tell that because we + // don't track the actual range, only the bit-width. + if ((s ? 1 : 0) + (us ? 1 : 0) > 1) {} + if ((s ? 1 : 0) + (us ? 1 : 0) > 2) {} + if ((s ? 1 : 0) + (us ? 1 : 0) > 3) {} // #addrange1 +#if TEST == 2 + // expected-warning@#addrange1 {{comparison of 2-bit unsigned value > 3 is always false}} +#endif + + // FIXME: The second and third comparisons are also tautological; 0x40000000 + // is the greatest value that multiplying two int16s can produce. + if (s * s > 0x3fffffff) {} + if (s * s > 0x40000000) {} + if (s * s > 0x7ffffffe) {} + if (s * s > 0x7fffffff) {} // expected-warning {{result of comparison 'int' > 2147483647 is always false}} + + if ((s & 0x3ff) * (s & 0x1f) > 0x7be0) {} + if ((s & 0x3ff) * (s & 0x1f) > 0x7be1) {} // FIXME + if ((s & 0x3ff) * (s & 0x1f) > 0x7ffe) {} // FIXME + if ((s & 0x3ff) * (s & 0x1f) > 0x7fff) {} // #mulrange1 +#if TEST == 2 + // expected-warning@#mulrange1 {{comparison of 15-bit unsigned value > 32767 is always false}} +#endif + + if (a.a * a.b > 21) {} // FIXME + if (a.a * a.b > 31) {} // #mulrange2 +#if TEST == 2 + // expected-warning@#mulrange2 {{comparison of 6-bit signed value > 31 is always false}} +#endif + + if (a.a - (s & 1) < -4) {} + if (a.a - (s & 1) < -7) {} // FIXME + if (a.a - (s & 1) < -8) {} // #subrange1 + if (a.a - (s & 1) > 3) {} // FIXME: Can be < -4 but not > 3. + if (a.a - (s & 1) > 7) {} // #subrange2 + + if (a.a - (s & 7) < -8) {} + if (a.a - (s & 7) > 7) {} // FIXME: Can be < -8 but not > 7. + if (a.a - (s & 7) < -15) {} + if (a.a - (s & 7) < -16) {} // #subrange3 + if (a.a - (s & 7) > 15) {} // #subrange4 + + if (a.b - (s & 1) > 6) {} + if (a.b - (s & 1) > 7) {} // #subrange5 + if (a.b - (s & 7) < -8) {} // #subrange6 + if (a.b - (s & 15) < -8) {} + if (a.b - (s & 15) < -16) {} // #subrange7 +#if TEST == 2 + // expected-warning@#subrange1 {{comparison of 4-bit signed value < -8 is always false}} + // expected-warning@#subrange2 {{comparison of 4-bit signed value > 7 is always false}} + // expected-warning@#subrange3 {{comparison of 5-bit signed value < -16 is always false}} + // expected-warning@#subrange4 {{comparison of 5-bit signed value > 15 is always false}} + // expected-warning@#subrange5 {{comparison of 4-bit signed value > 7 is always false}} + // expected-warning@#subrange6 {{comparison of 4-bit signed value < -8 is always false}} + // expected-warning@#subrange7 {{comparison of 5-bit signed value < -16 is always false}} +#endif + + // a.a % 3 is in range [-2, 2], which we expand to [-4, 4) + if (a.a % 3 > 2) {} + if (a.a % 3 > 3) {} // #remrange1 + if (a.a % 3 == -1) {} + if (a.a % 3 == -2) {} + if (a.a % 3 < -3) {} // FIXME + if (a.a % 3 < -4) {} // #remrange2 + + // a.b % 3 is in range [0, 3), which we expand to [0, 4) + if (a.b % 3 > 2) {} + if (a.b % 3 > 3) {} // #remrange3 + if (a.b % 3 < 0) {} // #remrange4 +#if TEST == 2 + // expected-warning@#remrange1 {{comparison of 3-bit signed value > 3 is always false}} + // expected-warning@#remrange2 {{comparison of 3-bit signed value < -4 is always false}} + // expected-warning@#remrange3 {{comparison of 2-bit unsigned value > 3 is always false}} + // expected-warning@#remrange4 {{comparison of 2-bit unsigned value < 0 is always false}} #endif return 1;