<div dir="ltr">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<div><br></div><div>(because in any reducible flowgraph, v dominates u whenever u,v is a back-arc)</div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Apr 25, 2017 at 7:38 PM, Hongbin Zheng <span dir="ltr"><<a href="mailto:etherzhhb@gmail.com" target="_blank">etherzhhb@gmail.com</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 Daniel,<div><br></div><div>Thanks a lot for all these explanation, I will try it out.</div><span class="HOEnZb"><font color="#888888"><div><br></div><div>Hongbin </div></font></span></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Apr 25, 2017 at 7:04 PM, Daniel Berlin <span dir="ltr"><<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.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"><br><div class="gmail_extra"><br><div class="gmail_quote"><span>On Tue, Apr 25, 2017 at 6:42 PM, Hongbin Zheng <span dir="ltr"><<a href="mailto:etherzhhb@gmail.com" target="_blank">etherzhhb@gmail.com</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"><br><div class="gmail_extra"><br><div class="gmail_quote"><span>On Tue, Apr 25, 2017 at 6:32 PM, Daniel Berlin <span dir="ltr"><<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote"><span class="m_-8180491145931305055m_-6679299517870862802m_1010231429222730262gmail-">On Tue, Apr 25, 2017 at 6:17 PM, Hongbin Zheng <span dir="ltr"><<a href="mailto:etherzhhb@gmail.com" target="_blank">etherzhhb@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">Hi Daniel,<div><br></div><div>I mean "*<span style="font-size:12.8px">As a set*, B + C dominate D</span>".</div><div class="gmail_extra"><br><div class="gmail_quote"><span>On Tue, Apr 25, 2017 at 5:42 PM, Daniel Berlin <span dir="ltr"><<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><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></blockquote></span></div></div></div></blockquote></span></div></div></div></blockquote></span><div>"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.</div></div></div></div></blockquote><div><br></div></span><div>No, for each predecessor of D.</div><div><br></div><div>The definition of dominance is that d dominates n if every path from root to n goes through d.<br></div><div>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)</div><div>or cover every path into the block.</div><div><br></div><div>The only way to cover every path is to cover at least a dominator of all of the predecessors.</div><div><br></div><div>This would guarantee that collectively, every path to the predecessor must go through the set.</div><div><br></div><div>Note that this definition is recursive, actually, so while the algorithm i gave covers most examples.</div><div>For any block with multiple predecessors, you'd have to apply it recursively.</div><div><div class="m_-8180491145931305055h5"><div><br></div><div><br></div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div>Thanks</div><span class="m_-8180491145931305055m_-6679299517870862802HOEnZb"><font color="#888888"><div>Hongbin</div></font></span><span><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><span class="m_-8180491145931305055m_-6679299517870862802m_1010231429222730262gmail-"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div>What do you mean by NCA?</div></div></div></div></blockquote><div><br></div></span><div>Nearest common ancestor</div><div><br></div><div>If you have dfs numbers for the dom tree, you can do this very fast.</div><span class="m_-8180491145931305055m_-6679299517870862802m_1010231429222730262gmail-"><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><span><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><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></blockquote><div><br></div></span><div>Thanks a lot</div><span class="m_-8180491145931305055m_-6679299517870862802m_1010231429222730262gmail-m_-4206225771259444608HOEnZb"><font color="#888888"><div>Hongbin</div></font></span></div></div></div>
</blockquote></span></div><br></div></div>
</blockquote></span></div><br></div></div>
</blockquote></div></div></div><br></div></div>
</blockquote></div><br></div>
</div></div></blockquote></div><br></div>