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

[Xinliang David Li via llvm-dev]

On Wed, Jun 8, 2016 at 5:54 PM, Sanjoy Das <sanjoy at playingwithpointers.com>
wrote:

> Hi David,
>
> On Wed, Jun 8, 2016 at 4:20 PM, Xinliang David Li <xinliangli at gmail.com>
> wrote:
> > Is it in the category of invalidating the iterator while iterating' which
> > feels very wrong to me.  We should avoid going there and find better
> ways to
> > solve the motivating problems (perhaps defining them more clearly first
> ?).
>
> I'm not a 100% sure of what you meant by that, so I'll try to give a
> general answer, and hope that it covers the points you wanted to
> raise. :)
>
> In the scheme above I'm not trying to solve iterator invalidation --
> I'm trying to solve the following problem: the CGSCC pass manager ran
> the inliner and a set of function passes on a function, and they did
> something to invalidate the RefSCC we were iterating over[0].  How do
> we _continue_ our iteration over this now non-existent RefSCC?
>

What you described is:  "the iterator pointing to the current SCC gets
invalidated because the pointee disappears, so we need to find a way to let
continue working" - - so it does sound like it is trying to solve the
iterator invalidation problem?

What I suggested is that we should try to avoid getting into that situation
in the first place -- not trying to find a solution for the problem we
introduce in the design.



>
> The solution I'm trying to propose is this: The only possibility for
> invalidation is that the RefSCC was broken up into a forest of
> RefSCC-DAGs[1].  This means if we had a way to get to the leaves of
> this forest of RefSCCs, we could restart our iteration from there
> (I've tacitly assumed we're interested in a bottom-up SCC order).
> This may be difficult in general, but my idea was to "cheat" and
> explicitly remember the Ref-SCC-forest a RefSCC was broken down into
> when we do that invalidation.  Then once an RefSCC is split, we can
> pick up the forest from the original RefSCC* (which is otherwise
> useless now), gather the leaves, and re-start our iteration from those
> leaves.
>
> This leaves the question of what to do with the SCC DAG nested inside
> the RefSCC.  I'm not sure what Chandler has in mind in how much
> influence these should have over the iteration order, but if we wanted
> to iterate over the SCC-DAG in bottom up order as well (as we iterated
> over a single RefSCC), we could have the same scheme to handle
> SCC-splits, and a similar scheme to handle SCC-merges (when you merge
> an SCC, the SCC that gets cleaned out gets a pointer to the SCC where
> all the functions went, and if the SCC you were iterating over gets
> such a pointer after running the inliner/FPM you chase that pointer
> (possibly multiple times, if more than one SCC was merged) and
> re-start iteration over that SCC).
>
> By "incident data structure" I meant that with these additions the
> RefSCC or SCC is no longer a "pure" function of the structure of the
> module, but has state that is a function of what the pass manager did
> which is not ideal.  That is, in theory this isn't significantly
> cleaner than the passes reaching out into and changing the CGSCC pass
> manager's state, but perhaps we are okay with this kind of design for
> practicality's sake?
>


The complexity you described above is my main source of concerns.
Complicated algorithms are nice, but simplicity is better :)

thanks,

David


[0]: One question I don't know the answer to -- how will we detect
> that something has removed a call or ref edge?  Will we rescan
> functions to verify that edges that we though existed still exist?  Or
> will we have a ValueHandles-like scheme?
>
> [1]: As Sean mentioned, by design nothing in the function pass
> manaager pipeline could have invalidated the RefSCC by merging it with
> other RefSCCs.
>
> -- Sanjoy
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160608/28b5dff8/attachment-0001.html>