[gclist] tail-calls in C/C++

[Henry G. Baker]

jgm@cs.cornell.edu:
> Why hasn't someone hacked gcc to do full tail-call elimination?
[snip]
> I've constructed an ML-to-C compiler using TIL/ML as the front-end
> and high-level optimizer.  I'm currently using the Boehm-Weiser
> collector.  I'd like to stick to standard C and 
> standard C calling conventions in the generated code, ruling out 
> Baker's Cheney-on-the-MTA, in order to maintain as much interoperability
> with legacy code (i.e., C and C++ libraries) as possible.  

For what its worth, Cheney-on-the-MTA _does_ interoperate with legacy
code -- e.g., I/O calls, etc. -- so long as the legacy code doesn't
try to call back.  (Even this will often work, but the rules become
more complex.)

> I'm already turning self-tail calls into C loops.  I've also looked at 
> integrating known, mutually recursive functions into a single large 
> function, threaded by gotos.  The only thing left to tackle are 
> tail-calls to "unknown" functions -- i.e., code pointers imported from 
> another module, or pulled out of a closure.  

This particular set of optimizations is compatible with (orthogonal to?)
the Cheney-on-the-MTA stuff.  You can aggregate mutually recursive functions
up to a certain size (to allow for separate compilation, e.g.), and then
start using Cheney-MTA/CPS for the 'foreign' functions.

> For many applications, this happens quite often.  In particular, any 
> code written in a continuation passing style has (by definition) lots 
> of tail-calls to unknown functions. 

Agreed.

> -Greg Morrisett
>  jgm@cs.cornell.edu

-- 
Henry Baker
www/ftp directory:
ftp.netcom.com:/pub/hb/hbaker/home.html