[llvm-dev] An update on the DominatorTree and incremental dominators
Jakub (Kuba) Kuderski via llvm-dev
llvm-dev at lists.llvm.org
Mon Jul 17 11:24:00 PDT 2017
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:
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.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the llvm-dev