Works by

Ren's blog

@rennnosuke_rk 技術ブログです

トップ > Golang > 【Golang】Go のSSA表現形式のダンプとその解析

【Golang】Go のSSA表現形式のダンプとその解析

Golang

SSA 形式とは

静的単一代入(static simple-assignment)形式と呼ばれ、コンパイラによって生成される中間表現のこと。 SSA は、各変数への代入が一度のみ行われる式によって構成される。

例えば、以下のような式を含むコードを見ると、一行目のコードが不要であることが明らかにわかる。ただし、プログラム上で一行目を判断するためには、 Reaching-Defenitionのような分析手法とそれを実現するアルゴリズムを実行しなければならない。

y := 1
y := 2
x := y

(上記擬似コードでは := で変数の宣言・代入を表現している。重複した宣言は許可されている)

SSA 表現形式 では、変数への代入がただ一度になるようにコードが変換される。
上記のコードは、SSA 形式の表現では以下のように表現される。

y_1 := 1
y_2 := 2
x_1 := y_2

SSA では、重複する変数には各変数を別物として扱うため添字が付与される。
上記の SSA 形式表現では y_1 が参照されないことは明らかであり、プログラム上からもデッドコードとして容易に判断できる。

ちなみに、分岐内で同じ変数への代入が発生しても、SSA 形式では別の変数への代入として表現される。分岐終了後に元の変数への参照が発生した場合は、SSA 表現内では分岐によって参照する変数を切り替える phi 関数（実際には条件によって切り替わるマーカー）を参照する。

x := 1
if x > 2 {
    x := 2
} else {
    x := x + 1
}
y := x * 2
x := y
x_1 := 1
if x_1 > 2 {
    x_2 := 2
} else {
    x_3 := x_1 + 1
}
y_1 := phi(x_2, x_3) * 2
x_4 := y_1

この SSA 形式表現は、上記のデッドコードの発見・削除のようなコンパイラ最適化処理のために利用できる。
Go においても、この中間表現によるコンパイル最適化が行われている。

Go コードから SSA 形式表現を出力する

Go による SSA 形式出力は Go1.7 よりサポートされた。

  • GOSSAFUNC 環境変数を変更して go build
  • go tool compile オプション指定

のどちらかを実行すると、SSA 形式表現を記述したファイルをダンプすることができる。

GOSSAFUNC 環境変数を変更して go build する

GOSSAFUNC 環境変数にターゲットとなる関数を指定して .go ファイルをビルドすると、 .html 形式の SSA 形式表現ファイルが得られる。

$ env GOSSAFUNC=[関数名] go build main.go

この html ファイルには標準の SSA 形式表現のほか、最適化後の SSA 形式表現なども描画されている。

go tool compile オプションを指定する

go tool compile のオプション 'ssa' を指定することでも SSA 形式を出力できる。

$ go tool compile -d 'ssa/build/dump=main' main.go

ssa/help を指定することで、オプションの使用方法を確認できる。

$ go tool compile -d 'ssa/help'
compile: PhaseOptions usage:

    go tool compile -d=ssa/<phase>/<flag>[=<value>|<function_name>]

where:

- <phase> is one of:
    check, all, build, intrinsics, number_lines, early_phielim
    early_copyelim, early_deadcode, short_circuit, decompose_args
    decompose_user, opt, zero_arg_cse, opt_deadcode, generic_cse, phiopt
    nilcheckelim, prove, fuse_plain, decompose_builtin, softfloat, late_opt
    dead_auto_elim, generic_deadcode, check_bce, branchelim, fuse, dse
    writebarrier, insert_resched_checks, lower, lowered_cse
    elim_unread_autos, lowered_deadcode, checkLower, late_phielim
    late_copyelim, tighten, late_deadcode, critical, phi_tighten
    likelyadjust, layout, schedule, late_nilcheck, flagalloc, regalloc
    loop_rotate, stackframe, trim

- <flag> is one of:
    on, off, debug, mem, time, test, stats, dump

- <value> defaults to 1

- <function_name> is required for the "dump" flag, and specifies the
  name of function to dump after <phase>

Phase "all" supports flags "time", "mem", and "dump".
Phase "intrinsics" supports flags "on", "off", and "debug".

If the "dump" flag is specified, the output is written on a file named
<phase>__<function_name>_<seq>.dump; otherwise it is directed to stdout.

Examples:

    -d=ssa/check/on
