コンパイラの最適化を調査していたときに発見した if 文の最適化 (GCC編)

# はじめに
本投稿は、以前勤めていた会社で [OpenFOAM](https://www.openfoam.com/) の実行性能を向上させるために GCC、LLVM が出力するアセンブリを解析していた際に見つけた if 文の最適化をまとめたものであり、また自分の備忘録でもあるので、説明が分かりづらい部分もあるかと思いますがご承知ください。
なお、LLVM の方については別に投稿します。

# サンプルコード
実コードは忘れてしまった（探すのがメンドイ。。。）ので、以下に似たようなコードを載せています。
そもそも OpenFOAM も随時バージョンアップされていると思うので、以下のようなコードが最新バージョンにあるのかは不明・・・。
※ if 文の最適化と言いながら、if 文が存在しないですが、内部処理的に if 文があります。

```cpp
bool check(char c) {
    return (c != 3 &&
            c != 5 &&
            c != 11 &&
            c != 23 &&
            c != 30 &&
            c != 42);
}
```

上記のコードを -O0 で翻訳すると以下のようなアセンブリ（[x86-64 GCC 9.2 -O0](https://godbolt.org/z/mvm8AN)）が生成されます。
※ 最適化していないので、冗長で読みづらいです（汗）

```
_Z5checkc:
        pushq   %rbp
        movq    %rsp, %rbp
        movl    %edi, %eax
        movb    %al, -4(%rbp)
        cmpb    $3, -4(%rbp)
        je      .L2
        cmpb    $5, -4(%rbp)
        je      .L2
        cmpb    $11, -4(%rbp)
        je      .L2
        cmpb    $23, -4(%rbp)
        je      .L2
        cmpb    $30, -4(%rbp)
        je      .L2
        cmpb    $42, -4(%rbp)
        je      .L2
        movl    $1, %eax
        jmp     .L3
.L2:
        movl    $0, %eax
.L3:
        popq    %rbp
        ret
```

上記のコードを GCC は最適化し、以下のようなアセンブリ（[x86-64 GCC 9.2 -O2](https://godbolt.org/z/myg6D-)）を生成します。
※ -O2 で最適化していますが、-O1 でも同様なアセンブリが生成されます。

```
_Z5checkc:
        movl    $1, %eax
        cmpb    $42, %dil
        ja      .L1
        movabsq $4399128643624, %rax
        movl    %edi, %ecx
        shrq    %cl, %rax
        notq    %rax
        andl    $1, %eax
.L1:
        ret
```

最適化しなかった場合のアセンブリでは、cmp-jmp 命令が連発されていますが、最適化すると cmp-jmp 命令が 1 つだけとなります。

# 本最適化について
本最適化で注目するところは、以下のアセンブリ。

```
        movabsq $4399128643624, %rax
```

この数値はサンプルコードを見たところ、どこにも存在しません。
では、上記の数値は何を元に生成されるのか？についてですが、
これは仮引数 c と比較している数値（以下の3、5、11、23、30、42）から生成されています。

```cpp
    return (c != 3 &&
            c != 5 &&
            c != 11 &&
            c != 23 &&
            c != 30 &&
            c != 42);
```

では、生成方法についてですが、これらの数値に対応するビットを 1 にセットし、それを 10 進数に変換してみてください。
※ 3 なら、最下位ビット（0番目とする）をから数えて 3 番目を 1 にセット。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/513813/b4870d5f-c11b-ea1a-53ce-aacb9d6efcf7.png)

上記の画像の DEC（10進数）の部分を見ると、さきほどのアセンブリで見られる数値と一致することが分かります。
そして、GCCは、得られた数値と論理演算を使用することでサンプルコードのような if 文を最適化します。

最適化後の処理の流れについては、2 パターンに分けてアセンブリにコメントで記載しています。

* c の値が 3 の場合

```
_Z5checkc:
        movl    $1, %eax
        cmpb    $42, %dil             # %dil = 3
        ja      .L1
        movabsq $4399128643624, %rax
        movl    %edi, %ecx            # %ecx = 3
        shrq    %cl, %rax             # %rax = 100 0000 0000 0100 0000 1000 0000 0000 1000 0010 1000 >> 3
                                      #      = 100 0000 0000 0100 0000 1000 0000 0000 1000 0010 1
        notq    %rax                  # %rax = 011 1111 1111 1011 1111 0111 1111 1111 0111 1101 0
        andl    $1, %eax              # %eax = 0
.L1:
        ret
```

* c の値が 4 の場合

```
_Z5checkc:
        movl    $1, %eax
        cmpb    $42, %dil             # %dil = 4
        ja      .L1
        movabsq $4399128643624, %rax
        movl    %edi, %ecx            # %ecx = 4
        shrq    %cl, %rax             # %rax = 100 0000 0000 0100 0000 1000 0000 0000 1000 0010 1000 >> 4
                                      #      = 100 0000 0000 0100 0000 1000 0000 0000 1000 0010
        notq    %rax                  # %rax = 011 1111 1111 1011 1111 0111 1111 1111 0111 1101 
        andl    $1, %eax              # %eax = 1
.L1:
        ret
```

# 最後に
コンパイラが if 文などの分岐の最適化をする場合、論理演算に変換することが経験上多かったので、分岐の最適化を調査される（あまりないとは思いますが。。。）場合は、上記のような観点で見ると良いかもしれません。

# 関係する記事
[コンパイラの最適化を調査していたときに発見した if 文の最適化 (LLVM編)](https://qiita.com/garigari334/items/44918727974733b61b23)