11

I'm trying to write a program in functional style with C as much as possible. I know fine compilers like GCC/Clang do tail call optimization silently, but it's not guaranteed. Is there any option to force tail call optimization on the compilers? (Of course when only it's called at the end of itself)

eonil
  • 83,476
  • 81
  • 317
  • 516
  • 4
    The compiler is probably rather smart in this regard, just trust it. No need for *not-portable* hacks. – eq- Jan 24 '11 at 17:38
  • 1
    What do you want to happen in instances where you think tail optimization should occur but the compiler isn't capable of doing it (for whatever reason)? – Michael Burr Jan 24 '11 at 18:40
  • 6
    @Michael I expected an compile time error if forced tail call optimization is impossible to be done. – eonil Jan 25 '11 at 06:06
  • 3
    You can force GCC to provide TCO with a compiler flag: -foptimize-sibling-calls (see http://draketo.de/light/english/free-software/tco-debug ) – Arne Babenhauserheide Jul 22 '14 at 11:49

7 Answers7

14

Clang 13 "musttail" attribute to force tail call optimization in tail recursive functions even if optimizations are disabled.

https://clang.llvm.org/docs/AttributeReference.html#musttail

usage:

int f(int x) {
  ...
  __attribute__((musttail)) return f(x-1);
}
Bobisnotyouruncle
  • 199
  • 1
  • 9
6

Clang is not doing any optimisations at all. There is an LLVM pass tailcallelim which may do what you want (but it is not guaranteed). You can run it separately with opt.

SK-logic
  • 9,605
  • 1
  • 23
  • 35
2

A meta answer:

There are some lessons it's useful to take over into C from functional languages: use small functions, use functions which don't mutate either globals or input arguments, don't be frightened of function pointers. But there's a limit to what you can reasonably do here, and relying on tail-call elimination ('tail-call optimization' isn't really the right term) is probably beyond what's useful. You can't force the compiler to use this strategy, and even if you could, the resulting C would be extremely unidiomatic, and hard to read for others, including your future self.

Use languages to their strengths. C is good for some things, so use it for those, in good C style. If you want different strengths, or if you want to use a functional style (excellent decision!), use a functional language.

Norman Gray
  • 11,978
  • 2
  • 33
  • 56
  • I faced an interesting problem recently. A common idiom for spawning processes in C is fork()ing close to main() and delegating process spawning to the forked process (this will solve some problems on multi-threaded applications that can't rely on `/proc/self/exe`). So there's an `int child_main()` for the forked process. However, if you allow this technique recursively, `__attribute__((musttail)) return child_main()` will help a lot. – vinipsmaker May 17 '22 at 14:10
2

I don't think it really enforces it, but you can use -foptimize-sibling-calls when using gcc. It's automatically enabled if you use -O2, -O3 or -Os.

In general, I'd advice against overusing recursion in C. If you really want to do fp, pick a functional language. There are cases where it is suitable, like quicksort, buf if you make a habit out of using recursion instead of loops, chances are pretty high that you will blow the stack.

klutt
  • 30,332
  • 17
  • 55
  • 95
1

A GCC extension for Alpha and i386 is described in:

Proper Tail Recursion in C (Diploma Thesis) by Mark Probst, 2001.

false
  • 10,264
  • 13
  • 101
  • 209
0

In reality a lot of compilers for C already handle this for you. As eq mentioned you might as well let the compiler handle most of these things rather than trying to create optimizations that won't work elsewhere. Often times you'll find even if you set optimization flags that there is really no performance difference.

Jesus Ramos
  • 22,940
  • 10
  • 58
  • 88
  • A common time when you want to force tail-call optimization is threaded code. In that situation, a function will sometimes return, but usually call some other function with an identical signature (same params, same return value). A standard function call sequence will run the program out of stack space and crash almost immediately, so this isn't something we can leave up to the compiler. – jorgbrown Sep 23 '20 at 17:41
-1

If it really is a tail call then a while loop or a goto wont look that much different from a recursive call. Just update all variables instead of passing them as parameters. AFAIK this is the only cross-platform way in C to control stack usage at all optimization levels. It can actually be more readable too since you have one function with initialization followed by the loop, which is pretty idiomatic. The tail recursive version requires two functions, one for initialization and one for the recursive part.

Samuel Danielson
  • 5,231
  • 3
  • 35
  • 37
  • This is only true in trivial cases where TCO follows a single path to an end. Recursive functions which branch down a lot of different recursive paths are much cleaner when represented with recursion. – kerkeslager Sep 12 '19 at 14:29