32

On GCC manual,

-foptimize-sibling-calls

Optimize sibling and tail recursive calls.

I know tail recursive calls, for example

int sum(int n) { return n == 1 ? 1 : n + sum(n-1); }

However, what does sibling calls mean?

3
  • 1
    First Google hit apparently has some info Feb 26, 2014 at 9:41
  • 3
    In practice, GCC synonym for "tail" (they refer to it as a.k.a. tail in the internals documentation). Formally, some function which has a return type of the same size and a parameter list of the same total word size. Thus, e.g. int foo(char, char) and int bar(short) would be siblings and could be tail-optimized (so foo calling bar which calls foo would in principle work).
    – Damon
    Feb 28, 2014 at 15:25
  • 1
    @AngewisnolongerproudofSO this question is the first Google hit for "sibling calls function meaning" so it should have some info too. Mar 4, 2021 at 7:25

3 Answers 3

19

Tail Calls

If a function call is a last action performed in another function, it is said to be a tail call.

The name stems from the fact that the function call appears at the tail position of other function.

int foo(int a, int b) {
    // some code ...
    return bar(b);    // Tail call which is neither sibling call nor tail recursive call.
}

bar appears at the tail position of foo. Call to bar is a tail call.


Tail Recursive Calls

Tail recursive call is a special case of tail call where callee function is same as caller function.

int foo(int a, int b) {
    if (a > 0) {
        return foo(a - 1, b + 1);    // Tail recursive call
    } else {
        return b;
    }
}

Sibling Calls

Sibling call is another special case of tail call where caller function and callee function do not need to be same, but they have compatible stack footprint.

That means the return types of both functions must be same, and the arguments being passed must take same stack space.

int foo(int a, int b) {
    // some code ...
    return bar(a - 1, b);    // Sibling call, also a tail call, but not a tail recursive call.
}

Every tail recursive call is a sibling call, Since the definition implies every function is a sibling of itself.


Why Distinction?

Because of identical stack footprint, replacing stack frame becomes relatively easier. Compiler writers don't have to resize stack frame, and in place mutation becomes straightforward.

8

the compiler considers two functions as being siblings if they share the same structural equivalence of return types, as well as matching space requirements of their arguments.

http://www.drdobbs.com/tackling-c-tail-calls/184401756

7

It must be something like this:

int ispair(int n) { return n == 0 ? 1 : isodd(n-1); }
int isodd(int n) { return n == 0 ? 0 : ispair(n-1); }

In general, if the function call is the last sentence, then it can be replaced by a jump.

void x() { ......; y(); }

In this case y() can be replaced by a jump (or an inline function) instead of using a standard function call.

1
  • 3
    How is that different from tail-call optimization?
    – Pr0methean
    Jun 6, 2016 at 15:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.