enables checking after each phase

    -d=ssa/all/time
enables time reporting for all phases

    -d=ssa/prove/debug=2
sets debugging level to 2 in the prove pass

Multiple flags can be passed at once, by separating them with
commas. For example:

    -d=ssa/check/on,ssa/all/time

例えば、 'ssa/build/dump=[関数名]' を指定して、SSA 形式表現のダンプファイル( .dump )を得る。

$ go tool compile -d 'ssa/build/dump=main' main.go
$ ls
main.go              main.o               main_01__build.dump

'ssa/opt/dump=[関数名]' を指定すると、最適化後の SSA 形式表現のダンプファイル() .dump )を得られる。

Go の SSA を解析する

実際に、SSA 形式表現の Go コードをダンプしてその中身を見てみる。

hoge.go

package hoge

func hoge() int {
  x := 1
  return x
}

用意したのは素朴な関数一つを宣言した .go ファイル。
関数 hoge 内では変数 x を宣言、 整数 1 を代入し関数の返戻値としている。
この関数のダンプを取ると以下のようになる。

hoge func() int
  b1:                                   // ブロックラベル
    v1 = InitMem <mem>                  // ヒープメモリ領域の初期化。先頭アドレスがv1に格納される。
    v2 = SP <uintptr>                   // スタックポインタ（スタックの先頭アドレス）
    v3 = SB <uintptr> DEAD              // スタックベース（スタックの底アドレス。デッドコード）
    v4 = LocalAddr <*int> {~r0} v2 v1   // int型のローカルアドレス : v2上にマウントされる。{~r0}は結果を格納する変数
    v5 = Const64 <int> [0] DEAD         // int型定数 (x := 1のうち 宣言 var x; の部分。デッドコード)
    v6 = Const64 <int> [1] (x[int])     // int型定数 (x := 1のうち 代入 x = 1; の部分。)
    v7 = VarDef <mem> {~r0} v1          // 新規変数{~r0}を定義。参照先はv1
    v8 = Store <mem> {int} v4 v6 v7     // v7上のメモリでv6 を v4に格納する。該当するアドレスがv8に格納される。
    Ret v8

上記 SSA の変数のうち、 v3 v5 は使われていないためデッドコード扱いとなっている。
デッドコードを削除し、最適化された SSA 形式表現は以下のようになる。

hoge func() int
  b1:
    v1 = InitMem <mem>
    v2 = SP <uintptr>
    v4 = LocalAddr <*int> {~r0} v2 v1
    v6 = Const64 <int> [2] (x[int])
    v7 = VarDef <mem> {~r0} v1
    v8 = Store <mem> {int} v4 v6 v7
    Ret v9

表現形式こそ異なれど、処理の流れは Go バイナリと同じなのでバイナリ実行時も同様の最適化が行われている。
このように、最適化前後の SSA 形式表現を比較することでどの処理が最適化されているのか把握できる。

試しに、 hoge.go を以下のように改変してみる。

package hoge

func hoge() int {
  x := 1
  x = 2
  return x
}

明らかに、 x := 1 における代入部分が無駄なことがわかる。
SSA に起こすと以下のようになる。

hoge func() int
  b1:
    v1 = InitMem <mem>
    v2 = SP <uintptr>
    v3 = SB <uintptr> DEAD                // デッドコード
    v4 = LocalAddr <*int> {~r0} v2 v1
    v5 = Const64 <int> [0] DEAD           // x = 0 (x := 1 の宣言、デッドコード)
    v6 = Const64 <int> [1] (x[int]) DEAD  // x = 1 (x := 1 の代入、デッドコード)
    v7 = Const64 <int> [2] (x[int])       // x = 2
    v8 = VarDef <mem> {~r0} v1
    v9 = Store <mem> {int} v4 v7 v8
    Ret v9

代入 x = 2 が一つ増えていることがわかる。
また x = 2 によって x = 1 の代入がデッドコードになっている。
これを最適化すると、

hoge func() int
  b1:
    v1 = InitMem <mem>
    v2 = SP <uintptr>
    v4 = LocalAddr <*int> {~r0} v2 v1
    v7 = Const64 <int> [2] (x[int])
    v8 = VarDef <mem> {~r0} v1
    v9 = Store <mem> {int} v4 v7 v8
    Ret v9

のように変数ラベルこそ異なるものの同じ最適化結果となる。

参考文献