x86 Assembly

What Do the Register Names Mean?

The registers have their current names largely because of history. Intel's first 8-bit processor was the 8008, and it had seven physical 8-bit registers. The eighth "register" was a logical register (also called pseudo-register), created by encoding the registers within the instructions as three bits (${2^{3} = 8}$).

The A stood for accumulator, and it stored implicit operands and return values for arithmetic and logical operations. The pseudo-register was called the M register, for memory. The M register worked by pointing to the memory location resulting from combining the registers H (high-order byte) and L (low-order byte). In the 70s, this was the only way to construct addresses. The remaining registers, B, C, D, and E, were generic registers, so their names were completely arbitrary.

When the 8086 came along in 1986, the same names were used for backwards compatibility. The difference, however, was that the registers were now 16-bits wide:

The letter X was intended to represent a variable, signifying that it could be replaced with H or L to access the lower and higher order bytes, as was done in the 8008. Because there were now far more ways to construct address (more available memory, more possible methods to address), Intel made the design choice of restricting how some of the registers could be used. This in turn meant that the previously generic registers now had to have meaning: BX was the base register, CX was the count register, and DX was the data register (AX remained the accumulator).

The new registers were also given meaning: BP was the base pointer, SP was the stack pointer, SI was the source index, and DI was the destination index.

Fast forward to the x86, and the registers got bigger. Now they were 32-bits wide. Once again, for backwards compatibility, the first 16-bits could be accessed by using the 8080 register names — AX, AL, BX, CX, etc. Likewise, the two lower bytes could be referred to with AH, AL, BH, BL, and so on.

To refer to all 32-bits in the register, Intel appended the letter E (extended) to the names, yielding the register names like EAX and EBX.

