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

[Sanjoy Das via llvm-dev]

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

-- Sanjoy