SSA para el código de máquina de pila

Question

Estoy trabajando en un compilador para una máquina de pila (específicamente CIL) y he analizado el código en un gráfico de bloques básicos. Desde aquí estoy buscando aplicar SSA a los métodos, pero no va muy bien. Mi primer intento (mientras trabajaba con una lista plana, en lugar del gráfico) fue iterar sobre el código y mantener una pila de identificadores de SSA (es decir, para los objetivos de asignación), empujándolos cuando produzco una tarea, apareciendo cuando están usados. Esto funciona bien para un solo bloque básico, pero simplemente no puedo entender cómo manejar las funciones Φ de producción.

La idea que he estado dando vueltas es adjuntar una posición de pila a los identificadores SSA y luego ver qué hay en la pila cuando convergen las rutas de código, pero esto no parece ser el modo correcto (TM) de hacer cosas.

¿Hay un algoritmo simple para rastrear las manipulaciones de la pila en varias rutas de código y determinar las colisiones cuando convergen?

Answer 1

Debe consultar el conjunto múltiple de identificadores SSA que convergen en un nodo (bloque básico). Mantenga la estructura de bloques básica intermedia, de esa manera puede usar fácilmente (por ejemplo, consultar) todos los identificadores en un bloque.

no estoy seguro de lo que quiere decir con colisión, pero supongo que se quiere resolver algo así como

if (bExp)     if (bExp) 
    x := 1     x1 := 1 
else   SSA:  else 
    x := 2     x2 := 2 
y := x;     y := Phi(x1,x2) 

que es, desea que el Phi en este lugar. ¡Date cuenta de que no hay Phi en código ejecutable! Usando la información de que y es (dependiente) de x1 o x2, puede reescribir esto en el siguiente paso. Por ejemplo, en una representación centrada en la memoria, la Phi (x1, x2) le dice que x1 y x2 deben ser dos alias para la misma ubicación de memoria, es decir, la de y. Phi solo une información.

if (bExp) 
    stackframe[y_index] = 1  (y_index being some offset) 
else 
    stackframe[y_index] = 2 
nop 

Espero que esto ayude un poco!