Go言語のコンパイラは内部表現として SSA 形式を利用しており、様々な最適化パスを適用しています。
最適化パスのうち、shortcircuitパスのコードが比較的短かったので解説してみます。
なお、確認したソースコードは、go1.12 のものです。
shortcircuit最適化パス
short circuitパスは、ssa/shortcircuit.go で定義されている最適化パスで、このパスを適用することで制御フローの冗長な遷移を取り除くことができます。
shortcircuitは、アーキテクチャ独立の表現に対して適用されます。
この最適化パスは、2つのステップからなります。(コード上では3ステップで記載されているが、実質的には2ステップ）
-
ある条件を満たす
OpPhi(Phi関数に対応するOp)の引数をtrueまたはfalseに置き換える。 -
ステップ1の結果、
p -> b -> tのような間接的な遷移を、p -> tのような形の遷移に変換できるものが現れるため、これを置き換えます。(といってもb -> tの遷移が消えるわけではない)
ステップ1: If ブロックの制御値に対応する最適化
以下のような、 If ブロックの制御値 (b1.Control つまり v1) をb1の後続ブロックの OpPhi で利用しているケースでは、OpPhi の引数のうち、ブロック b1 に対応する引数を、定数 true または false で置き換えることができます。
正確には (OpConstBool <bool> [1または0]) で置き換えますが、煩雑なので true false で記載します。
具体例として、下記のSSAを考えます。
// 最適化前のSSA
b1:
...
If v1 -> bThen bElse // v1 が true なら bThen に遷移、false なら bElseに遷移
bThen:
...
v2 = OpPhi v1, ... // 前提: v1 には b1 が対応している
...
bElse:
...
v3 = OpPhi v1, ...
b1 から bThen ブロックに制御が移った場合、v1は true なので、
OpPhi の引数のうち、b1 ブロックに対応する値を true で置き換えてもよいことになります。
※Phi関数は、先行節ごとに利用する値を保持しています。
else 節でも同様の議論が行えて、この場合は false で置き換えることができます
bThen:
...
v2 = OpPhi true, ... // true で置き換える
...
bElse:
...
v3 = OpPhi false, ... // false で置き換える
...
ステップ2: 間接的なブロック遷移の短絡
前処理: ブロックをまたがるSSA値のチェック
前準備として、SSA値の引数とブロックの制御値のうちブロックをまたがる引数をメモしておきます。
ここで、ブロックをまたがるとは SSA値 v の引数 a が所属するブロックが、vのブロックと異なることを指します。
ブロックの制御値については、v.Control.Block != v.Block となるケースをブロックをまたがるとします。
ソースコード上ではブロックをまたがるSSA値について、live[v.ID] = true と設定します。
短絡できるブロックの条件
このステップで最適化するには、ブロックが下記の条件を全て満たしている必要があります。
-
b.KindがBlockIf -
b.Valuesが1つだけで、そのSSA値vがOpPhi -
vがほかのブロックで利用されていない (前処理で求めたlive[v.ID]が false) -
v.Argsの中に、trueまたはfalseを含む。(v.Args[i].Op == ConstBool)
ステップ1 の最適化の結果、最後の条件を満たすケースがあるため、ステップ3 に先んじてステップ1 を適用しています。
p:
goto b // If など
b:
v1 = OpPhi(..., true, ...) // 前提:
// v1 は、ほかのブロックで利用されていない
// true は先行ブロック p に対応する
If v1 -> then else
上記の例で ブロック p から b に遷移する場合は、v1 は true なので、
この遷移でブロック b に到達した場合は、b での分岐は常に then になります。
つまり、p から b を経由せずに直接 then に遷移してもよいわけです。
なお、遷移先を変えることで、b の先行ブロックが一つ減るので、
v の OpPhi の引数のうち p に対応する引数を減らす必要があります。
p:
goto then // 遷移先を b から then に変更(短絡)
b:
v1 = OpPhi(..., ...) // 先行ブロック p が取り除かれるので、1つ引数が減る
// p
If v1 then else
OpPhi が OpCopy になるケース
もし、最適化前の OpPhi の引数が2つ（つまり、bの先行ブロックが2つ)のケースでは、 最適化後の OpPhi を OpCopy に置き換えます。
例えば以下のケースでは 変換後のOpPhi は OpCopy に変化します。
p:
goto b
b:
v1 = OpPhi(true, v) // p に対応する引数が true
// p
If v1 then else
最適後のSSAは以下のようになります。
p:
goto then
b:
v1 = OpCopy(v)
If v1 then else
具体例
func f(a int) int {
cond := a == 0 || a == 1
if cond {
return 0
}
return 1
}
以下のようにコンパイルすると、ssa.htmlが作成されるのでこのファイルをブラウザで開くと、
各最適化パスでのSSA表現を表示できます。
$ GOSSAFUNC=f go tool compile sample.go
ssa.html で、short circuitと、その直前の early deadcode を比較してみると、以下のように最適化されていることがわかります。
- 最適化前のブロック
b3のv12はOpPhiで、その最初の引数v8は Ifブロックであるb1のControlになっています。
そこでv8をtrue(v17 = ConstBool <bool> [true])で置き換えます。
(ステップ1 と ステップ2 は、short circuit の中で適用されるため、ステップ1適用直後のSSA表現は確認できません) - その結果、
b2はステップ2の条件を満たすため、b1の後続ブロックのb3を、b4で置き換えます。v12は、2引数のOpPhiだったので、OpCopyに変換されます。
最適化前 最適化後
b1: b1:
v1 (?) = InitMem <mem> v1 (?) = InitMem <mem>
v2 (?) = SP <uintptr> v2 (?) = SP <uintptr>
v5 (?) = LocalAddr <*int> {~r1} v2 v1 v5 (?) = LocalAddr <*int> {~r1} v2 v1
v6 (3) = Arg <int> {a} (a[int]) v6 (3) = Arg <int> {a} (a[int])
v7 (?) = Const64 <int> [0] v7 (?) = Const64 <int> [0]
v8 (+4) = Eq64 <bool> v6 v7 v8 (+4) = Eq64 <bool> v6 v7
v10 (?) = Const64 <int> [1] v10 (?) = Const64 <int> [1]
v16 (?) = Const64 <int> [2] v16 (?) = Const64 <int> [2]
If v8 → b3 b2 (4) v17 (?) = ConstBool <bool> [true]
If v8 → b4 b2 (4)
b2: ← b1 b2: ← b1
v11 (+4) = Eq64 <bool> v6 v10 v11 (+4) = Eq64 <bool> v6 v10
Plain → b3 (4) Plain → b3 (4)
b3: ← b1 b2 b3: ← b2
v12 (4) = Phi <bool> v8 v11 (cond[bool]) v12 (4) = Copy <bool> v11 (cond[bool])
If v12 → b4 b5 (+5) If v12 → b4 b5 (+5)
b4: ← b3 b4: ← b3 b1
v14 (6) = VarDef <mem> {~r1} v1 v14 (6) = VarDef <mem> {~r1} v1
v15 (+6) = Store <mem> {int} v5 v10 v14 v15 (+6) = Store <mem> {int} v5 v10 v14
Ret v15 (+6) Ret v15 (+6)
b5: ← b3 b5: ← b3
v18 (8) = VarDef <mem> {~r1} v1 v18 (8) = VarDef <mem> {~r1} v1
v19 (+8) = Store <mem> {int} v5 v16 v18 v19 (+8) = Store <mem> {int} v5 v16 v18
Ret v19 (+8) Ret v19 (+8)