[rayiner]

The best way to deal with tail call "optimization" is to not treat it as an optimization at all. Tail calls are a syntactic property of source code. You can easily determine whether a given call is in a tail position by recursively traversing the AST. Then you just have to generate tail calls in a way that uses constant stack space. This is mostly a matter of properly designing the calling convention. See: www.complang.tuwien.ac.at/schani/diplarb.ps‎.

[cjh_]

Thanks for those words and that link.

I like that way of thinking of it, I see it as just reusing the existing stack frame as a call in a tail call position doesn't need anything from the current stack (returning to this frame adds no extra meaning to it).

Having never implemented them though I feel like my ideas still need some fleshing out, my naive approach seems to be similar to the idea of trampolining.

Really looking forward to reading the linked document, very thorough and looks to be just what I was looking for (it even covers architecture dependent aspects!).

[rayiner]

If you've got the freedom to design your calling convention, you don't need trampolines or anything like that.

The basic idea is to compile every call in a tail position to a jump. You just need to clean up your stack before making the call, and make sure to arrange your calling convention such that A can call B, which can jump to C, which can return directly to A.

In the A -> B -> C example, this means:

1) Using a callee-pops convention so that callees pop arguments off the stack rather than callers. If B and C take different numbers of arguments, A doesn't know how many arguments to pop. So functions should pop their arguments off the stack themselves before they return.

2) B must restore its callee-save registers before jumping to C, which will save those registers itself if it clobbers them.

3) To accommodate variadic functions, there has to be a hidden argument to let callees know how many arguments were actually pushed by the caller, so they can pop the right number.