<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On 4 May 2016 at 15:37, Manuel Klimek <span dir="ltr"><<a href="mailto:klimek@google.com" target="_blank">klimek@google.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"><div class="gmail_quote"><span class=""><div dir="ltr">On Wed, May 4, 2016 at 3:30 PM Gábor Horváth <<a href="mailto:xazax.hun@gmail.com" target="_blank">xazax.hun@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On 4 May 2016 at 15:28, Manuel Klimek <span dir="ltr"><<a href="mailto:klimek@google.com" target="_blank">klimek@google.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"><div class="gmail_quote"><span><div dir="ltr">On Wed, May 4, 2016 at 3:09 PM Gábor Horváth <<a href="mailto:xazax.hun@gmail.com" target="_blank">xazax.hun@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><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/pipermail/cfe-dev/2015-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></div></div></div></blockquote><div><br></div></span><div>I agree that we want cross translation unit analysis to be simpler to implement, but I think that parallelization of single steps will still be key for usability. Thus, I'm not convinced the "one large glob" approach is going to play out (but I might well be wrong).</div><span><div><br></div></span></div></div></blockquote><div><br></div></div></div></div><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div>Sorry for omitting this information, the serialized ASTs are actually not one large glob, but one for each translation unit. Are you comfortable with this level of granularity?<br></div></div></div></div></blockquote><div><br></div></span><div>Ah, sorry, I misread. That's definitely more interesting. Any ideas on whether we can also shard this?</div><div>For example, can we produce an AST of all directly called functions for each translation unit? (that will contain some denormalization, but on the other hand would enable effectively sharding the computation across machines)</div></div></div></blockquote><div><br><br></div><div>I think right now the serialized ASTs are just binary AST dumps. As far as I remember during the import there is an assumption: for each function body all the required type declarations/definitions are available. I think it is possible to do sharding but implementing this is non trivial and would require significant amount of engineering. Right now I think the best way (in terms of effort needed to get it done) to distribute the analysis across machines is to export as little redundant information as possible, so it is feasible to store a copy of the serialized ASTs on each of the machines.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_quote"><span class=""><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_quote"><span><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><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></span></div></div>
</blockquote></div></div></div></blockquote></span></div></div>
</blockquote></div><br></div></div>