Re: Algorithm for finding dominators in a control flow graph

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.

Return to the comp.compilers page.
Search the comp.compilers archives again.