Re: iterative data flow question

Max Hailperin <>
29 Apr 2006 13:29:45 -0400

          From comp.compilers

Related articles
iterative data flow question (Jeremy Wright) (2006-04-28)
Re: iterative data flow question (Max Hailperin) (2006-04-29)
| List of all articles for this month |

From: Max Hailperin <>
Newsgroups: comp.compilers
Date: 29 Apr 2006 13:29:45 -0400
Organization: Compilers Central
References: 06-04-167
Keywords: analysis
Posted-Date: 29 Apr 2006 13:29:45 EDT

"Jeremy Wright" <> 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 diagram may make this clearer:

A -> B -> D.

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

  -Max Hailperin
    Professor of Computer Science
    Gustavus Adolphus College

Post a followup to this message

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