4 ms·

>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

>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.
- omginternets 6y ago
  Sorry, I should have been more precise: I was referring to detecting that a function is tail recursive. (Yours is still a helpful explanation, though -- thanks!)
  - maximilianburke 6y ago
    I can't say how LLVM does it but in a compiler I built I detected tail recursion by scanning the IR and if the value of a recursive call (ie: call to self) was immediately returned it was considered a candidate for TCE. If the value was consumed by the parent, it wasn't.
chriswarbo 6y ago
As I said, tail-recursion is just a particular use of tail calls. Tail calls are very simple: anything of the form 'return foo(...)'; or, in languages without 'return', a function call which is the at the end of the definition (i.e. the last step). All we require is that the current function is calling some other function, and passing on its return value unchanged. For example, let's take a simple function: int foo(int x) { return bar(x); } 'return bar(x);' is a tail-call, since 'foo' isn't doing anything with the result; calling 'foo' is equivalent to calling 'bar'. In this case the compiler could actually replace every occurrence of 'foo' with 'bar' (e.g. inlining it), but we can't do that in general. However, when we call 'bar' we certainly don't need to keep any of 'foo's machinery around (stack frames, local variables, register contents, etc.); we can just start executing the code for 'bar' (i.e. a jump instruction). More realistically, 'foo' and 'bar' might not be equivalent, e.g. int foo(int x) { int y = baz(x); return bar(x + 3 * y); } Here we can't just replace calls to 'foo' with calls to 'bar', since they do different things. However, notice the order that things will run in: (1) 'baz(x)' will be called, (2) 'x + 3 * y' will be calculated, (3) 'bar' will be called. Even though these 'foo' and 'bar' functions are very different to begin with, once we reach step three (the call to 'bar') the remaining instructions are the same (since 'foo' is calling 'bar' and returning its result unchanged; i.e. the definition of a tail-call!). Hence we can still discard 'foo's machinery and just jump to 'bar' (e.g. we can throw away 'y'; and the compiler can ensure the result of (2) is put where 'bar' expects its argument). If 'foo' and 'bar' are the same function then we happen to have tail recursion. For example: uint fac(uint n) { if (n) return fac(n-1); return 1; } Here 'return fac(n-1)' is a tail-call; it also happens to be tail-recursion, since it's calling the 'fac' function from within the 'fac' function. We don't need to keep the stack frame for 'fac(n)' around, we can just overwrite it with the stack frame of 'fac(n-1)', and so on. We can also have mutually tail-recursive functions, e.g. uint even(uint n) { if (n) odd(n-1); return 1; } uint odd(uint n) { if (n) even(n-1); return 0; } This is harder to spot than direct tail-recursion, but it doesn't matter since tail-recursion isn't particularly special. As long as we implement tail-calls efficiently, then the benefits apply to tail-recursive functions (like 'fac') and mutually tail-recursive functions (like 'even' and 'odd'), as well as many other places which just-so-happen to use tail-calls. Intuitively, any time we find ourselves using a "main loop", or "driver loop", etc. which just calls out to a sequence of functions, possibly passing the return values of one into arguments of the next, that's equivalent to having each of those functions make a tail-call to the next one (i.e. such loops are "trampolines").

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.

omginternets 6y ago
Sorry, I should have been more precise: I was referring to detecting that a function is tail recursive. (Yours is still a helpful explanation, though -- thanks!)
- maximilianburke 6y ago
  I can't say how LLVM does it but in a compiler I built I detected tail recursion by scanning the IR and if the value of a recursive call (ie: call to self) was immediately returned it was considered a candidate for TCE. If the value was consumed by the parent, it wasn't.

chriswarbo 6y ago

As I said, tail-recursion is just a particular use of tail calls. Tail calls are very simple: anything of the form 'return foo(...)'; or, in languages without 'return', a function call which is the at the end of the definition (i.e. the last step). All we require is that the current function is calling some other function, and passing on its return value unchanged. For example, let's take a simple function: int foo(int x) { return bar(x); } 'return bar(x);' is a tail-call, since 'foo' isn't doing anything with the result; calling 'foo' is equivalent to calling 'bar'. In this case the compiler could actually replace every occurrence of 'foo' with 'bar' (e.g. inlining it), but we can't do that in general. However, when we call 'bar' we certainly don't need to keep any of 'foo's machinery around (stack frames, local variables, register contents, etc.); we can just start executing the code for 'bar' (i.e. a jump instruction). More realistically, 'foo' and 'bar' might not be equivalent, e.g. int foo(int x) { int y = baz(x); return bar(x + 3 * y); } Here we can't just replace calls to 'foo' with calls to 'bar', since they do different things. However, notice the order that things will run in: (1) 'baz(x)' will be called, (2) 'x + 3 * y' will be calculated, (3) 'bar' will be called. Even though these 'foo' and 'bar' functions are very different to begin with, once we reach step three (the call to 'bar') the remaining instructions are the same (since 'foo' is calling 'bar' and returning its result unchanged; i.e. the definition of a tail-call!). Hence we can still discard 'foo's machinery and just jump to 'bar' (e.g. we can throw away 'y'; and the compiler can ensure the result of (2) is put where 'bar' expects its argument). If 'foo' and 'bar' are the same function then we happen to have tail recursion. For example: uint fac(uint n) { if (n) return fac(n-1); return 1; } Here 'return fac(n-1)' is a tail-call; it also happens to be tail-recursion, since it's calling the 'fac' function from within the 'fac' function. We don't need to keep the stack frame for 'fac(n)' around, we can just overwrite it with the stack frame of 'fac(n-1)', and so on. We can also have mutually tail-recursive functions, e.g. uint even(uint n) { if (n) odd(n-1); return 1; } uint odd(uint n) { if (n) even(n-1); return 0; } This is harder to spot than direct tail-recursion, but it doesn't matter since tail-recursion isn't particularly special. As long as we implement tail-calls efficiently, then the benefits apply to tail-recursive functions (like 'fac') and mutually tail-recursive functions (like 'even' and 'odd'), as well as many other places which just-so-happen to use tail-calls. Intuitively, any time we find ourselves using a "main loop", or "driver loop", etc. which just calls out to a sequence of functions, possibly passing the return values of one into arguments of the next, that's equivalent to having each of those functions make a tail-call to the next one (i.e. such loops are "trampolines").