<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">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: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 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>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? 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><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><span class=""><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><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><div><br></div><div>David</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_extra"><div class="gmail_quote"><span class="HOEnZb"><font color="#888888"><div><br></div><div>-- Sean Silva</div></font></span><span class=""><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></div><br></div></div>