Lecture 5: C to Assembly

What this lecture covers

This lecture answers a practical question: what does a compiler actually do to turn C source into x86-64 assembly? Rather than treating the compiler as a black box, it walks through the intermediate stage clang uses, LLVM IR, and shows how C constructs (straight-line code, functions, conditionals, loops) map onto it, and then how LLVM IR maps onto assembly. It follows the previous lecture's introduction to x86-64 assembly in MIT's performance engineering course.

After watching, you should be able to read a short LLVM IR dump, recognize basic blocks and control-flow edges in a control flow graph, explain why a phi instruction exists, and trace how a recursive C function like fib becomes assembly that manages the stack, registers and calling convention.

Key ideas

• LLVM IR: an intermediate representation that looks like a simplified assembly language with an infinite number of named registers (%0, %1, ...) and explicit types.
• Static single assignment (SSA): in LLVM IR, each register is assigned a value by at most one instruction, which makes the code easier to analyze.
• Basic block: a straight-line sequence of instructions entered only at the top and exited only at the bottom; functions are modeled as a control flow graph of basic blocks connected by branch edges.
• phi instruction: a bookkeeping construct, not a real machine instruction, that picks a register's value based on which predecessor block control arrived from — needed because SSA can't otherwise represent a variable like a loop induction variable that changes across iterations.
• getelementptr: the LLVM IR instruction that computes a memory address from a base pointer and a sequence of indices, used for array and struct access.
• Calling convention: the Linux x86-64 convention that fixes which registers hold arguments and return values, which registers are caller-saved versus callee-saved, and how stack frames are laid out using rbp and rsp.
• Function prologue/epilogue: the instructions a function runs on entry (saving the caller's base pointer, setting up its own frame) and on exit (restoring saved registers and returning).

Walkthrough

Why look at assembly at all (1:01)

The lecture opens by reviewing why assembly matters for performance work: it exposes implicit costs like type casts, register-versus-memory choices, and what the compiler did or didn't optimize away. It can also expose bugs that appear only at high optimization levels, and it enables reverse-engineering code from a binary alone.

Compiler pipeline and the LLVM IR primer (7:03)

The compiler moves from C through preprocessing, to LLVM IR, and finally to assembly. The lecture focuses on the last two stages. A short primer introduces LLVM IR: it organizes code into functions and basic blocks, uses named registers similar to C variables, has an explicit type system (i64, i1, pointers, arrays, structs, vectors), and has a much smaller instruction set than x86.

Straight-line code and functions (19:17)

Simple sequences of C operations translate directly into sequences of LLVM IR instructions, with arguments evaluated before the operations that use them. Accessing array elements requires a getelementptr instruction to compute an address followed by a load. C functions and their parameter lists map onto LLVM IR functions with a similar structure, and return statements map onto LLVM ret instructions.

Basic blocks and conditionals (26:24)

Code inside a function is split into basic blocks wherever control can branch. An if-else in C produces a conditional branch (br) instruction that tests a Boolean predicate and jumps to one of two labeled blocks, forming a diamond-shaped pattern in the control flow graph. Unconditional branches merge the diamond back together.

Loops and the phi instruction (34:29)

A C loop becomes a literal loop (a back edge) in the control flow graph, split into a loop body and loop control (initialization, condition check, increment). Because SSA requires each register to be defined once, but an induction variable changes value each iteration, LLVM IR uses a phi instruction at the top of the loop block: it selects zero on entry from outside the loop, or the incremented value on entry from the back edge. The instruction is a representational trick and doesn't correspond to any assembly instruction.

Attributes and stack layout (43:35)

LLVM IR instructions and types can carry attributes such as alignment hints or noalias/readonly, coming either from source-level keywords like restrict and const or from compiler analysis. The lecture then turns to how a running program's virtual memory is organized into segments — stack, heap, BSS, data and text — and how assembler directives like .text, .data, .global and .align place content into those segments.

The calling convention (56:40)

Because functions from different source files and libraries must interoperate, they all follow the same Linux x86-64 calling convention. The stack is divided into per-call frames tracked by rbp and rsp. Some registers (rbx, rbp, r12-r15) are callee-saved and the rest are caller-saved, splitting the responsibility for preserving register state across a call. The lecture works through how one function passes arguments to another via a linkage block and how call/ret manage the return address.

Case study: compiling fib (1:07:47)

The lecture finishes by compiling a simple recursive Fibonacci function through both steps: fib.c to fib.ll (LLVM IR with three basic blocks for the base case and recursive case), and then fib.ll to assembly. It reads the resulting assembly line by line, identifying the function prologue, the callee-saved register pushes, the cmp/jge pair implementing the conditional, the lea instruction used for cheap arithmetic, the two recursive calls to fib, and the epilogue that restores registers before returning.

Before you watch

• Watch the previous lecture on x86-64 assembly basics (registers, instructions, addressing modes) in this course, since this lecture builds directly on it.
• Be comfortable reading simple C functions with conditionals, loops and recursion.
• Basic familiarity with what a stack and stack pointer are will help the calling-convention section make sense.

Check your understanding

1. Why does LLVM IR need a phi instruction for loop induction variables, and why doesn't that instruction appear in the final assembly?
2. What is the difference between a caller-saved and a callee-saved register in the Linux x86-64 calling convention, and why does the convention use both?
3. Walk through what a getelementptr instruction computes and why a memory load is a separate instruction afterward.
4. In the fib assembly example, why does the compiler save the result of the first recursive call into r14 before making the second call?
5. What does it mean for LLVM IR to obey the static single assignment invariant, and how does that help a compiler analyze code?