<div dir="ltr"><div>Hi George, Artem,<br><br></div>I am glad that you are looking into this problem!<br><div class="gmail_extra"><br><div class="gmail_quote">On 30 January 2018 at 01:12, George Karpenkov via cfe-dev <span dir="ltr"><<a href="mailto:cfe-dev@lists.llvm.org" target="_blank">cfe-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi All,<br>
<br>
I was investigating recently bug reports with very long analyzer paths (more than a few hundred nodes).<br>
In many of such cases the path is long for no good reason: namely, the analyzer would go 3 times around the loop before<br>
going further.<br>
The issue is surprisingly common, and it was exacerbated with a recent bump of analyzer thresholds.<br>
<br>
The problem is reproduced on the following file:<br>
<br>
```<br>
extern int coin();<br>
<br>
int foo() {<br>
int *x = 0;<br>
while (coin()) {<br>
if (coin())<br>
return *x;<br>
}<br>
return 0;<br>
}<br>
<br>
void bar() {<br>
while(coin())<br>
if (coin())<br>
foo();<br>
}<br>
```<br>
<br>
While a shortest path to the error does not loop around, the current version of the analyzer<br>
will go around the loop three times before going further.<br>
(and we are quite fortunate that the unrolling limit for loops is three, otherwise it would keep going<br>
until the unrolling limit is reached).<br>
<br>
Multiple issues were discovered during the investigation.<br>
<br>
1. Analyzer queue does not have a concept of priority, and performs a simple DFS by default.<br>
Thus if the successor of the if-branch under the loop in “bar" containing the desired destination is generated second,<br>
it will never be evaluated until the loop exploration limit is exhausted.<br>
<br>
2. The previous issue slows down the exploration, but is not enough to get a pathological behavior of ultra-long paths.<br>
The second problem is a combination of:<br>
a) Block counter is not a part of a node's identity, and node A with a small block counter can be merged into a node B with a large block counter,<br>
and the resulting node will have a block counter associated with B.<br></blockquote><div><br></div><div>Sorry for the questions, just wanted to clarify some things. You mean ExplodedNodes? By merge, you mean the same thing as "caching-out"?<br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
b) The issue in (a) is triggered due to our heuristic to abandon the function’s exploration and switch to conservative evaluation<br>
if we are already *inside* the function and the block limit has been reached.<br>
<br>
Issue (1) combined with (2-b) causes the problematic behavior: the issue is discovered on the longest path first,<br>
and by the time the shortest path gets to “bar”, the block limit is already reached, and the switch to conservative evaluation is performed.<br>
<br>
Thus there are two mitigation strategies currently being evaluated:<br>
<br>
i) Remove the heuristic in (2-b)<br>
ii) Use a priority queue to hold nodes which should be explored; prefer nodes which give new source code coverage over others<br>
(or alternatively prefer nodes with least depth of loop stack)<br>
<br>
Me and Artem have evaluated the option (i) and the results were surprisingly good: some reports disappear, and slightly more reports reappear.<br>
The quality of the new reports seems to be slightly better, and I am still trying to figure out exact reasons.<br>
I suspect merges resulting from heuristic (2-b) cause us to lose some actually valid reports.<br></blockquote><div><br></div><div>I also find the results surprising. If you have more information about the reasons please do not forget to follow up this thread. We are curious :)<br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
Option (ii) has not been evaluated fully yet, but current experiments show slightly more reports (5-10%), and a radical decline in report lengths<br>
(e.g. from 400+ to <100 for largest reports)<br>
<br>
Are there any thoughts on the matter?<br>
<br>
Personally I think we should do both (i) and (ii), even if they would shake up the results.<br>
- The original idea for heuristics (2-b) was to be able to produce a report even if we are out of budget, but since it actually results in less reports,<br>
I think the data does not validate the approach.<br>
<br>
- Option (ii) is AFAIK how most similar engines work, and should get us much larger coverage (and shorter paths) for the same node budget,<br>
even at the cost of log(N) overhead of the priority queue. Moreover, not having the priority queue will bite us later if we ever decide to further<br>
increase the analyzer budget or to increase the unroll limit.<br></blockquote><div><br></div><div>I wonder what will the performance implication be. But I also like the idea of having a priority queue. If we find that we get more and better report<br></div><div>but also have worse performance, we can also consider reducing the analysis budget slightly. <br><br></div><div>Regards,<br></div><div>Gábor<br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
George<br>
<br>
<br>
<br>
______________________________<wbr>_________________<br>
cfe-dev mailing list<br>
<a href="mailto:cfe-dev@lists.llvm.org">cfe-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/cfe-dev</a><br>
</blockquote></div><br></div></div>