Teach rustc to do tail calls

[graydon]

Rustc doesn't know how to do tail calls ('be' rather than 'ret') yet. It shouldn't be too hard to teach it how.

[brson]

Per Graydon, we need to do some more thinking about calling conventions before implementing this. LLVM requires the fastcc convention to implement tail calls, but it doesn't do quite what we want:

graydon: brson: judging from comments in llvm-land, we may be in trouble. we might be able to compensate for what fastcc is doing today, but it's allowed to change its mind tomorrow.
graydon: I thought fastcc == x86_fastcall, but I was wrong.
graydon: those are different calling conventions. fastcc is "whatever llvm feels like this week"
graydon: we need to switch to x86_fastcall and then, longer-term, write our own calling convention.

[graydon]

This is currently half-implemented due to some complications in the way LLVM treats tail calls. Rustc parses 'be' expressions and translates them as call+ret pairs, which is enough to get us to 'working' on simple, not-very-deep cases. Might be enough to bootstrap.

There is apparently only one CC (fastcc) which supports guaranteed tail calls, and to adapt to it we need to change our ABI assumptions in several places (it turns into callee-restore when you enable the -tailcallopt flag). So even if we annotate our call+ret pairs with 'tail', as required, we can't actually tell LLVM to start performing that optimization yet.

[graydon]

Turned out not to need more implementation than is shown here for self-hosting. Punting to next milestone.

[graydon]

Anyone feel we're actually going to do this anymore?

[brson]

Doesn't seem like it's going to happen.

[marijnh]

What is the situation with LLVM and tail calls? If they can be made to reliably work without some invasive stuff like declaring the callee to be tail-called, we could define a limited set of things that can be passed to tail-calls (caller's own arguments, scalars), and error when something else is passed. Such tail calls might not be very useful in practice, though.

[kud1ing]

Is it possible that looking at Haskell's GHC LLVM-backend might be helpful?

http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler/Backends/LLVM
http://llvm.org/docs/LangRef.html#callingconv
http://llvm.org/docs/CodeGenerator.html#tailcallopt

[graydon]

They only work with a callee ABI that is suboptimal in non-tail-call cases. So in a sense, yes, they require the callee to be declared-to-be-tail-called.

We could implement this by, say, analyzing a crate and when we find a function that is tail called, either separately compiling it under the friendly-to-tail-call ABI, or compiling wrappers that switch ABI on entry, or something. Or alternatively we can switch every function everywhere to using the tail-call-friendly ABI. I'm not sure if we're currently doing that. We were for a while but we may have stopped. It's the LLVM "fastcall" ABI, which I don't think we're using anymore.

In any case, it's a bit of a mess.

[msullivan]

We have sibling call optimization, now. Are we planning to try to do more?

[catamorphism]

Not going to happen, except to the extent addressed by #2216. Solution for #2216 should be broad enough to support general state machine coding.

[brson]

This continues to come up in conversation, and we've reserved be again. Reopening.