Re: dominator tree

David Chase <>
7 Mar 1998 22:37:17 -0500

          From comp.compilers

Related articles
dominator tree (1998-03-05)
Re: dominator tree (1998-03-07)
Re: dominator tree (David Chase) (1998-03-07)
Re: dominator tree (1998-03-08)
Re: dominator tree (1998-03-12)
Re: dominator tree (Vugranam Sreedhar) (1998-03-12)
Re: dominator tree (Richard F. Man) (1998-03-13)
Re: dominator tree cliffc@jaberwocky.Eng.Sun.COM (1998-03-15)
Re: dominator tree (1998-03-15)
| List of all articles for this month |

From: David Chase <>
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

David Chase,

Post a followup to this message

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