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

[Jakub (Kuba) Kuderski via llvm-dev]

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>