|Algorithm for finding dominators in a control flow graph email@example.com (2005-11-26)|
|Re: Algorithm for finding dominators in a control flow graph firstname.lastname@example.org (Jeff Kenton) (2005-11-27)|
|Re: Algorithm for finding dominators in a control flow graph email@example.com (2005-11-29)|
|Re: Algorithm for finding dominators in a control flow graph firstname.lastname@example.org (Martin Ward) (2005-11-29)|
|Re: Algorithm for finding dominators in a control flow graph email@example.com (2005-12-08)|
|From:||firstname.lastname@example.org (Nick Maclaren)|
|Date:||29 Nov 2005 16:06:57 -0500|
|Organization:||University of Cambridge, England|
|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
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.
Return to the
Search the comp.compilers archives again.