<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">
Hello,
<div class=""><br class="">
</div>
<div class="">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 class=""><br class="">
</div>
<div class="">A dominator relation is given by "if A dominates B", then all paths to B go through A.</div>
<div class=""><br class="">
</div>
<div class="">For example, take the CFG below (which is a directed graph (couldn’t make the arrow heads but ok.):</div>
<div class=""><font face="Menlo" class=""> A</font></div>
<div class=""><font face="Menlo" class=""> / \</font></div>
<div class=""><font face="Menlo" class="">B C</font></div>
<div class=""><font face="Menlo" class=""> \ /</font></div>
<div class=""><font face="Menlo" class=""> D</font></div>
<div class=""><font face="Menlo" class=""> |</font></div>
<div class=""><font face="Menlo" class=""> E </font></div>
<div class=""><br class="">
</div>
<div class="">We can construct the following dominator tree for the CFG above, DomTree:</div>
<div class=""><font face="Menlo" class=""> A</font></div>
<div class=""><font face="Menlo" class=""> / | \</font></div>
<div class=""><font face="Menlo" class="">B D C</font></div>
<div class=""><font face="Menlo" class=""> |</font></div>
<div class=""><font face="Menlo" class=""> E</font></div>
<div class=""><br class="">
</div>
<div class="">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 class=""><br class="">
</div>
<div class="">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 class="">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 class=""><br class="">
</div>
<div class="">Hope my question is clear enough.</div>
<div class=""><br class="">
</div>
<div class="">Kind regards,</div>
<div class="">Guus Leijsten </div>
</body>
</html>