Dead code elimination

Dead code elimination

In compiler theory, dead code elimination is a compiler optimization 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), and code that only affects dead variables, that is, variables that are irrelevant to the program.

Contents

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 << 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 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. 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. 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, 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.[1] 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.[2] An algorithm based on static single assignment form appears in the original journal article on SSA form by Cytron et al.[3] Shillner improved on the algorithm and developed a companion algorithm for removing useless control-flow operations.[4]

See also

References

Partial dead code elimination using slicing transformations Found in: Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation (PLDI '97) By Rastislav Bodík , Rajiv Gupta Issue Date:June 1997 pp. 682–694

  1. ^ Frances Allen, John Cocke, and Ken Kennedy. Reduction of Operator Strength. In Program Flow Analysis, Muchnick and Jones (editors), Prentice-Hall, 1981.
  2. ^ Ken Kennedy. A Survey of Data-flow Analysis Techniques. In Program Flow Analysis, Muchnick and Jones (editors), Prentice-Hall, 1981.
  3. ^ Ron Cytron, Jeanne Ferrante, Barry Rosen, and Ken Zadeck. Efficiently Computing Static Single Assignment Form and the Program Dependence Graph. ACM TOPLAS 13(4), 1991.
  4. ^ Keith D. Cooper and Linda Torczon, Engineering a Compiler, Morgan Kaufmann, 2003, pages 498ff.

Book references

  • Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1986). Compilers - Principles, Techniques and Tools. Addison Wesley Publishing Company. ISBN 0-201-10194-7. 
  • Grune, Dick; Bal, Henri E.; Jacobs, Ceriel J.H.; Langendoen, Koen G. (2000). Modern Compiler Design. John Wiley & Sons, Inc.. ISBN 0-471-97697-0. 

External Links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Dead code elimination — (englisch für Entfernung von totem Code) ist ein Verfahren aus dem Bereich des Compilerbaus, das nicht verwendete Anweisungen beseitigt. Dadurch kommt es zu einem kleineren Programm mit schnellerer Ausführung. Erläuterung mit Beispielen Gegeben… …   Deutsch Wikipedia

  • Dead code — is a computer programming term for code in the source code of a program which is executed but whose result is never used in any other computation.[1][2] The execution of dead code wastes computation time as its results are never used. While the… …   Wikipedia

  • Code bloat — is the production of code that is perceived as unnecessarily long, slow, or otherwise wasteful of resources. Code bloat can be caused by inadequacies in the language in which the code is written, inadequacies in the compiler used to compile the… …   Wikipedia

  • Unreachable code — In computer programming, unreachable code, or dead code, is code that exists in the source code of a program but can never be executed.Dead code is generally considered undesirable for a number of reasons, including:*If the author of the code… …   Wikipedia

  • Mathematical elimination — 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. The excluded outcome is considered… …   Wikipedia

  • code —    by William Pawlett   The concept of the code (le code, la grille) is an important term in Baudrillard s early work. It is used in two related senses: firstly, to understand and critique consumer capitalism, suggesting that it is a system of… …   The Baudrillard dictionary

  • Uniform civil code — is a term which has originated from the concept of a Civil Law Code. It envisages administering the same set of secular civil laws to govern different people belonging to different religions and regions. This supersedes the right of citizens to… …   Wikipedia

  • 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… …   Wikipedia

  • Static single assignment form — In compiler design, static single assignment form (often abbreviated as SSA form or SSA) is an intermediate representation (IR) in which every variable is assigned exactly once. Existing variables in the original IR are split into versions , new… …   Wikipedia

  • GNU Compiler Collection — Cc1 redirects here. For other uses of CC1 or CC 1, see CC1 (disambiguation). GNU Compiler Collection Developer(s) GNU Project Initial release May 23, 1987 ( …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”