Author: labath Date: Mon Aug 19 10:23:34 2013 New Revision: 188677 URL: http://llvm.org/viewvc/llvm-project?rev=188677&view=rev Log: [analyzer] Fix inefficiency in dead symbol removal
Summary: 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. Reviewers: jordan_rose CC: cfe-commits Differential Revision: http://llvm-reviews.chandlerc.com/D1398 Modified: cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h cfe/trunk/lib/StaticAnalyzer/Core/ProgramState.cpp Modified: cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h?rev=188677&r1=188676&r2=188677&view=diff ============================================================================== --- cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h (original) +++ cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h Mon Aug 19 10:23:34 2013 @@ -798,7 +798,7 @@ CB ProgramState::scanReachableSymbols(co /// A Utility class that allows to visit the reachable symbols using a custom /// SymbolVisitor. class ScanReachableSymbols { - typedef llvm::DenseMap<const void*, unsigned> VisitedItems; + typedef llvm::DenseSet<const void*> VisitedItems; VisitedItems visited; ProgramStateRef state; @@ -808,6 +808,7 @@ public: 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); Modified: cfe/trunk/lib/StaticAnalyzer/Core/ProgramState.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/StaticAnalyzer/Core/ProgramState.cpp?rev=188677&r1=188676&r2=188677&view=diff ============================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/ProgramState.cpp (original) +++ cfe/trunk/lib/StaticAnalyzer/Core/ProgramState.cpp Mon Aug 19 10:23:34 2013 @@ -526,6 +526,19 @@ ProgramStateRef ProgramStateManager::rem return getPersistentState(NewState); } +bool ScanReachableSymbols::scan(nonloc::LazyCompoundVal val) { + bool wasVisited = !visited.insert(val.getCVData()).second; + if (wasVisited) + return true; + + 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(); + 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)) @@ -535,10 +548,9 @@ bool ScanReachableSymbols::scan(nonloc:: } bool ScanReachableSymbols::scan(const SymExpr *sym) { - unsigned &isVisited = visited[sym]; - if (isVisited) + bool wasVisited = !visited.insert(sym).second; + if (wasVisited) return true; - isVisited = 1; if (!visitor.VisitSymbol(sym)) return false; @@ -570,16 +582,8 @@ bool ScanReachableSymbols::scan(SVal val 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()); @@ -600,11 +604,9 @@ bool ScanReachableSymbols::scan(const Me if (isa<MemSpaceRegion>(R)) return true; - unsigned &isVisited = visited[R]; - if (isVisited) + bool wasVisited = !visited.insert(R).second; + if (wasVisited) return true; - isVisited = 1; - if (!visitor.VisitMemRegion(R)) return false; _______________________________________________ cfe-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
