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

[Xinliang David Li 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}.
>
>
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>