Lecture 4: Assembly Language and Computer Architecture

What this lecture covers

This lecture explains why performance engineers need to read assembly: it reveals exactly what the compiler did and did not do, helps spot compiler bugs, lets you write assembly by hand when needed, and lets you reverse-engineer code you don't have source for. Charles Leiserson walks through the compilation pipeline from source to executable, then covers x86-64 registers, instructions, data types, and addressing modes, before moving into floating-point and vector hardware and a high-level look at pipelined, superscalar, out-of-order processor design.

After watching, you should be able to explain the four stages of compilation, read simple x86-64 assembly with reference to a manual, recognize common compiler idioms (like using XOR to zero a register), and describe why hazards like data dependencies and branch mispredictions cause pipeline stalls.

Key ideas

• Four compilation stages: preprocessing (textual substitution), compiling (source to assembly), assembling (assembly to object/machine code), and linking (combining object files into an executable).
• Why read assembly: to see what optimizations the compiler applied or missed, to catch compiler bugs, to hand-write performance-critical code, and to reverse-engineer code without source.
• x86-64 registers and instructions: general-purpose registers alias smaller and larger widths for historical reasons; instructions have an opcode plus up to a few operands, with AT&T syntax (used by the course's tools) putting the destination last, unlike Intel syntax.
• Addressing modes: immediate, register, and direct memory addressing, plus indirect modes (register indirect, indexed, instruction-pointer relative, and the general base-index-scale-displacement form used for stack and array access).
• SIMD vector hardware: SSE, AVX, and AVX2 registers hold multiple data "lanes" that execute the same operation in lockstep, giving one instruction to operate on several values at once, with alignment affecting performance.
• Pipeline hazards: structural hazards (contention for a functional unit), data hazards (true, anti-, and output dependencies between instructions), and control hazards (branches whose direction isn't known yet) can stall an in-order pipeline.
• Superscalar and out-of-order execution: modern processors like Haswell issue multiple micro-ops per cycle, use bypassing to skip the register file for chained results, and use techniques like register renaming to remove false dependencies.
• Branch prediction: processors speculatively execute the predicted branch path; a misprediction on Haswell costs roughly 15-20 cycles to undo.

Walkthrough

From source to executable (1:02)

Leiserson traces a program through four stages: clang -E shows the preprocessed output after macro expansion, clang -S produces human-readable assembly, assembling turns that into an object file, and linking (via ld) combines object files into a final executable. He notes that assembly and machine code correspond closely, almost one-to-one, unlike the much larger gap between C and machine code.

Why performance engineers read assembly (6:09)

Using objdump to disassemble compiled binaries, the lecture gives four reasons to read assembly: seeing exactly what the compiler did, catching compiler bugs (which can appear only at higher optimization levels), writing assembly directly when the compiler can't produce the desired code, and reverse-engineering unavailable source, illustrated by the earlier matrix multiplication example where the team inferred what Intel's library was doing without its source.

The x86-64 instruction set architecture (13:12)

The lecture covers the four core ISA concepts: registers (general-purpose, RFLAGS, the instruction pointer, and the SSE/AVX vector registers), instruction format (opcode plus a small operand list, with AT&T syntax putting the destination last), common opcodes (move, conditional move, sign extension, arithmetic, bitwise logic, jumps, and subroutine calls), and opcode suffixes that indicate data type or a jump condition (such as movq for a 64-bit "quad word").

Data types and addressing modes (27:27)

Assembly-level data type suffixes (byte, word, double word, quad word, and floating-point precisions) are mapped to C types, along with zero- versus sign-extension behavior when moving between register widths. The lecture then details direct addressing (immediate constants, register values, direct memory) and indirect addressing (register indirect, indexed, instruction-pointer relative, and the general base-index-scale-displacement form typically used for stack frames), emphasizing that memory access, at roughly a couple hundred cycles when not cached, is far more expensive than a register access.

Compiler idioms in assembly (42:37)

Several recognizable patterns are explained: xor %rax, %rax zeroing a register more cheaply than loading a zero constant, test computing a bitwise AND to check a value against zero without discarding the flags register, and sequences of no-op instructions that compilers insert purely for code alignment, such as starting a function at a cache line boundary.

Floating-point and vector hardware (48:43)

The lecture compares the SSE/AVX scalar and vector floating-point instructions (generally preferred by compilers) against the older x87 instruction set. Vector ("packed") instructions apply one operation across multiple lanes in lockstep, and the lecture explains how aligned vector operands generally perform better than unaligned ones, and how AVX and AVX2 extend SSE's register width and allow three-operand instructions.

Pipelining, hazards, and instruction-level parallelism (56:50)

Starting from the classic five-stage pipeline (fetch, decode, execute, memory, write-back), the lecture explains that real processors like Haswell have 14 to 19 pipeline stages. It defines three hazard types that can stall a pipeline: structural hazards (contention for a functional unit), data hazards (true, anti-, and output dependencies between instructions), and control hazards (branch outcomes not yet known). It describes techniques processors use to recover throughput: bypassing (feeding a result directly to a dependent instruction instead of round-tripping through the register file), superscalar issuing of multiple micro-ops per cycle, register renaming to eliminate false dependencies, and speculative execution with branch prediction, noting that a misprediction on Haswell costs about 15 to 20 cycles.

Before you watch

• Watch Lectures 1 through 3 first for context on why low-level performance work matters and for the bit-manipulation vocabulary reused here.
• Basic familiarity with how compilers work (source, object files, linking) and with binary/hex number representation is assumed.
• Some prior exposure to processor pipelining (such as an introductory computer architecture course) helps but the lecture reviews the basics.

Check your understanding

1. What are the four stages of compilation, and what does each one produce?
2. Give two concrete reasons a performance engineer would want to read a program's compiled assembly.
3. Why does xor %rax, %rax zero a register more efficiently than loading an explicit zero constant?
4. What is the difference between a true dependence, an anti-dependence, and an output dependence between two instructions?
5. Why does a mispredicted branch cost extra cycles on a pipelined processor, and how does branch prediction try to reduce that cost?