Dead-code elimination

In

Examples

Consider the following example written in C.

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

Simple analysis of the uses of values would show that the value of b after the first assignment is not used inside foo. Furthermore, b is declared as a local variable inside foo, so its value cannot be used outside foo. Thus, the variable b is dead and an optimizer can reclaim its storage space and eliminate its initialization.

Furthermore, because the first return statement is executed unconditionally and there is no label after it which a "goto" could reach, no feasible execution path reaches the second assignment to b. Thus, the assignment is unreachable and can be removed. If the procedure had a more complex control flow, such as a label after the return statement and a goto elsewhere in the procedure, then a feasible execution path might exist to the assignment to b.

Also, even though some calculations are performed in the function, their values are not stored in locations accessible outside the

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

int main(void) {
  int a = 5;
  int b = 6;
  int c;
  c = a * (b / 2);
  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.

In practice, much of the dead code that an optimizer finds is created by other transformations in the optimizer. For example, the classic techniques for operator strength reduction insert new computations into the code and render the older, more expensive computations dead.^[2] Subsequent dead-code elimination removes those calculations and completes the effect (without complicating the strength-reduction algorithm).

Historically, dead-code elimination was performed using information derived from data-flow analysis.^[3] An algorithm based on static single-assignment form (SSA) appears in the original journal article on SSA form by Ron Cytron et al.^[4] Robert Shillingsburg (aka Shillner) improved on the algorithm and developed a companion algorithm for removing useless control-flow operations.^[5]

Dynamic dead-code elimination

Dead code is normally considered dead unconditionally. Therefore, it is reasonable attempting to remove dead code through dead-code elimination at compile time.

However, in practice it is also common for code sections to represent dead or unreachable code only under certain conditions, which may not be known at the time of compilation or assembly. Such conditions may be imposed by different

• Redundant code
• Simplification (symbolic computation)
• Partial-redundancy elimination
• Conjunction elimination
• Dynamic software updating
• Dynamic coupling (computing)
• Self-relocation
• Software cruft
• Tree shaking
• Post-pass optimization
• Profile-guided optimization
• Superoptimizer
• Function multi-versioning

References