<div dir="ltr"><span id="gmail-docs-internal-guid-19dc77b9-9fad-e5e1-6ab3-f9a53bd1e7ea"><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">Earlier today I submitted for review a patch <a href="https://reviews.llvm.org/D36167">D36167</a> that introduces API for performing batch updates on the (Post)DominatorTree. Before that, the DomTree exposed only very low-level functions for performing incremental updates: insertEdge(From, To) and deleteEdge(From, To). The main problem with it is that the API needed to know about every inserted and deleted CFG edge as the update happened -- it wasn’t possible to perform some transformation and then do all of the DomTree updates.</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">The batch updates enable us to do a transformation and defer informing the tree about it until we are done with changing the CFG. The list of updates to perform doesn’t even have to be provided in the same order in which they really happened. Moreover, the batch updater is able to optimize away redundant updates and in the future it will be also able to reorder updates to reduce the amount of work needed to apply them.</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">I updated two of my patches (in review) to use the new batch update API, you can find them here: </span><span style="font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap"><a href="https://reviews.llvm.org/D35581">D35581</a>, <a href="https://reviews.llvm.org/D35528">D35528</a></span><span style="font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">. Here’s a snippet taken from the LoopRotate patch that uses the batch update API:</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></p><blockquote style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" class="gmail_quote"><span style="font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">SmallVector<DominatorTree::UpdateType, 3> Updates;<br></span><span style="font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Updates.push_back({DominatorTree::Insert, OrigPreheader, Exit});<br></span><span style="font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Updates.push_back({DominatorTree::Insert, OrigPreheader, NewHeader});<br></span><span style="font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Updates.push_back({DominatorTree::Delete, OrigPreheader, OrigHeader});<br></span><span><span style="font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">DT->applyUpdates(Updates);</span></span></blockquote><p></p></span><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">If you are interested in discussing the design or the implementation, please leave a comment here or on phabricator.</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">Thanks,</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></span><br clear="all"><div><br></div>-- <br><div class="gmail_signature"><div>Jakub Kuderski</div></div>
</div>