La numeración de valores es una técnica para determinar cuándo dos cálculos en un programa son equivalentes y eliminar uno de ellos con una optimización que preserva la semántica.
Numeración de valor global
La numeración de valor global (GVN) es una optimización del compilador basada en la representación intermedia del formulario de asignación única estática (SSA). A veces ayuda a eliminar el código redundante que la eliminación de subexpresiones comunes (CSE) no hace. Sin embargo, al mismo tiempo, CSE puede eliminar código que GVN no hace, por lo que ambos se encuentran a menudo en compiladores modernos. La numeración de valor global es distinta de la numeración de valor local en que las asignaciones de valor-número también se mantienen a través de los límites de bloques básicos, y se utilizan diferentes algoritmos para calcular las asignaciones.
La numeración de valores globales funciona asignando un número de valor a variables y expresiones. Se asigna el mismo número de valor a aquellas variables y expresiones que sean demostrablemente equivalentes. Por ejemplo, en el siguiente código:
w: = 3x: = 3y: = x + 4z: = w + 4
una buena rutina de GVN asignaría el mismo número de valor a w
y x
, y el mismo número de valor a y
y z
. Por ejemplo, el mapaconstituiría un mapeo de valor-número óptimo para este bloque. Con esta información, el fragmento de código anterior se puede transformar de forma segura en:
w: = 3x: = wy: = w + 4z: = y
Dependiendo del código que sigue a este fragmento, la propagación de copias puede eliminar las asignaciones ay x
paraz
La razón por la que GVN a veces es más poderoso que CSE proviene del hecho de que CSE coincide con expresiones léxicamente idénticas mientras que GVN intenta determinar una equivalencia subyacente. Por ejemplo, en el código:
a: = c × de: = cf: = e × d
Sin propagación de copias, CSE no eliminaría el recálculo asignado f
, pero incluso un algoritmo GVN deficiente debería descubrir y eliminar esta redundancia.
Se requiere el formulario SSA para realizar GVN de modo que no se creen asignaciones falsas de {nombre de variable → nombre de valor}.
Numeración de valor local
La numeración de valor local (LVN) es una optimización del compilador que tiene como objetivo encontrar múltiples instancias de expresiones equivalentes (es decir, expresiones que producen el mismo resultado) y reemplazarlas con la primera aparición. LVN es una optimización local, lo que significa que, a diferencia de la numeración de valor global , opera en un solo bloque básico a la vez.
La numeración de valores locales funciona asignando un número único a cada operación y recordando estas asociaciones. A continuación, se buscan las instrucciones posteriores y, en caso de que ya se haya registrado una instrucción idéntica, se reemplaza con el resultado de la instrucción anterior. Por ejemplo:
a ← 4 a está etiquetado como # 1b ← 5 b está etiquetado como # 2c ← a + bc (# 1 + # 2) está etiquetado como # 3d ← 5 d está etiquetado como # 2, lo mismo que be ← a + de, siendo '# 1 + # 2' se etiqueta como # 3
Al asignar números a las instrucciones, la comparación de duplicados se convierte en comparaciones de enteros simples. En este ejemplo particular, a 'c' y 'e' se les asigna el mismo número (# 3), lo que indica al compilador que cualquier referencia a e puede ser simplemente reemplazada por unas a c.
Dificultades y extensiones
Una implementación ingenua podría intentar realizar la optimización utilizando directamente los nombres de las variables en lugar de los números. Sin embargo, este enfoque no funciona cuando los valores de las variables pueden cambiar. Considere el pseudocódigo :
a ← 1 a está etiquetado como # 1b ← 2 b está etiquetado como # 2c ← a + bc está etiquetado como # 3b ← 3d ← a + bd está etiquetado incorrectamente como # 3
En este escenario, a 'd' se le asigna incorrectamente el número 3 porque los argumentos coinciden con los de 'c'. Sin embargo, esto es incorrecto porque 'b' ha cambiado el valor de 2 a 3, lo que hace que los resultados reales sean diferentes.
Una implementación simple también podría ser incapaz de capturar todas las expresiones equivalentes, incluso cuando solo difieren por el orden de sus operandos. En el siguiente ejemplo, a 'a' y 'b' se les podría asignar el mismo número:
a ← 1 + 2b ← 2 + 1
Este problema se puede resolver fácilmente asignando el mismo número a ambos casos (es decir, "a + b" y "b + a" se registran con el mismo número) o clasificando los operandos antes de buscar equivalentes. [1]
Los optimizadores de numeración de valores locales también pueden conocer las identidades matemáticas. Suponiendo que 'a' es un número entero, a todas las siguientes expresiones se les puede asignar el mismo valor: [2]
b ← a + 0c ← a * 1d ← min (a, MAX_INT)e ← max (a, a)f ← a & 0xFF..FF (asumiendo que '&' denota la operación bit a bit )
Ver también
Referencias
- ^ Cooper, Keith D .; Torczon, Linda. "Terminología, principios e inquietudes (con ejemplos de numeración de valores locales)" . elsevier . Consultado el 15 de mayo de 2017 .
- ^ Cooper, Keith D .; Torczon, Linda. "Optimización local: numeración de valores" (PDF) . Universidad de Rice . Consultado el 15 de mayo de 2017 .
Otras lecturas
- Kildall, Gary Arlen (1973). "Un enfoque unificado para la optimización del programa global" . Actas del 1er Simposio Anual ACM SIGACT-SIGPLAN sobre Principios de Lenguajes de Programación . Popl '73: 194-206. doi : 10.1145 / 512927.512945 . hdl : 10945/42162 . Consultado el 20 de noviembre de 2006 . [1]
- Alpern, Bowen, Wegman, Mark N. y Zadeck, F. Kenneth. "Detectando la Igualdad de Variables en los Programas". Registro de la Conferencia del Decimoquinto Simposio Anual de ACM sobre Principios de Lenguajes de Programación ( POPL ), ACM Press, San Diego, CA, EE.UU., enero de 1988, páginas 1–11.
- L. Taylor Simpson, "Eliminación de la redundancia impulsada por el valor". Informe técnico 96-308, Departamento de Ciencias de la Computación, Universidad de Rice, 1996. (Tesis de doctorado del autor)
- Muchnick, Steven Stanley (1997). Diseño e implementación de compiladores avanzados . Editores Morgan Kaufmann . ISBN 978-1-55860-320-2.
- Briggs, P .; Cooper, Keith D .; Simpson, L. Taylor (1997). "Numeración de valores". Práctica y experiencia en software . 27 (6): 701–724.