How CPUs Run Functions

This video was sponsored by Brilliant. Every program is constantly stopping what it's doing, going somewhere else to perform a small task, and then continuing exactly where it left off. In this video, we're going to explore the mechanisms that makes it possible for CPUs to execute functions. It sounds simple, but for a machine that only executes instructions in order, it's actually a surprisingly tricky problem. Hi friends, my name is George, and this is Core Dumped. There's nothing inherently special about running code that calls other code, at least not from the hardware's perspective. On the software side, however, things are different. The compiler is responsible for generating valid machine code that makes all this possible, including the logic the CPU needs to follow to execute functions. As I've mentioned many times before, the compiler is the one that emits the actual machine instructions the processor will execute. It takes all those lines of code you write and translates them into something the computer's circuitry can understand, a precise sequence of instructions. For educational purposes, we're going to explain everything using assembly, because raw machine code is mostly unreadable for humans, and assembly is simply a textual representation of the ones and zeros that end up in the executable file. There are two basic ways a compiler can implement function calls, function inlining and function outlining. The simpler one, function inlining, works by copying the function body, resolving variables for each call, and pasting that code directly into the caller every time the function is invoked. From a high-level perspective, it's as if the compiler produced code that was never modularized using functions at all, but instead written as one long sequence of instructions in a single scope. Because all the instructions end up laid out sequentially, the CPU can execute the program by simply running one instruction after another. Believe it or not, even when we try to modularize our code, compilers attempt to use function inlining as much as possible. To understand why, however, we need to look at the second approach, function outlining. With function outlining, the compiler generates the code for a function only once, places it in memory in a different region than the calling code, and when the function is called, the CPU goes to that code. Once the function finishes, execution goes back to the original location in the caller. Of course, this doesn't magically happen. The compiler must emit additional instructions telling the CPU not to continue with the next instruction, but instead go to the function's code, and somehow return to the place where the function was called. Many people believe that calling functions this way requires two special instructions, call and ret. But that's not entirely true. These instructions are really just shortcuts that automate a process we can build ourselves with regular instructions. So, in the next part of this video, we're going to figure out how to do that without dedicated instructions. If you think about it, all we really need are jump instructions. For those who don't know, a jump instruction tells the CPU not to execute the instruction that comes next in memory, but instead to continue execution at a different, specified address. Most of the time, the CPU executes the instruction immediately following the previous one in memory, but sometimes we need to explicitly tell it to run code located somewhere else. In assembly, the memory addresses of instructions are usually written as labels, which are later resolved into actual memory addresses in the final executable, so the CPU knows exactly where to jump. Jump instructions have nothing inherently to do with functions. They exist because, at a fundamental level, they're essential for controlling program flow, allowing the CPU to implement loops and conditional logic, as we explored in a previous episode. Now to make things easier to understand, we'll start with functions that don't receive parameters and don't return values. Remember, function outlining requires the CPU to jump to the executable code of the function when the main program calls it. So the simplest possible approach is this. When a program needs to call an outlined function, it uses an unconditional jump instruction to transfer execution to the address where that function begins. That's all the CPU needs to start running a different section of code. The next question is, once the function finishes executing, how does the CPU know where to return? Some of you might think, just define another label for the return point, and add a jump instruction at the end of the function that jumps back to the instruction right after the function call. If we resolve the addresses and load this program into memory, it looks like this solution works. The main function jumps to the code of the DoSomething function, and once that function finishes, it jumps back to the main function. But this doesn't actually work in the general case, because a function can be called from multiple places in the program. If we hardcode a single return address, the function will always return to the same location. That means it can be called from anywhere, but it can only return to one place. To fix this, we can make the return address dynamic. One idea is to define a variable called returnAddress. When the main program wants to call a function, it first writes the address it should return to into this variable, and then jumps to the function. Inside the function, instead of jumping back to a hardcoded address, it reads the return address from memory, and jumps to that location. This way, the function always returns to the correct place. Here's an intuitive animation of how this program flows. Intuitive. Like every single lesson on Brilliant. If you're the kind of person who enjoys peeling back the layers of how computers actually work, Brilliant is hands-down one of the best ways to push your learning deeper. Their courses are designed by world-class teachers from MIT, Harvard, and Stanford, and they cover everything from math and data science to computer science and AI. What I love about Brilliant is that it's entirely interactive. Instead of watching explanations, you're constantly predicting outcomes, testing assumptions, and correcting yourself in real time. That feedback loop is what turns concepts into instincts. To learn for free on Brilliant for a full 30 days, go to brilliant.org slash core dumped, scan the QR code on screen, or click on the link in the description. Brilliant's also given our viewers 20% off an annual premium subscription, which gives you unlimited daily access to everything on Brilliant. And now, back to the video. If we make the return address dynamic, here's what happens. The program starts executing in the main function. When it reaches the first function call, it stores the return address and jumps to the function. The function then starts executing. When it reaches the end, it fetches the address it needs to return to. Once that address is obtained, it simply jumps to it. Execution continues in main until a second function call is needed. Once again, before jumping to the function code, the program updates the return address. When the function finishes executing, it fetches the return address and uses it in a jump instruction, returning to the correct place. It makes sense, right? But once again, this approach is not perfect. Think about what happens when the main program calls a function, and that function then calls another function. The main code writes its return address into the variable and jumps to the first function. Then, when that function calls a second function, it overwrites the same variable with a new return address before jumping again. As a result, the inner function can return correctly. But the return address for the outer function is lost. Instead of returning to the main program, it jumps to the wrong place, making the program incorrect. In this scenario, the program can even get stuck executing the same instructions forever. Creating a separate variable to store the return address for each function call might sound like a solution. But good programmers know that dynamic problems require dynamic solutions. We need something more flexible. We need a data structure. And by the very nature of this problem, that data structure is a stack. The structure that stores elements on top of each other and always removes the most recently added one first. Here's the core idea. Every time a function is called, before jumping to the function's code, the program pushes the return address onto the stack. When a function finishes, it simply pops the top value from the stack and uses it as a return address. The next question is how to implement a stack in assembly. Well, it is actually not that difficult. First we choose a region of memory where the stack will live. For simplicity, let's say our stack starts at memory address 9999, and it grows downward in memory, toward lower addresses. To push and pop elements, we need to keep track of where the top of the stack is. For that, we introduce another variable called the stack pointer. This variable holds the address of the topmost element in the stack. To push an element onto the stack, we read the stack pointer, decrement it to point to the next free location, store the new value there, and then update the stack pointer so it points to this new topmost element. To pop an element, we fetch the stack pointer and then fetch the content in the memory location that value points to. After that, we increment the stack pointer and update its value in memory, so it once again points to the element below. Usually data structure operations like this are implemented as reusable routines stored somewhere else in memory, and you jump to them when needed. But we can't do that here, because jumping to helper routines is exactly the mechanism we're trying to build in the first place. So at this stage, we have no choice but to inline the stack logic itself, inject the code that pushes the return address onto the stack at every function call, and inject the code that pops an address from the stack at every function return. Here's an animation of how this approach works. A program starts executing. When it reaches a point where it needs to jump into a function, it first pushes the return address for that specific call onto the stack, and only then jumps to the function. If that function calls another function, it does the same thing again. Push the return address for that call onto the stack, then jump to the inner function. When the inner function finishes, it pops the most recently pushed address from the stack and uses it in a jump instruction, returning to the exact place where it was called. Then the outer function continues executing. And when it eventually needs to return to the main function, because the stack is back to the exact state it had before the inner call, the outer function's return address is once again the topmost element. So the CPU simply pops the stack and jumps to the address it retrieves. That's how functions can reliably return to the correct locations, without overwriting return addresses from earlier, outer calls. And that's how function outlining can be achieved without dedicated CPU instructions, using only jumps and a stack. Notice that this entire stack mechanism is completely hidden from our high-level code. There's no mention of a stack anywhere in the source program. Behind the scenes, the compiler must inject all of this extra logic just to make function outlining possible. This is where we can start noticing one of the benefits of function inlining. Since no extra instructions need to be injected at each call site, an execution never needs to jump to another location in the program. Fewer instructions are executed overall, which can improve performance. The stack, however, is fundamental to program execution, at least in the way we commonly write programs. As a quick spoiler, function inlining is not always ideal, neither possible. So CPUs, even back in the 1970s, included hardware specifically designed to manage the stack more efficiently. Instead of storing the address of the topmost stack element in a normal memory variable, CPUs provide a dedicated register called the stack pointer. The stack itself still lives in memory, but since the pointer is kept inside the processor, accessing it is extremely fast because two memory operations are avoided. Having the stack pointer in a special register also allows the CPU to provide dedicated instructions to manipulate the stack, push and pop. Push stores a value on the stack and updates the stack pointer in a single instruction. Pop retrieves a value from the stack and updates the stack pointer in a single instruction. So all the boilerplate code we wrote earlier can now be simplified into something like this. For those who have been wondering about the call and ret instructions since the beginning of this video, this is where I finally introduce them. These instructions are really just shortcuts built on top of stack operations. Call tells the CPU to push the return address onto the stack and then jump to the function. Ret tells the CPU to pop the stack and jump to the retrieved address. So the entire process of jumping to a function and returning to the caller can ultimately be simplified to something like this. If you ask me, that's definitely more readable than manually handling the stack. This not only makes programs easier to read, but also more efficient, since the CPU needs to fetch and execute fewer instructions to achieve the same result. Regarding function parameters and return values, the compiler also needs to inject additional code to handle these cases. When a function is called, before jumping to its code, additional instructions are needed to place the arguments somewhere the callee can access them. There are two fundamental ways to do this. One approach is to pass arguments through general purpose registers. When this method is used, the function is written to read its parameters directly from specific registers. Once the function starts running, it can directly use the values in the CPU registers. Returning a value can also be done through registers. Before jumping back, the callee simply leaves the result in a designated register, and the caller reads it from there. Another way to pass arguments and return values is through memory. Before jumping to the function, the caller writes the arguments into specific memory locations, and the callee loads them from there when it needs to access its parameters. The return value can also be written to memory for the caller to retrieve. This second approach is often more flexible, because sometimes arguments are complex data that won't fit in registers, or because a function may require more arguments than the number of available general purpose registers on a system. This is part of the platform's calling convention, which is defined by the ABI. Once again, these additional instructions used for argument passing can affect performance compared to function inlining. Even when no parameters or return value are involved, the extra instructions required to jump to a function and return from it can have a measurable performance overhead. Now based on everything we've discussed so far, it might sound like function inlining is always the best choice. But that's not actually true. Imagine we have a very large function. If that function is called hundreds of times throughout the program, inlining it everywhere could make the executable grow dramatically in size. In that case, function outlining is the better option, because the function's code is emitted only once, and the program jumps to it whenever needed, resulting in a smaller binary. On the other hand, if the function is short and called frequently, outlining may not be ideal. The extra instructions required to handle the call and return could end up adding more code than they save, producing the opposite of the intended effect. This is why I like this topic. The decision is situational. You can't simply assume one method is always better than the other. And in some situations, it ultimately depends on the purpose of each function. Cache, for example, plays a huge role in this decision on modern systems. Suppose we have a function that is only called in one place, inside a loop. If that function is outlined, there's a good chance its code won't already be in the CPU cache. When the program reaches it, a cache miss may occur, forcing the CPU to wait while the instruction cache is filled. When the function returns, the same thing may happen again. In that situation, inlining could help, because the function's code would likely reside in the cache alongside the caller, reducing the likelihood of cache misses and improving performance. What I find very interesting about this example is that, even though both versions are technically the same program, the cache changes everything. But that doesn't mean functions should always be inlined for cache reasons. Consider a function that handles rare errors. Statistically, it almost never runs. If that code is moved elsewhere through outlining, the frequently executed code has a better chance of fitting entirely in cache, which can improve overall performance. Cache behavior is a topic that deserves its own video, so we won't go deeper into it here. What I can tell you is that if you really want control over whether a function is inlined or outlined, systems programming languages often provide a way to influence the compiler. In C, for example, you can use the inline keyword in the definition of a function. Or in Rust, you can use the inline attribute to suggest that the compiler inline a function, regardless of the heuristics it would normally use. And finally, there's one more scenario where function inlining simply isn't viable – recursion. If a function calls itself, and at compile time we don't know how many levels of recursion will occur, it's impossible to inline it. In those situations, function outlining is essential. The interesting part is that, to make recursion work, the compiler must not only ensure functions jump and return correctly as we learned in this video, but also generate code so that each recursive call doesn't overwrite the variables from previous call levels. In the example shown here, the program won't behave as expected because the memory location used to pass variables is hard-coded. Every time the function makes a recursive call, it overwrites its own parameter while trying to pass the argument to the next call. It turns out the solution to this problem also lies in the runtime stack. And that's what we'll cover in the next episode. I'm gonna go ahead and wrap things up for now. Don't forget to subscribe if you want to learn more. If you want to support the channel, please check out the sponsors in the description below. And if you enjoyed this video, or learned something new, please hit the like button. It's free, and it helps me out a lot. See you in the next one.