investigation of tail calls on mainline

investigation of tail calls on mainline

[Brad Lucier]

[-- Attachment #1: Type: text/plain, Size: 1480 bytes --]

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

[-- Attachment #2: assembler program text --]
[-- Type: text/plain, Size: 5561 bytes --]

	.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)"

[-- Attachment #3: ascii text --]
[-- Type: text/plain, Size: 10250 bytes --]

# 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;
}

Re: investigation of tail calls on mainline

[Richard Henderson]

On Thu, Dec 12, 2002 at 10:23:53AM -0500, Brad Lucier wrote:
> 	call	%g2, 0
> 	mov	1, %g3
> 	ret
> 	restore %g0, %o0, %o0

At the moment that this is only going to work on x86, and
only on basic-improvements-branch.  It's certainly possible
to implement for sparc though.


r~

Re: investigation of tail calls on mainline

[Andreas Bauer]

On Thu, Dec 12, 2002 at 12:26:50PM -0800, Richard Henderson wrote:
> On Thu, Dec 12, 2002 at 10:23:53AM -0500, Brad Lucier wrote:
> > 	call	%g2, 0
> > 	mov	1, %g3
> > 	ret
> > 	restore %g0, %o0, %o0
> 
> At the moment that this is only going to work on x86, and
> only on basic-improvements-branch.  It's certainly possible
> to implement for sparc though.

I'm planning to pick up work on porting this mechanism together with
the help offered by Robert Stone.

Cheers,
Andi.

Re: investigation of tail calls on mainline

[Fergus Henderson]

On 12-Dec-2002, Richard Henderson <rth@redhat.com> wrote:
> On Thu, Dec 12, 2002 at 10:23:53AM -0500, Brad Lucier wrote:
> > 	call	%g2, 0
> > 	mov	1, %g3
> > 	ret
> > 	restore %g0, %o0, %o0
> 
> At the moment that this is only going to work on x86, and
> only on basic-improvements-branch.

And only for non-PIC code
(i.e. it won't work if you compile with `-fpic' or `-fPIC').

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.

Re: investigation of tail calls on mainline

[Fergus Henderson]

On 12-Dec-2002, Brad Lucier <lucier@math.purdue.edu> wrote:
> 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 ;-).

Well, computed gotos may work properly, but the program that you attached
also made use of global register variables, and global register variables
don't work properly.  If you use global register variables, the GCC code
generator can (and sometimes does) throw up its hands whenever it gets
to anything complicated, e.g. an assignment statement.

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.

Re: investigation of tail calls on mainline

[Brad Lucier]

> Well, computed gotos may work properly, but the program that you attached
> also made use of global register variables, and global register variables
> don't work properly.

Global register variables are not really necessary; -fPIC or -fpic may be,
unfortunately.

Brad