Generación de código de compilación: asignación de registro dentro de bloques condicionales

Question

Estoy escribiendo un compilador para un curso. Me he encontrado con algunos problemas de optimización que no estoy seguro de cómo manejar de manera óptima. Supongamos que hay un ciclo while del lenguaje de entrada que usa N variables locales que deben mantenerse en registros (o deberían serlo, para cálculos rápidos). Supongamos que N> K, el número de registros. Existe la posibilidad de que el registro condicional se cambie cerca del final del ciclo while.

Por ejemplo, supongamos que el registro para x (digamos% eax en i386) se determinó antes la siguiente declaración:

while (x) { x = x - 1 ; /* more statements */ } 

En el código más declaraciones, es posible para que x sea derramada de vuelta a la pila. Cuando el código salta de nuevo al comienzo del ciclo while para volver a evaluar x, intentará usar% eax, pero puede que ni siquiera tenga el valor de x ahora. Así que podríamos tener algo como

 movl -8(%ebp), %eax  # eax <- x 
     ....      # do stuff but let x stay in %eax 
_LOOP1: cmpl $0, %eax 
     .... 
     movl -12(%ebp), %eax  #eax now holds something else 
     .... 
     jmp _LOOP1 

Una solución que estoy usando es para forzar el código derramar todos los registros modificados antes de la sentencia while (por lo que los registros son vistos como vacío desde la perspectiva del generador de código). Después de la etiqueta para el ciclo while, el código tiene que cargar todo en un registro según sea necesario.

Mi solución es algo como esto:

 movl -8(%ebp), %eax  # eax <- x 
     ....      # do stuff but let x stay in %eax 
     movl %eax, -8(%ebp)  # spilling and clearing all registers 
_LOOP1: movl -8(%ebp), %eax  # get a register for x again 
     cmpl $0, %eax 
     .... 
     movl -12(%ebp), %eax  # eax now holds something else 
     .... 
     movl %eax, -8(%ebp)  # spill to prevent overwrite 
     jmp _LOOP1 

Parece que mi solución es un poco extraño o innecesario. ¿Hay algún truco de optimización general que estoy olvidando aquí?

EDITAR: También me gustaría notar algo similar ocurre con condicionales como if y if else. Esto ocurre para ellos porque se puede asignar un registro para una variable dentro del bloque para el condicional, pero el generador de código asume que se movió allí para todo lo demás después. Tengo casi el mismo enfoque para tratar con ese caso.

Answer 1

La técnica general que está buscando aquí generalmente se llama "división de rango en vivo". Un Google Search para ese término le dará consejos para un montón de papeles diferentes. Básicamente, la idea es que quiera dividir una sola variable (x en su ejemplo) en múltiples variables con rangos en vivo disjuntos, cada uno de los cuales se copia al siguiente en el punto de división. Por lo tanto, tendría x.0 antes del ciclo, que se copia en x.1 justo antes del while y se usa como tal en el ciclo. Luego, justo después del bucle, debe copiar x.1 en x.2 y usarlo después del bucle. Cada uno de los vars divididos se asignaría potencialmente a un registro diferente (o ranura de pila).

Aquí hay una gran cantidad de compensaciones: demasiada división conduce a (muchas) más variables en el código, lo que hace que la asignación de registros sea mucho más lenta y, potencialmente, genere copias innecesarias.