29 Nov 2005 16:06:57 -0500

Related articles |
---|

Algorithm for finding dominators in a control flow graph marouane.tlili@gmail.com (2005-11-26) |

Re: Algorithm for finding dominators in a control flow graph jeffrey.kenton@comcast.net (Jeff Kenton) (2005-11-27) |

Re: Algorithm for finding dominators in a control flow graph nmm1@cus.cam.ac.uk (2005-11-29) |

Re: Algorithm for finding dominators in a control flow graph martin@gkc.org.uk (Martin Ward) (2005-11-29) |

Re: Algorithm for finding dominators in a control flow graph neal.wang@gmail.com (2005-12-08) |

From: | nmm1@cus.cam.ac.uk (Nick Maclaren) |

Newsgroups: | comp.compilers |

Date: | 29 Nov 2005 16:06:57 -0500 |

Organization: | University of Cambridge, England |

References: | 05-11-117 05-11-124 |

Keywords: | analysis |

On an only vaguely related matter, what do you need such an algorithm

for? Please note that I am am not, repeat NOT, saying that there are

no uses, but am surveying.

The algorithms I usually want in 'compilation uses' are more along

the following lines:

Can A pass control to B? [ Standard graph completion ]

Given a set of nodes with a characteristic, what is the closest

node that dominates all of them? [ NOT the dominance algorithm, as

I understand it. ]

Given two sets of nodes, is there any node that can be reached

from both?

Obviously, there are ways to may these and other questions into

each other, but the main use of what I understand to be the simple

dominance algorithm strikes me as being something that would be

better avoided by cleaner language design. However, I could well

have missed an important use.

Note that I understand the simple dominance algorithm to be, given

a node in a rooted DAG, find the 'closest' node that must be passed

through when traversing from the root to the selected node.

Regards,

Nick Maclaren.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.