Compiler optimization is the process of tuning the output of a compiler to minimize or maximize some attributes of an executable computer program. The most common requirement is to minimize the time taken to execute a program; a less common one is to minimize the amount of memory occupied...
to remove code which does not affect the program results. Removing such code has two benefits: it shrinks program size, an important
consideration in some contexts, and it allows the running program to avoid executing irrelevant operations, which
reduces its running time. Dead code includes code that can never be executed (unreachable code
Unreachable code
Unreachable code is a computer programming term for code in the source code of a program which can never be executed because there exists no control flow path to the code from the rest of the program....
), and code that only affects dead variables, that is, variables that are irrelevant to the program.
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
.
int foo(void)
{
int a = 24;
int b = 25; /* Assignment to dead variable */
int c;
c = a << 2;
return c;
b = 24; /* Unreachable code */
return 0;
}
Because the return statement is executed unconditionally, no feasible execution path reaches the
assignment to b. Thus, the assignment is unreachable and can be removed.
(In a procedure with 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 through the assignment to b.)
Simple analysis of the uses of values would show that the value of b 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.
Also, even though some calculations are performed in the function, their values are not stored in locations accessible outside the scope
Scope (programming)
In computer programming, scope is an enclosing context where values and expressions are associated. Various programming languages have various types of scopes. The type of scope determines what kind of entities it can contain and how it affects them—or semantics...
of this function. Furthermore, given the function returns a static value (96), it may be simplified to the value it returns (this simplification is called Constant folding
Constant folding
Constant folding and constant propagation are related compiler optimizations used by many modern compilers. An advanced form of constant propagation known as sparse conditional constant propagation can more accurately propagate constants and simultaneously remove dead code.- Constant folding...
).
Most advanced compilers have options to activate dead code elimination, sometimes at varying levels. A lower level might only remove instructions that 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
Preprocessor
In computer science, a preprocessor is a program that processes its input data to produce output that is used as input to another program. The output is said to be a preprocessed form of the input data, which is often used by some subsequent programs like compilers...
. Consider the following code.
int main(void) {
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
False
False or falsehood may refer to:*False *Lie or falsehood, a type of deception in the form of an untruthful statement*Falsity or falsehood, in law, deceitfulness by one party that results in damage to another...
, 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
Debugging
Debugging is a methodical process of finding and reducing the number of bugs, or defects, in a computer program or a piece of electronic hardware, thus making it behave as expected. Debugging tends to be harder when various subsystems are tightly coupled, as changes in one may cause bugs to emerge...
to optionally activate blocks of code; using an optimizer with dead code elimination eliminates the need for using a preprocessor
Preprocessor
In computer science, a preprocessor is a program that processes its input data to produce output that is used as input to another program. The output is said to be a preprocessed form of the input data, which is often used by some subsequent programs like compilers...
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.
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.
An algorithm based on static single assignment form
Static single assignment form
In compiler design, static single assignment form is a property of an intermediate representation , which says that each variable is assigned exactly once...
appears in the original journal article on SSA form by Cytron et al.
Shillner improved on the algorithm and developed a companion algorithm for removing useless control-flow
operations.
In Computer programming, if we assign a value to a local variable, but the value is not read by any subsequent instruction, then it is referred to as a Dead Store...
Redundant code is a computer programming term for code, which may be source code or compiled code in a computer program, that has any form of redundancy, such as recomputing a value that has previously been calculated and is still available, code that is never executed , or code which is executed...
Unreachable code is a computer programming term for code in the source code of a program which can never be executed because there exists no control flow path to the code from the rest of the program....
In commutative algebra and algebraic geometry, elimination theory is the classical name for algorithmic approaches to eliminating between polynomials of several variables....
The terms "mathematical elimination" and "mathematically eliminated" mean to be excluded in a decision, based on numerical counts, due to insufficient total numbers, even if all remaining events were 100% in favor...
