From 12294f8d2ecfe62d6f84170856bde8dc02cb80aa Mon Sep 17 00:00:00 2001 From: Artem Dergachev Date: Thu, 13 Apr 2017 07:20:04 +0000 Subject: [PATCH] [analyzer] Simplify values in binary operations a bit more aggressively. SValBuilder tries to constant-fold symbols in the left-hand side of the symbolic expression whenever it fails to evaluate the expression directly. However, it only constant-folds them when they are atomic expressions, not when they are complicated expressions themselves. This patch adds recursive constant-folding to the left-hand side subexpression (there's a lack of symmetry because we're trying to have symbols on the left and constants on the right). As an example, we'd now be able to handle operations similar to "$x + 1 < $y", when $x is constrained to a constant. rdar://problem/31354676 Differential Revision: https://reviews.llvm.org/D31886 llvm-svn: 300178 --- .../Core/PathSensitive/SValBuilder.h | 5 ++ .../lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp | 87 ++++++++++++++++++++-- clang/test/Analysis/additive-folding.cpp | 9 +++ 3 files changed, 96 insertions(+), 5 deletions(-) diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h index a4c01fc..14aa3af 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h @@ -112,6 +112,11 @@ public: /// Evaluates a given SVal. If the SVal has only one possible (integer) value, /// that value is returned. Otherwise, returns NULL. virtual const llvm::APSInt *getKnownValue(ProgramStateRef state, SVal val) = 0; + + /// Simplify symbolic expressions within a given SVal. Return an SVal + /// that represents the same value, but is hopefully easier to work with + /// than the original SVal. + virtual SVal simplifySVal(ProgramStateRef State, SVal Val) = 0; /// Constructs a symbolic expression for two non-location values. SVal makeSymExprValNN(ProgramStateRef state, BinaryOperator::Opcode op, diff --git a/clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp b/clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp index 3598416..77de0c3 100644 --- a/clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp +++ b/clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp @@ -14,6 +14,7 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h" #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/SValVisitor.h" using namespace clang; using namespace ento; @@ -44,6 +45,10 @@ public: /// (integer) value, that value is returned. Otherwise, returns NULL. const llvm::APSInt *getKnownValue(ProgramStateRef state, SVal V) override; + /// Recursively descends into symbolic expressions and replaces symbols + /// with their known values (in the sense of the getKnownValue() method). + SVal simplifySVal(ProgramStateRef State, SVal V) override; + SVal MakeSymIntVal(const SymExpr *LHS, BinaryOperator::Opcode op, const llvm::APSInt &RHS, QualType resultTy); }; @@ -537,11 +542,12 @@ SVal SimpleSValBuilder::evalBinOpNN(ProgramStateRef state, // Does the symbolic expression simplify to a constant? // If so, "fold" the constant by setting 'lhs' to a ConcreteInt // and try again. - ConstraintManager &CMgr = state->getConstraintManager(); - if (const llvm::APSInt *Constant = CMgr.getSymVal(state, Sym)) { - lhs = nonloc::ConcreteInt(*Constant); - continue; - } + SVal simplifiedLhs = simplifySVal(state, lhs); + if (simplifiedLhs != lhs) + if (auto simplifiedLhsAsNonLoc = simplifiedLhs.getAs()) { + lhs = *simplifiedLhsAsNonLoc; + continue; + } // Is the RHS a constant? if (const llvm::APSInt *RHSValue = getKnownValue(state, rhs)) @@ -993,3 +999,74 @@ const llvm::APSInt *SimpleSValBuilder::getKnownValue(ProgramStateRef state, // FIXME: Add support for SymExprs. return nullptr; } + +SVal SimpleSValBuilder::simplifySVal(ProgramStateRef State, SVal V) { + // For now, this function tries to constant-fold symbols inside a + // nonloc::SymbolVal, and does nothing else. More simplifications should + // be possible, such as constant-folding an index in an ElementRegion. + + class Simplifier : public FullSValVisitor { + ProgramStateRef State; + SValBuilder &SVB; + + public: + Simplifier(ProgramStateRef State) + : State(State), SVB(State->getStateManager().getSValBuilder()) {} + + SVal VisitSymbolData(const SymbolData *S) { + if (const llvm::APSInt *I = + SVB.getKnownValue(State, nonloc::SymbolVal(S))) + return Loc::isLocType(S->getType()) ? (SVal)SVB.makeIntLocVal(*I) + : (SVal)SVB.makeIntVal(*I); + return nonloc::SymbolVal(S); + } + + // TODO: Support SymbolCast. Support IntSymExpr when/if we actually + // start producing them. + + SVal VisitSymIntExpr(const SymIntExpr *S) { + SVal LHS = Visit(S->getLHS()); + SVal RHS; + // By looking at the APSInt in the right-hand side of S, we cannot + // figure out if it should be treated as a Loc or as a NonLoc. + // So make our guess by recalling that we cannot multiply pointers + // or compare a pointer to an integer. + if (Loc::isLocType(S->getLHS()->getType()) && + BinaryOperator::isComparisonOp(S->getOpcode())) { + // The usual conversion of $sym to &SymRegion{$sym}, as they have + // the same meaning for Loc-type symbols, but the latter form + // is preferred in SVal computations for being Loc itself. + if (SymbolRef Sym = LHS.getAsSymbol()) { + assert(Loc::isLocType(Sym->getType())); + LHS = SVB.makeLoc(Sym); + } + RHS = SVB.makeIntLocVal(S->getRHS()); + } else { + RHS = SVB.makeIntVal(S->getRHS()); + } + return SVB.evalBinOp(State, S->getOpcode(), LHS, RHS, S->getType()); + } + + SVal VisitSymSymExpr(const SymSymExpr *S) { + SVal LHS = Visit(S->getLHS()); + SVal RHS = Visit(S->getRHS()); + return SVB.evalBinOp(State, S->getOpcode(), LHS, RHS, S->getType()); + } + + SVal VisitSymExpr(SymbolRef S) { return nonloc::SymbolVal(S); } + + SVal VisitMemRegion(const MemRegion *R) { return loc::MemRegionVal(R); } + + SVal VisitNonLocSymbolVal(nonloc::SymbolVal V) { + // Simplification is much more costly than computing complexity. + // For high complexity, it may be not worth it. + if (V.getSymbol()->computeComplexity() > 100) + return V; + return Visit(V.getSymbol()); + } + + SVal VisitSVal(SVal V) { return V; } + }; + + return Simplifier(State).Visit(V); +} diff --git a/clang/test/Analysis/additive-folding.cpp b/clang/test/Analysis/additive-folding.cpp index 52056d4..823b176 100644 --- a/clang/test/Analysis/additive-folding.cpp +++ b/clang/test/Analysis/additive-folding.cpp @@ -205,3 +205,12 @@ void multiplicativeSanityTest(int x) { clang_analyzer_eval(x == 3); // expected-warning{{UNKNOWN}} } + +void additiveSymSymFolding(int x, int y) { + // We should simplify 'x - 1' to '0' and handle the comparison, + // despite both sides being complicated symbols. + int z = x - 1; + if (x == 1) + if (y >= 0) + clang_analyzer_eval(z <= y); // expected-warning{{TRUE}} +} -- 2.7.4