Re: finding all dominator trees

Hans-Peter Diettrich <DrDiettrich1@aol.com>
29 Nov 2006 11:51:18 -0500

          From comp.compilers

Related articles
[2 earlier articles]
Re: finding all dominator trees martin@gkc.org.uk (Martin Ward) (2006-11-27)
Re: finding all dominator trees amichail@gmail.com (Amir Michail) (2006-11-27)
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)
[2 later articles]
| List of all articles for this month |

From: Hans-Peter Diettrich <DrDiettrich1@aol.com>
Newsgroups: comp.compilers
Date: 29 Nov 2006 11:51:18 -0500
Organization: Compilers Central
References: 06-11-09606-11-114 06-11-117
Keywords: analysis

Amir Michail wrote:


> But maybe there's a more efficient way (even though the relationship
> between these dominator trees may not be obvious in general).


I'm not sure what you mean with dominator "trees". Isn't it sufficient
to find the immediate dominator for each each node, in order to create
any other dominator structure subsequently? AFAIR all the basic
algorithms are O(n).


A root node is not normally required by graph algorithms, the only
requirement IMO is an ordered list of all nodes. Within that list more
orders can be implemented, e.g. by (reverse) DFS numbering, to simplify
procedures like finding dominators.


The results of properly implemented algorithms are independent from any
order of the nodes. For completeness: A graph can have zero or more
"root" nodes, which are not reachable from any other nodes. There can
exist singletons and isolated subgraphs, too, which must be treated as
separate graphs.


DoDi


Post a followup to this message

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