[analyzer] Improve performance of the SVal simplification mechanism.

When neither LHS nor RHS of a binary operator expression can be simplified,
return the original expression instead of re-evaluating the binary operator.

Such re-evaluation was causing recusrive re-simplification which caused
the algorithmic complexity to explode.

Differential Revision: https://reviews.llvm.org/D47155

llvm-svn: 333670

1 files changed, 19 insertions, 5 deletions

diff --git a/clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp b/clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
index 4171ebf1368..d26ea498f95 100644
--- a/clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
+++ b/clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
@@ -1222,6 +1222,10 @@ SVal SimpleSValBuilder::simplifySVal(ProgramStateRef State, SVal V) {
     ProgramStateRef State;
     SValBuilder &SVB;
 
+    static bool isUnchanged(SymbolRef Sym, SVal Val) {
+      return Sym == Val.getAsSymbol();
+    }
+
   public:
     Simplifier(ProgramStateRef State)
         : State(State), SVB(State->getStateManager().getSValBuilder()) {}
@@ -1231,8 +1235,7 @@ SVal SimpleSValBuilder::simplifySVal(ProgramStateRef State, SVal V) {
               SVB.getKnownValue(State, nonloc::SymbolVal(S)))
         return Loc::isLocType(S->getType()) ? (SVal)SVB.makeIntLocVal(*I)
                                             : (SVal)SVB.makeIntVal(*I);
-      return Loc::isLocType(S->getType()) ? (SVal)SVB.makeLoc(S) 
-                                          : nonloc::SymbolVal(S);
+      return SVB.makeSymbolVal(S);
     }
 
     // TODO: Support SymbolCast. Support IntSymExpr when/if we actually
@@ -1240,6 +1243,8 @@ SVal SimpleSValBuilder::simplifySVal(ProgramStateRef State, SVal V) {
 
     SVal VisitSymIntExpr(const SymIntExpr *S) {
       SVal LHS = Visit(S->getLHS());
+      if (isUnchanged(S->getLHS(), LHS))
+        return SVB.makeSymbolVal(S);
       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.
@@ -1264,6 +1269,8 @@ SVal SimpleSValBuilder::simplifySVal(ProgramStateRef State, SVal V) {
     SVal VisitSymSymExpr(const SymSymExpr *S) {
       SVal LHS = Visit(S->getLHS());
       SVal RHS = Visit(S->getRHS());
+      if (isUnchanged(S->getLHS(), LHS) && isUnchanged(S->getRHS(), RHS))
+        return SVB.makeSymbolVal(S);
       return SVB.evalBinOp(State, S->getOpcode(), LHS, RHS, S->getType());
     }
 
@@ -1274,13 +1281,20 @@ SVal SimpleSValBuilder::simplifySVal(ProgramStateRef State, SVal V) {
     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);
+  // A crude way of preventing this function from calling itself from evalBinOp.
+  static bool isReentering = false;
+  if (isReentering)
+    return V;
+
+  isReentering = true;
+  SVal SimplifiedV = Simplifier(State).Visit(V);
+  isReentering = false;
+
+  return SimplifiedV;
 }