Generación de código y asignación de registros — las huellas que deja el compilador

Operativo · Actualizado el 16 de agosto de 2026

Este capítulo recorre la última fase del compilador: la que convierte la representación intermedia en instrucciones máquina. Para el ingeniero inverso tiene un interés particular, porque cada una de estas transformaciones deja una huella reconocible en el binario, y saber cuál la produjo es la mitad del trabajo de deshacerla.

23.1 Las fases del generador de código

En un compilador para lenguajes imperativos, el generador de código (code generator) abarca las transformaciones y optimizaciones que operan sobre una representación cercana al juego de instrucciones de la máquina, y produce ensamblador o código objeto reubicable.

Sus tareas principales son: bajar (lowering) la representación intermedia a las instrucciones de la máquina y a los convenios de llamada; disponer los objetos de datos en secciones; componer los marcos de pila; asignar los rangos de vida de las variables a registros arquitectónicos; planificar las instrucciones para explotar las características de la microarquitectura; y emitir el resultado.

La lista clásica, tal como la fija el Dragon Book de 1986, es:

selección de instrucciones y bajada de los convenios de llamada;
análisis de flujo de control —dominadores, bucles— y de flujo de datos —vivacidad—;
asignación de registros y construcción del marco de pila;
optimizaciones de mirilla (peephole).

Diez años después, Muchnick la amplía con desenrollado de bucles y replicación de bloques, planificación de instrucciones y software pipelining, y optimizaciones de saltos y alineamiento de bloques. Y en los compiladores actuales —Open64, GCC, LLVM— el generador de código incorpora además if-conversion con instrucciones de movimiento condicional o predicadas, modos de direccionamiento especializados, aprovechamiento de bucles por hardware y de pistas de predicción de saltos, reconocimiento de idiomas de aritmética de punto fijo y SIMD, optimizaciones de jerarquía de memoria como el precargado, y empaquetado de instrucciones VLIW.

Esta sofisticación es lo que motiva introducir la forma SSA en la representación a nivel de código máquina: la vivacidad, la if-conversion, las optimizaciones basadas en desenrollado y la explotación de modos de direccionamiento especiales se benefician significativamente de ella.

23.2 Vivacidad bajo SSA

El análisis de variables vivas del capítulo «6» se calcula por punto fijo. Bajo SSA con propiedad de dominancia puede hacerse mucho mejor, gracias a la propiedad estructural del capítulo «12»:

Formalización

Los rangos de vida son subárboles del árbol de dominadores

Bajo SSA con propiedad de dominancia, todos los usos de una variable están dominados por su definición. Por tanto todo el rango de vida está dominado por la definición, y como la dominancia induce un árbol, los rangos de vida tienen forma de árbol: pueden ramificarse hacia abajo por el árbol de dominadores, pero tienen una única raíz, el punto de definición.

De esa propiedad se siguen tres consecuencias operativas:

Consulta de vivacidad sin iteración. Se puede responder «¿está v viva en q?» sin calcular conjuntos de vivas, combinando una prueba de dominancia con alcanzabilidad. Sobre un CFG reducible, basta el bosque de anidamiento de bucles y la alcanzabilidad hacia adelante.
Cálculo de conjuntos de vivas sin punto fijo. Existen algoritmos que recorren el árbol de dominadores una vez, o que exploran los caminos desde cada uso hacia su definición, en lugar de iterar sobre el CFG.
Test de interferencia barato. Dos rangos de vida se intersecan si y sólo si uno contiene el punto de definición del otro, lo que se comprueba con dos consultas de dominancia.

Los grafos irreducibles complican los dos primeros puntos, pero existen variantes que los tratan. Es otra razón práctica para preocuparse por la irreducibilidad del capítulo «4».

23.3 Árbol de bucles y variables de inducción

Hay una propiedad de SSA menos conocida y muy útil: buena parte de la estructura del CFG puede recuperarse a partir del propio grafo SSA. Como las φ se colocan siguiendo reglas precisas —en los puntos de confluencia—, identificando patrones de definiciones y usos se puede exponer parte de la estructura del CFG, incluidas las componentes fuertemente conexas, es decir, los bucles reducibles.

