Re: dominator tree (Michael Wolfe)
7 Mar 1998 22:36:18 -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)
[1 later articles]
| List of all articles for this month |

From: (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

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.