[cfe-dev] [analyzer] exploration strategies and paths

[Anna Zaks via cfe-dev]

> On Jan 29, 2018, at 4:12 PM, George Karpenkov via cfe-dev <cfe-dev at lists.llvm.org> wrote:
> 
> Hi All,
> 
> I was investigating recently bug reports with very long analyzer paths (more than a few hundred nodes).
> In many of such cases the path is long for no good reason: namely, the analyzer would go 3 times around the loop before
> going further.
> The issue is surprisingly common, and it was exacerbated with a recent bump of analyzer thresholds.
> 
> The problem is reproduced on the following file:
> 
> ```
> extern int coin();
> 
> int foo() {
>    int *x = 0;
>    while (coin()) {
>        if (coin())
>            return *x;
>    }
>    return 0;
> }
> 
> void bar() {
>    while(coin())
>        if (coin())
>            foo();
> }
> ```
> 
> While a shortest path to the error does not loop around, the current version of the analyzer
> will go around the loop three times before going further.
> (and we are quite fortunate that the unrolling limit for loops is three, otherwise it would keep going
> until the unrolling limit is reached).
> 
> Multiple issues were discovered during the investigation.
> 
> 1. Analyzer queue does not have a concept of priority, and performs a simple DFS by default.
> Thus if the successor of the if-branch under the loop in “bar" containing the desired destination is generated second,
> it will never be evaluated until the loop exploration limit is exhausted.
> 
> 2. The previous issue slows down the exploration, but is not enough to get a pathological behavior of ultra-long paths.
> The second problem is a combination of:
> 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,
> and the resulting node will have a block counter associated with B.
> b) The issue in (a) is triggered due to our heuristic to abandon the function’s exploration and switch to conservative evaluation
> if we are already *inside* the function and the block limit has been reached.
> 
> Issue (1) combined with (2-b) causes the problematic behavior: the issue is discovered on the longest path first,
> and by the time the shortest path gets to “bar”, the block limit is already reached, and the switch to conservative evaluation is performed.
> 
> Thus there are two mitigation strategies currently being evaluated:
> 
> i) Remove the heuristic in (2-b)
> ii) Use a priority queue to hold nodes which should be explored; prefer nodes which give new source code coverage over others
> (or alternatively prefer nodes with least depth of loop stack)
> 
> Me and Artem have evaluated the option (i) and the results were surprisingly good: some reports disappear, and slightly more reports reappear.
> The quality of the new reports seems to be slightly better, and I am still trying to figure out exact reasons.
> I suspect merges resulting from heuristic (2-b) cause us to lose some actually valid reports.
> 
> Option (ii) has not been evaluated fully yet, but current experiments show slightly more reports (5-10%), and a radical decline in report lengths
> (e.g. from 400+ to <100 for largest reports)
> 
> Are there any thoughts on the matter?
> 
> Personally I think we should do both (i) and (ii), even if they would shake up the results.
> - 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,
> I think the data does not validate the approach.

Attached is some of the data I used to justify this change in early 2012 when we just turned on inlining and were looking at heuristics to increase coverage. I did see more reports (10% increase in reports per second). There were more heuristics added after that. 

> 
> - Option (ii) is AFAIK how most similar engines work, and should get us much larger coverage (and shorter paths) for the same node budget,
> 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
> increase the analyzer budget or to increase the unroll limit.
> 

What is the memory and performance impact of using the priority queue?


-------------- next part --------------
A non-text attachment was scrubbed...
Name: Inlining_numbers.pdf
Type: application/pdf
Size: 22436 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20180130/f6ac9e3b/attachment.pdf>
-------------- next part --------------

> George
> 
> 
> 
> _______________________________________________
> cfe-dev mailing list
> cfe-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev