<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Oct 27, 2017 at 5: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></blockquote><div><br></div><div>No, the only way to guarantee this is a reverse postorder traversal.</div><div><br></div><div>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.</div><div><br></div><div><br></div></div></div></div>