20 Dec 2001 00:39:53 -0500

Related articles |
---|

A question about Dominators rsherry8@home.com (Robert Sherry) (2001-12-15) |

Re:A question about Dominators kvinay@ip.eth.net (kvinay) (2001-12-20) |

Re: A question about Dominators vbdis@aol.com (2001-12-20) |

Re: A question about Dominators Martin.Ward@durham.ac.uk (2001-12-20) |

Re: A question about Dominators sweeks@acm.org (2001-12-20) |

Re: A question about Dominators jeremy.wright@merant.com (Jeremy Wright) (2001-12-20) |

From: | Jeremy Wright <jeremy.wright@merant.com> |

Newsgroups: | comp.compilers |

Date: | 20 Dec 2001 00:39:53 -0500 |

Organization: | Micro Focus |

References: | 01-12-067 |

Keywords: | analysis |

Posted-Date: | 20 Dec 2001 00:39:53 EST |

Robert Sherry wrote:

*>*

*> The following paragraph is from the book Advanced Compiler Design*

*> Implementation by Steven S. Muchnick. I can be found on page 182.*

*>*

*> We give two approaches to computing the set of dominators of each node*

*> in a flowgraph. The basic idea of the first approach is that node a*

*> dominates node b if and only if a=b or a is the unique immediate predecessor*

*> of b or b has more then one immediate predecessor and for all immediate*

*> predecessors c of b, c is not equal to a and a dominates c.*

*>*

*> I believe that the above statement is incorrect. Please consider the*

*> following flowgraph.*

*> Nodes{ a, b, c, d, e }*

*> Edges{ (a,c), (a,d), (c,e), (d,e), (e,b) )*

*> a is the start node*

*>*

*> In this case, a dominates b. However, it violates the if and only if given*

*> above since b has a unique predecessor. The believe the correct statement*

*> would be:*

*>*

*> The basic idea of the first approach is that node a dominates*

*> node b if and only if a=b or a is the unique immediate predecessor of*

*> b or for all immediate predecessors c of b, c is not equal to a and a*

*> dominates c.*

I think the last phrase should read "c equals a or a dominates c"

which of course simplifies to "a dominates c".

Consider

N = { a, b, c}

E = { (a,b), (a,c) }

G = < N, E, a >

a is an immediate predecessor of b, but not a unique predecessor.

Remember though that this is an English description of an algorithm -

not a formal express of the algorithm, or a definition of the

dominator relation.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.