<div dir="ltr">Hi Guus,<br><br>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.<br><br>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.<br><br>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.<br><br>Wouldn't a BFS RPO perhaps work in your case?<br><br>Hope that this makes things a bit more clear,<br>Kuba<br><br><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Oct 27, 2017 at 8:03 AM, Leijsten, G.H.P. via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">



<div style="word-wrap:break-word">
Hello,
<div><br>
</div>
<div>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.</div>
<div><br>
</div>
<div>A dominator relation is given by "if A dominates B", then all paths to B go through A.</div>
<div><br>
</div>
<div>For example, take the CFG below (which is a directed graph (couldn’t make the arrow heads but ok.):</div>
<div><font face="Menlo">   A</font></div>
<div><font face="Menlo"> /   \</font></div>
<div><font face="Menlo">B     C</font></div>
<div><font face="Menlo"> \   /</font></div>
<div><font face="Menlo">   D</font></div>
<div><font face="Menlo">   |</font></div>
<div><font face="Menlo">   E </font></div>
<div><br>
</div>
<div>We can construct the following dominator tree for the CFG above, DomTree:</div>
<div><font face="Menlo">    A</font></div>
<div><font face="Menlo"> /  |  \</font></div>
<div><font face="Menlo">B   D   C</font></div>
<div><font face="Menlo">    |</font></div>
<div><font face="Menlo">    E</font></div>
<div><br>
</div>
<div>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. </div>
<div><br>
</div>
<div>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. </div>
<div>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?</div>
<div><br>
</div>
<div>Hope my question is clear enough.</div>
<div><br>
</div>
<div>Kind regards,</div>
<div>Guus Leijsten </div>
</div>

<br>______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
<br></blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="m_-3580891849680935332m_-6185738293544003221gmail_signature" data-smartmail="gmail_signature"><div>Jakub Kuderski</div></div>
</div></div>