<div dir="ltr">Hi folks,<br><br>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:<br><ul><li>Infinite loops are now included in the PostDominatorTree.<br></li><li>Incrementally updated DominatorTree and PostDominatorTree are now guaranteed to be the same as freshly recalculated ones.</li><li>The low-level incremental API (<font face="monospace, monospace">insertEdge/deleteEdge</font>) is used to update dominators in LoopDeletion and AgressiveDeadCodeElimination.</li><li>Support for batch updates (<font face="monospace, monospace">applyUpdates</font><font face="arial, helvetica, sans-serif">)</font><font face="monospace, monospace"> </font><font face="arial, helvetica, sans-serif">was introduced to make updating dominators *much* easier. The batch updater landed upstream earlier this week.</font></li><li><font face="arial, helvetica, sans-serif">The batch updater is now used to preserve dominators in LoopUnswitching, LoopRotation, and BreakCriticalEdges.<br></font></li></ul><div><font face="arial, helvetica, sans-serif">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 :).<br><br>Best,<br>Kuba</font></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Jul 17, 2017 at 11:24 AM, Jakub (Kuba) Kuderski <span dir="ltr"><<a href="mailto:kubakuderski@gmail.com" target="_blank">kubakuderski@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><span id="m_5195005880809531910gmail-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="m_5195005880809531910gmail-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="m_5195005880809531910gmail-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" target="_blank"><span style="font-family:Arial;background-color:transparent;text-decoration-line:underline;vertical-align:baseline;white-space:pre-wrap">http://lists.llvm.org/<wbr>pipermail/llvm-dev/2017-June/<wbr>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="m_5195005880809531910gmail-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="m_5195005880809531910gmail-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="m_5195005880809531910gmail-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="m_5195005880809531910gmail-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="m_5195005880809531910gmail-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="m_5195005880809531910gmail-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="m_5195005880809531910gmail-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="m_5195005880809531910gmail-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>
</blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature" data-smartmail="gmail_signature"><div>Jakub Kuderski</div></div>
</div>