SSA para el código máquina de pila

Question

Estoy trabajando en un compilador para una máquina de pila (específicamente CIL ) y estoy hemos analizado el código en un gráfico de bloques básicos. De aquí que estoy buscando para aplicar SSA a los métodos, pero no va demasiado bien. Mi primer intento (mientras se trabaja con una lista plana, en lugar de la gráfica) era para repetir el código y tener una pila de identificadores de la SSA (es decir, para los objetivos de asignar), empujándolos cuando produzco una asignación, apareciendo cuando se utilizan. Esto funciona muy bien para un único bloque básico, pero simplemente no puede encontrar la manera de manejar la producción de funciones phi.

La idea que he estado en torno a lanzar es adjuntar una posición pila a los identificadores de la SSA y luego ver lo que está todavía en la pila cuando las rutas de código convergen, pero esto no parece ser la manera correcta (TM) de hacer las cosas.

¿Existe un algoritmo simple para el seguimiento de las manipulaciones de la pila a través de múltiples rutas de código y determinar las colisiones cuando convergen?

Answer 1

Es necesario buscar en el múltiple conjunto de identificadores de SSA que convergen en un nodo (bloque básico). Mantener la estructura básica del bloque intermedio, de esa manera puede utilizar simplemente (por ejemplo consulta) 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)

es decir, desea que el Phi en este lugar. Darse cuenta de que no hay Phi en código ejecutable! Utilizando la información que y es o bien (dependiente) en x1 o x2, puede volver a escribir esto en el siguiente paso. Por ejemplo, en una representación centrada en la memoria, el Phi (x1, x2) le dice que X1 y X2 deben ser dos alias en la misma ubicación de memoria, es decir, la de y. Phi simplemente está unida información en conjunto.

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

Espero que esto ayude un poco!