La optimización de compiladores busca reducir el trabajo computacional en tiempo de ejecución. Una de las formas más fundamentales de lograr esto es identificando y eliminando cálculos redundantes. Value Numbering (VN) aborda este problema asignando un identificador único a cada valor computado, permitiendo que el compilador reconozca cuándo dos expresiones, aunque textualmente diferentes o separadas por flujo de control, producirán el mismo resultado. Esto se vuelve particularmente potente en la forma de Asignación Estática Única (SSA), donde cada variable es asignada una sola vez, simplificando el análisis de dependencias de datos.
La relevancia de VN se ha incrementado con la complejidad de los lenguajes modernos y las arquitecturas de CPU, donde la reducción de instrucciones y el mejor uso de la caché son críticos para el rendimiento. En entornos de JIT (Just-In-Time) para lenguajes dinámicos, donde las optimizaciones se aplican en tiempo de ejecución, VN es crucial para limpiar el código generado después de desvirtualizaciones y especializaciones, que a menudo introducen redundancias. La capacidad de un compilador para razonar sobre la equivalencia de valores es un pilar para optimizaciones posteriores como la propagación de copias y la eliminación de código muerto.
Arquitectura del Sistema
La implementación de Value Numbering se basa en la representación intermedia (IR) del compilador, típicamente en forma SSA. El proceso se divide en Value Numbering Local (LVN) y Global (GVN).
LVN opera dentro de un bloque básico (basic block) de código. Mantiene un ValueMap (generalmente un hash map) que asocia un 'número de valor' (o la instrucción original que lo produjo) con el hash de cada instrucción pura. Al procesar una instrucción, se calcula su hash. Si el hash ya existe en el ValueMap y la instrucción es valueEqual a la almacenada, la instrucción actual se reemplaza por una referencia a la instrucción previamente computada (una Assign o Identity instruction). Este reemplazo no es una reescritura textual, sino una modificación del grafo IR, redirigiendo los usos de la instrucción redundante al resultado ya existente. La función valueNumber() de una instrucción genera un hash basado en su opcode y los System.identityHashCode de sus operandos, mientras que valueEqual() realiza una comparación profunda. Las instrucciones 'impuras' (ej. LoadField, printf) optan por no participar en VN directamente, ya que su resultado puede depender del estado externo o tener efectos secundarios.
GVN extiende LVN a toda la función, manejando el flujo de control. Requiere un recorrido topológico de los bloques básicos, generalmente en Reverse Post-Order (RPO). La clave para GVN es el concepto de dominancia: un bloque A domina a un bloque B si todo camino desde el punto de entrada de la función hasta B debe pasar por A. Para GVN, se utiliza un ValueMap por bloque, inicializado con el ValueMap de su dominador inmediato. Esto asegura que solo los valores garantizados como computados en todos los caminos de ejecución previos sean considerados para reutilización. La implementación de Maxine VM, por ejemplo, utiliza un HashMap<BlockBegin, ValueMap> para almacenar los mapas de valores de cada bloque y un InstructionSubstituter para aplicar los reemplazos. Las phi-functions en SSA requieren un tratamiento especial en bucles, ya que sus entradas pueden no tener un número de valor asignado si provienen de un 'back edge'.
Flujo de Value Numbering Local (LVN)
- 1 Inicializar ValueMap Crea un mapa vacío para el bloque actual.
- 2 Iterar Instrucciones Procesa cada instrucción en el bloque de arriba a abajo.
- 3 Calcular Value Number Genera un hash (valueNumber) para la instrucción actual.
- 4 Buscar en ValueMap Verifica si el hash ya existe en el mapa.
- 5 Instrucción Existente Si existe y es valueEqual, reemplaza la instrucción actual con la existente.
- 6 Instrucción Nueva Si no existe o no es valueEqual, añade la instrucción al ValueMap.
Flujo de Value Numbering Global (GVN) con Dominadores
- 1 Inicializar ValueMaps Crea un mapa de ValueMaps, uno por bloque, y un substitutor.
- 2 Recorrer Bloques (RPO) Itera los bloques básicos de la función en Reverse Post-Order.
- 3 Obtener Dominador Para cada bloque, identifica su dominador inmediato.
- 4 Heredar ValueMap Crea un ValueMap para el bloque actual, copiando el de su dominador.
- 5 Aplicar LVN Ejecuta Value Numbering Local en el bloque actual usando el ValueMap heredado.
- 6 Almacenar ValueMap Guarda el ValueMap actualizado del bloque para sus sucesores.
- 7 Finalizar Sustituciones Una vez procesados todos los bloques, aplica las sustituciones pendientes.
| Capa | Tecnología | Justificación |
|---|---|---|
| data-processing | SSA (Static Single Assignment) | Representación intermedia del programa que simplifica el análisis de dependencias de valores, haciendo explícitas las asignaciones únicas y facilitando la identificación de equivalencias. |
| data-processing | Control Flow Graph (CFG) | Estructura de datos que representa todos los caminos posibles que puede tomar la ejecución de un programa, esencial para el análisis de flujo de datos global y la determinación de dominadores. |
| data-processing | HashMap | Utilizado como `ValueMap` para almacenar y buscar instrucciones por su 'value number' (hash), permitiendo la identificación eficiente de expresiones equivalentes. vs Balanced Trees, Tries |
| data-processing | Union-Find | Estructura de datos para mantener conjuntos disjuntos, utilizada implícitamente o explícitamente para la propagación de copias y la gestión de equivalencias de valores tras las sustituciones. |
public abstract class Op2 extends Instruction {
public final int opcode;
Value x;
Value y;
@Override
public int valueNumber() {
return 0x20000000 | (opcode + 7 * System.identityHashCode(x) + 11 * System.identityHashCode(y));
}
@Override
public boolean valueEqual(Instruction i) {
if (i instanceof Op2) {
Op2 o = (Op2) i;
return opcode == o.opcode && x == o.x && y == o.y;
}
return false;
}
}public class GlobalValueNumberer {
final HashMap<BlockBegin, ValueMap> valueMaps;
final InstructionSubstituter subst;
ValueMap currentMap;
public GlobalValueNumberer(IR ir) {
this.subst = new InstructionSubstituter(ir);
List<BlockBegin> blocks = ir.linearScanOrder(); // reverse post-order
valueMaps = new HashMap<BlockBegin, ValueMap>(blocks.size());
optimize(blocks);
subst.finish();
}
void optimize(List<BlockBegin> blocks) {
BlockBegin startBlock = blocks.get(0);
valueMaps.put(startBlock, new ValueMap());
for (int i = 1; i < blocks.size(); i++) {
BlockBegin block = blocks.get(i);
BlockBegin dominator = block.dominator();
currentMap = new ValueMap(valueMaps.get(dominator)); // inherit from dominator
// << INSERT LOCAL VALUE NUMBERING HERE >>
valueMaps.put(block, currentMap);
}
}
}Fundamentos Teóricos
El concepto de Value Numbering tiene raíces profundas en la teoría de compiladores. Aunque el artículo se centra en la implementación práctica, la base teórica se remonta a trabajos pioneros en optimización de flujo de datos. La idea de identificar expresiones equivalentes es un componente clave del análisis de 'available expressions', un problema clásico de análisis de flujo de datos hacia adelante. El paper de Briggs sobre GVN (Briggs, Cooper, Kennedy, Torczon, 1998) es una referencia fundamental que detalla algoritmos y complejidades.
La dependencia de GVN en las relaciones de dominancia se basa en el trabajo de Lengauer y Tarjan (1979) sobre la computación eficiente de árboles de dominadores. La forma SSA en sí misma, popularizada por Alpern, Wegman y Zadeck (1988), simplifica enormemente el análisis de flujo de datos al hacer explícitas las dependencias de valor, lo que facilita la aplicación de VN. La conexión con hash-consing (compartir estructuras de datos idénticas en memoria usando hashing) es directa: el ValueMap actúa como un mecanismo de hash-consing para las instrucciones del IR, garantizando que solo una instancia de un valor computado exista en el grafo de valores. Esto reduce no solo el cómputo, sino también el uso de memoria para el IR.