Re: dominator tree. The true

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
www:


http://www.diku.dk/research/techreports/blaa97.html
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
paper




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


http://www.diku.dk/users/stephen/newpapers.html


Regards,
stephen.
--

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