Hacker News Reader

Comment by toast0 | Hacker News Reader

With the right calling convention, tail calls could conform to the convention.

A tail call certainly can't use a CALL instruction, because it would set the wrong return address. But that doesn't mean it's not a call; architectures without CALL/RETURN instructions exist, but you can still call into functions and return from them, the compiler just has to do different work.

In a callee cleanup convention, a tail caller could adjust the stack and jump to an unaware tail callee. The original caller and the tail callee would be none the wiser. I don't know enough to really evaluate calling conventions against each other, but it's pretty clear that caller cleanup makes tail call optimization more intrusive.

View on HN

>In a callee cleanup convention, a tail caller could adjust the stack and jump to an unaware tail callee.

You can still do that with a caller-cleanup convention. Suppose you have a convention like

* Set up stack

* Call

* Clean up stack

and you have functions f(), g(), and h(), where g() and h() use this convention and f() calls into g(), and g() into h(). The sequence of instructions from f() to h() without TCO would be

* f: Set up stack for g()

* f: Call g()

* g: Do work

* g: Set up stack for h()

* g: Call h()

* h: Do work

* h: Return

* g: Clean up stack

* g: Return

* f: Clean up stack

And with TCO:

* f: Set up stack for g()

* f: Call g()

* g: Do work

* g: Move things around on the stack so that h()'s arguments are written where g()'s were. This may require a temporary stack allocation that's released before the next step.

* g: Jump to h()

(At this point it looks as if f() called h() directly.)

* h: Do work

* h: Return

* f: Clean up stack

This is always possible as long as h()'s caller-managed stack allocation is no bigger than g()'s.

h() can't have more arguments than g(): that's an important limitation.

Consider what was being discussed originally, though. If h() has fewer arguments than g() and is in a different module (e.g. a static library) from h() such that the calling convention was necessary, how would h() recurse back to g()?

The example you set up was about f() calling into g() calling into h(). Why do you mention h() calling into g() now?

The whole thread is about how the traditional calling convention makes it difficult to implement TCO in C. Functions with different arity having different stack layout is indeed one of the roadblocks, so I think we agree here, no?

That was in response to a specific point that TCO needed callee-cleanup. But nobody cares about TCO in non-recursive call stacks, and nobody does cross-module recursion. Hence my question: if the only situation where anyone would care whether TCO is being performed is one in which the compiler can see both sides of the call, what does it matter what the calling convention is? The compiler is not bound to use any calling convention to generate the code for the call, it can just generate the caller and callee to be compatible with other and with no one else.

Ah, now I see that indeed we agree without understanding each other. The source is a misinterpretation of your sentence far up the thread:

> I can't see why the calling convention could matter.

The "could matter" was understood as "would influence TCO" and so the rest of the thread was devoted to explain how the two are connected, while you meant "should be fixed and not be changed at the compiler's whims".

And you are right, of course: if a function is static and its address is never taken, the compiler can choose whatever calling strategy it wants, possibly one that facilitates TCO.

No, I meant the former. Even if those conditions are not met, TCO is not off the table. The compiler can simply generate a second copy of the function specifically for the recursive call.

Reply on news.ycombinator.com