Incompiler theory,dead-code elimination (DCE,dead-code removal,dead-code stripping, ordead-code strip) is acompiler optimization to removedead code (code that does not affect the program results). Removing such code has several benefits: it shrinksprogram 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 irrelevantoperations, which reduces itsrunning 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 affectsdead variables (written to, but never read again), that is, irrelevant to the program.
Consider the following example written inC.
intfoo(void){inta=24;intb=25;// Assignment to dead variableintc;c=a*4;returnc;b=24;// Unreachable codereturn0;}
Simple analysis of the uses of values would show that the value ofb after the first assignment is not used insidefoo. Furthermore,b is declared as a local variable insidefoo, so its value cannot be used outsidefoo. Thus, the variableb isdead 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 tob. Thus, the assignment isunreachable and can be removed.If the procedure had a more complexcontrol flow, such as a label after the return statement and agoto elsewhere in the procedure, then a feasible execution path might exist to the assignment tob.
Also, even though some calculations are performed in the function, their values are not stored in locations accessible outside thescope of this function. Furthermore, given the function returns a static value (96), it may be simplified to the value it returns (this simplification is calledconstant 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 apreprocessor. Consider the following code.
// set DEBUG_MODE to falseconstexprboolDEBUG_MODE=false;intmain(void){inta=5;intb=6;intc;c=a*(b/2);if(DEBUG_MODE){printf("%d\n",c);}returnc;}
Because the constantDEBUG_MODE will always evaluate tofalse (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 indebugging to optionally activate blocks of code; using an optimizer with dead-code elimination eliminates the need for using apreprocessor 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 operatorstrength 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 fromdata-flow analysis.[3] An algorithm based onstatic single-assignment form (SSA) appears in the original journal article onSSA 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]
Dead code is normally considered deadunconditionally. Therefore, it is reasonable attempting to remove dead code through dead-code elimination atcompile time.
However, in practice it is also common for code sections to represent dead or unreachable code onlyunder certain conditions, which may not be known at the time of compilation or assembly. Such conditions may be imposed by differentruntime 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.[6][7] 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.[6][7] 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 atload orruntime are calleddynamic dead-code elimination[8][9][10] ordynamic dead-instruction elimination.[11]
Most programming languages, compilers and operating systems offer no or little more support thandynamic loading of libraries andlate linking, therefore software utilizing dynamic dead-code elimination is very rare in conjunction with languagescompiled ahead-of-time or written inassembly language.[12][13][14] However, language implementations doingjust-in-time compilation may dynamically optimize for dead-code elimination.[10][15][16]
Although with a rather different focus, similar approaches are sometimes also utilized fordynamic software updating andhot patching.
[…] any of the […] options can be "permanently" excluded at installation time (will also save the memory for the corresponding code excerpts due to ourDynamic Dead Code Elimination), or it can be disabled or enabled at any later time via API functions in case someone wants to keep a user from being able to reboot the machine. […] we are considering to add more synchronous cache flush calls […] Due to our Dynamic Dead Code Elimination method this would not cause any kind of bloating when not needed in a particular target configuration as a particular cache flush call would be included in FreeKEYB's runtime image only if the corresponding disk cache is loaded as well or FreeKEYB was told by command line switches to load the corresponding support.
[…] FreeKEYB builds the driver's runtime image at initialization time depending on the type of machine it is being loaded on, the type of keyboard, layout, country and code page used, the type of mouse and video adapter(s) installed, the other drivers loaded on that system, the operating system and the load and relocation method(s) used, the individual features included, and the configuration options specified in the command line. Due to the large number of command line switches and options supported […] (around fifty switches […] with multiple possible settings) there is a high number of feature combinations with uncountable dependencies […] resulting in […] endless number of […] different target images. FreeKEYB's Dynamic Dead Code Elimination technique manages to resolve […] these […] dependencies and […] remove dead code and data […] is not restricted to […] include or exclude a somewhat limited number of modules or whole sub-routines and fix up some dispatch tables as in classical TSR programming, but […] works […] at […] byte level […] able to remove […] individual instructions in the middle of larger routines […] distributed all over the code to handle a particular case or support a specific feature […] special tools are used to analyze the code […] and create […] fixup tables […] automated […] using conditional defines […] to declare the various cases […] not only optional at assembly time but at initialization time […] without the […] overhead of having at least some amount of dead code left in the runtime image […] to keep track of all the dependencies between […] these conditionals, dynamically build and relocate the runtime image, fix up all the references between these small, changing, and moving binary parts […] still allowing to use the tiny .COM/.SYS style […] model […] is done at initialization time […] API to import and export object structures between FreeKEYB and the calling application […] to transparently resize and move them internally […] at runtime […]
[…]Lazy evaluation is basicallydynamic dead code elimination. […](NB. Possibly the first public use of the termdynamic dead-code elimination, though only conceptually and with a focus on lazy evaluation infunctional languages.)
[…] brandneue[s] Feature, derdynamischen Dead-Code-Elimination, die die jeweils notwendigen Bestandteile des Treibers erst zum Installationszeitpunkt zusammenbastelt und reloziert, so daß keine ungenutzten Code- oder Datenbereiche mehr resident bleiben (z.B. wenn jemand ein bestimmtes FreeKEYB-Feature nicht benötigt). […](NB. This represents the first known implementation of byte-level granulardynamic dead-code elimination for softwareassembled orcompiled ahead-of-time.)