sibling call是什麼？

01-05

sibling call與tail call相似，都要求函數調用在過程的末尾，並且sibling call對參數有特殊要求：主調函數與被調函數參數相似。那麼，sibling call與tail call的區別在於？

Definition (Proper Tail Call). A tail call from function f to function b is
a proper tail call iff the memory held by the stack frame of f can be released
before jumping to function b.

Definition (Tail Recursive). A proper tail call is properly tail recursive iff f
and b are not two distinct functions.

Definition (Sibling Call). Let f and b be two not necessarily distinct func-
tions. A call from function f to function b is a sibling call iff

it qualifies as proper tail call,

the number of arguments to b (or the space occupied by them) do not exceed the number of arguments to f (or the space occupied by them),

the return types of function f and function b match.

Obviously, this definition covers proper tail recursion as well, because if in a
call, f and b are really the same function, then the number of arguments and the
return type are guaranteed to be always the same. In all other cases, however,

the definition means that the caller』s and the callee』s function signature have
to be at least somewhat similar in order to be regarded as 「siblings」.

來自以前下的PDF，http://home.in.tum.de/~baueran/thesis/baueran_thesis.pdf

MUNICH UNIVERSITY OF TECHNOLOGY Department of Informatics

A Thesis submitted for the Degree of Diplom Informatik

Compilation of Functional Programming Languages using GCC—Tail Calls

Andreas Bauer

Date: January 15, 2003

貌似原始鏈接已經失效- -。

Silbling Call的做法：

The caller stores the callee』s arguments in the area for its own incoming arguments. (By definition, this is not part of the epilogue, but without this step the following instructions would not make sense.)

The caller has to pop callee saved registers, should it be required.

If not given the option -fomit-frame-pointer, the caller restores the frame and base pointer, by reloading both with their prior values. (On Intel ix86 architectures this can be achieved by issuing only a single instruction: leave [Brey 1995, ?6-4].)

Instead of finishing with a generic function call, the callee is invoked via the architecture』s low level jump command to reuse the existing stack frame along with the stack slots reserved for incoming arguments.

PDF里還有示例圖片：

最後作者說：

Saving one stack frame may not seem like much of an improvement, but if
this example is stretched out to mutual tail recursion, for instance, then the
gain can make a remarkable difference. In fact, if the depth of recursion is
sufficiently high, such a (sibling) call mechanism would be GCC』s only solution
to prevent a system』s run time stack from overflowing.

不過這是2003年的情況了。。。

"Sibling call"應該不是一個特別通用的術語。我的理解是它是GCC造出來的一種歸類方式。

GCC所說的sibling call指的是一種特殊的tail call：caller和callee的signature要結構一致才算。

傳送門：Tackling C++ Tail Calls，"Tail Call Optimization in GCC"那段。摘取其中一部分：

To address optimization needs, GCC has introduced the concept called "sibcalls" (short for "sibling calls"). Basically, a sibcall is an optimized tail call, but restricted to functions that share a similar signature. In other words, 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.

而ICC所說的sibling call似乎只關注tail recursive的情況。文檔上看不出來到底它的限制是什麼。

https://software.intel.com/en-us/node/522809

Description
This option determines whether the compiler optimizes tail recursive calls. It enables conversion of tail recursion into loops.
If you do not want to optimize tail recursive calls, specify -fno-optimize-sibling-calls.
Tail recursion is a special form of recursion that doesn"t use stack space. In tail recursion, a recursive call is converted to a GOTO statement that returns to the beginning of the function. In this case, the return value of the recursive call is only used to be returned. It is not used in another expression. The recursive function is converted into a loop, which prevents modification of the stack space used.