Re: Dead Code Elimination

mjc@dsbc.icl.co.uk (Mike Clarke) writes:
>There have been numerous items covering dead code elimination, but I have
>yet to see what may amount to a fundamental understanding of what may or
>may not be considered to be acceptable/achievable.
>
>If a function has no side effects, should that function collapse into a
>'no-op'. Where exactly should the line be drawn?


There's a couple of optimizations that are common.


First is removal of unreachable code. Sometimes, as a result of constant
propagation or value numbering, we find that a conditional branch becomes
unconditional and a chunk of code may therefore become unreachable. It
saves some code space and compilation time to clean up the mess.


Second is removal of computations whose results are never referenced. The
best version of this removes computations whose results don't affect the
program (e.g., are not 'critical'). Consider, for example


i = 0;
for (...) {
...
i = i + 1;
...
}


where 'i' is never mentioned anywhere else. The results of both 'i = 0'
and 'i = i + 1' are referenced, but are not critical. Therefore, both
expressions may be eliminated.


This is the limit to what most optimizers bother with.


The definition of 'critical' leaves room for both sharp and sloppy
analysis. Most compilers are conservative and assume stores to memory are
critical. Suppose we see


*p = 10;


Is it critical or not? Hard to say. How about


a[i] = 10;


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?


How about 'empty loops'?


for (i=0; i<100; i++) {
}


Well, it's not really empty. 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.)


Preston Briggs
--

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