Hispanopedia Wiki
Articulo de referencia

eliminación de código muerto

En la teoría de compiladores , la eliminación de código muerto ( DCE , eliminación de código muerto , eliminación de código muerto o eliminación de código muerto ) es una optimi...

Hispanopedia WikiContenido en espanolLectura gratuita

En la teoría de compiladores , la eliminación de código muerto ( DCE , eliminación de código muerto , eliminación de código muerto o eliminación de código muerto ) es una optimización del compilador para eliminar 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 la cantidad 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 inaccesible ) y código que solo afecta a variables muertas (escritas, pero nunca leídas de nuevo), es decir, irrelevante 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 sencillo del uso de los valores mostraría que el valor 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á muerta y un optimizador puede recuperar su espacio de almacenamiento y eliminar su inicialización.

Además, debido a que la primera instrucción return 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 puede eliminarse. Si el procedimiento tuviera un flujo de control más complejo , como una etiqueta después de la instrucción return y un gotoen otra parte del procedimiento, entonces podría existir una ruta de ejecución factible a la asignación a b.

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

La mayoría de los compiladores avanzados ofrecen 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 podría no reservar espacio para variables no utilizadas. Un nivel aún más alto podría identificar las instrucciones o funciones que no tienen ninguna utilidad 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.

// establecer DEBUG_MODE en falso constexpr bool DEBUG_MODE = falso ;int main ( void ) { int a = 5 ; int b = 6 ; int c ; c = a * ( b / 2 ); if ( DEBUG_MODE ) { printf ( "%d \n " , c ); } return c ; }

Dado que la constante DEBUG_MODEsiempre se evaluará como falsa (por estar definida de esa manera), el código dentro de la instrucción if nunca se ejecutará, y la eliminación de 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; usar un optimizador con eliminación de código muerto elimina la necesidad de usar un preprocesador para realizar la misma tarea.

En la práctica, gran parte del código muerto que encuentra un optimizador se genera mediante otras transformaciones dentro del propio optimizador. Por ejemplo, las técnicas clásicas para la reducción de la complejidad de los operadores insertan nuevos cálculos en el código y hacen que los cálculos más antiguos y costosos se vuelvan innecesarios. [ 2 ] La posterior eliminación de código muerto elimina esos cálculos y completa el efecto (sin complicar el algoritmo de reducción de complejidad).

Históricamente, la eliminación de código muerto se realizaba utilizando información derivada del análisis de flujo de datos . [ 3 ] Un algoritmo basado en la forma estática de asignación única (SSA) aparece en el artículo original de la revista sobre la forma 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 ]

Tiempo de eliminación

Tiempo de compilación

En el ejemplo anterior, eliminamos el código muerto en tiempo de compilación . Esto solo permite eliminar el código que es incondicionalmente muerto y que el optimizador puede demostrar que lo es. La presencia de límites de unidad de compilación (CU) dificulta la determinación de la muerte del código por parte del optimizador.

Consideremos, por ejemplo, una biblioteca estática de Unix ( *.a) que contiene varios archivos objeto ( *.o). En tiempo de enlace, el enlazador ld examina los símbolos referenciados por otras partes del código y decide incluir solo los archivos objeto necesarios : aquellos que contienen los símbolos referenciados, tanto por el código original como por los archivos objeto incorporados para satisfacer las necesidades del archivo objeto original. Esto constituye una versión muy general de la eliminación de código muerto.

Los archivos objeto constan de secciones relativamente independientes que pueden referenciarse entre sí. Cuando un archivo objeto se divide en más secciones, por ejemplo, con cada función y/o variable en su propia sección ( -ffunction-sections -fdata-sections), y si se le indica al enlazador que analice las interdependencias con una granularidad a nivel de sección ( --gc-sections), se puede lograr una forma más completa de DCE en tiempo de enlace. ( -fdata-sectionspuede aumentar de forma contraproducente el tamaño del binario al crear más entradas de reubicación). [ 6 ]

