Register asignación y derrames, el camino más fácil?

https://stackoverflow.com/questions/1960888

21-09-2019
|

Pregunta

Estoy buscando una manera de asignar las variables locales a los registros. Soy consciente de un par de métodos serios para hacerlo (es decir, los mencionados Wikipedia ) , pero estoy atascado en la forma "derramamiento" se lleva a cabo. Además, la literatura relevante es bastante intimidante. Estoy esperando que hay algo más simple que satisfaga mis prioridades:

Corrección - un algoritmo que genere código correcto independientemente del número de variables locales existen
Simplicidad -. Algo que pueda entender sin tener que leer demasiado la literatura
Eficiencia - que tiene que ser mejor que el método actual, que es:

Traducir un x = y # z operación a:

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

Como estoy focalización Intel 386, algunas limitaciones relevantes son:

Las operaciones binarias toman dos argumentos, uno de los cuales es una fuente y destino. operaciones unarios un solo argumento.
Las operaciones sólo pueden acceder a una posición de memoria; Por lo tanto, las operaciones binarias necesitan por lo 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 un último recurso.)
Hay casos especiales, tales como la división de enteros y registros regresan, pero pueden ignorarlos por ahora.

Hay tres pasos el compilador recibe a través de momento:

i386ification:. Todas las operaciones se convierten en una forma a = a # b (o a = #a para operaciones unarios)
análisis Liveness:. Los conjuntos de variables en vivo antes y después de cada operación se determinan
Registrar la asignación:. Un gráfico de interferencias se construye y coloreado

Y a continuación, el compilador tiros sus lápices de colores 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 interferencias en lugar bonito para la función y el CFG con la información de vivacidad. La imagen CFG requiere un cierto desplazamiento vertical, por desgracia.

Se utilizaron siete colores. Me gustaría derramar una de ellas (o el conjunto de variables asignado ese color). El método de elección que no es demasiado importante. Lo que se complica es cómo hacer frente a las variables derramados.

Digamos que derramo "rosa", que es el conjunto de variables t, $t4, $t7. Esto significa que estas operaciones se refieren a una de estas variables acceder a él 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, ¿y si el programa era:

...
a = a + b
...

y ambos a y b que se habían derramado? No puedo emitir una instrucción addl b, a con dos direcciones de memoria. Yo necesitaría otro registro repuesto para mantener temporalmente uno de los operandos, y eso significa que se derrame otro color. Esto sugiere un método general de:

Si todas las variables se pueden colorear con colores r, genial!
Si no, derramar algunos colores y sus variables asociadas.
Si existe una operación que accede a dos variables derramados, derrame de otro color y utilizar el registro de repuesto para el almacenamiento temporal de todas las operaciones.

En este punto yo sospecho que muchas más cosas se derrama de lo necesario, y me pregunto si hay alguna manera más inteligente para derramar cosas, como derramar parte de la vida de una variable, en lugar del than toda la propia variable. ¿Hay algunos (ISH) técnicas sencillas que podría utilizar aquí? De nuevo, no estoy apuntando particularmente alto - ciertamente no lo suficientemente alta como para requerir leer nada 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 todas las instrucciones de uso de esa variable necesidad de acceder a ella directamente en la memoria (a partir de su posición de pila)? ¿Cómo este trabajo si una operación se utilizan dos derramado variables? (La arquitectura no permite instrucciones para acceder a dos posiciones de memoria distintas.)

problemas secundarios son:

¿Cómo puedo determinar dónde insertar instrucciones de carga / almacenamiento, para su corrección (y menos importante, la eficiencia)?
¿Puedo derramar una variable sólo para esa parte de su vida cuando no está en uso inmediato, y unspill más tarde? Así que todas las instrucciones actúan en un registro unspilled. 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 que se devuelve pasó a ser asignado a dicho registro por el momento en que se encontró el retorno. Del mismo modo, algunos registros son "destinatario de la llamada-save", por lo que si un menor número de variables que resultaron ser vivo en el momento de una llamada de función, de haberlos asignados a no destinatario de la llamada a guardar registros significarían puedo evitar el almacenamiento de dichos registros.
¿Podría SSA forma ayuda mucho (o nada)? Ser capaz de eliminar subexpresiones comunes y evaluar constantes podría reducir (?) De alta presión, pero por lo demás sería tener algún efecto?

Los aspectos que no estoy preocupado (en este momento) son:

asignación de pila y optimización: se implementa ingenuamente ya, y se pueden optimizar el uso de la gráfica de interferencia si es necesario
La eficiencia en tiempo de compilación, al igual que siempre que sus extremos. (NP-completitud no implica un algoritmo dado debe ser evitado.)

