<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">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><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi Sean,<br>
<span class=""><br>
On Thu, Jun 16, 2016 at 4:48 AM, Sean Silva via llvm-dev<br>
<<a href="mailto:llvm-dev@lists.llvm.org">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 class=""><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>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><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;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><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><br></div><div>David</div><div><br></div><div><br></div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;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 class="HOEnZb"><font color="#888888"><br>
-- Sanjoy<br>
</font></span></blockquote></div><br></div></div>