Re: finding all dominator trees

diablovision@yahoo.com
26 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

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