Implement support for tail calls in Wasmtime and Cranelift

[brunoczim]

To write a functional language compiler using this IR, tail call eliminations would be desirable. Are there any plans to support this? I couldn't find any details in the docs.

[lachlansneff]

Webassembly will be getting explicit tail calls soon, so cranelift will have to support as well. At the moment, tce is not supported. I assume we'll add an instruction.

[sunfishcode]

Agreed. We'll need direct and indirect forms. And, we'll need a new calling convention, since native calling conventions don't support guaranteed tail calling in general.

For the calling convention, I imagine we can pick between implementing GHC's and/or HiPE's, and/or inventing something Cranelift-specific.

[michalmuskala]

I would be interested in this for a project I'm working on.

As far as I understand, the primary issue with calling conventions and tail calls are callee-saved registers. The issue is that there's generally no way of efficiently knowing if they were already spilt to stack or not by the time we're in a function prologue and similarly if we should restore them (and even from where) in the epilogue.

That's one of the reasons, why AFAIK all the calling conventions in LLVM that support tail calls don't have any callee-saved registers. That way the tail call can easily deallocate the current frame and just jump into the new function passing all the arguments in the registers or on the stack if needed, but does not keep anything on the stack that would need to be manipulated when finally returning.

In LLVM (at least on x64) the HiPE convention means that all integer types are "upgraded" to i64, all stack slots are 8-byte wide and 8-byte aligned. It additionally pins 6 registers - for the process struct (similar to the VM data Cranelift already supports), for the heap pointer and for 4 arguments.
The GHC convention also promotes all integer types to i64 and pins 10 registers - 4 for VM state and 6 for arguments. It additionally pins some floating point registers for arguments.

Looking through the code and some opened issues and PRs, I can see there's quite some work on special-casing some arguments to be pinned in specific registers, etc. I wonder if that could be somehow generalized for the front-end to provide those settings, if needed.

As far as what I would consider ideal support for my project - I'd be happy with instructions to execute the guaranteed tail calls as well as a way to pin certain registers for needed data structures. I believe it's not very scalable for the code generator itself to support all the various schemes - it probably would be better for the front-end to provide this information somehow. A separate issue is stackmaps that is already touched on in a separate PR.

[wingo]

I am not sure that implementing wasm tail calls will require a specific calling convention, as the set of functions that may be tail-called is not known to the compiler. It is up to the tail-caller to restore registers that it saved when it performs the call, along with popping off any arguments pushed on the stack and possibly shuffling the saved return address. It is always possible to do this, AFAIU.

[sunfishcode]

@wingo Cranelift will indeed need special calling conventions for tail calls. You're right that if the current tail call proposal advances in its current form, we won't know which wasm functions are tail callable and which are not, but that just means we'll need to mark all wasm functions with the special calling conventions.

[wingo]

Hah I am an idiot, indeed a new convention is needed -- callees always have to pop spilled arguments, because callers no longer have the information to do this.

[wingo]

See also https://bugzilla.mozilla.org/show_bug.cgi?id=1572400.

[birktj]

Has any work been done on this lately?

[simvux]

Could this also be implemented in the x86 codegen?

[L-as]

Any update on this? Is it easy enough that an outsider could do it?

[cfallin]

Hi @L-as -- no, there unfortunately hasn't been progress on this. I'd love for that to be different; if you or another motivated person wants to tackle it, it's possible, but it's likely a month or more of delicate surgery updating our ABI and runtime code to use a new calling convention that supports tail calls.

It's the sort of problem that feels simple-ish at first -- indeed if you only have args that go in registers, and no callee-saves or spillslots, it can be as simple as some moves to set up the tailcall args and then a jump... but imposing those requirements on the CLIF producer to obtain a guaranteed tailcall would lead to some surprisingly brittle behavior where e.g. changing some unrelated code requires a spill and suddenly breaks the tailcall. Basically, in the general case, one needs to clean up one's own stackframe, restore callee-saves, and remove one's stack args from the stack, and then set up args on the stack for the callee, but possibly some of those args need to come from your spillslots or stack args (and if there are enough of them you can't hold all of them in the register file at once) so you need to do the arbitrary-state-permute possibly with some temps somewhere, or maybe in the worst case you set up the new frame before you pop your own then memmove() it up, but then what about return-area pointers that need to be fixed up... ah and take care to mind any stack-limit checks we need to do as well... in short, it's a mess.

The Bugzilla bug for SpiderMonkey's Wasm tail call support here contains a link to 25-page Google Doc that outlines in some good detail new ABI that the SpiderMonkey folks have designed to support this... it's a lot of work, but understanding that (or at least the reasons for its decisions) would be a good starting point.

Anyway, if you or anyone else has the resources to tackle this and want to dig in more, I'd be happy to help work out details!