iterative data flow question

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"
http://www.cs.rice.edu/~harv/my_papers/worklist.pdf


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))


Jeremy Wright
Compiler Team Leader
Micro Focus

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