27 Nov 2006 17:44:21 -0500

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) |

[8 later articles] |

From: | Martin Ward <martin@gkc.org.uk> |

Newsgroups: | comp.compilers |

Date: | 27 Nov 2006 17:44:21 -0500 |

Organization: | Compilers Central |

References: | 06-11-096 |

Keywords: | analysis, bibliography |

Posted-Date: | 27 Nov 2006 17:44:21 EST |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.