[analyzer] Refactor range inference for symbolic expressions

[vsavchenko]

Summary

This change introduces a new component to unite all of the reasoning
we have about operations on ranges in the analyzer's solver.
In many cases, we might conclude that the range for a symbolic operation
is much more narrow than the type implies. While reasoning about
runtime conditions (especially in loops), we need to support more and
more of those little pieces of logic. The new component mostly plays
a role of an organizer for those, and allows us to focus on the actual
reasoning about ranges and not dispatching manually on the types of the
nested symbolic expressions.

[NoQ]

Very nice, i like this architecture.

@baloghadamsoftware @steakhal @ASDenysPetrov will you be able to plug D49074/D50256/D77792/D77802/D78933 into this so that to separate algebra from pattern-matching and ensure no performance regressions? Or is something still missing?

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

321–331

Can we replace these three with a single VisitBinarySymExpr()? Or is there too much template duck typing involved?

390–395

I think this is a must-have, at least in some form. We've been exploding like this before on real-world code, well, probably not with bitwise ops but i'm still worried.

[vsavchenko]

Very nice, i like this architecture.

Aww, thanks 😊

@baloghadamsoftware @steakhal @ASDenysPetrov will you be able to plug D49074/D50256/D77792/D77802/D78933 into this so that to separate algebra from pattern-matching and ensure no performance regressions? Or is something still missing?

Yeah, I'll be happy to hear what will be good to have for all the different cases we have and might have in the future.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

321–331

Unfortunately no, we need to know more derived types in order to use getLHS and getRHS methods. And that's why VisitBinaryOperator function is a template.

390–395

It will be pretty easy to introduce a limit on how deep we go into a tree of the given symbolic expression. That can also be a solution.

[ASDenysPetrov]

In D79232#2016065, @NoQ wrote:

@baloghadamsoftware @steakhal @ASDenysPetrov will you be able to plug D49074/D50256/D77792/D77802/D78933 into this so that to separate algebra from pattern-matching and ensure no performance regressions? Or is something still missing?

Sure. I'll plug my changes D77802/D78933 as soon as this patch is available in the master.

[NoQ]

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

390–395

I mean, doing something super trivial, like defining a map from symexprs to ranges in SymbolicRangeInferrer itself and find-or-inserting into it, will probably not be harder than counting depth(?)

[vsavchenko]

Now getRange is more likely to return unfeasible range. Calling Intersect and pin methods from such ranges might cause a crash.
Check for unfeasible ranges.

[NoQ]

clang/test/Analysis/constant-folding.c

127–128

How can both of these be false? o.o

[xazax.hun]

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

390–395

I am a bit ignorant of this topic, but I wonder what a good caching mechanism would look like.
A simple symexpr -> range mapping does not feel right as the same symexpr might have a different range in a different program state (e.g., we might learn new ranges for our symbols). But having a separate map for each state state might do relatively little caching?

[xazax.hun]

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

430

I always get surprised when I read code like the one above seeing that only RHS is tested for being a concerte value. Later on, I vaguely start to remember that we only produce SymIntExprs (is that correct?). I wonder if we should add an assert so this code blows up when someone is trying to add IntSymExprs, so she will know what code needs modification.

[vsavchenko]

Add clarification on infeasible ranges in bitwise tests

[vsavchenko]

clang/test/Analysis/constant-folding.c

127–128

Yeah :) I realized how weird it is.
Anything is possible in the land of infeasible ranges.

I changed a comment there to address this

[NoQ]

clang/test/Analysis/constant-folding.c

127–128

I mean, this pretty much never happened before. How are you not tripping on this assert? (probably it's simply been disabled in normal debug builds now that it's under "expensive checks")

The correct thing to do is to detect the paradox earlier and mark the path as infeasible. What prevents us from doing it right away here?

[vsavchenko]

clang/test/Analysis/constant-folding.c

127–128

Before we didn't really care about constraints on the operands and I changed it :)
So, now Intersect (which is logically not a correct way to do what is meant) can cause this type of behaviour

[NoQ]

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

390–395

Even a simple symexpr -> range mapping with lifetime of SymbolicRangeInferrer should be able to improve algorithmic complexity dramatically. And it doesn't need to consider different states because it only lives for the duration of a single assume() operation.

