SSA für Stapelmaschinencode

Question

Ich arbeite an einem Compiler für eine Stapelmaschine (speziell CIL ) und I‘ ve den Code in einer grafischen Darstellung der Basisblöcke geparst. Von hier aus bin ich auf der Suche SSA auf die Methoden anzuwenden, aber es ist nicht so gut laufen. Mein erster Versuch (während mit einer flachen Liste arbeiten, anstatt der Grafik) war über den Code zu durchlaufen und einen Stapel von SSA ids halten (das heißt, für die assign Ziele), sie drängen, wenn ich einen Auftrag erzeugen, knallen sie, wenn sie verwendet. Dies funktioniert gut für einen einzelnen Basisblock, aber ich kann einfach nicht herausfinden, wie Φ Funktionen produzieren zu handhaben.

Die Idee Ich habe herum werfen ist eine Stapelposition zu den SSA-IDs zu befestigen und dann schauen, was auf dem Stapel noch ist, wenn die Codepfade zusammenlaufen, aber dies scheint nicht, wie die richtige Weg (TM) von Dinge zu tun.

Gibt es einen einfachen Algorithmus, um die Stapelmanipulationen über mehrere Codepfade für die Verfolgung und Ermittlung der Kollisionen, wenn sie zusammenlaufen?

Answer 1

Sie müssen an dem mehrere aussehen Satz von SSA-IDs auf einem Knoten (Basisblock) zusammenlaufen. Halten Sie die Zwischenbasisblock-Struktur, so Sie leicht (z Abfrage) alle Bezeichner in einem Block verwenden können.

Ich bin mir nicht sicher, was Sie mit Kollision bedeuten, aber ich nehme an, Sie so etwas wie

lösen wollen

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

das ist, möchten Sie die Phi an dieser Stelle. Erkennen, dass es keine Phi in ausführbarem Code ist! Unter Verwendung der Information, dass y entweder (abhängig) auf x1 oder x2, können Sie umschreiben diese im nächsten Schritt. Zum Beispiel in einem Speicher-zentrierte Darstellung, die Phi (x1, x2) sagt Ihnen, dass x1 und x2 sollten zwei Aliase auf den gleichen Speicherplatz, nämlich dass von y. Phi bindet nur Informationen zusammen.

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

Hope, das hilft ein wenig!