Para que eso funcione hace falta añadir una pizca de información: la forma SSA cerrada respecto de bucles (loop-closed SSA), que introduce una variable extra al final de cada bucle por cada variable definida dentro y usada fuera. Es análoga a la función φ_exit de la GSA del capítulo «16».

Sobre esa base se construye el reconocimiento de variables de inducción (induction variable recognition), que detecta autorreferencias en el grafo SSA. Una variable de inducción básica aparece como

i2 <- phi(i1, i3)      // cabecera del bucle
...
i3 <- i2 + 1           // el ciclo i2 -> i3 -> i2 en el grafo SSA

es decir, como un ciclo en el grafo SSA que pasa por una φ de cabecera de bucle. Detectar el ciclo da el paso (stride); traducirlo a cadenas de recurrencias (chains of recurrences) da una forma cerrada que permite calcular el valor en la iteración k, el número de iteraciones y el valor al salir del bucle.

23.4 Selección de instrucciones e if-conversion

La selección de instrucciones (instruction selection) elige qué instrucciones máquina implementan cada operación de la IR. Sobre patrones de árbol se resuelve clásicamente por programación dinámica; sobre el grafo SSA, que no es un árbol sino un DAG, el problema se vuelve más difícil, y una formulación elegante lo plantea como un problema cuadrático booleano particionado (partitioned boolean quadratic problem, PBQP), que se resuelve con heurísticas eficaces en la práctica.

La if-conversion sustituye control por datos: convierte un if-then-else en una secuencia de instrucciones predicadas o en un movimiento condicional. Es una transformación rentable en procesadores con predicción de saltos costosa, y produce código sin saltos. Su interacción con SSA es la que motiva la forma Psi-SSA del capítulo «16»: al desaparecer la bifurcación, desaparece el punto de confluencia donde iba la φ, y hace falta la función ψ con predicados.

23.5 Asignación de registros: los dos enfoques clásicos

La asignación de registros aplica las variables del programa a posiciones físicas de memoria. Idealmente, tantas operaciones como sea posible deberían tomar sus operandos de registros del procesador sin cargarlos previamente de memoria; dada la latencia de la jerarquía de memoria, es una de las optimizaciones más importantes del compilador.

Como sólo hay un número pequeño de registros —típicamente entre 8 y 128—, no suele ser posible usar sólo registros, y la asignación tiene que decidir además qué variables expulsar a memoria y en qué puntos guardarlas y recargarlas: el spilling. Y tiene que eliminar las copias espurias que han insertado las fases anteriores —el coalescing, recuérdese la destrucción de SSA del capítulo «13»— y lidiar con las restricciones que impone la arquitectura.

Un asignador de registros debe responder a tres preguntas:

¿Hay registros suficientes para todas mis variables? (test de spill)
Si los hay, ¿qué registro asigno a cada variable? (asignación)
Si no los hay, ¿qué variables mando a memoria? (spilling)

Linear scan. Considera el procedimiento como un único bloque básico largo, de modo que los rangos de vida se aproximan por intervalos. Recorre el bloque de arriba abajo; al encontrar la definición de una variable comprueba si hay registros libres y, si no, expulsa la variable cuyo próximo uso esté más lejos; al llegar al final de un rango de vida libera el registro. Es muy rápido y su modelo tiene un test de spill exacto dentro del modelo, pero el modelo es muy impreciso: los procedimientos reales no son código lineal, y los rangos de vida quedan artificialmente alargados.

Coloreado de grafos. Representa las interferencias como un grafo de interferencia no dirigido: los nodos son las variables y hay arista entre dos si sus rangos de vida se intersecan. Asignar registros equivale entonces a colorear el grafo con a lo sumo R colores. Si se consigue, la coloración es una asignación válida; si no, se eligen algunos nodos —normalmente los de mayor grado— y se expulsan a memoria.

   codigo                          grafo de interferencia

   p <- ...                                p ---- a
   a <- ...                                | \   /|
   b <- ...                                |  \ / |
   if (...)                                |   X  |
      /        \                           |  / \ |
   x <- 12    x <- 42 + b                  | /   \|
   y <- b     y <- a                       x ---- b
      \        /                            \    /
   return x + y + p                          \  /
                                              y

Un ejemplo con un condicional, sus dos modelos y su grafo de interferencia.

