Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mentat!blc
From: blc@mentat.COM (Bruce Carneal)
Newsgroups: comp.arch
Subject: Re: Optimal Computer Architectures
Message-ID: <335@mentat.COM>
Date: 14 Nov 90 02:36:30 GMT
References: <212412@<1990Nov8> <3300209@m.cs.uiuc.edu> <334@mentat.COM> <1990Nov11.102907.7706@cs.cmu.edu> <9507@fy.sei.cmu.edu>
Reply-To: blc@mentat.UUCP (Bruce Carneal)
Organization: Mentat Inc., Santa Monica CA
Lines: 37

In article <1990Nov11.102907.7706@cs.cmu.edu> spot@WOOZLE.GRAPHICS.CS.CMU.EDU (Scott Draves) writes:

>It is my understanding that the SunOS 4.x compiler does
>detect and eliminate tail recursion.  This is verified by
>compiling (-O4 -S)
> (example of intra procedural tail recursion deleted)

Unfortunately this doesn't work in the general case.
Compiling under SunOS 4.1 with 'cc -O4 -S ...' the trivial
program fragment:

	func1(arg) int arg;  { return func2(arg); }
	func2(arg) int arg;  { return func3(arg); }
	func3(arg) int arg;  { return arg; }

you get (with some junk removed):

	_func1:
		save	%sp,-96,%sp
		call	_func2,1
		mov	%i0,%o0
		ret
		restore	%g0,%o0,%o0
	_func2:
		save	%sp,-96,%sp
		call	_func3,1
		mov	%i0,%o0
		ret
		restore	%g0,%o0,%o0
	_func3:
		retl
		nop

As shown, no tail call optimization occurs.
This form of call is used along the main paths
of some Streams modules (and elsewhere of course).
Later compilers can/do optimize those calls.