Page MenuHomePhabricator

Make updateDFSNumbers API public

Authored by dberlin on Apr 9 2015, 5:35 PM.



There are a number of passes that could be sped up by using dominator tree DFS numbers to order or compare things across multiple bbs
(MemorySSA, MergedLoadStoreMotion, EarlyCSE, Sinking, GVN, NewGVN, for starters :P).

For example, GVN/CSE elimination can be done with a simple stack/etc (instead of full-on scoped hash table or repeated leader set walks)

if the DFS pair is stored next to leaders.

The dominator tree keeps them, and the DOM tree nodes expose them as public, but you have no guarantee they are up to date (and in fact,
if you split blocks or whatever during your pass, they definitely won't be)

This means passes either have to compute their own versions[1], or make 32 queries, or ....
Rather than try to hide this, i just made the API public, and make it do nothing if the numbers are already valid.

[1] Which we want as a non-recursive walk, which is not pretty, sadly,
because it cannot use the depth first iterators since you don't get called on the way back up. So you either have to do one walk with po_iterator
and one with df_iterator, or write your own non-recursive walk that looks identical to the one in updateDFSNumbers.

Diff Detail


Event Timeline

dberlin updated this revision to Diff 23549.Apr 9 2015, 5:35 PM
dberlin retitled this revision from to Make updateDFSNumbers API public.
dberlin updated this object.
dberlin edited the test plan for this revision. (Show Details)
dberlin added a reviewer: chandlerc.
dberlin added a subscriber: Unknown Object (MLST).

It looks like it generated the stupidest diff possible for this change.

In reality, what happened is i moved the updateDFSNumbers below the
public: line.

Instead, it generated a diff that makes it look like i moved everything up.

chandlerc accepted this revision.Apr 14 2015, 8:08 AM
chandlerc edited edge metadata.

LGTM. We should consider documenting this and teaching people to use it like they would use vector::reserve when they *know* they're going to make mor ethan 32 queries and it doesn't make sense to have the first 32 be slow.

This revision is now accepted and ready to land.Apr 14 2015, 8:08 AM

Not recalculating if valid exposes a bug in maintenance of the DFSInfoValid
flag (which is very hard to trigger, but expensive debugging has a check
that catches it on two out of the 13000 testcases we have because it
requires passes to recalculate the dom tree and then do something with it)

I am submitting the change without that part (IE just moving
updateDFSNumbers), then submitting a bug fix (coming) to maintain the flag
properly and add the check back along with a unit test.

The bug is that GenericDomTree::recalculate never sets DFSInfoValid =
false, but calls DT.updateDFSNumbers at the end, expecting it will always
recalculate the DFS numbers.

This revision was automatically updated to reflect the committed changes.