Collectively dominance

Hi,

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

Thanks
Hongbin

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.

Hi Daniel,

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

Hi Daniel,

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

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?

Nearest common ancestor

If you have dfs numbers for the dom tree, you can do this very fast.

Hi Daniel,

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

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.

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

Thanks
Hongbin

Hi Daniel,

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

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.

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

No, for each predecessor of D.

The definition of dominance is that d dominates n if every path from root
to n goes through d.
This means for anything to collectively dominate a node, it either must:
Be be in the idom tree (ie so that the above is definitely true)
or cover every path into the block.

The only way to cover every path is to cover at least a dominator of all of
the predecessors.

This would guarantee that collectively, every path to the predecessor must
go through the set.

Note that this definition is recursive, actually, so while the algorithm i
gave covers most examples.
For any block with multiple predecessors, you'd have to apply it
recursively.

Thanks

Hi Daniel,

Thanks a lot for all these explanation, I will try it out.

Hongbin

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

(because in any reducible flowgraph, v dominates u whenever u,v is a back-arc)

Curious to learn how this is eventually working out?

Some (“well-structured”?) cases could well be solved quickly, e.g. by covering dominators, but this seems a sufficient rather than a necessary condition in general. A set of nodes S could collectively dominate a given node N, where each node in S dominates only itself.

Ayal.

There is a trivial algorithm to do it, it’s making it fast that is hard.

The trivial algorithm is:

Disconnect the incoming edges from the nodes in the set you are testing.

Do a pre-order DFS walk from the root.
If the target node is still reachable, the set does not jointly dominate it.

By definition, if set {a, b, …} dominates y, then all paths that reach y go through {a, b, …}.

If you remove the incoming edges from those nodes, and y is still reachable, there must be another path to y, so the set does not jointly dominate it.

Obviously, you can do this in O(N) per test

I imagine there is some precomputation way to build a spanning forest or something that gives you faster answers.