Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Assembly II

The assembly examples use GNU assembler’s AT&T syntax: source comes before destination, registers have a % prefix, and immediate values have a $ prefix. A few examples use names such as %1 and %2 for virtual registers; these are compiler intermediate-representation notation, not registers that can be written directly in x86-64 assembly.

For the x86-64 System V calling convention, see the AMD64 System V ABI. For instruction semantics, use Intel’s 64 and IA-32 Software Developer’s Manuals or AMD’s AMD64 Architecture Programmer’s Manual, Volume 3.

Registers

Caller-Saved and Callee-Saved

A function-call ABI specifies which register values must survive a call. From the caller’s point of view:

  • A caller-saved register may be overwritten by the function being called. If the caller still needs its value afterward, the caller must save it or arrange for the compiler to keep it elsewhere.
  • A callee-saved register must have its original value when the called function returns. A function that uses one must save and restore it, often in its stack frame.

Under the x86-64 System V ABI, the general-purpose caller-saved registers are %rax, %rcx, %rdx, %rsi, %rdi, and %r8–%r11. The callee-saved registers are %rbx, %rbp, and %r12–%r15; %rsp must also be restored to its required value before returning. Other ABIs can make different choices, so check the ABI for the target system.

Caller-saved registers are convenient for short-lived values and for passing function arguments. Their values do not survive a call unless the caller saves them. Callee-saved registers are useful when a value needs to remain available across calls: the callee pays the cost of preserving a register it uses, rather than every caller saving a live value around every call.

For example, both the loop index and its bound may be needed after each call:

for (int i = 0; i < size; ++i) {
    func(i);
}

If the compiler keeps i and size in registers across func, it must ensure they survive the call. It might choose callee-saved registers, or save and restore caller-saved registers. The best choice depends on the function and surrounding code.

In this ABI, the first six integer or pointer arguments are passed in %rdi, %rsi, %rdx, %rcx, %r8, and %r9. %r10 and %r11 are caller-saved, but are not argument registers for ordinary function calls.

Some languages allow a function to be defined inside another function. The inner function can then refer to variables in the enclosing function. A static link (also called a static chain) points to the enclosing function’s stack frame, where those variables live.

The x86-64 System V ABI assigns %r10 for passing this pointer when a nested-function implementation needs one. GCC supports nested functions as a C extension; nested functions are not part of standard C. Closures in languages such as C++, Python, and Rust also carry an environment, though their representation and calling convention need not use a static chain or %r10.

int func_p(int arg1, int arg2) {
    int a_p = arg1 + arg2;

    int func_c(int arg1, int arg2) {
        int a_c = arg1 - arg2;
        return a_p + a_c;  // reads a_p from the enclosing frame
    }

    return func_c(arg1, arg2);
}

When func_c runs, its static chain lets it find a_p in func_p’s frame. See GCC’s documentation on nested functions and the AMD64 System V ABI.

RFLAGS

RFLAGS holds processor status and control bits. Arithmetic and comparison instructions set status flags such as ZF (zero), CF (carry), SF (sign), and OF (signed overflow); conditional branches read them. For example, cmp sets flags as though it subtracted its source operand from its destination operand, without keeping the result:

cmpq %rsi, %rdi       # flags for %rdi - %rsi
je equal              # branch if ZF is set
jl signed_less        # signed comparison
jb unsigned_less      # unsigned comparison

RFLAGS also matters when control crosses from a user program into the operating-system kernel. A normal function call follows the function ABI; a system call follows the processor’s system-call mechanism and the operating system’s syscall ABI.

System Calls: syscall and sysret

A process runs with restricted privileges and cannot directly perform operations such as reading a file or creating a process. It requests these services from the operating-system kernel through system calls.

On x86-64, the syscall instruction transfers control to an operating-system entry point. The processor saves the next instruction address in %rcx and the old RFLAGS value in %r11; the kernel saves any state it needs before using those registers. The kernel eventually returns to user mode, commonly with sysret, which uses the saved return state. Thus %rcx and %r11 are clobbered by the syscall instruction.

The Linux x86-64 syscall convention is different from the ordinary function-call convention. The syscall number is in %rax; up to six arguments are in %rdi, %rsi, %rdx, %r10, %r8, and %r9; the result is returned in %rax. In particular, the fourth syscall argument uses %r10, even though %r10 is not an argument register for an ordinary function call.

For the processor behavior, see AMD’s AMD64 Architecture Programmer’s Manual, Volume 3 or Intel’s instruction-set manuals. The AMD64 System V ABI describes the Linux kernel calling convention.

Physical and Virtual Registers

Physical registers are the finite registers provided by the processor, such as %rax or %r12. Their use is constrained by the instruction set and the ABI.

Compilers often first translate a program into an intermediate form with virtual registers such as %1, %2, and %3. These names represent values, not fixed hardware locations. A compiler can create as many as its intermediate code needs, then assign virtual registers to physical registers or to stack slots. Liveness and register allocation are discussed below.

Control Flow

Control flow describes the order in which instructions execute:

  • Sequential execution moves to the next instruction.
  • A jump transfers control to another instruction in the current function.
  • A call transfers control to a function and records where execution should continue after the function returns.

Basic Blocks and Control-Flow Graphs

