Re: Program flow analysis and Invariants.

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

Return to the comp.compilers page.
Search the comp.compilers archives again.