Dead-code elimination#Dynamic dead-code elimination
{{Short description|Compiler optimization to remove code which does not affect the program results}}
{{Use dmy dates|date=April 2019|cs1-dates=y}}
{{Use list-defined references|date=December 2021}}
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, it reduces resource usage such as the number of bytes to be transferredMalavolta, Ivano et al. “JavaScript Dead Code Identification, Elimination, and Empirical Assessment.” IEEE transactions on software engineering 49.7 (2023): 3692–3714. Web. 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 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.
Examples
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;
}
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 and there is no label after it which a "goto" could reach, 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, 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 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) {
int a = 5;
int b = 6;
int c;
c = a * (b / 2);
if (0) { /* DEBUG */
printf("%d\n", c);
}
return c;
}
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 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. An algorithm based on static single-assignment form (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.
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 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. 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 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 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. 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
References
{{reflist|refs=
{{cite book |author-first1=Frances |author-last1=Allen |author-first2=John |author-last2=Cocke |author-link2=John Cocke (computer scientist) |author-first3=Ken |author-last3=Kennedy |author-link3=Ken Kennedy (computer scientist) |chapter=Reduction of Operator Strength |title=Program Flow Analysis: Theory & Application |editor-first1=Neil D. |editor-last1=Jones |editor-link1=Neil D. Jones |editor-first2=Steven Stanley |editor-last2=Muchnick |editor-link2=Steven Stanley Muchnick |publisher=Prentice-Hall |date=June 1981 |isbn=0-13729681-9}}
{{cite book |author-first=Ken |author-last=Kennedy |author-link=Ken Kennedy (computer scientist) |chapter=A Survey of Data-flow Analysis Techniques |title=Program Flow Analysis: Theory & Application |editor-first1=Neil D. |editor-last1=Jones |editor-link1=Neil D. Jones |editor-first2=Steven Stanley |editor-last2=Muchnick |editor-link2=Steven Stanley Muchnick |publisher=Prentice-Hall |date=June 1981 |isbn=0-13729681-9}}
{{cite book |author-first1=Ron K. |author-last1=Cytron |author-first2=Jeanne |author-last2=Ferrante |author-link2=Jeanne Ferrante |author-first3=Barry K. |author-last3=Rosen |author-first4=F. Kenneth |author-last4=Zadeck |title=Efficiently Computing Static Single Assignment Form and the Program Dependence Graph |id=ACM TOPLAS 13(4) |date=1991}}
{{cite book |author-first1=Keith D. |author-last1=Cooper |author-link1=Keith D. Cooper |author-first2=Linda |author-last2=Torczon |title=Engineering a Compiler |publisher=Morgan Kaufmann |date=2003 |orig-year=2002-01-01 |pages=498ff |isbn=978-1-55860698-2}}
{{cite newsgroup |title=Cyclic data structures |author-first=Andrew |author-last=Conway |date=1995-12-04 |newsgroup=comp.lang.functional |url=https://groups.google.com/d/msg/comp.lang.functional/zFsRAGroeVM/2L5TIgcG-1IJ |access-date=2017-07-03 |url-status=live |archive-url=https://archive.today/20170909085605/https://groups.google.com/forum/%23!msg/comp.lang.functional/zFsRAGroeVM/2L5TIgcG-1IJ |archive-date=2017-09-09 |quote=[…] Lazy evaluation is basically dynamic dead code elimination. […]}} (NB. Possibly the first public use of the term dynamic dead-code elimination, though only conceptually and with a focus on lazy evaluation in functional languages.)
{{cite newsgroup |title=[ANN] FreeDOS beta 6 released |author-first=Matthias R. |author-last=Paul |date=2001-04-10 |language=German |newsgroup=de.comp.os.msdos |url=https://groups.google.com/d/msg/de.comp.os.msdos/qCZs8p6MyPQ/Pksl0Pv6qM8J |access-date=2017-07-02 |url-status=live |archive-url=https://archive.today/20170909084250/https://groups.google.com/forum/%23!msg/de.comp.os.msdos/qCZs8p6MyPQ/Pksl0Pv6qM8J |archive-date=2017-09-09 |quote=[…] brandneue[s] Feature, der dynamischen 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 granular dynamic dead-code elimination for software assembled or compiled ahead-of-time.)
{{cite web |title=[fd-dev] Ctrl+Alt+Del |author-first=Matthias R. |author-last=Paul |date=2002-04-03 |orig-year=2001-06-18 |work=freedos-dev |url=https://marc.info/?l=freedos-dev&m=101783474625117 |access-date=2017-09-09 |url-status=live |archive-url=https://archive.today/20170909084942/https://marc.info/?l=freedos-dev&m=101783474625117 |archive-date=2017-09-09 |quote=[…] any of the […] options can be "permanently" excluded at installation time (will also save the memory for the corresponding code excerpts due to our Dynamic 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.}}
{{citation |title=FreeKEYB - Enhanced DOS keyboard and console driver |edition=v6.5 |author-first1=Matthias R. |author-last1=Paul |author-first2=Axel C. |author-last2=Frinke |type=User Manual |date=1997-10-13 |orig-year=first published 1991}} [https://web.archive.org/web/20190309194320/http://sta.c64.org/dosprg/fk657p1.zip] (NB. FreeKEYB is a Unicode-based dynamically configurable successor of K3PLUS supporting most keyboard layouts, code pages, and country codes. Utilizing an off-the-shelf macro assembler as well as a framework of automatic pre- and post-processing analysis tools to generate dependency and code morphing meta data to be embedded into the executable file alongside the binary code and a self-discarding, relaxing and relocating loader, the driver implements byte-level granular dynamic dead-code elimination and relocation techniques at load-time as well as self-modifying code and reconfigurability at run-time to minimize its memory footprint downto close the canonical form depending on the underlying hardware, operating system, and driver configuration as well as the selected feature set and locale (about sixty configuration switches with hundreds of options for an almost unlimited number of possible combinations). This complexity and the dynamics are hidden from users, who deal with a single executable file just like they would do with a conventional driver. K3PLUS was an extended keyboard driver for DOS widely distributed in Germany at its time, with adaptations to a handful of other European languages available. It supported a sub-set of features already, but did not implement dynamic dead-code elimination.)
{{cite web |title=Dynamic Dead-Instruction Detection and Elimination |author-first1=J. Adam |author-last1=Butts |author-first2=Guri |author-last2=Sohi |publisher=Computer Science Department, University of Wisconsin-Madison |date=October 2002 |id=ASPLOS X ACM 1-58113-574-2/02/0010 |location=San Jose, CA, USA |url=https://ftp.cs.wisc.edu/sohi/papers/2002/deadinstructions.asplos.pdf |access-date=2017-06-23 |url-status=live |archive-url=https://archive.today/20190420144100/http://ftp.cs.wisc.edu/sohi/papers/2002/deadinstructions.asplos.pdf |archive-date=2019-04-20}}
{{cite book |title=Intentia Movex Java on the IBM iSeries Server - An Implementation Guide - Overview of Movex Java on the iSeries server - Movex Java on iSeries installation and configuration - Operational tips and techniques |chapter=Chapter 5. Java overview and iSeries implementation - 5.1.1. Miscellaneous components |author-first1=Yessong |author-last1=Johng |author-first2=Per |author-last2=Danielsson |author-first3=Per |author-last3=Ehnsiö |author-first4=Mats |author-last4=Hermansson |author-first5=Mika |author-last5=Jolanki |author-first6=Scott |author-last6=Moore |author-first7=Lars |author-last7=Strander |author-first8=Lars |author-last8=Wettergren |page=41 |series=Red Books |publisher=IBM Corp. |date=2002-11-08 |id=SG24-6545-00 |isbn=0-73842461-7 |url=https://www.redbooks.ibm.com/redbooks/pdfs/sg246545.pdf |access-date=2019-04-20 |url-status=live |archive-url=https://web.archive.org/web/20131008194558/http://www.redbooks.ibm.com/redbooks/pdfs/sg246545.pdf |archive-date=2013-10-08}} [https://www.redbooks.ibm.com/abstracts/sg246545.html]
{{cite web |title=Virtualization Support for Application Runtime Specialization and Extension - Programming Languages |author-first=Guillermo |author-last=Polito |publisher=Universite des Sciences et Technologies de Lille |date=2015 |id=HAL Id: tel-01251173 |pages=111–124 |url=https://hal.inria.fr/tel-01251173/file/Poli15Thesis.pdf |access-date=2017-06-23 |url-status=live |archive-url=https://web.archive.org/web/20170623021500/https://hal.inria.fr/tel-01251173/file/Poli15Thesis.pdf |archive-date=2017-06-23}}
{{cite thesis |title=A Just in Time Register Allocation and Code Optimization Framework for Embedded Systems |author-first=Sathyanarayan |author-last=Thammanur |date=2001-01-31 |type=MS thesis |id=ucin982089462 |publisher=University of Cincinnati, Engineering: Computer Engineering |url=http://rave.ohiolink.edu/etdc/view?acc_num=ucin982089462}} [https://etd.ohiolink.edu/!etd.send_file?accession=ucin982089462&disposition=inline] {{Webarchive|url=https://web.archive.org/web/20190728221938/https://etd.ohiolink.edu/!etd.send_file?accession=ucin982089462&disposition=inline |date=2019-07-28}}[https://etd.ohiolink.edu/!etd.send_file?accession=ucin982089462&disposition=attachment] {{Webarchive|url=https://web.archive.org/web/20190728221727/https://etd.ohiolink.edu/!etd.send_file?accession=ucin982089462&disposition=attachment |date=2019-07-28}}
}}
Further reading
- {{cite journal |title=Partial dead code elimination using slicing transformations |journal=Proceedings of the ACM SIGPLAN 1997 Conference on Programming Language Design and Implementation (PLDI '97) |author-first1=Rastislav |author-last1=Bodík |author-first2=Rajiv |author-last2=Gupta |author-link2=Rajiv Gupta (technocrat) |date=June 1997 |pages=682–694}}
- {{cite book |author-first1=Alfred Vaino |author-last1=Aho |author-link1=Alfred Vaino Aho |author-first2=Ravi |author-last2=Sethi |author-link2=Ravi Sethi |author-first3=Jeffrey David |author-last3=Ullman |author-link3=Jeffrey David Ullman |title=Compilers - Principles, Techniques and Tools |url=https://archive.org/details/compilersprincip00ahoa |url-access=registration |publisher=Addison Wesley Publishing Company |date=1986 |isbn=0-201-10194-7}}
- {{cite book |author-first=Steven Stanley |author-last=Muchnick |author-link=Steven Stanley Muchnick |title=Advanced Compiler Design and Implementation |publisher=Morgan Kaufmann Publishers |date=1997 |isbn=1-55860-320-4 |url-access=registration |url=https://archive.org/details/advancedcompiler00much }}
- {{cite book |author-first1=Dick |author-last1=Grune |author-link1=Dick Grune |author-first2=Henri Elle |author-last2=Bal |author-link2=Henri Elle Bal |author-first3=Ceriel J. H. |author-last3=Jacobs |author-first4=Koen G. |author-last4=Langendoen |title=Modern Compiler Design |publisher=John Wiley & Sons, Inc. |date=2000 |isbn=0-471-97697-0}}
- {{cite book |author-last1=Kennedy |author-first1=Ken |author-link1=Ken Kennedy (computer scientist) |author-last2=Allen |author-first2=Randy |title=Optimizing Compilers for Modern Architectures: A Dependence-Based Approach |url=https://archive.org/details/optimizingcompil00alle_837 |url-access=limited |chapter=Chapter 4.4. Data Flow Analysis - Chapter 4.4.2. Dead Code Elimination |publisher=Academic Press / Morgan Kaufmann Publishers / Elsevier |date=2002 |edition=2011 digital print of 1st |isbn=978-1-55860-286-1 |lccn=2001092381 |pages=[https://archive.org/details/optimizingcompil00alle_837/page/n134 137], 145–147, 167}}
- {{cite journal |date=January 2001 |orig-date=1999-11-02 |title=alto: a link-time optimizer for the Compaq Alpha. |author-first1=Robert |author-last1=Muth |author-first2=Saumya K. |author-last2=Debray |author-first3=Scott |author-last3=Watterson |author-first4=Koen |author-last4=De Bosschere |journal=Software: Practice and Experience |volume=31 |issue=1 |doi=10.1002/1097-024X(200101)31:1<67::AID-SPE357>3.0.CO;2-A |s2cid=442062 |citeseerx=10.1.1.33.4933 |pages=67–101}} [https://web.archive.org/web/20100721082900/http://www.cs.arizona.edu/~debray/Publications/alto.pdf]
External links
- [https://archive.today/20130112201318/http://www.futurechips.org/tips-for-power-coders/how-to-trick-cc-compilers-into-generating-terrible-code.html How to trick C/C++ compilers into generating terrible code?]
{{Compiler optimizations}}