[llvm-dev] Collectively dominance

[Hongbin Zheng via llvm-dev]

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>