Re: finding all dominator trees

Martin Ward <martin@gkc.org.uk>
5 Dec 2006 06:20:50 -0500

          From comp.compilers

Related articles
[8 earlier articles]
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: Martin Ward <martin@gkc.org.uk>
Newsgroups: comp.compilers
Date: 5 Dec 2006 06:20:50 -0500
Organization: Compilers Central
References: 06-11-096 06-12-025 06-12-033
Keywords: analysis
Posted-Date: 05 Dec 2006 06:20:49 EST

On Monday 04 Dec 2006 13:28, diablovision@yahoo.com wrote:
> 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.


Several people, including myself, assumed that when Amir
referred to "dominators in a graph", he meant a control
flow graph (with a unique entry node from which the meaning
of dominance can be defined). He actually wants to compute
the set of dominator trees for the set of control flow graphs
which can be constructed from a given graph by taking each node
in turn to be the entry node (and, presumably, ignoring nodes
which are not reachable from that node). Each of these CFGs
has the same nodes and edges, but a different entry node,
and therefore a different dominance relation and dominator tree.


--
Martin


martin@gkc.org.uk http://www.cse.dmu.ac.uk/~mward/ Erdos number: 4
Don't email: d3457f@gkc.org.uk



Post a followup to this message

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