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 mediante una optimización que preserve la semántica .

La numeración global de valores (GVN) es una optimización del compilador basada en la representación intermedia de asignación única estática (SSA). En ocasiones, ayuda a eliminar código redundante que la eliminación de subexpresiones comunes (CSE) no elimina. Sin embargo, al mismo tiempo, CSE puede eliminar código que GVN no elimina, por lo que ambas se encuentran frecuentemente en los compiladores modernos. La numeración global de valores se distingue de la numeración local de valores en que las asignaciones valor-número se mantienen incluso entre bloques básicos , y se utilizan algoritmos diferentes para calcular dichas asignaciones.

La numeración global de valores 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 son equivalentes. Por ejemplo, en el siguiente código:

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

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

w := 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 proviene del hecho de 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 e := c f := e × d

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

En IR y lenguajes fuente donde es posible la reasignación (asignación a la misma variable más de una vez), se requiere la forma SSA para realizar GVN de modo que se produzcan falsos${\displaystyle \left\{{\text{nombre de la variable}}\mapsto {\text{número de valor}}\right\}}$No se crean asignaciones.

La numeración de valores locales (LVN, por sus siglas en inglés) es una optimización del compilador que busca múltiples instancias de expresiones equivalentes (es decir, expresiones que producen el mismo resultado) y las reemplaza por la primera que aparece. LVN es una optimización local, lo que significa que, a diferencia de la numeración de valores globales, opera sobre 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. A continuación, se buscan las instrucciones subsiguientes 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 #1 b ← 5 b está etiquetado como #2 c ← a + bc (#1 + #2) está etiquetado como #3 d ← 5 d está etiquetado como #2, igual que b e ← a + de, siendo '#1 + #2' etiquetado como #3

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

• Eliminación de redundancia parcial
• Compilador optimizador
• 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 . págs. 194-206 . doi : 10.1145/512927.512945 . hdl : 10945/42162 . ISBN  9781450373494. S2CID 10219496 . Consultado el 20/11/2006 . 
• Alpern, Bowen, Wegman, Mark N. y Zadeck, F. Kenneth. "Detección de igualdad de variables en programas.", Actas 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 redundancias basada en el valor". Informe técnico 96-308, Departamento de Ciencias de la Computación, Universidad Rice, 1996. (Tesis doctoral del autor)
• Muchnick, Steven Stanley (1997). Diseño e implementación avanzados de compiladores . Morgan Kaufmann Publishers . ISBN 978-1-55860-320-2.
• Briggs, P.; Cooper, Keith D .; Simpson, L. Taylor (1997). "Numeración de valores". Software-Practice and Experience . 27 (6): 701– 724.