diff options
author | Artem Dergachev <artem.dergachev@gmail.com> | 2017-04-13 07:20:04 +0000 |
---|---|---|
committer | Artem Dergachev <artem.dergachev@gmail.com> | 2017-04-13 07:20:04 +0000 |
commit | ce3969a0d17b1f5453f4a16da9f8ba3791f35536 (patch) | |
tree | d53751de1206f92a0c97c4a5998d9e502aad7b9f /lib/StaticAnalyzer | |
parent | e65ba1f3740b2c95223526d7927bb6cc12a898db (diff) |
[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
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@300178 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/StaticAnalyzer')
-rw-r--r-- | lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp | 87 |
1 files changed, 82 insertions, 5 deletions
diff --git a/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp b/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp index 359841660b..77de0c3ebc 100644 --- a/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp +++ b/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<NonLoc>()) { + 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<Simplifier, SVal> { + 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); +} |