Re: Program flow analysis and Invariants.

"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

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