20 Dec 2001 00:38:48 -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: | sweeks@acm.org (Stephen Weeks) |

Newsgroups: | comp.compilers |

Date: | 20 Dec 2001 00:38:48 -0500 |

Organization: | http://groups.google.com/ |

References: | 01-12-067 |

Keywords: | analysis |

Posted-Date: | 20 Dec 2001 00:38:48 EST |

Muchnick's condition:

*> 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.*

Sherry's condition:

*> 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.*

Here is a counterexample.

Nodes{ r, a, b, c }

Edges{ (r,a), (a,b), (a,c), (c,b) }

r is the start node

In this graph, a dominates b, but a != b, a is not the unique

immediate predecessor of b, and a is an immediate predecessor of b.

Hence Muchnick's condition is violated. Sherry's condition is

violated for the same reason -- a is an immediate predecessor of b,

but not the unique one.

A property that is easy to verify and similar to both of the above

conditions is the following:

a dom b iff (a = b or for all immediate predecessors c of b, a dom c)

This corresponds well with the pseudocode on Muchnick page 182. BTW,

it also is the basis for the pseudocode on page 671 of the Dragon

book, which gives the same algorithm.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.