Tail-call optimization in C is relatively recent

Tail-call optimization in C is relatively recent

Actually tail calls in C have not been around forever. The C calling convention has been that the callee does not remove any stuff the caller has put on the stack. The caller could see the declaration int f();, the actual call could have n>0 arguments, and the actual function could have m≤n parameters. That would not always work if the callee removed the arguments.

So the caller had to remove the arguments between the call and the following return, turning the call into a non-tail call.

When I looked in 1994 at the C compilers of the day, they did not perform tail-call optimization for the kind of usage shown in the article. In 2001 Mark Probst implemented tail-call optimization in GCC with a separate calling convention; he lists the limitations of the then-existing tail-call optimization in GCC in section 6.4, among them: "It cannot handle indirect calls" (which would have been used in tail calls for interpreter dispatch).

I have not looked at the issue since then (GCC's goto * was good enough (well, mostly)), and I had not much reason for assuming that something had changed wrt to GCC support for tail-calls (although one release note mentioned sibcalls, and I remember thinking that I should be checking that out.

Anyway, last year I read the paper on "Copy-and-Patch Compilation" by Xu and Kjolstad, and they use tail-call optimization. In any case, after reading that paper, I made some tests if gcc and clang can do tail-call optimization for the kind of tail calls shown in the article. And it works. And Xu and Kjolstad report that they use 100,000 code snippets, whereas we limit ourselves in Gforth to <2000 (for VM instructions, stack caching variations thereof, static superinstructions etc.). Being able to do 100,000 would allow us to use techniques that need too many different code snippets to be usable in a goto *-based system.

We have not gotten around to putting this into Gforth yet, so congratulations to the Python community for being there first.