SSAとはStatic Single Assignment Form、つまり静的単一代入のことです。
各変数が一度のみ代入されるよう定義されたものである。
変数は再代入できるプログラミング言語は多いです。たとえばn
というローカル変数に2回代入しているとします。SSAはこの代入(割り当て)を別々のものに変換します。それぞれn1
とn2
に割り当てたことにします。
イメージとしてはif文はどうでしょうか。
int n; if (somethingBoolean) { n = 10; } else { n = 20; } return n;
この10の割り当てと20の割り当てを、n
ではなくn1
/n2
としたということです。returnされた結果を後続のブロックが利用する場合、実行ルートによってn1
かn2
のどちらかを用います。この結果もSSAとしてn3
に割り当てたいです。このようなとき、表記としてはn3 = [n1, n2]
とします。実行時、n1の方の先行ブロックが実行されればn1
、n2の方の先行ブロックが実行されればn2
がn3に割り当てられます。n3
も単一定義できました。
この先行ブロックで実行されたものを利用するといったことは、コンパイラでどのように実現するのでしょう?ファイ関数(phi functions)と呼ばれるものを使います。ファイ関数が、先行ブロックの結果状態をマージして、次のブロックで利用できるようにします。
http://www.christianwimmer.at/Publications/Wimmer04a/Wimmer04a.pdf P.35 Figure 4.7
実際のJavaコードのHIRを見て、ファイ関数を確認してみます。
public class Factorial { public static int factorial(int n) { int p = 1; while (n > 0) { p = p * n; n = n - 1; } return p; } public static void main(String[] args) { System.out.println(factorial(10)); } }
pやnに何度も代入があります。
以前解説したCFGとc1visualizerを使います。
$ java -XX:+PrintCFGToFile -XX:CompileOnly=Factorial.factorial -Xcomp -XX:-Inline Factorial 3628800
出力された.cfgファイルをc1visualizerで見ます。HIRが対象です。
static jint Factorial.factorial(jint) Dec 18, 2017 7:08:43 PM After Generation of HIR B4 -> B5 [0, 0] Locals size 2 [static jint Factorial.factorial(jint)] 0 i4 [method parameter] _p__bci__use__tid__instruction__________________________________________________ (HIR) . 0 0 v19 std entry B5 B5 <- B4 -> B0 [0, 0] std Locals size 2 [static jint Factorial.factorial(jint)] 0 i4 _p__bci__use__tid__instruction__________________________________________________ (HIR) . 0 0 v18 goto B0 B0 <- B5 -> B1 [0, 2] std Locals size 2 [static jint Factorial.factorial(jint)] 0 i4 _p__bci__use__tid__instruction__________________________________________________ (HIR) 0 0 i5 1 . 2 0 v6 goto B1 B1 <- B0,B2 -> B3,B2 [2, 3] plh Locals size 2 [static jint Factorial.factorial(jint)] 0 i7 [i4,i13] 1 i8 [i5,i11] _p__bci__use__tid__instruction__________________________________________________ (HIR) 3 0 i9 0 . 3 0 v10 if i7 <= i9 then B3 else B2 B2 <- B1 -> B1 [6, 14] Locals size 2 [static jint Factorial.factorial(jint)] 0 i7 1 i8 _p__bci__use__tid__instruction__________________________________________________ (HIR) 8 0 i11 i8 * i7 11 0 i12 1 12 0 i13 i7 - i12 . 14 0 v14 goto B1 (safepoint) B3 <- B1 [17, 18] Locals size 2 [static jint Factorial.factorial(jint)] 1 i8 _p__bci__use__tid__instruction__________________________________________________ (HIR) . 18 0 i15 ireturn i8
plh
がついたブロックがあります。これはファイ関数があるブロックです。
B1 <- B0,B2 -> B3,B2 [2, 3] plh Locals size 2 [static jint Factorial.factorial(jint)] 0 i7 [i4,i13] 1 i8 [i5,i11] _p__bci__use__tid__instruction__________________________________________________ (HIR) 3 0 i9 0 . 3 0 v10 if i7 <= i9 then B3 else B2
i7、i8はファイ関数が適用されます。たとえばi8にはi5かi11のどちらかの値が入ります。それは、先行ブロックとしてB0とB2のどちらが実行されたかに依存します。
このHIRのCFGを見てみるとわかりやすいです。