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 points-to 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
|
