28 Apr 2006 23:51:14 -0400

Related articles |
---|

iterative data flow question Jeremy.Wright@microfocus.com (Jeremy Wright) (2006-04-28) |

Re: iterative data flow question max@gustavus.edu (Max Hailperin) (2006-04-29) |

From: | "Jeremy Wright" <Jeremy.Wright@microfocus.com> |

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"

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.