gccはswitch文でcaseが連続してると表を牽くようになるってきいたことがあったので確かめてみた。

int
foo(int x)
{
    //値が連続している
    switch (x) {
    case 10: return 0;
    case 11: return 1;
    case 12: return 2;
    case 13: return 3;
    case 14: return 4;
    case 15: return 5;
    }
    return -1;
}
int
bar(int x)
{
    //値が10step
    switch (x) {
    case 100: return 0;
    case 110: return 1;
    case 120: return 2;
    case 130: return 3;
    case 140: return 4;
    case 150: return 5;
    }
    return -1;
}
int
buz(int x)
{
    //値が100step
    switch (x) {
    case 1000: return 0;
    case 1100: return 1;
    case 1200: return 2;
    case 1300: return 3;
    case 1400: return 4;
    case 1500: return 5;
    }
    return -1;
}

gcc47 -O9 -Sでコンパイルしてみると、10飛びくらいなら表にしてしまうが100飛びだとさすがにそれはしなくて素直に条件分岐、とおもったら全然素直じゃねぇ。

	.file	"foo.c"
	.text
	.p2align 4,,15
	.globl	foo
	.type	foo, @function
foo:
.LFB0:
	.cfi_startproc
	subl	$10, %edi
	movl	$-1, %eax
	cmpl	$5, %edi
	ja	.L2
	movl	CSWTCH.2(,%rdi,4), %eax
.L2:
	rep
	ret
	.cfi_endproc
.LFE0:
	.size	foo, .-foo
	.p2align 4,,15
	.globl	bar
	.type	bar, @function
bar:
.LFB1:
	.cfi_startproc
	subl	$100, %edi
	movl	$-1, %eax
	cmpl	$50, %edi
	ja	.L6
	movsbl	CSWTCH.5(%rdi), %eax
.L6:
	rep
	ret
	.cfi_endproc
.LFE1:
	.size	bar, .-bar
	.p2align 4,,15
	.globl	buz
	.type	buz, @function
buz:
.LFB2:
	.cfi_startproc
	cmpl	$1200, %edi
	movl	$2, %eax
	je	.L11
	jle	.L24
	cmpl	$1400, %edi
	movl	$4, %eax
	je	.L11
	cmpl	$1500, %edi
	movb	$5, %al
	je	.L11
	cmpl	$1300, %edi
	movb	$3, %al
	je	.L11
.L9:
	movl	$-1, %eax
	.p2align 4,,10
.L11:
	rep
	ret
	.p2align 4,,10
.L24:
	xorb	%al, %al
	cmpl	$1000, %edi
	je	.L11
	cmpl	$1100, %edi
	movb	$1, %al
	jne	.L9
	rep
	ret
	.cfi_endproc
.LFE2:
	.size	buz, .-buz
	.section	.rodata
	.align 16
	.type	CSWTCH.2, @object
	.size	CSWTCH.2, 24
CSWTCH.2:
	.long	0
	.long	1
	.long	2
	.long	3
	.long	4
	.long	5
	.align 32
	.type	CSWTCH.5, @object
	.size	CSWTCH.5, 51
CSWTCH.5:
	.byte	0
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	1
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	2
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	3
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	4
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	-1
	.byte	5
	.ident	"GCC: (FreeBSD Ports Collection) 4.7.1 20120324 (prerelease)"
	.section	.note.GNU-stack,"",@progbits

二分探索してるんかとおもったら、そうでもなさそう。疑似コードにしてみたらこんな感じ

int
buz(int x)
{
    cmp(x, 1200);
    r = 2;
    if (==)
        retun r;
    if (<=) {
        r = 0;
        cmp(x, 1000);
        if (==)
            return r;
        cmp(x, 1100);
        r = 1;
        if (!=)
            return -1;
        return r;
    }
    cmp(x, 1400);
    r = 4;
    if (==)
        return r;
    cmp(x, 1500);
    r = 5;
    if (==)
        return r;
    cmp(x, 1300);
    r = 3;
    if (==)
        return r;
    return -1;
}

もうチョイ複雑でありがちなケースで、即値リターンじゃなくて関数末尾呼び出しだとこうなった。

