Hi jordan_rose,
ScanReachableSymbols uses a "visited" set to avoid scanning the same object
twice. However, it did not use the optimization for LazyCompoundVal objects,
which resulted in exponential complexity for long chains of temporary objects.
Adding this resulted in a decrease of analysis time from >3h to 3 seconds for
some files.
I have no idea how to unittest this, suggestions welcome.
http://llvm-reviews.chandlerc.com/D1398
Files:
include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h
lib/StaticAnalyzer/Core/ProgramState.cpp
Index: include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h
===================================================================
--- include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h
+++ include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h
@@ -808,6 +808,7 @@
ScanReachableSymbols(ProgramStateRef st, SymbolVisitor& v)
: state(st), visitor(v) {}
+ bool scan(nonloc::LazyCompoundVal val);
bool scan(nonloc::CompoundVal val);
bool scan(SVal val);
bool scan(const MemRegion *R);
Index: lib/StaticAnalyzer/Core/ProgramState.cpp
===================================================================
--- lib/StaticAnalyzer/Core/ProgramState.cpp
+++ lib/StaticAnalyzer/Core/ProgramState.cpp
@@ -526,6 +526,20 @@
return getPersistentState(NewState);
}
+bool ScanReachableSymbols::scan(nonloc::LazyCompoundVal val) {
+ StoreManager &StoreMgr = state->getStateManager().getStoreManager();
+ // FIXME: We don't really want to use getBaseRegion() here because pointer
+ // arithmetic doesn't apply, but scanReachableSymbols only accepts base
+ // regions right now.
+ const MemRegion *R = val.getRegion()->getBaseRegion();
+ unsigned &isVisited = visited[R];
+ if (isVisited)
+ return true;
+ isVisited = 1;
+
+ return StoreMgr.scanReachableSymbols(val.getStore(), R, *this);
+}
+
bool ScanReachableSymbols::scan(nonloc::CompoundVal val) {
for (nonloc::CompoundVal::iterator I=val.begin(), E=val.end(); I!=E; ++I)
if (!scan(*I))
@@ -570,16 +584,8 @@
return scan(X->getRegion());
if (Optional<nonloc::LazyCompoundVal> X =
- val.getAs<nonloc::LazyCompoundVal>()) {
- StoreManager &StoreMgr = state->getStateManager().getStoreManager();
- // FIXME: We don't really want to use getBaseRegion() here because pointer
- // arithmetic doesn't apply, but scanReachableSymbols only accepts base
- // regions right now.
- if (!StoreMgr.scanReachableSymbols(X->getStore(),
- X->getRegion()->getBaseRegion(),
- *this))
- return false;
- }
+ val.getAs<nonloc::LazyCompoundVal>())
+ return scan(*X);
if (Optional<nonloc::LocAsInteger> X = val.getAs<nonloc::LocAsInteger>())
return scan(X->getLoc());
Index: include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h
===================================================================
--- include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h
+++ include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h
@@ -808,6 +808,7 @@
ScanReachableSymbols(ProgramStateRef st, SymbolVisitor& v)
: state(st), visitor(v) {}
+ bool scan(nonloc::LazyCompoundVal val);
bool scan(nonloc::CompoundVal val);
bool scan(SVal val);
bool scan(const MemRegion *R);
Index: lib/StaticAnalyzer/Core/ProgramState.cpp
===================================================================
--- lib/StaticAnalyzer/Core/ProgramState.cpp
+++ lib/StaticAnalyzer/Core/ProgramState.cpp
@@ -526,6 +526,20 @@
return getPersistentState(NewState);
}
+bool ScanReachableSymbols::scan(nonloc::LazyCompoundVal val) {
+ StoreManager &StoreMgr = state->getStateManager().getStoreManager();
+ // FIXME: We don't really want to use getBaseRegion() here because pointer
+ // arithmetic doesn't apply, but scanReachableSymbols only accepts base
+ // regions right now.
+ const MemRegion *R = val.getRegion()->getBaseRegion();
+ unsigned &isVisited = visited[R];
+ if (isVisited)
+ return true;
+ isVisited = 1;
+
+ return StoreMgr.scanReachableSymbols(val.getStore(), R, *this);
+}
+
bool ScanReachableSymbols::scan(nonloc::CompoundVal val) {
for (nonloc::CompoundVal::iterator I=val.begin(), E=val.end(); I!=E; ++I)
if (!scan(*I))
@@ -570,16 +584,8 @@
return scan(X->getRegion());
if (Optional<nonloc::LazyCompoundVal> X =
- val.getAs<nonloc::LazyCompoundVal>()) {
- StoreManager &StoreMgr = state->getStateManager().getStoreManager();
- // FIXME: We don't really want to use getBaseRegion() here because pointer
- // arithmetic doesn't apply, but scanReachableSymbols only accepts base
- // regions right now.
- if (!StoreMgr.scanReachableSymbols(X->getStore(),
- X->getRegion()->getBaseRegion(),
- *this))
- return false;
- }
+ val.getAs<nonloc::LazyCompoundVal>())
+ return scan(*X);
if (Optional<nonloc::LocAsInteger> X = val.getAs<nonloc::LocAsInteger>())
return scan(X->getLoc());
_______________________________________________
cfe-commits mailing list
[email protected]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
