15 Dec 2001 00:38: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: | "Robert Sherry" <rsherry8@home.com> |

Newsgroups: | comp.compilers |

Date: | 15 Dec 2001 00:38:53 -0500 |

Organization: | Excite@Home - The Leader in Broadband http://home.com/faster |

Keywords: | analysis, books, question |

Posted-Date: | 15 Dec 2001 00:38:52 EST |

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.

Please comment.

Robert Sherry

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.