[llvm-dev] RFC: Dynamic dominators

[Tobias Grosser via llvm-dev]

On Tue, Jun 13, 2017, at 08:29 PM, Daniel Berlin via llvm-dev wrote:
> 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.

Alright. This sounds to be more in line with what I expected. Thanks for
clarifying.

Best,
Tobias
 
> 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"
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev