[llvm-dev] Dominator tree side effect or intentional

[Leijsten, G.H.P. via llvm-dev]

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>