Re: finding all dominator trees

Brooks Moses <bmoses-nospam@cits1.stanford.edu>
29 Nov 2006 00:52:26 -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)
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)
[4 later articles]
| List of all articles for this month |

From: Brooks Moses <bmoses-nospam@cits1.stanford.edu>
Newsgroups: comp.compilers
Date: 29 Nov 2006 00:52:26 -0500
Organization: Stanford University
References: 06-11-09606-11-111 06-11-114
Keywords: analysis

s1l3ntr3p wrote:
> Amir Michail wrote:
>> 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.
>
> This is from Torczon's book: "In a CFG, node i <dominates> node j if
> every path from the entry node to j passes through i". What this tells
> us is that we need a root (entry) node.


Yes, but isn't what Amir is asking for the set of dominator trees
obtained when one chooses each node in turn as the entry node? So any
given node will be the root for one of the trees, but he wants some
way to calculate all of them.


- Brooks


--
The "bmoses-nospam" address is valid; no unmunging needed.


Post a followup to this message

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