Chapter 3. Machine-Level Representation of Programs

TL;DR

Machine code sees 16 general-purpose 64-bit registers, the program counter %rip, four condition codes (CF, ZF, SF, OF), and memory as a flat byte array with no types. mov copies data, leaq computes addresses and cheap arithmetic, cmp and test set the flags, and conditional jumps or cmov consume them. Loops compile to tests and jumps, dense switches to jump tables. Procedures pass the first six integral arguments in %rdi, %rsi, %rdx, %rcx, %r8, %r9, return in %rax, and keep %rbx, %rbp, %r12 through %r15 callee saved on a downward-growing stack topped by %rsp. Arrays are row major, struct fields sit at fixed compile-time offsets with alignment padding. Unchecked stack buffers let input overwrite the return address, mitigated by ASLR, stack canaries, and the NX bit. Floating point lives in %xmm0 through %xmm15 with its own instruction set, passing arguments in %xmm0 through %xmm7 and returning in %xmm0.

The presentation is based on x86-64 as generated by gcc on Linux.

3.1 A Historical Perspective

The Intel processor line, colloquially x86, evolved from one of the first single-chip 16-bit microprocessors. Transistor counts trace the growth in complexity.

Processor	Year	Transistors	Machine-level significance
8086	1978	29 K	First-generation 16-bit; 20-bit addresses. The 8087 coprocessor (1980) established the "x87" floating-point model
80286	1982	134 K	More (now obsolete) addressing modes; basis of the IBM PC-AT
i386	1985	275 K	Expanded to 32 bits; flat addressing model used by Linux; first in the series to fully support Unix
i486	1989	1.2 M	Integrated the FPU onto the chip
Pentium	1993	3.1 M	Minor instruction set extensions
PentiumPro	1995	5.5 M	New P6 microarchitecture; added conditional move instructions
Pentium/MMX	1997	4.5 M	Integer vector instructions (64-bit vectors of 1-, 2-, or 4-byte elements)
Pentium II	1997	7 M	P6 continuation
Pentium III	1999	8.2 M	SSE: 128-bit vectors of integer or floating-point data
Pentium 4	2000	42 M	SSE2 with double-precision floating point; compilers can use SSE instead of x87 for floating-point code
Pentium 4E	2004	125 M	Hyperthreading; EM64T, Intel's implementation of the AMD-developed 64-bit extension referred to here as x86-64
Core 2	2006	291 M	First multi-core Intel processor; no hyperthreading
Core i7, Nehalem	2008	781 M	Hyperthreading plus multi-core
Core i7, Sandy Bridge	2011	1.17 G	AVX: 256-bit vectors
Core i7, Haswell	2013	1.4 G	AVX2

Every processor is backward compatible with code compiled for earlier versions, which explains the many strange artifacts of the instruction set. Intel names the line IA32 (32-bit) and Intel64 (the 64-bit extension). AMD produces compatible processors and introduced x86-64, the widely adopted 64-bit extension to IA32, around 2002. The 8086 memory model and its 80286 extensions became obsolete with the i386, and the x87 floating-point instructions became obsolete with SSE2.

3.2 Program Encodings

Compiling with gcc -Og -o p p1.c p2.c runs the full pipeline. The C preprocessor expands #include files and #define macros. The compiler generates assembly files p1.s and p2.s. The assembler converts these into binary relocatable object files p1.o and p2.o, machine code with the addresses of global values not yet filled in. The linker merges the object files with library code such as printf into the executable p, the exact form of code the processor runs.

The option -Og (gcc 4.8 and later) produces machine code that follows the overall structure of the source. Higher levels such as -O1 and -O2 give better performance at the cost of heavily transformed code.

3.2.1 Machine-Level Code

Two abstractions define machine-level programming. First, the instruction set architecture (ISA) defines the processor state, the instruction formats, and the effect of each instruction on the state. The ISA presents program behavior as if instructions execute sequentially, one completing before the next begins. The hardware executes many instructions concurrently but ensures the observable behavior matches the sequential model. Second, machine-level programs use virtual addresses, presenting memory as a very large byte array. The OS and hardware translate them to physical addresses.

Machine code exposes processor state that C hides.

• The program counter (PC, register %rip) holds the address of the next instruction to execute.
• The integer register file contains 16 named locations holding 64-bit values, either addresses or integer data.
• The condition code registers hold status about the most recently executed arithmetic or logical instruction and implement conditional control and data flow.
• A set of vector registers each hold one or more integer or floating-point values.

Machine code views memory as a byte-addressable array. Aggregate types such as arrays and structures are contiguous byte collections. Assembly makes no distinction between signed and unsigned integers, between pointer types, or even between pointers and integers. In current x86-64 implementations the upper 16 bits of a virtual address must be zero, so addresses span at most 2^48 bytes (256 TB).

A single instruction performs only an elementary operation, such as adding two register values, moving data between register and memory, or branching. The compiler composes sequences of such instructions to implement expressions, loops, and procedure calls.

3.2.2 Code Examples

The running example is mstore.c.

mstore.c

long mult2(long, long);

void multstore(long x, long y, long *dest) {
    long t = mult2(x, y);
    *dest = t;
}

gcc -Og -S mstore.c stops after compilation and produces mstore.s.

mstore.s

multstore:
  pushq    %rbx
  movq     %rdx, %rbx
  call     mult2
  movq     %rax, (%rbx)
  popq     %rbx
  ret

gcc -Og -c mstore.c compiles and assembles into mstore.o. The procedure occupies 14 bytes of object code.

