Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Teach rustc to do tail calls #217

Closed
graydon opened this issue Jan 27, 2011 · 18 comments
Closed

Teach rustc to do tail calls #217

graydon opened this issue Jan 27, 2011 · 18 comments
Labels
A-LLVM Area: Code generation parts specific to LLVM. Both correctness bugs and optimization-related issues.

Comments

@graydon
Copy link
Contributor

graydon commented Jan 27, 2011

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
Copy link
Contributor

brson commented Feb 10, 2011

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
Copy link
Contributor Author

graydon commented Feb 18, 2011

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
Copy link
Contributor Author

graydon commented May 5, 2011

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

@graydon
Copy link
Contributor Author

graydon commented Dec 5, 2011

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

@brson
Copy link
Contributor

brson commented Dec 6, 2011

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

@marijnh
Copy link
Contributor

marijnh commented Dec 7, 2011

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
Copy link

kud1ing commented Dec 18, 2011

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
Copy link
Contributor Author

graydon commented Dec 19, 2011

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.

@ghost ghost assigned graydon Mar 15, 2012
@msullivan
Copy link
Contributor

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

@catamorphism
Copy link
Contributor

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
Copy link
Contributor

brson commented Sep 28, 2012

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

@bstrie
Copy link
Contributor

bstrie commented Apr 10, 2013

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.

@bstrie bstrie closed this as completed Apr 10, 2013
@graydon graydon removed their assignment Jun 16, 2014
@burdges
Copy link

burdges commented Jul 31, 2015

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
Copy link

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
Copy link
Contributor

Stargateur commented Aug 3, 2016

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
Copy link
Member

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_).

telkkar added a commit to telkkar/rust_playing_around that referenced this issue Dec 5, 2016
The previous version used a bunch of manual string splitting and
recursion and bad decisions.

Recursion - To my knowledge, Rust doesn't support tail call
optimization, so recursion can eventually blow the stack on long
strings.

rust-lang/rust#217

String Splitting - Given that Rust strings are UTF8, there's a non-zero
chance that the algorithm may split on a non-character boundary if the
code isn't careful. Development while creating the split was
problematic at best and resulted in lots of issues involving the
boundary.

Bad decisions - I originally wrote the code in a way that bent Rust to
my will rather than using what Rust provided.
@timthelion
Copy link

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.

keeperofdakeys pushed a commit to keeperofdakeys/rust that referenced this issue Dec 12, 2017
Add MAP_STACK and MAP_HUGETLB entries to MIPS so that the nix crate can be built
@ewtoombs
Copy link

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.

kazcw pushed a commit to kazcw/rust that referenced this issue Oct 23, 2018
* update docs

* cargo clean deletes previous docs

* remove stdsimd from coresimd examples

* use stdsimd instead of coresimd in core docs

* add stdsimd as a dev-dependency of coresimd
djtech-dev pushed a commit to djtech-dev/rust that referenced this issue Dec 9, 2021
Added support for an llvm 11 feature
Fixed the Debug builder API to support the new arguments
celinval pushed a commit to celinval/rust-dev that referenced this issue Jun 4, 2024
* Move expected tests out of run-make tests.

* Skip copyright check for `*expected` and `.gitignore` files.

* Fix typos.

* Readd code to add scripts directory to path.

* Factor out duplicated code.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-LLVM Area: Code generation parts specific to LLVM. Both correctness bugs and optimization-related issues.
Projects
None yet
Development

No branches or pull requests