From source code to a running binary

The previous chapter compared compiling, interpreting and JIT compilation. This one opens the compiler itself. Running cc -O2 prog.c looks like a single step, but a C toolchain is a pipeline of separate programs, each turning one representation into the next:

1. the preprocessor expands #include and macros;
2. the compiler proper turns C into assembly, through tokens, a syntax tree and an intermediate representation, optimizing along the way;
3. the assembler turns assembly into an object file;
4. the linker combines object files and libraries into an executable.

Steps 3 and 4 are covered at the assembly level, in assembler, linker and loader, and the file they produce in executable files. This chapter follows steps 1 and 2, on one small function, with the real output of clang at each stage:

#define SQUARE(x) ((x) * (x))

int square_sum(int a, int b) {
    return SQUARE(a) + SQUARE(b);
}

1. The preprocessor

Before the compiler sees anything, the preprocessor handles every line that starts with #. It pastes in the files named by #include, keeps or drops code according to #if/#ifdef, and expands macros. It works on text: it knows nothing about C types or functions. clang -E shows its output:

int square_sum(int a, int b) {
    return ((a) * (a)) + ((b) * (b));
}

SQUARE(a) became ((a) * (a)), a pure text substitution, like the assembler's macros. The extra parentheses matter: without them, SQUARE(a + 1) would expand to a + 1 * a + 1. And because it's textual, SQUARE(i++) would increment i twice. In real programs, #include <stdio.h> alone pastes in hundreds of lines of declarations.

2. Lexing: characters into tokens

The lexer cuts the text into tokens, the words of the language: keywords, identifiers, numbers, operators, punctuation. Whitespace and comments disappear. clang -Xclang -dump-tokens lists them:

int 'int'                 Loc=<sq.c:3:1>
identifier 'square_sum'   Loc=<sq.c:3:5>
l_paren '('               Loc=<sq.c:3:15>
int 'int'                 Loc=<sq.c:3:16>
identifier 'a'            Loc=<sq.c:3:20>
comma ','                 Loc=<sq.c:3:21>
…
return 'return'           Loc=<sq.c:4:5>
l_paren '('               Loc=<sq.c:4:12 <Spelling=sq.c:1:19>>

