llvm dev - Dec 2017 - Dominator tree side effect or intentional

Hello,

I was wondering whether or not some behaviour that I am seeing is expected
behaviour and that it has been designed like this, or not.

A dominator relation is given by "if A dominates B", then all paths to
B go through A.

For example, take the CFG below (which is a directed graph (couldn’t make the
arrow heads but ok.):
   A
 /   \
B     C
 \   /
   D
   |
   E

We can construct the following dominator tree for the CFG above, DomTree:
    A
 /  |  \
B   D   C
    |
    E

I want my pass to do a top-down traversal on the basic blocks in a function. I
now have an approach where you start at the root of the dominator tree and build
a work list by visiting all children, similar or the same as in MachineCSE. Now
I see the following behaviour: when I visit the nodes of the root (A in this
case), its children have the nice property that B and C come before D. This is
actually what I want, but is this on purpose, or not? It is kind of hard to
proof that B and C come before D when iterating through the children of the root
in this dominator tree.

Is it safe to assume that this always happens? If you look at dominator theory
only, then D can just as well come before C, since they are on the same level,
namely, as children of A.
Has the topological order been taken into account such that iterating through
children of a dominator tree node, visits children first that would be strictly
before other children in topological order?

Hope my question is clear enough.

Kind regards,
Guus Leijsten
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171027/d3b36acf/attachment.html>

Hi Guus,

In (Post)DominatorTree children (of the same parent) are unordered. The
thing you observed is the result of the initial DFS walk on the CFG that
uses the `successors` and `predecessors` functions.

There is no strong guarantee of the order of children in a freshly
constructed (post)dom tree, and it was in fact changed for postdominators a
few months ago without any breakage that I know of. What's more, the order
can be changed during a domtree update.

On top of that, you have to keep in mind that the LLVM's implementation of
the DominatorTree doesn't store nodes (forward) unreachable basic blocks,
and it claims that every node dominates a (forward) unreachable node.

Wouldn't a BFS RPO perhaps work in your case?

Hope that this makes things a bit more clear,
Kuba


On Fri, Oct 27, 2017 at 8:03 AM, Leijsten, G.H.P. via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hello,
>
> I was wondering whether or not some behaviour that I am seeing is expected
> behaviour and that it has been designed like this, or not.
>
> A dominator relation is given by "if A dominates B", then all
paths to B
> go through A.
>
> For example, take the CFG below (which is a directed graph (couldn’t make
> the arrow heads but ok.):
>    A
>  /   \
> B     C
>  \   /
>    D
>    |
>    E
>
> We can construct the following dominator tree for the CFG above, DomTree:
>     A
>  /  |  \
> B   D   C
>     |
>     E
>
> I want my pass to do a top-down traversal on the basic blocks in a
> function. I now have an approach where you start at the root of the
> dominator tree and build a work list by visiting all children, similar or
> the same as in MachineCSE. Now I see the following behaviour: when I visit
> the nodes of the root (A in this case), its children have the nice property
> that B and C come before D. This is actually what I want, but is this on
> purpose, or not? It is kind of hard to proof that B and C come before D
> when iterating through the children of the root in this dominator tree.
>
> Is it safe to assume that this always happens? If you look at dominator
> theory only, then D can just as well come before C, since they are on the
> same level, namely, as children of A.
> Has the topological order been taken into account such that iterating
> through children of a dominator tree node, visits children first that would
> be strictly before other children in topological order?
>
> Hope my question is clear enough.
>
> Kind regards,
> Guus Leijsten
>
> _______________________________________________
> 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/20171027/ce4340ea/attachment.html>

On Fri, Oct 27, 2017 at 5:03 AM, Leijsten, G.H.P. via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hello,
>
> I was wondering whether or not some behaviour that I am seeing is expected
> behaviour and that it has been designed like this, or not.
>
> A dominator relation is given by "if A dominates B", then all
paths to B
> go through A.
>
> For example, take the CFG below (which is a directed graph (couldn’t make
> the arrow heads but ok.):
>    A
>  /   \
> B     C
>  \   /
>    D
>    |
>    E
>
> We can construct the following dominator tree for the CFG above, DomTree:
>     A
>  /  |  \
> B   D   C
>     |
>     E
>
> I want my pass to do a top-down traversal on the basic blocks in a
> function. I now have an approach where you start at the root of the
> dominator tree and build a work list by visiting all children, similar or
> the same as in MachineCSE. Now I see the following behaviour: when I visit
> the nodes of the root (A in this case), its children have the nice property
> that B and C come before D. This is actually what I want, but is this on
> purpose, or not? It is kind of hard to proof that B and C come before D
> when iterating through the children of the root in this dominator tree.
>
No, the only way to guarantee this is a reverse postorder traversal.

NewGVN actually sorts the siblings of the dominator tree into RPO order
(since the parent-child relationship is already an RPO) so it can just walk
the dominator tree.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171027/d459eb49/attachment.html>

Hi Kuba,

Thanks for clearing that up.

Now I see the following behaviour: when I visit the nodes of the root (A in this
case), its children have the nice property that B and C come before D. This is
actually what I want, but is this on purpose, or not? It is kind of hard to
proof that B and C come before D when iterating through the children of the root
in this dominator tree.
After some time, I can contradict the above statement (that I wrote in Oktober)
with a yuv2rgb benchmark and the children of a dominator tree or the successors
of a basic block are indeed unordered like you said already.


Kind regards,
Guus Leijsten


On 28 Oct 2017, at 22:25, Jakub (Kuba) Kuderski <kubakuderski at
gmail.com<mailto:kubakuderski at gmail.com>> wrote:

Hi Guus,

Yes I think this will work, however, I still have doubt on one small detail.
In the post order traversal, that I am using, does the range based iterator
always visit both B and C, before D? That is, does the ReversePostOrderTraversal
do a breadth first search? Not sure, but I think it does do it breadth first.

I haven't used it much, but I think that ReversePostOrderTravelsal is DFS.
The simplest way to get the order you want would be to use the DT and sort the
siblings by their order in RPO, as Danny mentioned.

https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/Scalar/NewGVN.cpp#L3406

Best,
Kuba

On Sat, Oct 28, 2017 at 9:31 AM, Leijsten, G.H.P. <g.h.p.leijsten at
student.tue.nl<mailto:g.h.p.leijsten at student.tue.nl>> wrote:
Hey Kuba,

Thanks of the explanation. I added an include to llvm/ADT/PostOrderIterator.h
and get a ranged based iterator with the following single line of code:

ReversePostOrderTraversal<MachineFunction*> RPOT(&MF);

The post order traversal is now done as follows:

for (MachineBasicBlock *MBB : RPOT)
    <do work>

Wouldn't a BFS RPO perhaps work in your case?
Yes I think this will work, however, I still have doubt on one small detail.
In the post order traversal, that I am using, does the range based iterator
always visit both B and C, before D? That is, does the ReversePostOrderTraversal
do a breadth first search? Not sure, but I think it does do it breadth first.

Anyway,
Thanks for the quick responses.

Kind regards,
Guus Leijsten

On 27 Oct 2017, at 16:12, Jakub (Kuba) Kuderski <kubakuderski at
gmail.com<mailto:kubakuderski at gmail.com>> wrote:

Hi Guus,

In (Post)DominatorTree children (of the same parent) are unordered. The thing
you observed is the result of the initial DFS walk on the CFG that uses the
`successors` and `predecessors` functions.

There is no strong guarantee of the order of children in a freshly constructed
(post)dom tree, and it was in fact changed for postdominators a few months ago
without any breakage that I know of. What's more, the order can be changed
during a domtree update.

On top of that, you have to keep in mind that the LLVM's implementation of
the DominatorTree doesn't store nodes (forward) unreachable basic blocks,
and it claims that every node dominates a (forward) unreachable node.

Wouldn't a BFS RPO perhaps work in your case?

Hope that this makes things a bit more clear,
Kuba


On Fri, Oct 27, 2017 at 8:03 AM, Leijsten, G.H.P. via llvm-dev <llvm-dev at
lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:
Hello,

I was wondering whether or not some behaviour that I am seeing is expected
behaviour and that it has been designed like this, or not.

A dominator relation is given by "if A dominates B", then all paths to
B go through A.

For example, take the CFG below (which is a directed graph (couldn’t make the
arrow heads but ok.):
   A
 /   \
B     C
 \   /
   D
   |
   E

We can construct the following dominator tree for the CFG above, DomTree:
    A
 /  |  \
B   D   C
    |
    E

I want my pass to do a top-down traversal on the basic blocks in a function. I
now have an approach where you start at the root of the dominator tree and build
a work list by visiting all children, similar or the same as in MachineCSE. Now
I see the following behaviour: when I visit the nodes of the root (A in this
case), its children have the nice property that B and C come before D. This is
actually what I want, but is this on purpose, or not? It is kind of hard to
proof that B and C come before D when iterating through the children of the root
in this dominator tree.

Is it safe to assume that this always happens? If you look at dominator theory
only, then D can just as well come before C, since they are on the same level,
namely, as children of A.
Has the topological order been taken into account such that iterating through
children of a dominator tree node, visits children first that would be strictly
before other children in topological order?

Hope my question is clear enough.

Kind regards,
Guus Leijsten

_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev




--
Jakub Kuderski




--
Jakub Kuderski


-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171221/099026f1/attachment.html>