llvm dev - Apr 2017 - Collectively dominance

Hi,

Is there any way to quickly test if a set of basic block collectively
dominate another basic block?

Thanks
Hongbin
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170425/b9336a6d/attachment.html>

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.
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}


Or do you mean  "all of the the members of the set individually dominate
the block"?

IE
A
|
B
|
C
|
D

The set "A, B, C" dominates D.

The latter is quite easy, because dominance is transitive.
The only way for it to be true is if all of them are on the idom path to
root.
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.

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.


On Tue, Apr 25, 2017 at 5:07 PM, Hongbin Zheng via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hi,
>
> Is there any way to quickly test if a set of basic block collectively
> dominate another basic block?
>
> Thanks
> Hongbin
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170425/41187cb0/attachment.html>

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>