[llvm-dev] RFC: Dynamic dominators

[Hal Finkel via llvm-dev]

On 06/12/2017 07:58 PM, Sean Silva via llvm-dev wrote:
>
>
> On Mon, Jun 12, 2017 at 5:12 PM, Jakub (Kuba) Kuderski via llvm-dev 
> <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
>
>     Hi folks,
>     ...
>     a) Keep the existing DomTree and gradually replace its uses with
>     the new one. It is possible to convert the DBS-based dominators to
>     the old ones.
>     b) Replace the existing DomTree with the new, dynamic dominators.
>     Nuke all of the old update functions and replace their uses with
>     the new incremental API in one commit.
>     c) Replace the existing DomTree with the new one, but keep the old
>     API around and mark it as deprecated. If someone invokes one of
>     the old update functions, mark the the additional information as
>     invalid for dynamic deletions. Follow the pessimistic but correct
>     dynamic deletion path if the additional information is marked as
>     invalidated. Gradually modernize the projects to use the new API
>     instead and then remove the old update functions.
>     Maintaining the old DT and the new one simultaneously seems like a
>     waste of time as the DBS offers better or similar performance to
>     the existing SLT-based implementation.
>     The problem with replacing the old API with the new one is that
>     it’s used in many places (~100) across the project and I believe
>     that doing that all at once would be tricky to get correct.
>     Gradual update seems much easier to ensure correctness and the
>     transitional API (invalid additional data check) is trivial to
>     implement. Because of that, I propose to follow the option (c).
>
>
> (c) sounds like the best choice to me too. That would also allow 
> fixing dominator verification failures first, giving a nice immediate 
> benefit to motivate and kickstart the transition.

+1

  -Hal

>
> -- Sean Silva
>
>
>
>
>     [1] Georgiadis et al., An Experimental Study of Dynamic
>     Dominators, https://arxiv.org/pdf/1604.02711.pdf
>     <https://arxiv.org/pdf/1604.02711.pdf>
>     [2] llvm-dominators LLVM fork on Github,
>     https://github.com/kuhar/llvm-dominators
>     <https://github.com/kuhar/llvm-dominators>
>     [3] L. Georgiadis, Linear-Time Algorithms for Dominators and
>     Related Problems, ftp://ftp.cs.princeton.edu/reports/2005/737.pdf
>     <ftp://ftp.cs.princeton.edu/reports/2005/737.pdf> p. 38
>     [4] Google Doc with the performance numbers,
>     https://docs.google.com/document/d/1wPYeWykeO51YDPLYQEg4KNTlDIGIdyF65OTfhSMaNHQ/edit?usp=sharing
>     <https://docs.google.com/document/d/1wPYeWykeO51YDPLYQEg4KNTlDIGIdyF65OTfhSMaNHQ/edit?usp=sharing>
>
>     _______________________________________________
>     LLVM Developers mailing list
>     llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
>     http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>     <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
>
>
>
>
> _______________________________________________
> 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/fb1b770e/attachment.html>