# Re: finding all dominator trees

## "Amir Michail" <amichail@gmail.com>27 Nov 2006 17:44:34 -0500

From comp.compilers

Related articles
finding all dominator trees amichail@gmail.com (Amir Michail) (2006-11-22)
Re: finding all dominator trees diablovision@yahoo.com (2006-11-26)
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)
[7 later articles]
| List of all articles for this month |

 From: "Amir Michail" Newsgroups: comp.compilers Date: 27 Nov 2006 17:44:34 -0500 Organization: Compilers Central References: 06-11-09606-11-106 Keywords: analysis Posted-Date: 27 Nov 2006 17:44:34 EST

diablovision@yahoo.com wrote:
> > Is there an efficient algorithm for finding all dominator trees of a
> > graph? That is, for every node, find its dominator tree. I'm looking
> > for something better than simply running a dominator tree algorithm
> > for each node in the graph.
>
> Unless I am missing some subtlety of your situation, you should just be
> able to run the dominator tree algorithm for the root node of the
> graph. Dominator trees have the property that each subtree for a node
> corresponds to the dominator tree for that node.
>

There is no root. This is an arbitrary graph.

Amir

> See "Efficiently Computing Static Single Assignment Form and the
> Control Dependence Graph" by Cytron et al.

Post a followup to this message