Chapter 3. Machine-Level Representation of Programs

Computers execute machine code: sequences of bytes encoding low-level operations that manipulate data, manage memory, read and write storage devices, and communicate over networks. A compiler generates machine code through a series of stages based on the rules of the programming language, the instruction set of the target machine, and the conventions of the operating system. gcc emits assembly code, a textual representation of machine code, then invokes an assembler and a linker to produce executable machine code.

Reading compiler-generated assembly is a form of reverse engineering: understanding the transformation process by studying its output. It matters for analyzing compiler optimizations and code inefficiencies, understanding run-time behavior hidden by the language abstraction (e.g., shared versus private thread data), and understanding security vulnerabilities such as buffer overflow, which arise from how programs store run-time control information.

The presentation is based on x86-64 as generated by gcc on Linux, ignoring the arcane legacy features of the architecture. A 32-bit machine can address only about 4 GB (2^32 bytes); current 64-bit machines can use up to 256 TB (2^48 bytes) and could be extended to 16 EB (2^64 bytes).

3.1 A Historical Perspective

The Intel processor line, colloquially x86, evolved from one of the first single-chip 16-bit microprocessors. Transistor counts indicate 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; 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 (e.g., printf) into the executable file p, the exact form of code executed by the processor.

The option -Og (gcc 4.8 and later) produces machine code that follows the overall structure of the source; higher levels (-O1, -O2) yield better performance but 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 ISA model. Second, memory addresses are virtual addresses, presenting memory as a very large byte array; the OS and hardware translate them to physical addresses.

Parts of the processor state visible in machine code but hidden from the C programmer:

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

