Unify implementation of our two different flavours of -Wtautological-compare.

In so doing, fix a handful of remaining bugs where we would report false
positives or false negatives if we promote a signed value to an unsigned type
for the comparison.

llvm-svn: 320122

1 files changed, 155 insertions, 145 deletions

diff --git a/clang/lib/Sema/SemaChecking.cpp b/clang/lib/Sema/SemaChecking.cpp
index d0017da..c5e4f26 100644
--- a/clang/lib/Sema/SemaChecking.cpp
+++ b/clang/lib/Sema/SemaChecking.cpp
@@ -8662,54 +8662,113 @@ static bool isKnownToHaveUnsignedValue(Expr *E) {
 }
 
 namespace {
+/// The promoted range of values of a type. In general this has the
+/// following structure:
+///
+///     |-----------| . . . |-----------|
+///     ^           ^       ^           ^
+///    Min       HoleMin  HoleMax      Max
+///
+/// ... where there is only a hole if a signed type is promoted to unsigned
+/// (in which case Min and Max are the smallest and largest representable
+/// values).
+struct PromotedRange {
+  // Min, or HoleMax if there is a hole.
+  llvm::APSInt PromotedMin;
+  // Max, or HoleMin if there is a hole.
+  llvm::APSInt PromotedMax;
+
+  PromotedRange(IntRange R, unsigned BitWidth, bool Unsigned) {
+    if (R.Width == 0)
+      PromotedMin = PromotedMax = llvm::APSInt(BitWidth, Unsigned);
+    else {
+      PromotedMin = llvm::APSInt::getMinValue(R.Width, R.NonNegative)
+                        .extOrTrunc(BitWidth);
+      PromotedMin.setIsUnsigned(Unsigned);
 
-enum class LimitType {
-  Max = 1U << 0U,  // e.g. 32767 for short
-  Min = 1U << 1U,  // e.g. -32768 for short
-  Both = Max | Min // When the value is both the Min and the Max limit at the
-                   // same time; e.g. in C++, A::a in enum A { a = 0 };
-};
+      PromotedMax = llvm::APSInt::getMaxValue(R.Width, R.NonNegative)
+                        .extOrTrunc(BitWidth);
+      PromotedMax.setIsUnsigned(Unsigned);
+    }
+  }
 
-} // namespace
+  // Determine whether this range is contiguous (has no hole).
+  bool isContiguous() const { return PromotedMin <= PromotedMax; }
 
-/// Checks whether Expr 'Constant' may be the
-/// std::numeric_limits<>::max() or std::numeric_limits<>::min()
-/// of the Expr 'Other'. If true, then returns the limit type (min or max).
-/// The Value is the evaluation of Constant
-static llvm::Optional<LimitType> IsTypeLimit(Sema &S, Expr *Constant,
-                                             Expr *Other,
-                                             const llvm::APSInt &Value) {
-  if (IsEnumConstOrFromMacro(S, Constant))
-    return llvm::Optional<LimitType>();
+  // Where a constant value is within the range.
+  enum ComparisonResult {
+    LT = 0x1,
+    LE = 0x2,
+    GT = 0x4,
+    GE = 0x8,
+    EQ = 0x10,
+    NE = 0x20,
+    InRangeFlag = 0x40,
 
-  if (isKnownToHaveUnsignedValue(Other) && Value == 0)
-    return LimitType::Min;
+    Less = LE | LT | NE,
+    Min = LE | InRangeFlag,
+    InRange = InRangeFlag,
+    Max = GE | InRangeFlag,
+    Greater = GE | GT | NE,
 
-  // TODO: Investigate using GetExprRange() to get tighter bounds
-  // on the bit ranges.
-  QualType OtherT = Other->IgnoreParenImpCasts()->getType();
-  if (const auto *AT = OtherT->getAs<AtomicType>())
-    OtherT = AT->getValueType();
-
-  IntRange OtherRange = IntRange::forValueOfType(S.Context, OtherT);
-  if (Other->isKnownToHaveBooleanValue())
-    OtherRange = IntRange::forBoolType();
-
-  // Special-case for C++ for enum with one enumerator with value of 0.
-  if (OtherRange.Width == 0)
-    return Value == 0 ? LimitType::Both : llvm::Optional<LimitType>();
+    OnlyValue = LE | GE | EQ | InRangeFlag,
+    InHole = NE
+  };
 
-  if (llvm::APSInt::isSameValue(
-          llvm::APSInt::getMaxValue(OtherRange.Width, OtherRange.NonNegative),
-          Value))
-    return LimitType::Max;
+  ComparisonResult compare(const llvm::APSInt &Value) const {
+    assert(Value.getBitWidth() == PromotedMin.getBitWidth() &&
+           Value.isUnsigned() == PromotedMin.isUnsigned());
+    if (!isContiguous()) {
+      assert(Value.isUnsigned() && "discontiguous range for signed compare");
+      if (Value.isMinValue()) return Min;
+      if (Value.isMaxValue()) return Max;
+      if (Value >= PromotedMin) return InRange;
+      if (Value <= PromotedMax) return InRange;
+      return InHole;
+    }
+
+    switch (llvm::APSInt::compareValues(Value, PromotedMin)) {
+    case -1: return Less;
+    case 0: return PromotedMin == PromotedMax ? OnlyValue : Min;
+    case 1:
+      switch (llvm::APSInt::compareValues(Value, PromotedMax)) {
+      case -1: return InRange;
+      case 0: return Max;
+      case 1: return Greater;
+      }
+    }
 
-  if (llvm::APSInt::isSameValue(
-          llvm::APSInt::getMinValue(OtherRange.Width, OtherRange.NonNegative),
-          Value))
-    return LimitType::Min;
+    llvm_unreachable("impossible compare result");
+  }
 
-  return llvm::None;
+  static llvm::Optional<bool> constantValue(BinaryOperatorKind Op,
+                                            ComparisonResult R,
+                                            bool ConstantOnRHS) {
+    ComparisonResult TrueFlag, FalseFlag;
+    if (Op == BO_EQ) {
+      TrueFlag = EQ;
+      FalseFlag = NE;
+    } else if (Op == BO_NE) {
+      TrueFlag = NE;
+      FalseFlag = EQ;
+    } else {
+      if ((Op == BO_LT || Op == BO_GE) ^ ConstantOnRHS) {
+        TrueFlag = LT;
+        FalseFlag = GE;
+      } else {
+        TrueFlag = GT;
+        FalseFlag = LE;
+      }
+      if (Op == BO_GE || Op == BO_LE)
+        std::swap(TrueFlag, FalseFlag);
+    }
+    if (R & TrueFlag)
+      return true;
+    if (R & FalseFlag)
+      return false;
+    return llvm::None;
+  }
+};
 }
 
 static bool HasEnumType(Expr *E) {
@@ -8747,28 +8806,46 @@ static bool CheckTautologicalComparison(Sema &S, BinaryOperator *E,
   if (S.inTemplateInstantiation() || !E->isRelationalOp())
     return false;
 
-  BinaryOperatorKind Op = E->getOpcode();
-
-  QualType OType = Other->IgnoreParenImpCasts()->getType();
-  if (!OType->isIntegerType())
+  if (IsEnumConstOrFromMacro(S, Constant))
     return false;
 
-  // Determine which limit (min/max) the constant is, if either.
-  llvm::Optional<LimitType> ValueType = IsTypeLimit(S, Constant, Other, Value);
-  if (!ValueType)
-    return false;
+  Expr *OriginalOther = Other;
 
-  bool ConstIsLowerBound = (Op == BO_LT || Op == BO_LE) ^ RhsConstant;
-  bool ResultWhenConstEqualsOther = (Op == BO_LE || Op == BO_GE);
-  if (ValueType != LimitType::Both) {
-    bool ResultWhenConstNeOther =
-        ConstIsLowerBound ^ (ValueType == LimitType::Max);
-    if (ResultWhenConstEqualsOther != ResultWhenConstNeOther)
-      return false; // The comparison is not tautological.
-  } else if (ResultWhenConstEqualsOther == ConstIsLowerBound)
-    return false; // The comparison is not tautological.
+  Constant = Constant->IgnoreParenImpCasts();
+  Other = Other->IgnoreParenImpCasts();
 
-  const bool Result = ResultWhenConstEqualsOther;
+  // TODO: Investigate using GetExprRange() to get tighter bounds
+  // on the bit ranges.
+  QualType OtherT = Other->getType();
+  if (const auto *AT = OtherT->getAs<AtomicType>())
+    OtherT = AT->getValueType();
+  IntRange OtherRange = IntRange::forValueOfType(S.Context, OtherT);
+
+  // Whether we're treating Other as being a bool because of the form of
+  // expression despite it having another type (typically 'int' in C).
+  bool OtherIsBooleanDespiteType =
+      !OtherT->isBooleanType() && Other->isKnownToHaveBooleanValue();
+  if (OtherIsBooleanDespiteType)
+    OtherRange = IntRange::forBoolType();
+
+  if (FieldDecl *Bitfield = Other->getSourceBitField())
+    if (!Bitfield->getBitWidth()->isValueDependent())
+      OtherRange.Width =
+          std::min(Bitfield->getBitWidthValue(S.Context), OtherRange.Width);
+
+  // Check whether the constant value can be represented in OtherRange. Bail
+  // out if so; this isn't an out-of-range comparison.
+  PromotedRange OtherPromotedRange(OtherRange, Value.getBitWidth(),
+                                   Value.isUnsigned());
+
+  auto Cmp = OtherPromotedRange.compare(Value);
+  if (Cmp != PromotedRange::Min && Cmp != PromotedRange::Max &&
+      Cmp != PromotedRange::OnlyValue)
+    return false;
+
+  auto Result = PromotedRange::constantValue(E->getOpcode(), Cmp, RhsConstant);
+  if (!Result)
+    return false;
 
   // Should be enough for uint128 (39 decimal digits)
   SmallString<64> PrettySourceValue;
@@ -8782,20 +8859,20 @@ static bool CheckTautologicalComparison(Sema &S, BinaryOperator *E,
     S.DiagRuntimeBehavior(
       E->getOperatorLoc(), E,
       S.PDiag(diag::warn_tautological_bool_compare)
-          << OS.str() << classifyConstantValue(Constant->IgnoreParenImpCasts())
-          << OType << !OType->isBooleanType() << Result
+          << OS.str() << classifyConstantValue(Constant)
+          << OtherT << !OtherT->isBooleanType() << *Result
           << E->getLHS()->getSourceRange() << E->getRHS()->getSourceRange());
     return true;
   }
 
-  unsigned Diag = (isKnownToHaveUnsignedValue(Other) && Value == 0)
-                      ? (HasEnumType(Other)
+  unsigned Diag = (isKnownToHaveUnsignedValue(OriginalOther) && Value == 0)
+                      ? (HasEnumType(OriginalOther)
                              ? diag::warn_unsigned_enum_always_true_comparison
                              : diag::warn_unsigned_always_true_comparison)
                       : diag::warn_tautological_constant_compare;
 
   S.Diag(E->getOperatorLoc(), Diag)
-      << RhsConstant << OType << E->getOpcodeStr() << OS.str() << Result
+      << RhsConstant << OtherT << E->getOpcodeStr() << OS.str() << *Result
       << E->getLHS()->getSourceRange() << E->getRHS()->getSourceRange();
 
   return true;
@@ -8817,7 +8894,6 @@ static bool DiagnoseOutOfRangeComparison(Sema &S, BinaryOperator *E,
   QualType OtherT = Other->getType();
   if (const auto *AT = OtherT->getAs<AtomicType>())
     OtherT = AT->getValueType();
-
   IntRange OtherRange = IntRange::forValueOfType(S.Context, OtherT);
 
   // Whether we're treating Other as being a bool because of the form of
@@ -8827,91 +8903,25 @@ static bool DiagnoseOutOfRangeComparison(Sema &S, BinaryOperator *E,
   if (OtherIsBooleanDespiteType)
     OtherRange = IntRange::forBoolType();
 
-  unsigned OtherWidth = OtherRange.Width;
-
-  BinaryOperatorKind op = E->getOpcode();
-  bool IsTrue = true;
+  if (FieldDecl *Bitfield = Other->getSourceBitField())
+    if (!Bitfield->getBitWidth()->isValueDependent())
+      OtherRange.Width =
+          std::min(Bitfield->getBitWidthValue(S.Context), OtherRange.Width);
 
   // Check whether the constant value can be represented in OtherRange. Bail
   // out if so; this isn't an out-of-range comparison.
-  {
-    QualType ConstantT = Constant->getType();
-    QualType CommonT = E->getLHS()->getType();
-
-    if (S.Context.hasSameUnqualifiedType(OtherT, ConstantT) &&
-        !OtherIsBooleanDespiteType)
-      return false;
-    assert((OtherT->isIntegerType() && ConstantT->isIntegerType()) &&
-           "comparison with non-integer type");
-
-    bool ConstantSigned = ConstantT->isSignedIntegerType();
-    bool CommonSigned = CommonT->isSignedIntegerType();
-
-    bool EqualityOnly = false;
-
-    if (CommonSigned) {
-      // The common type is signed, therefore no signed to unsigned conversion.
-      if (!OtherRange.NonNegative) {
-        // Check that the constant is representable in type OtherT.
-        if (ConstantSigned) {
-          if (OtherWidth >= Value.getMinSignedBits())
-            return false;
-        } else { // !ConstantSigned
-          if (OtherWidth >= Value.getActiveBits() + 1)
-            return false;
-        }
-      } else { // !OtherSigned
-               // Check that the constant is representable in type OtherT.
-        // Negative values are out of range.
-        if (ConstantSigned) {
-          if (Value.isNonNegative() && OtherWidth >= Value.getActiveBits())
-            return false;
-        } else { // !ConstantSigned
-          if (OtherWidth >= Value.getActiveBits())
-            return false;
-        }
-      }
-    } else { // !CommonSigned
-      if (OtherRange.NonNegative) {
-        if (OtherWidth >= Value.getActiveBits())
-          return false;
-      } else { // OtherSigned
-        assert(!ConstantSigned &&
-               "Two signed types converted to unsigned types.");
-        // Check to see if the constant is representable in OtherT.
-        if (OtherWidth > Value.getActiveBits())
-          return false;
-        // Check to see if the constant is equivalent to a negative value
-        // cast to CommonT.
-        if (S.Context.getIntWidth(ConstantT) ==
-                S.Context.getIntWidth(CommonT) &&
-            Value.isNegative() && Value.getMinSignedBits() <= OtherWidth)
-          return false;
-        // The constant value rests between values that OtherT can represent
-        // after conversion.  Relational comparison still works, but equality
-        // comparisons will be tautological.
-        EqualityOnly = true;
-      }
-    }
+  PromotedRange OtherPromotedRange(OtherRange, Value.getBitWidth(),
+                                   Value.isUnsigned());
+  auto Cmp = OtherPromotedRange.compare(Value);
 
-    bool PositiveConstant = !ConstantSigned || Value.isNonNegative();
+  // If Value is in the range of possible Other values, this comparison is not
+  // tautological.
+  if (Cmp & PromotedRange::InRangeFlag)
+    return false;
 
-    if (op == BO_EQ || op == BO_NE) {
-      IsTrue = op == BO_NE;
-    } else if (EqualityOnly) {
-      return false;
-    } else if (RhsConstant) {
-      if (op == BO_GT || op == BO_GE)
-        IsTrue = !PositiveConstant;
-      else // op == BO_LT || op == BO_LE
-        IsTrue = PositiveConstant;
-    } else {
-      if (op == BO_LT || op == BO_LE)
-        IsTrue = !PositiveConstant;
-      else // op == BO_GT || op == BO_GE
-        IsTrue = PositiveConstant;
-    }
-  }
+  auto IsTrue = PromotedRange::constantValue(E->getOpcode(), Cmp, RhsConstant);
+  if (!IsTrue)
+    return false;
 
   // If this is a comparison to an enum constant, include that
   // constant in the diagnostic.
@@ -8930,7 +8940,7 @@ static bool DiagnoseOutOfRangeComparison(Sema &S, BinaryOperator *E,
     E->getOperatorLoc(), E,
     S.PDiag(diag::warn_out_of_range_compare)
         << OS.str() << classifyConstantValue(Constant)
-        << OtherT << OtherIsBooleanDespiteType << IsTrue
+        << OtherT << OtherIsBooleanDespiteType << *IsTrue
         << E->getLHS()->getSourceRange() << E->getRHS()->getSourceRange());
 
    return true;