Explore Black History

In compiler theory, dead-code elimination (DCE, dead-code removal, dead-code stripping, or dead-code strip) is a compiler optimization to remove dead code (code that does not affect the program results). Removing such code has several benefits: it shrinks program size (an important consideration in some contexts); reduces resource usage, such as the number of bytes to be transferred^[1]; and 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 includes code that can never be executed (unreachable code) and code that only affects dead variables (written to, but never read again), that is, irrelevant to the program.

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;
}

Trivial analysis of the control flow would mark lines 7 and 8 for removal as they are never reached after return c;. 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.

Furthermore, simple analysis of the uses of values would then show that the value of b is only written to and never read from. 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 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), resulting in:

int foo(void) {
    return 96;
}

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.

// set DEBUG_MODE to false
constexpr bool DEBUG_MODE = false;

int main(void) {
    int a = 5;
    int b = 6;
    int c;
    c = a * (b / 2);
    if (DEBUG_MODE) {
        printf("%d\n", c);
    }
    return c;
}

Because the constant DEBUG_MODE will always evaluate to false (due to being defined as so), 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 (e.g. #define DEBUG_MODE 0 then #if DEBUG_MODE...).

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]

In the above example we eliminate the dead code at compile time. Doing so only allows removal of code that is unconditionally dead and can be shown by the optimizer to be the case. The presence of compilation unit (CU) boundaries hinder the determination of deadness by the optimizer.

Consider, for example, a Unix static library (*.a) which contains a number of object files (*.o). At link-time, the linker ld examines the symbols referenced by other pieces of code and chooses to only include the necessary object files – ones that contain the referenced symbols, both by the original code and by the object files pulled in to satisfy the needs of the original object file. This consists a very coarse-grained version of dead-code elimination.

Object files consist of relatively independent sections that may reference each other. When an object file is broken down into more sections, e.g. with each function and/or variable in their own section (-ffunction-sections -fdata-sections), and if the linker is told to analyze the inter-dependencies in a section-level granularity (--gc-sections), a more complete form of link-time DCE can be achieved. (-fdata-sections may counter-productively inflate the size of the binary by creating more relocation entries.)^[6]

The gold standard for link-time DCE is to turn link time into another compile time, i.e. link-time optimization. In this setup, object files contain intermediate representations used by the compiler instead of (or in addition to) machine code. In this way, the optimizer is no longer hindered by CU boundaries since it has access to the entire program, enabling it to prove many more properties of the code that can be used for optimization. This comes with the downside of extended compile times for processing such a large representation of the program.

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 environments (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.^[7][8] 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.^[7][8] 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 or runtime are called dynamic dead-code elimination^[9][10][11] or dynamic dead-instruction elimination.^[12]

Most programming languages, compilers and operating systems offer no or little more support than dynamic loading 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.^[13][14][15] However, language implementations doing just-in-time compilation may dynamically optimize for dead-code elimination.^[11][16][17]

Although with a rather different focus, similar approaches are sometimes also utilized for dynamic software updating and hot patching.

• Redundant code
• Simplification (symbolic computation)
• Partial-redundancy elimination
• Conjunction elimination
• Dynamic software updating
• Dynamic coupling (computing)
• Self-relocation
• Software cruft
• Tree shaking – Bundle-time DCE for dynamic languages, analogous to link-time DCE
• Post-pass optimization
• Profile-guided optimization
• Superoptimizer
• Function multi-versioning

• Bodík, Rastislav; Gupta, Rajiv (June 1997). "Partial dead code elimination using slicing transformations". Proceedings of the ACM SIGPLAN 1997 Conference on Programming Language Design and Implementation (PLDI '97): 682–694.
• Aho, Alfred Vaino; Sethi, Ravi; Ullman, Jeffrey David (1986). Compilers - Principles, Techniques and Tools. Addison Wesley Publishing Company. ISBN 0-201-10194-7.
• Muchnick, Steven Stanley (1997). Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers. ISBN 1-55860-320-4.
• Grune, Dick; Bal, Henri Elle; Jacobs, Ceriel J. H.; Langendoen, Koen G. (2000). Modern Compiler Design. John Wiley & Sons, Inc. ISBN 0-471-97697-0.
• Kennedy, Ken; Allen, Randy (2002). "Chapter 4.4. Data Flow Analysis - Chapter 4.4.2. Dead Code Elimination". Optimizing Compilers for Modern Architectures: A Dependence-Based Approach (2011 digital print of 1st ed.). Academic Press / Morgan Kaufmann Publishers / Elsevier. pp. 137, 145–147, 167. ISBN 978-1-55860-286-1. LCCN 2001092381.
• Muth, Robert; Debray, Saumya K.; Watterson, Scott; De Bosschere, Koen (January 2001) [1999-11-02]. "alto: a link-time optimizer for the Compaq Alpha". Software: Practice and Experience. 31 (1): 67–101. doi:10.1002/1097-024X(200101)31:1<67::AID-SPE357>3.0.CO;2-A. S2CID 442062. [5]

• How to trick C/C++ compilers into generating terrible code?^{[link removed]}