Fast forward to the x86-64, and we see that the letter E was replaced with the letter R. Importantly, this change wasn't done by Intel, but by AMD, Intel's primary competitor in the early 2000s (Intel's main competitor today is ARM, which currently dominates the processor market for mobile phones, tablets, and embedded devices). AMD made the decision to cut backwards compatibility at 8086, so the smallest lower-order reference we can make is AX, AL, etc. Moreover, AMD decided to name the new registers by replacing E with R for register.

The x86-64 register names today do not necessarily map to their registers' purpose. The function argument register names can be traced back to destination index, source index, data register, count register, and so on, but they aren't necessarily used the way they were used when the 8080 first appeared. In sum, the register names don't originate in their purposes today, but history.

Simple Addressing Modes

The simplest addressing modes are:

1. Normal addressing, and
2. Displacement addressing

movq (%rcx), %rax

// suppose i, j, and k are hexadecimals
int a = 5; // address 0xi in memory holds the value 5
int *p = &a; // address 0xj in memory holds the address 0xi
int c = *p + 1; // address 0xk in memory holds (value at 0xi) + 1

movq 5(%rbp), %rdx

int arr[5] = {1,2,3,4,5};

arr[2]

0x8(%rdx)        // => 0xf000 + 0x8 = 0xf008
(%rdx, %rcx)     // => 0xf000 + 0x100 = 0xf100
(%rdx, %rcx, 4)  // => 0xf000 + (4 * 0x100) = 0xf400
0x80(,%rdx,2)    // => 0x0000 + (2 * 0xf000) + 0x80 = 0x1e080

Comparison Operators

The comparison operators in high-level code are ultimately executed by the processor using the condition code registers. To understand how, recall this basic property in real analysis:

property. Let ${a,b,S \in \reals.}$ The following properties hold:

1. ${s = 0 \iff (a-b) = 0 \iff a = b \iff b = a}$
2. ${s > 0 \iff (a-b) > 0 \iff a > b \iff b < a}$
3. ${s < 0 \iff (a-b) < 0 \iff a < b \iff b > a}$

In Assembly, the comparison operators take the form:

where ${a,b \in \uint.}$ When we execute the command above, we are actually computing:

without specifying a destination. And since we're computing ${a - b,}$ we can map the mathematical properties to the condition codes:

1. If the ZF register is set, then a = b.
2. else if the SF register is set, then a < b.
3. else a > b.

Unlike real numbers, however, there's always the possibility of an overflow. Accordingly, there are a few more applicable rules for comparisons on a computer:

1. For signed comparisons, if the OF register is set, then the result of the comparison is possibly incorrect.
2. For unsigned comparisons, if the CF register is set, then the result of the comparison is possible incorrect.

Test Instructions

One unusual instruction related to branching should be mentioned — the test instruction. This instruction takes the form:

This instruction is equivalent to computing src1 & src2 without setting a destination. This is useful because it sets the condition codes based on the result of computing src1 & src2.

• If src1 & src2 = 0, then the ZF register is set.
• If src1 & src2 < 0, then the SF register is set.

Effectively, the test instructions can be used to determine if the value in some register is 0 or negative. This leads to instructions that look like:

testq %rax, %rax

It looks unusual, but its a perfectly valid — even useful — instruction, since checking for negativity and zeroness is a common enough operation. Intel opted to introduce the instruction because it followed all of the other instruction formats — the instruction took two operands. In turn, costs are saved from having to introduce new unary instructions that only took one operand.

Set Instructions

The set𝑥 instructions take the following form:

In short, the instruction works as follows:

1. If the condition is true, set the low-order byte of the destination to 1.
2. If the condition is false, set the low-order byte of the destination to 0.

where the condition is the current value of a particular condition code register. The set instructions are as follows:

The set instructions are the storage part for the comparison instructions. Remember, when we write the instruction compq 𝑎,𝑏, all we're doing is computing 𝑎 - 𝑏. We still have to determine whether that result is is greater than, equal to, or less than 0. The way to do so is not by comparing the actual result of the computation, but by comparing the effects that computation had on the condition code registers.

For example, if we wanted to check if a == b (equality), the computation a - b would return 0. This sets the ZF conditition code to 1, which then sets the lower order byte in the destination register to 1. This means that the condition is true.

For example, consider the code:

int gt (long x, long y) {
   return x > y;
}

This code translates to the following:

cmpq %rsi, %rdi  # compare x:y
setq %al         # set register `%al` to 1 if the condition is true, 0 otherwise
movzbl %l, %eax  # zero the rest of %rax
ret              # return

Notice the instruction movzbl %l, %eax. This instruction will zero the rest of the contents in the register %rax. The step is necessary because the set instructions only change the lower-order byte of the register's contents. This means that anything above that byte (the other 7 bytes) will comprise a garbage value.

Do-while Loops

Consider the following program that uses a do-while loop:

int number_of_1_bits(unsigned int x) {
	int result = 0;
	do {
		result += x & 0x1;
		x >>= 1;
	} while (x);
	return result;
}

int main() {
	int n = 5;
	int r = number_of_1_bits(5);
	printf("There are %d one bits in %d\n", r, n);
	return 0;
}

There are 2 one bits in 5

The function number_of_1_bits() returns the number 1 bits in its integer argument. We could also have written the program in goto style:

int number_of_1_bits(unsigned int x) {
	int result = 0;
	Loop:
		result += x & 0x1;
		x >>= 1;
		if (x) goto Loop;
		return result;
}

Examining the goto version, we have the following in Assembly:

mov1     $0,     %eax  # result = 0;
.L2:                   # Loop:
   movq   %rdi,  %rdx
   andl   $1,    %edx  # t = x & 0x1
   addq   %rdx,  %rax  # result += t
   shrq   %rdi         # x >>= 1
   jne    .L2          # if (x) goto Loop
   rep; ret

Generally, the do-while loop in Assembly takes the form (C form to the right and Assembly to the left):

Like the conditional instructions, looping is a matter of jumping to labels depending on the loop's test condition. Note that the rep instruction, for our purposes, is just a dummy instruction. Compilers produce this instruction for largely historical reasons that aren't very relevant today.

While-loops

For the while-loop, the Assembly form is similar, but with just a few more labels:

For-loops

The for-loop is really just syntactic sugar for a common sequence of instructions. In C, the general form of a for-loop is:

Thus, all we're really doing is:

1. Initialize the index counter.
2. Perform the test.
3. Update the index counter.
4. Evaluate the body.
5. Return to step 2.

In Assembly form:

Importantly, notice the ${!(test).}$ Modern compilers are smart enough to recognize that this initial test will likely be false, so it immediately enters the loop.

Switch Statements

In C, switch statments take the form:

In Assembly, these statements are executed as follows. First, a jump table is constructed. Each cell in the table contains the memory address of the first instruction in the code block (subsequent instructions are stored contiguously thereafter). These addresses are called targets:

In Assembly: Using the same condition codes we saw earlier, if one of the cases returns true, we execute the instruction:

This instruction encapsulates the instructions:

1. If ${x}$ is ${val_0}$, go to the jump table cell indexed 0.
2. If ${x}$ is ${val_1}$, go to the jump table cell indexed 1.
3. If ${x}$ is ${val_2}$, go to the jump table cell indexed 2.
4. etc.

Notice the use of the * in the instruction. This tells the processor that the instruction is in an address, rather than the actual jump table cell. Now, we know that languages like C default to fall-through behavior, but allow users to employ the break keyword to prevent this default. Accordingly, compilers must address the cases where a mixture of break and fall-through is used. To do so, the actual Assembly program looks something like:

a_switch:
   movq %rdx, %rcx
   cmpq $8 %rdi
   ja .L8
   jmp *.L4(,%rdi,8)

Above, we can see usual move and jump instructions. But what is that $8? This instruction maps to some switch statement with 8 cases. This means that if the compiler encounters any value beyond the greatest possible value or the smallest possible value, it can immediately infer that this is the default case. If it is the default case, jump immediately to the label .L8 — the last cell in the jump table. Otherwise, we jump to the label *.L4. That label might look like the following:

.section .rodata
   .align 8
.L4:
   .quad .L0 # first case
   .quad .L1 # second case
   .quad .L2 # third case
   .quad .L3 # fourth case
   .quad .L4 # fifth case
   .quad .L5 # sixth case
   .quad .L6 # seventh case
   .quad .L7 # eight case
   .quad .L8 # default

To implement fall-through behavior (say case 5 falls through to case 6), the relevant labels under .L4 contain a merge label:

.L5:
   # instructions for case 5
   goto merge
.L6
   merge:
      # instructions for case 6

How do the break statements work? Well, suppose each of the cases contained a break statement. Then, inside any of the labels under .L4, say .L3, we would have something that looks like:

.L3:
   movq %rsi, %rax
   # more statements
   ret

That is, including the break keyword in any one of the cases results in an implicit ret (return) instruction.

At this point, we can likely see the downside to switch statements. Each case requires a pointer, which, in a 64-bit program, takes up 8 bytes. Thus, given ${n}$ cases, the switch statement alone takes up ${8n}$ bytes of memory. This is not to say that switch statements are sub-optimal in terms of memory, but we certainly should not be writing switch statements with hundreds or thousands of cases.

The Stack

On a modern computer, memory can be thought of as a long line of numbered addresses, where each address identifies a particular byte of memory:

To help manage such a large amount of memory, the addresses are organized into certain regions, called memory regions. There are many different regions, but we for now, we're just going to think about the stack:

Within the stack region, the memory looks like:

The %rsp register always contains a pointer to the top of the stack. Notice that the top of stack, visually, is at the bottom. This is because modern machines use the little endian approach to address organization: The smaller addresses hold the most significant bytes, while the larger addresses hold the lease significant bytes.

The use of little endian also means that as the stack gets bigger, it grows "down". This is an import point to keep in mind, as it helps us determine whether we want to add to, subtract from, the stack.

In x86, there are two core instructions associated with the stack: push and pop.

Example: Function Execution in Assembly

Consider the following code:

void multstore(int x, int y, int *destination) {
   int t = mult2(int x, int y);
   *destination = t;
}
int mult2(int a, int b) {
   int s = a * b;
   return s;
}

The two functions multstore and mult2 can be translated as follows:

void multstore(int x, int y, int *destination) {
   int t = mult2(int x, int y);
   *destination = t;
}

0000000004000540 <multstore>:
   400540: push   %rbx
   400541: mov    %rdx,   %rbx
   400544: callq  400550  <mult2>
   400549: mov    %rax,   (%rbx)
   40054c: pop    %rbx
   40054d: retq

int mult2(int a, int b) {
   int s = a * b;
   return s;
}

0000000040000550 <mult2>:
   400550: mov  %rdi, %rax
   400553: imul %rsi, %rax
   400557: retq

Examining the Assembly translations, the first thing we want to focus on is the instruction:

400544: callq  400550  <mult2>

Let's go over each part of the translations carefully, starting with multstore's translation. First, we have the line:

0000000004000540 <multstore>:

The bit vector 0000000004000540 is the address for the block of instructions constituting the function multstore. Specifically, it's the address of the first instruction in the code block. The symbol <multstore> is the symbolic, human-readable label for that block.

Within that code block, there are two key instructions we see, push %rbx and pop %rbx. We'll get back to those instructions later.

The next instruction is mov %rdx, %rbx. This says, "Move the contents of inside register %rdx (a register that stores the third argument for a function) into register %rbx. The %rbx register stores a local variable for the caller (<multstore>). Local variable registers are essentially shields — the values they contain are protected against any changes. In the source code, the third argument is a pointer. Thus, the instruction mov %rdx, %rbx means that we now have a local variable storing some location in memory.

Importantly, at this point, the processor registers and the stack have the following state:

Recall that the %rip register stores the instruction pointer (the program counter), and contains the address of the current instruction. The %rsp register stores the address of the current top of the stack. The address 0x120 (and all the other addresses labeled on the stack) is just an arbitrary address used for demonstration purposes.

The next line is callq 400550 <mult2>. This instruction says, "Go to the address 400550, and continue execution with the instructions under the label <mult2>. This takes us to the address 0x400550, and we get the following effect in memory:

First, notice what was pushed onto the stack when we use a call instruction. In this case, it's 0x400549. This is called the return address. By pushing this instruction onto the stack, we're "bookmarking" where we left off. As we'll see, when <mult2> finishes executing, we'll get back to precisely where we should.

Second, the %rip register now contains 0x400550. This is the first instruction for the code block under the label <mult2>. So, we go to the instruction 0x400550, and execute the instructions thereafter.

Inside that code block, we have the first instruction, stored at the address 400550. This instruction says, "Move the contents of register %rdi into the register %rax.

400550: mov  %rdi, %rax

The register %rdi stores the first argument in the function (in the source code, the argument x), and the register %rax stores the return value. Thus, we are moving the contents inside %rdi into the register %rax (remember that %rax is callee-owned, meaning that the value will persist).

Next, we have the instruction:

400553: imul  %rsi, %rax

This tells us to compute the signed multiplication of the value inside the register %rsi (the register that stores the second argument of the function), with the value inside %rax (which, at this point, stores the first argument of the function, per the earlier mov instruction).

After the imul instruction finishes executing, we get to the next instruction:

retq

At this point, the %rip register is 0x400557. Importantly, however, the %rsp register never changed — it's been storing 0x118 this whole time.

When we get to the retq instruction, we essentially execute goto instruction. We go from wherever we are now, to whatever the return address is. How do we get that return address? Well, it's at the top of the stack, which is pointed to by the %rsp register. So, we go to the address 0x118, and get the value stored in there: 0x400549.

We take this value, 0x400549, and update the %rip register. The %rip register changes from 0x400557 to 0x400549, and the %rsp register now becomes 0x120:

Once that has finished, the %rsp register is incremented (since the return address is no longer needed), and we the stack pointer back to 0x120:

When we get back to 400549, we execute the instruction mov %rax, (%rbx). Recall that the register %rbx stored the third argument for <multstore>, which was some address in memory. When we write (%rbx), we dereference that address, and store the value now in %rax (the return value from <mult2>) inside that address.

This is a good point to recall the registers related to functions:

If a function has more than six arguments, they must be pushed onto the stack:

This leads to a helpful observation when it comes to designing functions:

Lemma. For a 64-bit program, a function with 𝑎 = 6 + 𝑛 arguments, where 𝑎 is the number of arguments, must allocate the 𝑛 arguments on the stack, and is therefore less efficient than a function with 𝑎 ≤ 6 arguments.

More generally:

Lemma. The more arguments a function has, the less efficient it is.

What about the push and pop instructions from earlier? To understand how these instructions impact the big picture, we have to talk about recursion.

Handling Recursion

The simplest recursive function takes the form:

where ${n}$ is the function's argument, ${b}$ is the base case, ${x}$ is the result of the base case, and ${f(n \to b)}$ is a call to the function with an argument ${n}$ that tends towards the base case. Put together, the recursive function is a function with a two-pronged definition:

1. It's some determinable value under certain circumstances (the base case), and
2. it's an evaluation of itself with a different argument that brings the definition closer to the first prong.

This is a high-level view of recursive functions. At the lower levels, the definition looks more like:

This might not seem like much of a change, but with this notation, we've included subscripts to emphasize a critical fact about recursive functions at the low level: Whenever we make a recursive call, we are essentially making a call to an entirely new function. In other words, if we had code that looked like:

f(n) {
   if (n=0) return 0;
   else f(n-1);
}
f(3)

We could accomplish the same result by writing:

a(n) { return n-1; }
b(n) { return n-1; }
c(n) { return n-1; }
f(n) {
   let x = a(n);
   let y = b(x);
   let z = c(y);
   return z;
}
f(3);

Obviously the recursive definition allows us to pass more than 3 arguments, but the point is, recursive calls result in memory consumption just as if we were calling completely different functions (setting aside compiler optimizations).

Keeping this fact in mind, we see that there are several requirements for implementing recursion:

1. Each call must have their own memory to store arguments.
2. Each call must have their own memory to store local variables.
3. Each call must have a return pointer.

These requirements ensure that each function call has its own state. Additionally, that state must only exist for a limited amount of time: Starting at (1) the moment the call is made, and ending at (2) the moment the return instruction is reached. And because this time restriction implies that the calls are ordered, an additional rule is needed: The caller can return only if the callee has returned.

Let's consider an example. Suppose we have the following recursive pseudocode:

h(n) => {
   n = 0? => return 0
   else: h(n-1)
}
g(...) => h(n)
f(...) => g(...)

Here, we see that f(...) calls the function g(...), which calls the function h(n). The function h(n) then either calls itself or returns 0.

When we call the function f(...), we get the following effect in the stack:

Notice the labels f() frame and previous frame. All of the stacks elements (the individual rectangles in the diagram) used for a particular function constitute the function's frame. These elements might store any of the following for f():

1. Optionally, the value inside %rbp, which contains the address of the stack element immediately prior. This is optional because it's only necessary if there is a variable amount of elements to be allocated for the call. Why? Because if there is a variable amount of elements, then the compiler needs a bookmark. If the amount of elements to be allocated is fixed, the compiler does not need to set this register's value — it simply performs arithmetic on the current address to get back to where it should go back to: "I know I pushed 8 bytes of data, so I only have to subtract 8 bytes worth of data."
2. Return information for f().
3. Arguments for f().
4. Local storage for f().
5. If f() has more than 6 arguments, the data needed to get those arguments.
6. Temporary space for f(), if needed.

When we encounter the callq instruction for g(), we get something that looks like:

When we get to h(), we the same thing:

And when make a recursive call, we see the same:

As we can see, if the recusive calls contain local variables, those will result in new allocations. If there are too many recursive calls, we get a stack overflow (often presented as the runtime error "maximum stack size exceeded"). Assuming the base case for h() is reached, we might get something that looks like this:

Notice how the stack frames grow and shrinks with time — every frame beneath a given stack frame cannot "disappear" until the frame above it is finished.

Inside the Stack Frame

Inside the stack frame, we have something that looks like the following:

The ellipses indicate are used to indicate further stack elements corresponding to that particular kind of data. Importantly, all of the data from argument 1 to the return address is the caller frame — the frame of the caller that called the function. Everything from the optional old %rbp up to the next return address is called the callee frame — the frame of the function called.

Caller- v. Callee-saved

Recall: When a function 𝑓 calls a function 𝑔, we say that 𝑓 is the caller , and 𝑔 is the callee. Now suppose that both 𝑓 and 𝑔 both want to use some register ${R_n,}$ say the register %rdx. Because there's one, and only one %rdx, if 𝑓 uses %rdx and stores something in there, when 𝑔 later uses %rdx, they'd overwrite whatever 𝑓 stored in %rdx.

On an x86-64 chip, there are only 16 registers. This presents a challenge: How do ensure that the 16 registers are used efficiently? With 16 registers, there's the threat of a single procedure hogging too many of the registers. This threat is addressed through register saving conventions. There are two such conventions:

1. Caller saved - The caller saves temporary values in its frame before the call.
2. Callee saved - The callee saves temporary values in its frame before using the register, and restores the values before returning control to the caller.

The caller saved registers are as follows (the Other Purpose column lists another purpose for the register, along side caller saved):

For example, suppose f() must call g(). Both f() and g() use the register %rdi. To ensure %rdi is shared between both f() and g(), f() will save the contents of %rdi in its stack frame, alongside any other data it must save:

By keeping storing this data in its own frame, f() doesn't have to concern itself with whatever happens to registers later down the call chain. When control gets back to f(), all it must do is use the data it stored away in its frame.

Alternatively, f() could employ the callee saved approach. Here, the callee g() must save f()'s data somewhere, and it is g()'s responsibility to save and restore that data before it returns control to f(). The callee saved registers are laid out below.