More accurately compute the ranges of possible values for +, -, *, &, %.

[rsmith]

Summary

Continue to heuristically pick the wider of the two operands for
narrowing conversion warnings so that some_char + 1 isn't treated as
being wider than a char, but use the more accurate computation for
tautological comparison warnings.

[sberg]

Fixes all the false positives it had reported for LibreOffice (which had all involved expressions containing either ~ or +).

[rtrieu]

LGTM

clang/lib/Sema/SemaChecking.cpp

10166

NonNegative

[nikic]

Just for the record, the additional analysis has a measurable compile-time impact (0.3% at O0): https://llvm-compile-time-tracker.com/compare.php?from=e7f53044e7263cdbbb4fed9abf086b88ba486bba&to=cff6dda604cb0548bef5e5951dd1e74536110588&stat=instructions

[zequanwu]

Hi, this change seems like hits a false positive case in chromium build: https://bugs.chromium.org/p/chromium/issues/detail?id=1124085

[rsmith]

In D85778#2248714, @nikic wrote:

Just for the record, the additional analysis has a measurable compile-time impact (0.3% at O0): https://llvm-compile-time-tracker.com/compare.php?from=e7f53044e7263cdbbb4fed9abf086b88ba486bba&to=cff6dda604cb0548bef5e5951dd1e74536110588&stat=instructions

Thanks, it seems very likely that this is caused by CheckImplicitConversion now calling CheckExprRange twice. It looks like that's not only avoidable, but there's a (pre-existing) bug here that we can squash at the same time :) Should be fixed in rG0ffbbce78de60f4f4d03d6ef97fe2f3bb4275e08.

[rsmith]

In D85778#2251160, @zequanwu wrote:

Hi, this change seems like hits a false positive case in chromium build: https://bugs.chromium.org/p/chromium/issues/detail?id=1124085

That's not a false positive. The code is (simplified):

int RoundDown(int a, long b) { return a & -b; }

... which is implicitly converting an expression of type long to int, losing precision. For example, RoundDown(-1, 0x1'0000'0000) is -4294967296 prior to the implicit conversion from long to int. Given that the truncation is presumably intentional (0 at least seems like the least-bad answer for rounding down 0 to a multiple of 2^32 as a 32-bit integer), you can suppress the warning with a cast.

[zequanwu]

In D85778#2251173, @rsmith wrote:

In D85778#2251160, @zequanwu wrote:

Hi, this change seems like hits a false positive case in chromium build: https://bugs.chromium.org/p/chromium/issues/detail?id=1124085

That's not a false positive. The code is (simplified):

int RoundDown(int a, long b) { return a & -b; }

... which is implicitly converting an expression of type long to int, losing precision. For example, RoundDown(-1, 0x1'0000'0000) is -4294967296 prior to the implicit conversion from long to int. Given that the truncation is presumably intentional (0 at least seems like the least-bad answer for rounding down 0 to a multiple of 2^32 as a 32-bit integer), you can suppress the warning with a cast.

Sorry, I didn't notice that the type of second parameter is based on __LP64__ (didn't scroll up...)

