<div dir="ltr"><span id="gmail-docs-internal-guid-a4916f74-ebab-6f79-523e-be6e1f4a1f73"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt;text-align:justify"><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">I’m wor</span><span style="font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">king on adding an API for incremental updates to DominatorTree and I noticed that there isn’t a simple way to quickly build and update CFG (just for testing) -- one has to either build CFG programmatically, or write IR by hand and manually map pointers to </span><span style="font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">basic blocks. The downside is that it tends to be pretty verbose and not easy to update (e.g. adding a new edge often involves changing the type of terminator instruction).</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">My idea is to create a simple format for building arbitrary CFG’s and new utilities for updating it.</span></p><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">It can look something like this:</span><span style="font-size:11pt;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-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">b ModuleName FunctionName // Build module ‘ModuleName’ with a single</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">                          // function ‘FunctionName’.</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">a entry if                // Add new basic blocks (entry and if) and</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">                          // connect them with an edge.</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">a if if.then              // Add new basic block (if.then) and create </span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">                          // an edge from if to if.then</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">a if if.else</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">a if.then foo</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">a if.else foo</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">a bar                     // Add a new block bar, but don’t create </span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">                          // any edges. </span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">e                         // Finish constructing initial CFG</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">i foo bar                 // Insert and edge from foo to bar.</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">d if if.then              // Delete the edge from if to if.then.</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">i if bar                  // Insert an edge from if to bar.</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"> </span><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;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-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Under the hood, the utility would build IR with just switch instructions.</span></p><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">Then you could assign it to a string and use in a unit test:</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">CFGBuilder B(MyString);</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Function *F = B.getFunction();</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;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:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">while (!B.finished()) {</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">    Update U = B.applyNextUpdate(); // B changes the CFG.   </span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">// U stores type of update (insertion/deletion) and a pair of BB’s </span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">// (From and To).</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">    doSomethingWithTheUpdate(U);</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">}</span></p><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">Other CFG passes (e.g. LoopInfo, NewGVN) could also use it for testing. It would be also possible to hook it up to a fuzzer at some point in the future.</span></p><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"> </span></p><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">What do you think about having such a utility in llvm?</span></p><div><span style="font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"><span style="font-size:11pt">
</span>~Kuba</span></div></span><div><br></div>-- <br><div class="gmail_signature"><div>Jakub Kuderski</div></div>
</div>