12 Mar 1998 23:23:02 -0500

Related articles |
---|

dominator tree lkaplan@mips.complang.tuwien.ac.at (1998-03-05) |

Re: dominator tree. The true stephen@diku.dk (Stephen Alstrup) (1998-03-12) |

From: | Stephen Alstrup <stephen@diku.dk> |

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

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.

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.