[llvm-dev] RFC: Dynamic dominators

[Hal Finkel via llvm-dev]

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,
Hal

>
>
>
>
>
> _______________________________________________
> 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>