コグノスケ

GCCを調べる - memmoveのfoldingその1

目次: GCC

GCCのmemmoveに対する最適化とバグっぽい挙動についてのメモです。半年経ったら絶対忘れてわからなくなる自信があるので、書き残しておきます。

検証に使用するのは下記のプログラムです。"AB0123456789abcdefg" が格納された配列sから、同じ配列sに2文字だけずらしてmemmove() します。期待値は先頭2文字が消えた "0123456789abcdefg" です。このプログラムはmemmove() を使う必要があります。memcpy() はコピー元（src）とコピー先（dst）が重複したメモリ領域だと正常に動作しないことがあるからです。

#include <stdio.h>
#include <string.h>

#define PRE "AB"
#define STR "0123456789abcdefg"
#define NOP __asm__ volatile("nop;")

int main(int argc, char *argv[])
{
	volatile char s[] = PRE STR;
	char *p = (char *)s;
	size_t sz_pre = strlen(PRE);
	size_t sz = strlen(p) - sz_pre + 1;

	NOP;
	memmove(p, p + sz_pre, sz);
	NOP; NOP;

	if (strcmp(p, STR) == 0) {
		printf("  OK: %s\n", p);
	} else {
		printf("  NG: %s\n", p);
	}
}

$ gcc -O2 -Wall -g test.c

$ ./a.out
  NG: 01234567abcdefg

しかし、実行してみると期待値と一致しません。真ん中の "89" がどこかに消えました。また配列sの宣言からvolatileを削除すると、正常に動作するようになります。一体、何が起きているのでしょうか？

GCCのアグレッシブな最適化

GCCはある条件下でmemmove() を __builtin_memcpy() に置き換えるという最適化を行います。その様子を観察するために、オプション --dump-tree-allを付けて、GIMPLEのファイルを出力します。

$ gcc -O2 -Wall -g test.c --dump-tree-all

$ grep -r 'memmove ' ./ | sort

./test.c.004t.original:  memmove ((void *) p, (const void *) (p + (sizetype) sz_pre), sz);
./test.c.005t.gimple:    memmove (p, _3, sz);
./test.c.007t.omplower:    memmove (p, _3, sz);
./test.c.008t.lower:  memmove (p, _3, sz);
./test.c.011t.eh:  memmove (p, _3, sz);
./test.c.013t.cfg:  memmove (p, _3, sz);
./test.c.015t.ompexp:  memmove (p, _3, sz);
./test.c.020t.fixup_cfg1:  memmove (p, _3, sz);
./test.c.021t.ssa:  memmove (p_8, _3, sz_10);
./test.c.023t.nothrow:  memmove (p_8, _3, sz_10);
./test.c.025t.fixup_cfg2:  memmove (p_8, _3, sz_10);
./test.c.026t.local-fnsummary1:  memmove (p_8, _3, sz_10);
./test.c.027t.einline:  memmove (p_8, _3, sz_10);
./test.c.028t.early_optimizations:  memmove (p_8, _3, sz_10);
./test.c.029t.objsz1:  memmove (p_8, _3, sz_10);

ファイルをmemmoveで検索すると、029t.objsz1を最後に出現しなくなっています。029t.objsz1の次である030t.cpp1を見て、memmoveがどうなったのか確かめます。

// test.c.030t.ccp1

;; Function main (main, funcdef_no=11, decl_uid=2555, cgraph_uid=12, symbol_order=11)

main (int argc, char * * argv)
{

...

  __asm__ __volatile__("nop;");
  # DEBUG BEGIN_STMT
  __builtin_memcpy (&s, &MEM <volatile char[20]> [(void *)&s + 2B], sz_10);
  # DEBUG BEGIN_STMT
  __asm__ __volatile__("nop;");
  # DEBUG BEGIN_STMT
  __asm__ __volatile__("nop;");

...

検証用プログラムではmemmoveと書いたはずの場所が、__builtin_memcpy() に変わっています。この __builtin_memcpy() は最終的にアセンブラに展開されます。あまり詳しく追っていませんが、末尾の余りバイトをコピーしてから、先頭から8バイトずつコピーするループが実行されるようで、srcとdestが重なっていると、正常に動作しません。

$ objdump -drS a.out

...

        NOP;
    1084:       90                      nop
        size_t sz = strlen(p) - sz_pre + 1;
    1085:       48 8d 50 ff             lea    -0x1(%rax),%rdx
        memmove(p, p + sz_pre, sz);
    1089:       48 8d 4c 24 02          lea    0x2(%rsp),%rcx
    108e:       48 83 fa 08             cmp    $0x8,%rdx
    1092:       73 52                   jae    10e6 <main+0x86>    ★コピーするコードの本体
    1094:       f6 c2 04                test   $0x4,%dl
    1097:       0f 85 85 00 00 00       jne    1122 <main+0xc2>
    109d:       48 85 d2                test   %rdx,%rdx
    10a0:       74 0f                   je     10b1 <main+0x51>
    10a2:       0f b6 01                movzbl (%rcx),%eax
    10a5:       88 45 00                mov    %al,0x0(%rbp)
    10a8:       f6 c2 02                test   $0x2,%dl
    10ab:       0f 85 80 00 00 00       jne    1131 <main+0xd1>
        NOP; NOP;
    10b1:       90                      nop
    10b2:       90                      nop

...

        memmove(p, p + sz_pre, sz);
    10e6:       48 8b 74 14 fa          mov    -0x6(%rsp,%rdx,1),%rsi
    10eb:       48 83 e8 02             sub    $0x2,%rax
    10ef:       48 89 74 14 f8          mov    %rsi,-0x8(%rsp,%rdx,1)
    10f4:       48 83 f8 08             cmp    $0x8,%rax
    10f8:       72 b7                   jb     10b1 <main+0x51>
    10fa:       48 83 e0 f8             and    $0xfffffffffffffff8,%rax
    10fe:       31 d2                   xor    %edx,%edx
    1100:       48 8b 34 11             mov    (%rcx,%rdx,1),%rsi      ★この辺りがコピーのためのループ
    1104:       48 89 74 15 00          mov    %rsi,0x0(%rbp,%rdx,1)
    1109:       48 83 c2 08             add    $0x8,%rdx
    110d:       48 39 c2                cmp    %rax,%rdx
    1110:       72 ee                   jb     1100 <main+0xa0>
    1112:       eb 9d                   jmp    10b1 <main+0x51>
                printf("  OK: %s\n", p);
    1114:       48 8d 3d fb 0e 00 00    lea    0xefb(%rip),%rdi        # 2016 <_IO_stdin_used+0x16>
    111b:       e8 20 ff ff ff          callq  1040 <printf@plt>
    1120:       eb bc                   jmp    10de <main+0x7e>
        memmove(p, p + sz_pre, sz);
    1122:       8b 01                   mov    (%rcx),%eax
    1124:       89 45 00                mov    %eax,0x0(%rbp)
    1127:       8b 44 11 fc             mov    -0x4(%rcx,%rdx,1),%eax
    112b:       89 44 15 fc             mov    %eax,-0x4(%rbp,%rdx,1)
    112f:       eb 80                   jmp    10b1 <main+0x51>
    1131:       0f b7 44 11 fe          movzwl -0x2(%rcx,%rdx,1),%eax
    1136:       66 89 44 15 fe          mov    %ax,-0x2(%rbp,%rdx,1)
    113b:       e9 71 ff ff ff          jmpq   10b1 <main+0x51>

長くなってきたので、また次回。