7 Sep 2004 23:52:53 -0400

Related articles |
---|

Program flow analysis and Invariants. neal.wang@gmail.com (2004-08-23) |

Re: Program flow analysis and Invariants. nick.roberts@acm.org (Nick Roberts) (2004-09-03) |

Re: Program flow analysis and Invariants. skaller@nospam.com.au (John Max Skaller) (2004-09-07) |

Re: Program flow analysis and Invariants. neal.wang@gmail.com (2004-09-13) |

Re: Program flow analysis and Invariants. neal.wang@gmail.com (2004-09-13) |

From: | "John Max Skaller" <skaller@nospam.com.au> |

Newsgroups: | comp.compilers |

Date: | 7 Sep 2004 23:52:53 -0400 |

Organization: | Compilers Central |

References: | 04-08-126 |

Keywords: | analysis |

Posted-Date: | 07 Sep 2004 23:52:53 EDT |

On Mon, 23 Aug 2004 12:11:54 -0400, Neal Wang wrote:

*> I'm studying the program flow analysis and compiler optimization.*

*> What's the purpose of program flow analysis? The answer I can come is*

*> "to synthesize invariants". Is this claim true? Can we say the more*

*> invariants we can find, the more optimization opportunities we can*

*> explore?*

Control or data flow?

There are some obvious optimisations based on control

flow -- for example dead code elimination and tail

recursion optimisation.

Just as an example of data flow: consider

function f() ... return f();

Well that's clearly tail recursive but so is this:

function f() .. val x = f(); return x;

but you need data flow to discover this fact. My compiler

has a lot of heuristic optimisations based on pattern

matching such as

return f x;

generates the body of f, with x substituted, but I also

unravel expressions to 3 address code .. which defeats

detection by simple pattern matching, for example;

g = f;

return g x;

Now 'g' is a variable not a function, so we again need data

flow to discover it is always equal to f, and thus we can

inline f now (and eliminate g).

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.