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.

[bstrie]

I think Graydon's comment on the mailing list:

https://mail.mozilla.org/pipermail/rust-dev/2013-April/003557.html

puts a nail in this coffin. Reproduced here:

---

On 10/04/2013 5:43 AM, Artella Coding wrote:

Hi does rust do tail call optimization? The reason I am asking is that
the following tail call recursive implementation results in a stack
overflow. Thanks.

No, and it very likely won't. We have a longstanding bug on this:

#217

as well as a wiki page and several mailing list threads:

https://github.com/mozilla/rust/wiki/Bikeshed-tailcall
https://mail.mozilla.org/pipermail/rust-dev/2011-August/000689.html
https://mail.mozilla.org/pipermail/rust-dev/2012-January/001280.html
...

The summary of all this is:

• We all know that tail calls are a virtuous language feature.
  Further elaboration of their virtues is not required. Many of us
  have lisp and ML backgrounds and would quite like them. Their
  absence is heartache and sadness, not arrived-at lightly.
• Tail calls "play badly" with deterministic destruction. Including
  deterministic drop of ~ boxes. Not to say that they're not
  composable, but the options for composing them are UI-awkward,
  performance-penalizing, semantics-complicating or all of the above.
• Tail calls also "play badly" with assumptions in C tools, including
  platform ABIs and dynamic linking.
• Tail calls require a calling convention that is a performance hit
  relative to the C convention.
• We find most cases of tail recursion convert reasonably well to
  loops, and most cases of non-recursive tail calls encode state
  machines that convert reasonably well to loops wrapped around
  enums. Neither of these are quite as pretty as the
  tail-call-using variants, but they do work and are "as fast"*,
  as well as idiomatic for C and C++ programmers (who are our
  primary audience).

I'm sorry to be saying all this, and it is with a heavy heart, but we
tried and did not find a way to make the tradeoffs associated with them
sum up to an argument for inclusion in rust.

-Graydon

• speed-wise, a switch-in-a-loop state machine is indirect dispatch so
  will likely run slower than a state machine encoded by tail calls from
  state to state; on the other hand if the way to get this performance
  "back" is to turn on tail calls everywhere, we'd be trading one isolated
  suboptimal-perf case for a cross-all-programs suboptimal-perf tax. We
  don't find this trade acceptable.

[burdges]

It's maybe worth noting that Haskell commonly needs a static argument transformation for inlining, fusion, etc. http://stackoverflow.com/a/9660027/667457

Rust could support the static argument transformation by saying that functions defined inside another function should be elidgible for tailcall optimizations. Or simply warn if tailcalls between functions nested inside another fuction failed sibling optimization. Not sure the current situation.

[real-felix]

It is sad the tail recursion will not be implemented. Then I have a question: why creating a language syntax that seems like a functional language syntax if there lacks an essential feature of functional?

[Stargateur]

I'm news in rust and I'm very sad. I try a tail recursive function and I stack overflow so fast. worst when I compile in release the behavior change. He just don't call my function. A friend said to me that the LLVM optimize to undefined value (LLVM know that is a tail recursion infinite ?!?).

fn rec(i: i32) {
  rec(i + 1)
}

fn main() {
  println!("{}", rec(0));
}

I agree with Boiethios, a language with functional features who doesn't implement tail call miss something.

I write in C and C++, they don't guarantee tail call, but in fact they handle it very well. It's not gonna stop me to learn rust, now I know that rust doesn't handle it. I will code without so it's not a big problem.

But I think that is a very good feature for a modern language.

notice that

fn rec(i: i32) {
  println!("Hello");
  rec(i + 1)
}

stack overflow too in release mode of cargo

[steveklabnik]

We have plans to eventually implement guaranteed TCO, if possible. We even reserved a keyword for it, "become". Please check the RFCs repo.

On Aug 3, 2016, 19:46 -0400, Antoine PLASKOWSKI [email protected], wrote:

I'm news in rust and I'm very sad. I try a tail recursive function and I stack overflow so fast. worst when I compile in release the behavior change. He just don't call my function. A friend said to me that the LLVM optimize to undefine value (LLVM know that is a tail recursion infinite ?!?).

fn rec(i: i32) { rec(i + 1) } fn main() { println!("{}", rec(0)); }

I'm agree with Boiethios, a language with functional features who doesn't implement tail call miss something.

I write in C and C++, they don't guaranty tail call but in fact they handle it very well. It's not gonna stop me to learn rust, now I know that rust doesn't handle it I will code without so it's not a big problem.

But I think that is a very good feature for a modern language.

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub (#217 (comment)), or mute the thread (https://github.com/notifications/unsubscribe-auth/AABsipoedHrbnKDekmzCr-dl8M6g-Gojks5qcShKgaJpZM4AC-q_).

[timthelion]

Just a question: It is hypothetically possible to do call graph analysis and transform tail calls into loops, at least within a single crate, but it is computationally expensive at compile time and quite tricky to code. Was there any discussion of this possibility? That would still be an option now, without regard to the choice of calling convention.

[ewtoombs]

lbstanza's approach is to require annotation of functions to make them eligible for TCO (defn+ instead of defn). In rust, that would largely mitigate the extra compile time overhead to timthelion's suggestion, just so long as you aren't using tail calls literally everywhere lol.