# Re: finding all dominator trees

## diablovision@yahoo.com26 Nov 2006 21:54:02 -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)
[9 later articles]
| List of all articles for this month |

 From: diablovision@yahoo.com Newsgroups: comp.compilers Date: 26 Nov 2006 21:54:02 -0500 Organization: Compilers Central References: 06-11-096 Keywords: analysis Posted-Date: 26 Nov 2006 21:54:02 EST

> 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.

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

Post a followup to this message