Dead code elimination

From Wikipedia, the free encyclopedia

This article does not cite any references or sources. (January 2007) Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.

In compiler theory, dead code elimination is a compiler optimization used to reduce program size by removing code which does not affect the program. Dead code includes code that can never be executed (unreachable code), and code that only affects dead variables, that is, variables that are irrelevant to the program.

Consider the following example written in C.

int foo()
{
  int a = 24;
  int b = 25; /* Assignment to dead variable */
  int c;
  c = a << 2;
  return c;
  b = 24; /* Unreachable code */
}

The variable b is assigned a value after a return statement, which makes it impossible to get to. That is, since code execution is linear, and there is no conditional expression wrapping the return statement, any code after the return statement cannot possibly be executed. (This would not be the case if there were a label after the return statement, which opens the possibility of there being a jump that places execution after the return statement.)

Furthermore, if we eliminate that assignment, then we can see that the variable b is never used at all, except for its declaration and initial assignment. Depending on the aggressiveness of the optimizer, the variable b might be eliminated entirely from the generated code.

Also, even though some calculations are performed in the function, their values are not stored in locations accessible outside the scope of this function. Furthermore, given the function returns a static value (96), it may be simplified to the value it returns.

Most advanced compilers have options to activate dead code elimination, sometimes at varying levels. A lower level might only remove instructions which cannot be executed. A higher level might also not reserve space for unused variables. Yet a higher level might determine instructions or functions that serve no purpose and eliminate them.

A common use of dead code elimination is as an alternative to optional code inclusion via a preprocessor. Consider the following code.

int main() {
  int a = 5;
  int b = 6;
  int c;
  c = a * (b >> 1);
  if (0) {   /* DEBUG */
    printf("%d\n", c);
  }
  return c;
}

Because the expression 0 will always evaluate to false, the code inside the if statement can never be executed, and dead code elimination would remove it entirely from the optimized program. This technique is common in debugging to optionally activate blocks of code; using an optimizer with dead code elimination eliminates the need for using a preprocessor to perform the same task.

[edit] References

Partial dead code elimination using slicing transformations Found in: Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation (PLDI '97) By Rastislav Bodík , Rajiv Gupta Issue Date:June 1997 pp. 682-694