Re: Re: Dead Code Elimination

preston@dawn.cs.rice.edu (Preston Briggs) writes:


>The definition of 'critical' leaves room for both sharp and sloppy
>analysis. Most compilers are conservative and assume stores to memory are
>critical.
...
>Well, if the 'a' is a local variable and never ref'd again in the
>procedure and no aliased, then it's probably not critical. Relatively
>expensive to check. And how often does it pay off?
...
>The body of the loop really has an increment
>of 'i' and 'i' is used to control the loop. Generally, we say that
>variables used in control flow are critical.


>Once again, this case could be checked for, but the cost is a fair amout
>of relatively special-purpose machinery that's good for nothing else but
>smoking Byte benchmarks (which some compiler writers enjoy -- Hi Bob.)


The cost of these more aggressive analyses depends on the program
representation used by the compiler. In the Typhoon compiler project at
Cornell, the intermediate program representation used for optimization is
the Dependence Flow Graph (DFG), which explicitly represents all program
dependences. As a result, local calculations which do not contribute to
side effects or to return values are easily eliminated, as are empty
loops. I believe the Typhoon FORTRAN compiler would turn an entire
procedure like the one Mike presented into a no-op. Dependence analysis
in C is harder.


Before anyone jumps down my throat, let me be the first to admit that
there are costs to working with the DFG representation, mainly due to its
size. The point I'm making is that once this overhead is paid, further
global analyses become much simpler and less expensive. Very aggressive
forms of analysis tend to be the most natural when working with a
dependence-based intermediate representation. The machinery is expensive,
but it is not special purpose.


Micah Beck
--

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