Re: finding all dominator trees

> Chris F Clark wrote:
>> An incorrect algorithm...


"Amir Michail" <amichail@gmail.com> writes:
> I don't understand this solution. How would it work in this example?
>
> A -> B <-> C
>
> The dominator tree for A:
>
> A
> |
> B
> |
> C
>
...
> The dominator tree for C:
>
> C
> |
> B


The issue is for cases where the desired root is a member of a cycle.


You can construct the dominator tree for C from the one for A. One
simply slits the tree at C, in this case pulls C from the bottom.
Next, one removes from the tree all vertexes unreachable from C
(that's the node A in this case) and adds C to the top along with any
descendants of C in the original tree. I was thinking this
modification would always work. Thus, is you had the dominator tree
for A, you could calculate the dominator tree for every node reachable
from A.


However, there are cases where this won't work.


First, there is the problem with cycles. If you pick a root that is a
member of a cycle (and that node doesn't dominate all nodes in the
cycle given the root originally used), it will have different
dominator for some elements of the cycle. Your A->B->C->B graph shows
the basics of that case, a graph like A->B->C->D->E, D->B gives an
even better example. Essentially loop back edges, resulting in an
extra path of domination for roots that are within the cycle. I think
one could supplement the normal dominator graph with a ring to deal
with the elements in the cycle, or in the example A-B-C-D-E as the
normal dominator tree, with C-D-B-C as the dominators within the
cycle. You use the cycle for the case where the desired root is
within a cycle to help you disconnet the original dominator tree and
construct a new dominator tree.


Next there are cases involve fork/join trees (DAGs), such as:
A->B->D and A->C->D


In this case, A immediately dominates D. However, if you pick either
B or C as a root, they also dominate D when you have excluded the
other path (i.e. B dominates D from any root that can't reach C and
vice-versa). Note, that if you the fork a the DAG (A in this case) is
reachable from the root you choose, then that root dominates the join
node of the DAG (D in this case). However, any node along the path
from the fork of a DAG to the join of the DAG will have some
intermediate dominator, B and C are examples of this. You could model
this by making multiple dominator trees, one the includes the fork of
the jag, and one for each path through the jag. In the example, given
this would be A-D for the fork, and B-D and C-D, for the two paths.


Note, that both of these problems are local to a specific type of
sub-graph. That is if you root node and target node are not part of
either a DAG or a cycle, then the information from any dominator tree
where the root node reached both vertexes will still contain the right
dominators. It seems that dealing with these two issues would allow
one to modify the dominator algorithm to construct the extra trees
efficiently, especially if one allows sharing. Perhaps if you work
through the two problem cases, you can fill such ans algorithm out.


Of course, don't forget that the two issues can be mixed, as in:
A->B->C->D->F->G->H->J, A->E->F, G->C, J->E, G->I->J which is 2 DAGs
(A->B->C->D->F, A->E->F and G->H-J, G->I->J) with 2 cycles
(C->D->F->G->C and E->F->G->H/I->J->E) interlinked.


Note, that it may help to replace these sub-problems when you
encounter them with nodes that summarize the subproblem. So, if you
find a DAG in the graph, you do the computation on the DAG, and
replace the DAG with a single node that summarizes the DAG, similarly
for cycles. However, such solutions often work best on reducible
graphs and the hardest cases are the irreducible graphs. But even if
you simply dealth with irreducible sub-graphs as chunks and summarized
on them, it still might be effective.


My apologies for providing a wrong first answer. I had thought about
the cycle case (and the DAG case also), but I made a mistake in
thinking that constructing the relevant dominator tree would be
trivial given the original dominator tree. After reading your
question and giving the problem more thought, I realized that I was
wrong about that. I hope this revision is sufficient to patch the
problems in the original algorithm. I hope I haven't made the problem
worse.


Sorry,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)

Return to the comp.compilers page.
Search the comp.compilers archives again.