はじめに

コンパイラの最適化を調査していたときに発見した 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

関係する記事

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