Re: finding all dominator trees

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.

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