5 Dec 2006 06:20:38 -0500

Related articles |
---|

[7 earlier articles] |

Re: finding all dominator trees s1l3ntR3p@gmail.com (s1l3ntr3p) (2006-11-29) |

Re: finding all dominator trees DrDiettrich1@aol.com (Hans-Peter Diettrich) (2006-11-29) |

Re: finding all dominator trees cfc@shell01.TheWorld.com (Chris F Clark) (2006-11-30) |

Re: finding all dominator trees amichail@gmail.com (Amir Michail) (2006-12-03) |

Re: finding all dominator trees diablovision@yahoo.com (2006-12-04) |

Re: finding all dominator trees amichail@gmail.com (Amir Michail) (2006-12-05) |

Re: finding all dominator trees cfc@shell01.TheWorld.com (Chris F Clark) (2006-12-05) |

Re: finding all dominator trees martin@gkc.org.uk (Martin Ward) (2006-12-05) |

Re: finding all dominator trees mailbox@dmitry-kazakov.de (Dmitry A. Kazakov) (2006-12-06) |

Re: finding all dominator trees cfc@shell01.TheWorld.com (Chris F Clark) (2006-12-06) |

From: | Chris F Clark <cfc@shell01.TheWorld.com> |

Newsgroups: | comp.compilers |

Date: | 5 Dec 2006 06:20:38 -0500 |

Organization: | The World Public Access UNIX, Brookline, MA |

References: | 06-11-096 06-11-117 06-11-125 06-11-131 06-12-025 |

Keywords: | analysis |

Posted-Date: | 05 Dec 2006 06:20:38 EST |

*> 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)

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.