53 48 89 d3 e8 00 00 00 00 48 89 03 5b c3

The machine executes a plain byte sequence encoding instructions and retains almost no information about the source. A disassembler regenerates assembly-like text from machine code.

linux> objdump -d mstore.o

0000000000000000 <multstore>:
   0:  53                    push   %rbx
   1:  48 89 d3              mov    %rdx,%rbx
   4:  e8 00 00 00 00        callq  9 <multstore+0x9>
   9:  48 89 03              mov    %rax,(%rbx)
   c:  5b                    pop    %rbx
   d:  c3                    retq

Properties of x86-64 machine code.

1. Instructions range from 1 to 15 bytes. Common instructions and those with fewer operands get shorter encodings.
2. From a given starting position, bytes decode uniquely into instructions. Only pushq %rbx can start with byte 53.
3. The disassembler works purely from the byte sequence and needs no source or assembly files.
4. The disassembler's naming differs slightly from gcc output. It may omit size suffixes (push for pushq) and adds q to call and ret. These suffixes can safely be omitted either way.

Linking (gcc -Og -o prog main.c mstore.c) shifts the code to its run-time address range, fills in the target address of the callq to mult2 (matching calls with executable code locations is a linker task), and may pad functions with trailing nop instructions to a multiple of 16 bytes for better memory system placement of subsequent code.

Displaying the byte representation

(gdb) x/14xb multstore displays 14 hex-formatted bytes starting at the address of multstore.

3.2.3 Notes on Formatting

gcc-generated assembly contains directives, lines beginning with ., that guide the assembler and linker and can generally be ignored.

ATT versus Intel format

The presentation uses ATT format, the default for gcc and objdump. Intel format, used in Intel and Microsoft documentation, omits size suffixes (push, mov instead of pushq, movq), omits the % before register names, writes memory operands differently (QWORD PTR [rbx] versus (%rbx)), and lists operands in the reverse order. gcc -Og -S -masm=intel mstore.c generates Intel format.

Assembly combines with C either as whole functions in assembly files linked with C code, or through gcc's inline asm directive. This is needed only for machine features inaccessible from C, such as reading the parity flag PF.

3.3 Data Formats

Owing to its 16-bit origins, Intel calls 16 bits a "word", 32 bits a "double word", and 64 bits a "quad word".

C declaration	Intel data type	Assembly suffix	Size (bytes)
char	Byte	b	1
short	Word	w	2
int	Double word	l	4
long	Quad word	q	8
char *	Quad word	q	8
float	Single precision	s	4
double	Double precision	l	8

Pointers are 8-byte quad words and long is 64 bits. The legacy 80-bit x87 format is accessible as long double but is neither portable nor implemented with high-performance hardware. Avoid it.

Most instructions carry a single-character size suffix, as in movb, movw, movl, movq. The suffix l serves both 4-byte integers ("long words") and 8-byte double-precision floats without ambiguity, since floating point uses an entirely separate set of instructions and registers.

3.4 Accessing Information

An x86-64 CPU contains 16 general-purpose registers storing 64-bit values, integer data and pointers. The original 8086 had eight 16-bit registers, %ax through %bp. IA32 extended them to 32 bits (%eax through %ebp). x86-64 extended them to 64 bits (%rax through %rbp) and added %r8 through %r15.

64-bit	32-bit	16-bit	8-bit	Role
%rax	%eax	%ax	%al	Return value
%rbx	%ebx	%bx	%bl	Callee saved
%rcx	%ecx	%cx	%cl	4th argument
%rdx	%edx	%dx	%dl	3rd argument
%rsi	%esi	%si	%sil	2nd argument
%rdi	%edi	%di	%dil	1st argument
%rbp	%ebp	%bp	%bpl	Callee saved
%rsp	%esp	%sp	%spl	Stack pointer
%r8	%r8d	%r8w	%r8b	5th argument
%r9	%r9d	%r9w	%r9b	6th argument
%r10	%r10d	%r10w	%r10b	Caller saved
%r11	%r11d	%r11w	%r11b	Caller saved
%r12	%r12d	%r12w	%r12b	Callee saved
%r13	%r13d	%r13w	%r13b	Callee saved
%r14	%r14d	%r14w	%r14b	Callee saved
%r15	%r15d	%r15w	%r15b	Callee saved

Instructions can operate on the low-order 1, 2, 4, or 8 bytes of any register. Two conventions govern the remaining bytes when an instruction with a register destination generates a value smaller than 8 bytes. Instructions generating 1- or 2-byte quantities leave the remaining bytes unchanged. Instructions generating 4-byte quantities zero the upper 4 bytes, a convention adopted with the expansion from IA32 to x86-64.

%rsp, the stack pointer, indicates the end position of the run-time stack and is the most constrained register. The other 15 are more flexible, with programming conventions governing their use for stack management, argument passing, return values, and local storage.

3.4.1 Operand Specifiers

Operands come in three types. An immediate is a constant, written $Imm in ATT syntax, as in $-577 or $0x1F. A register operand denotes the contents R[ra], treating the register set as an array R. A memory operand denotes M[Addr], treating memory as a large byte array. The subscript for the operand byte count is usually dropped.

