[analyzer] Generalize bitwise OR rules for ranges

[vsavchenko]

Summary

Previously the current solver started reasoning about bitwise OR
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]

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

[xazax.hun]

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

77

Yeah, this is quite unfortunate. But you might end up calling this a lot for bitwise operations. I wonder if it is worth to solve this problem before commiting this patch. I do not insist though.

450

Is roughen part of a nomenclature? If not, what about something like cover?

480

Why do we need this conversion?
Do we want to model a cast in the code somewhere?
If so, I think this is more like a workaround and in the future we would need an explicit way to represent those cast operations. It might be worth to have a TODO.

[vsavchenko]

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

77

I was even thinking about fixing it myself, this shouldn't be very hard, Also addition of lower_bound and upper_bound can really help implementing Includes for RangeSet.

450

Yeah 😆 I spend quite some time thinking about a proper name for that one. It is used to be coarsen (yep, yuck!), but I don't really feel "cover" either. Mb something like "unify" will work? What do you think?

480

Those ranges that we inferred have nothing to do with upper operations. I mean, in theory, VisitBinaryOperator can take care of conversions, but I don't know how it can be done in the most generic way. In this particular situation, we really care that From and To don't change signs or something like that after conversion, but for other operators it might be not so important.

Answering the question of why we even need those, putting it simple - there is no other way, this is how APSInt works, couldn't do anything with values of different types (e.g. comparison).

I am totally on board with you on the inconvenience of the whole thing. Every implementer of the Visit* method should take care of conversions on their own. I would say that SValBuilder adding special symbolic values for this kind of casts, can be a solution.

[ASDenysPetrov]

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

77

Be aware as D77792 also implements such a method.

[NoQ]

Math looks good to me :)

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

450

Well, this is basically a one-dimensional convex hull...

But i do think that something like fillGaps() would be easier to understand.

480

Yeah i think this is correct. This is exactly how our symbolic expressions aren't type-safe: expression of type T corresponds to result of operations during which operand symbols were promoted to T.

[vsavchenko]

Fix few things here and there

[vsavchenko]

Fix clang-format issue

[vsavchenko]

Fix a bug with double expressions withing integer expressions

[vsavchenko]

Rebase

clang/include/clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h

const llvm::APSInt &Convert(const llvm::APSInt& To,
     if (TargetType == APSIntType(From))
       return From;
 
     return getValue(TargetType.convert(From));
   }
 
   const llvm::APSInt &Convert(QualType T, const llvm::APSInt &From) {
     APSIntType TargetType = getAPSIntType(T);
+    return Convert(TargetType, From);
+  }
+
+  const llvm::APSInt &Convert(APSIntType TargetType, const llvm::APSInt &From) {
     if (TargetType == APSIntType(From))
       return From;
 
     return getValue(TargetType.convert(From));
   }
 
   const llvm::APSInt &getIntValue(uint64_t X, bool isUnsigned) {
     QualType T = isUnsigned ? Ctx.UnsignedIntTy : Ctx.IntTy;
     return getValue(X, T);
   }
 
   const llvm::APSInt &getMaxValue(const llvm::APSInt &v) {
     return getValue(APSIntType(v).getMaxValue());
   }
 
   const llvm::APSInt &getMinValue(const llvm::APSInt &v) {
     return getValue(APSIntType(v).getMinValue());
   }
 
   const llvm::APSInt &getMaxValue(QualType T) {
-    return getValue(getAPSIntType(T).getMaxValue());
+    return getMaxValue(getAPSIntType(T));
   }
 
   const llvm::APSInt &getMinValue(QualType T) {
-    return getValue(getAPSIntType(T).getMinValue());
+    return getMinValue(getAPSIntType(T));
+  }
+
+  const llvm::APSInt &getMaxValue(APSIntType T) {
+    return getValue(T.getMaxValue());
+  }
+
+  const llvm::APSInt &getMinValue(APSIntType T) {
+    return getValue(T.getMinValue());
   }
 
   const llvm::APSInt &Add1(const llvm::APSInt &V) {
     llvm::APSInt X = V;
     ++X;
     return getValue(X);
   }
 

clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h

public:
 
   /// getConcreteValue - If a symbol is contrained to equal a specific integer
   ///  constant then this method returns that value.  Otherwise, it returns
   ///  NULL.
   const llvm::APSInt *getConcreteValue() const {
     return ranges.isSingleton() ? ranges.begin()->getConcreteValue() : nullptr;
   }
 
+  /// Get a minimal value covered by the ranges in the set
+  const llvm::APSInt &getMinValue() const;
+  /// Get a maximal value covered by the ranges in the set
+  const llvm::APSInt &getMaxValue() const;
+
 private:
   void IntersectInRange(BasicValueFactory &BV, Factory &F,
                         const llvm::APSInt &Lower, const llvm::APSInt &Upper,
                         PrimRangeSet &newRanges, PrimRangeSet::iterator &i,
                         PrimRangeSet::iterator &e) const;
 
-  const llvm::APSInt &getMinValue() const;
-
   bool pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const;
 
 public:
   RangeSet Intersect(BasicValueFactory &BV, Factory &F, llvm::APSInt Lower,
                      llvm::APSInt Upper) const;
   RangeSet Intersect(BasicValueFactory &BV, Factory &F,
                      const RangeSet &Other) const;
   RangeSet Negate(BasicValueFactory &BV, Factory &F) const;
 
   void print(raw_ostream &os) const;
 
   bool operator==(const RangeSet &other) const {
     return ranges == other.ranges;
   }
 };
 
