# Re: Program flow analysis and Invariants.

## "John Max Skaller" <skaller@nospam.com.au>7 Sep 2004 23:52:53 -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: "John Max Skaller" 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