[llvm-dev] RFC: Dynamic dominators

[Daniel Berlin via llvm-dev]

On Mon, Jun 12, 2017 at 11:24 PM, Tobias Grosser via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

> Hi  Jakub,
>
> thanks for the update. I was already eagerly waiting to hear what your
> internship on dominance brings. I think the numbers are already very
> encouraging and I believe moving incrementally over to the new algorithm
> is exactly the right approach.
>
> I have a couple of questions:
>
> 1) Daniel and Chandler have for a long time been talking about computing
> dominance and post-dominance in one shot to reduce the cost of
> post-dominance and make it (freely) available everywhere.  Is this
> covered by your current (or planned) work?
>

I think chandler more than me. If me, assume I was wrong :P

I believe you can prove it is not possible to  do this without doing all
the work of the separate passes. The main cost is the DFS walk, and you
can't do an undirected DFS that will work here.
I believe related things have even been proven to show the brokenness of
various algorithms.

See https://hal.inria.fr/hal-00761505 section 4.1

Given the difficulties and subtleties here, I would consider any such
approach that tried to share work between the passes as "fraught with peril"
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170613/7e634774/attachment.html>