This is an archive of the discontinued LLVM Phabricator instance.

[Dominators] Use a custom DFS implementation
ClosedPublic

Authored by kuhar on Jun 26 2017, 3:41 PM.

Details

Summary

Custom DFS implementation allows us to skip over certain nodes without adding them to the visited map, which is not easily doable with llvm's dfs iterators. What's more, caching predecessors becomes easy.

This patch implements a single DFS function (template) for both forward and reverse DFS, which should be easier to maintain then separate two ones.

Skipping over nodes based on a predicate will be necessary later to implement incremental updates.

There also seems to be a very slight performance improved when bootstrapping clang with this patch on my machine (3:28s -> 3:26s) .

Diff Detail

Repository
rL LLVM

Event Timeline

kuhar updated this revision to Diff 104034.Jun 26 2017, 3:41 PM
kuhar created this revision.

Format patch

kuhar updated this revision to Diff 104040.Jun 26 2017, 4:17 PM

Remove unused alias declaration

dberlin edited edge metadata.Jun 26 2017, 4:34 PM

So, just to note: It's generally nonsense to try to calculate the root list prior to DFS (and a source of bugs in the current postdominator tree). By nonsense i mean "impossible".
You need to see what's reachable to know what ends up needing to be connected to a virtual root.

kuhar updated this revision to Diff 104078.Jun 26 2017, 7:02 PM

Update the diff so that it applies cleanly.

dberlin accepted this revision.Jul 11 2017, 2:56 PM

At some point we should make the DFS iterators more flexible, but i don't think we need to design that for this

This revision is now accepted and ready to land.Jul 11 2017, 2:56 PM
kuhar updated this revision to Diff 106107.Jul 11 2017, 3:45 PM

Update the diff to apply cleanly.

This revision was automatically updated to reflect the committed changes.