Type	Form	Operand value	Name
Immediate	$Imm	Imm	Immediate
Register	ra	R[ra]	Register
Memory	Imm	M[Imm]	Absolute
Memory	(ra)	M[R[ra]]	Indirect
Memory	Imm(rb)	M[Imm + R[rb]]	Base + displacement
Memory	(rb,ri)	M[R[rb] + R[ri]]	Indexed
Memory	Imm(rb,ri)	M[Imm + R[rb] + R[ri]]	Indexed
Memory	(,ri,s)	M[R[ri] * s]	Scaled indexed
Memory	Imm(,ri,s)	M[Imm + R[ri] * s]	Scaled indexed
Memory	(rb,ri,s)	M[R[rb] + R[ri] * s]	Scaled indexed
Memory	Imm(rb,ri,s)	M[Imm + R[rb] + R[ri] * s]	Scaled indexed

The most general form Imm(rb,ri,s) has four components. Imm is the immediate offset, rb the base register, ri the index register, and s a scale factor of 1, 2, 4, or 8. Base and index must be 64-bit registers. The computed address Imm + R[rb] + R[ri] * s is called the effective address. The other forms are special cases. The general form arises when referencing array and structure elements.

3.4.2 Data Movement Instructions

The mov class copies data from source to destination without transformation.

Instruction	Effect	Description
mov S, D	D ← S	Move
movb		Move byte
movw		Move word
movl		Move double word
movq		Move quad word
movabsq I, R	R ← I	Move absolute quad word

The source can be an immediate, register, or memory location, and the destination a register or memory location. A move cannot have both operands in memory, so memory-to-memory copies require two instructions through a register. Register operands must match the size suffix. movl with a register destination additionally zeroes the upper 4 bytes. The other mov variants update only the designated bytes. The five source/destination combinations look as follows.

movl $0x4050,%eax        Immediate to register, 4 bytes
movw %bp,%sp             Register to register,  2 bytes
movb (%rdi,%rcx),%al     Memory to register,    1 byte
movb $-17,(%rsp)         Immediate to memory,   1 byte
movq %rax,-12(%rbp)      Register to memory,    8 bytes

movq accepts only immediates representable as 32-bit two's-complement values, sign extended to 64 bits. movabsq accepts an arbitrary 64-bit immediate but only a register destination.

Two instruction classes copy a smaller source (register or memory) to a larger register destination. movz fills the remaining bytes with zeros. movs fills by sign extension, replicating the most significant bit of the source. The final two characters of each name are size designators, source then destination.

Instruction	Effect	Description
movz S, R	R ← ZeroExtend(S)
movzbw		Zero-extend byte to word
movzbl		Zero-extend byte to double word
movzwl		Zero-extend word to double word
movzbq		Zero-extend byte to quad word
movzwq		Zero-extend word to quad word

Instruction	Effect	Description
movs S, R	R ← SignExtend(S)
movsbw		Sign-extend byte to word
movsbl		Sign-extend byte to double word
movswl		Sign-extend word to double word
movsbq		Sign-extend byte to quad word
movswq		Sign-extend word to quad word
movslq		Sign-extend double word to quad word
cltq	%rax ← SignExtend(%eax)	Sign-extend %eax to %rax

There is no movzlq. Zero extension from 4 to 8 bytes is achieved with movl to a register destination, exploiting the upper-4-byte zeroing convention. cltq has no operands and is a compact equivalent of movslq %eax, %rax.

How byte moves differ

movabsq $0x0011223344556677, %rax    %rax = 0011223344556677
movb    $0xAA, %dl                   %dl  = AA
movb    %dl,%al                      %rax = 00112233445566AA
movsbq  %dl,%rax                     %rax = FFFFFFFFFFFFFFAA
movzbq  %dl,%rax                     %rax = 00000000000000AA

movb leaves the other bytes unchanged. movsbq sets them from the sign bit of the source (0xAA has high bit 1). movzbq zeroes them. Similarly, movw $-1, %ax changes only the low 2 bytes, movl $-1, %eax sets the low 4 bytes and zeroes the high 4, and movq $-1, %rax sets the full register.

3.4.3 Data Movement Example

long exchange(long *xp, long y) {
    long x = *xp;
    *xp = y;
    return x;
}

  xp in %rdi, y in %rsi
exchange:
  movq    (%rdi), %rax      Get x at xp. Set as return value.
  movq    %rsi, (%rdi)      Store y at xp.
  ret

Two observations follow. C pointers are plain addresses, and dereferencing copies the pointer into a register and uses that register in a memory reference. Local variables are typically kept in registers rather than memory, since register access is much faster.

3.4.4 Pushing and Popping Stack Data

Instruction	Effect	Description
pushq S	R[%rsp] ← R[%rsp] − 8; M[R[%rsp]] ← S	Push quad word
popq D	D ← M[R[%rsp]]; R[%rsp] ← R[%rsp] + 8	Pop quad word

The program stack lives in memory and grows toward lower addresses. The top element has the lowest address of all stack elements, and %rsp holds that address. pushq %rbp behaves like subq $8,%rsp followed by movq %rbp,(%rsp) but encodes in a single byte instead of eight. popq %rax behaves like movq (%rsp),%rax followed by addq $8,%rsp. A popped value remains in memory until overwritten. Since the stack occupies ordinary memory, any addressing mode can reach arbitrary stack positions, so movq 8(%rsp),%rdx reads the second quad word from the stack.

3.5 Arithmetic and Logical Operations

Integer and logic operations divide into four groups, load effective address, unary, binary, and shifts. Each group except leaq has byte, word, double-word, and quad-word variants.

