
<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Jun 8, 2016, at 2:54 PM, Sean Silva <<a href="mailto:chisophugis@gmail.com" class="">chisophugis@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><br class="Apple-interchange-newline"><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><div class="gmail_quote" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">On Wed, Jun 8, 2016 at 9:39 AM, Daniel Berlin<span class="Apple-converted-space"> </span><span dir="ltr" class=""><<a href="mailto:dberlin@dberlin.org" target="_blank" class="">dberlin@dberlin.org</a>></span><span class="Apple-converted-space"> </span>wrote:<br class=""><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-style: solid; border-left-color: rgb(204, 204, 204); padding-left: 1ex;"><div dir="ltr" class=""><br class=""><div class="gmail_extra"><br class=""><div class="gmail_quote"><div class=""><div class="h5">On Wed, Jun 8, 2016 at 4:19 AM, Sean Silva<span class="Apple-converted-space"> </span><span dir="ltr" class=""><<a href="mailto:chisophugis@gmail.com" target="_blank" class="">chisophugis@gmail.com</a>></span><span class="Apple-converted-space"> </span>wrote:<br class=""><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-style: solid; border-left-color: rgb(204, 204, 204); padding-left: 1ex;"><div dir="ltr" class=""><div class="">Hi Chandler, Philip, Mehdi, (and llvm-dev,)</div><div class=""><br class=""></div><div class="">(this is partially a summary of some discussions that happened at the last LLVM bay area social, and partially a discussion about the direction of the CGSCC pass manager)</div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">A the last LLVM social we discussed the progress on the CGSCC pass manager. It seems like Chandler has a CGSCC pass manager working, but it is still unresolved exactly which semantics we want (more about this below) that are reasonably implementable.</div><div class=""><br class=""></div><div class="">AFAICT, there has been no public discussion about what exact semantics we ultimately want to have. We should figure that out.</div><div class=""><br class=""></div><div class="">The main difficulty which Chandler described is the apparently quite complex logic surrounding needing to run function passes nested within an SCC pass manager, while providing some guarantees about exactly what order the function passes are run. The existing CGSCC pass manager just punts on some of the problems that arise (look in CGPassManager::runOnModule, CGPassManager::RunAllPassesOnSCC, and CGPassManager::RunPassOnSCC in llvm/lib/Analysis/CallGraphSCCPass.cpp), and these are the problems that Chandler has been trying to solve.</div><div class=""><br class=""></div><div class="">(</div><div class="">Why is this "function passes inside CGSCC passes" stuff interesting? Because LLVM can do inlining on an SCC (often just a single function) and then run function passes to simplify the function(s) in the SCC before it tries to inline into a parent SCC. (the SCC visitation order is post-order)</div><div class="">For example, we may inline a bunch of code, but after inlining we can tremendously simplify the function, and we want to do so before considering this function for inlining into its callers so that we get an accurate evaluation of the inline cost.</div><div class="">Based on what Chandler said, it seems that LLVM is fairly unique in this regard and other compilers don't do this (which is why we can't just look at how other compilers solve this problem; they don't have this problem (maybe they should? or maybe we shouldn't?)). For example, he described that GCC uses different inlining "phases"; e.g. it does early inlining on the entire module, then does simplifications on the entire module, then does late inlining on the entire module; so it is not able to incrementally simplify as it inlines like LLVM does.</div><div class="">)</div><div class=""><br class=""></div><div class="">As background for what is below, the LazyCallGraph tracks two graphs: the "call graph" and the "ref graph". </div><div class="">Conceptually, the call graph is the graph of direct calls, where indirect calls and calls to external functions do not appear (or are connected to dummy nodes). The ref graph is basically the graph of all functions transitively accessible based on the globals/constants/etc. referenced by a function (e.g. if a function `foo` references a vtable that is defined in the module, there is an edge in the ref graph from `foo` to every function in the vtable).</div><div class="">The call graph is a strict subset of the ref graph.<br class=""></div><div class=""><br class=""></div><div class="">Chandler described that he had a major breakthrough in that the CGSCC pass manager only had to deal with 3 classes of modifications that can occur:</div><div class="">- a pass may e.g. propagate a load of a function pointer into an indirect call, turning it into an direct call. This requires adding an edge in the CG but not in the ref graph.</div><div class="">- a pass may take a direct call and turn it into an indirect call. This requires removing an edge from the CG, but not in the ref graph.</div><div class="">- a pass may delete a direct call. This removes an edge in the CG and also in the ref graph.</div><div class=""><br class=""></div><div class="">From the perspective of the CGSCC pass manager, these operations can affect the SCC structure. Adding an edge might merge SCC's and deleting an edge might split SCC's. Chandler mentioned that apparently the issues of splitting and merging SCC's within the current infrastructure are actually quite challenging and lead to e.g. iterator invalidation issues, and that is what he is working on.</div><div class=""><br class=""></div><div class="">(</div><div class="">The ref graph is important to guide the overall SCC visitation order because it basically represents "the largest graph that the CG may turn into due to our static analysis of this module". I.e. no transformation we can statically make in the CGSCC passes can ever cause us to need to merge SCC's in the ref graph.</div><div class="">)</div><div class=""><br class=""></div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">I have a couple overall questions/concerns:</div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">1. The ref graph can easily go quadratic. E.g.</div><div class=""><br class=""></div><div class="">typedef void (*fp)();</div><div class="">fp funcs[] = {</div><div class=""> <span class="Apple-converted-space"> </span>&foo1,</div><div class=""> <span class="Apple-converted-space"> </span>&foo2,</div><div class=""> <span class="Apple-converted-space"> </span>...</div><div class=""> <span class="Apple-converted-space"> </span>&fooN</div><div class="">}</div><div class="">void foo1() { funcs[something](); }<br class=""></div><div class="">void foo2() { funcs[something](); }</div><div class="">...</div><div class="">void fooN() { funcs[something](); }</div><div class=""><br class=""></div><div class="">One real-world case where this might come about is in the presence of vtables.</div><div class=""><br class=""></div><div class="">The existing CGSCC pass manager does not have this issue AFAIK because it does not consider the ref graph.</div><div class=""><br class=""></div><div class="">Does anybody have any info/experience about how densely connected the ref graph can get in programs that might reasonably be fed to the compiler?</div></div></blockquote><div class=""><br class=""></div><div class=""><br class=""></div></div></div><div class="">I can state that almost all call graphs of compilers include edges for indirect calls and external functions, so they are already quadratic in this sense.</div><div class=""><br class=""></div><div class="">if what you state is correct, and we don't have a conservatively correct call graph, that would be ... interesting.</div></div></div></div></blockquote><div class=""><br class=""></div><div class=""><div class="">Mehdi clarified downthread the situation (at least for me).</div><div class=""><br class=""></div><div class="">Now that I look more closely at the comments in<span class="Apple-converted-space"> </span><a href="https://github.com/llvm-mirror/llvm/blob/master/include/llvm/Analysis/LazyCallGraph.h" class="">https://github.com/llvm-mirror/llvm/blob/master/include/llvm/Analysis/LazyCallGraph.h</a><span class="Apple-converted-space"> </span>it intentionally does not model a call graph in this sense. I.e.</div><div class="">- in a traditional CG, an edge means something like "at runtime there may be a call from A->B"</div><div class="">- in the LazyCallGraph an edge (a "ref edge" as it calls it) represents something like "during optimization of this module, we may discover the existence of a direct call from A->B". There is also a distinguished subgraph of the ref graph (which I think LazyCallGraph calls just the "call graph") which represents the actual direct calls that are present in the module currently.</div><div class=""><br class=""></div><div class="">The comments in LazyCallGraph.h are quite good, but the existing CallGraph.h doesn't seem to touch on this up front in its comments in quite the same way, but it does at least say that it models with two external nodes like Mehdi mentioned:</div><div class=""><a href="https://github.com/llvm-mirror/llvm/blob/master/include/llvm/Analysis/CallGraph.h#L30" class="">https://github.com/llvm-mirror/llvm/blob/master/include/llvm/Analysis/CallGraph.h#L30</a></div><div class="">So its edges don't represent "at runtime there may be a call from A->B". But since it doesn't maintain a "ref graph" I'm not sure what the edges exactly represent.</div></div></div></div></blockquote><div><br class=""></div><div><br class=""></div><div>I thought of it as the edges are "there is a direct call from A -> B". Which is a subset of "at runtime there may be a call from A->B".</div><div><br class=""></div><div>I think that with all this discussion, it is important to distinguish that (I think) there is no "correctness" issue at stance (we won't miscompile anything), but there may be missing optimization in some cases. I think the current scheme catches most cases and when it does not we are just missing potential inlining. The question may be how much (more) cases we really need to catch with the new pass manager? </div><div>And could a first implementation not catch everything and be improved incrementally? This comes back somehow to what Hal was mentioning (reproducing the current behavior before improving it).</div><div><br class=""></div><div>-- </div><div>Mehdi</div><div><br class=""></div><div><br class=""></div><div><br class=""></div><br class=""><blockquote type="cite" class=""><div class=""><div class="gmail_quote" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><div class=""><br class=""></div><div class=""> </div><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-style: solid; border-left-color: rgb(204, 204, 204); padding-left: 1ex;"><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><div class="">The solution to most issues (large sccs, etc) that exist here that most other compilers take is to try to make the call graph more precise, not to avoid indirect/external calls in the call graph.<br class=""></div><div class=""><br class=""></div><div class="">In turn, this means the solution often take is to not have two graphs at all.</div></div></div></div></blockquote></div></div></blockquote></div><br class=""></body></html>