Eliminando código muerto

En la teoría del compilador , la eliminación de código inactivo ( DCE ) es una optimización que elimina el código inactivo .  El código muerto (también código inútil ) es un código cuya ejecución no afecta la salida del programa, todos los resultados de calcular dicho código son variables muertas , es decir, variables cuyos valores no se utilizan más adelante en el programa [1] [2] .

En relación con la ambigüedad existente del término código muerto [3] [4] , es importante tener en cuenta que la optimización de eliminación de código muerto no se ocupa de la eliminación de código inalcanzable . El recolector de elementos no utilizados [5] u otras optimizaciones, como la eliminación del código inalcanzable [2] , pueden manejar la localización y eliminación del código inalcanzable .

Eliminar código inútil puede acelerar el programa al reducir la cantidad de operaciones realizadas en él y reducir el tamaño del programa o la representación intermedia .

Ejemplos

Considere el siguiente código C :

int foo ( vacío ) { int a = 24 ; intb ; _ b = un + 3 ; /* código inútil */ devuelve un << 2 ; }

En este ejemplo, la operación de suma b = a + 3es código inactivo, ya que la variable bno se usa en cálculos posteriores y está inactiva desde este punto hasta el final del procedimiento. Después de eliminar esta instrucción, obtenemos:

int foo ( vacío ) { int a = 24 ; intb ; _ /* Variable muerta */ devuelve un << 2 ; }

Después de eliminar la operación de suma, la variable bqueda muerta en todo el procedimiento. Dado que se declara localmente , se puede eliminar por completo del programa:

int foo ( vacío ) { int a = 24 ; devuelve un << 2 ; }

Aunque la evaluación se lleva a cabo dentro de una función, su resultado se escribe en una variable que se encuentra únicamente en el ámbito de esa función; y dado que la función devuelve incondicionalmente el número 96, se puede simplificar optimizando la propagación constante para que su cuerpo consista únicamente en la operación return 96. Y luego el compilador puede reemplazar todas las llamadas a esa función con el valor devuelto.

Algoritmos

El algoritmo clásico DCE ( "Dead" ) funciona en la representación SSA y consta de dos omisiones: la primera omisión ( "Mark" ) marca (marca) todas las operaciones obviamente activas (operaciones de salida de procedimiento, operaciones de entrada-salida que cambian variables globales) ; el segundo barrido ( "Sweep" ) comienza con operaciones en vivo y sube por las definiciones de argumentos, marcando todas las operaciones en su camino como en vivo, terminando con aquellas operaciones que no tienen predecesores en formato SSA [6] . La máxima complejidad computacional de tal algoritmo depende del tamaño del programa como O(n 2 ) [7] .

Es posible que DCE no realice ningún análisis independiente, sino que simplemente utilice los resultados del análisis de variables activas [8] , pero la complejidad computacional de dicho análisis es O(n 3 ) en el peor de los casos [7] . Existen algoritmos específicos que se ocupan de eliminar nodos vacíos en un gráfico CFG , combinar varios bloques básicos en uno, etc. Para dicho análisis, se necesita un gráfico de flujo de control construido [9] .

El algoritmo "muerto" se publicó por primera vez en el artículo "Formulario de asignación única estática y el gráfico de dependencia del programa" en ACM TOPLAS en 1991 [10] . El algoritmo " Clean " que funciona con un gráfico CFG fue desarrollado e implementado por Rob Schiller en 1992 [11] .

Aplicación

La eliminación de código muerto se puede aplicar varias veces durante el proceso de compilación, ya que el código muerto está en el programa no solo porque está contenido en el código fuente, sino que otras transformaciones pueden hacer que el código quede muerto. Por ejemplo, las optimizaciones de propagación de copia y las optimizaciones de propagación constante a menudo convierten las instrucciones en código inútil [1] [12] . También debe eliminar el código muerto creado por otras transformaciones en el compilador [12] . Por ejemplo, el algoritmo clásico para reducir la fuerza de una operación reemplaza las operaciones intensivas en mano de obra por otras menos laboriosas, después de lo cual la eliminación del código muerto elimina las operaciones antiguas y completa la transformación (sin complicar el algoritmo para reducir la fuerza). ) [13] .

Datos interesantes

  • En noviembre de 2010, Microsoft lanzó una nueva versión de Internet Explorer 9 Platform Preview 7, que superó a todos los demás navegadores en la velocidad de interpretación de JavaScript en el punto de referencia SunSpider . En el blog oficial de Internet Explorer , el líder del proyecto, Dean J. Hachamovitch, afirmó que una de las innovaciones del lanzamiento es el uso de la optimización de eliminación de código muerto, por lo que se logró este resultado. Sin embargo, pronto se hizo evidente que los cambios menores en el código fuente de referencia causaron una caída significativa en el rendimiento de Internet Explorer 9, lo que no sucedió al probar Google Chrome u Opera . Como resultado, se acusó a los desarrolladores de Internet Explorer de "ajustar" el producto a un punto de referencia específico [14] [15] .

Véase también

Notas

  1. 1 2 Compiladores - principios, tecnologías, herramientas - S. 713, 714.
  2. 1 2 Ingeniería de un compilador - página 544.
  3. Detección y eliminación de código muerto . Aivosto. Consultado el 14 de julio de 2012. Archivado desde el original el 5 de agosto de 2012. ( mezclando los conceptos de códigos muertos e inalcanzables )
  4. Compiladores - principios, tecnologías, herramientas - S. 669 ( código inalcanzable ), 713 ( código muerto ).
  5. A. Yu. Drozdov, A. M. Stepanenkov. Paquetes de optimización gestionados. En Tecnología de la información y sistemas informáticos , 2004, No. 3 ( archivado el 4 de marzo de 2016 en Wayback Machine )
  6. Ingeniería de un compilador - págs. 544-546.
  7. 1 2 Ene Olaf Blech, Lars Gesellensetter, Sabine Glesner . Verificación formal de eliminación de código muerto en Isabelle/HOL. IEEE Computer Society Press , septiembre de 2005 ( texto archivado el 7 de marzo de 2016 en Wayback Machine ).
  8. Diseño e implementación avanzados del compilador - P. 443.
  9. Ingeniería de un compilador - págs. 547-550.
  10. Ron Cytron, Jeanne Ferrante, Barry Rosen y Ken Zadeck . Cálculo eficiente del formulario de asignación única estática y el gráfico de dependencia del programa. ACM TOPLAS 13(4), 1991 ( texto archivado el 24 de septiembre de 2011 en Wayback Machine ).
  11. Ingeniería de un compilador - S. 593.
  12. 1 2 Diseño e implementación de compiladores avanzados - S. 13, 327, 603.
  13. Frances Allen, John Cocke y Ken Kennedy . Reducción de la fuerza del operador. En Análisis de flujo de programas: teoría y aplicación , Muchnick y Jones, Prentice-Hall, 1981.
  14. Debate del navegador: ¿Microsoft hizo trampa? . The H. Consultado el 12 de junio de 2012. Archivado desde el original el 25 de junio de 2012.
  15. Mentiras, malditas mentiras y puntos de referencia: ¿IE9 está haciendo trampa en SunSpider? . Ars Technica. Consultado el 3 de diciembre de 2017. Archivado desde el original el 25 de junio de 2012.

Literatura

Enlaces