llvm dev - Aug 2017 - An update on the DominatorTree and incremental dominators

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170717/e5d79bc6/attachment.html>

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 :).

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170818/37c6bb51/attachment.html>

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