El método de referencia para la optimización dinámica de código (DCE) en tiempo de enlace consiste en convertir el tiempo de enlace en otro tiempo de compilación, es decir, la optimización en tiempo de enlace . En esta configuración, los archivos objeto contienen representaciones intermedias que el compilador utiliza en lugar de (o además de) el código máquina . De esta forma, el optimizador ya no se ve limitado por los límites de las unidades de compilación (CU), puesto que tiene acceso a todo el programa, lo que le permite demostrar muchas más propiedades del código que pueden utilizarse para la optimización. Esto conlleva la desventaja de tiempos de compilación más largos para procesar una representación tan grande del programa.

Dinámica

En la práctica, también es común que las secciones de código representen código muerto o inaccesible solo bajo ciertas condiciones , que pueden no ser conocidas en el momento de la compilación o el ensamblaje. Dichas condiciones pueden ser impuestas por diferentes entornos de tiempo 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 muerto condicional para los otros casos. [ 7 ] [ 8 ] 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, lo que hace que las porciones de código no utilizadas sean inútiles en un escenario particular. [ 7 ] [ 8 ] Si bien el software modular puede desarrollarse para cargar bibliotecas dinámicamente solo bajo demanda, en la mayoría de los casos, no es posible cargar solo las rutinas relevantes de una biblioteca particular, e incluso si esto fuera compatible, una rutina aún puede incluir secciones de código que pueden considerarse código muerto en un escenario dado, pero que no se pudieron descartar en tiempo de 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 tiempo de carga o ejecución se denominan eliminación dinámica de código muerto [ 9 ] [ 10 ] [ 11 ] o eliminación dinámica de instrucciones muertas . [ 12 ]

La mayoría de los lenguajes de programación, compiladores y sistemas operativos ofrecen poco o ningún soporte más allá de 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 raro en combinación con lenguajes compilados con anticipación o escritos en lenguaje ensamblador . [ 13 ] [ 14 ] [ 15 ] Sin embargo, las implementaciones de lenguajes que realizan compilación justo a tiempo pueden optimizar dinámicamente la eliminación de código muerto. [ 11 ] [ 16 ] [ 17 ]

