<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta name=Generator content="Microsoft Word 15 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:#954F72;
text-decoration:underline;}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
{mso-style-priority:34;
margin-top:0in;
margin-right:0in;
margin-bottom:0in;
margin-left:.5in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
span.EmailStyle18
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:windowtext;}
span.EmailStyle19
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:687607093;
mso-list-type:hybrid;
mso-list-template-ids:-492155498 67698703 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l0:level1
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l0:level4
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l0:level7
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l1
{mso-list-id:1633752999;
mso-list-type:hybrid;
mso-list-template-ids:-794813116 67698703 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l1:level1
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l1:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l1:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l1:level4
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l1:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l1:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l1:level7
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l1:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l1:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
ol
{margin-bottom:0in;}
ul
{margin-bottom:0in;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=EN-US link="#0563C1" vlink="#954F72"><div class=WordSection1><p class=MsoNormal>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:<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoListParagraph style='text-indent:-.25in;mso-list:l0 level1 lfo2'><![if !supportLists]><span style='mso-list:Ignore'>1.<span style='font:7.0pt "Times New Roman"'> </span></span><![endif]>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.<o:p></o:p></p><p class=MsoListParagraph style='text-indent:-.25in;mso-list:l0 level1 lfo2'><![if !supportLists]><span style='mso-list:Ignore'>2.<span style='font:7.0pt "Times New Roman"'> </span></span><![endif]>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.<o:p></o:p></p><p class=MsoListParagraph style='text-indent:-.25in;mso-list:l0 level1 lfo2'><![if !supportLists]><span style='mso-list:Ignore'>3.<span style='font:7.0pt "Times New Roman"'> </span></span><![endif]>Roughly 20% (inclusive) is spent in the Immutable family of data structures.<o:p></o:p></p><p class=MsoListParagraph style='text-indent:-.25in;mso-list:l0 level1 lfo2'><![if !supportLists]><span style='mso-list:Ignore'>4.<span style='font:7.0pt "Times New Roman"'> </span></span><![endif]>Roughly 25% (inclusive) is spent in the llvm::FoldingSet code. Much of this is memory / cache bound.<o:p></o:p></p><p class=MsoListParagraph style='text-indent:-.25in;mso-list:l0 level1 lfo2'><![if !supportLists]><span style='mso-list:Ignore'>5.<span style='font:7.0pt "Times New Roman"'> </span></span><![endif]>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.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>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. <o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>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.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>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.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Question summary:<o:p></o:p></p><p class=MsoListParagraph style='text-indent:-.25in;mso-list:l1 level1 lfo4'><![if !supportLists]><span style='mso-list:Ignore'>1.<span style='font:7.0pt "Times New Roman"'> </span></span><![endif]>Is there a good, existing benchmark for static analysis that I should be using?<o:p></o:p></p><p class=MsoListParagraph style='text-indent:-.25in;mso-list:l1 level1 lfo4'><![if !supportLists]><span style='mso-list:Ignore'>2.<span style='font:7.0pt "Times New Roman"'> </span></span><![endif]>Is there some reasonable criteria to know in advance if an ExplodedNode needs to be stored for later deduplication?<o:p></o:p></p><p class=MsoListParagraph style='text-indent:-.25in;mso-list:l1 level1 lfo4'><![if !supportLists]><span style='mso-list:Ignore'>3.<span style='font:7.0pt "Times New Roman"'> </span></span><![endif]>Why is ImmutableMap<EnvironmentEntry, SVal> being used instead of std::map, std::hash_map, or even llvmFoldingSet?<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>Employee of Qualcomm Innovation Center, Inc.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project<o:p></o:p></span></p><p class=MsoNormal><o:p> </o:p></p></div></body></html>