If become was implemented, could it be supported everywhere?


#1

When I first started implementing become, I was very gung-ho about it. I felt like it could make totally new ways of programming in Rust possible. However, I have since soured on this for two reasons.

  1. (Less important) It imposes a tiny overhead on each non-tail function call.

    Tail call optimization forces LLVM to use a callee-pops calling convention. That means that every non-tail function call involves a stack readjustment. This might be a 1 instruction penalty.

  2. (Far more important) I don’t know if tail calls can be made portable, either cross-platform or cross-implementation.

    LLVM supports proper tail calls natively, via the tail attribute and the -tailcallopt option. However, the LLVM documentation only claims support on i386, x86-64, and PowerPC. GHC uses LLVM tail calls on ARM, but it uses a custom calling convention so this is not a guarantee that Rust can do the same.

    The situation is far worse for unconventional backends and alternative implementations. The alternative Rust compiler mrustc compiles via C, and cannot implement proper tail calls. Proper tail calls in WebAssembly are listed as a “future feature”, which means that it will be a long time before they (or, in fact, any way of emulating them) is implemented. Implementing proper tail calls in Rust would make life extremely difficult for those implementing the WebAssembly port. In fact, it might make an efficient implementation impossible.

For those reasons, I am reconsidering whether the world outside of Rust is ready for Rust to have proper tail calls. I would like to see what others think of this. Thoughts?


#2

What stops us implementing this as a MIR transformation? Why can’t rustc just do it? I understand that this might be technically complicated, but is it technically impossible?


#4

#5

Just FYU, I have cross compiled to arm and aarch64, with LLVM generating tail call optimization in release builds.


#6

My original plan for become was for it to be completely general: able to jump to any function from any other (as long as the return types match up). However, I see your point: in any self-recursive function, things are much easier.