[llvm-dev] RFC: Dynamic dominators

Hal Finkel via llvm-dev llvm-dev at lists.llvm.org
Wed Jun 21 18:00:41 PDT 2017

On 06/13/2017 01: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 <mailto: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"

Is there a difference here between sharing work and sharing updates? The 
difficult part of using postdominance seems to be not the one-time cost 
of computing it, but the fact that we don't preserve it anywhere. Thus, 
using it would require re-computing it a lot. Even if we can't share the 
work of constructing a dominance and post-dominance tree, could we have 
an update API that could be used to keep both trees consistent?

Thanks again,

> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170621/6dfe4066/attachment.html>

More information about the llvm-dev mailing list