Registro de asignación y derramamiento, de la manera fácil?

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 mencionados en Wikipedia), pero estoy atascado en cómo se logra "derramar". Además, la literatura relevante es bastante intimidante. Espero que haya algo más simple que satisfaga mis prioridades:

1. Correctness an un algoritmo que generará código correcto sin importar cuántas variables locales haya ser.
2. Simplicidad something algo que puedo entender sin tener que leer demasiada literatura.
3. Eficiencia needs necesita ser mejor que el método actual, que es:

Traduce una operación x = 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 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 de los registros disponibles: %eax %ebx %ecx %edx %esi %edi. (%ebp también podría incluirse como último recurso.)
• Hay casos especiales como para la división de enteros y los registros de retorno, pero puedo ignorarlos por ahora.

Hay tres pasos a través del compilador en este momento:

• i386ification: todas las operaciones son convertido a un formulario a = a # b (o a = #a para operaciones unarias).
• Análisis de vivencia: se determinan los conjuntos de variables vivas antes y después de cada operación.
• Asignación de registros: se construye y colorea un gráfico de interferencia.

Y luego el compilador lanza sus crayones en el 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 liveness. El Imagen CFG requiere un poco de desplazamiento vertical, por desgracia.

• Gráfico de interferencia para una función sobre 14 variables
• Gráfico de flujo de control 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 pone complicado es cómo lidiar con las variables derramadas.

Digamos que derrame "rosa", que es el conjunto de variables t, $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 a través de un registro. Esto debería funcionar para este ejemplo.

Pero qué pasaría si el programa fuera:

...
a = a + b
...

Y ambos a y b tuvieron que ser derramados? No puedo emitir una instrucción addl b, a con dos direcciones de memoria. Necesitaría otro registro de repuesto para mantener temporalmente uno de los operandos, y eso significa derramar otro color. Esto sugiere un método general de:

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

En este punto, sospecharía que se están derramando muchas más cosas de lo necesario, 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í? Una vez más, no estoy apuntando particularmente alto certainly ciertamente no lo suficientemente alto como para requerir leer algo demasiado profundo. ;-)

Problemas específicos

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

Los problemas secundarios son:

• ¿Cómo determino dónde insertar instrucciones de carga/almacenamiento, para la corrección (y menos importante, la eficiencia) ?
• Puedo derramar una variable solo durante esa parte de su vida cuando ¿no está en uso inmediato, y unspill él más adelante? Para que todas las instrucciones actúen sobre registros no rellenados. 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 devuelto, 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. Del mismo modo, algunos registros son "callee-save", por lo que si se estar en vivo en el momento de una llamada a una función, tenerlos asignados a registros no-callee-save significaría que puedo evitar almacenar esos registros.
• ¿Ayudaría mucho el formulario SSA (si es que lo ayuda) ? Ser capaz de eliminar subexpresiones comunes y evaluar constantes podría reducir (?) registrar la presión, pero de lo contrario tendría algún efecto?

Los aspectos que no me preocupan (en este momento) son: {[24]]}

• Asignación y optimización de pilas: ya se ha implementado ingenuamente, y se puede optimizar utilizando el gráfico de interferencia si es necesario.
• Eficiencia en tiempo de compilación, siempre y cuando termine. (NP-completitud no implica un determinado algoritmo debe ser evitado.)

Actualización

Lo siento por el tiempo de inactividad've He estado pensando en las respuestas dadas y tratando de encontrar un enfoque fácil de tomar para comenzar a implementar algunas de las ideas. Para ser honesto, he estado postergando... :-\

Encontré la presentación muy agradable (PPT, tristemente):

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

Que responde a la pregunta sobre cómo lidiar con necesidades de operación específicas (como usar el mismo registro para origen y destino; o necesitar un cierto registro para algunas operaciones). De lo que no estoy seguro es de si el ciclo de Asignación de Color-Vida termina.

Voy a tratar de hacer un poco de trabajo real pronto y espero cerrar el pregunta.