NoQ created this revision.
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 expression (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.
The constant-folding procedure, which i put into `SValBuilder::simplifySVal()`,
is reusable, and i suspect that there are numerous places around `SValBuilder`,
`ConstraintManager`, and our checkers, where it could be useful, but this patch
tries to be relatively careful.
I'm still to see how it affects performance.
https://reviews.llvm.org/D31886
Files:
include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h
lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
test/Analysis/additive-folding.cpp
Index: test/Analysis/additive-folding.cpp
===================================================================
--- test/Analysis/additive-folding.cpp
+++ test/Analysis/additive-folding.cpp
@@ -205,3 +205,12 @@
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}}
+}
Index: lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
===================================================================
--- lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
+++ 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 @@
/// (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 thier 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 @@
// 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<NonLoc>()) {
+ lhs = *simplifiedLhsAsNonLoc;
+ continue;
+ }
// Is the RHS a constant?
if (const llvm::APSInt *RHSValue = getKnownValue(state, rhs))
@@ -993,3 +999,64 @@
// 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<Simplifier, SVal> {
+ ProgramStateRef State;
+
+ public:
+ Simplifier(ProgramStateRef State) : State(State) {}
+
+ SVal VisitSymbolData(const SymbolData *S) {
+ SValBuilder &SVB = State->getStateManager().getSValBuilder();
+ 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);
+ }
+
+ SVal VisitSymIntExpr(const SymIntExpr *S) {
+ SValBuilder &SVB = State->getStateManager().getSValBuilder();
+ SVal LHS, RHS;
+ if (Loc::isLocType(S->getLHS()->getType()) &&
+ BinaryOperator::isComparisonOp(S->getOpcode())) {
+ LHS = Visit(S->getLHS());
+ if (SymbolRef Sym = LHS.getAsSymbol())
+ LHS = SVB.makeLoc(Sym);
+ RHS = SVB.makeIntLocVal(S->getRHS());
+ } else {
+ LHS = Visit(S->getLHS());
+ RHS = SVB.makeIntVal(S->getRHS());
+ }
+ return SVB.evalBinOp(State, S->getOpcode(), LHS, RHS, S->getType());
+ }
+
+ SVal VisitSymSymExpr(const SymSymExpr *S) {
+ SValBuilder &SVB = State->getStateManager().getSValBuilder();
+ 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);
+}
Index: include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h
===================================================================
--- include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h
+++ include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h
@@ -112,6 +112,11 @@
/// 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,
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
