<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Jun 8, 2016 at 5:54 PM, Sanjoy Das <span dir="ltr"><<a href="mailto:sanjoy@playingwithpointers.com" target="_blank">sanjoy@playingwithpointers.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi David,<br>
<span class=""><br>
On Wed, Jun 8, 2016 at 4:20 PM, Xinliang David Li <<a href="mailto:xinliangli@gmail.com">xinliangli@gmail.com</a>> wrote:<br>
> Is it in the category of invalidating the iterator while iterating' which<br>
> feels very wrong to me.  We should avoid going there and find better ways to<br>
> solve the motivating problems (perhaps defining them more clearly first ?).<br>
<br>
</span>I'm not a 100% sure of what you meant by that, so I'll try to give a<br>
general answer, and hope that it covers the points you wanted to<br>
raise. :)<br>
<br>
In the scheme above I'm not trying to solve iterator invalidation --<br>
I'm trying to solve the following problem: the CGSCC pass manager ran<br>
the inliner and a set of function passes on a function, and they did<br>
something to invalidate the RefSCC we were iterating over[0].  How do<br>
we _continue_ our iteration over this now non-existent RefSCC?<br></blockquote><div><br></div><div>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?</div><div><br></div><div>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.</div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
The solution I'm trying to propose is this: The only possibility for<br>
invalidation is that the RefSCC was broken up into a forest of<br>
RefSCC-DAGs[1].  This means if we had a way to get to the leaves of<br>
this forest of RefSCCs, we could restart our iteration from there<br>
(I've tacitly assumed we're interested in a bottom-up SCC order).<br>
This may be difficult in general, but my idea was to "cheat" and<br>
explicitly remember the Ref-SCC-forest a RefSCC was broken down into<br>
when we do that invalidation.  Then once an RefSCC is split, we can<br>
pick up the forest from the original RefSCC* (which is otherwise<br>
useless now), gather the leaves, and re-start our iteration from those<br>
leaves.<br>
<br>
This leaves the question of what to do with the SCC DAG nested inside<br>
the RefSCC.  I'm not sure what Chandler has in mind in how much<br>
influence these should have over the iteration order, but if we wanted<br>
to iterate over the SCC-DAG in bottom up order as well (as we iterated<br>
over a single RefSCC), we could have the same scheme to handle<br>
SCC-splits, and a similar scheme to handle SCC-merges (when you merge<br>
an SCC, the SCC that gets cleaned out gets a pointer to the SCC where<br>
all the functions went, and if the SCC you were iterating over gets<br>
such a pointer after running the inliner/FPM you chase that pointer<br>
(possibly multiple times, if more than one SCC was merged) and<br>
re-start iteration over that SCC).<br>
<br>
By "incident data structure" I meant that with these additions the<br>
RefSCC or SCC is no longer a "pure" function of the structure of the<br>
module, but has state that is a function of what the pass manager did<br>
which is not ideal.  That is, in theory this isn't significantly<br>
cleaner than the passes reaching out into and changing the CGSCC pass<br>
manager's state, but perhaps we are okay with this kind of design for<br>
practicality's sake?<br></blockquote><div><br></div><div><br></div><div>The complexity you described above is my main source of concerns. Complicated algorithms are nice, but simplicity is better :)</div><div><br></div><div>thanks,</div><div><br></div><div>David</div><div><br></div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
[0]: One question I don't know the answer to -- how will we detect<br>
that something has removed a call or ref edge?  Will we rescan<br>
functions to verify that edges that we though existed still exist?  Or<br>
will we have a ValueHandles-like scheme?<br>
<br>
[1]: As Sean mentioned, by design nothing in the function pass<br>
manaager pipeline could have invalidated the RefSCC by merging it with<br>
other RefSCCs.<br>
<span class="HOEnZb"><font color="#888888"><br>
-- Sanjoy<br>
</font></span></blockquote></div><br></div></div>