Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!rutgers!njin!princeton!phoenix!haahr
From: haahr@phoenix.Princeton.EDU (Paul Gluckauf Haahr)
Newsgroups: gnu.gcc
Subject: Re: Suggestions for improvements/enhancements to GCC
Summary: be careful with tail-call elimination
Message-ID: <8641@phoenix.Princeton.EDU>
Date: 24 May 89 00:54:36 GMT
References: <4462@omepd.UUCP>
Reply-To: haahr@princeton.edu (Paul Gluckauf Haahr)
Organization: Princeton University, Princeton NJ
Lines: 35

In article <4462@omepd.UUCP> mcg@mipon2.intel.com (Steven McGeady) writes:
> 2. Optimization Issues
> 	a. Support for leaf-procedure and tail-call optimizations
> 	   Tail-calls are calls made immediately prior to a return.  The call
> 	   can often "piggy-back" on the current procedure's stack, and avoid
> 	   the overhead of allocating another one.  The crucial test is
> 	   whether any of the called procedure's actual parameters are
> 	   addresses on the calling procedure's frame.  There is no easy way
> 	   to determine this currently (that I am aware of), so I scan all the
> 	   insns looking for a load effective address insn that references the
> 	   frame pointer.  This is not optimal though, because such references
> 	   may have nothing to do with the actual parameters of any particular
> 	   call.  An indication of whether a call is a potential tail-call
> 	   would be useful.

the conditions listed above are not sufficient.  any reference to
an address in stack allocated memory that might store the address
(ie, passing it to a function or storing it in a global) is enough
to indicate that tail-call elimination is unsafe.  for example,

	char *global;
	int f(const char *s, int n) {
		char buf[1000];
		strcpy(buf, s);
		if (n == 0)
			global = buf;
		if (*s == '\0') {
			printf("length of %s is %d\n", global, n);
			return n;
		}
		return f(s + 1, n + 1);
	}

if the tail-call is eliminated, the global pointer will be
pointing to the wrong instance of buf.