Btw, here is another interesting paper about post-dominators and control dependence: https://pdfs.semanticscholar.org/cbb2/9a0e4895025bd9df24f9263217df12f1ed1e.pdf I think a great outcome of your internship would be some precise documentation regarding the guarantees the LLVM dominators give -- possibly also considering classic and weak control dependence and the difference between loop-dominance and dominance. Please keep me up-to-date with your work. This is really work that has long been overdue! Best, Tobias On Tue, Jun 13, 2017, at 10:23 AM, Tobias Grosser via llvm-dev wrote:> On Tue, Jun 13, 2017, at 09:22 AM, Jakub (Kuba) Kuderski via llvm-dev > wrote: > > Tobias, > > > > Thanks for the comments and taking a look at my fork. > > > > > > > - It would be convenient to allow .ll files to be read. > > > > Sure, I can add it tomorrow. > > Thank you! > > > - You do not use the BB names in the output, right? This would certainly > > > improve readability! > > > > You actually don't have to convert you bitcode files to 'graph' files (as > > long as they contain a single function) -- then names should be > > preserved, > > but you don't get to play with updates. The format I'm using isn't very > > good, but it's compatible with some other implementation by Loucas -- the > > author of the algorithm. > > I tried to use a bitcode file directly: > > [grosser at greina0 build]$ cat ../test/Analysis/RegionInfo/test.ll > define void @foo() { > entry: > br i1 1, label %infloop, label %next > > infloop: > br label %infloop > > next: > ret void > > [grosser at greina0 build]$ bin/dominators > ../test/Analysis/RegionInfo/test.bc > > New Dominator Tree: > [0] %virtual_entry IO{0, 7}, R{nullptr}, P{nullptr} > [1] %entry_n_1 IO{1, 6}, R{virtual_entry}, P{virtual_entry} > [2] %n_2 IO{2, 3}, R{entry_n_1}, P{entry_n_1} > [2] %n_3 IO{4, 5}, R{entry_n_1}, P{entry_n_1} > > New Dominator Tree: > [0] %virtual_entry IO{0, 7}, R{nullptr}, P{nullptr} > [1] %entry_n_1 IO{1, 6}, R{virtual_entry}, P{virtual_entry} > [2] %n_2 IO{2, 3}, R{entry_n_1}, P{entry_n_1} > [2] %n_3 IO{4, 5}, R{entry_n_1}, P{entry_n_1} > =============================-------------------------------- > Inorder Dominator Tree: > [1] %entry_n_1 {0,5} > [2] %n_2 {1,2} > [2] %n_3 {3,4} > > It seems the names "inloop" and "next" are not used. > > > Do you think that having a format like that in > > LLVM would make sense? Danny and I though about in the context of quickly > > writing and modifying tests for dominators and things like the NewGVN. > > For from-scratch dominance computation LLVM-IR seems fine, but for all > the incremental stuff you are doing, such input indeed might make sense. > Especially if you are planning to generate many of these test cases > automatically. > > > - My output prints "New Dominator Tree" to times in a row. What is the > > > difference? What is the difference to Inorder Dominator Tree? > > > > > When you graph files have updates (i numFrom numTo and d numFrom numTo) > > then the first one is the original one and the second one is the one > > after > > applying all the updates. > > Inorder Dominator Tree is the existing DomTree > > Interesting. Probably it is just a testing/debugging tool, but maybe > clarifying this in the output may avoid confusion for others who try > your changes. > > > -- > > I used to use it just for visual comparison. > > That's what I did. > > > - How do I get the post-dominator tree with your tool? Do you already > > > have test cases? In fact, normal IR test cases would be really cool. We > > > do not have a lot of test coverage for all the dominance stuff. > > > > I haven't really played with postdominators yet. Do you have any > > specific > > ideas on how to test it in mind? And I definitely agree, dominators need > > to > > be tested more thoroughly. I think that because of the manual updates (of > > questionable correctness) and frequent recalculations there must be many > > undiscovered bugs that we just haven't had a chance to observe yet. > > I think we certainly should have standard LLVM-IR style test cases, > where we use -analyze to dump the domtree for a given piece of IR that > clarfies how/what dominator tree is expected for a certain piece of > input and where it is easy for others to add test cases. > > Now, most of the bugs you might expect are likely in the update / > invalidation cycle. What would look very nice and readable to me, is to > write test cases as follows: > > ; RUN: opt -domtree -domtree-modifier -dom-tree-modifier-input=%s \ > ; RUN: < %s | FileCheck %s > ; > ; CHECK-LABEL; delete (bb3 -> bb4) > ; CHECK: <new-dom-tree> > > ; CHECK-LABEL; delete (bb4 -> bb5) > ; CHECK: <new-dom-tree> > > .... > > We could even have a tool that records the dom-tree modification > requests, and dumps a corresponding IR-file. > > Obviously, this is just an idea. > > Best, > Tobias > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Jakub (Kuba) Kuderski via llvm-dev
2017-Jun-13 18:14 UTC
[llvm-dev] RFC: Dynamic dominators
> > I tried to use a bitcode file directly: > > ... > > It seems the names "inloop" and "next" are not used.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. Interesting. Probably it is just a testing/debugging tool, but maybe> clarifying this in the output may avoid confusion for others who try > your changes.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. We could even have a tool that records the dom-tree modification> requests, and dumps a corresponding IR-file. > > Obviously, this is just an idea.I'll think about it. Btw, here is another interesting paper about post-dominators and control> dependence: >https://pdfs.semanticscholar.org/cbb2/9a0e4895025bd9df24f9263217df12> f1ed1e.pdfInteresting, thanks for the link, I'll try to take a look at it and probably report back with some ideas and more questions. Best, Kuba On Tue, Jun 13, 2017 at 1:27 AM, Tobias Grosser <tobias.grosser at inf.ethz.ch> wrote:> Btw, here is another interesting paper about post-dominators and control > dependence: > > https://pdfs.semanticscholar.org/cbb2/9a0e4895025bd9df24f9263217df12 > f1ed1e.pdf > > I think a great outcome of your internship would be some precise > documentation regarding the guarantees the LLVM dominators give -- > possibly also considering classic and weak control dependence and the > difference between loop-dominance and dominance. > > Please keep me up-to-date with your work. This is really work that has > long been overdue! > > Best, > Tobias > > On Tue, Jun 13, 2017, at 10:23 AM, Tobias Grosser via llvm-dev wrote: > > On Tue, Jun 13, 2017, at 09:22 AM, Jakub (Kuba) Kuderski via llvm-dev > > wrote: > > > Tobias, > > > > > > Thanks for the comments and taking a look at my fork. > > > > > > > > > > - It would be convenient to allow .ll files to be read. > > > > > > Sure, I can add it tomorrow. > > > > Thank you! > > > > > - You do not use the BB names in the output, right? This would > certainly > > > > improve readability! > > > > > > You actually don't have to convert you bitcode files to 'graph' files > (as > > > long as they contain a single function) -- then names should be > > > preserved, > > > but you don't get to play with updates. The format I'm using isn't very > > > good, but it's compatible with some other implementation by Loucas -- > the > > > author of the algorithm. > > > > I tried to use a bitcode file directly: > > > > [grosser at greina0 build]$ cat ../test/Analysis/RegionInfo/test.ll > > define void @foo() { > > entry: > > br i1 1, label %infloop, label %next > > > > infloop: > > br label %infloop > > > > next: > > ret void > > > > [grosser at greina0 build]$ bin/dominators > > ../test/Analysis/RegionInfo/test.bc > > > > New Dominator Tree: > > [0] %virtual_entry IO{0, 7}, R{nullptr}, P{nullptr} > > [1] %entry_n_1 IO{1, 6}, R{virtual_entry}, P{virtual_entry} > > [2] %n_2 IO{2, 3}, R{entry_n_1}, P{entry_n_1} > > [2] %n_3 IO{4, 5}, R{entry_n_1}, P{entry_n_1} > > > > New Dominator Tree: > > [0] %virtual_entry IO{0, 7}, R{nullptr}, P{nullptr} > > [1] %entry_n_1 IO{1, 6}, R{virtual_entry}, P{virtual_entry} > > [2] %n_2 IO{2, 3}, R{entry_n_1}, P{entry_n_1} > > [2] %n_3 IO{4, 5}, R{entry_n_1}, P{entry_n_1} > > =============================-------------------------------- > > Inorder Dominator Tree: > > [1] %entry_n_1 {0,5} > > [2] %n_2 {1,2} > > [2] %n_3 {3,4} > > > > It seems the names "inloop" and "next" are not used. > > > > > Do you think that having a format like that in > > > LLVM would make sense? Danny and I though about in the context of > quickly > > > writing and modifying tests for dominators and things like the NewGVN. > > > > For from-scratch dominance computation LLVM-IR seems fine, but for all > > the incremental stuff you are doing, such input indeed might make sense. > > Especially if you are planning to generate many of these test cases > > automatically. > > > > > - My output prints "New Dominator Tree" to times in a row. What is the > > > > difference? What is the difference to Inorder Dominator Tree? > > > > > > > When you graph files have updates (i numFrom numTo and d numFrom > numTo) > > > then the first one is the original one and the second one is the one > > > after > > > applying all the updates. > > > Inorder Dominator Tree is the existing DomTree > > > > Interesting. Probably it is just a testing/debugging tool, but maybe > > clarifying this in the output may avoid confusion for others who try > > your changes. > > > > > -- > > > I used to use it just for visual comparison. > > > > That's what I did. > > > > > - How do I get the post-dominator tree with your tool? Do you already > > > > have test cases? In fact, normal IR test cases would be really cool. > We > > > > do not have a lot of test coverage for all the dominance stuff. > > > > > > I haven't really played with postdominators yet. Do you have any > > > specific > > > ideas on how to test it in mind? And I definitely agree, dominators > need > > > to > > > be tested more thoroughly. I think that because of the manual updates > (of > > > questionable correctness) and frequent recalculations there must be > many > > > undiscovered bugs that we just haven't had a chance to observe yet. > > > > I think we certainly should have standard LLVM-IR style test cases, > > where we use -analyze to dump the domtree for a given piece of IR that > > clarfies how/what dominator tree is expected for a certain piece of > > input and where it is easy for others to add test cases. > > > > Now, most of the bugs you might expect are likely in the update / > > invalidation cycle. What would look very nice and readable to me, is to > > write test cases as follows: > > > > ; RUN: opt -domtree -domtree-modifier -dom-tree-modifier-input=%s \ > > ; RUN: < %s | FileCheck %s > > ; > > ; CHECK-LABEL; delete (bb3 -> bb4) > > ; CHECK: <new-dom-tree> > > > > ; CHECK-LABEL; delete (bb4 -> bb5) > > ; CHECK: <new-dom-tree> > > > > .... > > > > We could even have a tool that records the dom-tree modification > > requests, and dumps a corresponding IR-file. > > > > Obviously, this is just an idea. > > > > Best, > > Tobias > > _______________________________________________ > > LLVM Developers mailing list > > llvm-dev at lists.llvm.org > > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >-- Jakub Kuderski -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170613/073ccdc4/attachment.html>
On Tue, Jun 13, 2017, at 08:14 PM, Jakub (Kuba) Kuderski via llvm-dev wrote:> > > > I tried to use a bitcode file directly: > > > > ... > > > > It seems the names "inloop" and "next" are not used. > > > 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. > > Interesting. Probably it is just a testing/debugging tool, but maybe > > clarifying this in the output may avoid confusion for others who try > > your changes. > > 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.Great. It now works as expected. I still don't have an option to compute post-dominators (I assume it is not yet implemented), but otherwise the tools now does what I expect. Thanks for improving it! Best, Tobias> We could even have a tool that records the dom-tree modification > > requests, and dumps a corresponding IR-file. > > > > Obviously, this is just an idea. > > I'll think about it. > > Btw, here is another interesting paper about post-dominators and control > > dependence: > > > https://pdfs.semanticscholar.org/cbb2/9a0e4895025bd9df24f9263217df12 > > f1ed1e.pdf > > Interesting, thanks for the link, I'll try to take a look at it and > probably report back with some ideas and more questions. > > Best, > Kuba > > On Tue, Jun 13, 2017 at 1:27 AM, Tobias Grosser > <tobias.grosser at inf.ethz.ch> > wrote: > > > Btw, here is another interesting paper about post-dominators and control > > dependence: > > > > https://pdfs.semanticscholar.org/cbb2/9a0e4895025bd9df24f9263217df12 > > f1ed1e.pdf > > > > I think a great outcome of your internship would be some precise > > documentation regarding the guarantees the LLVM dominators give -- > > possibly also considering classic and weak control dependence and the > > difference between loop-dominance and dominance. > > > > Please keep me up-to-date with your work. This is really work that has > > long been overdue! > > > > Best, > > Tobias > > > > On Tue, Jun 13, 2017, at 10:23 AM, Tobias Grosser via llvm-dev wrote: > > > On Tue, Jun 13, 2017, at 09:22 AM, Jakub (Kuba) Kuderski via llvm-dev > > > wrote: > > > > Tobias, > > > > > > > > Thanks for the comments and taking a look at my fork. > > > > > > > > > > > > > - It would be convenient to allow .ll files to be read. > > > > > > > > Sure, I can add it tomorrow. > > > > > > Thank you! > > > > > > > - You do not use the BB names in the output, right? This would > > certainly > > > > > improve readability! > > > > > > > > You actually don't have to convert you bitcode files to 'graph' files > > (as > > > > long as they contain a single function) -- then names should be > > > > preserved, > > > > but you don't get to play with updates. The format I'm using isn't very > > > > good, but it's compatible with some other implementation by Loucas -- > > the > > > > author of the algorithm. > > > > > > I tried to use a bitcode file directly: > > > > > > [grosser at greina0 build]$ cat ../test/Analysis/RegionInfo/test.ll > > > define void @foo() { > > > entry: > > > br i1 1, label %infloop, label %next > > > > > > infloop: > > > br label %infloop > > > > > > next: > > > ret void > > > > > > [grosser at greina0 build]$ bin/dominators > > > ../test/Analysis/RegionInfo/test.bc > > > > > > New Dominator Tree: > > > [0] %virtual_entry IO{0, 7}, R{nullptr}, P{nullptr} > > > [1] %entry_n_1 IO{1, 6}, R{virtual_entry}, P{virtual_entry} > > > [2] %n_2 IO{2, 3}, R{entry_n_1}, P{entry_n_1} > > > [2] %n_3 IO{4, 5}, R{entry_n_1}, P{entry_n_1} > > > > > > New Dominator Tree: > > > [0] %virtual_entry IO{0, 7}, R{nullptr}, P{nullptr} > > > [1] %entry_n_1 IO{1, 6}, R{virtual_entry}, P{virtual_entry} > > > [2] %n_2 IO{2, 3}, R{entry_n_1}, P{entry_n_1} > > > [2] %n_3 IO{4, 5}, R{entry_n_1}, P{entry_n_1} > > > =============================-------------------------------- > > > Inorder Dominator Tree: > > > [1] %entry_n_1 {0,5} > > > [2] %n_2 {1,2} > > > [2] %n_3 {3,4} > > > > > > It seems the names "inloop" and "next" are not used. > > > > > > > Do you think that having a format like that in > > > > LLVM would make sense? Danny and I though about in the context of > > quickly > > > > writing and modifying tests for dominators and things like the NewGVN. > > > > > > For from-scratch dominance computation LLVM-IR seems fine, but for all > > > the incremental stuff you are doing, such input indeed might make sense. > > > Especially if you are planning to generate many of these test cases > > > automatically. > > > > > > > - My output prints "New Dominator Tree" to times in a row. What is the > > > > > difference? What is the difference to Inorder Dominator Tree? > > > > > > > > > When you graph files have updates (i numFrom numTo and d numFrom > > numTo) > > > > then the first one is the original one and the second one is the one > > > > after > > > > applying all the updates. > > > > Inorder Dominator Tree is the existing DomTree > > > > > > Interesting. Probably it is just a testing/debugging tool, but maybe > > > clarifying this in the output may avoid confusion for others who try > > > your changes. > > > > > > > -- > > > > I used to use it just for visual comparison. > > > > > > That's what I did. > > > > > > > - How do I get the post-dominator tree with your tool? Do you already > > > > > have test cases? In fact, normal IR test cases would be really cool. > > We > > > > > do not have a lot of test coverage for all the dominance stuff. > > > > > > > > I haven't really played with postdominators yet. Do you have any > > > > specific > > > > ideas on how to test it in mind? And I definitely agree, dominators > > need > > > > to > > > > be tested more thoroughly. I think that because of the manual updates > > (of > > > > questionable correctness) and frequent recalculations there must be > > many > > > > undiscovered bugs that we just haven't had a chance to observe yet. > > > > > > I think we certainly should have standard LLVM-IR style test cases, > > > where we use -analyze to dump the domtree for a given piece of IR that > > > clarfies how/what dominator tree is expected for a certain piece of > > > input and where it is easy for others to add test cases. > > > > > > Now, most of the bugs you might expect are likely in the update / > > > invalidation cycle. What would look very nice and readable to me, is to > > > write test cases as follows: > > > > > > ; RUN: opt -domtree -domtree-modifier -dom-tree-modifier-input=%s \ > > > ; RUN: < %s | FileCheck %s > > > ; > > > ; CHECK-LABEL; delete (bb3 -> bb4) > > > ; CHECK: <new-dom-tree> > > > > > > ; CHECK-LABEL; delete (bb4 -> bb5) > > > ; CHECK: <new-dom-tree> > > > > > > .... > > > > > > We could even have a tool that records the dom-tree modification > > > requests, and dumps a corresponding IR-file. > > > > > > Obviously, this is just an idea. > > > > > > Best, > > > Tobias > > > _______________________________________________ > > > LLVM Developers mailing list > > > llvm-dev at lists.llvm.org > > > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev > > > > > > -- > Jakub Kuderski > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev