Dead code elimination

Dead Code Elimination is a compiler optimization which removes instructions which can be shown not to affect the operation of the program. Dead code elimination can operate on control flow graphs (CFG) or during the peephole optimization stage.

There are two main types of dead code: code that is never executed, and code whose computation is never used. Different techniques are used to remove each.

Removing Code that is never Executed

Using a CFG, dead code is easily identified as basic blocks which have no influx edges. Though it may seem odd that such blocks would ever appear in a CFG, it is often the result of earlier optimizations such as constant folding. One often finds conditionals or loops which can be determined to always fail at compile time, for instance, because of a compile time debugging setting. Similarly, since librarys often define many more functions than are used, the unused functions also qualify as dead code. For example,

1. const DEBUGGING_ENABLED = false
2. if( DEBUGGING_ENABLED )
3. then
4. print("Debug");
5. end if

A peephole optimizer can identify dead code as any instruction preceded by an unconditional branch (or return) instruction and which is not the destination of any branch (i.e. does not have a label). Take for instance the previous example in RTL,

1. $A\gets false$
2. if( A == true ) then goto label1
3. call print("Debug")
4. label1:

After one copy propagation optimization,

1. if( false == true ) then goto label1
2. call print("Debug")
3. label1:

And after one constant folding optimization,

1. goto label1
2. call print("Debug")
3. label1:

The peephole optimizer then identifies the function call as dead code, since it is preceded by an unconditional branch and is not the destination of any other branch (symbolized by the lack of a label before it).

Removing Computations whose Result is never Used

If the result of a computation (including any possible side effects of that computation) are never used by the program, then that computation cannot affect the operation of the program. A compiler can easily identify and remove such dead computations with the aid of use-def chains or static single assignment. For any temporary which has a definition but no use, remove all instructions that define that temporary.

This sort of inefficient code often occurs in the intermediate representation as an artifact of high level languages, but can also appear as a result of enabling optimizations.

How Dead Code Elimination Improves Performance

In the case that the removed dead code is a computation whose result is never used, the program will execute more quickly because it has one fewer instruction to perform.

Removing code that is never executed also improves performance for a few reasons. Because the program takes up less memory, larger fractions of the program will fit into single cache lines, thus improving memory performance. Additionally, one some computer architectures, shorter branches can be encoded with smaller or more efficient instructions.