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 del formulario 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. Al mismo tiempo, sin embargo, CSE puede eliminar código que GVN no elimina, por lo que ambos se encuentran a menudo en los compiladores modernos. La numeración de valores globales se diferencia de la numeración de valores locales en que las asignaciones de números y valores también se aplican a través de los límites de los 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 probablemente sean equivalentes. Por ejemplo, en el siguiente código:
w := 3x := 3y := x + 4z := 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 un mapeo óptimo de valor-número 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 la copia puede eliminar las asignaciones a xy a z.
La razón por la que GVN es a veces más poderoso que CSE proviene del hecho de que CSE coincide con expresiones léxicas idénticas, mientras que GVN intenta determinar una equivalencia subyacente. Por ejemplo, en el código:
a := c×dmi := cf := mi × d
Sin propagación de copia, CSE no eliminaría el recálculo asignado a f, pero incluso un algoritmo GVN deficiente debería descubrir y eliminar esta redundancia.
En los IR y los idiomas de origen donde es posible volver a vincular (asignar a la misma variable más de una vez), se requiere el formulario SSA para realizar GVN para que no se creen asignaciones falsas.
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 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 valores globales , opera en un único 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 #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 simples comparaciones de números enteros. En este ejemplo particular, cy ese les asigna el mismo número (#3), lo que indica al compilador que cualquier referencia a epuede simplemente reemplazarse con unas 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 #1b ← 2 b está etiquetado como #2c ← a + bc está etiquetado como #3segundo ← 3d ← 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 difieran. El uso de la representación de la SSA resuelve esta disparidad.
Es posible que una implementación simple tampoco pueda capturar todas las expresiones equivalentes, incluso cuando solo difieren en el orden de sus operandos. En el siguiente ejemplo, aa y bse le podría asignar el mismo número:
un ← 1 + 2segundo ← 2 + 1
Este problema se puede resolver fácilmente asignando el mismo número a ambos casos (es decir, a + by b + aambos 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 identidades matemáticas. Suponiendo que aes un número entero , a todas las siguientes expresiones se les puede asignar el mismo valor: [2]
segundo ← un + 0c ← un * 1d ← mín(a, MAX_INT)mi ← máx(a, a)f ← a & 0xFF..FF (asumiendo que '&' denota AND bit a bit )