Actualizar

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

He encontrado la presentación muy agradable (PPT, por desgracia):

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

¿Qué responde a la pregunta acerca de cómo hacer frente a las necesidades específicas de operación (como usar el mismo registro de origen y de destino, o que necesitan un cierto registro para algunas operaciones). Lo que no estoy seguro es si el ciclo de Liveness-colorear-Asignación termina.

Voy a tratar de hacer un trabajo real pronto y es de esperar cerrar la pregunta.

Solución

He utilizado un enfoque codiciosos en un asignador JVM vez, lo que funcionó bastante bien. Básicamente comenzar en la parte superior de un bloque básico con todos los valores almacenados en la pila. A continuación, sólo escanear las instrucciones hacia adelante, mantener una lista de registros que contienen un valor, y si el valor está sucio (necesita ser escrito posterior). Si una instrucción utiliza un valor que no está en un registro (o no en el registro correcto), emite una carga (o mover) para ponerlo en un registro libre antes de la instrucción. Si una instrucción escribe un valor, asegurar que esté en un registro y se marca sucia después de la instrucción.

Si alguna vez necesita un registro, derrame de un registro utilizado por cancelar la asignación del valor de ella, y la escritura a la pila si está sucio y vivir. Al final del bloque básico, escribir de nuevo los registros sucios y en vivo.

Este esquema deja claro exactamente donde todas las cargas / tiendas van, les generan a medida que avanza. Es fácilmente adaptable a las instrucciones que tienen un valor en la memoria, o que puede tomar cualquiera de los dos argumentos en la memoria, pero no ambos.

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

Puede obtener arbitrariamente complicado sobre cómo establecer los valores a derramarse y que registra asignar. Algunos de búsqueda hacia delante puede ser útil, por ejemplo mediante el marcado de cada valor con un registro específico que tiene que ser en algún momento en el bloque básico (por ejemplo eax para un valor de retorno, o ecx para una cantidad de desplazamiento) y prefiriendo que registrarse cuando el valor se asigna primero (y evitar que el registro de otras asignaciones). Pero es fácil separar la corrección del algoritmo de la heurística de mejora.

He utilizado este asignador de un compilador SSA, tu caso es distinto.

Otros consejos

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

¿Cómo se realiza el derrame:

El usuario ejecuta el algoritmo de asignación de registro y obtener una lista de variables que hay que derramar. Ahora se puede asignar un poco de espacio en la pila al comienzo de su función. Enlace todas las variables derramado también un lugar en la pila. Si quieres ser la memoria se unen inteligente con rangos en vivo que no se solapan. Siempre que necesite un registro derrame guardarlo en la memoria y cargarlo, cuando se necesita de nuevo.

Como manejar EAX:

Marcar el registro como lleno, pero no se almacena ninguna variable en ella (preasignación). Esto hará que el generador de código de borrar ese registro. Para ser inteligente tienda el valor en otro registro si beneficioso.

Fácil y formas correctas de manejar el derrame:

Sólo contarlo todo. Esto asume que el rango en vivo de cada variable es todo el programa. Esto se puede aumentar mediante el uso de cosas como LRU o el uso contar para elegir qué registros deberían ser liberado.

La siguiente mejor cosa que hacer es probablemente exploración lineal del alojamiento de registros . Debe ser bastante fácil de implementar incluso cuando se utiliza preasignación. Le sugiero que busque en el documento vinculado.

respuestas específicas

¿Qué significa la corrección para usted? Incluso los simples algoritmos asignaciones son correctas si no se comete un error de programación. A prueba de corrección (matemática) es mucho más difícil. Ambas cargas y almacenamientos deben insertarse antes de que se necesita el valor / registro nuevo. Ambos necesitan ser insertada después se almacena el valor / creado.
Sí. Si programa de esa manera. Si el algoritmo puede manejar un valor en múltiples registros durante su Livetime puede utilizar esas optimizaciones.
Es de nuevo a usted para poner en práctica ciertas mejoras. Una posibilidad sería la única eax bloque cuando se necesita, no para todo el programa.
Bajo ciertas condiciones SSA sí ayuda. gráficos de inferencia de código SSA son siempre cordal , lo que significa que no existe un ciclo con más de 3 nodos. Este es un caso especial de coloración gráfica, en la que una coloración mínima se puede encontrar en tiempo polinómico. La conversión a la SSA no significa necesariamente más o menos presión en el registro. Mientras el formulario SSA tiene generalmente más variables, éstas tienden a tener livetimes más pequeñas.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow