<div dir="ltr"><span id="gmail-docs-internal-guid-01d6577e-51c9-19e9-3e65-6602d9d6188b"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Hi folks,</span><span style="font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"><br class="gmail-kix-line-break"></span><span style="font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"><br class="gmail-kix-line-break"></span><span style="font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">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: </span><a href="http://lists.llvm.org/pipermail/llvm-dev/2017-June/114045.html" style="text-decoration-line:none"><span style="font-family:Arial;background-color:transparent;text-decoration-line:underline;vertical-align:baseline;white-space:pre-wrap">http://lists.llvm.org/pipermail/llvm-dev/2017-June/114045.html</span></a><span style="font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"> .</span><span style="font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"><br class="gmail-kix-line-break"></span><span style="font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"><br class="gmail-kix-line-break"></span><span style="font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Here’s a short summary of what changed upstream since posting it:</span></p><ul style="margin-top:0pt;margin-bottom:0pt"><li dir="ltr" style="list-style-type:disc;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="background-color:transparent;vertical-align:baseline;white-space:pre-wrap">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.</span></p></li><li dir="ltr" style="list-style-type:disc;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="background-color:transparent;vertical-align:baseline;white-space:pre-wrap">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.</span></p></li><li dir="ltr" style="list-style-type:disc;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="background-color:transparent;vertical-align:baseline;white-space:pre-wrap">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.</span></p></li><li dir="ltr" style="list-style-type:disc;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="background-color:transparent;vertical-align:baseline;white-space:pre-wrap">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).</span></p></li></ul><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">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.</span><span style="font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"><br class="gmail-kix-line-break"></span><span style="font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">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 :).</span><span style="font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"><br class="gmail-kix-line-break"></span><span style="font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"><br class="gmail-kix-line-break"></span><span style="font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">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.</span><span style="font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"><br class="gmail-kix-line-break"></span><span style="font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"><br class="gmail-kix-line-break"></span><span style="font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Best,</span><span style="font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"><br class="gmail-kix-line-break"></span><span style="font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Kuba</span></p><div><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"><br></span></div></span>
</div>