This is an archive of the discontinued LLVM Phabricator instance.

[Dominators] Keep tree level in DomTreeNode and use it to find NCD and answer dominance queries
ClosedPublic

Authored by kuhar on Jun 22 2017, 7:54 PM.

Details

Summary

This patch makes DomTreeNodes keep their level (depth) in the DomTree. By having this information always available, it is possible to speedup and simplify findNearestCommonDominator and certain dominance queries.

In the future, level information will be also needed to perform incremental updates.

My testing doesn't show any noticeable performance differences after applying this patch. There may be some improvements when other passes are thought to use the level information.

Diff Detail

Event Timeline

kuhar updated this revision to Diff 103746.Jun 23 2017, 10:29 AM

Add level verification and update tests.

kuhar updated this revision to Diff 103747.Jun 23 2017, 10:33 AM

Minor cleanup

dberlin accepted this revision.Jun 23 2017, 7:21 PM

Can you also change IteratedDominanceFrontier to use this level info instead of computing it on it's own?

This revision is now accepted and ready to land.Jun 23 2017, 7:21 PM
kuhar updated this revision to Diff 104073.Jun 26 2017, 6:58 PM

Update the diff.

I would like to teach IDF to use levels in a separate patch.

kuhar updated this revision to Diff 104930.Jun 30 2017, 2:05 PM

Update the diff to apply cleanly.

This revision was automatically updated to reflect the committed changes.