SSA per codice macchina stack

Question

Sto lavorando su un compilatore per una macchina stack (in particolare CIL) e ho analizzato il codice in un grafico di blocchi di base.Da qui sto cercando di candidarmi SSA ai metodi, ma non sta andando troppo bene.Il mio primo tentativo (mentre lavoravo con un elenco piatto, piuttosto che con il grafico) è stato quello di ripetere il codice e mantenere uno stack di ID SSA (ovvero per gli obiettivi di assegnazione), spingendoli quando produco un compito, spuntandoli quando sono usati.Funziona perfettamente per un singolo blocco base, ma semplicemente non riesco a capire come gestire la produzione di funzioni Φ.

L'idea che mi è venuta in mente è quella di allegare una posizione nello stack agli ID SSA e poi guardare cosa c'è ancora nello stack quando i percorsi del codice convergono, ma questo non sembra il modo giusto (TM) di fare le cose.

Esiste un semplice algoritmo per tenere traccia delle manipolazioni dello stack su più percorsi di codice e determinare le collisioni quando convergono?

Answer 1

Devi guardare il multiplo insieme di ID SSA convergente su un nodo (blocco base).Mantieni la struttura a blocchi di base intermedia, in questo modo puoi utilizzare facilmente (ad es.query) tutti gli identificatori in un blocco.

Non sono sicuro di cosa intendi con collisione, ma presumo che tu voglia risolvere qualcosa del genere

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

cioè, vuoi il Phi in questo posto.Renditi conto che non c'è Phi nel codice eseguibile!Utilizzando l'informazione che y è (dipendente) da x1 o x2, puoi riscriverlo nel passaggio successivo.Ad esempio, in una rappresentazione incentrata sulla memoria, Phi(x1,x2) indica che x1 e x2 dovrebbero essere due alias nella stessa posizione di memoria, ovvero quella di y.Phi si limita a legare insieme le informazioni.

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

Spero che questo aiuti un po'!