# Re: Algorithm for finding dominators in a control flow graph

## nmm1@cus.cam.ac.uk (Nick Maclaren)29 Nov 2005 16:06:57 -0500

From comp.compilers

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)
| List of all articles for this month |

 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 Posted-Date: 29 Nov 2005 16:06:57 EST

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