<div dir="ltr">Hi Tobias,<br><br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span style="font-size:12.8px">1) Daniel and Chandler have for a long time been talking about computing</span><br style="font-size:12.8px"><span style="font-size:12.8px">dominance and post-dominance in one shot to reduce the cost of</span><br style="font-size:12.8px"><span style="font-size:12.8px">post-dominance and make it (freely) available everywhere.  Is this</span><br style="font-size:12.8px"><span style="font-size:12.8px">covered by your current (or planned) work?</span></blockquote><div><br></div><div>I'm not sure what you exactly mean by one shot; I'll ask around tomorrow.<br><br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> <span style="font-size:12.8px">I wanted to play a little bit with your work, but run in some issues:</span><br style="font-size:12.8px"><span style="font-size:12.8px">> bin/llvm-as ../test/Analysis/Dominators/</span><wbr style="font-size:12.8px"><span style="font-size:12.8px">2007-07-11-SplitBlock.ll<br></span><span style="font-size:12.8px">> bin/dominators -to-graph ../test/Analysis/Dominators/</span><wbr style="font-size:12.8px"><span style="font-size:12.8px">2007-07-11-SplitBlock.bc | tee graph<br></span><span style="font-size:12.8px">p 5 5 1 1<br></span><span style="font-size:12.8px">a 1 3<br></span><span style="font-size:12.8px">a 1 5<br></span><span style="font-size:12.8px">a 2 3<br></span><span style="font-size:12.8px">a 3 2<br></span><span style="font-size:12.8px">a 3 4<br></span><span style="font-size:12.8px">e<br></span><span style="font-size:12.8px">> bin/dominators graph<br></span><span style="font-size:12.8px">Unknown file format for graph<br></span><span style="font-size:12.8px">Invalid input graph</span><br style="font-size:12.8px"><span style="font-size:12.8px">I must do something obvious wrong. Any idea what?</span></blockquote><div><br></div><div>You almost got it right -- 'graph' files must end with ".txt"... :P<br><br>Best,<br>Kuba</div></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Jun 12, 2017 at 11:24 PM, Tobias Grosser <span dir="ltr"><<a href="mailto:tobias.grosser@inf.ethz.ch" target="_blank">tobias.grosser@inf.ethz.ch</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi  Jakub,<br>
<br>
thanks for the update. I was already eagerly waiting to hear what your<br>
internship on dominance brings. I think the numbers are already very<br>
encouraging and I believe moving incrementally over to the new algorithm<br>
is exactly the right approach.<br>
<br>
I have a couple of questions:<br>
<br>
1) Daniel and Chandler have for a long time been talking about computing<br>
dominance and post-dominance in one shot to reduce the cost of<br>
post-dominance and make it (freely) available everywhere.  Is this<br>
covered by your current (or planned) work?<br>
<br>
2) I tried to use tools/dominators<br>
<br>
I wanted to play a little bit with your work, but run in some issues:<br>
<br>
> bin/llvm-as ../test/Analysis/Dominators/<wbr>2007-07-11-SplitBlock.ll<br>
> bin/dominators -to-graph ../test/Analysis/Dominators/<wbr>2007-07-11-SplitBlock.bc | tee graph<br>
p 5 5 1 1<br>
a 1 3<br>
a 1 5<br>
a 2 3<br>
a 3 2<br>
a 3 4<br>
e<br>
> bin/dominators graph<br>
Unknown file format for graph<br>
Invalid input graph<br>
<br>
I must do something obvious wrong. Any idea what?<br>
<br>
Best,<br>
Tobias<br>
<br>
On Tue, Jun 13, 2017, at 02:12 AM, Jakub (Kuba) Kuderski via llvm-dev<br>
wrote:<br>
<span class="">> Hi folks,<br>
><br>
> This summer I'm working on improving dominators during my internship at<br>
> Google. Below is an RFC on switching to dynamic dominators, which you can<br>
> also read as a Google Doc<br>
</span>> <<a href="https://docs.google.com/document/d/1wPYeWykeO51YDPLYQEg4KNTlDIGIdyF65OTfhSMaNHQ/edit?usp=sharing" rel="noreferrer" target="_blank">https://docs.google.com/<wbr>document/d/<wbr>1wPYeWykeO51YDPLYQEg4KNTlDIGId<wbr>yF65OTfhSMaNHQ/edit?usp=<wbr>sharing</a>><br>
<span class="">> if you prefer so. Please let us know what you think.<br>
><br>
> ~Kuba<br>
><br>
> ==============================<wbr>==============================<wbr>===========<br>
><br>
</span>> *1. Context*<br>
<span class="">><br>
> Currently LLVM uses the Simple Lengauer-Tarjan algorithm to build the<br>
> (post)dominator tree. The only way to update it is by manually setting<br>
> IDoms which is not obvious in many cases and can be extremely<br>
> error-prone.<br>
> And because updating it manually is so difficult, programmers tend to<br>
> just<br>
> recompute it after changing the CFG (by not AU.addPreserved()'ing the<br>
> DomTree). This causes DomTree calculation to fire very often even if only<br>
> a<br>
> very small portion of it gets really affected by the changes in CFG. As<br>
> an<br>
> example, when optimizing a Full LTO clang bitcode,<br>
> DominatorTreeWrapperPass<br>
> alone calls DT.recalculate over 6.5 million times, which takes 20s on my<br>
> machine.<br>
><br>
> Using an incremental algorithm it would be much easier to keep an<br>
> up-to-date DomTree without custom update logic, which will save us the<br>
> time<br>
> currently spent during DomTree recalculations and reduce the number of<br>
> bugs<br>
> caused by manual updates. It would also make it feasible to maintain<br>
> postdominators and use them more broadly, which currently can be too<br>
> complicated and expensive.<br>
><br>
</span>> *2. Proposal*<br>
<span class="">><br>
> The proposal is to make dominators use the incremental algorithm that<br>
> allows to keep (post)dominator tree up to date as CFG changes. To achieve<br>
> that, we would implement the dynamic depth based search algorithm (DBS)<br>
</span>> described in this paper [1] <<a href="https://arxiv.org/pdf/1604.02711.pdf" rel="noreferrer" target="_blank">https://arxiv.org/pdf/1604.<wbr>02711.pdf</a>> and<br>
<span class="">> expose 2 main new functions: insertArc(From, To) and deleteArc(From, To).<br>
> The algorithm uses SemiNCA under the hood which would replace<br>
> Lengauer-Tarjan implementation currently used.<br>
><br>
> The second part of the proposal is to gradually deprecate and remove the<br>
> existing API for manually manipulating dominator tree<br>
> (changeImmediateDominator, addNewBlock) and replace its use within LLVM<br>
> with the new incremental API.<br>
><br>
</span>> *3. Proof of concept*<br>
<span class="">><br>
> The prototype implementation can be found in my LLVM fork [2]<br>
</span>> <<a href="https://github.com/kuhar/llvm-dominators" rel="noreferrer" target="_blank">https://github.com/kuhar/<wbr>llvm-dominators</a>>. It comes with several layers<br>
<span class="">> of<br>
> verification and was tested on clang, llvm test suite and a few open<br>
> source<br>
> libraries.<br>
> The code provides the basic functionality and tries be ‘API-equivalent’<br>
> with the current DomTree implementation. The NewDomTree is also able to<br>
> convert itself to the current one for testing and verification purposes.<br>
> Dynamic dominators are hacked into 3 existing passes (DomTreeWrapperPass,<br>
> LoopDeletion, LoopSimplifyCFG) to test correctness and experiment with<br>
> the<br>
> use of the new API.<br>
><br>
> The prototype also comes with a bunch of testing utilities and a simple<br>
> benchmarking tool.<br>
><br>
</span>> *4. Performance*<br>
<span class="">><br>
> The real life performance of full dynamic DBS-based DomTree recalculation<br>
> is between 20% and 2% better on a machine with two Xeon E5-2680v2 CPUs<br>
> than<br>
> the existing SLT algorithm, which is consistent with the findings from<br>
> this<br>
</span>> thesis [3] <<a href="ftp://ftp.cs.princeton.edu/reports/2005/737.pdf" rel="noreferrer" target="_blank">ftp://ftp.cs.princeton.edu/<wbr>reports/2005/737.pdf</a>>. The<br>
<span class="">> advantage<br>
> is not that visible on debug builds, where the DBS-algorithm can be up to<br>
> 8% slower. It is most like possible to speed up debug builds, but I<br>
> haven’t<br>
> looked into that yet.<br>
> The benchmark performed [4]<br>
</span>> <<a href="https://docs.google.com/document/d/1wPYeWykeO51YDPLYQEg4KNTlDIGIdyF65OTfhSMaNHQ/edit?usp=sharing" rel="noreferrer" target="_blank">https://docs.google.com/<wbr>document/d/<wbr>1wPYeWykeO51YDPLYQEg4KNTlDIGId<wbr>yF65OTfhSMaNHQ/edit?usp=<wbr>sharing</a>><br>
<span class="">> loads of a (full LTO) bitcode file and builds DomTress of all functions<br>
> 15<br>
> times.<br>
><br>
> The current DomTree updates DFS in-out numbers eagerly upon construction,<br>
> while the new one postpones is until they are actually needed. To make<br>
> the<br>
> benchmark fair, numbers were collected for both eager and lazy strategy<br>
> for<br>
> the new DomTree.<br>
><br>
> The main advantage of the incremental algorithm comes from the fact that<br>
> it<br>
> allows incremental updates without rebuilding the whole tree, not from<br>
> the<br>
> slightly faster construction.<br>
> What’s more, the insertArc / deleteArc API doesn’t force updates to<br>
> happen<br>
> immediately -- they can be queued behind the scenes and happen in batches<br>
> if we decide to pursue that design later.<br>
><br>
</span>> *5. Transition plan*<br>
<div class="HOEnZb"><div class="h5">><br>
> There are several possibilities when it comes to transition. The biggest<br>
> problem is that the current DomTree exposes an interface for manual<br>
> updates<br>
> (setIDom, changeImmediateDominator), and for manual construction<br>
> (addNewBlock). Because of the additional data stored in the incremental<br>
> algorithm (relative dominators, preorder parents, levels) it is not<br>
> really<br>
> possible to use the old API while keeping this data up-to-date. The<br>
> incremental algorithm relies on this information when performing fast arc<br>
> deletions; It is still able to perform them without it -- deletions are<br>
> then just slower in some cases.<br>
> The most straightforward solutions are:<br>
><br>
> a) Keep the existing DomTree and gradually replace its uses with the new<br>
> one. It is possible to convert the DBS-based dominators to the old ones.<br>
> b) Replace the existing DomTree with the new, dynamic dominators. Nuke<br>
> all<br>
> of the old update functions and replace their uses with the new<br>
> incremental<br>
> API in one commit.<br>
> c) Replace the existing DomTree with the new one, but keep the old API<br>
> around and mark it as deprecated. If someone invokes one of the old<br>
> update<br>
> functions, mark the the additional information as invalid for dynamic<br>
> deletions. Follow the pessimistic but correct dynamic deletion path if<br>
> the<br>
> additional information is marked as invalidated. Gradually modernize the<br>
> projects to use the new API instead and then remove the old update<br>
> functions.<br>
><br>
> Maintaining the old DT and the new one simultaneously seems like a waste<br>
> of<br>
> time as the DBS offers better or similar performance to the existing<br>
> SLT-based implementation.<br>
> The problem with replacing the old API with the new one is that it’s used<br>
> in many places (~100) across the project and I believe that doing that<br>
> all<br>
> at once would be tricky to get correct. Gradual update seems much easier<br>
> to<br>
> ensure correctness and the transitional API (invalid additional data<br>
> check)<br>
> is trivial to implement. Because of that, I propose to follow the option<br>
> (c).<br>
><br>
><br>
><br>
> [1] Georgiadis et al., An Experimental Study of Dynamic Dominators,<br>
> <a href="https://arxiv.org/pdf/1604.02711.pdf" rel="noreferrer" target="_blank">https://arxiv.org/pdf/1604.<wbr>02711.pdf</a><br>
> [2] llvm-dominators LLVM fork on Github,<br>
> <a href="https://github.com/kuhar/llvm-dominators" rel="noreferrer" target="_blank">https://github.com/kuhar/llvm-<wbr>dominators</a><br>
> [3] L. Georgiadis, Linear-Time Algorithms for Dominators and Related<br>
> Problems, <a href="ftp://ftp.cs.princeton.edu/reports/2005/737.pdf" rel="noreferrer" target="_blank">ftp://ftp.cs.princeton.edu/<wbr>reports/2005/737.pdf</a> p. 38<br>
> [4] Google Doc with the performance numbers,<br>
> <a href="https://docs.google.com/document/d/1wPYeWykeO51YDPLYQEg4KNTlDIGIdyF65OTfhSMaNHQ/edit?usp=sharing" rel="noreferrer" target="_blank">https://docs.google.com/<wbr>document/d/<wbr>1wPYeWykeO51YDPLYQEg4KNTlDIGId<wbr>yF65OTfhSMaNHQ/edit?usp=<wbr>sharing</a><br>
</div></div><div class="HOEnZb"><div class="h5">> ______________________________<wbr>_________________<br>
> LLVM Developers mailing list<br>
> <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
> <a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
</div></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>