<div dir="ltr">There is a trivial algorithm to do it, it's making it fast that is hard.<div><br>The trivial algorithm is:<br></div>Disconnect the incoming edges from the nodes in the set you are testing.<div><br></div><div>Do a pre-order DFS walk from the root.</div><div>If the target node is still reachable, the set does not jointly dominate it.</div><div><br></div><div>By definition, if set {a, b, ...} dominates y, then all paths that reach y go through {a, b, ...}.</div><div><br></div><div>If you remove the incoming edges from those nodes, and y is still reachable, there must be another path to y, so the set does not jointly dominate it.</div><div><br></div><div>Obviously, you can do this in O(N) per test</div><div><br></div><div>I imagine there is some precomputation way to build a spanning forest or something that gives you faster answers.</div><div><br></div><div><br></div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Sat, May 20, 2017 at 4:43 PM, Zaks, Ayal <span dir="ltr"><<a href="mailto:ayal.zaks@intel.com" target="_blank">ayal.zaks@intel.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">





<div lang="EN-US" link="blue" vlink="purple">
<div class="m_4196315599967883126WordSection1">
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">Curious to learn how this is eventually working out?<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">Some (“well-structured”?) cases could well be solved quickly, e.g. by covering dominators, but this seems a sufficient rather than a necessary condition in general.
 A set of nodes S could collectively dominate a given node N, where each node in S dominates only itself.<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"><u></u> <u></u></span></p>
<p class="MsoNormal"><a name="m_4196315599967883126__MailEndCompose"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">Ayal.<u></u><u></u></span></a></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"><u></u> <u></u></span></p>
<div style="border:none;border-left:solid blue 1.5pt;padding:0cm 0cm 0cm 4.0pt">
<p class="MsoNormal"><a name="m_4196315599967883126______replyseparator"></a><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> llvm-dev [mailto:<a href="mailto:llvm-dev-bounces@lists.llvm.org" target="_blank">llvm-dev-bounces@<wbr>lists.llvm.org</a>]
<b>On Behalf Of </b>Daniel Berlin via llvm-dev<br>
<br>
</span></p><div><div class="h5">
<div>
<p class="MsoNormal">Like I said, i'm nearly positive there is a much faster way, as the sets are mostly shared except in the cyclic case, and in all reducible cyclic cases, removal of back-arcs does not affect dominance<u></u><u></u></p>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">(because in any reducible flowgraph, v dominates u whenever u,v is a back-arc)<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<p class="MsoNormal">On Tue, Apr 25, 2017 at 7:38 PM, Hongbin Zheng <<a href="mailto:etherzhhb@gmail.com" target="_blank">etherzhhb@gmail.com</a>> wrote:<u></u><u></u></p>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<p class="MsoNormal">Hi Daniel,<u></u><u></u></p>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Thanks a lot for all these explanation, I will try it out.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><span style="color:#888888"><u></u> <u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:#888888">Hongbin <u></u><u></u></span></p>
</div>
</div>
<div>
<div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<p class="MsoNormal">On Tue, Apr 25, 2017 at 7:04 PM, Daniel Berlin <<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>> wrote:<u></u><u></u></p>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<p class="MsoNormal">On Tue, Apr 25, 2017 at 6:42 PM, Hongbin Zheng <<a href="mailto:etherzhhb@gmail.com" target="_blank">etherzhhb@gmail.com</a>> wrote:<u></u><u></u></p>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<p class="MsoNormal">On Tue, Apr 25, 2017 at 6:32 PM, Daniel Berlin <<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>> wrote:<u></u><u></u></p>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<p class="MsoNormal"><span class="m_4196315599967883126m-8180491145931305055m-6679299517870862802m1010231429222730262gmail-">On Tue, Apr 25, 2017 at 6:17 PM, Hongbin Zheng <<a href="mailto:etherzhhb@gmail.com" target="_blank">etherzhhb@gmail.com</a>> wrote:<u></u><u></u></span></p>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<p class="MsoNormal">Hi Daniel,<u></u><u></u></p>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">I mean "*<span style="font-size:9.5pt">As a set*, B + C dominate D</span>".<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<p class="MsoNormal">On Tue, Apr 25, 2017 at 5:42 PM, Daniel Berlin <<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>> wrote:<u></u><u></u></p>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<p class="MsoNormal">When you say collectively, you mean "would dominate it if considered a single block together?<u></u><u></u></p>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">IE<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">   A<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">/      \<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">B    C<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">  \  /<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">   D<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">As a set, B + C dominate D.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">The set you are looking for there is (i believe):<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">For each predecessor, walk the idom tree until you hit NCA of all predecessors.<u></u><u></u></p>
</div>
</div>
</blockquote>
</div>
</div>
</div>
</blockquote>
</div>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal">"For each predecessor" do you mean "For each predecessor of the basic blocks in the set"? I.e. for each predecessor of B and C in this example.<u></u><u></u></p>
</div>
</div>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">No, for each predecessor of D.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">The definition of dominance is that d dominates n if every path from root to n goes through d.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">This means for anything to collectively dominate a node, it either must:<br>
Be be in the idom tree (ie so that the above is definitely true)<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">or cover every path into the block.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">The only way to cover every path is to cover at least a dominator of all of the predecessors.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">This would guarantee that collectively, every path to the predecessor must go through the set.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Note that this definition is recursive, actually, so while the algorithm i gave covers most examples.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">For any block with multiple predecessors, you'd have to apply it recursively.<u></u><u></u></p>
</div>
<div>
<div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<div>
<div>
<div>
<p class="MsoNormal">Thanks<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><span style="color:#888888">Hongbin<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<div>
<div>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<div>
<div>
<div>
<p class="MsoNormal">What do you mean by NCA?<u></u><u></u></p>
</div>
</div>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Nearest common ancestor<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">If you have dfs numbers for the dom tree, you can do this very fast.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<div>
<div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<div>
<p class="MsoNormal">While you walk it, place all nodes on each branch in a set.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Any set that collectively dominates D must contain at least one member from each of these set, or be on the idom path between NCA and root.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">IE above, it would be that <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">Set 1 = {B}<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">Set 2 = {C}<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">Set IDOM to root = {A}.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">If you find something in "set IDOM to root", the answer is always "yes", since that block alone dominates it, the collective set must dominate it.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">(unless you use a stricter definition of collective)<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">For the tree<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">  A<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> /   \<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">B   D<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">|     |<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">C   E<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> \   /<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">   F<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Set 1 = {B, C}<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">Set 2 = {D, E}<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt">set IDOM to root = {A}<u></u><u></u></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Thanks a lot<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><span style="color:#888888">Hongbin<u></u><u></u></span></p>
</div>
</div>
</div>
</div>
</blockquote>
</div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
</div>
</blockquote>
</div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
</div>
</blockquote>
</div>
</div>
</div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
</div>
</blockquote>
</div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
</div>
</div>
</blockquote>
</div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
</div></div></div>
</div>
<p>------------------------------<wbr>------------------------------<wbr>---------<br>
Intel Israel (74) Limited</p>

<p>This e-mail and any attachments may contain confidential material for<br>
the sole use of the intended recipient(s). Any review or distribution<br>
by others is strictly prohibited. If you are not the intended<br>
recipient, please contact the sender and delete all copies.</p></div>

</blockquote></div><br></div>