Forth like interpreter

[Kragen Sitaker]

In article <8al719$h5c$1 at nnrp1.deja.com>,  <fredrik at pythonware.com> wrote:
>> Not all compilers implement switch statements as jump-tables.
>
>really?  can you name one that doesn't?

gcc 2.95.2 doesn't always implement switch statements as jump-tables
when compiling for i386.  Sometimes it implements them with a rat's
nest of jumps.  Here are two examples, one where it uses a jump-table
and one where it doesn't.

nclude <stdio.h>

int main(int argc, char **argv) {
        switch(argc) {
                case 1:
                        printf("got a unity\n");
                        return 0;
                case 2: case 3:
                        printf("got two or three\n");
                        return 1;
                case 4:
                        printf("got four, a square!\n");
                        return 2;
                case 5:
                        printf("got five\n");
                        return 1;
                case 6:
                        printf("got the first perfect number\n");
                        return 2;
                case 7:
                        printf("got seven\n");
                        return 1;
                default:
                        printf("got something weird\n");
                        return -1;
        }
}

This switch compiles to a jump table.  Here's the output of gcc -Wall
-S; the jump table is at .L12.  -O2 leaves it as a jump table.

        .file   "switch2.c"
        .version        "01.01"
gcc2_compiled.:
.section        .rodata
.LC0:
        .string "got a unity\n"
.LC1:
        .string "got two or three\n"
.LC2:
        .string "got four, a square!\n"
.LC3:
        .string "got five\n"
.LC4:
        .string "got the first perfect number\n"
.LC5:
        .string "got seven\n"
.LC6:
        .string "got something weird\n"
.text
        .align 4
.globl main
        .type    main, at function
main:
        pushl %ebp
        movl %esp,%ebp
        subl $8,%esp
        movl 8(%ebp),%eax
        decl %eax
        cmpl $6,%eax
        ja .L11
        movl .L12(,%eax,4),%eax
        jmp *%eax
        .p2align 4,,7
.section        .rodata
        .align 4
        .align 4
.L12:
        .long .L4
        .long .L6
        .long .L6
        .long .L7
        .long .L8
        .long .L9
        .long .L10
.text
        .p2align 4,,7
.L4:
        addl $-12,%esp
        pushl $.LC0
        call printf
        addl $16,%esp
        xorl %eax,%eax
        jmp .L2
        .p2align 4,,7
.L5:
.L6:
        addl $-12,%esp
        pushl $.LC1
        call printf
        addl $16,%esp
        movl $1,%eax
        jmp .L2
        .p2align 4,,7
.L7:
        addl $-12,%esp
        pushl $.LC2
        call printf
        addl $16,%esp
        movl $2,%eax
        jmp .L2
        .p2align 4,,7
.L8:
        addl $-12,%esp
        pushl $.LC3
        call printf
        addl $16,%esp
        movl $1,%eax
        jmp .L2
        .p2align 4,,7
.L9:
        addl $-12,%esp
        pushl $.LC4
        call printf
        addl $16,%esp
        movl $2,%eax
        jmp .L2
        .p2align 4,,7
.L10:
        addl $-12,%esp
        pushl $.LC5
        call printf
        addl $16,%esp
        movl $1,%eax
        jmp .L2
        .p2align 4,,7
.L11:
        addl $-12,%esp
        pushl $.LC6
        call printf
        addl $16,%esp
        movl $-1,%eax
        jmp .L2
        .p2align 4,,7
.L3:
.L2:
        leave
        ret
.Lfe1:
        .size    main,.Lfe1-main
        .ident  "GCC: (GNU) 2.95.2 20000220 (Debian GNU/Linux)"

This switch, on the other hand, compiles to an altogether different
sort of structure:

#include <stdio.h>

int main(int argc, char **argv) {
        switch (argv[0][0]) {
                case 'a':
                        return 73;
                case 'Q':
                        return 81;
                case '!':
                        return 33;
                case '-':
                        printf("%s [aQ!]\n", argv[0]);
                        return 0;
                default:
                        return 1;
        }
}

Here's what it compiles to, with some comments I added:

        .file   "switch.c"
        .version        "01.01"
gcc2_compiled.:
.section        .rodata
.LC0:
        .string "%s [aQ!]\n"
.text
        .align 4
.globl main
        .type    main, at function
main:
        pushl %ebp
        movl %esp,%ebp
        subl $8,%esp
        movl 12(%ebp),%eax
        movl (%eax),%edx
        movb (%edx),%al   ; load argv[0][0]
        cmpb $81,%al
        je .L5            ; if 'Q', go to .L5
        cmpb $81,%al
        jg .L10           ; if not above 'Q':
        cmpb $33,%al
        je .L6                ; if '!', go to .L6
        cmpb $45,%al
        je .L7                ; if '-', go to .L7
        jmp .L8               ; otherwise, go to .L8 ("default:")
        .p2align 4,,7
.L10:                     ; else (below 'Q'):
        cmpb $97,%al          
        je .L4                ; if 'a', go to .L4
        jmp .L8               ; otherwise, go to .L8 ("default:")
        .p2align 4,,7
.L4:
        movl $73,%eax
        jmp .L2
        .p2align 4,,7
.L5:
        movl $81,%eax     ; when I wrote this code, I honestly didn't 
                          ; realize 81 was the ASCII code for 'Q'.  I guess
                          ; I have ASCII on the brain.
        jmp .L2
        .p2align 4,,7
.L6:
        movl $33,%eax     ; I *did* know '!' was 33, though.
        jmp .L2
        .p2align 4,,7
.L7:
        addl $-8,%esp
        movl 12(%ebp),%eax
        movl (%eax),%edx
        pushl %edx
        pushl $.LC0
        call printf
        addl $16,%esp
        xorl %eax,%eax
        jmp .L2
        .p2align 4,,7
.L8:
        movl $1,%eax
        jmp .L2
        .p2align 4,,7
.L3:
.L2:
        leave
        ret
.Lfe1:
        .size    main,.Lfe1-main
        .ident  "GCC: (GNU) 2.95.2 20000220 (Debian GNU/Linux)"

-O2 swizzles some blocks around and eliminates some useless
instructions, but leaves the rat's-nest.

The polymorphic inline cache people seem to think that a couple of
tests might be quicker than a jump table in many cases these days.
-- 
<kragen at pobox.com>       Kragen Sitaker     <http://www.pobox.com/~kragen/>
The Internet stock bubble didn't burst on 1999-11-08.  Hurrah!
<URL:http://www.pobox.com/~kragen/bubble.html>
The power didn't go out on 2000-01-01 either.  :)