How do function inlining and Tail Call Optimization affect call stack?

Question

I've just accidentally came across this answer about inlined functions and I'd like to know how this affects call stack. But I can't add comments because I don't have enough rep so I decided to ask this question. Also recently I discovered Tail Call Optimization (TCO) and now I want to learn more about this topic. And since TCO is also related to call stack, I actually have 2 question.

1. AFAIK every function call adds a new stack frame into a call stack. But what about functions inlined by a compiler? As this IBM article says:

An inline function is one for which the compiler copies the code from the function definition directly into the code of the calling function

It makes me think that in this case we don't really use a function at all. We use it's inner code but an actual function call doesn't happen. So does it mean that a new stack frame isn't created for such function? Hence "every function call creates a new stack frame" is a false claim?

2. TCO allows a runtime to use the same stack frame for multiple recursive function calls. New stack frames are not added into a call stack. Instead the runtime just swap data inside the same stack frame - data that was necessary for the previous recursive call is replaced with data that is necessary for the next recursive call. Does it mean that in this case we can intentionally create an infinite recursion and we won't have a stack overflow since we always have a fixed amount of stack frames in a call stack?

Those 2 question are not language specific. And since different languages have different compilers, and every language can have multiple compilers that work differently, I'd like to get answers about any language and any compiler you used and know about.

Answer 1

AFAIK every function call adds a new stack frame into a call stack.

This is true for some functions, but not for all functions.  On some processors, simple functions, called leaf functions (functions that may do work but simply do not call other functions), usually operate without a stack frame.  On x86, the "stack frame" (if you can even call it one) for a leaf function may be as small as one word, for holding the return address; whereas on RISC machines, may be a small as zero words.

---

Inlining is a feature of some translators, when the compiler can see the internal implementation of a called function (the callee) at the point(s) where it is translating the caller.

Inlining is usually performed at a fairly high level in the translater, such as at the AST.  The optimization substitutes the function invocation in the caller with a copy of the callee's function body.  In use, the caller behaves the same as if it had actually called the callee, as with most languages there's no mechanism within the language that allows us to observe whether inlining was done or not.

Inlining enables numerous other options as the callee's body is placed within the context of the caller's code — loop optimizations, common sub expressions, constant propagation, direct use of variables provided by the caller instead of formal parameters in the callee, etc..

Since with inlining there is no actual low-level function invocation, the call stack is not (necessarily) enlarged by the execution of the copy of the callee's function body.  However, the caller's call frame my be enlarged to accommodate the new code and its variables.

Inlining has limitations, and if there's recursion, inlining has to be artificially limited to some number of levels.  Since inlining makes copies of the callee's function body, the generated code may get larger (but it may also get smaller).

---

TCO allows a runtime to use the same stack frame for multiple recursive function calls.

Tail Call Optimization applies to any function invocation that is the last operation of a function before returning to its caller.  It is very helpful in recursive code, but no recursion is required.  It applies when the last thing a function does, dynamically, is a function call, meaning that multiple return points allow for multiple TCO opportunities within the same function.

Because a tail call is specifically the last operation of an invoked function, it is the last thing it does before it returns to its caller, the caller no longer needs their own stack frame — the caller has nothing left to do (i.e. no computation or changing of state) to return to its caller — except actually return.  Thus, the TCO sets up the stack frame such that the callee returns, not to the caller, but rather directly to the caller's caller.  This removes the need for the intermediate (the caller's) stack frame, and in properly written recursive code (i.e. written for TCO) many levels of stack frames might be elided with TCO, and in addition, the caller's stack frame itself may be simpler (more like a leaf function's).

Does it mean that in this case we can intentionally create an infinite recursion and we won't have a stack overflow since we always have a fixed amount of stack frames in a call stack?

Yes, TCO can eliminate stack overflow that might have occurred without it.