iterative data flow question

"Jeremy Wright" <>
28 Apr 2006 23:51:14 -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: "Jeremy Wright" <>
Newsgroups: comp.compilers
Date: 28 Apr 2006 23:51:14 -0400
Organization: Compilers Central
Keywords: analysis, question
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))

Jeremy Wright
Compiler Team Leader
Micro Focus

Post a followup to this message

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