From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Mark H Weaver Newsgroups: gmane.lisp.guile.devel Subject: Problem with GCC as a Scheme compiler: tail calls Date: Thu, 07 Apr 2011 10:25:45 -0400 Message-ID: <87vcyqb0k6.fsf_-_@netris.org> References: <871v1ecvjr.fsf@netris.org> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: dough.gmane.org 1302186382 5570 80.91.229.12 (7 Apr 2011 14:26:22 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Thu, 7 Apr 2011 14:26:22 +0000 (UTC) Cc: guile-devel@gnu.org To: Noah Lavine Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Thu Apr 07 16:26:16 2011 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1Q7qA2-0001of-Tp for guile-devel@m.gmane.org; Thu, 07 Apr 2011 16:26:15 +0200 Original-Received: from localhost ([127.0.0.1]:49014 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Q7qA2-0007BR-6r for guile-devel@m.gmane.org; Thu, 07 Apr 2011 10:26:14 -0400 Original-Received: from [140.186.70.92] (port=41029 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Q7q9v-0007BM-NB for guile-devel@gnu.org; Thu, 07 Apr 2011 10:26:12 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Q7q9u-0006xK-6Z for guile-devel@gnu.org; Thu, 07 Apr 2011 10:26:07 -0400 Original-Received: from world.peace.net ([96.39.62.75]:42603) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Q7q9t-0006x7-Pp for guile-devel@gnu.org; Thu, 07 Apr 2011 10:26:06 -0400 Original-Received: from 209-6-39-128.c3-0.smr-ubr1.sbo-smr.ma.cable.rcn.com ([209.6.39.128] helo=freedomincluded) by world.peace.net with esmtpa (Exim 4.69) (envelope-from ) id 1Q7q9n-0002yA-KN; Thu, 07 Apr 2011 10:25:59 -0400 Original-Received: from mhw by freedomincluded with local (Exim 4.69) (envelope-from ) id 1Q7q9Z-0001KV-4i; Thu, 07 Apr 2011 10:25:45 -0400 In-Reply-To: (Noah Lavine's message of "Thu, 7 Apr 2011 09:10:26 -0400") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.3 (gnu/linux) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3) X-Received-From: 96.39.62.75 X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:12187 Archived-At: Noah Lavine writes: >> There is one _very_ serious problem with using GCC to compile Scheme, or >> at least there was the last time I researched this issue: tail calls. > > I might be wrong about this, but I thought that GCC supported multiple > calling conventions, with the user telling GCC which one to use > (cdecl, fastcall, possibly others). If so, it must have some way to > represent that in its intermediate representations. We might be able > to add our own calling convention. > > I also know that GCC has an --optimize-sibling-calls argument, which > will make it do something similar to at least some regular C calls. > I'm not sure if it's possible, but maybe we could arrange for whatever > code transformation implements this to be run on every Scheme call. Please read section 3.3 of the thesis I referenced: http://users.cecs.anu.edu.au/~baueran/thesis/ There you will find the list of conditions required for tail calls to be optimized by GCC circa 2003. Among other things, it includes: * The caller's stack frame must be empty (i.e. no stack-allocated local variables or temporaries). * No overlapping arguments (i.e. if it's too difficult to rearrange the input arguments on the stack to match what the next function expects, gcc will bail on the tail call) * No position-independent code on several platforms, including x86 (i.e. no tail calls in shared libraries) * No indirect calls (i.e. no tail calls to function pointers) * No setjmp or longjmp * Sibling call epilogue must be defined (i.e. many targets aren't supported) * Additional machine-independent constraints (i.e. many targets impose additional restrictions) The end result of all of these restrictions is that tail calls can only be optimized by GCC in extremely simple cases like fibonacci. Some of these restrictions may have been lifted since 2003, but I'm reasonably sure the problem has not been solved satisfactorily. If it had been, it would've been very big news in the functional programming language implementors community, since this has been a long-standing problem. However, what I find more persuasive than any paper is that fact that I've never found an implementation of a high-level programming language based on GCC that manages to support tail calls without doing some nasty hacks. Lots of smart people have worked on this, but to my knowledge, no one has found a good solution. The solutions I'm aware of are: * Cheney on the MTA, as is done by Chicken * Trampoline: instead of calling functions directly, return the address of the next function back to the trampoline loop. * Don't do function calls at all. Instead use inline asm to jump to the inside of the next function, passing arguments via register globals. GHC did this at one point. GCC's problems in this area are almost certainly the main reason so many functional programming language implementors have resorted to writing their own native code generators from scratch. If anyone knows of a recent breakthrough in this area, please speak up. Best, Mark