[llvm-dev] An update on the DominatorTree and incremental dominators

[Tobias Grosser via llvm-dev]

On Sat, Aug 19, 2017, at 00:58, Jakub (Kuba) Kuderski via llvm-dev
wrote:
> Hi folks,
> 
> Today is the last day of my internship, so here is a short list of
> changes
> to dominators that I committed since the last email:
> 
>    - Infinite loops are now included in the PostDominatorTree.
>    - Incrementally updated DominatorTree and PostDominatorTree are now
>    guaranteed to be the same as freshly recalculated ones.
>    - The low-level incremental API (insertEdge/deleteEdge) is used to
>    update dominators in LoopDeletion and AgressiveDeadCodeElimination.
>    - Support for batch updates (applyUpdates) was introduced to make
>    updating dominators *much* easier. The batch updater landed upstream
>    earlier this week.
>    - The batch updater is now used to preserve dominators in
>    LoopUnswitching, LoopRotation, and BreakCriticalEdges.
> 
> Thank you all for giving me feedback and reviewing my patches, especially
> to Danny, Sanjoy, Davide, Tobias, and Brian. I cannot imagine getting so
> far without your support :).

Dear Kuba,

thanks a lot for all of your hard work! I am very impressive by your
output. The incremental dominator construction in LLVM is indeed a large
step forward. We may not always have agreed on everything, but
independently it was a pleasure to work with you.
As you likely soon fly back to Europe, feel invited to pass by at ETH at
any point.

Best,
Tobias

> 
> Best,
> Kuba
> 
> On Mon, Jul 17, 2017 at 11:24 AM, Jakub (Kuba) Kuderski <
> kubakuderski at gmail.com> wrote:
> 
> > Hi folks,
> >
> > For the past month I’ve been working on improving the DominatorTree and
> > PostDominatorTree in LLVM. The RFC that explains the motivations and plans
> > can be found here: http://lists.llvm.org/pipermail/llvm-dev/2017-June/
> > 114045.html .
> >
> > Here’s a short summary of what changed upstream since posting it:
> >
> >    -
> >
> >    We switched from the Simple Lengauer-Tarjan algorithm for computing
> >    dominators to Semi-NCA, which is a bit faster in most cases. Although it is
> >    possible to construct a CFG that triggers the pathological quadratic
> >    complexity of Semi-NCA, we weren’t able to observe it in practice.
> >    -
> >
> >    DomTreeNodes now automatically store their level (depth) in the tree,
> >    which is always up-to-date. This is used for fast nearest common dominator
> >    computation and for building iterated dominance frontier. You can get it by
> >    calling .getLevel() on a DomTreeNode.
> >    -
> >
> >    We have a new set of verifiers that are able to prove or disprove
> >    correctness of a DomTree -- you can explicitly do it by calling
> >    DT.verify(). The check has a disadvantage of being quite slow (O(n^3)), so
> >    the legacy DT.verifyDominatorTree() uses it only when
> >    ENABLE_EXPENSIVE_CHECK is enabled, or when the -verify-dom-info command
> >    line option is set to 1. Some of the transforms assume that calling
> >    DT.verifyDomTree() is fast, so we cannot turn it on by default.
> >    -
> >
> >    Dominators and Postdominators are now different types, i.e. IsPostDom
> >    is a template argument and not a runtime value. It is no longer possible to
> >    assign a PostDomTree to a DomTree (or the other way round).
> >
> >
> > And now the big thing: support for incremental updates (insertEdge and
> > deleteEdge) has just landed upstream. This should make updating
> > DominatorTree much easier and less error-prone.
> > Although he API is quite basic at the moment, it should be sufficient to
> > replace manual DomTree updates in many places. Please give the new
> > incremental API a try and share your feedback :).
> >
> > During the remaining 5 weeks of my internship at Google, I plan to make a
> > few transforms use the new incremental API, further improve
> > PostDominatorTree by making it always have a virtual root, and to
> > investigate batch updates. After that I would like to continue maintaining
> > dominators, but I won’t be able spend as much time on it as I do now.
> >
> > Best,
> > Kuba
> >
> >
> 
> 
> -- 
> Jakub Kuderski
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev