<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jun 16, 2016 at 11:51 PM, Sean Silva <span dir="ltr"><<a href="mailto:chisophugis@gmail.com" target="_blank">chisophugis@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 Thu, Jun 16, 2016 at 11:07 PM, Xinliang David Li <span dir="ltr"><<a href="mailto:davidxl@google.com" target="_blank">davidxl@google.com</a>></span> wrote:<br><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"><br><div class="gmail_extra"><br><div class="gmail_quote"><div><div>On Thu, Jun 16, 2016 at 10:47 PM, Sean Silva <span dir="ltr"><<a href="mailto:chisophugis@gmail.com" target="_blank">chisophugis@gmail.com</a>></span> wrote:<br><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"><br><div class="gmail_extra"><br><div class="gmail_quote"><div><div>On Thu, Jun 16, 2016 at 9:53 PM, Xinliang David Li <span dir="ltr"><<a href="mailto:davidxl@google.com" target="_blank">davidxl@google.com</a>></span> wrote:<br><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"><br><div class="gmail_extra"><br><div class="gmail_quote"><span>On Thu, Jun 16, 2016 at 11:12 AM, Sanjoy Das <span dir="ltr"><<a href="mailto:sanjoy@playingwithpointers.com" target="_blank">sanjoy@playingwithpointers.com</a>></span> wrote:<br></span><div><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">Hi Sean,<br>
<span><br>
On Thu, Jun 16, 2016 at 4:48 AM, Sean Silva via llvm-dev<br>
<<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<br>
> One question is what invariants we want to provide for the visitation.<br>
><br>
> For example, should a CGSCC pass be able to assume that all "child" SCC's<br>
> (SCC's it can reach via direct calls emanating from the SCC being visited)<br>
> have already been visited? Currently I don't think it can, and IIRC from the<br>
> discussion at the social this is one thing that Chandler is hoping to fix.<br>
> The "ref edge" notion in LazyCallGraph ensures that we cannot create a call<br>
> edge (devirtualizing a ref edge) that will point at an SCC that has not yet<br>
> been visited.<br>
><br>
> E.g. consider this graph:<br>
><br>
> digraph G {<br>
> A -> B; B -> A; // SCC {A,B}<br>
> S -> T; T -> S; // SCC {S,T}<br>
> X -> Y; Y -> X; // SCC {X,Y}<br>
><br>
> B -> X;<br>
> B -> S;<br>
> T -> Y [label="Ref edge that is devirtualized\nwhen visiting SCC<br>
> {S,T}",constraint=false,style=dashed]<br>
> }<br>
><br>
> (can visualize conveniently at <a href="http://www.webgraphviz.com/" rel="noreferrer" target="_blank">http://www.webgraphviz.com/</a> or I have put an<br>
> image at <a href="http://reviews.llvm.org/F2073104" rel="noreferrer" target="_blank">http://reviews.llvm.org/F2073104</a>)<br>
><br>
> If we do not consider the ref graph, then it is possible for SCC {S,T} to be<br>
<br>
</span>I'm not sure why you wouldn't consider the ref graph? I think the<br>
general idea is to visit RefSCCs in bottom up order, and when visiting<br>
a RefSCC, visiting the SCC's inside the RefSCC in bottom up order.<br>
<br>
So in your example, given the edges you've shown, we will visit {X,Y}<br>
before visiting {S,T}.<br>
<span><br>
> A more complicated case is when SCC {S,T} and SCC {X,Y} both call into each<br>
> other via function pointers. So eventually after devirtualizing the calls in<br>
> both directions there will be a single SCC {S,T,X,Y}.<br>
><br>
> digraph G {<br>
> A -> B; B -> A; // SCC {A,B}<br>
> S -> T; T -> S; // SCC {S,T}<br>
> X -> Y; Y -> X; // SCC {X,Y}<br>
><br>
> B -> X;<br>
> B -> S;<br>
> T -> Y [label="Ref edge that is devirtualized\nwhen visiting SCC<br>
> {S,T}",constraint=false,style=dashed]<br>
> X -> S [label="Ref edge that is devirtualized\nwhen visiting SCC<br>
> {X,Y}",constraint=false,style=dashed]<br>
> }<br>
><br>
> (rendering at: <a href="http://reviews.llvm.org/F2073479" rel="noreferrer" target="_blank">http://reviews.llvm.org/F2073479</a>)<br>
><br>
> Due to the cyclic dependence there is no SCC visitation order that can<br>
> directly provide the invariant above. Indeed, the problem of maintaining the<br>
<br>
</span>I think the workflow in the above will (roughly) be:<br>
<br>
Visit the RefSCC {X,Y,S,T}<br></blockquote><div><br></div></div></div><div>Are we sure RefSCC has ref edges between {X, Y} and {S, T} in this case? I may miss the code handling it.</div></div></div></div></blockquote><div><br></div></div></div><div>The ref graph is conservative and so it would have the appropriate edges.</div><div><a href="https://github.com/llvm-project/llvm-project/blob/master/llvm/lib/Analysis/LazyCallGraph.cpp#L90" target="_blank">https://github.com/llvm-project/llvm-project/blob/master/llvm/lib/Analysis/LazyCallGraph.cpp#L90</a></div></div></div></div></blockquote><div><br></div><div><br></div></div></div><div>That is where the confusion is -- the findReferences's function body only handles constant operands which may be function addresses. Did I miss something obvious?</div></div></div></div></blockquote><div><br></div></div></div><div>It is somewhat subtle. There are 3 potential meanings of "call graph" in this thread:</div><div>1. The graph of *direct calls* in the current module. (this is mutated during optimization)</div><div>2. A supergraph of 1., conservatively chosen such 1. remains a subgraph under arbitrary semantics-preserving function transformations (note: 2. and 1. must be updated in sync during deletion of functions).</div><div>3. The conservative graph representing all edges which may exist *at runtime*.</div><div><br></div><div>LazyCallGraph models 1. (the "call graph") and 2. (the "ref graph"). It does not model 3.</div><div>The search for constants in findReferences guarantees that we find (a conserative superset of) all call destinations addresses that transformations may add direct calls (and hence update 1.).</div><div><br></div><div>The existing CallGraph data structure (used by e.g. the old PM CGSCC visitation) only models 1.</div><span class=""><div><br></div><div> </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"><div class="gmail_extra"><div class="gmail_quote"><div> Another point is that it may not be practical to model edges to indirect targets. For virtual calls, without CHA, each virtual callsite will end up referencing all potential address taken functions. </div></div></div></div></blockquote><div><br></div></span><div>In this statement, you are thinking in terms of 3.</div><div>Note that in both 1. and 2. the indirect calls are modeled as calling an external dummy node. This dummy node is *distinct* from a second external dummy node that calls all address-taken functions. (hence the indirect calls do not end up forming a RefSCC with all address taken functions).</div></div></div></div></blockquote><div><br></div><div><br></div><div>For C++ programs, most ref edges are probably from ctors and dtors that reference vtable -- they will have large fan-out of ref edges to virtual member functions they are unlikely to call. In other words, such ref edges mostly do not represent real caller->callee relationship, so I wonder what is the advantage of forming refSCC from SCCs?</div><div><br></div><div>David </div><div><br></div><div><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"><div><br></div><div>Note that `opt -dot-callgraph` can produce a graphviz file for the old PM callgraph. I'm not sure if we have one for LazyCallGraph (which has both ref graph and call graph); I'll post a patch adding one if not.<span class="HOEnZb"><font color="#888888"><br></font></span></div><span class="HOEnZb"><font color="#888888"><div><br></div><div>-- Sean Silva</div></font></span><span class=""><div><br></div><div> </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"><div class="gmail_extra"><div class="gmail_quote"><span><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"><div class="gmail_extra"><div class="gmail_quote"><div><br></div><span><div> </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"><div class="gmail_extra"><div class="gmail_quote"><span><div><br></div><div> </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">
Visit the SCC {X,Y} // arbitrary<br>
Optimize({X,Y})<br>
// Now there's an edge to {S,T}, invalidate<br>
// the analyses cached for {X,Y} and visit {S,T}<br></blockquote><div><br></div></span><div>I am not sure if this makes sense. If dynamically, the call edge from {X, Y} to {S, T} does exist, but not discovered by the analysis, then the cached {X, Y} will still be invalid, but who is going to invalidate it?</div></div></div></div></blockquote><div><br></div></span><div>I assume that if dynamically there was a call from {X,Y} to {S,T}, then the analysis would have observed an indirect call and would have behaved conservatively.</div></div></div></div></blockquote><div><br></div></span><div>See above, I did not see how indirect call is handled. Also if the result for {X, Y} is conservatively correct before the direct call edge is discovered, why bother invalidating its analysis when the call edge is exposed?</div><span><font color="#888888"><div><br></div><div>David</div></font></span><span><div> </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"><div class="gmail_extra"><div class="gmail_quote"><span><font color="#888888"><div><br></div><div>-- Sean Silva</div></font></span><span><div> </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"><div class="gmail_extra"><div class="gmail_quote"><span><font color="#888888"><div><br></div><div>David</div></font></span><span><div><br></div><div><br></div><div><br></div><div> </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">
Visit the SCC {S,T}<br>
Optimize({S,T})<br>
// Now {X,Y,S,T} collapses to form a single SCC<br>
Visit the SCC {S,T,X,Y}<br>
Optimize({S,T,X,Y})<br>
<br>
The difficult bit is to make the inner "// Now.*" bits work well.<br>
<span><font color="#888888"><br>
-- Sanjoy<br>
</font></span></blockquote></span></div><br></div></div>
</blockquote></span></div><br></div></div>
</blockquote></span></div><br></div></div>
</blockquote></span></div><br></div></div>
</blockquote></div><br></div></div>