[analyzer] Generalize bitwise AND rules for ranges

[vsavchenko]

Summary

Previously the current solver started reasoning about bitwise AND
expressions only when one of the operands is a constant. However,
very similar logic could be applied to ranges. This commit addresses
this shortcoming. Additionally, it refines how we deal with negative
operands.

[vsavchenko]

Add parent change

[vsavchenko]

Here is a little proof I've put together (using Z3): https://gist.github.com/SavchenkoValeriy/2355170159ce1febd27498c36ea22149

[vsavchenko]

Rebase

[vsavchenko]

Rebase

[NoQ]

Looks correct, thanks!!

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

return VisitBinaryOperator(inferAs(Sym->getLHS(), ResultType),
                                Sym->getOpcode(),
                                inferAs(Sym->getRHS(), ResultType), ResultType);
   }
 
   RangeSet VisitBinaryOperator(RangeSet LHS, BinaryOperator::Opcode Op,
                                RangeSet RHS, QualType T) {
     switch (Op) {
     case BO_Or:
-      return VisitOrOperator(LHS, RHS, T);
+      return VisitBinaryOperator<BO_Or>(LHS, RHS, T);
     case BO_And:
-      return VisitAndOperator(LHS, RHS, T);
+      return VisitBinaryOperator<BO_And>(LHS, RHS, T);
     default:
       return infer(T);
     }
   }
 
   //===----------------------------------------------------------------------===//
   //                         Ranges and operators
   //===----------------------------------------------------------------------===//
llvm::Optional<Range> convert(const Range &Origin, APSIntType To) {
     if (To.testInRange(Origin.From(), false) != APSIntType::RTR_Within ||
         To.testInRange(Origin.To(), false) != APSIntType::RTR_Within) {
       return llvm::None;
     }
     return Range(ValueFactory.Convert(To, Origin.From()),
                  ValueFactory.Convert(To, Origin.To()));
   }
 
