Scheme Compiler の勉強(16) - SSA

scheme

いよいよ 1.4 Conditional Expressions の実装。そのまえに SSA についてメモ。

Redhat の GCC に関する文書 http://www.jp.redhat.com/magazine/NO5/

静的単一代入（SSA）
静的単一代入形式は、GIMPLE上に構築される表現で、プログラム内のデータの流れを非常に明示的に明らかにします。中心となるアイデアはバージョニングというアイデアです。変数Xに新しい値が代入されるたびに、コンパイラによりXの新しいバージョンが生成されます。次に変数Xが使用されるときには、コンパイラにより最新のバージョンのXが調べられ、使用されます。

ほほう。これが、わたしのトイプログラムが吐き出す以下のようないっさい最適化なんて考えていない LLVM IR でさえも、ちゃんと opt コマンドによって最適化される理由か（もっと他のレベルで根本的に間違ってるかもしれないけど・・）。

gosh> (compile-program '($fxadd1 ($fxadd1 ($fxadd1 ($fxadd1 1)))))
define i32 @scheme_entry() nounwind {
entry:
    %ret = alloca i32
    store i32 4, i32* %ret
    %var7 = load i32* %ret
    %var8 = add i32 4, %var7
    store i32 %var8, i32* %ret
    %var5 = load i32* %ret
    %var6 = add i32 4, %var5
    store i32 %var6, i32* %ret
    %var3 = load i32* %ret
    %var4 = add i32 4, %var3
    store i32 %var4, i32* %ret
    %var1 = load i32* %ret
    %var2 = add i32 4, %var1
    store i32 %var2, i32* %ret
    %retval = load i32* %ret
    ret i32 %retval
}

続き。

では、変数の最新のバージョンが何であるか決められないときには、どうなるのでしょう。実際のプログラムは、直線的に順番に実行されるコードであることはほとんどなく、制御の流れを変えるループや条件文を含みます。たとえば、次のプログラムでは、プログラムの実行時に条件文よる分岐がどうなるのか、コンパイラが判断することは不可能です。

プログラムをSSA形式に変換しようとするとき、コンパイラは変数aの2つのバージョンのどちらを使用すべきか判断できません。このあいまいさを解消するために、2つの矛盾するバージョンをマージした3番目のバージョンが生成されます。このマージ操作は、次のPHI関数として知られています。

そして、LLVM のチュートリアル。
http://llvm.org/docs/tutorial/LangImpl5.html

The answer to this question involves an important SSA operation: the Phi operation. If you're not familiar with SSA, the wikipedia article is a good introduction and there are various other introductions to it available on your favorite search engine. The short version is that "execution" of the Phi operation requires "remembering" which block control came from. The Phi operation takes on the value corresponding to the input control block. In this case, if control comes in from the "then" block, it gets the value of "calltmp". If control comes from the "else" block, it gets the value of "calltmp1".

At this point, you are probably starting to think "Oh no! This means my simple and elegant front-end will have to start generating SSA form in order to use LLVM!". Fortunately, this is not the case, and we strongly advise not implementing an SSA construction algorithm in your front-end unless there is an amazingly good reason to do so. In practice, there are two sorts of values that float around in code written for your average imperative programming language that might need Phi nodes:

Code that involves user variables: x = 1; x = x + 1;
Values that are implicit in the structure of your AST, such as the Phi node in this case.

ん、ちょっとちゃんと読まないといけなさそうだ。