[analyzer] Exploration strategy prioritizing unexplored nodes first
authorGeorge Karpenkov <ekarpenkov@apple.com>
Mon, 26 Feb 2018 22:14:18 +0000 (22:14 +0000)
committerGeorge Karpenkov <ekarpenkov@apple.com>
Mon, 26 Feb 2018 22:14:18 +0000 (22:14 +0000)
commit6dcbc1dbb387cf465090cffece6fccc1564233ab
tree76347cf4cef1eafc0df27c7090eff1eaca8648d5
parent1d3e49e781a38bf9e2efd5ed9e001f92602e5552
[analyzer] Exploration strategy prioritizing unexplored nodes first

See D42775 for discussion.  Turns out, just exploring nodes which
weren't explored first is not quite enough, as e.g. the first quick
traversal resulting in a report can mark everything as "visited", and
then subsequent traversals of the same region will get all the pitfalls
of DFS.
Priority queue-based approach in comparison shows much greater
increase in coverage and even performance, without sacrificing memory.

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

llvm-svn: 326136
clang/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h
clang/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h
clang/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
clang/lib/StaticAnalyzer/Core/CoreEngine.cpp
clang/test/Analysis/exploration_order/prefer_unexplored.cc