はじめに
本投稿は、以前勤めていた会社で OpenFOAM の実行性能を向上させるために GCC、LLVM が出力するアセンブリを解析していた際に見つけた if 文の最適化をまとめたものであり、また自分の備忘録でもあるので、説明が分かりづらい部分もあるかと思いますがご承知ください。
なお、LLVM の方については別に投稿します。
サンプルコード
実コードは忘れてしまった（探すのがメンドイ。。。）ので、以下に似たようなコードを載せています。
そもそも OpenFOAM も随時バージョンアップされていると思うので、以下のようなコードが最新バージョンにあるのかは不明・・・。
※ if 文の最適化と言いながら、if 文が存在しないですが、内部処理的に if 文があります。
bool check(char c) {
return (c != 3 &&
c != 5 &&
c != 11 &&
c != 23 &&
c != 30 &&
c != 42);
}
上記のコードを -O0 で翻訳すると以下のようなアセンブリ（x86-64 GCC 9.2 -O0）が生成されます。
※ 最適化していないので、冗長で読みづらいです（汗）
_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）を生成します。
※ -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）から生成されています。
return (c != 3 &&
c != 5 &&
c != 11 &&
c != 23 &&
c != 30 &&
c != 42);
では、生成方法についてですが、これらの数値に対応するビットを 1 にセットし、それを 10 進数に変換してみてください。
※ 3 なら、最下位ビット（0番目とする）をから数えて 3 番目を 1 にセット。
上記の画像の 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 文などの分岐の最適化をする場合、論理演算に変換することが経験上多かったので、分岐の最適化を調査される（あまりないとは思いますが。。。）場合は、上記のような観点で見ると良いかもしれません。