SSA pour le code machine de la pile

Question

Je travaille sur un compilateur pour une machine de pile (spécifiquement CIL) et j'ai analysé le code dans un graphique de blocs de base. De là, je cherche à appliquer SSA aux méthodes, mais ça ne va pas trop bien. Ma première tentative (en travaillant avec un listing plat, plutôt qu'avec le graphique) consistait à parcourir le code et à conserver une pile d'identifiants SSA (c'est-à-dire pour les cibles assignées), à les pousser quand je produisais une assignation. ils sont utilisés. Cela fonctionne très bien pour un seul bloc de base, mais je n'arrive tout simplement pas à comprendre comment gérer les fonctions Φ. L'idée que j'ai jetée est d'attacher une position de pile aux identifiants SSA et de regarder ce qui est encore sur la pile quand les chemins de code convergent, mais cela ne semble pas être le bon chemin (TM) de faire des choses.

Existe-t-il un algorithme simple pour suivre les manipulations de pile sur plusieurs chemins de code et déterminer les collisions lorsqu'elles convergent?

Answer 1

Vous devez consulter les ensembles d'ID SSA convergeant sur un noeud (bloc de base). Conservez la structure de bloc de base intermédiaire, de cette façon vous pouvez facilement utiliser (par exemple, interroger) tous les identifiants d'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. Réalisez qu'il n'y a pas de Phi dans le code exécutable! En utilisant l'information que y est (dépendante) sur x1 ou x2, vous pouvez réécrire ceci à l'étape suivante. Par exemple, dans une représentation centrée sur la mémoire, le Phi (x1, x2) vous dit que x1 et x2 devraient être deux alias au même emplacement de mémoire, à savoir celui de y. Phi lie juste l'information 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!