graph-theory - developer - open graph checker

Registre la asignación y el derrame, la manera fácil? (2)

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 que se mencionan en 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ó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 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 en una forma a = a # b (o a = #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 algún desplazamiento vertical, desafortunadamente.

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 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 hacerlo a través de un registro. Esto debería funcionar para este ejemplo.

Pero y si el programa fuera:

... a = a + b ...

y tanto a como b tuvieron que ser derramados? No puedo emitir una instrucción addl 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 con r colores, ¡excelente!
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í? De nuevo, 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 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 usa para el valor de retorno, por lo que sería bueno que la variable que se devuelva se asigne 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 de guardado no llamado 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 está implementado 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 la fuente y el destino, o la necesidad de un registro determinado para algunas operaciones) De lo que no estoy seguro es de si el ciclo de asignación de coloración-vitalidad termina.

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

Primero: No hay una forma inteligente de hacerlo. El problema es NP-completo ;-)

Cómo se hace el derrame:

Usted ejecuta su algoritmo de asignación de registros y obtiene una lista de variables que debe derramar. Ahora puede asignar algo de espacio en la pila al comienzo de su función. Enlace cada variable derramada también un lugar en la pila. Si desea ser una memoria de fusión inteligente con rangos en vivo que no se superpongan. Cada vez que necesite derramar un registro, guárdelo en la memoria y cárguelo cuando lo necesite de nuevo.

Cómo manejar eax:

Marque el registro como lleno, pero no almacene ninguna variable en él (asignación previa). Esto hará que el generador de código borre ese registro. Para ser inteligente almacene el valor en otro registro si es beneficioso.

Maneras fáciles y correctas de manejar el derrame:

Sólo derrame todo. Esto supone que el rango en vivo de cada variable es el programa completo. Esto puede aumentarse mediante el uso de elementos como LRU o recuento de uso para elegir qué registros deben liberarse.

La siguiente mejor cosa que hacer es probablemente la asignación de registro de exploración lineal . Debería ser bastante fácil de implementar, incluso cuando se utiliza la asignación previa. Te sugiero que mires en el papel vinculado.

Respuestas especificas

¿Qué significa la corrección para ti? Incluso los algoritmos de asignación simples son correctos si no comete un error de programación. La corrección (matemática) de corrección es mucho más difícil. Tanto las cargas como las tiendas deben insertarse antes de que se necesite nuevamente el valor / registro. Ambos deben insertarse después de que se almacene / cree el valor.
Sí. Si lo programa así. Si su algoritmo puede manejar un valor en varios registros durante su tiempo de vida, puede usar esas optimizaciones.
De nuevo depende de usted implementar ciertas mejoras. Una posibilidad sería bloquear solo eax cuando sea necesario, no para todo el programa.
Bajo ciertas condiciones, la SSA ayuda. Los gráficos de inferencia del código SSA son siempre chordal , lo que significa que no hay un ciclo con más de 3 nodos. Este es un caso especial de coloración gráfica, en la que se puede encontrar una coloración mínima en el tiempo polinomial. La conversión a SSA no significa necesariamente más o menos presión de registro. Mientras que la forma SSA tiene generalmente más variables, estas tienden a tener tiempos de vida más pequeños.

Una vez utilicé un enfoque codicioso en un asignador JVM, que funcionó bastante bien. Básicamente comienza en la parte superior de un bloque básico con todos los valores almacenados en la pila. Luego, simplemente escanee las instrucciones hacia adelante, mantenga una lista de registros que contengan un valor, y si el valor está sucio (debe escribirse de nuevo). Si una instrucción utiliza un valor que no está en un registro (o no en el registro correcto), emita una carga (o mueva) para ponerlo en un registro libre antes de la instrucción. Si una instrucción escribe un valor, asegúrese de que esté en un registro y márquelo como sucio después de la instrucción.

Si alguna vez necesita un registro, derrame un registro usado asignando el valor de él y escribiéndolo en la pila si está sucio y vivo. Al final del bloque básico, escriba cualquier registro sucio y activo.

Este esquema deja en claro exactamente a dónde van todas las cargas / tiendas, usted las genera a medida que avanza. Es fácilmente adaptable a instrucciones que toman un valor en la memoria, o que pueden tomar cualquiera de los dos argumentos en la memoria, pero no ambos.

Si está de acuerdo con tener todos los datos en la pila en cada límite de bloque básico, este esquema funciona bastante bien. Debería dar resultados similares a la exploración lineal dentro de un bloque básico, ya que básicamente hace cosas muy similares.

Puede complicarse arbitrariamente sobre cómo decidir qué valores derramar y qué registros asignar. Algunos lookahead pueden ser útiles, por ejemplo, marcando cada valor con un registro específico en el que debe estar en algún punto del bloque básico (por ejemplo, eax para un valor de retorno, o ecx para un monto de turno) y preferir ese registro cuando el valor Se asigna primero (y evita ese registro para otras asignaciones). Pero es fácil separar la corrección del algoritmo de las heurísticas de mejora.

He utilizado este asignador en un compilador SSA, YMMV.