Page MenuHomePhabricator

[NFCI] Replace linear scan with bisection.
Needs ReviewPublic

Authored by nicholas on Apr 16 2019, 12:51 AM.
This revision needs review, but there are no reviewers specified.

Details

Reviewers
None
Summary

Instead of storing each DomTreeNode that we've visited and checking whether our next block is dominated by any of them, store only the blocks which aren't dominated by other blocks in the visited set, and use bisection on the dfs-in number to identify the only block in the set that might be dominating.

Diff Detail