Re: Program flow analysis and Invariants.

neal.wang@gmail.com (Neal Wang)
13 Sep 2004 10:48:56 -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: neal.wang@gmail.com (Neal Wang)
Newsgroups: comp.compilers
Date: 13 Sep 2004 10:48:56 -0400
Organization: http://groups.google.com
References: 04-08-126 04-09-047
Keywords: analysis
Posted-Date: 13 Sep 2004 10:48:56 EDT

"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


Post a followup to this message

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