[analyzer] Create one state for a range switch case instead of multiple.

This fixes PR16833, in which the analyzer was using large amounts of memory
for switch statements with large case ranges.

rdar://problem/14685772

A patch by Aleksei Sidorin!

Differential Revision: http://reviews.llvm.org/D5102

llvm-svn: 248318

1 files changed, 67 insertions, 0 deletions

diff --git a/clang/lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp b/clang/lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp
index 35930e47f82..4051242434e 100644
--- a/clang/lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp
+++ b/clang/lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp
@@ -190,6 +190,42 @@ ProgramStateRef SimpleConstraintManager::assumeAux(ProgramStateRef state,
   } // end switch
 }
 
+ProgramStateRef SimpleConstraintManager::assumeWithinInclusiveRange(
+    ProgramStateRef State, NonLoc Value, const llvm::APSInt &From,
+    const llvm::APSInt &To, bool InRange) {
+
+  assert(From.isUnsigned() == To.isUnsigned() &&
+         From.getBitWidth() == To.getBitWidth() &&
+         "Values should have same types!");
+
+  if (!canReasonAbout(Value)) {
+    // Just add the constraint to the expression without trying to simplify.
+    SymbolRef Sym = Value.getAsSymExpr();
+    assert(Sym);
+    return assumeSymWithinInclusiveRange(State, Sym, From, To, InRange);
+  }
+
+  switch (Value.getSubKind()) {
+  default:
+    llvm_unreachable("'assumeWithinInclusiveRange' is not implemented"
+                     "for this NonLoc");
+
+  case nonloc::LocAsIntegerKind:
+  case nonloc::SymbolValKind: {
+    if (SymbolRef Sym = Value.getAsSymbol())
+      return assumeSymWithinInclusiveRange(State, Sym, From, To, InRange);
+    return State;
+  } // end switch
+
+  case nonloc::ConcreteIntKind: {
+    const llvm::APSInt &IntVal = Value.castAs<nonloc::ConcreteInt>().getValue();
+    bool IsInRange = IntVal >= From && IntVal <= To;
+    bool isFeasible = (IsInRange == InRange);
+    return isFeasible ? State : nullptr;
+  }
+  } // end switch
+}
+
 static void computeAdjustment(SymbolRef &Sym, llvm::APSInt &Adjustment) {
   // Is it a "($sym+constant1)" expression?
   if (const SymIntExpr *SE = dyn_cast<SymIntExpr>(Sym)) {
@@ -262,6 +298,37 @@ ProgramStateRef SimpleConstraintManager::assumeSymRel(ProgramStateRef state,
   } // end switch
 }
 
+ProgramStateRef
+SimpleConstraintManager::assumeSymWithinInclusiveRange(ProgramStateRef State,
+                                                       SymbolRef Sym,
+                                                       const llvm::APSInt &From,
+                                                       const llvm::APSInt &To,
+                                                       bool InRange) {
+  // Get the type used for calculating wraparound.
+  BasicValueFactory &BVF = getBasicVals();
+  APSIntType WraparoundType = BVF.getAPSIntType(Sym->getType());
+
+  llvm::APSInt Adjustment = WraparoundType.getZeroValue();
+  SymbolRef AdjustedSym = Sym;
+  computeAdjustment(AdjustedSym, Adjustment);
+
+  // Convert the right-hand side integer as necessary.
+  APSIntType ComparisonType = std::max(WraparoundType, APSIntType(From));
+  llvm::APSInt ConvertedFrom = ComparisonType.convert(From);
+  llvm::APSInt ConvertedTo = ComparisonType.convert(To);
+
+  // Prefer unsigned comparisons.
+  if (ComparisonType.getBitWidth() == WraparoundType.getBitWidth() &&
+      ComparisonType.isUnsigned() && !WraparoundType.isUnsigned())
+    Adjustment.setIsSigned(false);
+
+  if (InRange)
+    return assumeSymbolWithinInclusiveRange(State, AdjustedSym, ConvertedFrom,
+                                            ConvertedTo, Adjustment);
+  return assumeSymbolOutOfInclusiveRange(State, AdjustedSym, ConvertedFrom,
+                                         ConvertedTo, Adjustment);
+}
+
 } // end of namespace ento
 
 } // end of namespace clang