extern int unko(int);
int
foo(int x)
{
    //値が連続している
    switch (x) {
    case 10: return bar(1);
    case 11: return bar(1);
    case 12: return bar(2);
    case 13: return bar(3);
    case 14: return bar(4);
    case 15: return bar(5);
    }
    return -1;
}
int
bux(int x)
{
    //値が100step
    switch (x) {
    case 1000: return bar(1);
    case 1100: return bar(1);
    case 1200: return bar(2);
    case 1300: return bar(3);
    case 1400: return bar(4);
    case 1500: return bar(5);
    }
    return -1;
}

これがこうなる

	.file	"boke.c"
	.text
	.p2align 4,,15
	.globl	foo
	.type	foo, @function
foo:
.LFB0:
	.cfi_startproc
	subl	$10, %edi
	cmpl	$5, %edi
	jbe	.L11
	movl	$-1, %eax
	ret
	.p2align 4,,10
.L11:
	jmp	*.L9(,%rdi,8)
	.section	.rodata
	.align 8
	.align 4
.L9:
	.quad	.L4
	.quad	.L4
	.quad	.L5
	.quad	.L6
	.quad	.L7
	.quad	.L8
	.text
	.p2align 4,,10
.L4:
	movl	$1, %edi
	xorl	%eax, %eax
	jmp	bar
	.p2align 4,,10
.L7:
	movl	$4, %edi
	xorl	%eax, %eax
	jmp	bar
	.p2align 4,,10
.L5:
	movl	$2, %edi
	xorl	%eax, %eax
	jmp	bar
	.p2align 4,,10
.L6:
	movl	$3, %edi
	xorl	%eax, %eax
	jmp	bar
	.p2align 4,,10
.L8:
	movl	$5, %edi
	xorl	%eax, %eax
	jmp	bar
	.cfi_endproc
.LFE0:
	.size	foo, .-foo
	.p2align 4,,15
	.globl	bux
	.type	bux, @function
bux:
.LFB1:
	.cfi_startproc
	cmpl	$1200, %edi
	je	.L16
	jle	.L21
	cmpl	$1400, %edi
	je	.L18
	cmpl	$1500, %edi
	je	.L19
	cmpl	$1300, %edi
	je	.L22
.L13:
	movl	$-1, %eax
	ret
	.p2align 4,,10
.L21:
	cmpl	$1000, %edi
	je	.L15
	cmpl	$1100, %edi
	jne	.L13
.L15:
	movl	$1, %edi
	xorl	%eax, %eax
	jmp	bar
	.p2align 4,,10
.L19:
	movl	$5, %edi
	xorl	%eax, %eax
	jmp	bar
	.p2align 4,,10
.L18:
	movl	$4, %edi
	xorl	%eax, %eax
	jmp	bar
	.p2align 4,,10
.L16:
	movl	$2, %edi
	xorl	%eax, %eax
	jmp	bar
	.p2align 4,,10
.L22:
	movl	$3, %edi
	xorl	%eax, %eax
	jmp	bar
	.cfi_endproc
.LFE1:
	.size	bux, .-bux
	.ident	"GCC: (FreeBSD Ports Collection) 4.7.1 20120324 (prerelease)"
	.section	.note.GNU-stack,"",@progbits

疑似コードにするとこんなかんじ。


int
bux(int x)
{
    cmp(x, 1200);
    if (==)
        return bar(2);
    if (<=) {
        cmp(x, 1000);
        if (==)
            return bar(1);
        cmp(x, 1100);
        if (!=)
            return -1;
        return bar(1);
    }    
    cmp(x, 1400);
    if (==)
        return bar(4);
    cmp(x, 1500);
    if (==)
        return bar(5);
    cmp(x, 1300);
    if (==)
        return bar(3);
    return -1;
}

二分探索と線形探索を組み合わせた感じか?caseを9個に増やしてみる。

        1400
         / \
        /   \
     1100   1700
    / \      /  \
1000  1200 1500  1800
       |    |     |
      1300 1600  1900

やっぱり二分探索かな。

koie