clang/test/Analysis/constant-folding.c

127–128

[visible confusion]

Could you elaborate? I see that only constraint so far is $a: [11; UINT_MAX]. I don't see any infeasible ranges here. (a & 1) <= 1 is clearly true. If we were previously thinking that it's unknown and now we think that it's false, then it's a regression.

[vsavchenko]

clang/test/Analysis/constant-folding.c

127–128

a is indeed [11, UINT_MAX].
Current implementation checks a constant (i.e. 1) and intersects the range for LHS [11, UINT_MAX] with [UINT_MIN, 1], which produces empty range set (aka infeasible).

This is why I'm saying that intersection is a bad choice, it's even plain wrong.
Before this patch we ignored constraints for a and considered it to be [UINT_MIN, UINT_MAX]. In that setting, intersection does indeed work (which doesn't make it correct).

Yes, it is a regression. I'm changing this implementation in the child revisions.

[NoQ]

clang/test/Analysis/constant-folding.c

127–128

Yes, it is a regression. I'm changing this implementation in the child revisions.

Oh, right, got it :D

Ok, let's land 'em together then!

[vsavchenko]

Fix a problem with doubles sneaking into integer symbolic expressions

[vsavchenko]

Rebase

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

 /// guarantee that from <= to.  Note that Range is immutable, so as not
 /// to subvert RangeSet's immutability.
 class Range : public std::pair<const llvm::APSInt *, const llvm::APSInt *> {
 public:
   Range(const llvm::APSInt &from, const llvm::APSInt &to)
       : std::pair<const llvm::APSInt *, const llvm::APSInt *>(&from, &to) {
     assert(from <= to);
   }
+
+  Range(const llvm::APSInt &point)
+      : std::pair<const llvm::APSInt *, const llvm::APSInt *>(&point, &point) {}
+
   bool Includes(const llvm::APSInt &v) const {
     return *first <= v && v <= *second;
   }
   const llvm::APSInt &From() const { return *first; }
   const llvm::APSInt &To() const { return *second; }
   const llvm::APSInt *getConcreteValue() const {
     return &From() == &To() ? &From() : nullptr;
   }
public:
   iterator end() const { return ranges.end(); }
 
   bool isEmpty() const { return ranges.isEmpty(); }
 
   /// Construct a new RangeSet representing '{ [from, to] }'.
   RangeSet(Factory &F, const llvm::APSInt &from, const llvm::APSInt &to)
       : ranges(F.add(F.getEmptySet(), Range(from, to))) {}
 
+  /// Construct a new RangeSet representing the given point as a range.
+  RangeSet(Factory &F, const llvm::APSInt &point) : RangeSet(F, point, point) {}
+
   /// Profile - Generates a hash profile of this RangeSet for use
   ///  by FoldingSet.
   void Profile(llvm::FoldingSetNodeID &ID) const { ranges.Profile(ID); }
 
   /// 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 {

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/Basic/JsonSupport.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SValVisitor.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/ImmutableSet.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace clang;
 using namespace ento;
 
+//===----------------------------------------------------------------------===//
+//                           RangeSet implementation
+//===----------------------------------------------------------------------===//
+
 void RangeSet::IntersectInRange(BasicValueFactory &BV, Factory &F,
-                      const llvm::APSInt &Lower, const llvm::APSInt &Upper,
-                      PrimRangeSet &newRanges, PrimRangeSet::iterator &i,
+                                const llvm::APSInt &Lower,
+                                const llvm::APSInt &Upper,
+                                PrimRangeSet &newRanges,
+                                PrimRangeSet::iterator &i,
                                 PrimRangeSet::iterator &e) const {
   // There are six cases for each range R in the set:
   //   1. R is entirely before the intersection range.
   //   2. R is entirely after the intersection range.
   //   3. R contains the entire intersection range.
   //   4. R starts before the intersection range and ends in the middle.
   //   5. R starts in the middle of the intersection range and ends after it.
   //   6. R is entirely contained in the intersection range.
   // These correspond to each of the conditions below.

 }
 
 const llvm::APSInt &RangeSet::getMinValue() const {
   assert(!isEmpty());
   return ranges.begin()->From();
 }
 
 bool RangeSet::pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const {
+  if (isEmpty()) {
+    // This range is already infeasible.
+    return false;
+  }
+
   // This function has nine cases, the cartesian product of range-testing
   // both the upper and lower bounds against the symbol's type.
   // Each case requires a different pinning operation.
   // The function returns false if the described range is entirely outside
   // the range of values for the associated symbol.
   APSIntType Type(getMinValue());
   APSIntType::RangeTestResultKind LowerTest = Type.testInRange(Lower, true);
   APSIntType::RangeTestResultKind UpperTest = Type.testInRange(Upper, true);
for (iterator i = begin(), e = end(); i != e; ++i) {
 
     os << '[' << i->From().toString(10) << ", " << i->To().toString(10)
        << ']';
   }
   os << " }";
 }
 
 namespace {
+
+/// A little component aggregating all of the reasoning we have about
+/// the ranges of symbolic expressions.
+///
+/// Even when we don't know the exact values of the operands, we still
+/// can get a pretty good estimate of the result's range.
+class SymbolicRangeInferrer
+    : public SymExprVisitor<SymbolicRangeInferrer, RangeSet> {
+public:
+  static RangeSet inferRange(BasicValueFactory &BV, RangeSet::Factory &F,
+                             ProgramStateRef State, SymbolRef Sym) {
+    SymbolicRangeInferrer Inferrer(BV, F, State);
+    return Inferrer.infer(Sym);
+  }
+
+  RangeSet VisitSymExpr(SymbolRef Sym) {
+    // If we got to this function, the actual type of the symbolic
+    // expression is not supported for advanced inference.
+    // In this case, we simply backoff to the default "let's simply
+    // infer the range from the expression's type".
+    return infer(Sym->getType());
+  }
+
+  RangeSet VisitSymIntExpr(const SymIntExpr *Sym) {
+    return VisitBinaryOperator(Sym);
+  }
+
+  RangeSet VisitIntSymExpr(const IntSymExpr *Sym) {
+    return VisitBinaryOperator(Sym);
+  }
+
+  RangeSet VisitSymSymExpr(const SymSymExpr *Sym) {
+    return VisitBinaryOperator(Sym);
+  }
+
+private:
+  SymbolicRangeInferrer(BasicValueFactory &BV, RangeSet::Factory &F,
+                        ProgramStateRef S)
+      : ValueFactory(BV), RangeFactory(F), State(S) {}
+
+  /// Infer range information from the given integer constant.
+  ///
+  /// It's not a real "inference", but is here for operating with
+  /// sub-expressions in a more polymorphic manner.
+  RangeSet inferAs(const llvm::APSInt &Val, QualType) {
+    return {RangeFactory, Val};
+  }
+
+  /// Infer range information from symbol in the context of the given type.
+  RangeSet inferAs(SymbolRef Sym, QualType DestType) {
+    QualType ActualType = Sym->getType();
+    // Check that we can reason about the symbol at all.
+    if (ActualType->isIntegralOrEnumerationType() ||
+        Loc::isLocType(ActualType)) {
+      return infer(Sym);
+    }
+    // Otherwise, let's simply infer from the destination type.
+    // We couldn't figure out nothing else about that expression.
+    return infer(DestType);
+  }
+
+  RangeSet infer(SymbolRef Sym) {
+    const RangeSet *AssociatedRange = State->get<ConstraintRange>(Sym);
+
+    // If Sym is a difference of symbols A - B, then maybe we have range set
+    // stored for B - A.
+    const RangeSet *RangeAssociatedWithNegatedSym =
+        getRangeForMinusSymbol(State, Sym);
+
+    // If we have range set stored for both A - B and B - A then calculate the
+    // effective range set by intersecting the range set for A - B and the
+    // negated range set of B - A.
+    if (AssociatedRange && RangeAssociatedWithNegatedSym)
+      return AssociatedRange->Intersect(
+          ValueFactory, RangeFactory,
+          RangeAssociatedWithNegatedSym->Negate(ValueFactory, RangeFactory));
+
+    if (AssociatedRange)
+      return *AssociatedRange;
+
+    if (RangeAssociatedWithNegatedSym)
+      return RangeAssociatedWithNegatedSym->Negate(ValueFactory, RangeFactory);
+
+    return Visit(Sym);
+  }
+
+  /// Infer range information solely from the type.
+  RangeSet infer(QualType T) {
+    // Lazily generate a new RangeSet representing all possible values for the
+    // given symbol type.
+    RangeSet Result(RangeFactory, ValueFactory.getMinValue(T),
+                    ValueFactory.getMaxValue(T));
+
+    // References are known to be non-zero.
+    if (T->isReferenceType())
+      return assumeNonZero(Result, T);
+
+    return Result;
+  }
+
+  template <class BinarySymExprTy>
+  RangeSet VisitBinaryOperator(const BinarySymExprTy *Sym) {
+    // TODO #1: VisitBinaryOperator implementation might not make a good
+    // use of the inferred ranges.  In this case, we might be calculating
+    // everything for nothing.  This being said, we should introduce some
+    // sort of laziness mechanism here.
+    //
+    // TODO #2: We didn't go into the nested expressions before, so it
+    // might cause us spending much more time doing the inference.
+    // This can be a problem for deeply nested expressions that are
+    // involved in conditions and get tested continuously.  We definitely
+    // need to address this issue and introduce some sort of caching
+    // in here.
+    QualType ResultType = Sym->getType();
+    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);
+    case BO_And:
+      return VisitAndOperator(LHS, RHS, T);
+    default:
+      return infer(T);
+    }
+  }
+
+  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));
+      }
+
+      // 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);
+      }
+    }
+    return infer(T);
+  }
+
+  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);
+  }
+
+  /// 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;
+};
+
 class RangeConstraintManager : public RangedConstraintManager {
 public:
   RangeConstraintManager(ExprEngine *EE, SValBuilder &SVB)
       : RangedConstraintManager(EE, SVB) {}
 
   //===------------------------------------------------------------------===//
   // Implementation for interface from ConstraintManager.
   //===------------------------------------------------------------------===//
public:
   ProgramStateRef assumeSymOutsideInclusiveRange(
       ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
       const llvm::APSInt &To, const llvm::APSInt &Adjustment) override;
 
 private:
   RangeSet::Factory F;
 
   RangeSet getRange(ProgramStateRef State, SymbolRef Sym);
-  const RangeSet* getRangeForMinusSymbol(ProgramStateRef State,
-                                         SymbolRef Sym);
+  const RangeSet *getRangeForMinusSymbol(ProgramStateRef State, SymbolRef Sym);
 
   RangeSet getSymLTRange(ProgramStateRef St, SymbolRef Sym,
                          const llvm::APSInt &Int,
                          const llvm::APSInt &Adjustment);
   RangeSet getSymGTRange(ProgramStateRef St, SymbolRef Sym,
                          const llvm::APSInt &Int,
                          const llvm::APSInt &Adjustment);
   RangeSet getSymLERange(ProgramStateRef St, SymbolRef Sym,
                          const llvm::APSInt &Int,
                          const llvm::APSInt &Adjustment);
   RangeSet getSymLERange(llvm::function_ref<RangeSet()> RS,
                          const llvm::APSInt &Int,
                          const llvm::APSInt &Adjustment);
   RangeSet getSymGERange(ProgramStateRef St, SymbolRef Sym,
                          const llvm::APSInt &Int,
                          const llvm::APSInt &Adjustment);
-
 };
 
 } // end anonymous namespace
 
 std::unique_ptr<ConstraintManager>
 ento::CreateRangeConstraintManager(ProgramStateManager &StMgr,
                                    ExprEngine *Eng) {
   return std::make_unique<RangeConstraintManager>(Eng, StMgr.getSValBuilder());
if (SymReaper.isDead(Sym)) {
       Changed = true;
       CR = CRFactory.remove(CR, Sym);
     }
   }
 
   return Changed ? State->set<ConstraintRange>(CR) : State;
 }
 
