[llvm-dev] RFC: Dynamic dominators
Tobias Grosser via llvm-dev
llvm-dev at lists.llvm.org
Tue Jun 13 01:23:20 PDT 2017
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
More information about the llvm-dev
mailing list