<div dir="ltr"><b style="font-weight:normal" id="gmail-docs-internal-guid-39e3b671-dbfc-752b-6f9f-94b747e3bea7"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">TL;DR</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">The purpose of this RFC is to bring a new updater to unify the API when performing updates to the <span class="" id=":tv.1" tabindex="-1" style="">dominator</span> tree and the post <span class="" id=":tv.2" tabindex="-1" style="">dominator</span> tree using different update strategies. The prototype of the new updater class APIs is available on <span class="" id=":tv.3" tabindex="-1" style="">Github</span> for feedback. [1] The existing interface to update the <span class="" id=":tv.4" tabindex="-1" style="">dominator</span> tree/post <span class="" id=":tv.5" tabindex="-1" style="">dominator</span> tree is fragmented. (</span><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap"><span class="" id=":tv.6" tabindex="-1" style="">DT</span>.<span class="" id=":tv.7" tabindex="-1" style="">applyUpdates</span>(Updates)</span><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap"> when performing eager updates or construct a <span class="" id=":tv.8" tabindex="-1" style="">DeferredDominance</span> class instance to perform deferred updates). </span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">The new <span class="" id=":tv.9" tabindex="-1" style="">dominator</span> tree updater resolves these issues by providing a cleaner API to perform updates on available <span class="" id=":tv.10" tabindex="-1" style="">dominator</span> trees (none, only <span class="" id=":tv.11" tabindex="-1" style="">DomTree</span>, only <span class="" id=":tv.12" tabindex="-1" style="">PostDomTree</span>, both) using different update strategies (eagerly or lazily) to simplify the updating process. We will also try to enable more <span class="" id=":tv.13" tabindex="-1" style="">optimizations</span> when performing updates in the future.</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap"> </span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">—Motivation—</span></p><ol style="margin-top:0pt;margin-bottom:0pt"><li dir="ltr" style="list-style-type:decimal;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">The current API is quite fragmented and different functions using these APIs need to write redundant code to manually deal with various kinds of update strategies which makes code hard to maintain. Directly calling update functions of <span class="" id=":tv.14" tabindex="-1" style="">DominatorTree</span> updates the data structure eagerly while <span class="" id=":tv.15" tabindex="-1" style="">DeferredDominance</span> does updates lazily. Thus some functions need to perform lazy incremental updates in the <span class="" id=":tv.16" tabindex="-1" style="">codebase</span> need to construct an additional lazy updater. [2] <span class="" id=":tv.17" tabindex="-1" style="">DeferredDominance</span> class cannot be used when a <span class="" id=":tv.18" tabindex="-1" style="">PostDominatorTree</span> also needs to be updated because <span class="" id=":tv.19" tabindex="-1" style="">BasicBlocks</span> are maybe pending to be removed. And functions receiving <span class="" id=":tv.20" tabindex="-1" style="">DominatorTrees</span> can avoid code patterns like that in [5] which is currently necessary.</span></p></li></ol><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:35.4331pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">For eager updates:</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:35.4331pt"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap"><span class="" id=":tv.21" tabindex="-1" style="">DT</span>.<span class="" id=":tv.22" tabindex="-1" style="">applyUpdates</span>(Updates);</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:35.4331pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">For deferred updates:</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:35.4331pt"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap"><span class="" id=":tv.23" tabindex="-1" style="">DeferredDominance</span> DDT(<span class="" id=":tv.24" tabindex="-1" style="">DT</span>);</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:35.4331pt"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">DDT.<span class="" id=":tv.25" tabindex="-1" style="">applyUpdates</span>(Updates);</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:35.4331pt"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap"><b style="font-weight:normal" id="gmail-docs-internal-guid-34b9e6ae-dc03-6aec-c500-20aa6d775d1d"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">...</span></b></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:35.4331pt"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap"><b style="font-weight:normal" id="gmail-docs-internal-guid-a1b515f1-dc02-dbd6-98e5-0ca21cd5d607"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">DDT.flush();</span></b><br></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:35.4331pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">When passing into functions:</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:35.4331pt"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">void <span class="" id=":tv.26" tabindex="-1" style="">llvm</span>::<span class="" id=":tv.27" tabindex="-1" style="">Func</span>(<span class="" id=":tv.28" tabindex="-1" style="">DominatorTree</span> *<span class="" id=":tv.29" tabindex="-1" style="">DT</span>, <span class="" id=":tv.30" tabindex="-1" style="">PostDominatorTree</span> *PDT, <span class="" id=":tv.31" tabindex="-1" style="">LoopInfo</span> *LI){</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:35.4331pt"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">  // Some code from the <span class="" id=":tv.32" tabindex="-1" style="">LLVM</span> code reviewer</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:35.4331pt"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">  if (!<span class="" id=":tv.33" tabindex="-1" style="">DT</span> && !PDT && !LI)</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:35.4331pt"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">    return;</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:35.4331pt"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">  if (<span class="" id=":tv.34" tabindex="-1" style="">DT</span> || PDT) {</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:35.4331pt"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">    // Construct the Updates vector.</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:35.4331pt"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">    if (<span class="" id=":tv.35" tabindex="-1" style="">DT</span>)</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:35.4331pt"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">      <span class="" id=":tv.36" tabindex="-1" style="">DT</span>-><span class="" id=":tv.37" tabindex="-1" style="">applyUpdates</span>(Updates);</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:35.4331pt"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">    if (PDT)</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:35.4331pt"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">      PDT-><span class="" id=":tv.38" tabindex="-1" style="">applyUpdates</span>(Updates);</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:35.4331pt"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">}</span></p><ol style="margin-top:0pt;margin-bottom:0pt" start="2"><li dir="ltr" style="list-style-type:decimal;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">Some functions using both <span class="" id=":tv.39" tabindex="-1" style="">DomTree</span> and <span class="" id=":tv.40" tabindex="-1" style="">PostDomTree</span> need to call the update function separately on both trees. [3] </span></p></li></ol><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:35.4331pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">For example:</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:35.4331pt"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap"><span class="" id=":tv.41" tabindex="-1" style="">DominatorTree</span> <span class="" id=":tv.42" tabindex="-1" style="">DT</span>;</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:35.4331pt"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap"><span class="" id=":tv.43" tabindex="-1" style="">PostDominatorTree</span> PDT;</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:35.4331pt"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap"><b style="font-weight:normal" id="gmail-docs-internal-guid-3b5487cc-dc06-52a6-537a-c13d552e5121"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">...</span></b><br></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:35.4331pt"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap"><span class="" id=":tv.44" tabindex="-1" style="">DT</span>.<span class="" id=":tv.45" tabindex="-1" style="">applyUpdates</span>(Updates);</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;margin-left:35.4331pt"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">PDT.<span class="" id=":tv.46" tabindex="-1" style="">applyUpdates</span>(Updates);</span></p><ol style="margin-top:0pt;margin-bottom:0pt" start="3"><li dir="ltr" style="list-style-type:decimal;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">With the current APIs, we need to manually decide whether to erase a <span class="" id=":tv.47" tabindex="-1" style="">BasicBlock</span> from the <span class="" id=":tv.48" tabindex="-1" style="">dominator</span> tree when one is removed from the <span class="" id=":tv.49" tabindex="-1" style="">CFG</span> [4]. </span></p></li><li dir="ltr" style="list-style-type:decimal;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">When using lazy updating methods, the <span class="" id=":tv.50" tabindex="-1" style="">BasicBlock</span> waiting to delete will be deleted in an unforeseeable time after being removed from the Function so the user cannot do further actions on it.</span></p></li><li dir="ltr" style="list-style-type:decimal;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">When we have both trees (<span class="" id=":tv.51" tabindex="-1" style="">DomTree</span> and <span class="" id=":tv.52" tabindex="-1" style="">PostDomTree</span>), we can try using the update information of one of them to prune updates of another to accelerate the updating process. </span></p></li></ol><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap"> </span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">—General Design—</span></p><ol style="margin-top:0pt;margin-bottom:0pt"><li dir="ltr" style="list-style-type:decimal;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">To address the issue (1), the new updater class needs to have the ability to perform either eager updates or lazy updates. So, all the abilities of the <span class="" id=":tv.53" tabindex="-1" style="">DeferredDominance</span> are subsumed by the new updater class. And the API user can use an <span class="" id=":tv.54" tabindex="-1" style="">enum</span> to specify which update strategy to use.</span></p></li><li dir="ltr" style="list-style-type:decimal;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">To address the issue (2), the new updater class can update all the data structures it holds when the user calls the update function.</span></p></li><li dir="ltr" style="list-style-type:decimal;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">To address the issue (3), the new updater class will first check whether these <span class="" id=":tv.55" tabindex="-1" style="">BasicBlocks</span> still act as a node in the holding trees then call delete to prevent further manual checks. </span></p></li><li dir="ltr" style="list-style-type:decimal;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">To address the issue (4), the updater class adds a </span><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap"><span class="" id=":tv.56" tabindex="-1" style="">callbackDeleteBB</span></span><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap"> function which accepts a callable to let users do additional operations on the <span class="" id=":tv.57" tabindex="-1" style="">BasicBlock</span> before deletion.</span></p></li></ol><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap"> </span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">—More Details—</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">The updater class can be constructed by specifying the related tree and the update strategy. It is because currently, a single pass will only use a single update strategy to update the <span class="" id=":tv.58" tabindex="-1" style="">DomTree</span>/<span class="" id=":tv.59" tabindex="-1" style="">PostDomTree</span>. When using the eager update strategy, it will perform updates the same as holding those trees. If it works in the lazy updating mode, it will perform updates <span class="" id=":tv.60" tabindex="-1" style="">deduplicating</span> and remove invert updates like <span class="" id=":tv.61" tabindex="-1" style="">DeferredDominance</span> class. Users can use </span><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap"><span class="" id=":tv.62" tabindex="-1" style="">hasDomTree</span>()</span><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap"> and </span><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap"><span class="" id=":tv.63" tabindex="-1" style="">hasPostDomTree</span>()</span><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap"> to query which tree the updater holds to enable further uses when passing into functions.</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">—Implementation plan—</span></p><ol style="margin-top:0pt;margin-bottom:0pt"><li dir="ltr" style="list-style-type:decimal;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:10.5pt;font-family:Arial;color:rgb(34,34,34);background-color:rgb(255,255,255);font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">New <span class="" id=":tv.64" tabindex="-1" style="">DomTreeUpdater</span> class, which brings a clean API to update <span class="" id=":tv.65" tabindex="-1" style="">DominatorTree</span> and <span class="" id=":tv.66" tabindex="-1" style="">PostDominatorTree</span> with either deferred/eager update strategy.</span></p></li><li dir="ltr" style="list-style-type:decimal;font-size:10.5pt;font-family:Arial;color:rgb(34,34,34);background-color:rgb(255,255,255);font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:10.5pt;font-family:Arial;color:rgb(34,34,34);background-color:rgb(255,255,255);font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap"><span class="" id=":tv.67" tabindex="-1" style="">Unittests</span> for basic functions of the new class.</span></p></li><li dir="ltr" style="list-style-type:decimal;font-size:10.5pt;font-family:Arial;color:rgb(34,34,34);background-color:rgb(255,255,255);font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:10.5pt;font-family:Arial;color:rgb(34,34,34);background-color:rgb(255,255,255);font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">Replace existing users of <span class="" id=":tv.68" tabindex="-1" style="">DeferredDominance</span> with the new class.</span></p></li><li dir="ltr" style="list-style-type:decimal;font-size:10.5pt;font-family:Arial;color:rgb(34,34,34);background-color:rgb(255,255,255);font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:10.5pt;font-family:Arial;color:rgb(34,34,34);background-color:rgb(255,255,255);font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">Remove <span class="" id=":tv.69" tabindex="-1" style="">DeferredDominance</span>.</span></p></li></ol><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">—Future—</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">Further <span class="" id=":tv.70" tabindex="-1" style="">optimizations</span><b style="font-weight:normal" id="gmail-docs-internal-guid-ea3bbd3c-dc06-fd0b-0a7b-c8aa9bd6a645"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap"> enabled by the new design</span></b>.</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">Thanks,</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap"><span class="" id=":tv.71" tabindex="-1" style="">Chijun</span> <span class="" id=":tv.72" tabindex="-1" style="">Sima</span></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap"> </span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap"> </span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">[1]</span><a href="https://github.com/NutshellySima/llvm/pull/1/files" style="text-decoration:none"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap"> </span><span style="font-size:11pt;font-family:Arial;color:rgb(17,85,204);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:underline;vertical-align:baseline;white-space:pre-wrap">https://<span class="" id=":tv.73" tabindex="-1" style="">github</span>.com/<span class="" id=":tv.74" tabindex="-1" style="">NutshellySima</span>/<span class="" id=":tv.75" tabindex="-1" style="">llvm</span>/pull/1/files</span></a></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">[2]</span><a href="https://llvm.org/doxygen/classllvm_1_1DeferredDominance.html" style="text-decoration:none"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap"> </span><span style="font-size:11pt;font-family:Arial;color:rgb(17,85,204);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:underline;vertical-align:baseline;white-space:pre-wrap">https://<span class="" id=":tv.76" tabindex="-1" style="">llvm</span>.org/<span class="" id=":tv.77" tabindex="-1" style="">doxygen</span>/<span class="" id=":tv.78" tabindex="-1" style="">classllvm</span>_1_1DeferredDominance.html</span></a></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">[3]</span><a href="https://github.com/llvm-mirror/llvm/blob/master/unittests/IR/DominatorTreeBatchUpdatesTest.cpp#L109-L112" style="text-decoration:none"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap"> </span><span style="font-size:11pt;font-family:Arial;color:rgb(17,85,204);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:underline;vertical-align:baseline;white-space:pre-wrap">https://<span class="" id=":tv.79" tabindex="-1" style="">github</span>.com/<span class="" id=":tv.80" tabindex="-1" style="">llvm</span>-mirror/<span class="" id=":tv.81" tabindex="-1" style="">llvm</span>/blob/master/<span class="" id=":tv.82" tabindex="-1" style="">unittests</span>/IR/<span class="" id=":tv.83" tabindex="-1" style="">DominatorTreeBatchUpdatesTest</span>.<span class="" id=":tv.84" tabindex="-1" style="">cpp</span>#L109-L112</span></a></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">[4]</span><a href="https://github.com/llvm-mirror/llvm/blob/master/unittests/IR/DominatorTreeTest.cpp#L578-L584" style="text-decoration:none"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap"> </span><span style="font-size:11pt;font-family:Arial;color:rgb(17,85,204);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:underline;vertical-align:baseline;white-space:pre-wrap">https://<span class="" id=":tv.85" tabindex="-1" style="">github</span>.com/<span class="" id=":tv.86" tabindex="-1" style="">llvm</span>-mirror/<span class="" id=":tv.87" tabindex="-1" style="">llvm</span>/blob/master/<span class="" id=":tv.88" tabindex="-1" style="">unittests</span>/IR/<span class="" id=":tv.89" tabindex="-1" style="">DominatorTreeTest</span>.<span class="" id=":tv.90" tabindex="-1" style="">cpp</span>#L578-L584</span></a></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">[5] </span><a href="https://reviews.llvm.org/D42804" style="text-decoration:none"><span style="font-size:11pt;font-family:Arial;color:rgb(17,85,204);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:underline;vertical-align:baseline;white-space:pre-wrap">https://reviews.<span class="" id=":tv.91" tabindex="-1" style="">llvm</span>.org/D42804</span></a></p></b><br class="gmail-Apple-interchange-newline"><br></div>