Re: finding all dominator trees

On Thursday 23 Nov 2006 02:18, you 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.


Once you have the domiator tree for the root, you have the dominator
tree for every node (take the subtree rooted at that node).


Pingali and Bilardi developed optimal algorithms for dominators, control
dependence and Static Single Assignment construction:


%A Keshav Pingali
%A Gianfranco Bilardi
%T Optimal Control Dependence Computation and the Roman Chariots Problem
%J |TOPLAS|
%S 19
%N 3
%P 462-491
%D |MAY|, 1997
%U http://www.cs.cornell.edu/Info/Projects/Bernoulli/papers/toplas97.ps


%A Gianfranco Bilardi
%A Keshav Pingali
%T The Static Single Assignment Form and its Computation
%R Cornell University Technical Report
%U http://www.cs.cornell.edu/Info/Projects/Bernoulli/papers/ssa.ps
%D |JUL|, 1999
%P 1-37
%K SSA


I have implemented these algorithms the perl modules Blocks.pm
and Control_Dep.pm in the FermaT Program Transformation System:


http://www.cse.dmu.ac.uk/~mward/fermat.html


--
Martin


martin@gkc.org.uk http://www.cse.dmu.ac.uk/~mward/
Don't send email to: d3457f@gkc.org.uk

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