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

[Sanjoy Das via llvm-dev]

Hi Sean,

On Thu, Jun 16, 2016 at 5:13 PM, Sean Silva <chisophugis at gmail.com> wrote:
> The simple answer is that this is the current state of things. The SCC
> visitation logic in the old PM does not consider the ref graph.
>
> So in some sense the question is why *should* we consider the ref graph?
> What is it buying us? Presumably this will take the form of some invariant
> on the `run(SCC &)` calls. But I have yet to see any explicit statement of
> an invariant that it gives us.

I'll have think harder to give a deeper answer, but trivially the
invariant you have is run(SCCA) is called before run(SCCB) if SCCB
Refs SCCA but not the other way around.  This is just a fancy way of
re-stating that we'll iterate over RefSCC's in bottom up order, of
course; but it already helps in cases like your first example -- if we
don't iterate in bottom up RefSCC order there is no ordering between
{X,Y} and {S,T}, but we would like to visit {X,Y} before {S,T}.

> For example, the examples I gave show that without bailing out in the middle

I'm not sure what design point Chandler's is pursuing, but bailing out
in the middle of a pass manager because the data structure it was
operating on is gone is not new to LLVM.  The LoopPassManager does
exactly this when a loop is deleted (due to full unrolling, for
instance).

> of a cgscc pass manager (e.g. after the `function(...simplifications that
> can devirtualize...)`) then we cannot even guarantee that the thing passed
> to the `run(SCC &)` function is actually an SCC.
>
> But consider that Optimize({S,T}) might be of the form:
> `cgscc(function(...simplifications that can
> devirtualize...),foo-cgscc-pass)`.
> After running `function(...simplifications that can devirtualize...)` we
> would end up running `foo-cgscc-pass` on {S,T} which is no longer an SCC
> anymore.
> What is the invariant here? What do we actually guarantee for the `run(SCC
> &)` function?

As I said, one possibility is to bail out of the current pipeline, and
re-start from the new leaves (similar to what we do for the loop pass
manager today).

-- Sanjoy