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

[Sean Silva via llvm-dev]

On Thu, Jun 16, 2016 at 9:53 PM, Xinliang David Li <davidxl at google.com>
wrote:

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

The ref graph is conservative and so it would have the appropriate edges.
https://github.com/llvm-project/llvm-project/blob/master/llvm/lib/Analysis/LazyCallGraph.cpp#L90


>
>
>
>>    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?
>

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.

-- Sean Silva


>
> 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/2d489762/attachment.html>