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" <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.