05. How Computers Work
The ultimate goal of this book is to compile our language into machine code that runs natively on the CPU. To do that, we need to have some understanding of how computers work. So let’s take a high-level look at what a computer can do, without going into detail.
This chapter is an outline of what you need to know before starting the compiler project. Details will be introduced later.
5.1 Registers, Memory, and Instructions
The CPU takes a list of “instructions” to execute sequentially, which is stored in memory. There are instructions for arithmetic operations, such as adding or multiplying numbers. And there are also instructions for control flows that break sequential execution (branching), such as jumping to another instruction, calling functions, and returning from calls.
A CPU contains a fixed number of internal storage units called “registers”. A register stores a certain number of binary bits, often representing an integer, a pointer, or something else (everything is some binary bits). Computations are performed on registers, not directly in memory.
Let’s say you want to add up two numbers, the numbers must be loaded from memory into registers, then the CPU can perform the addition. The result of the addition is also stored in a register, which can be transferred back into memory later.
In summary, CPU instructions can be categorized as follows:
- Arithmetic: Computing on registers.
- Memory: Load or store between memory and registers.
- Branching: Moving the execution around.
Note that CPU instructions do not always fall into a single category. In x86 (and x64), arithmetic instructions can also load or store memory. For example, in addition to adding up registers, x86 also allows adding a register to a memory location and vice versa (but not adding up 2 memory locations).
5.2 Function Calls and Stacks
There are usually 2 types of branch instructions:
- Jump to another instruction based on a condition, this is used for control flows such as if-then-else and loops.
- Function calls and returns.
Instructions for function calls are not essential. A compiler can use only the first type of branching to implement (emulate) calls and returns. However, there are some conventions for function calls.
When returning from a function call, how does the program know where
to go back? A common convention is that before jumping to the target
function, the caller pushes its position (the return address) into a
stack; thus, the callee knows where to return back by looking at the
stack. In x86, there are dedicated instructions that follow this
convention: the call instruction pushes the current program
position into the stack and jumps to the target function, and the
ret instruction does the reverse.
This is often referred to as the “calling convention”. There are other parts of the calling convention, such as how the stack is defined and how arguments are passed, which we’ll learn about later.
The stack also stores local variables in addition to the return address. You can see how local variables are “local” — they are removed from the stack when returning from a call.
5.3 System Calls
A program must interact with the operating system for input and output. The mechanism looks just like a normal function call: you call into an operating system routine, and the calling thread suspends until the call returns.
Programming in a high-level programming language such as C or Python rarely invokes system calls directly. The programmer relies on the language runtime or standard library to handle system calls under the hood.
However, since we are building a compiler from scratch, without an existing runtime, we’ll work on system calls directly later. A program that does not depend on a runtime or libraries is called a “freestanding” program.