<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="">
<div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">
Hi Kuba,<br class="">
<div class="">
<div class="">
<div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">
<div dir="auto" style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">
<div class=""><br class="">
</div>
<div class="">Thanks for clearing that up.</div>
<div class=""><br class="">
</div>
<div class="">
<blockquote type="cite" class="">
<div class="gmail_extra">
<div class="gmail_quote">
<blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-style: solid; border-left-color: rgb(204, 204, 204); padding-left: 1ex;">
<div class="" style="word-wrap: break-word;">
<div class="">
<div class="h5">
<div class="">
<div class="">
<blockquote type="cite" class="">
<div class="">
<div class="">
<div dir="ltr" class="">
<div class="gmail_extra">
<div class="gmail_quote">
<blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-style: solid; border-left-color: rgb(204, 204, 204); padding-left: 1ex;">
<div class="" style="word-wrap: break-word;">
<div class="">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>
</div>
</div>
</div>
</div>
</blockquote>
</div>
</div>
</div>
</div>
</div>
</blockquote>
</div>
</div>
</blockquote>
</div>
<div class="">After some time, I can contradict the above statement (that I wrote in Oktober) with a yuv2rgb benchmark and the children of a dominator tree or the successors of a basic block are indeed unordered like you said already.</div>
<div class=""><br class="">
</div>
<div class=""><br class="">
</div>
<div class="">Kind regards,</div>
<div class="">Guus Leijsten</div>
<div class=""><br class="">
</div>
<br class="">
<div class="">
<blockquote type="cite" class="">
<div class="">On 28 Oct 2017, at 22:25, Jakub (Kuba) Kuderski <<a href="mailto:kubakuderski@gmail.com" class="">kubakuderski@gmail.com</a>> wrote:</div>
<br class="Apple-interchange-newline">
<div class="">
<div dir="ltr" class="">Hi Guus,<br class="">
<br class="">
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div style="margin:0px;font-size:11px;line-height:normal" class="">Yes I think this will work, however, I still have doubt on one small detail.</div>
<div style="margin:0px;font-size:11px;line-height:normal" class="">In the post order traversal, that I am using, does the range based iterator always visit both B and C, before D? That is, does the <span style="color:rgb(52,149,175);font-family:Menlo" class="">ReversePostOrderTraversal</span> <wbr class="">do
a breadth first search? Not sure, but I think it does do it breadth first.</div>
</blockquote>
<div class=""><br class="">
</div>
<div class="">I haven't used it much, but I think that ReversePostOrderTravelsal is DFS. The simplest way to get the order you want would be to use the DT and sort the siblings by their order in RPO, as Danny mentioned.<br class="">
<br class="">
<a href="https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/Scalar/NewGVN.cpp#L3406" class="">https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/Scalar/NewGVN.cpp#L3406</a><br class="">
<br class="">
Best,<br class="">
Kuba</div>
</div>
<div class="gmail_extra"><br class="">
<div class="gmail_quote">On Sat, Oct 28, 2017 at 9:31 AM, Leijsten, G.H.P. <span dir="ltr" class="">
<<a href="mailto:g.h.p.leijsten@student.tue.nl" target="_blank" class="">g.h.p.leijsten@student.tue.nl</a>></span> wrote:<br class="">
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div style="word-wrap:break-word" class="">Hey Kuba,
<div class=""><br class="">
</div>
<div class="">Thanks of the explanation. I added an include to <span style="color:rgb(180,38,26);font-family:Menlo;font-size:11px;background-color:rgb(255,255,255)" class="">llvm/ADT/PostOrderIterator.<wbr class="">h</span> and get a ranged based iterator with
the following single line of code:</div>
<div class=""><font face="Menlo" class=""><span style="color:rgb(52,149,175);font-size:11px;background-color:rgb(255,255,255)" class=""><br class="">
</span></font></div>
<div class=""><font face="Menlo" class=""><span style="color:rgb(52,149,175);font-size:11px;background-color:rgb(255,255,255)" class="">ReversePostOrderTraversal</span><span style="font-size:11px;background-color:rgb(255,255,255)" class=""><</span><span style="color:rgb(52,149,175);font-size:11px;background-color:rgb(255,255,255)" class="">Mach<wbr class="">ineFunction</span><span style="font-size:11px;background-color:rgb(255,255,255)" class="">*>
RPOT(&MF);</span></font> </div>
<div class=""><br class="">
</div>
<div class="">The post order traversal is now done as follows:</div>
<div class=""><br class="">
</div>
<div class="">
<div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;color:rgb(52,149,175);background-color:rgb(255,255,255)" class="">
<span style="color:#0433ff" class="">for</span><span style="" class=""> (</span>MachineBasicBlock<span style="" class=""> *MBB : RPOT)</span></div>
</div>
<div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)" class="">
<do work></div>
<div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)" class="">
<br class="">
</div>
<div style="margin:0px;font-size:11px;line-height:normal;background-color:rgb(255,255,255)" class="">
<span class="">
<blockquote type="cite" style="font-family:Helvetica;font-size:12px" class="">
<div class="">
<div dir="ltr" class="">Wouldn't a BFS RPO perhaps work in your case?</div>
</div>
</blockquote>
</span>Yes I think this will work, however, I still have doubt on one small detail.</div>
<div style="margin:0px;font-size:11px;line-height:normal;background-color:rgb(255,255,255)" class="">
In the post order traversal, that I am using, does the range based iterator always visit both B and C, before D? That is, does the <span style="color:rgb(52,149,175);font-family:Menlo" class="">ReversePostOrderTraversal</span> <wbr class="">do a breadth first
search? Not sure, but I think it does do it breadth first.</div>
<div style="margin:0px;font-size:11px;line-height:normal;background-color:rgb(255,255,255)" class="">
<br class="">
</div>
<div style="margin:0px;font-size:11px;line-height:normal;background-color:rgb(255,255,255)" class="">
Anyway,</div>
<div style="margin:0px;font-size:11px;line-height:normal;background-color:rgb(255,255,255)" class="">
Thanks for the quick responses.</div>
<div style="margin:0px;font-size:11px;line-height:normal;background-color:rgb(255,255,255)" class="">
<br class="">
</div>
<div style="margin:0px;font-size:11px;line-height:normal;background-color:rgb(255,255,255)" class="">
Kind regards,</div>
<div style="margin:0px;font-size:11px;line-height:normal;background-color:rgb(255,255,255)" class="">
Guus Leijsten</div>
<div class="">
<div class="h5">
<div class=""><br class="">
</div>
<div class="">
<div class="">
<blockquote type="cite" class="">
<div class="">On 27 Oct 2017, at 16:12, Jakub (Kuba) Kuderski <<a href="mailto:kubakuderski@gmail.com" target="_blank" class="">kubakuderski@gmail.com</a>> wrote:</div>
<br class="m_6449481047287534476Apple-interchange-newline">
<div class="">
<div class="">
<div dir="ltr" class="">Hi Guus,<br class="">
<br class="">
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 class="">
<br class="">
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 class="">
<br class="">
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 class="">
<br class="">
Wouldn't a BFS RPO perhaps work in your case?<br class="">
<br class="">
Hope that this makes things a bit more clear,<br class="">
Kuba<br class="">
<br class="">
<div class="gmail_extra"><br class="">
<div class="gmail_quote">On Fri, Oct 27, 2017 at 8:03 AM, Leijsten, G.H.P. via llvm-dev
<span dir="ltr" class=""><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>></span> wrote:<br class="">
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div style="word-wrap:break-word" 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>
</div>
<br class="">
______________________________<wbr class="">_________________<br class="">
LLVM Developers mailing list<br class="">
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a><br class="">
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank" class="">http://lists.llvm.org/cgi-bin/<wbr class="">mailman/listinfo/llvm-dev</a><br class="">
<br class="">
</blockquote>
</div>
<br class="">
<br clear="all" class="">
<div class=""><br class="">
</div>
-- <br class="">
<div class="m_6449481047287534476m_-3580891849680935332m_-6185738293544003221gmail_signature" data-smartmail="gmail_signature">
<div class="">Jakub Kuderski</div>
</div>
</div>
</div>
</div>
</div>
</blockquote>
</div>
<br class="">
</div>
</div>
</div>
</div>
</blockquote>
</div>
<br class="">
<br clear="all" class="">
<div class=""><br class="">
</div>
-- <br class="">
<div class="gmail_signature" data-smartmail="gmail_signature">
<div class="">Jakub Kuderski</div>
</div>
</div>
</div>
</blockquote>
</div>
<br class="">
</div>
</div>
</div>
</div>
<br class="">
</div>
</body>
</html>