Switch implementation
bearophile
bearophileHUGS at lycos.com
Tue Sep 28 10:33:16 PDT 2010
Through Reddit I have found a small article about reverse engineering the switch statement:
http://www.codeproject.com/KB/cpp/switch.aspx
I have compiled a test program with GCC and then with DMD with minimal changes, this is the D program and the asm from the two compilers:
import std.c.stdio: puts;
import std.c.stdlib: atoi;
void f1() { puts("f1 called"); }
void f2() { puts("f2 called"); }
void f3() { puts("f3 called"); }
void main() {
int i = atoi("3");
switch (i) {
case 140: f1(); break;
case 300: f1(); break;
case 1280: f1(); break;
case 1540: f1(); break;
case 1660: f1(); break;
case 1770: f2(); break;
case 2150: f2(); break;
case 2190: f1(); break;
case 2530: f2(); break;
case 2560: f2(); break;
case 2590: f1(); break;
case 2660: f1(); break;
case 2720: f2(); break;
case 3010: f1(); break;
case 3100: f1(); break;
case 3390: f2(); break;
case 3760: f1(); break;
case 3970: f2(); break;
case 4050: f1(); break;
case 4140: f1(); break;
case 4360: f2(); break;
case 4540: f1(); break;
case 4600: f2(); break;
case 4720: f2(); break;
case 4730: f2(); break;
case 4740: f2(); break;
case 4880: f2(); break;
case 4950: f1(); break;
default: f3();
}
}
/*
------------------------------
DMD optimized build:
__Dmain comdat
push EBX
mov EAX,offset FLAT:_DATA[024h]
push EAX
call near ptr _atoi
add ESP,4
cmp EAX,08Ch
je L115
cmp EAX,012Ch
je L115
cmp EAX,0500h
je L115
cmp EAX,0604h
je L115
cmp EAX,067Ch
je L115
cmp EAX,06EAh
je L105
cmp EAX,0866h
je L105
cmp EAX,088Eh
je L115
cmp EAX,09E2h
je L105
cmp EAX,0A00h
je L105
cmp EAX,0A1Eh
je L115
cmp EAX,0A64h
je L115
cmp EAX,0AA0h
je L105
cmp EAX,0BC2h
je L115
cmp EAX,0C1Ch
je L115
cmp EAX,0D3Eh
je L105
cmp EAX,0EB0h
je L115
cmp EAX,0F82h
je L105
cmp EAX,0FD2h
je L115
cmp EAX,0102Ch
je L115
cmp EAX,01108h
je L105
cmp EAX,011BCh
je L115
cmp EAX,011F8h
je L105
cmp EAX,01270h
je L105
cmp EAX,0127Ah
je L105
cmp EAX,01284h
je L105
cmp EAX,01310h
je L105
cmp EAX,01356h
je L115
jmp short L125
L105: mov ECX,offset FLAT:_DATA[0Ch]
push ECX
call near ptr _puts
add ESP,4
jmp short L133
L115: mov EDX,offset FLAT:_DATA
push EDX
call near ptr _puts
add ESP,4
jmp short L133
L125: mov EBX,offset FLAT:_DATA[018h]
push EBX
call near ptr _puts
add ESP,4
L133: pop EBX
xor EAX,EAX
ret
----------------------------------
GCC 4.5.1 -O3
_main:
pushl %ebp
movl %esp, %ebp
andl $-16, %esp
subl $16, %esp
call ___main
movl $LC3, (%esp)
call _atoi
cmpl $3010, %eax
je L33
jle L43
cmpl $4360, %eax
je L32
.p2align 4,,6
jle L44
cmpl $4730, %eax
je L32
.p2align 4,,6
jle L45
cmpl $4880, %eax
je L32
cmpl $4950, %eax
je L33
cmpl $4740, %eax
jne L5
.p2align 4,,7
L32:
movl $LC1, (%esp)
call _puts
xorl %eax, %eax
leave
LCFI16:
ret
.p2align 4,,7
L45:
LCFI17:
cmpl $4600, %eax
je L32
cmpl $4720, %eax
je L32
cmpl $4540, %eax
jne L5
.p2align 4,,7
L33:
movl $LC0, (%esp)
call _puts
L41:
xorl %eax, %eax
leave
LCFI18:
ret
.p2align 4,,7
L43:
LCFI19:
cmpl $2150, %eax
je L32
.p2align 4,,4
jle L46
cmpl $2560, %eax
je L32
.p2align 4,,6
jle L47
cmpl $2660, %eax
je L33
cmpl $2720, %eax
je L32
cmpl $2590, %eax
jne L5
jmp L33
.p2align 4,,7
L44:
cmpl $3760, %eax
je L33
.p2align 4,,6
jle L48
cmpl $4050, %eax
je L33
cmpl $4140, %eax
je L33
cmpl $3970, %eax
jne L5
jmp L32
.p2align 4,,7
L46:
cmpl $1280, %eax
je L33
.p2align 4,,6
jle L49
cmpl $1660, %eax
je L33
cmpl $1770, %eax
je L32
cmpl $1540, %eax
jne L5
jmp L33
.p2align 4,,7
L47:
cmpl $2190, %eax
je L33
cmpl $2530, %eax
je L32
.p2align 4,,7
L5:
movl $LC2, (%esp)
call _puts
jmp L41
.p2align 4,,7
L49:
cmpl $140, %eax
je L33
cmpl $300, %eax
jne L5
jmp L33
.p2align 4,,7
L48:
cmpl $3100, %eax
je L33
cmpl $3390, %eax
jne L5
jmp L32
---------------------------
llvm-gcc V.2.7, -O3
_main:
pushl %ebp
movl %esp, %ebp
subl $8, %esp
call ___main
movl $L_.str3, (%esp)
call _atoi
cmpl $299, %eax
jg LBB4_4
cmpl $140, %eax
jne LBB4_56
LBB4_2:
movl $L_.str2, (%esp)
LBB4_3:
call _puts
xorl %eax, %eax
addl $8, %esp
popl %ebp
ret
LBB4_4:
cmpl $1279, %eax
jg LBB4_6
cmpl $300, %eax
je LBB4_2
jmp LBB4_56
LBB4_6:
cmpl $1539, %eax
jg LBB4_8
cmpl $1280, %eax
je LBB4_2
jmp LBB4_56
LBB4_8:
cmpl $1659, %eax
jg LBB4_10
cmpl $1540, %eax
je LBB4_2
jmp LBB4_56
LBB4_10:
cmpl $1769, %eax
jg LBB4_12
cmpl $1660, %eax
je LBB4_2
jmp LBB4_56
LBB4_12:
cmpl $2149, %eax
jg LBB4_15
cmpl $1770, %eax
jne LBB4_56
LBB4_14:
movl $L_.str1, (%esp)
jmp LBB4_3
LBB4_15:
cmpl $4949, %eax
jg LBB4_55
cmpl $4879, %eax
jg LBB4_54
cmpl $2189, %eax
jg LBB4_19
cmpl $2150, %eax
je LBB4_14
jmp LBB4_56
LBB4_19:
cmpl $2529, %eax
jg LBB4_21
cmpl $2190, %eax
je LBB4_2
jmp LBB4_56
LBB4_21:
cmpl $2559, %eax
jg LBB4_23
cmpl $2530, %eax
je LBB4_14
jmp LBB4_56
LBB4_23:
cmpl $2589, %eax
jg LBB4_25
cmpl $2560, %eax
je LBB4_14
jmp LBB4_56
LBB4_25:
cmpl $2659, %eax
jg LBB4_27
cmpl $2590, %eax
je LBB4_2
jmp LBB4_56
LBB4_27:
cmpl $2719, %eax
jg LBB4_29
cmpl $2660, %eax
je LBB4_2
jmp LBB4_56
LBB4_29:
cmpl $3009, %eax
jg LBB4_31
cmpl $2720, %eax
je LBB4_14
jmp LBB4_56
LBB4_31:
cmpl $3099, %eax
jg LBB4_33
cmpl $3010, %eax
je LBB4_2
jmp LBB4_56
LBB4_33:
cmpl $3389, %eax
jg LBB4_35
cmpl $3100, %eax
je LBB4_2
jmp LBB4_56
LBB4_35:
cmpl $3759, %eax
jg LBB4_37
cmpl $3390, %eax
je LBB4_14
jmp LBB4_56
LBB4_37:
cmpl $3969, %eax
jg LBB4_39
cmpl $3760, %eax
je LBB4_2
jmp LBB4_56
LBB4_39:
cmpl $4049, %eax
jg LBB4_41
cmpl $3970, %eax
je LBB4_14
jmp LBB4_56
LBB4_41:
cmpl $4139, %eax
jg LBB4_43
cmpl $4050, %eax
je LBB4_2
jmp LBB4_56
LBB4_43:
cmpl $4359, %eax
jg LBB4_45
cmpl $4140, %eax
je LBB4_2
jmp LBB4_56
LBB4_45:
cmpl $4539, %eax
jg LBB4_47
cmpl $4360, %eax
je LBB4_14
jmp LBB4_56
LBB4_47:
cmpl $4599, %eax
jg LBB4_49
cmpl $4540, %eax
je LBB4_2
jmp LBB4_56
LBB4_49:
cmpl $4719, %eax
jg LBB4_51
cmpl $4600, %eax
je LBB4_14
jmp LBB4_56
LBB4_51:
cmpl $4720, %eax
je LBB4_14
cmpl $4730, %eax
je LBB4_14
cmpl $4740, %eax
je LBB4_14
jmp LBB4_56
LBB4_54:
cmpl $4880, %eax
je LBB4_14
jmp LBB4_56
LBB4_55:
cmpl $4950, %eax
je LBB4_2
LBB4_56:
movl $L_.str, (%esp)
jmp LBB4_3
---------------------------------
*/
gcc and llvm-gcc use a binary search, dmd a linear one.
I have done a similar interesting test (similar to switch5.cpp of the article author) where a good implementation of the switch is a small table for part of the cases and a binary tree for the other cases.
Bye,
bearophile
More information about the Digitalmars-d
mailing list