<div dir="ltr"><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 tried to use a bitcode file directly:</span><br style="font-size:12.8px"><br style="font-size:12.8px"><span style="font-size:12.8px">...</span><br style="font-size:12.8px"><br style="font-size:12.8px"><span style="font-size:12.8px">It seems the names "inloop" and "next" are not used.</span></blockquote><div><br></div><div>My bad, I almost always use the tool with -view-cfg and didn't notice that BB names were different. I fixed that and now when you just run the dominators tool on a module it should work fine. It now also supports reading .ll files.</div><div><br></div><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">Interesting. Probably it is just a testing/debugging tool, but maybe</span><br style="font-size:12.8px"><span style="font-size:12.8px">clarifying this in the output may avoid confusion for others who try</span><br style="font-size:12.8px"><span style="font-size:12.8px">your changes.</span></blockquote><div>Yep, I briefly mentioned that in the first line of the tool's source file, but I should probably add a note in some more visible place. Sorry for making it confusing.</div><div><br></div><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">We could even have a tool that records the dom-tree modification</span><br style="font-size:12.8px"><span style="font-size:12.8px">requests, and dumps a corresponding IR-file.</span><br style="font-size:12.8px"><br style="font-size:12.8px"><span style="font-size:12.8px">Obviously, this is just an idea.</span></blockquote><div>I'll think about it.<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">Btw, here is another interesting paper about post-dominators and control</span><br style="font-size:12.8px"><span style="font-size:12.8px">dependence:</span><br></blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> <a href="https://pdfs.semanticscholar.org/cbb2/9a0e4895025bd9df24f9263217df12f1ed1e.pdf" rel="noreferrer" target="_blank" style="font-size:12.8px">https://pdfs.semanticscholar.<wbr>org/cbb2/<wbr>9a0e4895025bd9df24f9263217df12<wbr>f1ed1e.pdf</a></blockquote><div>Interesting, thanks for the link, I'll try to take a look at it and probably report back with some ideas and more questions.</div></div><div><br></div><div> Best,<br>Kuba</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Jun 13, 2017 at 1:27 AM, 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">Btw, here is another interesting paper about post-dominators and control<br>
dependence:<br>
<br>
<a href="https://pdfs.semanticscholar.org/cbb2/9a0e4895025bd9df24f9263217df12f1ed1e.pdf" rel="noreferrer" target="_blank">https://pdfs.semanticscholar.<wbr>org/cbb2/<wbr>9a0e4895025bd9df24f9263217df12<wbr>f1ed1e.pdf</a><br>
<br>
I think a great outcome of your internship would be some precise<br>
documentation regarding the guarantees the LLVM dominators give --<br>
possibly also considering classic and weak control dependence and the<br>
difference between loop-dominance and dominance.<br>
<br>
Please keep me up-to-date with your work. This is really work that has<br>
long been overdue!<br>
<br>
Best,<br>
Tobias<br>
<div class="HOEnZb"><div class="h5"><br>
On Tue, Jun 13, 2017, at 10:23 AM, Tobias Grosser via llvm-dev wrote:<br>
> On Tue, Jun 13, 2017, at 09:22 AM, Jakub (Kuba) Kuderski via llvm-dev<br>
> wrote:<br>
> > Tobias,<br>
> ><br>
> > Thanks for the comments and taking a look at my fork.<br>
> ><br>
> ><br>
> > >  -  It would be convenient to allow .ll files to be read.<br>
> ><br>
> > Sure, I can add it tomorrow.<br>
><br>
> Thank you!<br>
><br>
> > - You do not use the BB names in the output, right? This would certainly<br>
> > >    improve readability!<br>
> ><br>
> > You actually don't have to convert you bitcode files to 'graph' files (as<br>
> > long as they contain a single function) -- then names should be<br>
> > preserved,<br>
> > but you don't get to play with updates. The format I'm using isn't very<br>
> > good, but it's compatible with some other implementation by Loucas -- the<br>
> > author of the algorithm.<br>
><br>
> I tried to use a bitcode file directly:<br>
><br>
> [grosser@greina0 build]$ cat ../test/Analysis/RegionInfo/<wbr>test.ll<br>
> define void @foo() {<br>
> entry:<br>
>   br i1 1, label %infloop, label %next<br>
><br>
> infloop:<br>
>   br label %infloop<br>
><br>
> next:<br>
>   ret void<br>
><br>
> [grosser@greina0 build]$ bin/dominators<br>
> ../test/Analysis/RegionInfo/<wbr>test.bc<br>
><br>
> New Dominator Tree:<br>
>   [0] %virtual_entry IO{0, 7}, R{nullptr}, P{nullptr}<br>
>     [1] %entry_n_1 IO{1, 6}, R{virtual_entry}, P{virtual_entry}<br>
>       [2] %n_2 IO{2, 3}, R{entry_n_1}, P{entry_n_1}<br>
>       [2] %n_3 IO{4, 5}, R{entry_n_1}, P{entry_n_1}<br>
><br>
> New Dominator Tree:<br>
>   [0] %virtual_entry IO{0, 7}, R{nullptr}, P{nullptr}<br>
>     [1] %entry_n_1 IO{1, 6}, R{virtual_entry}, P{virtual_entry}<br>
>       [2] %n_2 IO{2, 3}, R{entry_n_1}, P{entry_n_1}<br>
>       [2] %n_3 IO{4, 5}, R{entry_n_1}, P{entry_n_1}<br>
> =============================-<wbr>------------------------------<wbr>-<br>
> Inorder Dominator Tree:<br>
>   [1] %entry_n_1 {0,5}<br>
>     [2] %n_2 {1,2}<br>
>     [2] %n_3 {3,4}<br>
><br>
> It seems the names "inloop" and "next" are not used.<br>
><br>
> > Do you think that having a format like that in<br>
> > LLVM would make sense? Danny and I though about in the context of quickly<br>
> > writing and modifying tests for dominators and things like the NewGVN.<br>
><br>
> For from-scratch dominance computation LLVM-IR seems fine, but for all<br>
> the incremental stuff you are doing, such input indeed might make sense.<br>
> Especially if you are planning to generate many of these test cases<br>
> automatically.<br>
><br>
> > - My output prints "New Dominator Tree" to times in a row. What is the<br>
> > > difference? What is the difference to Inorder Dominator Tree?<br>
> > ><br>
> >  When you graph files have updates (i numFrom numTo and d numFrom numTo)<br>
> > then the first one is the original one and the second one is the one<br>
> > after<br>
> > applying all the updates.<br>
> > Inorder Dominator Tree is the existing DomTree<br>
><br>
> Interesting. Probably it is just a testing/debugging tool, but maybe<br>
> clarifying this in the output may avoid confusion for others who try<br>
> your changes.<br>
><br>
> > --<br>
> > I used to use it just for visual comparison.<br>
><br>
> That's what I did.<br>
><br>
> > - How do I get the post-dominator tree with your tool? Do you already<br>
> > > have test cases? In fact, normal IR test cases would be really cool. We<br>
> > > do not have a lot of test coverage for all the dominance stuff.<br>
> ><br>
> >  I haven't really played with postdominators yet. Do you have any<br>
> >  specific<br>
> > ideas on how to test it in mind? And I definitely agree, dominators need<br>
> > to<br>
> > be tested more thoroughly. I think that because of the manual updates (of<br>
> > questionable correctness) and frequent recalculations there must be many<br>
> > undiscovered bugs that we just haven't had a chance to observe yet.<br>
><br>
> I think we certainly should have standard LLVM-IR style test cases,<br>
> where we use -analyze to dump the domtree for a given piece of IR that<br>
> clarfies how/what dominator tree is expected for a certain piece of<br>
> input and where it is easy for others to add test cases.<br>
><br>
> Now, most of the bugs you might expect are likely in the update /<br>
> invalidation cycle. What would look very nice and readable to me, is to<br>
> write test cases as follows:<br>
><br>
> ; RUN: opt -domtree -domtree-modifier -dom-tree-modifier-input=%s \<br>
> ; RUN:   < %s | FileCheck %s<br>
> ;<br>
> ; CHECK-LABEL; delete (bb3 -> bb4)<br>
> ; CHECK: <new-dom-tree><br>
><br>
> ; CHECK-LABEL; delete (bb4 -> bb5)<br>
> ; CHECK: <new-dom-tree><br>
><br>
> ....<br>
><br>
> We could even have a tool that records the dom-tree modification<br>
> requests, and dumps a corresponding IR-file.<br>
><br>
> Obviously, this is just an idea.<br>
><br>
> Best,<br>
> Tobias<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>