Author: dergachev Date: Thu May 31 10:22:38 2018 New Revision: 333670 URL: http://llvm.org/viewvc/llvm-project?rev=333670&view=rev Log: [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 Added: cfe/trunk/test/Analysis/hangs.c Modified: cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h cfe/trunk/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp Modified: cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h?rev=333670&r1=333669&r2=333670&view=diff ============================================================================== --- cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h (original) +++ cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h Thu May 31 10:22:38 2018 @@ -367,6 +367,15 @@ public: return loc::ConcreteInt(BasicVals.getValue(integer)); } + /// Make an SVal that represents the given symbol. This follows the convention + /// of representing Loc-type symbols (symbolic pointers and references) + /// as Loc values wrapping the symbol rather than as plain symbol values. + SVal makeSymbolVal(SymbolRef Sym) { + if (Loc::isLocType(Sym->getType())) + return makeLoc(Sym); + return nonloc::SymbolVal(Sym); + } + /// Return a memory region for the 'this' object reference. loc::MemRegionVal getCXXThis(const CXXMethodDecl *D, const StackFrameContext *SFC); Modified: cfe/trunk/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp?rev=333670&r1=333669&r2=333670&view=diff ============================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp (original) +++ cfe/trunk/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp Thu May 31 10:22:38 2018 @@ -1222,6 +1222,10 @@ SVal SimpleSValBuilder::simplifySVal(Pro 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(Pro 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(Pro 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(Pro 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(Pro 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; } Added: cfe/trunk/test/Analysis/hangs.c URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/test/Analysis/hangs.c?rev=333670&view=auto ============================================================================== --- cfe/trunk/test/Analysis/hangs.c (added) +++ cfe/trunk/test/Analysis/hangs.c Thu May 31 10:22:38 2018 @@ -0,0 +1,30 @@ +// RUN: %clang_analyze_cc1 -analyzer-checker core -verify %s + +// expected-no-diagnostics + +// Stuff that used to hang. + +int g(); + +int f(int y) { + return y + g(); +} + +int produce_a_very_large_symbol(int x) { + return f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f( + f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(x)))))))))))))))))))))))))))))))); +} + +void produce_an_exponentially_exploding_symbol(int x, int y) { + x += y; y += x + g(); + x += y; y += x + g(); + x += y; y += x + g(); + x += y; y += x + g(); + x += y; y += x + g(); + x += y; y += x + g(); + x += y; y += x + g(); + x += y; y += x + g(); + x += y; y += x + g(); + x += y; y += x + g(); + x += y; y += x + g(); +} _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
