<div dir="ltr">Tobias, David,<br><br>Thanks for sharing your opinions and concerns.<br><br>After some prototyping and an offline discussion with David, I think that it would be better to take a few steps back of the initial proposal. At this point it is not clear if and how such a tool would be useful for testing things other than dominators. It would certainly be a burden to commit and later maintain even a very small and simplistic DSL, especially if it was to be exposed by other tools (e.g. opt).<br><br>I believe that a better way forward would be to create a small and simple library-only solutions used only by dominator tests -- at least for now. I created a prototype which you can find here: <a href="https://reviews.llvm.org/D34798">https://reviews.llvm.org/D34798</a>.<br><br>With this design it shouldn't be expensive to extend it later, when it gains actual users (like the mentioned LoopInfo and NewGVN), or to even create a think wrapper for handling a custom DSL.<br><br>Please let me know what you think.<br><br>Thanks,<br><div>~Kuba</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Jun 28, 2017 at 7:39 AM, David Blaikie <span dir="ltr"><<a href="mailto:dblaikie@gmail.com" target="_blank">dblaikie@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">Off the cuff, I'd probably err on the side of improving/simplifying the API for building/querying the CFG if it's possible to go far enough along that route to address the issues (fuzzing could still be done there - by taking a byte array from libFuzzer and using the bytes to drive API calls to build a CFG, for example (is this byte less than <some constant> -> make an edge, etc)). But I realize there might be good reasons it's not practical - it'd be worth understanding/documenting those reasons before starting on a new tool/format/etc, I think.<br><br><div class="gmail_quote"><div><div class="h5"><div dir="ltr">On Tue, Jun 27, 2017 at 3:32 PM Jakub (Kuba) Kuderski via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<br></div></div></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div class="h5"><div dir="ltr"><span id="m_-270200727532502994m_-4449838116168653267gmail-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="m_-270200727532502994m_-4449838116168653267gmail-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_-270200727532502994m_-4449838116168653267gmail-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="m_-270200727532502994m_-4449838116168653267gmail-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_-270200727532502994m_-4449838116168653267gmail-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="m_-270200727532502994m_-4449838116168653267gmail-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)<wbr>;</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="m_-270200727532502994m_-4449838116168653267gmail_signature"><div>Jakub Kuderski</div></div>
</div></div></div><span class="">
______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">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>
</span></blockquote></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>