En el ejemplo, linear scan decidiría que hacen falta 5 registros, porque marca a como viva a lo largo de toda la rama izquierda aunque allí no se use nunca. El asignador por coloreado construye el grafo, que contiene un 4-clique —a, b, p, x—, y por tanto necesita al menos 4 colores; una heurística lo colorea con 4 sin problema.

Y sin embargo, en cada punto del procedimiento hay como mucho tres variables vivas a la vez. Pero como x interfiere con b en la rama izquierda y con a en la derecha, es imposible usar sólo tres registros.

Comparación. Linear scan es más rápido; el coloreado da mejores resultados. Pero ambos tienen un test de spill inexacto: el primero por las interferencias artificiales, el segundo porque el coloreado k de grafos arbitrarios es NP-completo y hay que usar heurísticas. Y ambos exigen que cada variable ocupe exactamente un registro durante todo su rango de vida, lo que hace que ambos expulsen a memoria más variables de las estrictamente necesarias.

23.6 Maxlive y división de rangos de vida

El número de variables simultáneamente vivas en un punto es la presión de registros (register pressure) en ese punto, y su máximo sobre todos los puntos del procedimiento se llama Maxlive.

Maxlive es el mínimo número de registros necesario para una asignación sin spill. En el ejemplo anterior, Maxlive = 3. Para código lineal, Maxlive es además suficiente; pero en general un procedimiento puede necesitar más, como acabamos de ver.

Eso cambia si se permite la división de rangos de vida (live-range splitting): insertar una copia en algún punto, creando una versión nueva de la variable, de modo que su valor pueda residir en registros distintos en momentos distintos. En el ejemplo, dividiendo x en la rama derecha —definiendo x₀ y añadiendo x ← x₀ al final del bloque— el nodo x se parte en dos, x y x₀, que no interfieren entre sí e interfieren de forma distinta con las demás: ahora x puede compartir registro con a y x₀ con b. Con 3 registros basta, y se ha cambiado un spill —un almacenamiento y una carga— por un movimiento, que es un excelente negocio.

Formalización

El test de spill bajo SSA es exacto

Aquí es donde SSA cambia el problema. Por la propiedad de la «sección 23.2 · Vivacidad bajo SSA», bajo SSA con propiedad de dominancia los rangos de vida tienen forma de árbol: se ramifican hacia abajo por el árbol de dominadores pero tienen una única raíz. La situación del ejemplo —donde x e y tenían «dos raíces» por estar definidas dos veces— ya no puede ocurrir, porque las φ dividen sus rangos de vida automáticamente.

La consecuencia es un teorema notable: el grafo de interferencia de un programa en forma SSA estricta es cordal (chordal), y en los grafos cordales el número cromático coincide con el tamaño de la mayor clique y se calcula en tiempo lineal. Como la mayor clique es exactamente Maxlive, se obtiene:

El\ programa\ es\ coloreable\ con\ R\ registros\ ⟺ Maxlive ≤ R

Es decir, el test de spill se vuelve exacto y trivial, y además se desacopla de la asignación: primero se decide qué expulsar, mirando sólo Maxlive, y después se asigna, con la garantía de que la asignación no fallará. La asignación misma se hace con un simple recorrido del árbol de dominadores —un tree scan— sin necesidad de construir el grafo de interferencia.

El precio, ya señalado en el capítulo «12»: si se refina la noción de interferencia —dos variables con el mismo valor no interfieren— el grafo deja de ser cordal y se pierde el resultado.

23.7 Spilling, coalescing y destrucción de SSA

Con el test de spill exacto, la asignación de registros bajo SSA se descompone en tres fases claramente separadas:

Spilling. Reducir Maxlive por debajo de R en todo punto, insertando almacenamientos y recargas. Hay enfoques basados en grafo y basados en recorrido; obsérvese que cada recarga es una definición nueva de la variable, lo que rompe SSA y obliga a la reconstrucción incremental del capítulo «14».

Coloreado y coalescing. Asignar registros por recorrido del árbol de dominadores, y a la vez eliminar el máximo número de copias. El coalescing es el problema difícil: fusionar dos variables unidas por una copia elimina la copia pero puede volver el grafo no coloreable, así que se distingue entre coalescing conservador —sólo fusiona si se garantiza que la colorabilidad se mantiene— y agresivo —fusiona y arregla después—.

