<div dir="ltr">When you say collectively, you mean "would dominate it if considered a single block together?<div><br></div><div>IE</div><div><br></div><div>   A</div><div>/      \</div><div>B    C</div><div>  \  /</div><div>   D</div><div><br></div><div>As a set, B + C dominate D.</div><div><br></div><div>The set you are looking for there is (i believe):</div><div><br></div><div>For each predecessor, walk the idom tree until you hit NCA of all predecessors.</div><div>While you walk it, place all nodes on each branch in a set.</div><div><br></div><div>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.</div><div><br></div><div>IE above, it would be that </div><div>Set 1 = {B}</div><div>Set 2 = {C}</div><div>Set IDOM to root = {A}.</div><div><br></div><div>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.</div><div>(unless you use a stricter definition of collective)</div><div><br></div><div>For the tree</div><div>  A</div><div> /   \</div><div>B   D</div><div>|     |</div><div>C   E</div><div> \   /</div><div>   F</div><div><br></div><div>Set 1 = {B, C}</div><div>Set 2 = {D, E}</div><div>set IDOM to root = {A}<br><br></div><div><br></div><div>Or do you mean  "all of the the members of the set individually dominate the block"?<br><br>IE</div><div>A</div><div>|</div><div>B</div><div>|</div><div>C</div><div>|</div><div>D</div><div><br></div><div>The set "A, B, C" dominates D.</div><div><br></div><div>The latter is quite easy, because dominance is transitive.</div><div>The only way for it to be true is if all of them are on the idom path to root.</div><div>You can actually just do an O(1) test for each one by seeing if it's in the dfs start/completion numbers from dfs numbering the dominator tree.</div><div><br></div><div>If you really want it even faster, you can eliminate things while building the set (IIRC, you only ever have to check the thing with the smallest distance between the dfs numbers in a given DFS subtree), and if the set ever contains two non-intersecting dfs pairs, the answer to "does this set dominate anything" is no.</div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Apr 25, 2017 at 5:07 PM, Hongbin Zheng 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 dir="ltr">Hi,<div><br></div><div>Is there any way to quickly test if a set of basic block collectively dominate another basic block?</div><div><br></div><div>Thanks</div><span class="HOEnZb"><font color="#888888"><div>Hongbin</div></font></span></div>
<br>______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org">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></div>