はじめに
コンパイラの最適化を調査していたときに発見した if 文の最適化(GCC編)
の LLVM についての記事となります。
サンプルコード
bool check(char c) {
return (c != 3 &&
c != 5 &&
c != 11 &&
c != 23 &&
c != 30 &&
c != 42);
}
-O0 で得られるアセンブリ(x86-64 clang 9.0.0 -O0)。
_Z5checkc: # @_Z5checkc
pushq %rbp
movq %rsp, %rbp
xorl %eax, %eax
movb %dil, -1(%rbp)
movsbl -1(%rbp), %ecx
cmpl $3, %ecx
movb %al, -2(%rbp) # 1-byte Spill
je .LBB0_6
xorl %eax, %eax
movsbl -1(%rbp), %ecx
cmpl $5, %ecx
movb %al, -2(%rbp) # 1-byte Spill
je .LBB0_6
xorl %eax, %eax
movsbl -1(%rbp), %ecx
cmpl $11, %ecx
movb %al, -2(%rbp) # 1-byte Spill
je .LBB0_6
xorl %eax, %eax
movsbl -1(%rbp), %ecx
cmpl $23, %ecx
movb %al, -2(%rbp) # 1-byte Spill
je .LBB0_6
xorl %eax, %eax
movsbl -1(%rbp), %ecx
cmpl $30, %ecx
movb %al, -2(%rbp) # 1-byte Spill
je .LBB0_6
movsbl -1(%rbp), %eax
cmpl $42, %eax
setne %cl
movb %cl, -2(%rbp) # 1-byte Spill
.LBB0_6:
movb -2(%rbp), %al # 1-byte Reload
andb $1, %al
movzbl %al, %eax
popq %rbp
retq
-O2 で得られるアセンブリ(x86-64 clang 9.0.0 -O2)。
_Z5checkc: # @_Z5checkc
addb $-3, %dil
cmpb $39, %dil
ja .LBB0_2
movabsq $549620547322, %rax # imm = 0x7FF7EFFEFA
movl %edi, %ecx
shrq %cl, %rax
andb $1, %al
retq
.LBB0_2:
movb $1, %al
retq
本最適化について
GCC 編と同様に本最適化で注目するところは、以下のアセンブリ。
movabsq $549620547322, %rax # imm = 0x7FF7EFFEFA
GCC 編と同様に上記の数値を生成する前に以下のアセンブリに注目すると、
addb $-3, %dil
のように、仮引数 c の数値を補正していることが分かります。
なので、この補正によって比較する数値は、(3、5、11、23、30、42)から(0、2、8、20、27、39)に変わります。
そして、これらの数値に対応するビットを 1 にセットすると、
となります。
よく見てみると、アセンブリで見られる数値と微妙に異なることが分かります。
LLVMは、GCC とは異なり、上記の数値に対応するビットを 1 にセットするのではなく、対応しないビットを 1 にセットしているのです。
このことを考慮すると、
となり、アセンブリで見られる数値と一致することが分かります。
そして、LLVM は、GCC と同様に得られた数値と論理演算を使用することでサンプルコードのような if 文を最適化します。
最適化後の処理の流れについては、2 パターンに分けてアセンブリにコメントで記載しています。
- c の値が 3 の場合
_Z5checkc: # @_Z5checkc
addb $-3, %dil # %dil = 3 - 3 = 0
cmpb $39, %dil
ja .LBB0_2
movabsq $549620547322, %rax # imm = 0x7FF7EFFEFA
movl %edi, %ecx # %ecx = 0
shrq %cl, %rax # %rax = 111 1111 1111 0111 1110 1111 1111 1110 1111 1010 >> 0
# = 111 1111 1111 0111 1110 1111 1111 1110 1111 1010
andb $1, %al # %al = 0
retq
.LBB0_2:
movb $1, %al
retq
- c の値が 4 の場合
_Z5checkc: # @_Z5checkc
addb $-3, %dil # %dil = 4 - 3 = 1
cmpb $39, %dil
ja .LBB0_2
movabsq $549620547322, %rax # imm = 0x7FF7EFFEFA
movl %edi, %ecx # %ecx = 0
shrq %cl, %rax # %rax = 111 1111 1111 0111 1110 1111 1111 1110 1111 1010 >> 1
# = 111 1111 1111 0111 1110 1111 1111 1110 1111 101
andb $1, %al # %al = 1
retq
.LBB0_2:
movb $1, %al
retq