Destrucción de SSA a nivel máquina. El algoritmo del capítulo «13» —dividir aristas críticas e insertar copias paralelas— tropieza a este nivel con tres dificultades: hay aristas que no se pueden dividir, por restricciones arquitectónicas, fronteras de región o código de manejo de excepciones; el número de copias generadas es grande y hay que minimizarlo; y en compilación dinámica el tiempo y la memoria están limitados. Los algoritmos de destrucción a nivel máquina se evalúan, por tanto, según tres criterios: corrección, calidad del código y velocidad y huella de memoria.

23.8 Las huellas en el binario

En ingeniería inversa

Leer el binario como un registro de lo que hizo el compilador

Cada transformación de este capítulo deja una marca reconocible. Saber cuál permite reconstruir el fuente original con mucha más confianza que analizar el binario en abstracto.

Copias de destrucción de SSA. mov entre registros que no corresponden a ninguna asignación del fuente, agrupados al final de bloques que preceden a un punto de confluencia, y especialmente en bloques que sólo contienen mov seguidos de jmp. Esos bloques son las aristas críticas divididas de la «sección 23.7 · Spilling, coalescing y destrucción de SSA». Reconocerlos permite reconstruir dónde estaban las φ y, por tanto, qué versiones pertenecían a la misma variable del fuente.

Rangos de vida divididos. Una variable del fuente que aparece en ebx en una parte de la función y en esi en otra, con un mov esi, ebx en medio. Es división de rango de vida para evitar un spill, y el indicio de que la presión de registros era alta ahí. Un decompilador que no lo detecte mostrará dos variables locales donde había una.

Spill y reload. Escrituras y lecturas a posiciones del marco de pila que no corresponden a variables declaradas: se escriben una vez y se leen una vez, en puntos separados por una región de alta presión de registros. Distinguirlas de las variables locales reales es una de las heurísticas importantes de un decompilador; confundirlas produce pseudocódigo lleno de variables espurias.

If-conversion. cmov, setcc seguido de aritmética, o secuencias sin saltos que calculan las dos ramas. Deshacerlo —volver a introducir el condicional— produce pseudocódigo mucho más legible, y es lo que hacen las reglas de reconocimiento de patrones de Hex-Rays. Ojo: la if-conversion calcula ambas ramas, así que el pseudocódigo reconstruido debe conservar los efectos de las dos si alguna los tiene.

Variables de inducción. Un registro que se incrementa en una constante cada iteración y se usa como base de direcciones. Reconocerlo es lo que convierte *(int *)(a1 + 4*i) en a1[i], y lo que permite recuperar el número de iteraciones de un bucle. La técnica es la de la «sección 23.3 · Árbol de bucles y variables de inducción», aplicada al grafo SSA del binario.

Reducción de fuerza y desenrollado. Multiplicaciones convertidas en lea y desplazamientos; bucles con el cuerpo replicado 4 u 8 veces más un epílogo que trata el resto. El epílogo es la firma inconfundible del desenrollado, y el factor de desenrollado suele ser reconocible por el valor de la comparación del preludio.

Convenios de llamada. Los registros que la función guarda al entrar y restaura al salir identifican el convenio y, con él, el compilador y a menudo la versión. Es información valiosa: fijar el compilador correcto en la herramienta mejora todas las heurísticas posteriores.

Una advertencia final sobre la asignación de registros, que es la fuente de confusión más persistente en RE. El registro no es la variable. Un mismo registro contiene a lo largo de una función valores de variables distintas del fuente; y una misma variable del fuente vive en registros distintos en tramos distintos. La única manera de recuperar la correspondencia es construir SSA, agrupar por φ-webs y después deshacer las divisiones de rango de vida detectando las copias. Es exactamente el proceso que se ha descrito hasta aquí, ejecutado al revés.

23.9 Lecturas

Los resultados sobre cordalidad de los grafos de interferencia bajo SSA son de Bouchez et al. (2006) y de Hack, Grund y Goos (2006), obtenidos de forma independiente. El algoritmo de iterated register coalescing es de George y Appel (1996); linear scan, de Poletto y Sarkar (1999).