En teoría compilador , eliminación de código muerto (también conocido como DCE , la eliminación de código muerto , código muerto de extracción , o tira de código muerto ) es una optimización del compilador para eliminar código que no afecta a los resultados del programa. Eliminar dicho código tiene varios beneficios: reduce el tamaño del programa, una consideración importante en algunos contextos, y permite que el programa en ejecución evite ejecutar operaciones irrelevantes, lo que reduce su tiempo de ejecución. También puede permitir más optimizaciones simplificando la estructura del programa. El código muerto incluye código que nunca se puede ejecutar ( código inalcanzable ) y código que solo afectavariables muertas (escritas en, pero nunca leídas de nuevo), es decir, irrelevantes para el programa.
Ejemplos de
Consideremos el siguiente ejemplo escrito en C .
int foo ( vacío ) { 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 ; }
El simple análisis de los usos de los valores mostraría que el valor de b
después de la primera asignación no se usa en el interior foo
. Además, b
se declara como una variable local en el interior foo
, por lo que su valor no se puede utilizar en el exterior foo
. Por lo tanto, la variable b
está muerta y un optimizador puede recuperar su espacio de almacenamiento y eliminar su inicialización.
Además, debido a que la primera declaración de retorno se ejecuta incondicionalmente, ninguna ruta de ejecución factible alcanza 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 declaración de retorno y goto
otra en el procedimiento, entonces podría existir una ruta de ejecución factible para la asignación 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), puede simplificarse 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 diferentes niveles. Un nivel inferior solo puede eliminar las instrucciones que no se pueden ejecutar. Es posible que un nivel superior tampoco reserve espacio para variables no utilizadas. Un nivel aún más alto podría determinar instrucciones o funciones que no tienen ningún propósito y eliminarlas.
Un uso común de la eliminación de código muerto es como una alternativa a la inclusión de código opcional a través de un preprocesador . Considere el siguiente código.
int main ( vacío ) { 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 instrucción if nunca se puede ejecutar y la eliminación del código muerto 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 muerto elimina la necesidad de utilizar un preprocesador para realizar la misma tarea.
En la práctica, gran parte del código muerto que encuentra un optimizador se crea mediante 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 mueren los cálculos más antiguos y costosos. [1] La eliminación posterior del código muerto elimina esos cálculos y completa el efecto (sin complicar el algoritmo de reducción de fuerza).
Históricamente, la eliminación de códigos muertos se realizaba utilizando información derivada del análisis de flujo de datos . [2] 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. [3] Robert Shillingsburg (también conocido como Shillner) mejoró el algoritmo y desarrolló un algoritmo complementario para eliminar operaciones de flujo de control inútiles. [4]
Eliminación dinámica de códigos muertos
El código muerto normalmente se considera muerto incondicionalmente . Por lo tanto, es razonable intentar eliminar el código inactivo mediante la eliminación del código inactivo 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 inactivo o inalcanzable solo bajo ciertas condiciones , que pueden no ser conocidas en el momento de la compilación o ensamblaje. Tales 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 en al mismo tiempo, se convierte en código condicionalmente muerto para los demás casos. [5] [6] Además, el software (por ejemplo, un controlador o un servicio residente) puede ser configurable para incluir o excluir ciertas características según las preferencias del usuario, haciendo que las porciones de código no utilizadas sean inútiles en un escenario particular. [5] [6] Si bien se puede desarrollar software modular para cargar dinámicamente bibliotecas solo bajo demanda, en la mayoría de los casos, no es posible cargar solo las rutinas relevantes de una biblioteca en particular, e incluso si esto fuera compatible, una rutina puede todavía incluyen secciones de código que pueden considerarse código inactivo en un escenario dado, pero que ya no se pueden descartar 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 condicionalmente muerto y recombinar el código restante en carga o tiempo de ejecución se denominan eliminación dinámica de código muerto [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] o eliminación dinámica de instrucción muerta . [18]
La mayoría de los lenguajes de programación, compiladores y sistemas operativos ofrecen poco o nada más soporte que la carga dinámica de bibliotecas y la vinculación tardía , por lo que el software que utiliza la eliminación dinámica de código muerto es muy raro junto con lenguajes compilados con anticipación o escritos en lenguaje ensamblador . [7] [11] [8] Sin embargo, las implementaciones de lenguaje que hacen compilación justo a tiempo pueden optimizar dinámicamente para la eliminación de código muerto. [17] [19] [20]
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 .
Ver también
- 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)
- Cruft de software
- Temblor de árbol
- Optimización posterior a la pasada
- Optimización guiada por perfiles
- Superoptimizer
- Compactación de la recolección de basura
Referencias
- ^ Allen, Frances; Cocke, John ; Kennedy, Ken (junio de 1981). "Reducción de la fuerza del operador". En Jones, Neil D .; Muchnick, Steven Stanley (eds.). Análisis de flujo del programa: teoría y aplicación . Prentice-Hall . ISBN 0-13729681-9.
- ^ Kennedy, Ken (junio de 1981). "Una encuesta de técnicas de análisis de flujo de datos". En Jones, Neil D .; Muchnick, Steven Stanley (eds.). Análisis de flujo del programa: teoría y aplicación . Prentice-Hall . ISBN 0-13729681-9.
- ^ Cytron, Ron K .; Ferrante, Jeanne ; Rosen, Barry K .; Zadeck, F. Kenneth (1991). Calcular eficientemente el formulario de asignación estática única y el gráfico de dependencia del programa . ACM TOPLAS 13 (4).
- ^ Cooper, Keith D .; Torczon, Linda (2003) [1 de enero de 2002]. Ingeniería de un compilador . Morgan Kaufmann . págs. 498ff. ISBN 978-1-55860698-2.
- ^ a b c Paul, Matthias R. (3 de abril de 2002) [18 de junio de 2001]. "[fd-dev] Ctrl + Alt + Supr" . freedos-dev . Archivado desde el original el 9 de septiembre de 2017 . Consultado el 9 de septiembre de 2017 .
[…] Cualquiera de las […] opciones se puede excluir "permanentemente" en el momento de la instalación (también guardará la memoria para los extractos de código correspondientes debido a nuestra eliminación dinámica de código muerto ), o se puede deshabilitar o habilitar en cualquier momento posterior a través de funciones API en caso de que alguien quiera evitar que un usuario pueda reiniciar la máquina. […] Estamos considerando agregar más llamadas de vaciado de caché síncronas […] Debido a nuestro método de eliminación dinámica de código muerto, esto no causaría ningún tipo de hinchazón cuando no sea necesario en una configuración de destino en particular, ya que se incluiría una llamada de vaciado de caché particular en La imagen de tiempo de ejecución de FreeKEYB solo si la caché de disco correspondiente también está cargada o si los interruptores de línea de comando le dijeron a FreeKEYB que cargara el soporte correspondiente.
- ^ a b c Paul, Matthias R. (6 de abril de 2002). "[fd-dev] Ctrl + Alt + Supr" . freedos-dev . Archivado desde el original el 27 de abril de 2019 . Consultado el 27 de abril de 2019 .
[…] FreeKEYB crea la imagen en tiempo de ejecución del controlador en el momento de la inicialización según el tipo de máquina en la que se está cargando, el tipo de teclado, la distribución, el país y la página de códigos utilizados, el tipo de mouse y adaptador (s) de video instalados, la otros controladores cargados en ese sistema, el sistema operativo y los métodos de carga y reubicación utilizados, las funciones individuales incluidas y las opciones de configuración especificadas en la línea de comandos. Debido a la gran cantidad de opciones y conmutadores de línea de comandos admitidos […] (alrededor de cincuenta conmutadores […] con múltiples configuraciones posibles), existe una gran cantidad de combinaciones de funciones con incontables dependencias […] que dan como resultado […] un sinfín de [ …] Diferentes imágenes de destino. La técnica de eliminación dinámica de códigos muertos de FreeKEYB logra resolver […] estas […] dependencias y […] eliminar códigos muertos y datos […] no se limita a […] incluir o excluir un número algo limitado de módulos o subrutinas completas y arreglar algunas tablas de despacho como en la programación TSR clásica, pero […] funciona […] a […] nivel de bytes […] capaz de eliminar […] instrucciones individuales en medio de rutinas más grandes […] distribuidas por todo el código para manejar un caso particular o dar soporte a una característica específica […] se utilizan herramientas especiales para analizar el código […] y crear […] tablas de corrección […] automatizadas […] usando definiciones condicionales […] para declarar los diversos casos […] No solo es opcional en el momento del ensamblaje sino en el momento de la inicialización […] sin la […] sobrecarga de tener al menos una cantidad de código muerto en la imagen en tiempo de ejecución […] para realizar un seguimiento de todas las dependencias entre […] estos condicionales, construyen dinámicamente y reubican la imagen en tiempo de ejecución, arreglan todas las referencias entre estos pequeños l, cambiando y moviendo partes binarias […] aún permite usar el pequeño estilo .COM / .SYS […] modelo […] se realiza en el momento de la inicialización […] API para importar y exportar estructuras de objetos entre FreeKEYB y la llamada aplicación […] para cambiar el tamaño de forma transparente y moverlos internamente […] en tiempo de ejecución […]
- ^ a b Paul, Matthias R .; Frinke, Axel C. (1997-10-13) [publicado por primera vez en 1991], FreeKEYB - Controlador de consola y teclado DOS mejorado (Manual del usuario) (v6.5 ed.) [1] (NB. FreeKEYB es un Unicode -basado sucesor dinámicamente configurable de K3PLUS apoyar la mayoría de las disposiciones de teclado , páginas de códigos , y los códigos de país . Utilizando un off-the-shelf macro ensamblador , así como un marco de pre- automático y post- procesando herramientas de análisis para generar dependencia y metadatos de transformación de código para ser incrustados en el archivo ejecutable junto con el código binario y un cargador de auto-descarte, relajación y reubicación , el controlador implementa técnicas de eliminación y reubicación de código muerto dinámico granular a nivel de bytes en la carga tiempo , así como código auto-modificable y reconfigurabilidad en tiempo de ejecución para minimizar su huella de memoria hacia abajo para cerrar la forma canónica según el hardware subyacente, el sistema operativo y la configuración del controlador, así como el conjunto de características y la configuración regional seleccionados (alrededor de sesenta conmutadores de configuración con cientos de opciones para un número casi ilimitado de combinaciones posibles). Esta complejidad y la dinámica están ocultas a los usuarios, que se ocupan de un solo archivo ejecutable tal como lo harían con un controlador convencional. K3PLUS era un controlador de teclado extendido para DOS ampliamente distribuido en Alemania en su momento, con adaptaciones a un puñado de otros idiomas europeos disponibles. Ya era compatible con un subconjunto de funciones, pero no implementó la eliminación dinámica de códigos muertos).
- ^ a b Paul, Matthias R. (10 de abril de 2001). "[ANN] FreeDOS beta 6 lanzado" (en alemán). Grupo de noticias : de.comp.os.msdos . Archivado desde el original el 9 de septiembre de 2017 . Consultado el 2 de julio de 2017 .
[…] 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 residente emandin wBEY Feature nicht benötigt). […]
(NB. Esto representa la primera implementación conocida de eliminación de código muerto dinámico granular a nivel de bytes para software ensamblado o compilado con anticipación ). - ^ Paul, Matthias R. (21 de agosto de 2001). "[fd-dev] Cambiando páginas de códigos en FreeDOS" . freedos-dev . Archivado desde el original el 19 de abril de 2019 . Consultado el 20 de abril de 2019 .
[…] Una […] característica única […] que llamamos eliminación dinámica de código muerto , por lo que puede en el momento de la instalación […] especificar qué componentes del controlador desea y cuáles no. Esto llega hasta cierto punto de modularización cargable dinámica y vinculación tardía que no he visto en DOS hasta ahora. Si no le gusta el protector de pantalla, las macros, la calculadora o la compatibilidad con el mouse, o
, puede especificar esto en la línea de comando, y FreeKEYB, teniendo en cuenta todas las dependencias entre las rutinas, lo hará completamente. elimine todos los fragmentos de código, que se ocupan de esa función y no son necesarios para proporcionar la funcionalidad solicitada, antes de que el controlador reubique la imagen en la ubicación de destino y se convierta en residente. Eliminar algunas características más pequeñas solo ahorra un par de bytes, pero excluir componentes más complejos puede ahorrarle medio Kb y más. También puede especificar el tamaño de las áreas de datos […] - ^ Paul, Matthias R. (30 de diciembre de 2001). "Estructura interna de KEYBOARD.SYS" . Grupo de noticias : comp.os.msdos.programmer . Archivado desde el original el 9 de septiembre de 2017 . Consultado el 3 de julio de 2017 .
[…] El cargador optimizará dinámicamente las áreas de datos residentes y las secciones de código a nivel de byte para eliminar cualquier redundancia del controlador dependiendo de la configuración local y del hardware / software / controlador dados. […]
- ^ a b Paul, Matthias R .; Frinke, Axel C. (2006-01-16), FreeKEYB - Controlador de consola y teclado DOS internacional avanzado (Manual del usuario) (v7 edición preliminar)
- ^ Paul, Matthias R. (2 de febrero de 2002). "Treiber dynamisch nachladen (Intra-Segment-Offset-Relokation zum Laden von TSRs in die HMA)" [Carga de controladores dinámicamente ( Reubicación de offset intrasegmento para cargar TSR en el HMA)] (en alemán). Grupo de noticias : de.comp.os.msdos . Archivado desde el original el 9 de septiembre de 2017 . Consultado el 2 de julio de 2017 .
- ^ Paul, Matthias R. (24 de febrero de 2002). "¿Información GEOS / NDO para RBIL62?" . Grupo de noticias : comp.os.geos.programmer . Archivado desde el original el 20 de abril de 2019 . Consultado el 20 de abril de 2019 .
[…] Dado que FreeKEYB usa nuestra eliminación dinámica de código muerto para optimizar su imagen de memoria para el entorno de destino en el tiempo de carga, ciertamente me gustaría agregar soporte especial en FreeKEYB para GEOS que podría ser controlado por una opción de línea de comando, por lo que el el código adicional solo se carga cuando también se usa GEOS. […]
- ^ Paul, Matthias R. (15 de marzo de 2002). "¿Capa de teclado AltGr debajo de GEOS?" . Grupo de noticias : comp.os.geos.misc . Archivado desde el original el 20 de abril de 2019 . Consultado el 20 de abril de 2019 .
[…] Estaría dispuesto a agregar ganchos especiales en FreeKEYB, nuestro controlador de teclado DOS muy avanzado, ¿demostraría mejorar la usabilidad bajo GEOS […] Debido a nuestra nueva y sofisticada tecnología Dynamic Dead Code Elimination que elimina a nivel de byte cualquier código fragmentos no utilizados en un determinado controlador, usuario o configuración del sistema y entorno de hardware cuando el instalador del controlador crea y reubica la imagen de carga de sí mismo, esto no tendría ningún impacto en la memoria para los usuarios que no son de GEOS, por lo que no hay mucho de qué preocuparse (espacio de memoria, etc.) como en los controladores DOS codificados tradicionalmente. […]
- ^ Thammanur, Sathyanarayan (31 de enero de 2001). Un marco de optimización de código y asignación de registros Just in Time para sistemas integrados (tesis de maestría). Universidad de Cincinnati , Ingeniería: Ingeniería informática. ucin982089462. [2] [3]
- ^ Glew, Andy (2 de marzo de 2011). "Eliminación dinámica de códigos muertos y futuros de hardware" . [4] [5]
- ^ a b Conway, Andrew (4 de diciembre de 1995). "Estructuras cíclicas de datos" . Grupo de noticias : comp.lang.functional . Archivado desde el original el 9 de septiembre de 2017 . Consultado el 3 de julio de 2017 .
[…] La evaluación perezosa es básicamente la eliminación dinámica de código muerto . […]
(NB. Posiblemente el primer uso público del término eliminación dinámica de código muerto , aunque solo conceptualmente y con un enfoque en la evaluación perezosa en lenguajes funcionales ). - ^ Butts, J. Adam; Sohi, Guri (octubre de 2002). "Detección y eliminación dinámica de instrucciones muertas" (PDF) . San José, CA, EE.UU .: Departamento de Ciencias de la Computación, Universidad de Wisconsin-Madison . ASPLOS X ACM 1-58113-574-2 / 02/0010 . Archivado (PDF) desde el original el 20 de abril de 2019 . Consultado el 23 de junio de 2017 .
- ^ Johng, Yessong; Danielsson, Per; Ehnsiö, Per; Hermansson, Mats; Jolanki, Mika; Moore, Scott; Strander, Lars; Wettergren, Lars (8 de noviembre de 2002). "Capítulo 5. Visión general de Java e implementación de iSeries - 5.1.1. Componentes varios". Intentia Movex Java en IBM iSeries Server - Guía de implementación - Visión general de Movex Java en el servidor iSeries - Instalación y configuración de Movex Java en iSeries - Consejos y técnicas operativas (PDF) . Libros rojos. IBM Corp. pág. 41. ISBN 0-73842461-7. SG24-6545-00. Archivado (PDF) desde el original el 8 de octubre de 2013 . Consultado el 20 de abril de 2019 . [6]
- ^ Polito, Guillermo (2015). "Soporte de virtualización para la especialización y extensión en tiempo de ejecución de aplicaciones - Lenguajes de programación" (PDF) . Université des Sciences et Technologies de Lille . págs. 111-124. Identificación de HAL: tel-01251173. Archivado (PDF) desde el original el 23 de junio de 2017 . Consultado el 23 de junio de 2017 .
Otras lecturas
- Bodík, Rastislav; Gupta, Rajiv (junio de 1997). "Eliminación parcial de código muerto mediante transformaciones de corte". 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 . Editores Morgan Kaufmann . 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 de flujo de datos - Capítulo 4.4.2. Eliminación de códigos muertos". Optimización de compiladores para arquitecturas modernas: un enfoque basado en la dependencia (impresión digital de 2011 de la 1ª ed.). Prensa académica / Morgan Kaufmann Publishers / Elsevier . págs. 137 , 145-147, 167. ISBN 978-1-55860-286-1. LCCN 2001092381 .
enlaces externos
- ¿Cómo engañar a los compiladores de C / C ++ para que generen un código terrible?