clang/lib/Sema/SemaChecking.cpp

 //===--- CHECK: Integer mixed-sign comparisons (-Wsign-compare) --------===//
 //===--- CHECK: Lossy implicit conversions (-Wconversion) --------------===//
 
 namespace {
 
 /// 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);
   }
 
   /// Returns the range of an opaque value of the given integral type.
   static IntRange forValueOfType(ASTContext &C, QualType T) {
     return forValueOfCanonicalType(C,
static IntRange forTargetOfCanonicalType(ASTContext &C, const Type *T) {
     const BuiltinType *BT = cast<BuiltinType>(T);
     assert(BT->isInteger());
 
     return IntRange(C.getIntWidth(QualType(T, 0)), BT->isUnsignedInteger());
   }
 
   /// 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);
   }
 };
 
 } // namespace
 
 static IntRange GetValueRange(ASTContext &C, llvm::APSInt &value,
                               unsigned MaxWidth) {
   if (value.isSigned() && value.isNegative())
static QualType GetExprType(const Expr *E) {
   if (const AtomicType *AtomicRHS = Ty->getAs<AtomicType>())
     Ty = AtomicRHS->getValueType();
   return Ty;
 }
 
 /// 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.
   Expr::EvalResult result;
   if (E->EvaluateAsRValue(result, C, InConstantContext))
     return GetValueRange(C, result.Val, GetExprType(E), MaxWidth);
 
   // I think we only want to look through implicit casts here; if the
   // user has an explicit widening cast, we should treat the value as
   // being of the new, wider type.
   if (const auto *CE = dyn_cast<ImplicitCastExpr>(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));
 
     bool isIntegerCast = CE->getCastKind() == CK_IntegralCast ||
                          CE->getCastKind() == CK_BooleanToSignedIntegral;
 
     // Assume that non-integer casts can span the full range of the type.
     if (!isIntegerCast)
       return OutputTypeRange;
 
     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)
       return OutputTypeRange;
 
     // Otherwise, we take the smaller width, and we're non-negative if
     // either the output type or the subexpr is.
     return IntRange(SubRange.Width,
                     SubRange.NonNegative || OutputTypeRange.NonNegative);
   }
 
   if (const auto *CO = dyn_cast<ConditionalOperator>(E)) {
     // If we can fold the condition, just take that operand.
     bool CondResult;
     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<BinaryOperator>(E)) {
+    IntRange (*Combine)(IntRange, IntRange) = IntRange::join;
+
     switch (BO->getOpcode()) {
     case BO_Cmp:
       llvm_unreachable("builtin <=> should have class type");
 
     // Boolean-valued operations are single-bit and positive.
     case BO_LAnd:
     case BO_LOr:
     case BO_LT:
if (const auto *BO = dyn_cast<BinaryOperator>(E)) {
     case BO_OrAssign:
       // TODO: bitfields?
       return IntRange::forValueOfType(C, GetExprType(E));
 
     // Simple assignments just pass through the RHS, which will have
     // 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:
     case BO_PtrMemI:
       return IntRange::forValueOfType(C, GetExprType(E));
 
     // 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:
       // ...except that we want to treat '1 << (blah)' as logically
       // positive.  It's an important idiom.
       if (IntegerLiteral *I
             = dyn_cast<IntegerLiteral>(BO->getLHS()->IgnoreParenCasts())) {
         if (I->getValue() == 1) {
           IntRange R = IntRange::forValueOfType(C, GetExprType(E));
           return IntRange(R.Width, /*NonNegative*/ true);
         }
       }
       LLVM_FALLTHROUGH;
 
     case BO_ShlAssign:
       return IntRange::forValueOfType(C, GetExprType(E));
 
     // 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.
       if (Optional<llvm::APSInt> shift =
               BO->getRHS()->getIntegerConstantExpr(C)) {
         if (shift->isNonNegative()) {
           unsigned zext = shift->getZExtValue();
           if (zext >= L.Width)
             L.Width = (L.NonNegative ? 0 : 1);
           else
             L.Width -= zext;
         }
       }
 
       return L;
     }
 
     // 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
     // of the LHS.
     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<llvm::APSInt> divisor =
               BO->getRHS()->getIntegerConstantExpr(C)) {
         unsigned log2 = divisor->logBase2(); // floor(log_2(divisor))
         if (log2 >= L.Width)
           L.Width = (L.NonNegative ? 0 : 1);
         else
           L.Width = std::min(L.Width - log2, MaxWidth);
         return L;
       }
 
       // 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<UnaryOperator>(E)) {
     switch (UO->getOpcode()) {
     // Boolean-valued operations are white-listed.
     case UO_LNot:
       return IntRange::forBoolType();
 
     // Operations with opaque sources are black-listed.
     case UO_Deref:
     case UO_AddrOf: // should be impossible
       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<OpaqueValueExpr>(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),
                     BitField->getType()->isUnsignedIntegerOrEnumerationType());
 
   return IntRange::forValueOfType(C, GetExprType(E));
 }
 
 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
 /// source semantics, has the same value when coerced through the
 /// target semantics.
 static bool IsSameFloatAfterCast(const llvm::APFloat &value,
                                  const llvm::fltSemantics &Src,
                                  const llvm::fltSemantics &Tgt) {
static bool CheckTautologicalComparison(Sema &S, BinaryOperator *E,
   //    the enumeration. In such a case, we should warn about the cast
   //    to enumeration type, not about the comparison.
   //  - If the constant is the maximum / minimum in-range value. For an
   //    enumeratin type, such comparisons can be meaningful and useful.
   if (Constant->getType()->isEnumeralType() &&
       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<AtomicType>())
     OtherT = AT->getValueType();
   IntRange OtherTypeRange = IntRange::forValueOfType(S.Context, OtherT);
 
   // Special case for ObjC BOOL on targets where its a typedef for a signed char
   // (Namely, macOS). FIXME: IntRange::forValueOfType should do this.
static void AnalyzeComparison(Sema &S, BinaryOperator *E) {
   } else if (RHS->getType()->hasSignedIntegerRepresentation()) {
     signedOperand = RHS;
     unsignedOperand = LHS;
   } else {
     return AnalyzeImpConvsInComparison(S, E);
   }
 
   // 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.
   AnalyzeImplicitConversions(S, LHS, E->getOperatorLoc());
   AnalyzeImplicitConversions(S, RHS, E->getOperatorLoc());
 
   // If the signed range is non-negative, -Wsign-compare won't fire.
   if (signedRange.NonNegative)
     return;
 
   // For (in)equality comparisons, if the unsigned operand is a
   // constant which cannot collide with a overflowed signed operand,
   // then reinterpreting the signed operand as unsigned will not
   // change the result of the comparison.
   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.
     assert(unsignedRange.NonNegative && "unsigned range includes negative?");
 
     if (unsignedRange.Width < comparisonWidth)
       return;
   }
static void CheckImplicitConversion(Sema &S, Expr *E, QualType T,
   }
 
   // If we are casting an integer type to a floating point type without
   // initialization-list syntax, we might lose accuracy if the floating
   // point type has a narrower significand than the integer type.
   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
     // target floating point type.
     unsigned int TargetPrecision = llvm::APFloatBase::semanticsPrecision(
         S.Context.getFloatTypeSemantics(QualType(TargetBT, 0)));
 
     if (SourcePrecision > 0 && TargetPrecision > 0 &&
static void CheckImplicitConversion(Sema &S, Expr *E, QualType T,
   if (isObjCSignedCharBool(S, T) && !Source->isCharType() &&
       !E->isKnownToHaveBooleanValue(/*Semantic=*/false)) {
     return adornObjCBoolConversionDiagWithTernaryFixit(
         S, E,
         S.Diag(CC, diag::warn_impcast_int_to_objc_signed_char_bool)
             << 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;
     if (E->EvaluateAsInt(Result, S.Context, Expr::SE_AllowSideEffects,
                          S.isConstantEvaluated())) {
       llvm::APSInt Value(32);
       Value = Result.Val.getInt();
 
       if (S.SourceMgr.isInSystemMacro(CC))
         return;
 
       std::string PrettySourceValue = Value.toString(10);
       std::string PrettyTargetValue = PrettyPrintInRange(Value, TargetRange);
 
       S.DiagRuntimeBehavior(
           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;
     }
 
     // People want to build with -Wshorten-64-to-32 and not -Wconversion.
     if (S.SourceMgr.isInSystemMacro(CC))
       return;
 
     if (TargetRange.Width == 32 && S.Context.getIntWidth(E->getType()) == 64)
       return DiagnoseImpCast(S, E, T, CC, diag::warn_impcast_integer_64_32,
                              /* pruneControlFlow */ true);
     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<UnaryOperator>(E))
       if (UO->getOpcode() == UO_Minus)
         if (Source->isUnsignedIntegerType()) {
           if (Target->isUnsignedIntegerType())
             return DiagnoseImpCast(S, E, T, CC,
                                    diag::warn_impcast_high_order_zero_bits);
           if (Target->isSignedIntegerType())
             return DiagnoseImpCast(S, E, T, CC,
                                    diag::warn_impcast_nonnegative_result);
         }
   }
 
-  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.
 
     Expr::EvalResult Result;
     if (E->EvaluateAsInt(Result, S.Context, Expr::SE_AllowSideEffects) &&
         !S.SourceMgr.isInSystemMacro(CC)) {
       llvm::APSInt Value = Result.Val.getInt();
       if (isSameWidthConstantConversion(S, E, T, CC)) {
         std::string PrettySourceValue = Value.toString(10);
         std::string PrettyTargetValue = PrettyPrintInRange(Value, TargetRange);
 
         S.DiagRuntimeBehavior(
             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;
       }
     }
 
     // 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;
 
     unsigned DiagID = diag::warn_impcast_integer_sign;
 
     // Traditionally, gcc has warned about this under -Wsign-compare.
     // We also want to warn about it in -Wconversion.
     // So if -Wconversion is off, use a completely identical diagnostic

clang/test/Sema/tautological-constant-compare.c

 // RUN: %clang_cc1 -triple x86_64-linux-gnu -fsyntax-only -Wtautological-constant-in-range-compare -DTEST=2 -verify %s
 // RUN: %clang_cc1 -triple x86_64-linux-gnu -fsyntax-only -Wtautological-constant-in-range-compare -DTEST=2 -verify -x c++ %s
 // RUN: %clang_cc1 -triple x86_64-linux-gnu -fsyntax-only -Wtautological-type-limit-compare -DTEST -verify %s
 // 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);
 
 #define macro(val) val
 
 #ifdef __cplusplus
 template<typename T>
 void TFunc() {
if (-32768L < s)
       return 0;
   if (-32768L <= s) // expected-warning {{comparison -32768 <= 'short' is always true}}
       return 0;
   if (-32768L > s) // expected-warning {{comparison -32768 > 'short' is always false}}
       return 0;
   if (-32768L >= s)
       return 0;
 #else
-  // expected-no-diagnostics
   if (s == 32767)
     return 0;
   if (s != 32767)
     return 0;
   if (s < 32767)
     return 0;
   if (s <= 32767)
     return 0;
if (65535UL < us) // expected-warning {{comparison 65535 < 'unsigned short' is always false}}
       return 0;
   if (65535UL <= us)
       return 0;
   if (65535UL > us)
       return 0;
   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)
       return 0;
   if (us < 65535)
       return 0;
   if (us <= 65535)
       return 0;
#if TEST == 2
   // expected-warning@#bitfield1 {{comparison of 3-bit signed value < 4 is always true}}
   // expected-warning@#bitfield2 {{comparison of 3-bit unsigned value < 8 is always true}}
   // expected-warning@#bitfield3 {{comparison of 3-bit signed value < 4 is always true}}
   // expected-warning@#bitfield4 {{comparison of 3-bit unsigned value < 8 is always true}}
 #endif
 
   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;
 }