Instruction	Effect	Description
leaq S, D	D ← &S	Load effective address
inc D	D ← D + 1	Increment
dec D	D ← D − 1	Decrement
neg D	D ← −D	Negate
not D	D ← ~D	Complement
add S, D	D ← D + S	Add
sub S, D	D ← D − S	Subtract
imul S, D	D ← D * S	Multiply
xor S, D	D ← D ^ S	Exclusive-or
or S, D	D ← D | S	Or
and S, D	D ← D & S	And
sal k, D	D ← D << k	Left shift
shl k, D	D ← D << k	Left shift (same as sal)
sar k, D	D ← D >>A k	Arithmetic right shift
shr k, D	D ← D >>L k	Logical right shift

3.5.1 Load Effective Address

leaq is a variant of movq that computes the effective address of its source operand and writes it to a register destination without touching memory. It generates pointers and, more often, compact arithmetic. If %rdx holds x, then leaq 7(%rdx,%rdx,4), %rax sets %rax to 5x + 7. The destination must be a register. An expression like x + 4*y + 12*z compiles to a sequence of three leaq instructions.

3.5.2 Unary and Binary Operations

Unary operations use a single operand as both source and destination, register or memory, as in incq (%rsp). Binary operations use the second operand as both a source and the destination, with the source given first. subq %rax,%rdx computes %rdx = %rdx - %rax, read as "subtract %rax from %rdx". The first operand may be immediate, register, or memory. The second must be register or memory, and both cannot be memory. A memory destination is read, updated, and written back.

3.5.3 Shift Operations

The shift amount comes first, as an immediate or the single-byte register %cl, and the value to shift second. For a w-bit value the amount is taken from the low-order m bits of %cl, where 2^m = w, and higher bits are ignored, so %cl = 0xFF shifts salb by 7, salw by 15, sall by 31, and salq by 63. sal and shl are the same left shift, filling with zeros. sar is arithmetic right shift, filling with the sign bit. shr is logical right shift, filling with zeros. The destination is a register or memory location.

3.5.4 Discussion

Most operations serve both unsigned and two's-complement arithmetic because their bit-level behavior is identical for the two encodings. Only right shifting distinguishes signed (sar) from unsigned (shr) data. This shared behavior is one reason two's complement is the preferred signed representation. Compilers freely reuse a single register for multiple program values and move values among registers.

3.5.5 Special Arithmetic Operations

Intel calls a 16-byte quantity an oct word. x86-64 supports full 128-bit products and 128/64 division.

Instruction	Effect	Description
imulq S	R[%rdx]:R[%rax] ← S * R[%rax]	Signed full multiply
mulq S	R[%rdx]:R[%rax] ← S * R[%rax]	Unsigned full multiply
cqto	R[%rdx]:R[%rax] ← SignExtend(R[%rax])	Convert to oct word
idivq S	R[%rdx] ← R[%rdx]:R[%rax] mod S; R[%rax] ← R[%rdx]:R[%rax] ÷ S	Signed divide
divq S	R[%rdx] ← R[%rdx]:R[%rax] mod S; R[%rax] ← R[%rdx]:R[%rax] ÷ S	Unsigned divide

imulq has two forms distinguished by operand count. The two-operand form in the earlier table produces a truncated 64-bit product. The one-operand forms, mulq unsigned and imulq signed, multiply the source by %rax and store the full 128-bit product in %rdx (high) and %rax (low). gcc exposes 128-bit integers as __int128.

Division takes a 128-bit dividend in %rdx:%rax and the divisor as the operand, storing the quotient in %rax and the remainder in %rdx. For a 64-bit dividend in %rax, %rdx must first be set to all zeros (unsigned) or to the sign of %rax (signed, via cqto, which Intel documentation calls cqo).

3.6 Control

Machine code implements conditional behavior in two steps. It tests data values, then alters either the control flow (jumps) or the data flow (conditional moves) based on the result. Data-dependent control flow is the more general and more common approach.

3.6.1 Condition Codes

The CPU maintains single-bit condition code registers describing the most recent arithmetic or logical operation.

• CF, carry flag. The operation carried out of the most significant bit, detecting unsigned overflow.
• ZF, zero flag. The result was zero.
• SF, sign flag. The result was negative.
• OF, overflow flag. The operation caused two's-complement overflow, positive or negative.

For t = a + b the flags are computed as follows.

CF   (unsigned) t < (unsigned) a
ZF   (t == 0)
SF   (t < 0)
OF   (a < 0 == b < 0) && (t < 0 != a < 0)

leaq sets no condition codes. Logical operations set CF and OF to zero. Shifts set CF to the last bit shifted out and OF to zero. inc and dec set OF and ZF but leave CF unchanged. Two instruction classes set condition codes without changing any other register.

Instruction	Based on	Description
cmp S1, S2	S2 − S1	Compare (like sub, no destination update)
test S1, S2	S1 & S2	Test (like and, no destination update)

cmp sets ZF when the operands are equal, and the other flags give ordering. test typically repeats an operand (testq %rax,%rax tests sign and zero) or applies a bit mask.

3.6.2 Accessing the Condition Codes

Condition codes are used in three ways, setting a byte to 0 or 1, jumping conditionally, or moving data conditionally. The set instructions write a single byte based on a combination of condition codes. The suffix denotes a condition, not a size.

