Re: Incremental computation of dominators

Jeff Kenton <jeffrey.kenton@comcast.net>
24 Aug 2005 18:18:47 -0400

          From comp.compilers

Related articles
Incremental computation of dominators luque@info.ucl.ac.be (Luis Quesada) (2005-08-13)
Re: Incremental computation of dominators luque@info.ucl.ac.be (Luis Quesada) (2005-08-16)
Re: Incremental computation of dominators jeffrey.kenton@comcast.net (Jeff Kenton) (2005-08-24)
Re: Incremental computation of dominators luque@info.ucl.ac.be (Luis Quesada) (2005-08-31)
| List of all articles for this month |

From: Jeff Kenton <jeffrey.kenton@comcast.net>
Newsgroups: comp.compilers
Date: 24 Aug 2005 18:18:47 -0400
Organization: Compilers Central
References: 05-08-049 05-08-058
Keywords: analysis, bibliography
Posted-Date: 24 Aug 2005 18:18:47 EDT

Luis Quesada wrote:


> I found this article that answers this question:
>
> @Article{lengauer79,
> author = {T. Lengauer and R. Tarjan},
> title = {A Fast Algorithm for Finding Dominators in a Flowgraph},
> journal = {ACM Transactions on Programming Languages and Systems},
> year = {1979},
> }
>


There is a much simpler algorithm developed by Keith Cooper, Tim Harvey and
Ken Kennedy -- A Simple, Fast Dominance Algorithm:


http://www.cs.rice.edu/~keith/EMBED/dom.pdf


It is at least as fast and much easier to understand. I also recommend
"Engineering A Compiler" by Keith Cooper and Linda Torczon.


jeff



Post a followup to this message

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