stringtranslate.com

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.

Ejemplos

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]

Eliminación dinámica de código muerto

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 .

Véase también

Referencias

  1. ^ Malavolta, Ivano et al. “Identificación, eliminación y evaluación empírica del código inactivo de JavaScript”. Transacciones IEEE sobre ingeniería de software 49.7 (2023): 3692–3714. Web.
  2. ^ 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 del flujo de programas: teoría y aplicación . Prentice-Hall . ISBN 0-13729681-9.
  3. ^ Kennedy, Ken (junio de 1981). "Un estudio de las técnicas de análisis de flujo de datos". En Jones, Neil D .; Muchnick, Steven Stanley (eds.). Análisis de flujo de programas: teoría y aplicación . Prentice-Hall . ISBN 0-13729681-9.
  4. ^ Cytron, Ron K.; Ferrante, Jeanne ; Rosen, Barry K.; Zadeck, F. Kenneth (1991). Cálculo eficiente de la forma de asignación única estática y el gráfico de dependencia del programa . ACM TOPLAS 13(4).
  5. ^ Cooper, Keith D .; Torczon, Linda (2003) [1 de enero de 2002]. Ingeniería de un compilador . Morgan Kaufmann . pp. 498ff. ISBN 978-1-55860698-2.
  6. ^ abc Paul, Matthias R. (2002-04-03) [2001-06-18]. "[fd-dev] Ctrl+Alt+Del". freedos-dev . Archivado desde el original el 2017-09-09 . Consultado el 2017-09-09 . […] cualquiera de las […] opciones se puede excluir "permanentemente" en el momento de la instalación (también ahorrará 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é sincrónicas […] 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 particular, ya que una llamada de vaciado de caché particular se incluiría en la imagen de tiempo de ejecución de FreeKEYB solo si el caché de disco correspondiente también está cargado o si los modificadores de la línea de comandos le dijeron a FreeKEYB que cargara el soporte correspondiente.
  7. ^ abc Paul, Matthias R. (6 de abril de 2002). «[fd-dev] Ctrl+Alt+Del». freedos-dev . Archivado desde el original el 27 de abril de 2019 . Consultado el 27 de abril de 2019 . […] FreeKEYB crea la imagen de ejecución del controlador en el momento de la inicialización según el tipo de máquina en la que se carga, el tipo de teclado, el diseño, el país y la página de códigos utilizados, el tipo de mouse y adaptador(es) de video instalados, los otros controladores cargados en ese sistema, el sistema operativo y el método(s) de carga y reubicación utilizados, las características individuales incluidas y las opciones de configuración especificadas en la línea de comandos. Debido a la gran cantidad de opciones y parámetros de línea de comandos admitidos […] (alrededor de cincuenta parámetros […] con múltiples configuraciones posibles), existe una gran cantidad de combinaciones de características con incontables dependencias […] lo que resulta en […] un número infinito de […] imágenes de destino diferentes. La técnica de Eliminación Dinámica de Código Muerto de FreeKEYB logra resolver […] estas […] dependencias y […] eliminar código muerto 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, sino que […] funciona […] a nivel de byte […] capaz de eliminar […] instrucciones individuales en medio de rutinas más grandes […] distribuidas por todo el código para manejar un caso particular o soportar una característica específica […] se utilizan herramientas especiales para analizar el código […] y crear […] tablas de arreglo […] automatizadas […] usando definiciones condicionales […] para declarar los diversos casos […] no solo opcionales en tiempo de ensamblaje sino en tiempo de inicialización […] sin la […] sobrecarga de tener al menos alguna cantidad de código muerto restante en la imagen de tiempo de ejecución […] para realizar un seguimiento de todas las dependencias entre […] estos condicionales, construir y reubicar dinámicamente la imagen de tiempo de ejecución, arreglar todas las referencias entre estas pequeñas partes binarias cambiantes y móviles […] aún permitiendo usar el pequeño modelo de estilo .COM/.SYS […] se realiza en tiempo de inicialización […] API para importar y exportar estructuras de objetos entre FreeKEYB y la aplicación que realiza la llamada […] para redimensionarlos y moverlos internamente de forma transparente […] en tiempo de ejecución […]
  8. ^ ab 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) (edición v6.5)[1] (NB. FreeKEYB es un sucesor de K3PLUS configurable dinámicamente basado en Unicode que admite la mayoría de los diseños de teclado , páginas de códigos y códigos de países . Utilizando un ensamblador de macros listo para usar, así como un marco de herramientas de análisis automático de preprocesamiento y posprocesamiento para generar metadatos de dependencia y transformación de código para ser incrustados en el archivo ejecutable junto con el código binario y un cargador de autodescarte, relajación y reubicación , el controlador implementa técnicas de eliminación y reubicación de código muerto dinámicas granulares a nivel de byte en el momento de la carga, así como código de automodificación y reconfigurabilidad en el momento de la ejecución para minimizar su huella de memoria hasta cerca de la forma canónica dependiendo del 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 interruptores 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 tratan con un solo archivo ejecutable 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 disponibles para un puñado de otros idiomas europeos. Ya admitía un subconjunto de características, pero no implementaba la eliminación dinámica de código muerto.
  9. ^ ab Paul, Matthias R. (10 de abril de 2001). "[ANN] Lanzamiento de FreeDOS beta 6" (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 bleiben (zB wenn jemand ein bestimmtes FreeKEYB- Característica no benötigt). […](NB. Esto representa la primera implementación conocida de eliminación de código muerto dinámica granular a nivel de bytes para software ensamblado o compilado con anticipación ).
  10. ^ Paul, Matthias R. (2001-08-21). "[fd-dev] Cambiar páginas de códigos en FreeDOS". freedos-dev . Archivado desde el original el 2019-04-19 . Consultado el 2019-04-20 . […] 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 a un 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 el soporte del mouse, o <casi cualquier otra cosa>, puede especificarlo en la línea de comandos y FreeKEYB, al tiempo que tiene en cuenta todas las dependencias entre las rutinas, eliminará por completo todos los fragmentos de código, que tratan con esa característica 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 funciones más pequeñas solo ahorra un par de bytes, pero excluir componentes más complejos puede ahorrar medio KB o más. También puede especificar el tamaño de las áreas de datos […]
  11. ^ 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 según la configuración y el entorno local del hardware/software/controlador. […]
  12. ^ ab Paul, Matthias R.; Frinke, Axel C. (16 de enero de 2006), FreeKEYB - Controlador de consola y teclado DOS internacional avanzado (Manual del usuario) (edición preliminar v7)
  13. ^ Paul, Matthias R. (2002-02-02). "Carga dinámica de controladores (reubicación de desplazamiento entre segmentos para cargar TSR en la HMA)" (en alemán). Grupo de noticias : de.comp.os.msdos. Archivado desde el original el 2017-09-09 . Consultado el 2017-07-02 .
  14. ^ Paul, Matthias R. (24 de febrero de 2002). «¿Información de 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 utiliza nuestra eliminación dinámica de código muerto para optimizar su imagen de memoria para el entorno de destino en el momento de la carga, me gustaría añadir soporte especial a FreeKEYB para GEOS que se pueda controlar mediante una opción de línea de comandos, de modo que el código adicional solo se cargue cuando también se utiliza GEOS. […]
  15. ^ Paul, Matthias R. (15 de marzo de 2002). "¿Capa de teclado AltGr bajo 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 a FreeKEYB, nuestro controlador de teclado DOS muy avanzado, ¿mejoraría la usabilidad bajo GEOS? […] Debido a nuestra nueva y sofisticada tecnología de eliminación dinámica de código muerto , que elimina a nivel de byte cualquier fragmento de código no utilizado en un controlador, usuario o configuración del sistema y entorno de hardware en particular 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 (huella de memoria, etc.) como en los controladores DOS codificados tradicionalmente. […]
  16. ^ Thammanur, Sathyanarayan (31 de enero de 2001). Un marco de trabajo de optimización de código y asignación de registros justo a tiempo para sistemas integrados (tesis de maestría). Universidad de Cincinnati , Ingeniería: Ingeniería informática. ucin982089462.[2] Archivado el 28 de julio de 2019 en Wayback Machine. [3] Archivado el 28 de julio de 2019 en Wayback Machine.
  17. ^ Kubice, Jan (17 de octubre de 2024). "Eliminación dinámica de código muerto: optimización para la flexibilidad".
  18. ^ ab Conway, Andrew (1995-12-04). «Estructuras de datos cíclicas». Grupo de noticias : comp.lang.functional. Archivado desde el original el 2017-09-09 . Consultado el 2017-07-03 . […] La evaluación diferida 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 sólo conceptualmente y con un enfoque en la evaluación perezosa en lenguajes funcionales ).
  19. ^ Butts, J. Adam; Sohi, Guri (octubre de 2002). "Dynamic Dead-Instruction Detection and Elimination" (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 .
  20. ^ Johng, Yessong; Danielsson, Per; Ehnsiö, Per; Hermansson, Mats; Jolanki, Mika; Moore, Scott; Strander, Lars; Wettergren, Lars (8 de noviembre de 2002). "Capítulo 5. Descripción general de Java e implementación de iSeries - 5.1.1. Componentes varios". Intentia Movex Java en el servidor IBM iSeries - Guía de implementación - Descripció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) del original el 8 de octubre de 2013. Consultado el 20 de abril de 2019 .[4]
  21. ^ Polito, Guillermo (2015). "Soporte de virtualización para la especialización y extensión del tiempo de ejecución de aplicaciones - Lenguajes de programación" (PDF) . Universite des Sciences et Technologies de Lille . págs. 111–124. HAL Id: tel-01251173. Archivado (PDF) desde el original el 23 de junio de 2017 . Consultado el 23 de junio de 2017 .

Lectura adicional

Enlaces externos