Re: finding all dominator trees

"Amir Michail" <amichail@gmail.com>
3 Dec 2006 21:32:18 -0500

          From comp.compilers

Related articles
[4 earlier articles]
Re: finding all dominator trees s1l3ntR3p@gmail.com (s1l3ntr3p) (2006-11-28)
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)
| List of all articles for this month |

From: "Amir Michail" <amichail@gmail.com>
Newsgroups: comp.compilers
Date: 3 Dec 2006 21:32:18 -0500
Organization: Compilers Central
References: 06-11-09606-11-117 06-11-125 06-11-131
Keywords: analysis, question

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


Amir


Post a followup to this message

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