[llvm-dev] Intended behavior of CGSCC pass manager.

[Xinliang David Li via llvm-dev]

On Thu, Jun 16, 2016 at 11:12 AM, Sanjoy Das <sanjoy at playingwithpointers.com
> wrote:

> Hi Sean,
>
> On Thu, Jun 16, 2016 at 4:48 AM, Sean Silva via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
> > One question is what invariants we want to provide for the visitation.
> >
> > For example, should a CGSCC pass be able to assume that all "child" SCC's
> > (SCC's it can reach via direct calls emanating from the SCC being
> visited)
> > have already been visited? Currently I don't think it can, and IIRC from
> the
> > discussion at the social this is one thing that Chandler is hoping to
> fix.
> > The "ref edge" notion in LazyCallGraph ensures that we cannot create a
> call
> > edge (devirtualizing a ref edge) that will point at an SCC that has not
> yet
> > been visited.
> >
> > E.g. consider this graph:
> >
> > digraph G {
> >   A -> B; B -> A; // SCC {A,B}
> >   S -> T; T -> S; // SCC {S,T}
> >   X -> Y; Y -> X; // SCC {X,Y}
> >
> >   B -> X;
> >   B -> S;
> >   T -> Y [label="Ref edge that is devirtualized\nwhen visiting SCC
> > {S,T}",constraint=false,style=dashed]
> > }
> >
> > (can visualize conveniently at http://www.webgraphviz.com/ or I have
> put an
> > image at http://reviews.llvm.org/F2073104)
> >
> > If we do not consider the ref graph, then it is possible for SCC {S,T}
> to be
>
> I'm not sure why you wouldn't consider the ref graph?  I think the
> general idea is to visit RefSCCs in bottom up order, and when visiting
> a RefSCC, visiting the SCC's inside the RefSCC in bottom up order.
>
> So in your example, given the edges you've shown, we will visit {X,Y}
> before visiting {S,T}.
>
> > A more complicated case is when SCC {S,T} and SCC {X,Y} both call into
> each
> > other via function pointers. So eventually after devirtualizing the
> calls in
> > both directions there will be a single SCC {S,T,X,Y}.
> >
> > digraph G {
> >   A -> B; B -> A; // SCC {A,B}
> >   S -> T; T -> S; // SCC {S,T}
> >   X -> Y; Y -> X; // SCC {X,Y}
> >
> >   B -> X;
> >   B -> S;
> >   T -> Y [label="Ref edge that is devirtualized\nwhen visiting SCC
> > {S,T}",constraint=false,style=dashed]
> >   X -> S [label="Ref edge that is devirtualized\nwhen visiting SCC
> > {X,Y}",constraint=false,style=dashed]
> > }
> >
> > (rendering at: http://reviews.llvm.org/F2073479)
> >
> > Due to the cyclic dependence there is no SCC visitation order that can
> > directly provide the invariant above. Indeed, the problem of maintaining
> the
>
> I think the workflow in the above will (roughly) be:
>
>  Visit the RefSCC {X,Y,S,T}
>

Are we sure RefSCC has ref edges between {X, Y} and {S, T} in this case?  I
may miss the code handling it.



>    Visit the SCC {X,Y} // arbitrary
>      Optimize({X,Y})
>      // Now there's an edge to {S,T}, invalidate
>      // the analyses cached for {X,Y} and visit {S,T}
>

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?

David





>    Visit the SCC {S,T}
>      Optimize({S,T})
>      // Now {X,Y,S,T} collapses to form a single SCC
>    Visit the SCC {S,T,X,Y}
>      Optimize({S,T,X,Y})
>
> The difficult bit is to make the inner "// Now.*" bits work well.
>
> -- Sanjoy
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160616/3fb32159/attachment.html>