8

I've tried to search, but was unable to find: what are requisites for functions so that gcc would optimize the tail recursion? Is there any reference or list that would contain the most important cases? Since this is version specific, of my interests are 4.6.3 or higher versions (the newer the better). However, in fact, any concrete reference would be greatly appreciated.

Thanks in advance!

dtldarek
  • 949
  • 1
  • 13
  • 17

1 Answers1

15

With -O2 enabled, gcc will perform tail call optimization, if possible. Now, the question is: When is it possible?

It is possible to eliminate a single recursive call whenever the recursive call happens either immediately before or inside the (single) return statement, so there are no observable side effects afterwards other than possibly returning a different value. This includes returning expressions involving the ternary operator.
Note that even if there are several recursive calls in the return expression (such as in the well-known fibonacci example: return (n==1) ? 1 : fib(n-1)+fib(n-2);), tail call recursion is still applied, but only ever to the last recursive call.

As an obvious special case, if the compiler can prove that the recursive function (and its arguments) qualifies as constant expression, it can (up to a configurable maximum recursion depth, by default 500) eliminate not only the tail call, but the entire execution of the function. This is something GCC does routinely and quite reliably at -O2, which even includes calls to certain library functions such as strlen on literals.

Damon
  • 67,688
  • 20
  • 135
  • 185
  • I remember that few versions ago I had a problem where gcc didn't optimize tail calls for some virtual function, but I was unable to reproduce this behavior now. Are there any special restrictions there? – dtldarek Apr 09 '13 at 10:30
  • 1
    Virtual function calls are converted to "normal" function calls if the object type is known at compile time, and so they can be tail call optimized and inlined. However, when they are really _virtual_ function calls, they cannot be optimized, because there is no way to know at compile time what will be called. There is no other choice but to do a "real" virtual call via the vtable. For example, when you pass a `B*` to your function and call `foo()` on that pointer (with `D1` and `D2` deriving from `B`), this might call `D1::foo` or `D2::foo` -- recursive or not, the compiler cannot know. – Damon Apr 09 '13 at 10:45
  • For tail-call optimization you don't need to know if the function is recursive, you just switch `call` to `jmp` and that's it (more or less). Gcc is able to do it with function pointers, do you have any idea why vtable would be any different (right now it does tail-calls for virtual functions too)? – dtldarek Apr 09 '13 at 11:12
  • In a very simplified way, you're correct that tail call optimization "only" replaces `call` with `jmp` (though, with additional constraints on observable effects as stated above, and to a slightly different code location). However, a non-static dispatch is a little bit more involved than a simple `call` or a function pointer in the general case (in the _easiest_ case it is equivalent to a function pointer). It certainly works reliably (always) with static dispatch of virtual functions, and it may (or may not) work with dynamic dispatch. Why or why not in one particular case is hard to tell. – Damon Apr 09 '13 at 12:38
  • Within a virtual function, the compiler should know what a recursive call is going to do. If the virtual method `foo` ends with `return foo()`, then surely it can be replaced with a `jmp`? It's recursive, so it's going to know which `foo` to call, regardless of virtual. The only exception I can think of is if somebody explicitly calls `d -> Base::foo()` where `d` is a pointer of `Derived` type. Then the first call goes to `Base::foo()`, and the recursive calls go to `Derived::foo()`. Is this correct? And is this the only reason (but a very good reason!) why `virtual` is difficult? – Aaron McDaid Aug 03 '15 at 18:37
  • It doesn't apply in the `fib()` case as you're adding the results of the recursive calls together. (However, there are other ways to write that specific function which _can_ be tail-recursive; a two argument scheme is sufficient.) – Donal Fellows Aug 25 '20 at 11:00