[llvm-dev] Collectively dominance (original) (raw)

Hongbin Zheng via llvm-dev llvm-dev at lists.llvm.org
Tue Apr 25 18:17:44 PDT 2017

Hi Daniel,

I mean "As a set, B + C dominate D".

On Tue, Apr 25, 2017 at 5:42 PM, Daniel Berlin <dberlin at dberlin.org> wrote:

When you say collectively, you mean "would dominate it if considered a single block together?

IE A _/ _ B C \ / D As a set, B + C dominate D. The set you are looking for there is (i believe): For each predecessor, walk the idom tree until you hit NCA of all predecessors. What do you mean by NCA?

While you walk it, place all nodes on each branch in a set.

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. IE above, it would be that Set 1 = {B} Set 2 = {C} Set IDOM to root = {A}. 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. (unless you use a stricter definition of collective) For the tree A _/ _ B D | | C E \ / F Set 1 = {B, C} Set 2 = {D, E} set IDOM to root = {A} Thanks a lot Hongbin -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170425/480b598c/attachment.html>

More information about the llvm-dev mailing list