4 Dec 2006 08:28:54 -0500

Related articles |
---|

[5 earlier articles] |

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

Re: finding all dominator trees bmoses-nospam@cits1.stanford.edu (Brooks Moses) (2006-11-29) |

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: | diablovision@yahoo.com |

Newsgroups: | comp.compilers |

Date: | 4 Dec 2006 08:28:54 -0500 |

Organization: | Compilers Central |

References: | 06-11-09606-11-125 06-11-131 06-12-025 |

Keywords: | analysis |

Amir Michail wrote:

*> Chris F Clark wrote:*

*> > ...*

*> >*

*> > Yes, there are more efficient algorithms for computing the sets of*

*> > dominators in a graph considering each vertex in the graph as a root.*

*> > Both reachable vertexes and strongly-connected-components (cycles)* are*

*> > part of the algorithm.*

*> >*

*> > First, if there is one unique vertex that can reach all other vertexes*

*> > (verticies if you prefer) in the graph, consider that vertex the root.*

*> > The dominator algorithm given that root will calculate the correct*

*> > dominators (the dominator tree) for every vertex (v1) in the graph*

*> > assuming that each other vertex (v2) is the root. That is, for any*

*> > target vertex v1 and root vertex v2, some vertex in the dominator tree*

*> > of v1 will be the dominator of v1 given the root v2.*

*> >*

*>*

*> 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 B:*

*>*

*> B*

*> |*

*> C*

*>*

*> The dominator tree for C:*

*>*

*> C*

*> |*

*> B*

The problem seems to be the definition of dominance. Dominance in

compiler land is defined with respect to some (already chosen) root

node, because the definition states that a node X dominates Y iff every

path from the root node R to Y goes through node X.

In your example, the dominator tree for C is not correct if we chose A

to be the root node. C cannot dominate B because there exists a path

from A to B that does not go through C (the direct path).

I'm not sure what property you are going after in the general graph

problem, but the standard definitions of dominance (in compiler land)

are going to assume the existence of a unique root node.

Perhaps if you collapse cycles (do a SCC decomposition) of your graph

first, and consider cyclic structures to be a single node, the

resulting DAG can be sorted topologically, and the top node can be

considered the root?

Because, in truth, the dominance relation doesn't make any sense unless

you have either or both of the following conditions:

1. a unique entry node.

2. an acyclic graph.

Hope this helps.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.