Eliminación de código muerto

En teoría del compilador , la eliminación de código muerto ( DCE , dead-code removal , dead-code stripping o dead-code strip ) es una optimización del compilador para eliminar el código muerto (código que no afecta los resultados del programa). Eliminar dicho código tiene varios beneficios: reduce el tamaño del programa , una consideración importante en algunos contextos, reduce el uso de recursos como el número de bytes a transferir ^[1] y permite que el programa en ejecución evite ejecutar operaciones irrelevantes , lo que reduce su tiempo de ejecución . También puede permitir optimizaciones adicionales al simplificar la estructura del programa. El código muerto incluye código que nunca se puede ejecutar ( código inalcanzable ) y código que solo afecta a las variables muertas (escritas, pero nunca leídas de nuevo), es decir, irrelevantes para el programa.

Considere el siguiente ejemplo escrito en C.

int foo ( void ) { int a = 24 ; int b = 25 ; /* Asignación a variable muerta */ int c ; c = a * 4 ; return c ; b = 24 ; /* Código inalcanzable */ return 0 ; }                          

Un análisis simple de los usos de los valores mostraría que el valor de bdespués de la primera asignación no se utiliza dentro de foo. Además, bse declara como una variable local dentro de foo, por lo que su valor no se puede utilizar fuera de foo. Por lo tanto, la variable bestá inactiva y un optimizador puede recuperar su espacio de almacenamiento y eliminar su inicialización.

Además, debido a que la primera instrucción de retorno se ejecuta incondicionalmente y no hay ninguna etiqueta después de ella a la que pueda llegar un "goto", ninguna ruta de ejecución factible llega a la segunda asignación a b. Por lo tanto, la asignación es inalcanzable y se puede eliminar. Si el procedimiento tuviera un flujo de control más complejo , como una etiqueta después de la instrucción de retorno y una gotoen otra parte del procedimiento, entonces podría existir una ruta de ejecución factible hacia la asignación a b.

Además, aunque algunos cálculos se realizan en la función, sus valores no se almacenan en ubicaciones accesibles fuera del alcance de esta función. Además, dado que la función devuelve un valor estático (96), se puede simplificar al valor que devuelve (esta simplificación se denomina plegado constante ).

La mayoría de los compiladores avanzados tienen opciones para activar la eliminación de código muerto, a veces en distintos niveles. Un nivel inferior podría eliminar únicamente las instrucciones que no se pueden ejecutar. Un nivel superior también podría no reservar espacio para las variables no utilizadas. Un nivel aún más alto podría determinar las instrucciones o funciones que no sirven para nada y eliminarlas.

Un uso común de la eliminación de código muerto es como alternativa a la inclusión de código opcional a través de un preprocesador . Considere el siguiente código.

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

Debido a que la expresión 0 siempre se evaluará como falsa , el código dentro de la declaración if nunca se puede ejecutar y la eliminación de código inactivo lo eliminaría por completo del programa optimizado. Esta técnica es común en la depuración para activar opcionalmente bloques de código; el uso de un optimizador con eliminación de código inactivo elimina la necesidad de usar un preprocesador para realizar la misma tarea.

En la práctica, gran parte del código inactivo que encuentra un optimizador es creado por otras transformaciones en el optimizador. Por ejemplo, las técnicas clásicas para la reducción de la fuerza del operador insertan nuevos cálculos en el código y hacen que los cálculos más antiguos y costosos queden inactivos. ^[2] La eliminación posterior del código inactivo elimina esos cálculos y completa el efecto (sin complicar el algoritmo de reducción de la fuerza).

Históricamente, la eliminación de código muerto se realizaba utilizando información derivada del análisis del flujo de datos . ^[3] Un algoritmo basado en el formulario de asignación única estática (SSA) aparece en el artículo de revista original sobre el formulario SSA de Ron Cytron et al. ^[4] Robert Shillingsburg (también conocido como Shillner) mejoró el algoritmo y desarrolló un algoritmo complementario para eliminar operaciones de flujo de control inútiles. ^[5]

El código muerto normalmente se considera muerto incondicionalmente . Por lo tanto, es razonable intentar eliminar el código muerto mediante la eliminación del código muerto en el momento de la compilación .

