4 ms·

> There is no reason for a compiler to limit itself to the system ABI for completely internal functions. As far as I understand it, this limitation is also the

> There is no reason for a compiler to limit itself to the system ABI for completely internal functions. As far as I understand it, this limitation is also the only thing preventing tail-call elimination in C/C++. Tail-recursive functions are essentially the same as 'while' loops (execute some instructions then conditionally go back to the start); they just have different scope and calling conventions. In particular, 'while' loops are always inline and can't be referenced from other functions, but tail-recursive functions can. Hence compilers can apply more aggressive optimisations to 'while' loops, e.g. re-using the same stack frame and iterating with a conditional jump. However, as you say, functions-as-subroutines don't necessarily need to coincide with functions-as-interface. Tail-recursive functions which are only used internally can also be optimised to re-use the same stack frame and iterate with a conditional jump. If such functions are also exposed in the interface, it's pretty trivial to expose a dummy entry point which invokes the optimised version (if we want to); although cross-unit tail calls wouldn't be eliminated in that case. Of course, this is more useful than just writing 'while' loops in a different style (although I personally prefer recursion https://news.ycombinator.com/item?id=11150346 https://news.ycombinator.com/item?id=11150346 ), since tail calls don't have to be recursive: we can split our code up into modular, composable, self-contained functions without having to worry about stack usage (or code bloat caused by inlining into multiple locations).

deleted 6y ago
[deleted]
tom_mellior 6y ago
> As far as I understand it, this limitation is also the only thing preventing tail-call elimination in C/C++. Nothing "prevents" tail-call elimination in C. Compilers do it all the time. > Tail-recursive functions which are only used internally can also be optimised to re-use the same stack frame and iterate with a conditional jump. If such functions are also exposed in the interface, it's pretty trivial to expose a dummy entry point which invokes the optimised version (if we want to) Can you illustrate with a concrete example what you mean? If the function doesn't need a stack frame, there will be no stack frame either way. If the function needs a stack frame, that stack frame must be allocated in the function's start block either way, and tail recursive calls will of course not jump to that start block but to its successor. I don't see how being "exposed in the interface" (in C speak, static vs. non-static) would make a difference here.
- heavenlyblue 6y ago
  The issue is basically that tail-recursive functions need to have this information recorded in their signature (for external interfaces), but this is not recorded in C and thus you can't provide this guarantee at the interface boundaries.
  - tom_mellior 6y ago
    This is not concrete in any way. What guarantee do you mean? What "this information" should be "recorded in their signature"? What does this murky "information" have to do with enabling tail recursion? Here's a tail recursive function C function that is compiled to tail recursive machine code without any problems: https://gcc.godbolt.org/z/dc886a https://gcc.godbolt.org/z/dc886a This function can be called from external compilation units without any problems. Whether or not it is compiled to tail recursive code is an implementation detail that the caller doesn't need to know about.
omginternets 6y ago
>As far as I understand it, this limitation is also the only thing preventing tail-call elimination in C/C++. At the risk of introducing a tangent, can someone explain how compilers detect tail recursion? This is still a complete mystery to me.
- Silfen 6y ago
  I'd recommend "Lambda, the ultimate GOTO" https://dspace.mit.edu/handle/1721.1/5753 https://dspace.mit.edu/handle/1721.1/5753
  - omginternets 6y ago
    Reading this now, cheers! Is there anything in particular I should be looking for, or will it jump out at me (bearing in mind that I've never written anything more complex than an unoptimized Lisp interpreter) ?
- tom_mellior 6y ago
  What part of the detection is giving you trouble? Detecting whether a call is recursive, or whether it is a tail call that can be optimized? The first part is relatively easy, you typically have some sort of data structure representing calls and their targets, and you know what function you're currently compiling. If the function you're compiling is the same as a call's target, you have recursion. LLVM's code is at https://llvm.org/doxygen/TailRecursionElimination_8cpp_source.html https://llvm.org/doxygen/TailRecursionElimination_8cpp_sourc... The core of this detection is in findTRECandidate. It iterates backwards over a basic block, looking for call instructions whose call target is the current function F: CallInst *CI = nullptr; BasicBlock::iterator BBI(TI); while (true) { CI = dyn_cast<CallInst>(BBI); if (CI && CI->getCalledFunction() == &F) break; if (BBI == BB->begin()) return nullptr; // Didn't find a potential tail call. --BBI; } The harder part is detecting whether calls are in fact tail calls that you can replace by jumps. There are all sorts of special cases, like whether alloca() might be called by the function.
  - 6y ago
gsg 6y ago
> As far as I understand it, this limitation is also the only thing preventing tail-call elimination in C/C++. That is not the case. Guaranteed TCE requires deallocating the stack frame before jumping to the target, but that is not possible when an object is allocated in that frame and its address passed to the target function. In C++ there is also the issue of destructors needing to run after the tail-call returns (in which case it is not really a tail-call). C/C++ compilers can and do eliminate tail calls where possible, but there's no guarantee like you get from a compiler for a functional language.
- chriswarbo 6y ago
  > that is not possible when an object is allocated in that frame and its address passed to the target function Ah of course, I hadn't thought about live aliases to stack-allocated data. You're right about destructors; I agree that they're not really tail-calls (since we're processing results). > C/C++ compilers can and do eliminate tail calls where possible, but there's no guarantee like you get from a compiler for a functional language. Yes, I tend to say "tail-call optimisation" when it's opportunistic (e.g. GCC/Clang), and "tail-call elimination" when it's guaranteed (e.g. Scheme/ML).

deleted 6y ago

[deleted]

tom_mellior 6y ago

> As far as I understand it, this limitation is also the only thing preventing tail-call elimination in C/C++. Nothing "prevents" tail-call elimination in C. Compilers do it all the time. > Tail-recursive functions which are only used internally can also be optimised to re-use the same stack frame and iterate with a conditional jump. If such functions are also exposed in the interface, it's pretty trivial to expose a dummy entry point which invokes the optimised version (if we want to) Can you illustrate with a concrete example what you mean? If the function doesn't need a stack frame, there will be no stack frame either way. If the function needs a stack frame, that stack frame must be allocated in the function's start block either way, and tail recursive calls will of course not jump to that start block but to its successor. I don't see how being "exposed in the interface" (in C speak, static vs. non-static) would make a difference here.

heavenlyblue 6y ago
The issue is basically that tail-recursive functions need to have this information recorded in their signature (for external interfaces), but this is not recorded in C and thus you can't provide this guarantee at the interface boundaries.
- tom_mellior 6y ago
  This is not concrete in any way. What guarantee do you mean? What "this information" should be "recorded in their signature"? What does this murky "information" have to do with enabling tail recursion? Here's a tail recursive function C function that is compiled to tail recursive machine code without any problems: https://gcc.godbolt.org/z/dc886a https://gcc.godbolt.org/z/dc886a This function can be called from external compilation units without any problems. Whether or not it is compiled to tail recursive code is an implementation detail that the caller doesn't need to know about.

omginternets 6y ago

>As far as I understand it, this limitation is also the only thing preventing tail-call elimination in C/C++. At the risk of introducing a tangent, can someone explain how compilers detect tail recursion? This is still a complete mystery to me.

Silfen 6y ago
I'd recommend "Lambda, the ultimate GOTO" https://dspace.mit.edu/handle/1721.1/5753 https://dspace.mit.edu/handle/1721.1/5753
- omginternets 6y ago
  Reading this now, cheers! Is there anything in particular I should be looking for, or will it jump out at me (bearing in mind that I've never written anything more complex than an unoptimized Lisp interpreter) ?
tom_mellior 6y ago
What part of the detection is giving you trouble? Detecting whether a call is recursive, or whether it is a tail call that can be optimized? The first part is relatively easy, you typically have some sort of data structure representing calls and their targets, and you know what function you're currently compiling. If the function you're compiling is the same as a call's target, you have recursion. LLVM's code is at https://llvm.org/doxygen/TailRecursionElimination_8cpp_source.html https://llvm.org/doxygen/TailRecursionElimination_8cpp_sourc... The core of this detection is in findTRECandidate. It iterates backwards over a basic block, looking for call instructions whose call target is the current function F: CallInst *CI = nullptr; BasicBlock::iterator BBI(TI); while (true) { CI = dyn_cast<CallInst>(BBI); if (CI && CI->getCalledFunction() == &F) break; if (BBI == BB->begin()) return nullptr; // Didn't find a potential tail call. --BBI; } The harder part is detecting whether calls are in fact tail calls that you can replace by jumps. There are all sorts of special cases, like whether alloca() might be called by the function.
- 6y ago

gsg 6y ago

> As far as I understand it, this limitation is also the only thing preventing tail-call elimination in C/C++. That is not the case. Guaranteed TCE requires deallocating the stack frame before jumping to the target, but that is not possible when an object is allocated in that frame and its address passed to the target function. In C++ there is also the issue of destructors needing to run after the tail-call returns (in which case it is not really a tail-call). C/C++ compilers can and do eliminate tail calls where possible, but there's no guarantee like you get from a compiler for a functional language.

chriswarbo 6y ago
> that is not possible when an object is allocated in that frame and its address passed to the target function Ah of course, I hadn't thought about live aliases to stack-allocated data. You're right about destructors; I agree that they're not really tail-calls (since we're processing results). > C/C++ compilers can and do eliminate tail calls where possible, but there's no guarantee like you get from a compiler for a functional language. Yes, I tend to say "tail-call optimisation" when it's opportunistic (e.g. GCC/Clang), and "tail-call elimination" when it's guaranteed (e.g. Scheme/ML).