Related articles 

iterative data flow question Jeremy.Wright@microfocus.com (Jeremy Wright) (20060428) 
Re: iterative data flow question max@gustavus.edu (Max Hailperin) (20060429) 
From:  Max Hailperin <max@gustavus.edu> 
Newsgroups:  comp.compilers 
Date:  29 Apr 2006 13:29:45 0400 
Organization:  Compilers Central 
References:  0604167 
Keywords:  analysis 
PostedDate:  29 Apr 2006 13:29:45 EDT 
"Jeremy Wright" <Jeremy.Wright@microfocus.com> 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/
Return to the
comp.compilers page.
Search the
comp.compilers archives again.