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

[Sean Silva via llvm-dev]

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>