SSA への変換
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/08 08:22 UTC 版)
ツリー上のコードの SSA 形式への変換は、代入の対象を新たな変数に置き換え、変数の使用箇所をその定義箇所に到達する「バージョン付き」のものに置き換えるだけの基本的に簡潔な問題である。例として、下記のような制御フローグラフを考える。 "x ← {\displaystyle \leftarrow } x - 3" の左辺の名前を変え、それ以降 x を新たな名前に変えることができ、それでもプログラムは全く同じ動作をする。このことを利用して、SSA ではそれぞれに対して一度しか代入が行われない新たな二つの変数x1 と x2 を作成する。同様に、全ての変数に対してバージョンを区別するための添え字を与える。 ここで、各々の変数を使用している箇所がどの定義を参照しているかをただ一点を除いて把握している。最後のブロックの y は制御フローのどちらを通るかによって y1 と y2のどちらを参照するかが異なる。ではこれをどのようにして知るのか？ その答えは、Φ (ファイ) 関数と呼ばれる特別な命令を最後のブロックの始めに追加することである。この命令は、どちらの制御フローから到達したのかによって y1 あるいは y2 を選択し y の新たな定義 y3 を生成する。 これにより、最後のブロックの y は y3 を用いることができ、いずれの場合でも正し値を得ることができる。x についても Φ 関数を追加する必要があるか？という質問があるかもしれないが、答えは「不要」である。x のバージョンは x2 のみがこの箇所に到達しており、問題にはならない。 より一般的な質問として、任意の制御フローが与えられたとき、どこに、またどの変数に対して Φ 関数を挿入するべきか、という問題がある。これは難しい質問であるが、支配辺境(dominance frontier) と呼ばれる概念を用いて求める優れた方法がある。 ここで、Φ 関数は実際に実装されるものではなく、コンパイラに対して Φ 関数でグループとされる全ての変数の値をメモリやレジスタの同じ場所に配置するよう指示するマーカーである。
※この「SSA への変換」の解説は、「静的単一代入」の解説の一部です。
「SSA への変換」を含む「静的単一代入」の記事については、「静的単一代入」の概要を参照ください。
- SSA への変換のページへのリンク
