7 Mar 1998 22:36:18 -0500

Related articles |
---|

dominator tree lkaplan@mips.complang.tuwien.ac.at (1998-03-05) |

Re: dominator tree mwolfe@pgroup.com (1998-03-07) |

Re: dominator tree chase@naturalbridge.com (David Chase) (1998-03-07) |

Re: dominator tree jason@reflections.com.au (1998-03-08) |

Re: dominator tree awaters@acm.org (1998-03-12) |

Re: dominator tree sreedhar@cup.hp.com (Vugranam Sreedhar) (1998-03-12) |

Re: dominator tree mun@cup.hp.com (Richard F. Man) (1998-03-13) |

Re: dominator tree cliffc@jaberwocky.Eng.Sun.COM (1998-03-15) |

[1 later articles] |

From: | mwolfe@pgroup.com (Michael Wolfe) |

Newsgroups: | comp.compilers |

Date: | 7 Mar 1998 22:36:18 -0500 |

Organization: | The Portland Group, Inc. Wilsonville, Oregon U.S.A. |

References: | 98-03-029 |

Keywords: | theory, analysis, question |

Aaron Leon Kaplan writes:

*> Has anyone implemented the dominator tree algorithm by Dov Harel*

*> (idescribed in the paper "A linear time algorithm for finding dominators*

*> in a flow graph and related problems")?*

I'd like to see this myself; I've never found anyone who claims to

have even really understood the whole algorithm. At one PLDI meeting,

there was one fellow from Australia who claimed he had the algorithm

'almost' implemented, but after the meeting I didn't get the promised

copy of the program. I've exchanged email with Dov Harel, but it's

been so long that he's not up to speed on all the details and not all

that interested either. While it is mostly of theoretical interest,

there are lots of papers claiming 'linear time complexity' based on

the linear time DOM algorithm, I think as a community we should make

the effort to verify the algorithm. Interestingly, none of the

authors making these claims shows any interest in doing such an

implementation.

Note to flamers: we all know about Lengauer&Tarjan's algorithm, which

is the algorithm of choice, even if Harel's algorithm truly is linear,

but the true academic in me gags when I see linear time complexity

claims based on an unproven algorithm.

Michael Wolfe, closet academic

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.