Instruction	Synonym	Effect	Set condition
sete	setz	D ← ZF	Equal / zero
setne	setnz	D ← ~ZF	Not equal / not zero
sets		D ← SF	Negative
setns		D ← ~SF	Nonnegative
setg	setnle	D ← ~(SF ^ OF) & ~ZF	Greater (signed >)
setge	setnl	D ← ~(SF ^ OF)	Greater or equal (signed >=)
setl	setnge	D ← SF ^ OF	Less (signed <)
setle	setng	D ← (SF ^ OF) | ZF	Less or equal (signed <=)
seta	setnbe	D ← ~CF & ~ZF	Above (unsigned >)
setae	setnb	D ← ~CF	Above or equal (unsigned >=)
setb	setnae	D ← CF	Below (unsigned <)
setbe	setna	D ← CF | ZF	Below or equal (unsigned <=)

A typical sequence for a < b with both long is cmpq %rsi, %rdi, then setl %al, then movzbl %al, %eax to clear the rest of the register. For a comparison t = a - b, signed tests combine SF ^ OF with ZF. Without overflow, a < b gives SF = 1. With overflow the sense of SF reverses, so SF ^ OF tests a < b correctly in all cases. Unsigned tests use CF and ZF. Machine code associates no type with a value. It selects signed versus unsigned behavior through instruction and condition-code choice.

3.6.3 Jump Instructions

A jump transfers control to a labeled destination. jmp is unconditional and can be direct (jmp .L1) or indirect (jmp *%rax, jmp *(%rax)). Conditional jumps can only be direct.

Instruction	Synonym	Jump condition	Description
jmp Label		1	Direct jump
jmp *Operand		1	Indirect jump
je	jz	ZF	Equal / zero
jne	jnz	~ZF	Not equal / not zero
js		SF	Negative
jns		~SF	Nonnegative
jg	jnle	~(SF ^ OF) & ~ZF	Greater (signed >)
jge	jnl	~(SF ^ OF)	Greater or equal (signed >=)
jl	jnge	SF ^ OF	Less (signed <)
jle	jng	(SF ^ OF) | ZF	Less or equal (signed <=)
ja	jnbe	~CF & ~ZF	Above (unsigned >)
jae	jnb	~CF	Above or equal (unsigned >=)
jb	jnae	CF	Below (unsigned <)
jbe	jna	CF | ZF	Below or equal (unsigned <=)

3.6.4 Jump Instruction Encodings

Most jumps use PC-relative encoding. The operand is the difference between the target address and the address of the instruction following the jump, stored in 1, 2, or 4 bytes. A second method gives a 4-byte absolute address. The offset is measured from the next instruction because the processor updates the PC before executing the jump. PC-relative encoding keeps jumps compact and lets code relocate without altering the encoded offsets, which matters for linking (Chapter 7).

rep; ret

gcc emits the combination rep; ret (disassembled repz retq) to avoid a ret that is the direct target of a conditional jump, which some AMD processors mispredict. Here rep acts as a no-op and can be ignored.

3.6.5 Implementing Conditional Branches with Conditional Control

The general translation of if (test-expr) then-statement else else-statement uses conditional and unconditional jumps.

    t = test-expr;
    if (!t) goto false;
    then-statement
    goto done;
false:
    else-statement
done:

The book renders assembly control flow as "goto code", C with goto mirroring the jump structure, which relates to the source more easily than raw assembly.

3.6.6 Implementing Conditional Branches with Conditional Moves

A conditional move computes both outcomes, then selects one based on the condition. This suits modern pipelined processors, which rely on branch prediction. A mispredicted conditional jump discards partially executed instructions and refills the pipeline, costing on the order of 15 to 30 cycles. A conditional move carries no control dependence, so nothing needs predicting.

Instruction	Synonym	Move condition	Description
cmove S, R	cmovz	ZF	Equal / zero
cmovne S, R	cmovnz	~ZF	Not equal / not zero
cmovs S, R		SF	Negative
cmovns S, R		~SF	Nonnegative
cmovg S, R	cmovnle	~(SF ^ OF) & ~ZF	Greater (signed >)
cmovge S, R	cmovnl	~(SF ^ OF)	Greater or equal (signed >=)
cmovl S, R	cmovnge	SF ^ OF	Less (signed <)
cmovle S, R	cmovng	(SF ^ OF) | ZF	Less or equal (signed <=)
cmova S, R	cmovnbe	~CF & ~ZF	Above (unsigned >)
cmovae S, R	cmovnb	~CF	Above or equal (unsigned >=)
cmovb S, R	cmovnae	CF	Below (unsigned <)
cmovbe S, R	cmovna	CF | ZF	Below or equal (unsigned <=)

Operands are 16, 32, or 64 bits, with no single-byte form. The assembler infers the size from the destination register. A conditional expression v = test-expr ? then-expr : else-expr compiles to evaluating both then-expr and else-expr, then if (!t) v = ve.

Conditional moves are invalid when an evaluated branch could fault or produce a side effect that must not occur, since both branches always evaluate. The expression xp ? *xp : 0 cannot use one, because it would dereference a possibly null xp. gcc uses conditional moves only when both expressions are cheap, such as a single add, since evaluating both wastes work when computation is expensive.

3.6.7 Loops

C loops compile to combinations of tests and jumps. No loop instructions exist.

Do-while. do body while (test-expr) translates as follows.

loop:
    body-statement
    t = test-expr;
    if (t) goto loop;

While. Two strategies exist. Jump to middle jumps unconditionally to the test at the end (used at -Og).

    goto test;
loop:
    body-statement
test:
    t = test-expr;
    if (t) goto loop;

Guarded do converts to a do-while guarded by an initial skip test (used at higher optimization, e.g. -O1).

    t = test-expr;
    if (!t) goto done;
loop:
    body-statement
    t = test-expr;
    if (t) goto loop;
done:

