Re: dominator tree. The true

Stephen Alstrup <>
12 Mar 1998 23:23:02 -0500

          From comp.compilers

Related articles
dominator tree (1998-03-05)
Re: dominator tree. The true (Stephen Alstrup) (1998-03-12)
| List of all articles for this month |

From: Stephen Alstrup <>
Newsgroups: comp.compilers
Date: 12 Mar 1998 23:23:02 -0500
Organization: Department of Computer Science, U of Copenhagen
References: 98-03-029
Keywords: analysis

The true story.

Harel's linear time algorithm was NOT correct.

Together with two other, I have shown this.

Furtheremore we developt a new linear time algorithm for finding
dominators. Submitted to journal. A technical version can be found at
paper number 97/28.

This paper is together with Harel, since we combined our work.

Two results can be found in the paper: A linear time algorithm for
general graphs. This one should only be implemented following the
advice in the conclusion of the paper. A simple linear time algorithm
for reducible graphs. This algorithm could be implemented directly.

The latest news is a paper at STOC'98 (due to people from AT&T),
presenting a linear time algorithm for the pointer machine. This
paper extend the approach from the technical report mentioned above.
The authors from that paper have implemented a non-pointer machine
version of the algorithm from that paper with very good results.
However, from practical point of view for general graphs USE the old
inverse ackermann algorithm.

Finaly one could questning the value of finding dominator trees. Is
this information what one is really interesting to know? I don't
believe that is the case. I believe the dominator informations is the
information which one have believe to be the best information you can
get in linear time. However, recently Thorup have shown that, the
control flow graph for structured programs (e.g. pascal with few
gotoes) have bounded tree width, implying that we can compute all kind
of informations in linear time. If you should be interested read the

"Generalized dominators for structured programs", sas'96, alstrup et.
al. Can also be found at www:


Post a followup to this message

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