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

[Sean Silva 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?


The simple answer is that this is the current state of things. The SCC
visitation logic in the old PM does not consider the ref graph.

So in some sense the question is why *should* we consider the ref graph?
What is it buying us? Presumably this will take the form of some invariant
on the `run(SCC &)` calls. But I have yet to see any explicit statement of
an invariant that it gives us.

For example, the examples I gave show that without bailing out in the
middle of a cgscc pass manager (e.g. after the `function(...simplifications
that can devirtualize...)`) then we cannot even guarantee that the thing
passed to the `run(SCC &)` function is actually an SCC.


>   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}
>    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}
>    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.
>

But consider that Optimize({S,T}) might be of the form:
`cgscc(function(...simplifications
that can devirtualize...),foo-cgscc-pass)`.
After running `function(...simplifications that can devirtualize...)` we
would end up running `foo-cgscc-pass` on {S,T} which is no longer an SCC
anymore.
What is the invariant here? What do we actually guarantee for the `run(SCC
&)` function?

-- Sean Silva


>
> -- Sanjoy
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160616/ca6cb463/attachment.html>