A basic block is a straight-line sequence of instructions with one entry point: execution starts at its first instruction and does not jump into its middle. A control-flow graph (CFG) represents each block as a node and each possible transfer between blocks as an edge. Conditional branches give a block multiple outgoing edges; loops create cycles in the graph.

For example, this loop can be divided into an entry block, a test block, a body block, and an exit block:

entry:
    i = 0
    sum = 0
    jump test

test:
    if i >= n, jump exit

body:
    sum = sum + i
    i = i + 1
    jump test

exit:
    return sum

The CFG has edges entry → test, test → body, test → exit, and body → test. Thinking in blocks makes it easier to see loops, branches, and which values can reach each part of the program. In a per-function CFG, calls are usually represented as instructions with a continuation; interprocedural graphs add edges into and out of called functions.

GCC’s internals manual describes basic blocks and the structures used to represent them.

Call Graph and Interprocedural CFG

A call graph (CG) has one node for each function and an edge from a caller to each function it may call. For example:

main ──→ fun1 ──→ fun2
  ├──────────────→ fun2
  └──────────────→ fun_rec ──→ fun_rec

The self-edge represents recursion. A call graph records which functions call one another, but it does not show the individual basic blocks inside each function.

An interprocedural control-flow graph (ICFG) includes basic blocks from multiple functions. It adds an edge from a call site to the callee’s entry and a return edge from the callee back to the continuation after that call. An ICFG therefore exposes how control can move across function boundaries.

Data Flow

Data-flow analysis follows values through instructions and control-flow edges. It helps a compiler decide where values are needed, which registers can share hardware, and which computations have no effect on the result.

Lifetime and Liveness

A value is live at a point if some possible future path reads that value before replacing it. Its live range is the part of the program where it remains live. Two values whose live ranges never overlap can often use the same physical register. The compiler builds this information across CFG edges, so branches and loops affect liveness.

Consider these illustrative instructions using virtual registers:

1  mov 8(%rsp), %1
2  mov 16(%rsp), %2
3  add %1, %2
4  mov 24(%rsp), %3
5  mov 32(%rsp), %4
6  mul %4, %3
7  call fun
8  sub %3, %2
9  mov %2, %rax
10 ret

After instruction 3, %1 is no longer needed. %4 is no longer needed after instruction 6, so %1 and %4 have non-overlapping live ranges and may share a physical register. %2 and %3 are both needed after the call, so they are live across it. The compiler can place them in callee-saved registers or save and reload them around the call if it uses caller-saved registers.

This is why register allocation is connected to both control flow and the calling convention: it must account for overlapping live ranges, branches, and calls that overwrite caller-saved registers. GCC documents liveness information used by its compiler passes.

Branches

At a conditional branch, only one successor executes at a time. Values used on different paths may therefore have non-overlapping live ranges and can sometimes share a physical register. At a point where paths join, the compiler must account for every value that may be needed along any incoming path.

cmp $0, %3
je ELSE
mov %4, %1
add $1, %1
mov %1, %rax
ret
ELSE:
mov %5, %2
add $1, %2
mov %2, %rax
ret

%1 and %2 are used on separate paths. Their live ranges do not overlap, so if they use compatible registers, the compiler can assign them the same physical register.

A value may also be created before a branch and remain live after the paths join:

mov 8(%rsp), %1       # value needed after the branch
cmp $0, %2
je ELSE
mov $1, %3
jmp JOIN
ELSE:
mov $2, %3
JOIN:
add %3, %1
mov %1, %rax
ret

%1 is defined before the branch and used after JOIN, so it must keep its value along both paths. %3 is also needed at JOIN; there the two values are live at the same time and cannot share a physical register.

Dead-Code Elimination

A computation is dead if its result is never used and it has no observable side effect. A compiler can remove dead computations. Branches also provide information: if every path produces the same result, the condition and the branch may be unnecessary.

mov 8(%rsp), %1
mov 16(%rsp), %2
add %1, %2            # result is never used
mov %1, %rax
ret

The result in %2 is never read, so the addition is dead. After removing it, the load into %2 is dead as well. A computation that writes through a pointer, performs I/O, calls a function with side effects, or accesses a volatile object cannot be removed merely because its numeric result is unused.

Conditional branches can also provide facts that make an inner branch unreachable:

cmp $0, %1
je ZERO

NONZERO:
cmp $0, %1
je DEAD               # impossible on this path
mov $1, %rax
jmp DONE
DEAD:
mov $2, %rax
jmp DONE

ZERO:
mov $0, %rax
DONE:
ret

If execution falls through the first je ZERO, %1 must be nonzero. Since %1 does not change before the second comparison, je DEAD can never be taken. Conditional data-flow analysis can fold that branch away, after which the unreachable DEAD block can be removed:

cmp $0, %1
je ZERO
mov $1, %rax
jmp DONE
ZERO:
mov $0, %rax
DONE:
ret

Extra

Liveness and Register Allocation

One way to picture register allocation is as a graph-coloring problem. Each virtual register is a node. Two nodes are connected when their values are live at the same time, meaning they cannot use the same physical register. Assigning physical registers is like assigning colors so connected nodes receive different colors. If there are not enough suitable registers, the compiler can move some values to memory (called spilling) and load them again when needed.

This is a simplified picture: real register allocators must also consider register classes, instruction constraints, calling conventions, and optimization costs. GCC’s documentation on RTL optimization passes describes its implementation stages.