Re: finding all dominator trees

Amir Michail wrote:


> But maybe there's a more efficient way (even though the relationship
> between these dominator trees may not be obvious in general).


I'm not sure what you mean with dominator "trees". Isn't it sufficient
to find the immediate dominator for each each node, in order to create
any other dominator structure subsequently? AFAIR all the basic
algorithms are O(n).


A root node is not normally required by graph algorithms, the only
requirement IMO is an ordered list of all nodes. Within that list more
orders can be implemented, e.g. by (reverse) DFS numbering, to simplify
procedures like finding dominators.


The results of properly implemented algorithms are independent from any
order of the nodes. For completeness: A graph can have zero or more
"root" nodes, which are not reachable from any other nodes. There can
exist singletons and isolated subgraphs, too, which must be treated as
separate graphs.


DoDi

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