7 Mar 1998 22:37:17 -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) |

Re: dominator tree mkgardne@cs.uiuc.edu (1998-03-15) |

From: | David Chase <chase@naturalbridge.com> |

Newsgroups: | comp.compilers |

Date: | 7 Mar 1998 22:37:17 -0500 |

Organization: | Natural Bridge LLC |

References: | 98-03-029 |

Keywords: | optimize |

Aaron Leon Kaplan wrote:

*> 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 would be very interested in the*

*> exchange of ideas.*

To the best of my knowledge, nobody has implemented this algorithm.

If I recall, some years ago, Michael Wolf(e?) (the older one, who did

not work with Monica Lam at Stanford) stood up at a PLDI conference

and asked if anyone in the audience had implemented it, and not one

person had.

In practice, I think most people use the O(n log n) Tarjan and Lengauer

algorithm. I implemented the faster one once O(n inverse-Ackerman(n));

I recall that the journal article describing it contains a typo. I

also recall that a friend of mine laughed at me for going to all the

trouble, since log N grows slowly enough, and the nlogn algorithm is

simpler.

--

David Chase, chase@world.std.com

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.