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

[Sanjoy Das via llvm-dev]

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