Re: dominator tree

David Chase <chase@naturalbridge.com>
7 Mar 1998 22:37:17 -0500

          From comp.compilers
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)
| List of all articles for this month |
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.