[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
> is exactly the right approach.
> I have a couple of questions:
> 1) Daniel and Chandler have for a long time been talking about
> 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
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?
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the llvm-dev