In
compiler theory
In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs that ...
, dead-code elimination (also known as DCE, dead-code removal, dead-code stripping, or dead-code strip) is a
compiler optimization
In computing, an optimizing compiler is a compiler that tries to minimize or maximize some attributes of an executable computer program. Common requirements are to minimize a program's execution time, memory footprint, storage size, and power con ...
to remove code which does not affect the program results. Removing such code has several 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. It can also enable further optimizations by simplifying program structure. ''
Dead code The term dead code has multiple definitions. Some use the term to refer to code (i.e. instructions in memory) which can never be executed at run-time.
In some areas of computer programming, dead code is a section in the source code of a program whic ...
'' includes code that can never be executed (''
unreachable code''), and code that only affects ''
dead variable
In computer programming, a local variable that is assigned a value but is not read by any subsequent instruction is referred to as a dead store. Dead stores waste processor time and memory, and may be detected through the use of static program anal ...
s'' (written to, but never read again), that is, irrelevant to the program.
Examples
Consider the following example written in
C.
int foo(void)
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, 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
In computer science, control flow (or flow of control) is the order in which individual statements, instructions or function calls of an imperative program are executed or evaluated. The emphasis on explicit control flow distinguishes an ''imper ...
, 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
scope
Scope or scopes may refer to:
People with the surname
* Jamie Scope (born 1986), English footballer
* John T. Scopes (1900–1970), central figure in the Scopes Trial regarding the teaching of evolution
Arts, media, and entertainment
* Cinem ...
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).
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. A yet 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(void)
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
In computer programming and software development, debugging is the process of finding and resolving '' bugs'' (defects or problems that prevent correct operation) within computer programs, software, or systems.
Debugging tactics can involve in ...
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.
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
In computing, dataflow is a broad concept, which has various meanings depending on the application and context. In the context of software architecture, data flow relates to stream processing or reactive programming.
Software architecture
Dataf ...
.
An algorithm based on
static single-assignment form In compiler design, static single assignment form (often abbreviated as SSA form or simply SSA) is a property of an intermediate representation (IR) that requires each variable to be assigned exactly once and defined before it is used. Existing var ...
(SSA) appears in the original journal article on ''SSA'' form by Ron Cytron et al.
Robert Shillingsburg (aka Shillner) improved on the algorithm and developed a companion algorithm for removing useless control-flow operations.
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
In computer science, compile time (or compile-time) describes the time window during which a computer program is compiled.
The term is used as an adjective to describe concepts related to the context of program compilation, as opposed to concept ...
.
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
runtime environment
In computer programming, a runtime system or runtime environment is a sub-system that exists both in the computer where a program is created, as well as in the computers where the program is intended to be run. The name comes from the compile t ...
s (for example different versions of an operating system, or different sets and combinations of drivers or services loaded in a particular target environment), which may require different sets of special cases in the code, but at the same time become conditionally dead code for the other cases.
Also, the software (for example, a driver or resident service) may be configurable to include or exclude certain features depending on user preferences, rendering unused code portions useless in a particular scenario.
While modular software may be developed to dynamically load libraries on demand only, in most cases, it is not possible to load only the relevant routines from a particular library, and even if this would be supported, a routine may still include code sections which can be considered dead code in a given scenario, but could not be ruled out at compile time, already.
The techniques used to dynamically detect demand, identify and resolve dependencies, remove such conditionally dead code, and to recombine the remaining code at
load
Load or LOAD may refer to:
Aeronautics and transportation
*Load factor (aeronautics), the ratio of the lift of an aircraft to its weight
*Passenger load factor, the ratio of revenue passenger miles to available seat miles of a particular transpo ...
or
runtime are called dynamic dead-code elimination
or dynamic dead-instruction elimination.
Most programming languages, compilers and operating systems offer no or little more support than
dynamic loading
Dynamic loading is a mechanism by which a computer program can, at run time, load a library (or other binary) into memory, retrieve the addresses of functions and variables contained in the library, execute those functions or access those varia ...
of libraries and
late linking, therefore software utilizing dynamic dead-code elimination is very rare in conjunction with languages
compiled ahead-of-time or written in
assembly language
In computer programming, assembly language (or assembler language, or symbolic machine code), often referred to simply as Assembly and commonly abbreviated as ASM or asm, is any low-level programming language with a very strong correspondence be ...
.
However, language implementations doing
just-in-time compilation may dynamically optimize for dead-code elimination.
Although with a rather different focus, similar approaches are sometimes also utilized for
dynamic software updating and
hot patching.
See also
*
Redundant code In computer programming, redundant code is source code or compiled code in a computer program that is unnecessary, such as:
* recomputing a value that has previously been calculated and is still available,
* code that is never executed (known as unr ...
*
Simplification (symbolic computation)
*
Partial-redundancy elimination
In compiler theory, partial redundancy elimination (PRE) is a compiler optimization that eliminates expressions that are redundant on some but not necessarily all paths through a program. PRE is a form of common subexpression elimination.
An exp ...
*
Conjunction elimination
*
Dynamic software updating
*
Dynamic coupling (computing)
*
Self-relocation
In computer programming, a self-relocating program is a program that relocates its own address-dependent instructions and data when run, and is therefore capable of being loaded into memory at any address. In many cases, self-relocating code is a ...
*
Software cruft
Cruft is a jargon word for anything that is left over, redundant and getting in the way. It is used particularly for defective, superseded, useless, superfluous, or dysfunctional elements in computer software.
History
Around 1958, the term was ...
*
Tree shaking
In computing, tree shaking is a dead code elimination technique that is applied when optimizing code. Often contrasted with traditional single-library dead code elimination techniques common to minifiers, tree shaking eliminates unused functions fr ...
*
Post-pass optimization
*
Profile-guided optimization
Profile-guided optimization (PGO, sometimes pronounced as ''pogo''), also known as profile-directed feedback (PDF), and feedback-directed optimization (FDO) is a compiler optimization technique in computer programming that uses profiling to impr ...
*
Superoptimizer
Superoptimization is the process where a compiler automatically finds the optimal sequence for a loop-free sequence of instructions. Real-world compilers generally cannot produce genuinely ''optimal'' code, and while most standard compiler optimi ...
*
Function multi-versioning
A fat binary (or multiarchitecture binary) is a computer executable program or library which has been expanded (or "fattened") with code native to multiple instruction sets which can consequently be run on multiple processor types. This results ...
References
Further reading
*
*
*
*
*
*
External links
How to trick C/C++ compilers into generating terrible code?
{{Compiler optimizations
Compiler optimizations