[PATCH] D47155: [analyzer] Reduce simplifySVal complexity threshold further.
NoQ updated this revision to Diff 148684.
NoQ added a comment.
Add an explicit brute-force protection against re-entering `simplifySVal()`.
Remove the threshold completely.
https://reviews.llvm.org/D47155
Files:
include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h
lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
test/Analysis/hangs.c
Index: test/Analysis/hangs.c
===
--- /dev/null
+++ test/Analysis/hangs.c
@@ -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();
+}
Index: lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
===
--- lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
+++ lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
@@ -1222,6 +1222,10 @@
ProgramStateRef State;
SValBuilder
+static bool isUnchanged(SymbolRef Sym, SVal Val) {
+ return Sym == Val.getAsSymbol();
+}
+
public:
Simplifier(ProgramStateRef State)
: State(State), SVB(State->getStateManager().getSValBuilder()) {}
@@ -1231,15 +1235,16 @@
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
// start producing them.
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 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 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;
}
Index: include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h
===
--- include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h
+++ include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h
@@ -367,6 +367,15 @@
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);
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D47155: [analyzer] Reduce simplifySVal complexity threshold further.
NoQ added a comment.
I only essentially did one optimization - introduce a short path that returns
the original value if visiting its sub-values changed nothing, which is a
relatively common case. The reason it works though is that `evalBinOp()` will
be called later to combine the sub-values, which may in turn call
`simplifySVal()` again, which is clearly unwanted.
Comment at: test/Analysis/hangs.c:18-30
+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();
This currently finishes in 1 second on my machine. This test, unlike the
original test, is easy to experiment with.
https://reviews.llvm.org/D47155
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D47155: [analyzer] Reduce simplifySVal complexity threshold further.
NoQ updated this revision to Diff 148681.
NoQ added a comment.
Optimize `simplifySVal()` instead of reducing the threshold.
I'll address the memoization separately.
https://reviews.llvm.org/D47155
Files:
include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h
lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
test/Analysis/hangs.c
Index: test/Analysis/hangs.c
===
--- /dev/null
+++ test/Analysis/hangs.c
@@ -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();
+}
Index: lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
===
--- lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
+++ lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
@@ -1222,6 +1222,10 @@
ProgramStateRef State;
SValBuilder
+static bool isUnchanged(SymbolRef Sym, SVal Val) {
+ return Sym == Val.getAsSymbol();
+}
+
public:
Simplifier(ProgramStateRef State)
: State(State), SVB(State->getStateManager().getSValBuilder()) {}
@@ -1231,15 +1235,16 @@
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
// start producing them.
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 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());
}
Index: include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h
===
--- include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h
+++ include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h
@@ -367,6 +367,15 @@
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);
Index: test/Analysis/hangs.c
===
--- /dev/null
+++ test/Analysis/hangs.c
@@ -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();
+}
Index: lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
===
--- lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
+++ lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
@@ -1222,6 +1222,10 @@
ProgramStateRef State;
SValBuilder
+static bool
[PATCH] D47155: [analyzer] Reduce simplifySVal complexity threshold further.
baloghadamsoftware added a comment. Hello! Thank you for addressing this problem. Are these kinds of symbols common in real code? For me it seems very artificial. However, I agree with George, it would be better to have this value as an analyzer option with a default value (of 20). Repository: rC Clang https://reviews.llvm.org/D47155 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D47155: [analyzer] Reduce simplifySVal complexity threshold further.
george.karpenkov added a comment. Also we should make sure that all recursive transformations on expressions represented as DAGs should be memoized. Repository: rC Clang https://reviews.llvm.org/D47155 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D47155: [analyzer] Reduce simplifySVal complexity threshold further.
george.karpenkov added a comment. @NoQ I'm really wary of magic numbers. - We should expose it through an analyzer-config flag. We already do so for the budget. - We should probably have both positive and negative tests. What scenarios _stop_ working after the threshold is decreased? [point 1 is required to be able to test that] - Finally, do we understand where the slowdown comes from? If it comes from attempted rearrangements due to https://reviews.llvm.org/rC329780 I think we should roll that back instead. Repository: rC Clang https://reviews.llvm.org/D47155 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D47155: [analyzer] Reduce simplifySVal complexity threshold further.
NoQ added a reviewer: mikhail.ramalho. NoQ added a subscriber: mikhail.ramalho. NoQ added a comment. @mikhail.ramalho Does it solve your problems with ffmpeg as well? :) Repository: rC Clang https://reviews.llvm.org/D47155 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D47155: [analyzer] Reduce simplifySVal complexity threshold further.
NoQ created this revision.
NoQ added reviewers: dcoughlin, xazax.hun, a.sidorin, george.karpenkov, szepet,
rnkovacs.
Herald added subscribers: cfe-commits, baloghadamsoftware.
Reported by Mikael Holmén on
http://lists.llvm.org/pipermail/cfe-commits/Week-of-Mon-20180416/225349.html -
a combination of https://reviews.llvm.org/rC329780 and
https://reviews.llvm.org/rC300178 caused a performance regression that seemed
to be a hang on the attached test case.
Reducing even further from 20 to 10 gives a ~15% further speed boost on the
test, but i don't think it's worth it because such code is not common and
therefore accuracy is more important.
Repository:
rC Clang
https://reviews.llvm.org/D47155
Files:
lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
test/Analysis/hangs.c
Index: test/Analysis/hangs.c
===
--- /dev/null
+++ test/Analysis/hangs.c
@@ -0,0 +1,16 @@
+// 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;
+}
Index: lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
===
--- lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
+++ lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
@@ -1274,7 +1274,7 @@
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)
+ if (V.getSymbol()->computeComplexity() > 20)
return V;
return Visit(V.getSymbol());
}
Index: test/Analysis/hangs.c
===
--- /dev/null
+++ test/Analysis/hangs.c
@@ -0,0 +1,16 @@
+// 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;
+}
Index: lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
===
--- lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
+++ lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
@@ -1274,7 +1274,7 @@
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)
+ if (V.getSymbol()->computeComplexity() > 20)
return V;
return Visit(V.getSymbol());
}
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