-/// Return a range set subtracting zero from \p Domain.
-static RangeSet assumeNonZero(
-    BasicValueFactory &BV,
-    RangeSet::Factory &F,
-    SymbolRef Sym,
-    RangeSet Domain) {
-  APSIntType IntType = BV.getAPSIntType(Sym->getType());
-  return Domain.Intersect(BV, F, ++IntType.getZeroValue(),
-      --IntType.getZeroValue());
-}
-
-/// Apply implicit constraints for bitwise OR- and AND-.
-/// For unsigned types, bitwise OR with a constant always returns
-/// a value greater-or-equal than the constant, and bitwise AND
-/// returns a value less-or-equal then the constant.
-///
-/// Pattern matches the expression \p Sym against those rule,
-/// and applies the required constraints.
-/// \p Input Previously established expression range set
-static RangeSet applyBitwiseConstraints(
-    BasicValueFactory &BV,
-    RangeSet::Factory &F,
-    RangeSet Input,
-    const SymIntExpr* SIE) {
-  QualType T = SIE->getType();
-  bool IsUnsigned = T->isUnsignedIntegerType();
-  const llvm::APSInt &RHS = SIE->getRHS();
-  const llvm::APSInt &Zero = BV.getAPSIntType(T).getZeroValue();
-  BinaryOperator::Opcode Operator = SIE->getOpcode();
-
-  // For unsigned types, the output of bitwise-or is bigger-or-equal than RHS.
-  if (Operator == BO_Or && IsUnsigned)
-    return Input.Intersect(BV, F, RHS, BV.getMaxValue(T));
-
-  // Bitwise-or with a non-zero constant is always non-zero.
-  if (Operator == BO_Or && RHS != Zero)
-    return assumeNonZero(BV, F, SIE, Input);
-
-  // 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 (Operator == BO_And && (IsUnsigned || RHS >= Zero))
-    return Input.Intersect(BV, F, BV.getMinValue(T), RHS);
-
-  return Input;
-}
-
 RangeSet RangeConstraintManager::getRange(ProgramStateRef State,
                                           SymbolRef Sym) {
-  ConstraintRangeTy::data_type *V = State->get<ConstraintRange>(Sym);
-
-  // If Sym is a difference of symbols A - B, then maybe we have range set
-  // stored for B - A.
-  BasicValueFactory &BV = getBasicVals();
-  const RangeSet *R = getRangeForMinusSymbol(State, Sym);
-
-  // If we have range set stored for both A - B and B - A then calculate the
-  // effective range set by intersecting the range set for A - B and the
-  // negated range set of B - A.
-  if (V && R)
-    return V->Intersect(BV, F, R->Negate(BV, F));
-  if (V)
-    return *V;
-  if (R)
-    return R->Negate(BV, F);
-
-  // Lazily generate a new RangeSet representing all possible values for the
-  // given symbol type.
-  QualType T = Sym->getType();
-
-  RangeSet Result(F, BV.getMinValue(T), BV.getMaxValue(T));
-
-  // References are known to be non-zero.
-  if (T->isReferenceType())
-    return assumeNonZero(BV, F, Sym, Result);
-
-  // Known constraints on ranges of bitwise expressions.
-  if (const SymIntExpr* SIE = dyn_cast<SymIntExpr>(Sym))
-    return applyBitwiseConstraints(BV, F, Result, SIE);
-
-  return Result;
+  return SymbolicRangeInferrer::inferRange(getBasicVals(), F, State, Sym);
 }
 
 // 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*

clang/test/Analysis/constant-folding.c

void testBitwiseRules(unsigned int a, int b) {
   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 dynamically computed constants also work.
-  int constant = 1 << 3;
+  unsigned int constant = 1 << 3;
   unsigned int d = a | constant;
-  clang_analyzer_eval(constant > 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(d >= constant); // expected-warning{{TRUE}}
+
+  // Check that nested expressions also work.
+  clang_analyzer_eval(((a | 10) | 5) >= 10); // 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}}
+  }
 }

clang/test/Analysis/double-ranges-bug.c

+// RUN: %clang_analyze_cc1 -verify %s -analyzer-checker=core
+
+// expected-no-diagnostics
+
+typedef unsigned long int A;
+
+extern int fill(A **values, int *nvalues);
+
+void foo() {
+  A *values;
+  int nvalues;
+  fill(&values, &nvalues);
+
+  int i = 1;
+  double x, y;
+
+  y = values[i - 1];
+  x = values[i];
+
+  if (x <= y) {
+  }
+}