13 Sep 2004 10:48:56 -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: | neal.wang@gmail.com (Neal Wang) |

Newsgroups: | comp.compilers |

Date: | 13 Sep 2004 10:48:56 -0400 |

Organization: | http://groups.google.com |

References: | 04-08-126 04-09-047 |

Keywords: | analysis |

Posted-Date: | 13 Sep 2004 10:48:56 EDT |

"John Max Skaller" <skaller@nospam.com.au> wrote

*> Control or data flow?*

I mean dataflow analysis.

*> There are some obvious optimisations based on control*

*> flow -- for example dead code elimination and tail*

*> recursion optimisation.*

IMHO, dead code elimination is based on dataflow analysis.

define-use chains are used to drive dead code elimination.

Yes, some optimizations are based on control flow analysis.

One example might be "Instruction scheduling", but we still need to use

data flow analysis to discover data dependency while we use control flow

analysis to discover control dependency.

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

Yes, it's one example of reach definition.

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

I think the purpose of dataflow analysis is to discover invariants.

Let me modify your example and make it more general:

g = f;

... ;no further assignment of g

assert (g == f) <-- this is the invariant.

return g x;

Neal

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.