[llvm-dev] RFC: Dynamic dominators

Tue Jun 13 15:12:16 PDT 2017

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