Machine code views memory as a byte-addressable array. Aggregate types (arrays, 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 (add two register values, move data between register and memory, conditionally branch). The compiler composes sequences of such instructions to implement expressions, loops, and procedure calls.

3.2.2 Code Examples

For a file 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, producing mstore.s:

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

gcc -Og -c mstore.c compiles and assembles, producing mstore.o. The 14 bytes of object code for the procedure are

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

The program executed by the machine is simply a byte sequence encoding instructions; the machine 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; it 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 grow them 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, and no explanatory content. The book's convention shows only relevant lines, numbered, with the parameter-to-register mapping stated above the listing and per-line annotations on the right.

ATT versus Intel format

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

Assembly code can be combined with C either by writing whole functions in assembly files linked with C code, or with gcc's inline asm directive. This is needed only for machine features inaccessible from C (e.g., 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. long is 64 bits. The legacy 80-bit x87 format is accessible as long double but is not portable and not implemented with high-performance hardware; avoid it.

Most instructions carry a single-character suffix denoting operand size: movb, movw, movl, movq. 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 what happens to the remaining bytes when an instruction generates a value smaller than 8 bytes with a register destination: instructions generating 1- or 2-byte quantities leave the remaining bytes unchanged; instructions generating 4-byte quantities set the upper 4 bytes to zero (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 a set of programming conventions governing their use for stack management, argument passing, return values, and local storage.

3.4.1 Operand Specifiers

Operands are of three types: immediate (constant, written $Imm in ATT syntax, e.g. $-577, $0x1F), register (R[ra], treating the register set as an array R), and memory (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: immediate offset, base register, index register, and scale factor s ∈ {1, 2, 4, 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; the destination a register or memory location. A move cannot have both operands in memory: 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. Five source/destination combinations:

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 by 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, 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. C "pointers" are simply addresses: 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 its 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; the stack top is always the address in %rsp. Since the stack occupies ordinary memory, any addressing mode can access arbitrary stack positions: 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 (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 accessing 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. For example, 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), e.g. 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 ("subtract %rax from %rdx"). The first operand is immediate, register, or memory; the second is register or memory; both cannot be memory. A memory destination is read, updated, and written back.

3.5.3 Shift Operations

The shift amount is given first (immediate, or the single-byte register %cl), the value to shift second. For a w-bit data value, the shift amount is taken from the low-order m bits of %cl where 2^m = w; higher bits are ignored (so %cl = 0xFF shifts salb by 7, salw by 15, sall by 31, salq by 63). sal/shl are the same left shift (fill with zeros). sar is arithmetic right shift (fill with sign bit); shr is logical right shift (fill 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 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 table above) produces a truncated 64-bit product; the one-operand forms (mulq unsigned, imulq signed) multiply the source by %rax and store the full 128-bit product in %rdx (high) and %rax (low). gcc supports 128-bit integers via __int128.

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

3.6 Control

Machine code implements conditional behavior by two mechanisms: 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 (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: 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; other flags give ordering. test typically repeats an operand (testq %rax,%rax tests sign/zero) or applies a bit mask.

3.6.2 Accessing the Condition Codes

Three uses of condition codes: set a byte to 0/1, conditionally jump, or conditionally move data. 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 (both long): 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 use combinations of SF ^ OF and ZF: without overflow, a < b gives SF = 1; with overflow the sense of SF reverses, so SF ^ OF correctly tests a < b in all cases. Unsigned tests use CF and ZF. Machine code does not associate a 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, in 1, 2, or 4 bytes. A second method gives a 4-byte absolute address. The PC-relative value 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 be relocated without altering the encoded offsets (important 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 cannot predict. Here rep acts as a no-op; it 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 is easier to relate to the source than the 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 a penalty on the order of 15 to 30 cycles. A conditional move has no control dependence, so the processor need not predict.

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 (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: evaluate both then-expr and else-expr, then if (!t) v = ve.

Conditional moves are invalid when an evaluated branch could cause an error or side effect that must not occur, since both branches are always evaluated. Example: xp ? *xp : 0 cannot use a conditional move, because it would dereference a possibly null xp. gcc uses conditional moves only when both expressions are cheap (e.g. 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 to:

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

While. Two strategies. 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 is defined to behave as init; while (test) { body; update; }, then translated 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 the computed goto (goto *jt[index]) and code-location pointers (&&label) as C extensions to express this.

The compiler shifts the index into a 0-based range (e.g. 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 (in .rodata, .aligned) lists a .quad per index: duplicate cases share a label, missing cases point to the default label, and fall-through is implemented by omitting 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 in P on return), passing data (arguments and return value), and allocating/deallocating 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; %rsp points to the top element. Space is allocated by decrementing %rsp and freed by incrementing it.

General frame structure (top to bottom in memory, high to low address): the caller's frame ends with arguments 7..n passed to the callee and the return address (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: a leaf procedure whose locals fit in registers and which calls 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 are callq/retq in objdump output. call targets may be direct (label) or indirect (* operand).

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

3.7.3 Data Transfer

Up to six integral (integer or pointer) arguments 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 there are too few registers, 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, %r12–%r15. A callee that uses one must preserve it (leave it unchanged, or push on entry and pop before return), so the caller sees the original value on return.
• 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 callee-saved registers, and locals; 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 (L = sizeof(T)) and introduces A as a pointer to the start, value xA. Element i is at xA + L·i. The scaled-index addressing modes (scale 1, 2, 4, 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 pointer p of type *T, p + i yields the address p + L·i. & produces addresses (often via leaq); pointer difference within one array is divided by the element size, yielding a long index. Operations returning array values use data-size operations and registers (e.g. movl, %eax); operations returning pointers use 8-byte operations and registers (e.g. leaq, %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] is at

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

For int A[5][3], A[i][j] 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. Element access A[i][j] computes xA + 4(n·i + j), requiring an imulq to scale i by n (a runtime value) rather than the shift/add sequence used for fixed dimensions; this 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 like 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; };

offsets are i=0, j=4, a=8, p=16, total 24 bytes. &(r->a[i]) for r in %rdi, i in %rsi: 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. Uses: saving space when fields are mutually exclusive (often paired with an enumerated tag field in an enclosing struct), and reinterpreting bit patterns of one type as another (e.g. reading a double's bits as unsigned long). When combining types of different sizes, byte ordering matters: on a little-endian x86-64, the first 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 (1 for char, 2 for short, 4 for int/float, 8 for long/double/pointer). 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, giving the struct an overall alignment equal to its largest field's, and pads the end so that 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 to 12. For struct S2 { int i; int j; char c; }, 3 bytes of trailing padding size it to 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. Consequently, memory allocators (malloc, etc.) return 16-byte-aligned blocks and most stack frames are 16-byte aligned. AVX removes this 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: an address of an object of its type; NULL (0) points nowhere.
• & creates a pointer, applicable to any lvalue; it often compiles to leaq.
• * dereferences, compiling 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; (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: set breakpoints (function or address), single-step (stepi, nexti), continue or run to return (continue, finish), examine registers and memory in various formats (print, x), and disassemble (disas). Running objdump -d first to obtain the disassembly is helpful.

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 (buffer overflow) can corrupt this saved state; a corrupted return address makes ret jump to an unexpected location. gets (and strcpy, strcat, 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, e.g. to spawn a shell. The 1988 Internet worm used a buffer overflow of 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, e.g. through alloca), so attackers cannot rely on a fixed stack address; more broadly, ASLR 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 checks the canary against its stored value (read from a read-only segment via %fs:40); 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 they are not complete safeguards.

3.10.5 Supporting Variable-Size Stack Frames

Some functions need a frame whose size is not known at compile time (a call to alloca, or a local variable-size array). x86-64 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 is allocated below. The leave instruction (equivalent to movq %rbp,%rsp; popq %rbp) restores %rsp and %rbp on exit. x86-64 uses a frame pointer only when the frame is variable-size; earlier IA32 code used it for every call. Mixing frame-pointer and non-frame-pointer code is fine 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: MM (64-bit), XMM (128-bit), YMM (256-bit) registers. From SSE2 (Pentium 4, 2000), scalar instructions operate on single float/double values in the low bytes of XMM/YMM registers; all x86-64 processors support at least SSE2. The presentation uses AVX2 (Haswell, 2013; gcc -mavx2).

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

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 alignment-tolerant (though alignment is recommended). gcc uses vmovss/vmovsd for memory transfers and vmovaps/vmovapd for register-to-register copies (the "a" is "aligned"; 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 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, vmovddup then vcvtpd2psx. The single-instruction equivalents (vcvtss2sd, vcvtsd2ss) are not used, for unclear reasons.

3.11.2 Floating-Point Code in Procedures

• Up to eight floating-point arguments pass in %xmm0–%xmm7, in order; further ones 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/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 is in %edi, y in %xmm0, 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 cannot take immediate operands, so the compiler stores constants in memory (labeled, e.g. .LC2) and reads them. 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, then high-order, 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); for scalar code only the low bytes matter. They implement operations like absolute value (mask off the sign bit with vandpd) and negation (flip 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; 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, CF for S2 < S1).

Ordering 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 (through packed operations) for data parallelism. The most reliable way to exploit that parallelism at present is gcc's vector extensions.

3.12 Summary

Machine-level programming exposes what the C abstraction hides: minimal distinction between data types, a program expressed as a sequence of single-operation instructions, and directly visible processor state (registers, the run-time stack, condition codes). The compiler composes low-level operations to realize data structures and control constructs. Understanding this level clarifies compiler optimization (Chapter 5) and the placement of data across the stack, heap, and global regions (Chapter 9), and it exposes security vulnerabilities such as buffer overflow.