-  RangeSet VisitOrOperator(RangeSet LHS, RangeSet RHS, QualType T) {
+  template <BinaryOperator::Opcode Op>
+  RangeSet VisitBinaryOperator(RangeSet LHS, RangeSet RHS, QualType T) {
     // We should propagate information about unfeasbility of one of the
     // operands to the resulting range.
     if (LHS.isEmpty() || RHS.isEmpty()) {
       return RangeFactory.getEmptySet();
     }
 
-    APSIntType ResultType = ValueFactory.getAPSIntType(T);
-    RangeSet DefaultRange = infer(T);
-
     Range CoarseLHS = fillGaps(LHS);
     Range CoarseRHS = fillGaps(RHS);
 
+    APSIntType ResultType = ValueFactory.getAPSIntType(T);
+
     // We need to convert ranges to the resulting type, so we can compare values
     // and combine them in a meaningful (in terms of the given operation) way.
     auto ConvertedCoarseLHS = convert(CoarseLHS, ResultType);
     auto ConvertedCoarseRHS = convert(CoarseRHS, ResultType);
 
     // It is hard to reason about ranges when conversion changes
     // borders of the ranges.
     if (!ConvertedCoarseLHS || !ConvertedCoarseRHS) {
-      return DefaultRange;
+      return infer(T);
     }
 
-    llvm::APSInt Zero = ResultType.getZeroValue();
+    return VisitBinaryOperator<Op>(*ConvertedCoarseLHS, *ConvertedCoarseRHS, T);
+  }
+
+  template <BinaryOperator::Opcode Op>
+  RangeSet VisitBinaryOperator(Range LHS, Range RHS, QualType T) {
+    return infer(T);
+  }
+
+  /// Return a range set subtracting zero from \p Domain.
+  RangeSet assumeNonZero(RangeSet Domain, QualType T) {
+    APSIntType IntType = ValueFactory.getAPSIntType(T);
+    return Domain.Intersect(ValueFactory, RangeFactory,
+                            ++IntType.getZeroValue(), --IntType.getZeroValue());
+  }
+
+  // FIXME: Once SValBuilder supports unary minus, we should use SValBuilder to
+  //        obtain the negated symbolic expression instead of constructing the
+  //        symbol manually. This will allow us to support finding ranges of not
+  //        only negated SymSymExpr-type expressions, but also of other, simpler
+  //        expressions which we currently do not know how to negate.
+  const RangeSet *getRangeForMinusSymbol(ProgramStateRef State, SymbolRef Sym) {
+    if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(Sym)) {
+      if (SSE->getOpcode() == BO_Sub) {
+        QualType T = Sym->getType();
+        SymbolManager &SymMgr = State->getSymbolManager();
+        SymbolRef negSym =
+            SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub, SSE->getLHS(), T);
+
+        if (const RangeSet *negV = State->get<ConstraintRange>(negSym)) {
+          // Unsigned range set cannot be negated, unless it is [0, 0].
+          if (T->isUnsignedIntegerOrEnumerationType() ||
+              T->isSignedIntegerOrEnumerationType())
+            return negV;
+        }
+      }
+    }
+    return nullptr;
+  }
+
+  BasicValueFactory &ValueFactory;
+  RangeSet::Factory &RangeFactory;
+  ProgramStateRef State;
+};
+
+template <>
+RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_Or>(Range LHS, Range RHS,
+                                                           QualType T) {
+  APSIntType ResultType = ValueFactory.getAPSIntType(T);
 
-    bool IsLHSPositiveOrZero = ConvertedCoarseLHS->From() >= Zero;
-    bool IsRHSPositiveOrZero = ConvertedCoarseRHS->From() >= Zero;
+  bool IsLHSPositiveOrZero = LHS.From() >= Zero;
+  bool IsRHSPositiveOrZero = RHS.From() >= Zero;
 
-    bool IsLHSNegative = ConvertedCoarseLHS->To() < Zero;
-    bool IsRHSNegative = ConvertedCoarseRHS->To() < Zero;
+  bool IsLHSNegative = LHS.To() < Zero;
+  bool IsRHSNegative = RHS.To() < Zero;
 
-    // Check if both ranges have the same sign.
-    if ((IsLHSPositiveOrZero && IsRHSPositiveOrZero) ||
-        (IsLHSNegative && IsRHSNegative)) {
-      // The result is definitely greater or equal than any of the operands.
-      const llvm::APSInt &Min =
-          std::max(ConvertedCoarseLHS->From(), ConvertedCoarseRHS->From());
+    const llvm::APSInt &Min = std::max(LHS.From(), RHS.From());
 
-      // We estimate maximal value for positives as the maximal value for the
-      // given type.  For negatives, we estimate it with -1 (e.g. 0x11111111).
-      //
-      // TODO: We basically, limit the resulting range from below (in absolute
-      //       numbers), but don't do anything with the upper bound.
-      //       For positive operands, it can be done as follows: for the upper
-      //       bound of LHS and RHS we calculate the most significant bit set.
-      //       Let's call it the N-th bit.  Then we can estimate the maximal
-      //       number to be 2^(N+1)-1, i.e. the number with all the bits up to
-      //       the N-th bit set.
-      const llvm::APSInt &Max = IsLHSNegative
-                                    ? ValueFactory.getValue(--Zero)
-                                    : ValueFactory.getMaxValue(ResultType);
+    // TODO: We basically, limit the resulting range from below, but don't do
+    //       anything with the upper bound.
+    //
 
-      return {RangeFactory, ValueFactory.getValue(Min), Max};
-    }
 
-    // Otherwise, let's check if at least one of the operands is negative.
-    if (IsLHSNegative || IsRHSNegative) {
-      // This means that the result is definitely negative as well.
-      return {RangeFactory, ValueFactory.getMinValue(ResultType),
-              ValueFactory.getValue(--Zero)};
-    }
 
-    // It is pretty hard to reason about operands with different signs
-    // (and especially with possibly different signs).  We simply check if it
-    // can be zero.  In order to conclude that the result could not be zero,
-    // at least one of the operands should be definitely not zero itself.
-    if (!ConvertedCoarseLHS->Includes(Zero) ||
-        !ConvertedCoarseRHS->Includes(Zero)) {
-      return assumeNonZero(DefaultRange, T);
-    }
+  RangeSet DefaultRange = infer(T);
+
+  if (!LHS.Includes(Zero) || !RHS.Includes(Zero)) {
 
-    // Nothing much else to do here.
-    return DefaultRange;
-  }
 
-  RangeSet VisitAndOperator(RangeSet LHS, RangeSet RHS, QualType T) {
-    // TODO: generalize for the ranged RHS.
-    if (const llvm::APSInt *RHSConstant = RHS.getConcreteValue()) {
-      const llvm::APSInt &Zero = ValueFactory.getAPSIntType(T).getZeroValue();
-
-      // For unsigned types, or positive RHS,
-      // bitwise-and output is always smaller-or-equal than RHS (assuming two's
-      // complement representation of signed types).
-      if (T->isUnsignedIntegerType() || *RHSConstant >= Zero) {
-        return LHS.Intersect(ValueFactory, RangeFactory,
-                             ValueFactory.getMinValue(T), *RHSConstant);
-      }
-    }
-    return infer(T);
-  }
+template <>
+RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_And>(Range LHS,
+                                                            Range RHS,
+                                                            QualType T) {
+  APSIntType ResultType = ValueFactory.getAPSIntType(T);
+  llvm::APSInt Zero = ResultType.getZeroValue();
 
-  /// Return a range set subtracting zero from \p Domain.
-  RangeSet assumeNonZero(RangeSet Domain, QualType T) {
-    APSIntType IntType = ValueFactory.getAPSIntType(T);
-    return Domain.Intersect(ValueFactory, RangeFactory,
-                            ++IntType.getZeroValue(), --IntType.getZeroValue());
-  }
+  bool IsLHSPositiveOrZero = LHS.From() >= Zero;
+  bool IsRHSPositiveOrZero = RHS.From() >= Zero;
 
-  // FIXME: Once SValBuilder supports unary minus, we should use SValBuilder to
-  //        obtain the negated symbolic expression instead of constructing the
-  //        symbol manually. This will allow us to support finding ranges of not
-  //        only negated SymSymExpr-type expressions, but also of other, simpler
-  //        expressions which we currently do not know how to negate.
-  const RangeSet *getRangeForMinusSymbol(ProgramStateRef State, SymbolRef Sym) {
-    if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(Sym)) {
-      if (SSE->getOpcode() == BO_Sub) {
-        QualType T = Sym->getType();
-        SymbolManager &SymMgr = State->getSymbolManager();
-        SymbolRef negSym =
-            SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub, SSE->getLHS(), T);
+  bool IsLHSNegative = LHS.To() < Zero;
+  bool IsRHSNegative = RHS.To() < Zero;
 
-        if (const RangeSet *negV = State->get<ConstraintRange>(negSym)) {
-          // Unsigned range set cannot be negated, unless it is [0, 0].
-          if (T->isUnsignedIntegerOrEnumerationType() ||
-              T->isSignedIntegerOrEnumerationType())
-            return negV;
-        }
-      }
-    }
-    return nullptr;
+  // Check if both ranges have the same sign.
+  if ((IsLHSPositiveOrZero && IsRHSPositiveOrZero) ||
+      (IsLHSNegative && IsRHSNegative)) {
+    // The result is definitely less or equal than any of the operands.
+    const llvm::APSInt &Max = std::min(LHS.To(), RHS.To());
+
+    // We conservatively estimate lower bound to be the smallest positive
+    // or negative value corresponding to the sign of the operands.
+    const llvm::APSInt &Min = IsLHSNegative
+                                  ? ValueFactory.getMinValue(ResultType)
+                                  : ValueFactory.getValue(Zero);
+
+    return {RangeFactory, Min, Max};
+
+  // Otherwise, let's check if at least one of the operands is positive.
+  if (IsLHSPositiveOrZero || IsRHSPositiveOrZero) {
+    // This makes result definitely positive.
+    //
+    // We can also reason about a maximal value by finding the maximal
+    // value of the positive operand.
+    const llvm::APSInt &Max = IsLHSPositiveOrZero ? LHS.To() : RHS.To();
+
+    // The minimal value on the other hand is much harder to reason about.
+    // The only thing we know for sure is that the result is positive.
+    return {RangeFactory, ValueFactory.getValue(Zero),
+            ValueFactory.getValue(Max)};
   }
 
-  BasicValueFactory &ValueFactory;
-  RangeSet::Factory &RangeFactory;
-  ProgramStateRef State;
-};
+  // Nothing much else to do here.
+  return infer(T);
+}
 
 class RangeConstraintManager : public RangedConstraintManager {
 public:
   RangeConstraintManager(ExprEngine *EE, SValBuilder &SVB)
       : RangedConstraintManager(EE, SVB) {}
 
   //===------------------------------------------------------------------===//
   // Implementation for interface from ConstraintManager.

clang/test/Analysis/constant-folding.c

void testMixedTypeComparisons (char a, unsigned long b) {
   if (b != 0x100) return;
 
   clang_analyzer_eval(a <= b); // expected-warning{{TRUE}}
   clang_analyzer_eval(b >= a); // expected-warning{{TRUE}}
   clang_analyzer_eval(a != b); // expected-warning{{TRUE}}
 }
 
 void testBitwiseRules(unsigned int a, int b, int c) {
-  clang_analyzer_eval((a | 1) >= 1); // expected-warning{{TRUE}}
+  clang_analyzer_eval((a | 1) >= 1);   // expected-warning{{TRUE}}
   clang_analyzer_eval((a | -1) >= -1); // expected-warning{{TRUE}}
-  clang_analyzer_eval((a | 2) >= 2); // expected-warning{{TRUE}}
-  clang_analyzer_eval((a | 5) >= 5); // expected-warning{{TRUE}}
+  clang_analyzer_eval((a | 2) >= 2);   // expected-warning{{TRUE}}
+  clang_analyzer_eval((a | 5) >= 5);   // expected-warning{{TRUE}}
   clang_analyzer_eval((a | 10) >= 10); // expected-warning{{TRUE}}
 
   // Argument order should not influence this
   clang_analyzer_eval((1 | a) >= 1); // expected-warning{{TRUE}}
 
-  clang_analyzer_eval((a & 1) <= 1); // expected-warning{{TRUE}}
-  clang_analyzer_eval((a & 2) <= 2); // expected-warning{{TRUE}}
-  clang_analyzer_eval((a & 5) <= 5); // expected-warning{{TRUE}}
-  clang_analyzer_eval((a & 10) <= 10); // expected-warning{{TRUE}}
+  clang_analyzer_eval((a & 1) <= 1);    // expected-warning{{TRUE}}
+  clang_analyzer_eval((a & 1) >= 0);    // expected-warning{{TRUE}}
+  clang_analyzer_eval((a & 2) <= 2);    // expected-warning{{TRUE}}
+  clang_analyzer_eval((a & 5) <= 5);    // expected-warning{{TRUE}}
+  clang_analyzer_eval((a & 10) <= 10);  // expected-warning{{TRUE}}
   clang_analyzer_eval((a & -10) <= 10); // expected-warning{{UNKNOWN}}
 
   // Again, check for different argument order.
   clang_analyzer_eval((1 & a) <= 1); // expected-warning{{TRUE}}
 
   unsigned int d = a;
   d |= 1;
   clang_analyzer_eval((d | 0) == 0); // expected-warning{{FALSE}}
 
   // Rules don't apply to signed typed, as the values might be negative.
   clang_analyzer_eval((b | 1) > 0); // expected-warning{{UNKNOWN}}
 
   // Even for signed values, bitwise OR with a non-zero is always non-zero.
-  clang_analyzer_eval((b | 1) == 0); // expected-warning{{FALSE}}
+  clang_analyzer_eval((b | 1) == 0);  // expected-warning{{FALSE}}
   clang_analyzer_eval((b | -2) == 0); // expected-warning{{FALSE}}
   clang_analyzer_eval((b | 10) == 0); // expected-warning{{FALSE}}
-  clang_analyzer_eval((b | 0) == 0); // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval((b | 0) == 0);  // expected-warning{{UNKNOWN}}
   clang_analyzer_eval((b | -2) >= 0); // expected-warning{{FALSE}}
 
   // Check that we can operate with negative ranges
   if (b < 0) {
     clang_analyzer_eval((b | -1) == -1);   // expected-warning{{TRUE}}
     clang_analyzer_eval((b | -10) >= -10); // expected-warning{{TRUE}}
+    clang_analyzer_eval((b & 0) == 0);     // expected-warning{{TRUE}}
+    clang_analyzer_eval((b & -10) <= -10); // expected-warning{{TRUE}}
+    clang_analyzer_eval((b & 5) >= 0);     // expected-warning{{TRUE}}
 
     int e = (b | -5);
     clang_analyzer_eval(e >= -5 && e <= -1); // expected-warning{{TRUE}}
 
     if (b < -20) {
-      clang_analyzer_eval((b | e) >= -5); // expected-warning{{TRUE}}
+      clang_analyzer_eval((b | e) >= -5);    // expected-warning{{TRUE}}
+      clang_analyzer_eval((b & -10) < -20);  // expected-warning{{TRUE}}
+      clang_analyzer_eval((b & e) < -20);    // expected-warning{{TRUE}}
+      clang_analyzer_eval((b & -30) <= -30); // expected-warning{{TRUE}}
+
+      if (c >= -30 && c <= -10) {
+        clang_analyzer_eval((b & c) <= -20); // expected-warning{{TRUE}}
+      }
+    }
+
+    if (a <= 40) {
+      int g = (int)a & b;
+      clang_analyzer_eval(g <= 40 && g >= 0); // expected-warning{{TRUE}}
     }
 
     // Check that we can reason about the result even if know nothing
     // about one of the operands.
     clang_analyzer_eval((b | c) != 0); // expected-warning{{TRUE}}
   }
 
   if (a <= 30 && b >= 10 && c >= 20) {
     // Check that we can reason about non-constant operands.
     clang_analyzer_eval((b | c) >= 20); // expected-warning{{TRUE}}
 
     // Check that we can reason about the resulting range even if
     // the types are not the same, but we still can convert operand
     // ranges.
     clang_analyzer_eval((a | b) >= 10); // expected-warning{{TRUE}}
+    clang_analyzer_eval((a & b) <= 30); // expected-warning{{TRUE}}
+
+    if (b <= 20) {
+      clang_analyzer_eval((a & b) <= 20); // expected-warning{{TRUE}}
+    }
   }
 
   // Check that dynamically computed constants also work.
   unsigned int constant = 1 << 3;
   unsigned int f = a | constant;
   clang_analyzer_eval(f >= constant); // expected-warning{{TRUE}}
 
   // Check that nested expressions also work.
   clang_analyzer_eval(((a | 10) | 5) >= 10); // expected-warning{{TRUE}}
 
   if (a < 10) {
     clang_analyzer_eval((a | 20) >= 20); // expected-warning{{TRUE}}
   }
 
-  // TODO: We misuse intersection of ranges for bitwise AND and OR operators.
-  //       Resulting ranges for the following cases are infeasible.
-  //       This is what causes paradoxical results below.
   if (a > 10) {
-    clang_analyzer_eval((a & 1) <= 1); // expected-warning{{FALSE}}
-    clang_analyzer_eval((a & 1) > 1);  // expected-warning{{FALSE}}
+    clang_analyzer_eval((a & 1) <= 1); // expected-warning{{TRUE}}
   }
 }

clang/test/Analysis/switch-case.c

void testConstant() {
   case 1 ... 5:
     clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
     break;
   default:
     clang_analyzer_warnIfReached(); // no-warning
     break;
   }
 }
+
+void testExhaustiveSwitch(unsigned int a) {
+  switch (a & 5) {
+  case 0 ... 5:
+    clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+    break;
+  default:
+    clang_analyzer_warnIfReached(); // no-warning
+    break;
+  }
+}

clang/test/Analysis/uninit-exhaustive-switch-bug.c

+// RUN: %clang_analyze_cc1 -analyzer-checker=core -verify %s
+
+// rdar://problem/54359410
+// expected-no-diagnostics
+
+int rand();
+
+void test() {
+  int offset = 0;
+  int value;
+  int test = rand();
+  switch (test & 0x1) {
+  case 0:
+  case 1:
+    value = 0;
+    break;
+  }
+
+  offset += value; // no-warning
+}