Estoy buscando una manera de asignar variables locales a los registros. Soy consciente de un par de métodos serios para hacerlo (a saber, los mencionadosen Wikipedia), pero estoy atascado en cómo se logra el "derrame". Además, la literatura relevante es bastante intimidante. Espero que haya algo más simple que satisfaga mis prioridades:

Corrección: un algoritmo que generará el código correcto sin importar cuántas variables locales haya.Sencillez, algo que puedo entender sin tener que leer demasiada literatura.Eficiencia: debe ser mejor que el método actual, que es:

Traducir una operaciónx = y # z a:

movl y, %eax
movl z, %ebx
op %ebx, %eax
movl %eax, x

Como estoy apuntando a Intel 386, algunas restricciones relevantes son:

Las operaciones binarias toman dos argumentos, uno de los cuales es un origen y un destino. Las operaciones unarias toman un solo argumento.Las operaciones solo pueden acceder a una ubicación de memoria; Por lo tanto, las operaciones binarias necesitan al menos un argumento en un registro.Hay un máximo de seis registros disponibles:%eax %ebx %ecx %edx %esi %edi. (%ebp También podría incluirse como último recurso.)Hay casos especiales, como los registros de división y retorno de enteros, pero puedo ignorarlos por ahora.

Hay tres pasos por los que pasa el compilador en este momento:

i386ification: todas las operaciones se convierten a un formularioa = a # b (oa = #a para operaciones unarias).Análisis de vitalidad: se determinan los conjuntos de variables en vivo antes y después de cada operación.Asignación de registro: se construye y se colorea un gráfico de interferencia.

Y luego el compilador lanza sus crayones al aire y no sabe qué hacer a continuación.

Ejemplo

public int mf(int cr, int ci) {
    int i = 0;
    int zr = 0;
    int zi = 0;

    while (i < 100 && zr*zr + zi*zi < 4) {
        int t = zr * zr - zi * zi + cr;
        zi = 2 * zr * zi + ci;
        zr = t;

        i = i + 1;
    }
    return i;
}

Aquí está el gráfico de interferencia bastante bonito para la función, y el CFG con información de vida. La imagen CFG requiere un desplazamiento vertical, desafortunadamente.

Gráfica de interferencia para una función en 14 variablesGráfico de control-flujo para una función, con información de vida

Se utilizaron siete colores. Me gustaría derramar uno de ellos (o el conjunto de variables asignadas a ese color). El método de elección que no es demasiado importante. Lo que se complica es cómo lidiar con las variables derramadas.

Digamos que derrame "rosa", que es el conjunto de variablest, $t4, $t7. Esto significa que las operaciones que se refieren a una de estas variables accederán a ella desde su posición en el marco de la pila, en lugar de hacerlo a través de un registro. Esto debería funcionar para este ejemplo.

Pero y si el programa fuera:

...
a = a + b
...

y ambosa yb tuvo que ser derramado? No puedo emitir una instrucciónaddl b, a con dos direcciones de memoria. Necesitaría otro registro de reserva para mantener temporalmente uno de los operandos, y eso significa derramar otro color. Esto sugiere un método general de:

Si todas las variables pueden ser coloreadas conr colores, genial!De lo contrario, derrame algunos colores y sus variables asociadas.Si existe una operación que accede a dos variables derramadas, derrame otro color y use el registro de reserva para el almacenamiento temporal de todas estas operaciones.

En este punto, sospecho que se están derramando muchas más cosas de las necesarias, y me pregunto si hay alguna forma más inteligente de derramar cosas, como derramar parte de la vida útil de una variable, en lugar de toda la variable en sí. ¿Hay algunas técnicas simples (ish) que podría usar aquí? Nuevamente, no estoy apuntando particularmente alto, ciertamente no lo suficientemente alto como para requerir leer algo demasiado profundo. ;-)

Problemas especificos

El principal problema específico es: cuando se derrama una variable, ¿cómo afecta esto a las instrucciones generadas? ¿Todas las instrucciones que usan esa variable necesitan acceder directamente en la memoria (desde su posición de pila)? ¿Cómo funcionará esto si una operación usa dos variables derramadas? (La arquitectura no permite instrucciones para acceder a dos ubicaciones de memoria distintas).

Los problemas secundarios son:

¿Cómo puedo determinar dónde insertar las instrucciones de carga / almacenamiento para la corrección (y, lo que es menos importante, la eficiencia)?¿Puedo derramar una variable solo para esa parte de su vida útil cuando no está en uso inmediato, y desecharla más tarde? Para que todas las instrucciones actúen sobre registros sin rellenar. Una variable puede vivir en diferentes registros en diferentes momentos.¿Puedo ser un poco más eficiente con casos especiales? Por ejemplo,%eax se utiliza para el valor de retorno, por lo que sería bueno si la variable a devolver se asignara a ese registro en el momento en que se encontró el retorno. De manera similar, algunos registros son "guardado de llamada", por lo que si hubiera menos variables activas en el momento de una llamada de función, tenerlos asignados a registros que no sean de guardado de llamada significaría que puedo evitar almacenar esos registros.¿Ayudaría mucho el formulario de la SSA (si es que lo hace)? Ser capaz de eliminar las subexpresiones comunes y evaluar las constantes podría reducir (?) La presión del registro, pero, de lo contrario, ¿tendría algún efecto?

Los aspectos que no me preocupan (en este momento) son:

Asignación y optimización de la pila: ya se implementó ingenuamente, y puede optimizarse utilizando el gráfico de interferencia si es necesario.Eficacia en tiempo de compilación, siempre y cuando termine. (La integridad de NP no implica que se deba evitar un algoritmo dado).Actualizar

Perdón por el tiempo de inactividad: he estado pensando en las respuestas dadas y tratando de encontrar un enfoque fácil para comenzar a implementar algunas de las ideas. Para ser honesto, he estado postergando ...: - \ Encontré la muy buena presentación (PPT, por desgracia):

http://www.cs.princeton.edu/courses/archive/spr05/cos320/notes/Register%20Allocation.ppt

Lo que responde a la pregunta sobre cómo lidiar con las necesidades específicas de la operación (como usar el mismo registro para el origen y el destino, o la necesidad de un determinado registro para algunas operaciones). De lo que no estoy seguro es de si termina el ciclo de asignación de coloración de color.

Intentaré hacer un trabajo real pronto y espero cerrar la pregunta.

Usted tiene razón: estará derramando registros que no están actualmente en uso para dar espacio a los que se usarán. Entonces, todas las operaciones pueden estar en los registros. Para aflojar esto y realizar algunas operaciones directamente en los registros derramados, modifique el algoritmo de asignación de registros para permitir que, como máximo, un registro permanezca derramado durante las instrucciones de registro a registro ... pero no es necesario.