investigation of tail calls on mainline
Brad Lucier
lucier@math.purdue.edu
Thu Dec 12 08:48:00 GMT 2002
Marc Feeley, author of the Gambit-C Scheme->C compiler, came up with the
following test of whether GCC will implement tail call optimizations
in types of code that might typically be generated for a C virtual machine
that depends on the full implementation of tail calls.
Right now, Gambit-C and MLton, the ML compiler, rely on trampolines for
inter-module calls when targetting C in the back end. Gambit-C uses computed
gotos for intra-module anonymous calls and returns, but has to do some extra
work on each such call to ensure that the target truly is in the same module;
MLton gave up on computed gotos a few years ago when there were still bugs in
GCC's implementation, but may look at them again after I assured them that
computed gotos now work properly ;-).
Full implementation of tail calls would greatly speed intermodule calls
(by about a factor of 30) and would probably be no worse than a wash (compared
to computed gotos) for intra-module calls and returns.
Well, actually, "full" implementation of tail calls is not really needed,
because of the restricted forms of the possible calls needed to implement
a Gambit-style virtual machine.
Anyway, enough blather. I took a look at the thread starting at
http://gcc.gnu.org/ml/gcc-patches/2001-01/msg00178.html
but (a) don't understand it totally and (b) don't know how much of
it still applies.
The attached file was compiled with mainline GCC and
"-O2 -fomit-frame-pointer" on sparc-sun-solaris2.8.
Brad
-------------- next part --------------
.file "newtail.c"
.section ".text"
.align 4
.global point0
.type point0, #function
.proc 04
point0:
!#PROLOGUE# 0
!#PROLOGUE# 1
sethi %hi(point3), %g1
sethi %hi(999424), %o5
or %g1, %lo(point3), %g2
sethi %hi(point1), %g1
jmpl %g1 + %lo(point1), %g0
or %o5, 576, %g3
nop
.size point0, .-point0
.align 4
.global point1
.type point1, #function
.proc 04
point1:
!#PROLOGUE# 0
save %sp, -112, %sp
!#PROLOGUE# 1
cmp %g3, 0
be .LL5
mov %i0, %o0
add %g3, -1, %g3
call point2, 0
restore
.LL5:
call %g2, 0
mov 0, %g3
ret
restore %g0, %o0, %o0
.size point1, .-point1
.align 4
.global point2
.type point2, #function
.proc 04
point2:
!#PROLOGUE# 0
save %sp, -112, %sp
!#PROLOGUE# 1
cmp %g3, 0
be .LL9
mov %i0, %o0
add %g3, -1, %g3
call point1, 0
restore
.LL9:
call %g2, 0
mov 1, %g3
ret
restore %g0, %o0, %o0
.size point2, .-point2
.align 4
.global point3
.type point3, #function
.proc 04
point3:
!#PROLOGUE# 0
!#PROLOGUE# 1
retl
mov %g3, %o0
.size point3, .-point3
.align 4
.global point4
.type point4, #function
.proc 04
point4:
!#PROLOGUE# 0
!#PROLOGUE# 1
sethi %hi(point8), %g1
or %g1, %lo(point8), %g2
sethi %hi(point5), %g1
jmpl %g1 + %lo(point5), %g0
mov 20, %g3
nop
.size point4, .-point4
.align 4
.global point5
.type point5, #function
.proc 04
point5:
!#PROLOGUE# 0
save %sp, -112, %sp
!#PROLOGUE# 1
mov %i0, %o0
.LL15:
cmp %g3, 1
ble .LL16
sethi %hi(point6), %g1
add %g4, -4, %g4
st %g2, [%g4]
add %g4, -4, %g4
or %g1, %lo(point6), %g2
st %g3, [%g4]
b .LL15
add %g3, -1, %g3
.LL16:
call %g2, 0
nop
ret
restore %g0, %o0, %o0
.size point5, .-point5
.align 4
.global point6
.type point6, #function
.proc 04
point6:
!#PROLOGUE# 0
!#PROLOGUE# 1
add %g4, -4, %g4
ld [%g4+4], %o5
st %g3, [%g4]
sethi %hi(point7), %g1
or %g1, %lo(point7), %g2
sethi %hi(point5), %g1
jmpl %g1 + %lo(point5), %g0
add %o5, -2, %g3
nop
.size point6, .-point6
.align 4
.global point7
.type point7, #function
.proc 04
point7:
!#PROLOGUE# 0
save %sp, -112, %sp
!#PROLOGUE# 1
ld [%g4], %g1
ld [%g4+8], %g2
mov %i0, %o0
add %g3, %g1, %g3
call %g2, 0
add %g4, 12, %g4
ret
restore %g0, %o0, %o0
.size point7, .-point7
.align 4
.global point8
.type point8, #function
.proc 04
point8:
!#PROLOGUE# 0
!#PROLOGUE# 1
retl
mov %g3, %o0
.size point8, .-point8
.align 4
.global computed_goto
.type computed_goto, #function
.proc 04
computed_goto:
!#PROLOGUE# 0
add %sp, -152, %sp
!#PROLOGUE# 1
sethi %hi(.LL21), %g1
or %g1, %lo(.LL21), %g1
sethi %hi(.LL22), %o5
st %g1, [%sp+96]
or %o5, %lo(.LL22), %o5
sethi %hi(.LL23), %g1
or %g1, %lo(.LL23), %g1
st %o5, [%sp+100]
st %g1, [%sp+104]
sethi %hi(.LL24), %o5
sethi %hi(.LL25), %g1
or %o5, %lo(.LL24), %o5
or %g1, %lo(.LL25), %g1
st %o5, [%sp+108]
st %g1, [%sp+112]
sethi %hi(.LL26), %o5
sethi %hi(.LL27), %g1
or %o5, %lo(.LL26), %o5
or %g1, %lo(.LL27), %g1
st %o5, [%sp+116]
st %g1, [%sp+120]
sethi %hi(.LL28), %o5
sethi %hi(.LL29), %g1
or %o5, %lo(.LL28), %o5
or %g1, %lo(.LL29), %g1
st %o5, [%sp+124]
sll %o1, 2, %o1
st %g1, [%sp+128]
add %sp, 96, %o5
ld [%o5+%o1], %g1
.LL36:
jmp %g1
nop
.LL21:
sethi %hi(999424), %g1
add %sp, 108, %g2
or %g1, 576, %g3
.LL22:
cmp %g3, 0
bne,a .LL30
add %g3, -1, %g3
ld [%g2], %g1
b .LL36
mov 0, %g3
.LL30:
.LL23:
cmp %g3, 0
bne,a .LL22
add %g3, -1, %g3
ld [%g2], %g1
b .LL36
mov 1, %g3
.LL24:
b .LL38
mov %g3, %o0
.LL25:
add %sp, 128, %g2
mov 20, %g3
.LL26:
cmp %g3, 1
ble,a .LL36
ld [%g2], %g1
add %g4, -4, %g4
st %g2, [%g4]
add %g4, -4, %g4
add %sp, 120, %g2
st %g3, [%g4]
b .LL26
add %g3, -1, %g3
.LL27:
add %g4, -4, %g4
ld [%g4+4], %g1
st %g3, [%g4]
add %sp, 124, %g2
b .LL26
add %g1, -2, %g3
.LL28:
ld [%g4+8], %g2
ld [%g4], %g1
ld [%g2], %o5
add %g3, %g1, %g3
jmp %o5
add %g4, 12, %g4
.LL29:
mov %g3, %o0
.LL38:
nop
retl
sub %sp, -152, %sp
.size computed_goto, .-computed_goto
.section ".rodata"
.align 8
.LLC0:
.asciz "usage: ./a.out <0_or_1> <0_or_1>"
.align 8
.LLC1:
.asciz "tail-call implementation"
.align 8
.LLC4:
.asciz "computed goto implementation"
.align 8
.LLC3:
.asciz "fib(20) = %d\n"
.align 8
.LLC2:
.asciz "odd(1000000) = %d\n"
.section ".text"
.align 4
.global main
.type main, #function
.proc 04
main:
!#PROLOGUE# 0
save %sp, -4096, %sp
add %sp, -32, %sp
!#PROLOGUE# 1
add %fp, -32, %l0
cmp %i0, 3
be .LL40
mov %l0, %g4
sethi %hi(.LLC0), %o0
call puts, 0
or %o0, %lo(.LLC0), %o0
.LL41:
call _exit, 0
mov 0, %o0
.LL40:
call atoi, 0
ld [%i1+8], %o0
cmp %o0, 1
be,a .LL79
sethi %hi(.LLC1), %o0
sethi %hi(.LLC4), %o0
call puts, 0
or %o0, %lo(.LLC4), %o0
ld [%i1+4], %o0
call atoi, 0
mov 99, %i0
cmp %o0, 1
be .LL82
mov %l0, %o0
.LL83:
call computed_goto, 0
mov 4, %o1
addcc %i0, -1, %i0
bpos,a .LL83
mov %l0, %o0
mov %o0, %o1
sethi %hi(.LLC3), %o0
.LL84:
or %o0, %lo(.LLC3), %o0
.LL76:
call printf, 0
add %o7, (.LL41-.-4), %o7
.LL61:
.LL82:
call computed_goto, 0
mov 0, %o1
addcc %i0, -1, %i0
bpos,a .LL61
mov %l0, %o0
mov %o0, %o1
sethi %hi(.LLC2), %o0
.LL85:
b .LL76
or %o0, %lo(.LLC2), %o0
.LL79:
call puts, 0
or %o0, %lo(.LLC1), %o0
ld [%i1+4], %o0
call atoi, 0
mov 99, %i0
cmp %o0, 1
be .LL48
nop
.LL54:
call point4, 0
mov %l0, %o0
addcc %i0, -1, %i0
bpos .LL54
mov %o0, %o1
b .LL84
sethi %hi(.LLC3), %o0
.LL48:
call point0, 0
mov %l0, %o0
addcc %i0, -1, %i0
bpos .LL48
mov %o0, %o1
b .LL85
sethi %hi(.LLC2), %o0
nop
.size main, .-main
.ident "GCC: (GNU) 3.3 20021209 (experimental)"
-------------- next part --------------
# 1 "newtail.c"
# 1 "<built-in>"
# 1 "<command line>"
# 1 "newtail.c"
# 1 "/home/c/lucier/local/gcc-test/lib/gcc-lib/sparc-sun-solaris2.8/3.3/include/stdio.h" 1 3 4
# 14 "/home/c/lucier/local/gcc-test/lib/gcc-lib/sparc-sun-solaris2.8/3.3/include/stdio.h" 3 4
# 1 "/home/c/lucier/local/gcc-test/lib/gcc-lib/sparc-sun-solaris2.8/3.3/include/stdarg.h" 1 3 4
# 43 "/home/c/lucier/local/gcc-test/lib/gcc-lib/sparc-sun-solaris2.8/3.3/include/stdarg.h" 3 4
typedef __builtin_va_list __gnuc_va_list;
# 15 "/home/c/lucier/local/gcc-test/lib/gcc-lib/sparc-sun-solaris2.8/3.3/include/stdio.h" 2 3 4
# 34 "/home/c/lucier/local/gcc-test/lib/gcc-lib/sparc-sun-solaris2.8/3.3/include/stdio.h" 3 4
#pragma ident "@(#)stdio.h 1.78 99/12/08 SMI"
# 1 "/usr/include/iso/stdio_iso.h" 1 3 4
# 32 "/usr/include/iso/stdio_iso.h" 3 4
#pragma ident "@(#)stdio_iso.h 1.2 99/10/25 SMI"
# 1 "/usr/include/sys/feature_tests.h" 1 3 4
# 13 "/usr/include/sys/feature_tests.h" 3 4
#pragma ident "@(#)feature_tests.h 1.18 99/07/26 SMI"
# 1 "/usr/include/sys/isa_defs.h" 1 3 4
# 9 "/usr/include/sys/isa_defs.h" 3 4
#pragma ident "@(#)isa_defs.h 1.20 99/05/04 SMI"
# 16 "/usr/include/sys/feature_tests.h" 2 3 4
# 36 "/usr/include/iso/stdio_iso.h" 2 3 4
# 1 "/usr/include/sys/va_list.h" 1 3 4
# 9 "/usr/include/sys/va_list.h" 3 4
#pragma ident "@(#)va_list.h 1.12 99/05/04 SMI"
# 26 "/usr/include/sys/va_list.h" 3 4
typedef void *__va_list;
# 37 "/usr/include/iso/stdio_iso.h" 2 3 4
# 1 "/home/c/lucier/local/gcc-test/lib/gcc-lib/sparc-sun-solaris2.8/3.3/include/stdio_tag.h" 1 3 4
# 18 "/home/c/lucier/local/gcc-test/lib/gcc-lib/sparc-sun-solaris2.8/3.3/include/stdio_tag.h" 3 4
#pragma ident "@(#)stdio_tag.h 1.3 98/04/20 SMI"
# 30 "/home/c/lucier/local/gcc-test/lib/gcc-lib/sparc-sun-solaris2.8/3.3/include/stdio_tag.h" 3 4
typedef struct __FILE __FILE;
# 38 "/usr/include/iso/stdio_iso.h" 2 3 4
# 1 "/usr/include/stdio_impl.h" 1 3 4
# 9 "/usr/include/stdio_impl.h" 3 4
#pragma ident "@(#)stdio_impl.h 1.8 99/06/10 SMI"
# 22 "/usr/include/stdio_impl.h" 3 4
typedef int ssize_t;
# 38 "/usr/include/stdio_impl.h" 3 4
struct __FILE
{
ssize_t _cnt;
unsigned char *_ptr;
unsigned char *_base;
unsigned char _flag;
unsigned char _file;
unsigned __orientation:2;
unsigned __ionolock:1;
unsigned __filler:5;
};
# 39 "/usr/include/iso/stdio_iso.h" 2 3 4
# 59 "/usr/include/iso/stdio_iso.h" 3 4
typedef long long __longlong_t;
# 75 "/usr/include/iso/stdio_iso.h" 3 4
typedef __FILE FILE;
typedef unsigned int size_t;
typedef long fpos_t;
# 147 "/usr/include/iso/stdio_iso.h" 3 4
extern __FILE __iob[20];
# 164 "/usr/include/iso/stdio_iso.h" 3 4
extern int remove(const char *);
extern int rename(const char *, const char *);
extern FILE *tmpfile(void);
extern char *tmpnam(char *);
extern int fclose(FILE *);
extern int fflush(FILE *);
extern FILE *fopen(const char *, const char *);
extern FILE *freopen(const char *, const char *, FILE *);
extern void setbuf(FILE *, char *);
extern int setvbuf(FILE *, char *, int, size_t);
extern int fprintf(FILE *, const char *, ...);
extern int fscanf(FILE *, const char *, ...);
extern int printf(const char *, ...);
extern int scanf(const char *, ...);
extern int sprintf(char *, const char *, ...);
extern int sscanf(const char *, const char *, ...);
extern int vfprintf(FILE *, const char *, __va_list);
extern int vprintf(const char *, __va_list);
extern int vsprintf(char *, const char *, __va_list);
extern int fgetc(FILE *);
extern char *fgets(char *, int, FILE *);
extern int fputc(int, FILE *);
extern int fputs(const char *, FILE *);
extern int getc(FILE *);
extern int putc(int, FILE *);
extern int getchar(void);
extern int putchar(int);
extern char *gets(char *);
extern int puts(const char *);
extern int ungetc(int, FILE *);
extern size_t fread(void *, size_t, size_t, FILE *);
extern size_t fwrite(const void *, size_t, size_t, FILE *);
extern int fgetpos(FILE *, fpos_t *);
extern int fseek(FILE *, long, int);
extern int fsetpos(FILE *, const fpos_t *);
extern long ftell(FILE *);
extern void rewind(FILE *);
extern void clearerr(FILE *);
extern int feof(FILE *);
extern int ferror(FILE *);
extern void perror(const char *);
extern int __filbuf(FILE *);
extern int __flsbuf(int, FILE *);
# 37 "/home/c/lucier/local/gcc-test/lib/gcc-lib/sparc-sun-solaris2.8/3.3/include/stdio.h" 2 3 4
# 105 "/home/c/lucier/local/gcc-test/lib/gcc-lib/sparc-sun-solaris2.8/3.3/include/stdio.h" 3 4
typedef long off_t;
typedef __longlong_t off64_t;
# 123 "/home/c/lucier/local/gcc-test/lib/gcc-lib/sparc-sun-solaris2.8/3.3/include/stdio.h" 3 4
typedef __longlong_t fpos64_t;
# 151 "/home/c/lucier/local/gcc-test/lib/gcc-lib/sparc-sun-solaris2.8/3.3/include/stdio.h" 3 4
extern unsigned char _sibuf[], _sobuf[];
# 193 "/home/c/lucier/local/gcc-test/lib/gcc-lib/sparc-sun-solaris2.8/3.3/include/stdio.h" 3 4
extern unsigned char *_bufendtab[];
extern FILE *_lastbuf;
# 229 "/home/c/lucier/local/gcc-test/lib/gcc-lib/sparc-sun-solaris2.8/3.3/include/stdio.h" 3 4
extern void setbuffer(FILE *, char *, size_t);
extern int setlinebuf(FILE *);
extern int snprintf(char *, size_t, const char *, ...);
extern int vsnprintf(char *, size_t, const char *, __gnuc_va_list);
# 250 "/home/c/lucier/local/gcc-test/lib/gcc-lib/sparc-sun-solaris2.8/3.3/include/stdio.h" 3 4
extern FILE *fdopen(int, const char *);
extern char *ctermid(char *);
extern int fileno(FILE *);
# 276 "/home/c/lucier/local/gcc-test/lib/gcc-lib/sparc-sun-solaris2.8/3.3/include/stdio.h" 3 4
extern FILE *popen(const char *, const char *);
extern char *cuserid(char *);
extern char *tempnam(const char *, const char *);
extern int getopt(int, char *const *, const char *);
extern int getsubopt(char **, char *const *, char **);
extern char *optarg;
extern int optind, opterr, optopt;
extern int getw(FILE *);
extern int putw(int, FILE *);
extern int pclose(FILE *);
extern int fseeko(FILE *, off_t, int);
extern off_t ftello(FILE *);
# 305 "/home/c/lucier/local/gcc-test/lib/gcc-lib/sparc-sun-solaris2.8/3.3/include/stdio.h" 3 4
extern FILE *fopen64(const char *, const char *);
extern FILE *freopen64(const char *, const char *, FILE *);
extern FILE *tmpfile64(void);
extern int fgetpos64(FILE *, fpos64_t *);
extern int fsetpos64(FILE *, const fpos64_t *);
extern int fseeko64(FILE *, off64_t, int);
extern off64_t ftello64(FILE *);
# 8 "newtail.c" 2
typedef int obj;
typedef struct processor_struct
{
obj r0, r1;
obj *sp;
} processor;
typedef int (*fn) (processor *proc);
# 45 "newtail.c"
register obj r0 asm ("%g2");
register obj r1 asm ("%g3");
register obj *sp asm ("%g4");
# 60 "newtail.c"
int point0 (processor *proc);
int point1 (processor *proc);
int point2 (processor *proc);
int point3 (processor *proc);
int point4 (processor *proc);
int point5 (processor *proc);
int point6 (processor *proc);
int point7 (processor *proc);
int point8 (processor *proc);
int point0 (processor *proc) {
r0 = ((obj)(point3));
r1 = 1000000;
return point1 (proc);
}
int point1 (processor *proc) {
if (r1 == 0)
{
r1 = 0;
return ((fn)(r0)) (proc);
}
else
{
r1--;
return point2 (proc);
}
}
int point2 (processor *proc) {
if (r1 == 0)
{
r1 = 1;
return ((fn)(r0)) (proc);
}
else
{
r1--;
return point1 (proc);
}
}
int point3 (processor *proc) {
return r1;
}
int point4 (processor *proc) {
r0 = ((obj)(point8));
r1 = 20;
return point5 (proc);
}
int point5 (processor *proc) {
if (r1 < 2)
return ((fn)(r0)) (proc);
else
{
*--sp = r0;
*--sp = r1;
r1--;
r0 = ((obj)(point6));
return point5 (proc);
}
}
int point6 (processor *proc) {
*--sp = r1;
r1 = sp[1] - 2;
r0 = ((obj)(point7));
return point5 (proc);
}
int point7 (processor *proc) {
r1 += sp[0];
r0 = sp[2];
sp += 3;
return ((fn)(r0)) (proc);
}
int point8 (processor *proc) {
return r1;
}
int computed_goto (processor *proc, int start)
{
void *lab[9] = { &&point0, &&point1, &&point2, &&point3, &&point4
, &&point5, &&point6, &&point7, &&point8 };
void **pc = &lab[start];
goto *(*pc);
point0:
r0 = ((obj)(&lab[3]));
r1 = 1000000;
goto point1;
point1:
if (r1 == 0)
{
r1 = 0;
goto *(*((void**)(r0)));
}
else
{
r1--;
goto point2;
}
point2:
if (r1 == 0)
{
r1 = 1;
goto *(*((void**)(r0)));
}
else
{
r1--;
goto point1;
}
point3:
return r1;
point4:
r0 = ((obj)(&lab[8]));
r1 = 20;
goto point5;
point5:
if (r1 < 2)
goto *(*((void**)(r0)));
else
{
*--sp = r0;
*--sp = r1;
r1--;
r0 = ((obj)(&lab[6]));
goto point5;
}
point6:
*--sp = r1;
r1 = sp[1] - 2;
r0 = ((obj)(&lab[7]));
goto point5;
point7:
r1 += sp[0];
r0 = sp[2];
sp += 3;
goto *(*((void**)(r0)));
point8:
return r1;
}
int main (int argc, char *argv[])
{
int i;
processor p;
processor *proc = &p;
obj stack[1000];
sp = &stack[1000];
if (argc != 3)
printf ("usage: ./a.out <0_or_1> <0_or_1>\n");
else
{
if (atoi (argv[2]) == 1)
{
printf ("tail-call implementation\n");
if (atoi (argv[1]) == 1)
{
obj r;
for (i=0; i<100; i++)
r = point0 (proc);
printf ("odd(1000000) = %d\n", r);
}
else
{
obj r;
for (i=0; i<100; i++)
r = point4 (proc);
printf ("fib(20) = %d\n", r);
}
}
else
{
printf ("computed goto implementation\n");
if (atoi (argv[1]) == 1)
{
obj r;
for (i=0; i<100; i++)
r = computed_goto (proc, 0);
printf ("odd(1000000) = %d\n", r);
}
else
{
obj r;
for (i=0; i<100; i++)
r = computed_goto (proc, 4);
printf ("fib(20) = %d\n", r);
}
}
}
_exit (0);
return 0;
}
More information about the Gcc
mailing list