# Re: Program flow analysis and Invariants.

## neal.wang@gmail.com (Neal Wang)13 Sep 2004 10:48:56 -0400

From comp.compilers

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)
| List of all articles for this month |

 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