|iterative data flow question Jeremy.Wright@microfocus.com (Jeremy Wright) (2006-04-28)|
|Re: iterative data flow question firstname.lastname@example.org (Max Hailperin) (2006-04-29)|
|From:||"Jeremy Wright" <Jeremy.Wright@microfocus.com>|
|Date:||28 Apr 2006 23:51:14 -0400|
|Posted-Date:||28 Apr 2006 23:51:14 EDT|
When solving forward flow problem using iterative data-flow analysis the
best order for processing the blocks is reverse post order (RPO) on the
control flow graph (CFG). When solving backwards flow problems the best
order is RPO on the reverse CFG.
In "Iterative Data Flow Analysis, revisited"
the authors note (in section 5.2 if you are interested) that RPO on
reverse CFG is distinct from the PO on the forward CFG.
Now - given that there are usually several different post order
traversals possible for a graph, any given PO of the CFG may be
different to a RPO of the CFG, but 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))
Compiler Team Leader
Return to the
Search the comp.compilers archives again.