Re: iterative data flow question
 From: Max Hailperin <max@xxxxxxxxxxxx>
 Date: 29 Apr 2006 13:29:45 0400
"Jeremy Wright" <Jeremy.Wright@xxxxxxxxxxxxxx> writes:
... I have yet to come up with an example
where a forward PO does not correspond to a reverse RPO (for graphs with
single entry and exit).
More generally, if PO() and RPO() return the set of all possible
[reverse] post orders of a graph, and rev() returns the graph with the
control flow edges reversed, is there a graph G such that
PO(G) != RPO(rev(G))
Consider a directed graph on four nodes A, B, C, and D, with A being
the entry and D being the exit, and with edges
A>B
B>C
B>D
C>B.
A diagram may make this clearer:
A > B > D.
^

V
C
Not only are the sets PO(G) and RPO(rev(G)) unequal, they are in fact
completely disjoint. Whether the graph is traversed forward or
reversed, C will be retreated out of before B is. Thus in any
postorder of either the graph or its reversal, C precedes B, whereas
in any reverse postoder of either the graph or its reversal, C follows
B.
Max Hailperin
Professor of Computer Science
Gustavus Adolphus College
http://www.gustavus.edu/+max/
.
 References:
 iterative data flow question
 From: Jeremy Wright
 iterative data flow question
 Prev by Date: Re: Refining pointsto information
 Next by Date: Re: stack overflow at compile time
 Previous by thread: iterative data flow question
 Next by thread: Release of Tom 2.3
 Index(es):
Relevant Pages
