llvm dev - Jun 2016 - Intended behavior of CGSCC pass manager.

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>

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>

Hi David,

On Thu, Jun 16, 2016 at 9:53 PM, Xinliang David Li <davidxl at google.com>
wrote:
>> 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.
I was going by the diagram -- the diagram explicitly has ref edges
between {X,Y} and {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}
>
>
> 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 cannot answer this with authority, since I'm not the one working on
the callgraph, but I'll jot down what I think is the case:

Whatever you analyze on {X,Y} will have to be conservative around
indirect calls that haven't yet been devirtualized.  Say you're trying
to prove that an SCC is readnone.  With the SCC iteration order,
you'll have to do:

  for every call site in CurrentSCC
    if the call is indirect, then ReadWrite, break out of loop
    if the call is to SSC X, then
      CurrentSCC.MemoryEffect.unionWith(X.MemoryEffect)  // L1

To avoid re-walking the call-sites in common cases like the above,
we'll have to add a "HasNonAnalyzedCalls" bit on SCCs that
we'll set
when building the call graph (Chandler had promised this a few socials
ago).  That would let us directly walk the outgoing call edges (the
bit would be the moral equivalent of having a call edge to
"external").

The invariant provided by the bottom up SCC iteration order, as I
understand it, assures us that in line L1, X.MemoryEffect is as
precise as it can be.  When we analyze a call site and the call target
is in a ReadOnly SCC, we are assured that the call target SCC could
not have been proved ReadNone -- we've already tried our best.  So in
a way the bottom up order gives us precision, not correctness.

-- Sanjoy

On Thu, Jun 16, 2016 at 10:47 PM, Sean Silva <chisophugis at gmail.com>
wrote:
>
>
> 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
>

That is where the confusion is -- the findReferences's function body only
handles constant operands which may be function addresses.  Did I miss
something obvious?  Another point is that it may not be practical to model
edges to indirect targets. For virtual calls, without CHA, each virtual
callsite will end up referencing all potential address taken functions.
>
>
>
>>
>>
>>
>>>    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.
>
See above, I did not see how indirect call is handled. Also if the result
for {X, Y} is conservatively correct before the direct call edge is
discovered, why bother invalidating its analysis when the call edge is
exposed?

David

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

On Thu, Jun 16, 2016 at 10:48 PM, Sanjoy Das <sanjoy at
playingwithpointers.com
> wrote:
> Hi David,
>
> On Thu, Jun 16, 2016 at 9:53 PM, Xinliang David Li <davidxl at
google.com>
> wrote:
> >> 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.
>
> I was going by the diagram -- the diagram explicitly has ref edges
> between {X,Y} and {S,T}.
>
To clarify: initially the indirect calls are represented by a call edge to
a dummy "unknown" node something like:
http://reviews.llvm.org/F2078426
These call edges to "unknown" are what force the conservative
analysis.

>
> >>    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 cannot answer this with authority, since I'm not the one working on
> the callgraph, but I'll jot down what I think is the case:
>
> Whatever you analyze on {X,Y} will have to be conservative around
> indirect calls that haven't yet been devirtualized.  Say you're
trying
> to prove that an SCC is readnone.  With the SCC iteration order,
> you'll have to do:
>
>   for every call site in CurrentSCC
>     if the call is indirect, then ReadWrite, break out of loop
>     if the call is to SSC X, then
>       CurrentSCC.MemoryEffect.unionWith(X.MemoryEffect)  // L1
>
> To avoid re-walking the call-sites in common cases like the above,
> we'll have to add a "HasNonAnalyzedCalls" bit on SCCs that
we'll set
> when building the call graph (Chandler had promised this a few socials
> ago).  That would let us directly walk the outgoing call edges (the
> bit would be the moral equivalent of having a call edge to
> "external").
>
> The invariant provided by the bottom up SCC iteration order, as I
> understand it, assures us that in line L1, X.MemoryEffect is as
> precise as it can be.  When we analyze a call site and the call target
> is in a ReadOnly SCC, we are assured that the call target SCC could
> not have been proved ReadNone -- we've already tried our best.  So in
> a way the bottom up order gives us precision, not correctness.
>
To put this another way, if we were to use a cached SCC visitation order,
then after visiting all cached SCC's we may not have incorporated all
information due to devirtualized or deleted calls. We would need to
recompute SCC's and do another cached visitation in order to benefit fully
from the information. If multiple devirtualizations are needed to fully
simplify, then multiple visitations are needed to fully propagate this
information.

With dynamic updates to the SCC structure, we can get increased precision
from a single visitation and more effective bottom-up propagation.

-- Sean Silva


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

On Thu, Jun 16, 2016 at 10:48 PM, Sanjoy Das <sanjoy at
playingwithpointers.com
> wrote:
> Hi David,
>
> On Thu, Jun 16, 2016 at 9:53 PM, Xinliang David Li <davidxl at
google.com>
> wrote:
> >> 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.
>
> I was going by the diagram -- the diagram explicitly has ref edges
> between {X,Y} and {S,T}.
>
>
Ok -- I thought the example is showing indirect calls across {X, Y} and {S,
T}, and call graph builder magically discovered the ref edges between them.

> >>    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 cannot answer this with authority, since I'm not the one working on
> the callgraph, but I'll jot down what I think is the case:
>
> Whatever you analyze on {X,Y} will have to be conservative around
> indirect calls that haven't yet been devirtualized.  Say you're
trying
> to prove that an SCC is readnone.  With the SCC iteration order,
> you'll have to do:
>
>   for every call site in CurrentSCC
>     if the call is indirect, then ReadWrite, break out of loop
>     if the call is to SSC X, then
>       CurrentSCC.MemoryEffect.unionWith(X.MemoryEffect)  // L1
>
yes, ff RefSCC has such special edge to 'unknown' node to model icall,
there is no problem, or the analysis still has to walk through the IR?


>
> To avoid re-walking the call-sites in common cases like the above,
> we'll have to add a "HasNonAnalyzedCalls" bit on SCCs that
we'll set
> when building the call graph (Chandler had promised this a few socials
> ago).  That would let us directly walk the outgoing call edges (the
> bit would be the moral equivalent of having a call edge to
> "external").
>
There is a disadvantage of setting bit on SCC compared with special call
edge -- the later can be per-callsite, so elimination of the last such edge
automatically makes caller 'clean'. With the special bit, it is not so
easy
to get rid of it.

>
> The invariant provided by the bottom up SCC iteration order, as I
> understand it, assures us that in line L1, X.MemoryEffect is as
> precise as it can be.  When we analyze a call site and the call target
> is in a ReadOnly SCC, we are assured that the call target SCC could
> not have been proved ReadNone -- we've already tried our best.  So in
> a way the bottom up order gives us precision, not correctness.
>
you mean 'correctness' not 'precision'?

thanks,

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