SSA pour le code machine de la pile

Question

Je travaille sur un compilateur pour une machine à pile (en particulier CIL ) et je ai analysé le code dans un diagramme de blocs de base. De là, je suis à la recherche d'appliquer SSA aux méthodes, mais ça ne va pas trop bien. Ma première tentative (tout en travaillant avec une liste plate, plutôt que le graphique) devait parcourir le code et garder une pile de ids SSA (qui est, pour les cibles Assign), les poussant quand je produis une mission, les claquements lorsque ils sont utilisés. Cela fonctionne très bien pour un seul bloc de base, mais je ne peux tout simplement pas comprendre comment gérer la production de fonctions & phiv.

L'idée que j'ai agitais est autour de fixer une position de la pile aux ids SSA, puis regarder ce qui est encore sur la pile lorsque les chemins de code convergent, mais cela ne semble pas la bonne façon (TM) de faire les choses.

Y at-il un algorithme simple pour le suivi des manipulations de la pile à travers de multiples chemins de code et de déterminer les collisions quand ils convergent?

Answer 1

Vous devez regarder le multiple ensemble de SSA ids convergent sur un nœud (bloc de base). Gardez la structure de bloc de base intermédiaire, de cette façon, vous pouvez facilement utiliser (par exemple la requête) tous les identifiants dans un bloc.

Je ne suis pas sûr de ce que vous entendez par collision, mais je suppose que vous voulez résoudre quelque chose comme

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

qui est, vous voulez Phi à cet endroit. Sachez qu'il n'y a pas de Phi dans le code exécutable! En utilisant les informations que y est soit (en fonction) sur x1 ou x2, vous pouvez réécrire ceci dans l'étape suivante. Par exemple, dans une représentation centrée sur la mémoire, le Phi (x1, x2) vous indique que x1 et x2 doivent être deux alias au même emplacement mémoire, à savoir celle de y. Phi lie seulement les informations ensemble.

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

Espérons que cela aide un peu!