[llvm-dev] Dominator tree side effect or intentional

[Daniel Berlin via llvm-dev]

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>