スタックマシンコード用のSSA

Question

私はスタックマシン用のコンパイラに取り組んでいます（特に CIL) そして、コードを基本ブロックのグラフに解析しました。ここから応募してみようと思います SSA 方法を考えましたが、あまりうまくいきません。私の最初の試みは(グラフではなくフラットなリストで作業しているとき)、コードを反復処理してSSA IDのスタック(つまり、割り当てターゲット用)を保持し、割り当てを生成するときにそれらをプッシュし、割り当てを生成するときにそれらをポップすることでした。彼らは使われています。これは単一の基本ブロックではうまく機能しますが、Φ 関数の生成を処理する方法がわかりません。

私が検討してきたアイデアは、SSA ID にスタック位置を付加し、コード パスが収束したときにスタック上に残っているものを確認することですが、これは物事を行う正しい方法 (TM) とは思えません。

複数のコードパスにわたるスタック操作を追跡し、それらが収束したときに衝突を判断するための単純なアルゴリズムはありますか?

Answer 1

複数で見る必要がある SSA ID のセット ノード (基本ブロック) に収束します。簡単に使用できるように、中間の基本ブロック構造を維持します (例:クエリ) ブロック内のすべての識別子。

衝突が何を意味するのかわかりませんが、次のようなものを解決したいと思います

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

つまり、この場所にファイが必要です。実行可能コードには Phi が存在しないことに注意してください。y が x1 または x2 に (依存して) いるという情報を使用して、次のステップでこれを書き直すことができます。たとえば、メモリ中心の表現では、Phi(x1,x2) は、x1 と x2 が同じメモリ位置、つまり y のメモリ位置に対する 2 つのエイリアスである必要があることを示します。ファイは情報を結び付けるだけです。

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

これが少しでも役立つことを願っています!