[cfe-dev] [Analyzer] Attempting to speed up static analysis

[Ben Craig via cfe-dev]

I am trying to speed up the static analyzer.  I also haven’t really worked
on LLVM or Clang much in the past, so some of this may be old news, or
naïve, or just plain wrong.  Regardless, here are some of the things I’ve
discovered while profiling and experimenting in the code base:

 

1.       Getting consistent static analysis times is difficult.  This has
been making it difficult for me to quantify the change in performance as I
make changes.  If anyone has suggestions, or even a standard benchmark to
use, then it would help me out a lot.

2.       For my toy test case, roughly 10% of the CPU’s time is spent in the
checkers (inclusive time / time including children).  This seems low.

3.       Roughly 20% (inclusive) is spent in the Immutable family of data
structures.

4.       Roughly 25% (inclusive) is spent in the llvm::FoldingSet code.
Much of this is memory / cache bound.

5.       In my toy test case, ExplodedGraph::getNode returns a new node ~99%
of the time.  The majority of the old nodes found are purge nodes, but there
are a few non-purge nodes that get returned.

 

With all this in mind, it seems reasonable for me to focus on the data
structures behind the static analyzer, rather than on the checkers.  I
suspect that there are some algorithmic changes hiding that could improve
the speed by orders of magnitude, if I only understood the underlying code
and their assumptions better.  

 

For example, with ExplodedGraph::Node, I think I am averaging 3 cache misses
per ExplodedGraph::getNode call in order to support deduplication, even
though less than 1% of lookups are going to be deduplicated.  Does anyone on
this list know if there are some reasonable criteria to know in advance if a
node needs to be stored for later deduplication?  If we know that a node
won’t / doesn’t need to be deduplicated, then we could insert the node
blindly into the hash map without looking at all the colliding nodes.

 

The other big area that I’m confused by is the use and purpose of the
ImmutableMap typedef Environment::BindingsTy, which maps EnvironmentEntry
keys to SVal values.  5% of my time is getting spent in this instantiations
ImmutableMap::Factory::add, largely because of a call to getCanonicalTree.
Why is ImmutableMap being used instead of alternative associative types?  Of
particular note is that even iteration is expensive because ImmutableMap
nodes can’t know their parent.  There are some other ImmutableMaps being
used, but I’m hoping that explanations of the EnvironmentEntry->SVal
instantiation will help me understand the other instantiations.

 

Question summary:

1.       Is there a good, existing benchmark for static analysis that I
should be using?

2.       Is there some reasonable criteria to know in advance if an
ExplodedNode needs to be stored for later deduplication?

3.       Why is ImmutableMap<EnvironmentEntry, SVal> being used instead of
std::map, std::hash_map, or even llvmFoldingSet?

 

Employee of Qualcomm Innovation Center, Inc.

Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux
Foundation Collaborative Project

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20150826/16483cfb/attachment.html>