Re: iterative data flow question



"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/
.