For. for (init; test; update) body behaves by definition as init; while (test) { body; update; } and then translates by one of the two while strategies.

3.6.8 Switch Statements

A switch provides a multiway branch on an integer index. When cases are numerous (roughly four or more) and span a small range, gcc uses a jump table, an array whose entry i holds the address of the code for index i. A single indirect jump through the table selects the branch, so the time is independent of the case count, unlike a chain of if-else tests. gcc supports computed goto (goto *jt[index]) and code-location pointers (&&label) as C extensions expressing this.

The compiler shifts the index into a 0-based range, for example by subtracting 100, then treats it as unsigned so that a single greater-than-upper-bound test (ja) covers both the too-small and too-large cases, jumping to the default. The jump table lives in .rodata, .aligned, one .quad per index. Duplicate cases share a label, missing cases point to the default label, and fall-through omits the terminating jump so control drops into the next block.

3.7 Procedures

Machine-level support for a call from P to Q involves passing control (set the PC to Q's entry, then back to the instruction after the call on return), passing data (arguments and the return value), and allocating and freeing local memory. x86-64 implements only as much of this as each procedure needs, a minimalist strategy.

3.7.1 The Run-Time Stack

Procedure calls follow last-in first-out discipline, matched by a stack. Each procedure's stack frame holds what does not fit in registers. The stack grows toward lower addresses and %rsp points to the top element. Space is allocated by decrementing %rsp and freed by incrementing it.

In the general frame structure, the caller's frame ends with arguments 7 through n passed to the callee and the return address, both considered part of the caller's frame. The callee's frame holds saved registers, local variables, and an argument build area for calls it makes. Frames are usually fixed size, allocated at procedure entry. Many procedures need no frame at all, namely leaf procedures whose locals fit in registers and which call nothing.

3.7.2 Control Transfer

call Q pushes the return address, the address of the instruction after the call, and sets the PC to Q's entry. ret pops the return address and sets the PC to it. Both appear as callq and retq in objdump output. Call targets may be direct (a label) or indirect (a * operand).

Instruction	Description
call Label / call *Operand	Procedure call
ret	Return from call

3.7.3 Data Transfer

Up to six integral arguments, integers or pointers, pass in registers in order, using the register name matching the argument size.

Argument	64-bit	32-bit	16-bit	8-bit
1	%rdi	%edi	%di	%dil
2	%rsi	%esi	%si	%sil
3	%rdx	%edx	%dx	%dl
4	%rcx	%ecx	%cx	%cl
5	%r8	%r8d	%r8w	%r8b
6	%r9	%r9d	%r9w	%r9b

Arguments beyond six pass on the stack, argument 7 at the top, each rounded up to a multiple of 8 bytes. The return value comes back in %rax.

3.7.4 Local Storage on the Stack

Local data goes on the stack when registers run out, when its address is taken with &, or when it is an array or structure. The procedure allocates by decrementing %rsp and deallocates by incrementing it. For an 8-argument callee, the caller stores arguments 7 and 8 at offsets 0 and 8 from %rsp. After the call pushes the return address, they appear at offsets 8 and 16 in the callee's view.

3.7.5 Local Storage in Registers

Registers are a shared resource, so conventions prevent a callee from clobbering a caller's live values.

• Callee saved. %rbx, %rbp, and %r12 through %r15. A callee that uses one must preserve it, either leaving it unchanged or pushing it on entry and popping before return, so the caller sees the original value.
• Caller saved. All others except %rsp. Any function may overwrite them, so a caller with a live value must save it before a call.

Callee-saved registers are pushed at entry and popped in reverse order before return, matching the stack's LIFO order.

3.7.6 Recursive Procedures

The register-saving and stack conventions suffice for recursion with no extra mechanism. Each call gets private stack space for its return address, saved registers, and locals, and allocation and deallocation match the call/return order. The scheme extends to mutual recursion.

3.8 Array Allocation and Access

3.8.1 Basic Principles

For T A[N], the declaration allocates a contiguous region of L * N bytes, where L = sizeof(T), and introduces A as a pointer to the start, with value xA. Element i sits at xA + L * i. The scaled-index addressing modes with scales 1, 2, 4, and 8 cover the common element sizes. For int E[] with base in %rdx and index in %rcx, movl (%rdx,%rcx,4),%eax reads E[i].

3.8.2 Pointer Arithmetic

A[i] is identical to *(A+i). For a pointer p of type T *, p + i yields the address p + L * i. & produces addresses, often via leaq. Pointer difference within one array divides by the element size and yields a long index. Operations returning array values use data-size operations and registers, such as movl with %eax. Operations returning pointers use 8-byte operations and registers, such as leaq with %rax.

3.8.3 Nested Arrays

T D[R][C] stores elements in row-major order, all of row 0, then row 1, and so on. Element D[i][j] sits at

&D[i][j] = xD + L * (C * i + j)

For int A[5][3], A[i][j] sits at xA + 12i + 4j = xA + 4(3i + j), computed with leaq (3i, then xA + 12i) and a scaled movl.

3.8.4 Fixed-Size Arrays

With -O1, gcc optimizes fixed-size matrix code. It removes the loop index variable, converts array references to pointer dereferences, precomputes pointer start and end values, and steps pointers by the element or row stride, replacing multiplications with additions.

3.8.5 Variable-Size Arrays

ISO C99 allows array dimensions computed at allocation. In int A[n][n], the size parameter must precede the array parameter. Access to A[i][j] computes xA + 4(n * i + j), requiring an imulq to scale i by the runtime value n rather than the shift and add sequence used for fixed dimensions. The multiply can be costly but is unavoidable. Within loops, gcc again converts to pointer stepping, keeping both n for bound tests and a scaled stride such as 4n for pointer increments.

3.9 Heterogeneous Data Structures

3.9.1 Structures

A struct groups objects of possibly different types into one contiguous region. A pointer to a struct is the address of its first byte. The compiler records the byte offset of each field and accesses fields by adding the offset to the base address, resolved entirely at compile time. Machine code contains no field names. For

struct rec { int i; int j; int a[2]; int *p; };

the offsets are i=0, j=4, a=8, p=16, for 24 bytes total. With r in %rdi and i in %rsi, &(r->a[i]) compiles to leaq 8(%rdi,%rsi,4), %rax.

3.9.2 Unions

A union lets one block of memory be referenced as several types. All fields share the same starting offset, and the union's size is the maximum field size. It saves space when fields are mutually exclusive, often paired with an enumerated tag field in an enclosing struct, and it reinterprets bit patterns of one type as another, such as reading a double's bits as an unsigned long. When combining types of different sizes, byte ordering matters. On little-endian x86-64, a 4-byte union member maps to the low-order bytes of an 8-byte member.

3.9.3 Data Alignment

Alignment requires that a K-byte primitive object have an address that is a multiple of K, with K = 1 for char, 2 for short, 4 for int and float, and 8 for long, double, and pointers. x86-64 works with unaligned data, but Intel recommends alignment for memory system performance. A single aligned access avoids splitting an object across memory blocks.

The compiler inserts gaps between struct fields so each satisfies its alignment, gives the struct an overall alignment equal to that of its largest field, and pads the end so every element of an array of structs stays aligned. For struct S1 { int i; char c; int j; }, a 3-byte gap after c puts j at offset 8, sizing the struct at 12. For struct S2 { int i; int j; char c; }, 3 bytes of trailing padding size it at 12 so array elements remain 4-aligned.

Mandatory alignment for SSE

Some SSE instructions operate on 16-byte blocks and require 16-byte-aligned memory addresses. Violating this raises an exception. Memory allocators such as malloc therefore return 16-byte-aligned blocks, and most stack frames are 16-byte aligned. AVX drops the mandatory requirement.

3.10 Combining Control and Data in Machine-Level Programs

3.10.1 Understanding Pointers

• Every pointer has a type indicating what it points to. void * is a generic pointer. Pointer types are a C abstraction, absent from machine code.
• Every pointer has a value, the address of an object of its type. NULL (0) points nowhere.
• & creates a pointer, applies to any lvalue, and often compiles to leaq.
• * dereferences a pointer and compiles to a memory access.
• Arrays and pointers are closely related. a[i] equals *(a+i), with offsets scaled by object size.
• Casting a pointer changes its type but not its value, and changes the scaling of subsequent pointer arithmetic. (int *) p + 7 computes p + 28, while (int *) (p + 7) computes p + 7.
• Pointers can point to functions. The value is the address of the function's first instruction.

3.10.2 Using the gdb Debugger

gdb runs a machine-level program under control. It sets breakpoints by function or address, single-steps (stepi, nexti), continues or runs to return (continue, finish), examines registers and memory in various formats (print, x), and disassembles (disas). Running objdump -d first to obtain the disassembly helps.

3.10.3 Out-of-Bounds Memory References and Buffer Overflow

C performs no array bounds checking, and locals sit on the stack alongside saved registers and return addresses. Writing past a stack buffer, a buffer overflow, can corrupt this saved state. A corrupted return address makes ret jump to an unexpected location. gets, strcpy, strcat, and sprintf write without knowing the buffer size and are unsafe. fgets and similar length-limited functions are safe.

A more dangerous use injects exploit code as part of the input and overwrites the return address to point at it, so ret runs the attacker's code, for example to spawn a shell. The 1988 Internet worm used a buffer overflow in the fingerd daemon among its attacks.

3.10.4 Thwarting Buffer Overflow Attacks

Stack randomization (ASLR). The stack position varies per run, via a random-size allocation at program start (for example through alloca), so attackers cannot rely on a fixed stack address. ASLR more broadly randomizes code, library, stack, global, and heap positions per run. Attackers counter partially with a nop sled preceding the exploit code, so hitting any address in the sled slides execution into the exploit. Large randomization ranges make this expensive.

Stack corruption detection (stack protector). gcc places a randomly generated canary (guard) value between a local buffer and the saved state. Before returning, the code compares the canary against its stored value, read from a read-only segment via %fs:40, and a mismatch calls __stack_chk_fail. gcc inserts this automatically when a function has a local char buffer. -fno-stack-protector disables it.

Limiting executable code regions. Marking the stack readable and writable but not executable, via the AMD/Intel NX (no-execute) bit checked in hardware with no penalty, prevents execution of injected stack code. Historically x86 merged read and execute permission, making the stack executable.

These three mechanisms need no programmer effort, cost little, and combine for stronger protection, though none is a complete safeguard.

3.10.5 Supporting Variable-Size Stack Frames

Some functions need a frame whose size is unknown at compile time, from a call to alloca or a local variable-size array. x86-64 then uses %rbp as a frame pointer (base pointer). The callee saves the old %rbp, a callee-saved register, sets %rbp to the fixed reference point, and addresses fixed-size locals at offsets from %rbp while the variable-size region grows below. The leave instruction, equivalent to movq %rbp,%rsp followed by popq %rbp, restores %rsp and %rbp on exit. x86-64 uses a frame pointer only when the frame is variable size, whereas IA32 used it for every call. Frame-pointer and non-frame-pointer code mix freely as long as every function treats %rbp as callee saved.

3.11 Floating-Point Code

The floating-point architecture covers how values are stored and accessed, the operating instructions, and the argument, return, and register-preservation conventions. Media instructions evolved through MMX, SSE, and AVX, operating in SIMD (single instruction, multiple data) mode on packed vectors in MM (64-bit), XMM (128-bit), and YMM (256-bit) registers. From SSE2 (Pentium 4, 2000), scalar instructions operate on single float or double values in the low bytes of XMM registers, and all x86-64 processors support at least SSE2. The presentation uses AVX2 (Haswell, 2013, gcc -mavx2).

AVX provides 16 YMM registers %ymm0 through %ymm15, each 256 bits. The low 128 bits form the XMM registers %xmm0 through %xmm15. Scalar code uses only the low 32 bits (float) or 64 bits (double).

3.11.1 Floating-Point Movement and Conversion Operations

Instruction	Source	Destination	Description
vmovss	M32 / X	X / M32	Move single precision
vmovsd	M64 / X	X / M64	Move double precision
vmovaps	X	X	Move aligned packed single
vmovapd	X	X	Move aligned packed double

Memory-referencing moves are scalar and tolerate misalignment, though alignment is recommended. gcc uses vmovss and vmovsd for memory transfers and vmovaps and vmovapd for register-to-register copies. The "a" stands for aligned, and register copies cannot be misaligned.

Conversion from floating point to integer truncates toward zero.

Instruction	Source	Destination	Description
vcvttss2si	X/M32	R32	Single to int
vcvttsd2si	X/M64	R32	Double to int
vcvttss2siq	X/M32	R64	Single to quad-word int
vcvttsd2siq	X/M64	R64	Double to quad-word int

Conversion from integer to floating point uses a three-operand form. The second source affects only the upper bytes and is conventionally the same register as the destination.

Instruction	Source 1	Source 2	Destination	Description
vcvtsi2ss	M32/R32	X	X	Int to single
vcvtsi2sd	M32/R32	X	X	Int to double
vcvtsi2ssq	M64/R64	X	X	Quad-word int to single
vcvtsi2sdq	M64/R64	X	X	Quad-word int to double

For single to double, gcc emits vunpcklps then vcvtps2pd, leaving a duplicated result. For double to single, it emits vmovddup then vcvtpd2psx. The single-instruction equivalents vcvtss2sd and vcvtsd2ss go unused, for unclear reasons.

3.11.2 Floating-Point Code in Procedures

• Up to eight floating-point arguments pass in %xmm0 through %xmm7, in order. Further ones go on the stack.
• A floating-point value returns in %xmm0.
• All XMM registers are caller saved.

Pointers and integers use the general-purpose argument registers, floats and doubles use the XMM registers, and the two sequences are assigned independently by type and order. In double f1(int x, double y, long z), x arrives in %edi, y in %xmm0, and z in %rsi.

3.11.3 Floating-Point Arithmetic Operations

Single	Double	Effect	Description
vaddss	vaddsd	D ← S2 + S1	Add
vsubss	vsubsd	D ← S2 − S1	Subtract
vmulss	vmulsd	D ← S2 * S1	Multiply
vdivss	vdivsd	D ← S2 / S1	Divide
vmaxss	vmaxsd	D ← max(S2, S1)	Maximum
vminss	vminsd	D ← min(S2, S1)	Minimum
sqrtss	sqrtsd	D ← sqrt(S1)	Square root

S1 may be an XMM register or memory. S2 and D must be XMM registers.

3.11.4 Defining and Using Floating-Point Constants

AVX operations take no immediate operands, so the compiler stores constants in memory under labels such as .LC2 and reads them from there. cel2fahr reads 1.8 and 32.0 with vmulsd .LC2(%rip) and vaddsd .LC3(%rip). Each constant is stored as a pair of .long values, low order first (little endian), that decode as the IEEE double bit pattern.

3.11.5 Using Bitwise Operations in Floating-Point Code

Single	Double	Effect	Description
vxorps	vxorpd	D ← S2 ^ S1	Bitwise exclusive-or
vandps	vandpd	D ← S2 & S1	Bitwise and

These act on all 128 bits (packed), but for scalar code only the low bytes matter. They implement operations like absolute value, masking off the sign bit with vandpd, and negation, flipping the sign bit with vxorpd.

3.11.6 Floating-Point Comparison Operations

Instruction	Based on	Description
ucomiss S1, S2	S2 − S1	Compare single
ucomisd S1, S2	S2 − S1	Compare double

S2 must be an XMM register, and S1 may be XMM or memory. These set ZF, CF, and the parity flag PF. For floating point, PF is set when either operand is NaN, the unordered case, matching C's rule that comparisons involving NaN fail (even x == x is false for NaN). jp jumps on the unordered result. Otherwise CF and ZF behave like an unsigned comparison, ZF for equal and CF for S2 < S1.

Ordering of S2, S1	CF	ZF	PF
Unordered (NaN)	1	1	1
S2 < S1	1	0	0
S2 = S1	0	1	0
S2 > S1	0	0	0

3.11.7 Observations about Floating-Point Code

AVX2 floating-point code resembles integer code in style. Registers hold and operate on values and pass arguments. It differs in the larger instruction set, the many data-type conversions, and the potential for data parallelism through packed operations. The most reliable way to exploit that parallelism at present is gcc's vector extensions.