Compilers - Program flow analysis and Invariants.

Author

Program flow analysis and Invariants.

Neal Wang

2004-08-23, 4:02 pm

Hi

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?

Thanks

Neal

Nick Roberts

2004-09-03, 4:03 pm

On 23 Aug 2004 12:11:54 -0400, Neal Wang <neal.wang@gmail.com> 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?

No-one else seems to have answered this one.

I think that program flow analysis is used to provide a basis for
further analyses to be done, including loop-invariant code motion.

Are you able to obtain a good text on the subject, Neal?

--
Nick Roberts

John Max Skaller

2004-09-08, 3:57 am

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

Neal Wang

2004-09-13, 4:00 pm

"Nick Roberts" <nick.roberts@acm.org> wrote
> No-one else seems to have answered this one.
>
> I think that program flow analysis is used to provide a basis for
> further analyses to be done, including loop-invariant code motion.
>
> Are you able to obtain a good text on the subject, Neal?

Nick,

I have one which is "Editor :Steven S. Muchnick, Neil D. Jones,
Program Flow Analysis -- Theory and Applications".

What I'm curious is what the results of program flow analyses *in
general* are. My conclusion is all program flow analyses producing
some sort of invariants.

Invariants are predicates which are true for all program executions.
Those invariants are used to drive semantic-based program
manipulation, such as optimization. loop-invariant code motion is one
example.

Neal

Neal Wang

2004-09-13, 4:00 pm

"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

Sponsored Links