GoのSSA最適化制御オプション

Go2 Advent Calendar 2017 14日目の記事です。
昨日空きを見つけたので代筆させていただきます。

Qiita初投稿となります。お手柔らかにお願い致します。

はじめに

今更ですが、1.7からGoのコンパイラにはSSA最適化が導入されました。
https://golang.org/doc/go1.7#compiler

そしてあまり知られていませんが、1.7からGoにはSSA最適化の各フェーズを制御するオプションが用意されています。

おそらくGoのコンパイラをいじる人くらいしか使わないと思いますが、何かの役に立つかもしれませんのでまとめておきます。

なお、このオプションはGoコンパイラのinternalなパッケージの実装を参考にしながら調査をしたものなので、将来のGoでは変更される可能性があります。ご注意ください。

では、オプションを見ていこうと思います。

その前にSSAってなんですか？

はい。私も知りませんでした。

SSAというより、SSA形式と言ったほうが正確かもしれません。 SSA形式(Static Single Assignment Form)とは、コンパイラが利用する中間表現の1つで、コンパイラがソースコードをマシン語に変換する過程で利用されます。

コンパイラが内部で扱うデータ構造としては抽象構文木(AST, Abstract Syntax Tree)が有名ですが、これは最適化を行うには複雑な構造となっています。またマシン語自体を最適化するというのも情報が欠落しており最適化には不向きです。(私の理解です）

SSA形式を導入することでシンプルな最適化アルゴリズムが開発しやすくなるという事のようです。

Wikipedia 静的単一代入に載っている例を示します。

x := 2
x := 3
y := x

3行の代入文があり、1行目の代入した値は、2行目の代入で上書きされています。そして上書きされた値を3行目でyにxの値を代入しています。2行目で上書きされるので、1行目の代入文がなくてもyの最終的な値には影響がありません。コンパイラとしては1行目のような不要なコードを削除したいわけですが、それを検知するのは意外と難しいです。「1行目で代入された値が、2行目で別の値に書き換わっているので、1行目は不要」といったように変数のデータの流れを追う必要があります。

これをSSA形式に変換して考えてみます。SSA形式はその名の通り変数に対する代入文が1回に限定されます（代入が1回ではありません）。つまり代入文ごとに新たな変数が用意されます。

x1 := 2
x2 := 3
y1 := x2

こうすると変換前はデータの流れを考慮する必要がありましたが、SSA形式では「x1はどこからも利用されていないので不要」と判断できます。

このようにSSA形式に変換することで最適化を比較的単純なアルゴリズムで実現できます。不要コード削除以外にも、共通部分式除去、レジスタ割り付け最適化などのアルゴリズムがあります。

なおSSA形式はGo言語で初めて考えられたものではなく他の言語でも利用されています。Wikipediaによると、1988年にIBMの方などが発表され、今日のコンパイラではLLVM、Java (JIT Compiler)、WebKit、Swiftなどでも利用されています。日本ではCOINSプロジェクトが有名です。¹

SSA最適化の過程を見る

最適化オプションの前に、SSA形式の最適化の様子を見る方法を書いておきます。

 $ env GOSSAFUNC=hoge go build hoge.go

とすることで、ssa.htmlというファイルが生成されます。
これを開くと各フェーズを適用した過程を見ることができます。

こちらの記事が詳しいです。

Looking at your program’s structure in Go 1.7

では最適化制御オプションについて

$ go tool compile -d ssa/help

と入力してみてください。以下は、Go1.12の出力です。(Go1.9より読みやすくなりました。）

$ 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, phi_tighten, late_deadcode, critical
    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最適化の各フェーズ（アルゴリズム）の実施有無、計算時間表示、メモリ使用量表示の指定方法です。

例えば、

go tool compile -d 'ssa/early_phielim/off' hoge.go

とすれば、early_phielimというフェーズが行われなくなります。

go build 等で使うときは、

go build -gcflags='-d ssa/early_phielim/off' hoge.go

とすれば指定できます。

また、次のようにカンマ区切りすることで、複数のフェーズに対して指定することもできます。

go compile -d 'ssa/early_phielim/off,ssa/generic_cse/off' hoge.go

最適化制御オプションは、これだけといえばそうなのですが、ここで終わるとあまりにあっさりしてしまうので注意点などをまとめておきます。

phase

phaseには最適化アルゴリズムの名称か特別な名称を指定します。以下の4つは特別な用途に使うものです。

• check 各フェーズの適用後にSSA形式のチェックを行います
• all 全てのフェーズに対して指定します
• build SSA形式に変換した直後の状態(どのフェーズも通っていない最適化されていない状態)に対して指定します
• intrinsics いくつかの標準パッケージの関数呼び出しをSSA形式にするかどうかを指定します

それぞれ見ていきます。

check

最適化フェーズ適用後にSSA形式の正当性をチェックします。デフォルトではチェックしません。

• チェック内容は以下をご覧ください。

• ssa/check.go

• 使用例：チェックをonにする。

$ go tool compile -d 'ssa/check/on' hoge.go

all

全てのフェーズに対して何らかの指示するときに使います。ただし、on/offは利用できずtime/ mem / dump に限られます。

• 使用例：各フェーズにかかった時間を表示する

$ go tool compile -d 'ssa/all/time' hoge.go

build

最適化前のSSA形式に対する指定です。debug / test / stat / dumpを指定できますが、実際に効くのはGo1.12ではdumpだけのようです。

• ssa/compile.go#L309
• 使用例：最適化前のSSA形式をダンプする。
• ダンプの場合関数名の指定が必要です。実行するとダンプファイルが生成されます。

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

intrinsics

標準パッケージのいくつかは関数呼び出しではなくSSA形式にインラインに変換されます。これを制御できます。変換対象の関数は以下に書かれています。

• gc/ssa.go#L2870
• 使用例：
• 次のような関数があったとします。(代入文で十分なのですが例ということでご容赦ください。)

package main

import "sync/atomic"

func main() {
    var a int64 = 1

    atomic.StoreInt64(&a, 2)
}

main関数を先ほどのbuildフェーズでダンプすると以下のような出力が得られます。

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

ダンプ結果

main func()
  b1:
    v1 = InitMem <mem>
    v2 = SP <uintptr>
    v3 = SB <uintptr>
    v4 = OffPtr <**byte> [0] v2
    v5 = Addr <*uint8> {type.int64} v3
    v6 = Store <mem> {*byte} v4 v5 v1
    v7 = StaticCall <mem> {runtime.newobject} [16] v6
    v8 = OffPtr <**int64> [8] v2
    v9 = Load <*int64> v8 v7 (&a[*int64])
    v10 = Const64 <int64> [1]
    v11 = Store <mem> {int64} v9 v10 v7
    v12 = Const64 <int64> [2]
    v13 = AtomicStore64 <mem> v9 v12 v11
    Ret v13
name &a[*int64]: [v9]

v13を見ると、AtomicStore64という命令が出力されています。

intrinsicsフェーズをoffとすると、このような最適化はされず関数呼び出しになっています。

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

ダンプ結果

main func()
  b1:
    v1 = InitMem <mem>
    v2 = SP <uintptr>
    v3 = SB <uintptr>
    v4 = OffPtr <**byte> [0] v2
    v5 = Addr <*uint8> {type.int64} v3
    v6 = Store <mem> {*byte} v4 v5 v1
    v7 = StaticCall <mem> {runtime.newobject} [16] v6
    v8 = OffPtr <**int64> [8] v2
    v9 = Load <*int64> v8 v7 (&a[*int64])
    v10 = Const64 <int64> [1]
    v11 = Store <mem> {int64} v9 v10 v7
    v12 = OffPtr <**int64> [0] v2
    v13 = Store <mem> {*int64} v12 v9 v11
    v14 = OffPtr <*int64> [8] v2
    v15 = Const64 <int64> [2]
    v16 = Store <mem> {int64} v14 v15 v13
    v17 = StaticCall <mem> {sync/atomic.StoreInt64} [16] v16
    Ret v17
name &a[*int64]: [v9]

• 今の所、特定の組み込み関数を指定してoffにすることはできないようです。

他

上記の特殊なフェーズ以外は実際の最適化アルゴリズムの名前を指定します。

名称は上で示したヘルプでも確認できますが、コードでも確認できます。（ヘルプの一部はここから自動生成されています）

• ssa/compile.go#379
• 一部フェーズが　required:true となっていますが、これらは off にはできません　（decompose user, optなど）。試しにrequire:falseでGoをコンパイルしたところ、Goのビルドのテストでコケました。
• また、フェーズを~から始めることで正規表現としてフェーズをまとめて指定もできます。
• 使用例： 各CSE(Common Subexpression Elimination)の時間を計測

go test -gcflags='-d=ssa/~^.*cse/time' -bench .

flag

flagは、フェーズに対しての動作を指定します。

• on フェーズを実行します
• off フェーズを実行しません (一部フェーズではoffを利用できません）
• debug デバッグレベルを指定します。ログが出力されるようになります。レベルは各フェーズごとに解釈が異なります。コンパイラのデバッグレポート用でしょうか。
• mem フェーズのメモリ使用量を表示します
• time フェーズの実行時間を表示します。
• test コンパイラ開発に便利なのだそうです(ssa/compile.go#L173)。Go1.12では、ssa/layout.go#19で使われています。
• stats 各フェーズの統計情報が出力されるようです。これもコンパイラ開発用と思います。3つのフェーズで使われていました（cse、likelyadjus、stackalloc）。また、出力をawkでパースする方法が書かれています。ssa/func.go#L212
• dump 各フェーズで変換された後のSSA形式をファイルにダンプします。ダンプには関数名の指定が必要です。

value

先ほどのflagsで説明した、debug / test / stats などで使用するようです。デフォルトが1なので、明示的に書かなくてもある程度は出力されます。詳細は各phaseを確認してください。

function_name

dumpで使用します。

まとめ

• Goにはコンパイラ開発者のために、SSA最適化の隠しオプションが用意されていることがわかりました。
• 一部フェーズについてはoffを指定できませんので、SSA最適化を全てoffにしてビルドすることはできません。
• Goコンパイラをいじるときや自分のGoプログラムが正しいはずなのにおかしな動作をしている時の調査などにお使いください。

ちなみに、私はベンチマークを結果を調査するときに少しだけ使いました。

この記事を読んでコンパイラに少しでも興味を持っていただければ幸いです。

それでは、良いお年を。

1. COINSコンパイラ・インフラストラクチャ http://coins-compiler.osdn.jp/ ↩