Goの shortcircuit 最適化パスを読んだので解説する

Go言語のコンパイラは内部表現として SSA 形式を利用しており、様々な最適化パスを適用しています。
最適化パスのうち、shortcircuitパスのコードが比較的短かったので解説してみます。

なお、確認したソースコードは、go1.12 のものです。

[ssa/shortcircuit.go](https://github.com/golang/go/blob/release-branch.go1.12/src/cmd/compile/internal/ssa/shortcircuit.go)

# shortcircuit最適化パス

`short circuitパス`は、`ssa/shortcircuit.go` で定義されている最適化パスで、このパスを適用することで制御フローの冗長な遷移を取り除くことができます。
shortcircuitは、アーキテクチャ独立の表現に対して適用されます。


この最適化パスは、2つのステップからなります。(コード上では3ステップで記載されているが、実質的には2ステップ）

1. ある条件を満たす`OpPhi` (Phi関数に対応する`Op`)の引数を `true` または `false` に置き換える。

2. ステップ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 に変化します。


```:最適化前：OpPhiの引数が2つの場合
p:
    goto b
b:
    v1 = OpPhi(true, v)  // p に対応する引数が true
    //         p
 If v1 then else
```

最適後のSSAは以下のようになります。

```:最適化後：OpPhiの引数が2つの場合
p:
   goto then
b:
    v1 = OpCopy(v)
 If v1 then else
```


 
## 具体例

```go:sample.go
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)

```