Re: Post-dominance relation in CFGs with no exit

On 26 Mar 2001 13:50:36 -0500, Dmitry Shaporenkov
<dsha@post.tepkom.ru> wrote:


> Does anybody know the proper way to
> apply algorithms for computation of post-dominators
> to flowgraphs without exit node? Obviously, it is necessary to
> augment CFG with the fake exit node, but how to determine what
> nodes of CFG connect with it?


The more general problem is the case where there is an exit node and
there are nodes which have no path to the exit node. When there is no
exit node create one. Now perform a depth first search on the reverse
of the flow graph (handling successors as predecessors and vice
versa). Any node that is not reached by the depth first search has no
path to the exit node.


Now perform a normal depth first search on the normal flow graph.
Visiting the nodes in post-order. Connect any node with no path to
the exit to an exit node with a fake edge, unless one of the
descendents of the node (in the normal depth first search) has already
been connected by a fake edge.


This should insure that every node has a path from entry to exit
without introducing too many new fake edges.


Bob Morgan

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