-
 class ConstraintRange {};
 using ConstraintRangeTy = llvm::ImmutableMap<SymbolRef, RangeSet>;
 
 template <>
 struct ProgramStateTrait<ConstraintRange>
   : public ProgramStatePartialTrait<ConstraintRangeTy> {
   static void *GDMIndex();
 };

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

if (i->Includes(Lower)) {
       } else
         newRanges = F.add(newRanges, *i);
     }
   }
 }
 
 const llvm::APSInt &RangeSet::getMinValue() const {
   assert(!isEmpty());
-  return ranges.begin()->From();
+  return begin()->From();
+}
+
+const llvm::APSInt &RangeSet::getMaxValue() const {
+  assert(!isEmpty());
+  // NOTE: It's a shame that we can't implement 'getMaxValue' without scanning
+  //       the whole tree to get to the last element.
+  //       llvm::ImmutableSet should support decrement for 'end' iterators
+  //       or reverse order iteration.
+  auto It = begin();
+  for (auto End = end(); std::next(It) != End; ++It) {
+  }
+  return It->To();
 }
 
 bool RangeSet::pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const {
   if (isEmpty()) {
     // This range is already infeasible.
     return false;
   }
 
case BO_Or:
       return VisitOrOperator(LHS, RHS, T);
     case BO_And:
       return VisitAndOperator(LHS, RHS, T);
     default:
       return infer(T);
     }
   }
 
+  //===----------------------------------------------------------------------===//
+  //                         Ranges and operators
+  //===----------------------------------------------------------------------===//
+
+  /// Return a rough approximation of the given range set.
+  ///
+  /// For the range set:
+  ///   { [x_0, y_0], [x_1, y_1], ... , [x_N, y_N] }
+  /// it will return the range [x_0, y_N].
+  static Range fillGaps(RangeSet Origin) {
+    assert(!Origin.isEmpty());
+    return {Origin.getMinValue(), Origin.getMaxValue()};
+  }
+
+  /// Try to convert given range into the given type.
+  ///
+  /// It will return llvm::None only when the trivial conversion is possible.
+  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) {
-    // TODO: generalize for the ranged RHS.
-    if (const llvm::APSInt *RHSConstant = RHS.getConcreteValue()) {
-      // For unsigned types, the output is greater-or-equal than RHS.
-      if (T->isUnsignedIntegerType()) {
-        return LHS.Intersect(ValueFactory, RangeFactory, *RHSConstant,
-                             ValueFactory.getMaxValue(T));
-      }
+    // We should propagate information about unfeasbility of one of the
+    // operands to the resulting range.
+    if (LHS.isEmpty() || RHS.isEmpty()) {
+      return RangeFactory.getEmptySet();
 
-      // Bitwise-or with a non-zero constant is always non-zero.
-      const llvm::APSInt &Zero = ValueFactory.getAPSIntType(T).getZeroValue();
-      if (*RHSConstant != Zero) {
-        return assumeNonZero(LHS, T);
-      }
+    APSIntType ResultType = ValueFactory.getAPSIntType(T);
+    RangeSet DefaultRange = infer(T);
+
+    Range CoarseLHS = fillGaps(LHS);
+    Range CoarseRHS = fillGaps(RHS);
+
+    // 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;
+
+    llvm::APSInt Zero = ResultType.getZeroValue();
+
+    bool IsLHSPositiveOrZero = ConvertedCoarseLHS->From() >= Zero;
+    bool IsRHSPositiveOrZero = ConvertedCoarseRHS->From() >= Zero;
+
+    bool IsLHSNegative = ConvertedCoarseLHS->To() < Zero;
+    bool IsRHSNegative = ConvertedCoarseRHS->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());
+
+      // 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);
+
+      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);
     }
-    return infer(T);
+
+    // 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,

clang/test/Analysis/constant-folding.c

void testMixedTypeComparisons (char a, unsigned long b) {
   if (a != 0) return;
   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) {
+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 | 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 & -10) <= 10); // expected-warning{{UNKNOWN}}
 
   // Again, check for different argument order.
   clang_analyzer_eval((1 & a) <= 1); // expected-warning{{TRUE}}
 
-  unsigned int c = a;
-  c |= 1;
-  clang_analyzer_eval((c | 0) == 0); // expected-warning{{FALSE}}
+  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 | -2) == 0); // expected-warning{{FALSE}}
   clang_analyzer_eval((b | 10) == 0); // expected-warning{{FALSE}}
   clang_analyzer_eval((b | 0) == 0); // expected-warning{{UNKNOWN}}
-#ifdef ANALYZER_CM_Z3
   clang_analyzer_eval((b | -2) >= 0); // expected-warning{{FALSE}}
-#else
-  clang_analyzer_eval((b | -2) >= 0); // expected-warning{{UNKNOWN}}
-#endif
+
+  // 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}}
+
+    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}}
+    }
+
+    // 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}}
+  }
 
   // Check that dynamically computed constants also work.
   unsigned int constant = 1 << 3;
-  unsigned int d = a | constant;
-  clang_analyzer_eval(d >= constant); // expected-warning{{TRUE}}
+  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}}
   }
-  if (a < 10) {
-    clang_analyzer_eval((a | 20) >= 20); // expected-warning{{FALSE}}
-    clang_analyzer_eval((a | 20) < 20);  // expected-warning{{FALSE}}
-  }
 }