Every token remembers where it came from — even the ( that came from the macro on line 1 — which is how error messages can point to the right line and column.

3. Parsing: tokens into a syntax tree

The parser checks the tokens against the grammar of C and builds an abstract syntax tree (AST): the structure of the program, with the punctuation gone. clang -Xclang -ast-dump, lightly trimmed:

FunctionDecl square_sum 'int (int, int)'
|-ParmVarDecl a 'int'
|-ParmVarDecl b 'int'
`-CompoundStmt
  `-ReturnStmt
    `-BinaryOperator 'int' '+'
      |-BinaryOperator 'int' '*'
      | |-ImplicitCastExpr 'int' <LValueToRValue>
      | | `-DeclRefExpr 'a'
      | `-ImplicitCastExpr 'int' <LValueToRValue>
      |   `-DeclRefExpr 'a'
      `-BinaryOperator 'int' '*'
        |-ImplicitCastExpr 'int' <LValueToRValue>
        | `-DeclRefExpr 'b'
        `-ImplicitCastExpr 'int' <LValueToRValue>
          `-DeclRefExpr 'b'

Operator precedence is now just the shape of the tree: the two * sit below the +. Semantic analysis runs on this tree. It resolves every name to its declaration, checks types, and inserts the implicit conversions C requires, like the LValueToRValue casts that mean "read the value stored in this variable". Most compile errors — undeclared names, type mismatches — come from this stage.

4. The intermediate representation

The tree is then lowered to an intermediate representation (IR): a simple, machine-independent instruction set. Clang produces LLVM IR. At -O0, it translates each C construct literally:

define i32 @square_sum(i32 %0, i32 %1) {
  %3 = alloca i32, align 4          ; stack slot for a
  %4 = alloca i32, align 4          ; stack slot for b
  store i32 %0, ptr %3, align 4
  store i32 %1, ptr %4, align 4
  %5 = load i32, ptr %3, align 4    ; read a
  %6 = load i32, ptr %3, align 4    ; read a again
  %7 = mul nsw i32 %5, %6
  %8 = load i32, ptr %4, align 4
  %9 = load i32, ptr %4, align 4
  %10 = mul nsw i32 %8, %9
  %11 = add nsw i32 %7, %10
  ret i32 %11
}

IR looks like assembly for an ideal machine: unlimited virtual registers (%5, %6…), each assigned exactly once, a form called SSA (static single assignment). That form makes data flow explicit, which is what optimizers need.

nsw means "no signed wrap": signed overflow is undefined behavior in C, so the compiler is allowed to assume it never happens, and optimizations rely on that assumption. That's why a signed integer overflow in C doesn't just "wrap around". The compiler may have transformed the code in ways that assume it can't happen at all.

5. Optimization

The optimizer runs dozens of passes over the IR, each a small transformation: promote stack variables to registers, remove duplicate computations and dead code, inline small functions, unroll loops, replace divisions by constants. At -O2, the same function becomes:

define i32 @square_sum(i32 %0, i32 %1) {
  %3 = mul nsw i32 %0, %0
  %4 = mul nsw i32 %1, %1
  %5 = add nuw nsw i32 %4, %3
  ret i32 %5
}

The stack slots, stores and repeated loads are gone. And the optimizer proved that the sum of two squares, assuming no overflow, can't be negative, so the add gained a nuw (no unsigned wrap) flag, a fact it can use later.

Because every language front end produces the same IR, the same optimizer and back ends serve C, C++, Rust, Swift and others. That separation — front end, middle end, back end — is why a new language or a new CPU needs only one new piece.

6. Code generation

The back end turns the IR into the target's machine instructions. It selects instructions, allocates the unlimited virtual registers onto the CPU's 16, spilling to the stack when they run out, and schedules instructions for the pipeline. The output is assembly. For x86-64, -O0 against -O2:

; -O0                               ; -O2
square_sum:                         square_sum:
    push rbp                            imul edi, edi
    mov  rbp, rsp                       imul esi, esi
    mov  DWORD PTR [rbp-4], edi         lea  eax, [rsi+rdi]
    mov  DWORD PTR [rbp-8], esi         ret
    mov  eax, DWORD PTR [rbp-4]
    imul eax, DWORD PTR [rbp-4]
    mov  ecx, DWORD PTR [rbp-8]
    imul ecx, DWORD PTR [rbp-8]
    add  eax, ecx
    pop  rbp
    ret

The optimized version never touches memory: the arguments arrive in edi and esi as the calling convention says, and the final addition is done by lea, which adds two registers into a third in one instruction.

The simulator's built-in compiler works like -O0: every variable gets a stack slot, so each C line maps visibly onto its instructions. Zoom in from the C level to compare:

It returns 25 after 27 instructions.

The driver ties it together

clang and gcc are drivers: small programs that run the real stages with the right options. clang -### prints what it would run without running it: the compiler proper (clang -cc1 … -O2 -emit-obj), which here also performs the assembler step internally, then the system linker. Each stage has a flag to stop there, which is how you inspect a build:

For reverse engineering, this pipeline explains what's left in a binary. Macros, comments, local variable names and the syntax tree are all gone. What survives is the optimized result of step 6 — plus, unless the binary is stripped, the symbol names, and debug information if it was built with -g.

Takeaways

• A C build is a pipeline: preprocessor → compiler (lexer, parser, semantic analysis, IR, optimizer, code generator) → assembler → linker.
• The preprocessor substitutes text (#include, macros) without knowing C.
• The lexer produces tokens, the parser builds an AST, and semantic analysis resolves names, checks types and adds implicit conversions.
• The IR (LLVM IR in SSA form) is where optimization happens, shared by every language and every target. nsw shows how undefined behavior licenses optimizations.
• The back end selects instructions, allocates registers and schedules code. -O0 keeps a readable, line-by-line mapping; -O2 turns 11 instructions into 4.