<div dir="ltr">Hi!<br><div><br>A side note, it might be worth to consider IDDFS instead of DFS (<a href="https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search">https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search</a>), to get more optimal coverage patterns regardless of the "shape" of the available code. <br></div><div>What do you think?<br><br></div><div>Regards,<br></div><div>Gábor<br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On 26 July 2016 at 10:07, Gábor Horváth <span dir="ltr"><<a href="mailto:xazax.hun@gmail.com" target="_blank">xazax.hun@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote"><div><div class="h5">On 15 July 2016 at 08:17, Anna Zaks <span dir="ltr"><<a href="mailto:ganna@apple.com" target="_blank">ganna@apple.com</a>></span> wrote:<br><blockquote style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" class="gmail_quote"><div style="word-wrap:break-word"><br><div><blockquote type="cite"><span><div>On Jul 12, 2016, at 4:59 AM, Gábor Horváth <<a href="mailto:xazax.hun@gmail.com" target="_blank">xazax.hun@gmail.com</a>> wrote:</div><br></span><div><div dir="ltr"><div><div><div><div><div><div><div><div><div><div><div><div><div><div><div><div>Hi!<br><br></div><div><div>(As a ping), I would like to summarize the measurements I done since the original e-mail:<br><br></div></div></div><div><div>The approach is to first serialize all the translation units to the storage, create an index of the functions, and then load them lazily on demand to achieve cross translation unit support. This does not modify the inter-procedural analysis of the Static Analyzer and could be used for Clang Tidy as well. Once a new inter-procedural analysis is introduced for the Static Analyzer, the cross tu support would profit from it immediately.<br><br></div></div></div><div><div>Benchmarks:<br><div>rAthena, a 150k LOC C project:<br></div><div>The size of the serialized ASTs was: 140MB<br></div><div>The size of the indexes: 4.4MB<br></div><div>The time of the analysis was bellow 4X<br></div>The amount of memory consumed was bellow 2X<br></div></div></div><div><div>The number of reports is 3 times more<br><br></div></div></div><div><div>Xerces, 150k LOC C++ project:<br>The size of the serialized ASTs was: 800MB<br>The size of the indexes: 90MB<br></div></div></div><div><div>The analysis time using CTU was the half of the one without CTU<br><br></div></div></div><div><div>LLVM + Clang + Clang tools extra:<br>The size of the serialized ASTs was: 45.4 GB<br>The size of the indexes: 1,6GB<br><br>Some optimization effort to reduce te size of the CFG:<br>TU ASTs after omitting function bodies from headers: 42.7 GB<br>TU ASTs after omitting STL: 34.0 GB<br>TU ASTs after skipping implicit instantiations: 21.5 GB<br>TU ASTs after omitting STL and implicit instantiations: 16.0 GB<br><br></div></div></div><div><div>Considering that the build directory of a debug build is also about 40 GB on my platform, I do not consider the size of the serialized ASTs a blocking issue. However, in case it is a concern, according to the attached statistics about the serialized AST dumps, there are some optimization possibilities in the binary format. <br><br></div></div></div><div><div>This solution also works in a multi process build/analysis environment. Some of the necessary framework, for example ASTImporter code is being accepted into mainline clang right now.<br><br></div></div></div><div><div>All in all, this approach:<br></div></div></div><div><div>- Can discover new bug reports as is.<br></div></div></div></div></div></div></div></div></div></blockquote><div><br></div>Hi Gabor,</div><div><br></div><div>I’d like to get more data on this point. We know that inlining-style inter-procedural analysis does not scale. That is the main issue with adding the cross-translation unit support to the clang static analyzer. </div><div><br></div><div>I suspect that the only way the suggested approach works is that we time out more often when the TU support is enabled. Since the static analyzer performs DFS of the paths, this means that we trade catching bugs localized within a single TU to bugs that require deep cross-TU analysis. I suspect those bugs are much harder to understand, but more, importantly, we trade coverage in a lot of cases instead of gaining it.</div></div></blockquote><div><br></div></div></div><div>Hi Anna,<br></div><div><br></div><div>Good point. Using the cross TU analysis, the analyzer has very different coverage pattern. I did not have time to look into the reports yet, but will do so soon.<br></div><span class=""><div> </div><blockquote style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" class="gmail_quote"><div style="word-wrap:break-word"><div><br></div><div>Looks like you clam that the number of bugs reported increased for one of the projects, but there is no data for all the other projects. Also, had that project ever been analyzed with the clang static analyzer before and had some of the intra-procedural bugs been fixed before you made the measurement?</div></div></blockquote><div><br></div></span><div>There is no trace of fixed static analyzer warnings in the commit logs of rAthena project. But in case issues found w/o cross tu and was fixed it can be still useful to analyze the project with a different coverage pattern.<br> </div><span class=""><blockquote style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" class="gmail_quote"><div style="word-wrap:break-word"><div> I’d like to see the absolute number of bugs reported in both cases. Also, it would be good to measure coverage and the number of times the analyzer times out in both cases. (Those statistics should be easy to generate as the tracking is already implemented by the analyzer and we used it when bringing up inter procedural analysis.)</div></div></blockquote><div><br></div></span><div>I did some measurements, and here are the results for the rAthena project:<br><br></div><div>Coverage results without cross translation unit:<br><div dir="ltr"><div><pre><span>105499</span> AnalysisConsumer <span>-</span> The <span># of basic blocks in the analyzed functions.</span>
<span>4167</span> AnalysisConsumer <span>-</span> The <span># of functions and blocks analyzed (as top level with inlining turned on).</span>
<span>10084</span> AnalysisConsumer <span>-</span> The <span># of functions at top level.</span>
<span>60.0244651798</span> AnalysisConsumer <span>-</span> The <span>%</span> of reachable basic blocks.
<span>3360</span> AnalysisConsumer <span>-</span> The maximum number of basic blocks in a function.
<span>960440</span> CoreEngine <span>-</span> The <span># of paths explored by the analyzer.</span>
<span>140425349</span> CoreEngine <span>-</span> The <span># of steps executed.</span>
<span>646201</span> ExprEngine <span>-</span> The <span># of aborted paths due to reaching the maximum block count in a top level function</span>
<span>24317519</span> ExprEngine <span>-</span> The <span># of times RemoveDeadBindings is called</span>
<span>489956</span> ExprEngine <span>-</span> The <span># of times we inlined a call</span>
<span>20300</span> ExprEngine <span>-</span> The <span># of times we re-evaluated a call without inlining</span></pre></div></div>Coverage results with cross translation unit:<br><div dir="ltr"><div><pre><span>150406</span> AnalysisConsumer <span>-</span> The <span># of basic blocks in the analyzed functions.</span>
<span>3308</span> AnalysisConsumer <span>-</span> The <span># of functions and blocks analyzed (as top level with inlining turned on).</span>
<span>9829</span> AnalysisConsumer <span>-</span> The <span># of functions at top level.</span>
<span>48.<a href="tel:9545495971" value="+19545495971" target="_blank">9545495971</a></span> AnalysisConsumer <span>-</span> The <span>%</span> of reachable basic blocks.
<span>3360</span> AnalysisConsumer <span>-</span> The maximum number of basic blocks in a function.
<span>2088751</span> CoreEngine <span>-</span> The <span># of paths explored by the analyzer.</span>
<span>345875017</span> CoreEngine <span>-</span> The <span># of steps executed.</span>
<span>464409</span> ExprEngine <span>-</span> The <span># of aborted paths due to reaching the maximum block count in a top level function</span>
<span>64756893</span> ExprEngine <span>-</span> The <span># of times RemoveDeadBindings is called</span>
<span>2176922</span> ExprEngine <span>-</span> The <span># of times we inlined a call</span>
<span>44215</span> ExprEngine <span>-</span> The <span># of times we re-evaluated a call without inlining</span></pre></div></div></div><div><br></div><div>Note that, the results are not fully precise for the following reasons:<br></div><div>* I simply collected and merged the results for each translation unit. In the cross translation unit case a function might be analyzed from multiple translation unit, that might include duplicates in the number of analyzed basic blocks. Inline functions in headers might cause the same effects even when cross translation unit is turned off.<br></div><div>* The coverage % is also imprecise. Basic blocks not reached in one TU might reached from another TU during the analysis.<br><br></div><div>Even though these numbers are just hints, they show about 50% increase in the number of analyzed blocks. This makes me think that the overall coverage is increased (however as you pointed out, the pattern is different). It is also worth noting that the number of functions analyzed as top level decreased. <br><br></div><div>In case the issues reported this way are too hard to understand, the heuristics might be tuned in case this feature is turned on. This is no silver bullet of course, but once a new interprocedural analysis is introduced, this would provide an easy way to evaluate it in a cross tu analysis.<br></div><div><br></div><div>What do you think?<br><br></div><div>Regards,<br></div><div>Gábor<br></div><div><div class="h5"><div><br></div><blockquote style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" class="gmail_quote"><div style="word-wrap:break-word"><div><br></div><div>Thank you,</div><div>Anna.</div><div><div><div><br><blockquote type="cite"><div><div dir="ltr"><div><div><div><div>- Feasible to implement, does not need sever modifications to the Static Analyzer or Clang Tidy.</div></div></div></div></div></div></blockquote></div></div></div><div><blockquote type="cite"><div><div><div><div dir="ltr"><div><div><div>- Has acceptable performance for lots of the real world projects. <br><br></div>I think, this would be a useful addition to the clang source tree. Do you agree?<br><br></div>Regards,<br></div>Gábor<br><div><div><div><div><div><div><div><div><div><div><div><div><div><div><div><div><div><div><br></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div><div class="gmail_extra"><br><div class="gmail_quote">On 4 May 2016 at 15:09, Gábor Horváth <span dir="ltr"><<a href="mailto:xazax.hun@gmail.com" target="_blank">xazax.hun@gmail.com</a>></span> wrote:<br><blockquote style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" class="gmail_quote"><div dir="ltr"><div><div><div><div><div><div>Hi!<br><br></div>This e-mail is a proposal based on the work done by Yury Gibrov et al.: <a href="http://lists.llvm.org/pipermail/cfe-dev/2015-December/046299.html" target="_blank">http://lists.llvm.org/<wbr>pipermail/cfe-dev/2015-<wbr>December/046299.html</a><b><br><br></b></div>They accomplished a two pass analysis, the first pass is serializing the AST of every translation unit and creates an index of functions, the second pass does the real analysis, which can load the AST of function bodies on demand.<br><br></div>This approach can be used to achieve cross translation unit analysis for the clang Static Analyzer to some extent, but similar approach could be applicable to Clang Tidy and other clang based tools.<br><br></div>While this method is not likely to be a silver bullet for the Static Analyzer, I did some benchmarks to see how feasible this approach is. The baseline was running the Static Analyzer without the two pass analyis, the second one was running using the framework linked above.<br><br></div><div>For a 150k LOC C projects I got the following results:<br></div><div>The size of the serialized ASTs was: 140MB<br></div><div>The size of the indexes (textual representation): 4.4MB<br></div><div>The time of the analysis was bellow 4X<br></div><div>The amount of memory consumed was bellow 2X<br><br></div><div>All in all it looks like a feasible approach for some use cases.<br><br></div><div>I also tried to do a benchmark on the LLVM+Clang codebase. Unfortunately I was not able to run the analysis due to some missing features in the AST Importer. But I was able to serialize the ASTs and generate the indices:<br></div><div>The siye of the serialized ASTs: 45.4 GB<br></div><div>The siye of the function index: 1,6GB<br><br></div><div>While these numbers are less promising, I think there are some opportunities to reduce them significantly.<br><br></div><div>I propose the introduction of an analysis mode for exporting ASTs. In analysis mode the AST exporter would not emit the function body of a function for several cases:<br></div><div>- In case a function is defined in a header, do not emit the body.<br></div><div>- In case the function was defined in an implicit template specialisation, do not emit the body.<br><br></div><div>I think after similar optimizations it might be feasible to use this approach on LLVM scale projects as well, and it would be much easier to implement Clang based tools that can utilize cross translation unit capabilities.<br><br></div><div>In case the analyzer gets a new interprocedural analysis method that would increase the performance the users of this framework would profit from that approach immediately.<br><br></div><div>Does a framework like this worth mainlining and working on? What do you think?<br><br></div><div>(Note that, AST Importer related improvements are already being mainlined by Yury et al. My question is about the "analysis mode" for exporting ASTs, and a general framework to consume those exported ASTs.)<br></div><div><br></div><div>Regards,<br></div><div>Gábor<br></div><div><br></div><div><br><br></div></div></div>
</blockquote></div><br></div>
</div></div><span><statistics.json></span></div></blockquote></div><br></div></blockquote></div></div></div><br></div></div>
</blockquote></div><br></div>