Aunque con un enfoque bastante diferente, a veces también se utilizan métodos 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. “JavaScript Dead Code Identification, Elimination, and Empirical Assessment.” IEEE transactions on software engineering 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). Computación eficiente de la forma de asignación única estática y el grafo de dependencia del programa . ACM TOPLAS 13(4).
  5. ↑ Cooper, Keith D. ; Torczon, Linda (2003) [2002-01-01]. Ingeniería de un compilador . Morgan Kaufmann . págs. 498 y ss. ISBN  978-1-55860698-2.
  6. ↑ "Consulta sobre las opciones -ffunction-section y -fdata-sections de gcc" . Stack Overflow .
  7. 1 2 Paul, Matthias R. (2002-04-03) [2001-06-18]. " [ fd-dev ] Ctrl+Alt+Del" . freedos-dev . Recuperado el 2017-09-09 . [...] cualquiera de las [...] opciones puede excluirse "permanentemente" en el momento de la instalación (también ahorrará memoria para los extractos de código correspondientes debido a nuestra Eliminación Dinámica de Código Muerto ), o puede deshabilitarse o habilitarse 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 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 la caché de disco correspondiente también está cargada o FreeKEYB recibió instrucciones de los interruptores de la línea de comandos para cargar el soporte correspondiente.{{cite web}}: CS1 maint: servicio de archivado obsoleto ( enlace )
  8. 1 2 Paul, Matthias R. (2002-04-06). " [ fd-dev ] Ctrl+Alt+Del" . freedos-dev . Recuperado el 27-04-2019 . [...] FreeKEYB crea la imagen de tiempo de ejecución del controlador en el momento de la inicialización, dependiendo del tipo de máquina en la que se carga, el tipo de teclado, distribución, país y página de códigos utilizados, el tipo de ratón y adaptador(es) de vídeo instalados, los demás 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 interruptores y opciones de línea de comandos admitidos [...] (alrededor de cincuenta interruptores [...] con múltiples configuraciones posibles), hay una gran cantidad de combinaciones de características con dependencias incontables [...] que dan como resultado [...] 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 corregir 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 admitir una característica específica […] se utilizan herramientas especiales para analizar el código […] y crear […] tablas de corrección […] automatizado […] usando definiciones condicionales […] para declarar los distintos casos […] no solo opcional 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 […] estas condicionales, construir y reubicar dinámicamente la imagen de tiempo de ejecución, corregir todas las referencias entre estas pequeñas, cambiantes y móviles partes binarias […] aún permitiendo usar el pequeño estilo .COM/.SYS […] modelo […] se realiza en tiempo de inicialización […] API para importar y exportar estructuras de objetos entre FreeKEYB y la llamada aplicación […] para redimensionarlas y moverlas internamente de forma transparente […] en tiempo de ejecución […]{{cite web}}: CS1 maint: servicio de archivado obsoleto ( enlace )
  9. ↑ 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 embebidos (tesis de maestría). Universidad de Cincinnati , Ingeniería: Ingeniería Informática. ucin982089462.Archivado el 28 de julio de 2019 en Wayback Machine.Archivado el 28 de julio de 2019 en Wayback Machine.
  10. ↑ Kubice, Jan (17 de octubre de 2024). "Eliminación dinámica de código muerto: optimización para la flexibilidad" .
  11. 1 2 Conway, Andrew (1995-12-04). "Estructuras de datos cíclicas" . Grupo de noticias : comp.lang.functional . Recuperado el 2017-07-03 . […] La evaluación perezosa es básicamente la eliminación dinámica de código muerto . […] {{cite newsgroup}}: CS1 maint: servicio de archivado obsoleto ( enlace ) (Nota: 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 ).
  12. ↑ 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 . Recuperado el 23 de junio de 2017 .{{cite web}}: CS1 maint: servicio de archivado obsoleto ( enlace )
  13. ↑ Paul, Matthias R.; Frinke, Axel C. (13 de octubre de 1997) [publicado por primera vez en 1991], FreeKEYB - Controlador mejorado de teclado y consola para DOS (Manual del usuario) ( ed. v6.5) (NB. FreeKEYB es un sucesor de K3PLUS basado en Unicode y configurable dinámicamente, que admite la mayoría de diseños de teclado , páginas de códigos y códigos de país . Utilizando un ensamblador de macros comercial , así como un marco de herramientas de análisis de preprocesamiento y posprocesamiento automático para generar metadatos de dependencia y transformación de código que se incrustan en el archivo ejecutable junto con el código binario y un cargador autodesechable, relajado y reubicable , el controlador implementa técnicas de eliminación y reubicación dinámicas de código muerto a nivel de byte en tiempo de carga , así como código automodificable y reconfigurabilidad en tiempo de ejecución para minimizar su huella de memoria hasta casi la forma canónica dependiendo del hardware subyacente, el sistema operativo y la configuración del controlador, así como del 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 para los usuarios, que trabajan con un único archivo ejecutable como lo harían con un controlador convencional. K3PLUS fue un controlador de teclado extendido para DOS ampliamente distribuido en En aquel entonces, Alemania contaba con adaptaciones para algunos otros idiomas europeos. Si bien ya admitía un subconjunto de funciones, no implementaba la eliminación dinámica de código muerto.
  14. ↑ Paul, Matthias R.; Frinke, Axel C. (16 de enero de 2006), FreeKEYB - Controlador avanzado internacional de teclado y consola DOS (Manual de usuario) ( edición preliminar v7) 
  15. ^ Pablo, Matías R. (10 de abril de 2001). " [ ANN ] Lanzamiento de FreeDOS beta 6" (en alemán). Grupo de noticias : de.comp.os.msdos . 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 La función FreeKEYB no está disponible). […] {{cite newsgroup}}: CS1 maint: servicio de archivado obsoleto ( enlace ) (Nota: Esta representa la primera implementación conocida de eliminación dinámica de código muerto a nivel de byte para software ensamblado o compilado con anticipación ).
  16. ↑ Johng, Yessong; Danielsson, Per; Ehnsiö, Per; Hermansson, Mats; Jolanki, Mika; Moore, Scott; Strander, Lars; Wettergren, Lars (2002-11-08). "Capítulo 5. Descripción general de Java e implementación en 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 08-10-2013 . Recuperado el 20-04-2019 .
  17. ↑ 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) . Université des Sciences et Technologies de Lille . pp. 111–124 . HAL Id: tel-01251173. Archivado (PDF) del original el 23-06-2017 . Recuperado el 23-06-2017 . 

Lecturas adicionales

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