Numeración de valores

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 .

La numeración de valores globales (GVN) es una optimización del compilador basada en la representación intermedia de la forma de asignación única estática (SSA). A veces ayuda a eliminar código redundante que la eliminación de subexpresiones comunes (CSE) no elimina. Sin embargo, al mismo tiempo, la CSE puede eliminar código que la GVN no elimina, por lo que ambas se encuentran a menudo en compiladores modernos. La numeración de valores globales se diferencia de la numeración de valores locales en que las asignaciones de valor-número también se mantienen en los límites de bloques básicos y se utilizan algoritmos diferentes para calcular las asignaciones.

La numeración de valores globales funciona asignando un número de valor a las variables y expresiones. El mismo número de valor se asigna a aquellas variables y expresiones que probablemente sean equivalentes. Por ejemplo, en el siguiente código:

en := 3
x := 3
y := x + 4
z := w + 4

Una buena rutina GVN asignaría el mismo número de valor a wy xy el mismo número de valor a yy z. Por ejemplo, el mapa constituiría una asignación óptima de valor-número para este bloque. Con esta información, el fragmento de código anterior se puede transformar de forma segura en: ${\displaystyle \left\{{w}\mapsto 1,{x}\mapsto 1,{y}\mapsto 2,{z}\mapsto 2\right\}}$

en := 3
x := w
y := w + 4
z := y

Dependiendo del código que sigue a este fragmento, la propagación de copias puede eliminar las asignaciones a xy a z.

La razón por la que GVN a veces es más potente que CSE se debe a que CSE compara expresiones léxicamente idénticas, mientras que GVN intenta determinar una equivalencia subyacente. Por ejemplo, en el código:

a := c × d
y := c
f := e × d

Sin la propagación de copias, CSE no eliminaría el recálculo asignado a f, pero incluso un algoritmo GVN pobre debería descubrir y eliminar esta redundancia.

En los IR y los idiomas de origen donde es posible volver a enlazar (asignar a la misma variable más de una vez), se requiere el formato SSA para realizar GVN de modo que no se creen asignaciones falsas. ${\displaystyle \left\{{\text{nombre de la variable}}\mapsto {\text{número del valor}}\right\}}$

La numeración de valores locales (LVN) es una optimización del compilador que tiene como objetivo encontrar múltiples instancias de expresiones equivalentes (es decir, expresiones que arrojan el mismo resultado) y reemplazarlas con la primera ocurrencia. LVN es una optimización local, lo que significa que a diferencia de la numeración de valores globales , 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. Luego se buscan las instrucciones posteriores y, en caso de que ya se haya registrado una instrucción idéntica, se reemplazan con el resultado de la instrucción anterior. Por ejemplo:

a ← 4 a está etiquetado como #1
b ← 5 b está etiquetado como #2
c ← a + bc (#1 + #2) está etiquetado como #3
d ← 5 d está etiquetado como #2, lo mismo que b
e ← a + de, siendo '#1 + #2' está etiquetado como #3

Al asignar números a las instrucciones, la comparación de duplicados se convierte en simples comparaciones de números enteros. En este ejemplo en particular, ca y ese les asigna el mismo número (#3), lo que indica al compilador que cualquier referencia a epuede simplemente reemplazarse por una a c.

Una implementación ingenua podría intentar realizar la optimización utilizando directamente los nombres de las variables en lugar de 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 #1
b ← 2 b está etiquetado como #2
c ← a + bc está etiquetado como #3
b ← 3
d ← a + bd está etiquetado incorrectamente como #3

En este escenario, dse le asigna incorrectamente el número 3 porque los argumentos coinciden con los de c. Sin embargo, esto es incorrecto porque bha cambiado el valor de 2 a 3, lo que hace que los resultados reales sean diferentes. El uso de la representación SSA resuelve esta disparidad.

Una implementación simple también podría no ser capaz de capturar todas las expresiones equivalentes, incluso cuando solo difieren en el orden de sus operandos. En el siguiente ejemplo, ay bpodrían tener asignado el mismo número:

un ← 1 + 2
b ← 2 + 1

Este problema se puede resolver fácilmente asignando el mismo número a ambos casos (es decir, a + by b + ase registran con el mismo número) o bien ordenando los operandos antes de buscar equivalentes. ^[1]

Los optimizadores de numeración de valores locales también pueden tener en cuenta las identidades matemáticas. Suponiendo que aes un entero , a todas las siguientes expresiones se les puede asignar el mismo valor: ^[2]

b ← a + 0
c ← a * 1
d ← mín(a, MÁXIMO_INT)
e ← máx(a, a)
f ← ​​a & 0xFF..FF (asumiendo que '&' denota AND bit a bit )

• Eliminación parcial de redundancia
• Optimización del compilador
• Eliminación de subexpresiones comunes

• Kildall, Gary Arlen (1973). "Un enfoque unificado para la optimización global de programas". Actas del 1.er simposio anual ACM SIGACT-SIGPLAN sobre Principios de lenguajes de programación - POPL '73 . pp.  194– 206. doi :10.1145/512927.512945. hdl :10945/42162. ISBN 9781450373494. S2CID  10219496 . Consultado el 20 de noviembre de 2006 .[1]
• Alpern, Bowen, Wegman, Mark N. y Zadeck, F. Kenneth. "Detección de igualdad de variables en programas", Acta de la conferencia del decimoquinto simposio anual de la 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 redundancia basada en el valor". Informe técnico 96-308, Departamento de Ciencias Informáticas, Universidad Rice, 1996. (Tesis doctoral del autor)
• Muchnick, Steven Stanley (1997). Diseño e implementación de compiladores avanzados . Morgan Kaufmann Publishers . ISBN 978-1-55860-320-2.
• Briggs, P.; Cooper, Keith D .; Simpson, L. Taylor (1997). "Numeración de valores". Software-Práctica y experiencia . 27 (6): 701– 724.