SSA: 静的単一代入

SSAとはStatic Single Assignment Form、つまり静的単一代入のことです。

各変数が一度のみ代入されるよう定義されたものである。

静的単一代入 - Wikipedia

変数は再代入できるプログラミング言語は多いです。たとえば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を見てみるとわかりやすいです。