Including tail-callability in signatures

[sunfishcode]

An open question in the design space is whether to include tail-callability in function signatures. This would provide greater consumer flexibility for functions that are not tail-called. For example, non-tail-callable functions wouldn't be restricted to callee-pop calling conventions (on platforms where that applies).

This would also provide a tidy answer to the open question about tail calls to host functions: each host function would indicate its tail-callability in its signature.

Performing a tail call to a non-tail-callable function, or importing a non-tail-callable export as tail-callable, would have the same behavior as a type signature mismatch.

Performing a non-tail call to a tail-callable function, or importing a tail-callable export as non-tail-callable, could either:

• behave as a type signature mismatch (simpler for spec and consumers, less flexible for producers), or
• succeed (modest subtyping, more flexible for producers).

[rossberg]

Interesting suggestion, though I'm a bit wary of the complexity this would add. And I believe that the subtyping you mention would probably be essential, because tables or function pointers would need be able to be heterogeneous (or they become a major tedium). But once you allow that, how can you still use incompatible calling conventions?

[lukewagner]

If we don't want this feature to impose a cross-cutting constraint across all wasm ABIs for all time, I think we need tail-callability in the signature. Unless there is a zero-cost ABI (which doesn't require a frame pointer), I think this is just a performance requirement to keep wasm efficient by design.

[rossberg]

Okay, I added that and a discussion item to the agenda.

[rossberg]

Luke, perhaps I do not fully understand. When you say ABI, do you mean matching an ABI defined by a host environment? Or are you talking about Wasm-internal calling conventions? The former should only be relevant at the Wasm/host boundaries, AFAIU, and I thought we already assume some conversion/wrapping is necessary there. And for intra-Wasm calling conventions, why might tail calls impose constraints regarding frame pointers? Sorry if this is a dumb question.

[lukewagner]

I mean for the engine-internal calling convention. As for fp, some tail-call-enabling ABIs require an fp to be kept (in particular, caller-pop, where the caller pops by setting sp = fp + K). There are multiple options, of course, but iiuc all end up making some amount of perf sacrifice (for non tail calls), so I think it's necessary to understand the precise ABI implications.

[titzer]

In general I am skeptical that calling convention differences for tail-callable functions rank high on anyone's list of performance concerns, since there are other mitigations, such as inlining. A feature like this would have to be very strongly motivated by hard data.

I am wary of what amounts to a performance hint that has semantic implications, since it has cross-cutting concerns, i.e. affects every single function. That includes indirect calls, as well. I assume that the semantic check is motivated by the desire to avoid validating the entire module before code generation begins, because validation would be able to compute the no-tail-call-to-this-function property.

However, I am not totally against this performance hint. A hint in the true sense might be better. E.g. we could introduce an optional section that declares functions which are not tail called, to appear before bodies are seen, that would allow the engine (even a baseline single-pass compiler) to use a different calling convention for those functions. Of course, the engine would need a backup plan if those hints were lies. That would have no semantic impact, engines would be free to ignore it, and engines that care could be informed early (as opposed to verify the no-tail-call property themselves by validating the whole module).

[jfbastien]

It seems like for JS the main issue with tail-call was across boundaries? Would it work for WebAssembly to initially support tail-call only within a module, and to disallow export of tail-call functions? I think if we do this we can punt signature questions until / if we decide to allow export. Toolchains would need to emit a tai-call wrapper for exports, but I think this might capture most uses of tail-call (intra-module).

[lukewagner]

@titzer I think the burden of proof goes the other way: calls are one of the most fundamental operations in wasm so we need to be quite certain that adding a new features doesn't negatively effect performance of modules that don't use the feature (or perhaps only use it in a very limited manner). Even eliminating tail calls across module boundaries, having to do a first-pass analysis of a whole module to determine who-tail-calls-who (and the fact that a single tail-call of a table pessimistically makes every entry of the table tail-callable) seems bad.

[ElvishJerricco]

It's worth noting that, AFAIK, the only reason the callee can't be the one who pops it's arguments is because of C's support for varargs. WebAssembly does not have varargs. So if the callee pops it's arguments, it can then push arguments and perform a jump to another function, thus performing a tailcall. This is effectively the GHC calling convention. It's nice because there's no need for a signature difference, and functions can be called and tail called with the same ABI. Of course the drawback is that we have to ask WebAssembly hosts to use this calling convention, or something equivalent, so they are less free to choose something that might be more optimal for their platform. But as long as we don't have to worry about varargs, it's hard for me to imagine this being a real performance limitation for any platform.

EDIT: As for supporting varargs in C, we can just keep doing that the way we are doing it currently, with the stipulation that LLVM will refuse to generate tail calls for varargs functions.

[rossberg]

@ElvishJerricco, one of the tougher platforms here is Edge, because the Wasm implementation in that browser is bound by the preexisting Windows ABI's calling conventions. The entire Windows tool chain relies on these calling conventions being used consistently across languages. But I believe we have settled that issue, see the notes from the last CG meeting.

[lukewagner]

@rossberg But, to be clear, I think there was a performance benefit for Edge (and any other browser that wants to adhere to the win64 stack conventions) from having tail-callability in the signature.

[ElvishJerricco]

I do not see anything in the last meetings notes about tail calls or windows. I'd appreciate it if you could elaborate here.

I don't have a problem with having tail calls in the signstures (as long as we have a way to keep function pointers efficient across the multiple tables), but I do question whether it's really necessary. Also, in the last meeting that did have notes on tail calls, it was suggested that tail calling simply has a bounded stack increase instead of zero, and that therefore the tail call only needs to be performed some of the time. I fail to see how this is useful; if it can be performed at all, why not do it every time the wasm module asks for it? GHC uses a truly massive amount of tail calls, so I'd worry about any stack increase, even if there's a theoretical bound.

[lukewagner]

@rossberg Do you have the slides you presented with the Win64 ABI impl strategy?

But essentially, it required an extra dynamic field be passed by the caller to hold the total amount of argument stack space owned by the frame. This field would need to be maintained in general even when no tail calls were used, and so would introduce non-zero overhead just for the existence of the feature. With tail calls in the signature, this overhead would be restricted to just the uses of tail calls. In general, putting tail-callability in the signature allows an engine to easily give tail-callable functions their own ABI (w/o interprocedural analyses which will be both overly conservative and in conflict with streaming compilation).

[Pauan]

@ElvishJerricco There is a tail-call strategy used by some Scheme implementations where they don't do tail-call elimination on every call, but when the stack grows too big they "garbage collect" the stack, removing the unneeded tail calls.

It's important to note that this strategy is compliant with the Scheme specification, which mandates tail call elimination.

It will not run out of stack space no matter how deep the tail recursion is. It is solely an implementation detail, it does not affect the behavior of the program. So it is the same as zero-stack-space tail calls.

This strategy has the benefit that it doesn't incur any performance impact when making tail calls, and it might make it easier to integrate with other languages (like C) which don't have tail calls.

The downside of course is that when it runs the "garbage collector" it might take a long time. So rather than paying the price a little bit at a time, it pays the price all at once.

I'm not sure if that's related to the meeting's mention of "bounded stack", but it is one reason to not mandate zero-stack-space tail calls.

[ElvishJerricco]

Well anyway, it sounds like we should just have signatures and let the implementations choose how to represent it at the machine level. I would hope that tail calls aren't as expensive as a GC... But @Pauan is right, this is an implementation detail.

So can we just update the spec and add a tail-callable type of function, with two new instructions for (in)direct tail calls? I'd say it's fine to punt on importing tail-callables for now, but it also doesn't sound like it would be hard to just have that in the signature of the import. What other questions remain?