Sin embargo, en la práctica también es común que las secciones de código representen código muerto o inalcanzable solo bajo ciertas condiciones , que pueden no conocerse en el momento de la compilación o el ensamblaje. Dichas condiciones pueden ser impuestas por diferentes entornos de ejecución (por ejemplo, diferentes versiones de un sistema operativo o diferentes conjuntos y combinaciones de controladores o servicios cargados en un entorno de destino particular), que pueden requerir diferentes conjuntos de casos especiales en el código, pero al mismo tiempo se convierten en código condicionalmente muerto para los otros casos. ^{[6] [7]} Además, el software (por ejemplo, un controlador o servicio residente) puede configurarse para incluir o excluir ciertas características según las preferencias del usuario, lo que hace que las porciones de código no utilizadas sean inútiles en un escenario particular. ^{[6] [7]} Si bien se puede desarrollar software modular para cargar bibliotecas dinámicamente solo a pedido, en la mayoría de los casos, no es posible cargar solo las rutinas relevantes de una biblioteca en particular, e incluso si esto se admitiera, una rutina aún puede incluir secciones de código que pueden considerarse código muerto en un escenario dado, pero que no podrían descartarse en el momento de la compilación.

Las técnicas utilizadas para detectar dinámicamente la demanda, identificar y resolver dependencias, eliminar dicho código muerto condicionalmente y recombinar el código restante en la carga o el tiempo de ejecución se denominan eliminación dinámica de código muerto ^{[6] [7] [ 8 ] [9 ] [10] [11] [12] [13] [14] [15] [16] [17] [18]} o eliminación dinámica de instrucciones muertas . ^[19]

La mayoría de los lenguajes de programación, compiladores y sistemas operativos no ofrecen, o ofrecen poco más, que la carga dinámica de bibliotecas y el enlace tardío , por lo tanto, el software que utiliza la eliminación dinámica de código muerto es muy poco común en conjunto con lenguajes compilados con anticipación o escritos en lenguaje ensamblador . ^{[8] [12] [9]} Sin embargo, las implementaciones de lenguajes que realizan compilación justo a tiempo pueden optimizar dinámicamente la eliminación de código muerto. ^{[18] [20] [21]}

Aunque con un enfoque bastante diferente, a veces también se utilizan enfoques similares para la actualización dinámica de software y la aplicación de parches en caliente .

• Código redundante
• Simplificación (cálculo simbólico)
• Eliminación de redundancia parcial
• Eliminación de conjunciones
• Actualización dinámica de software
• Acoplamiento dinámico (informática)
• Auto-reubicación
• Basura de software
• Sacudiendo el árbol
• Optimización post-pasada
• Optimización guiada por perfiles
• Superoptimizador
• Función multi-versionado

• Bodík, Rastislav; Gupta, Rajiv (junio de 1997). "Eliminación parcial de código muerto mediante transformaciones de segmentación". Actas de la Conferencia ACM SIGPLAN 1997 sobre diseño e implementación de lenguajes de programación (PLDI '97) : 682–694.
• Aho, Alfred Vaino ; Sethi, Ravi ; Ullman, Jeffrey David (1986). Compiladores: principios, técnicas y herramientas . Addison Wesley Publishing Company . ISBN 0-201-10194-7.
• Muchnick, Steven Stanley (1997). Diseño e implementación de compiladores avanzados . Morgan Kaufmann Publishers . ISBN 1-55860-320-4.
• Grune, Dick ; Bal, Henri Elle ; Jacobs, Ceriel JH; Langendoen, Koen G. (2000). Diseño de compilador moderno . John Wiley & Sons, Inc. ISBN 0-471-97697-0.
• Kennedy, Ken ; Allen, Randy (2002). "Capítulo 4.4. Análisis del flujo de datos - Capítulo 4.4.2. Eliminación de código muerto". Optimización de compiladores para arquitecturas modernas: un enfoque basado en dependencias (edición digital de 2011 de la 1.ª ed.). Academic Press / Morgan Kaufmann Publishers / Elsevier . págs. 137, 145–147, 167. ISBN 978-1-55860-286-1. Número de serie LCCN  2001092381.
• Muth, Robert; Debray, Saumya K.; Watterson, Scott; De Bosschere, Koen (enero de 2001) [2 de noviembre de 1999]. "alto: un optimizador de tiempo de enlace para Compaq Alpha". Software: práctica y experiencia . 31 (1): 67–101. CiteSeerX  10.1.1.33.4933 . doi :10.1002/1097-024X(200101)31:1<67::AID-SPE357>3.0.CO;2-A. S2CID  442062.[5]

• ¿Cómo engañar a los compiladores de C/C++ para que generen código terrible?