How a Compiler Actually Works

16.0 What this chapter gives you#

1. You will be able to name every stage between the text you type and the electricity that runs, in the right order, and say what each one does.
2. You will be able to take one five-word C function and follow it through preprocessing, tokens, tree, symbol table, intermediate code, optimization, assembly, object file, executable and running process.
3. You will be able to read real assembly output and explain every single line.
4. You will be able to say why compilers use an intermediate language in the middle instead of going straight to machine instructions.
5. You will be able to explain why -O2 turned our program into three instructions, and why that is legal.
6. You will be able to explain what a linker does, why “undefined reference” happens, and why the order of libraries on the command line matters.
7. You will be able to explain what happens at the moment you press Enter on a program, including the dynamic linker, the GOT and the PLT.
8. You will be able to compare compiled, bytecode and interpreted execution with real numbers, and explain why JavaScript got fast.
9. You will be able to explain the bootstrap problem and Ken Thompson’s 1984 trusting-trust attack to somebody who has never programmed.
10. You will be able to run the commands yourself and see the same output.

Our one running example, for the whole chapter, is this file. We will call it add.c. Everything below is that file at a different moment of its life.

int add(int a, int b) { return a + b; }
int main(void) { return add(2, 3); }

Every command shown was run on Ubuntu 24.04 on an x86-64 machine, with GCC 13.3.0 and Clang 18.1.3. The outputs pasted here are the real outputs.

16.1 The whole pipeline in one view#

PLAIN16.1.1 in simple words#

1. A computer chip does not understand the words you type. It understands numbers, and only a small fixed set of them.
2. A compiler is a program that reads your text and writes those numbers.
3. It does not do this in one jump. It does it in a chain of small steps.
4. Each step takes one shape of information and turns it into a simpler shape.
5. First the text is cleaned up and glued together with other files.
6. Then it is chopped into small pieces, like words in a sentence.
7. Then those pieces are arranged into a tree, the way a sentence has a subject and an object.
8. Then the meaning is checked: do these names exist, do the types match.
9. Then it is rewritten in a simple made-up language that is easy to improve.
10. Then it is improved: shortened, simplified, things that do nothing removed.
11. Then it is written as instructions for one particular chip.
12. Then those instructions become raw bytes in a file.
13. Then several such files are glued into one program.
14. Then the operating system loads it into memory and starts it.

PLAIN16.1.2 a picture in your head#

1. Think of a factory line that turns a handwritten recipe into a packed meal.
2. Station one gathers all the recipe pages that the main page refers to.
3. Station two reads the pages aloud, one word at a time.
4. Station three works out the grammar: which words are the ingredients, which are the actions, what belongs inside what.
5. Station four checks it makes sense: you cannot fry a number.
6. Station five rewrites the whole thing as a plain numbered work order.
7. Station six removes wasted steps: no need to boil water you never use.
8. Station seven writes the work order in the exact words this kitchen’s machines accept.
9. Station eight packs it in a box. Station nine puts several boxes in a crate.
10. Station ten unpacks the crate onto a table and starts cooking.

Where this comparison breaks: a factory line moves one item forward and never looks back. A real compiler often loops. The optimizer runs dozens of passes over the same code, some of them many times, and a later pass can undo an earlier one. Also, several stations can be the same piece of code in memory, not separate programs. The clean chain is a teaching model, not the shape of the source code inside GCC or Clang.

PLAIN16.1.3 a worked example#

Here is the chain, drawn for add.c.

  add.c   (the text you typed)
    |
    v
 [ preprocessor ]  glue in #include, expand #define
    |
    v
 [ lexer ]         text -> tokens: int, add, (, int, a, ...
    |
    v
 [ parser ]        tokens -> a tree of the program
    |
    v
 [ semantic ]      names, scopes, types, symbol table
    |
    v
 [ IR builder ]    tree -> simple three-address code
    |
    v
 [ optimizer ]     fold, propagate, inline, delete
    |
    v
 [ code generator ] IR -> assembly text for one CPU
    |
    v
 [ assembler ]     assembly -> object file add.o (bytes)
    |
    v
 [ linker ]        add.o + C library -> one executable
    |
    v
 [ loader ]        exec: map into memory, bind symbols
    |
    v
  a running process

One line for each stage, for add.c:

1. Preprocessor: nothing to do here, there are no # lines. Output is the same two lines of text.
2. Lexer: produces 32 tokens plus an end marker.
3. Parser: produces a tree with two function declarations at the top.
4. Semantic analysis: records that add takes two int and returns int, and that the call in main matches.
5. IR: produces _3 = a + b; return _3; for add.
6. Optimizer at -O2: notices add(2,3) is always 5.
7. Code generator: writes leal (%rdi,%rsi), %eax for add.
8. Assembler: writes the bytes 8d 04 37 for that instruction.
9. Linker: fills in the address of add inside main’s call instruction.
10. Loader: maps the file into memory and jumps to the entry point.
11. The process returns 5. echo $? prints 5.

PLAIN16.1.4 what is really happening inside#

1. Most of these “stages” are functions inside one program, passing data structures to each other, not separate processes.
2. But some really are separate programs. On Linux, gcc is only a driver: it runs other programs and passes files between them.
3. Running gcc -v add.c shows the driver’s real children. The three that matter are cc1, as and collect2.
4. cc1 is the actual C compiler. It reads add.c and writes assembly text to a temporary file.
5. as is the assembler. It reads that text and writes a temporary .o file.
6. collect2 is a wrapper around ld, the linker. It writes the executable.
7. So on a normal Linux box, compiling one C file starts three extra programs.
8. Each stage narrows what is possible. After lexing, you can no longer ask about spaces. After parsing, you can no longer ask about brackets. After code generation, you can no longer ask about variable names.
9. That narrowing is the point. Every stage throws away information the next stage does not need, so the next stage can be simpler.

TECHNICAL16.1.5 the engineer’s version#

1. The classical decomposition is front end, middle end, back end. The front end is language specific, the back end is target specific, and the middle end is neither.
2. The front end covers preprocessing, lexical analysis, syntax analysis and semantic analysis, and emits an intermediate representation (IR).
3. The middle end runs target-independent optimization passes on the IR.
4. The back end performs instruction selection, instruction scheduling and register allocation, and emits assembly or machine code directly.
5. The canonical reference is Compilers: Principles, Techniques, and Tools by Alfred Aho, Ravi Sethi and Jeffrey Ullman, 1986, known as the Dragon Book. The 2006 second edition adds Monica Lam.
6. The first true optimizing compiler was the IBM FORTRAN compiler for the IBM 704, delivered in April 1957 under John Backus. It took about 18 staff-years and its output had to beat hand-written assembly to be accepted.
7. Grace Hopper’s A-0 system of 1952 predates it but was closer to a linking loader than to a modern compiler.
8. GCC 1.0 was released by Richard Stallman in March 1987. LLVM began as Chris Lattner’s work at the University of Illinois, with LLVM 1.0 in 2003.

Observing the pipeline with real commands:

gcc -v add.c -o prog      # show cc1, as, collect2
gcc -E add.c              # stop after the preprocessor
clang -Xclang -dump-tokens -fsyntax-only add.c
clang -Xclang -ast-dump  -fsyntax-only add.c
clang -S -emit-llvm add.c -o add.ll
gcc -S add.c -o add.s     # stop after code generation
gcc -c add.c -o add.o     # stop after the assembler

WORDS16.1.6 remember these#

Compiler — a program that turns your text into machine numbers — a translator from a source language to a target language, usually with static checking. Pass — one walk over the program — a single traversal of the IR performing one analysis or transformation. Front end — the part that understands your language — lexing, parsing, semantic analysis, IR generation. Back end — the part that knows the chip — instruction selection, scheduling, register allocation, code emission. Driver — the program you actually type — gcc or clang, which orchestrates the real compiler, assembler and linker as child processes.

16.2 The preprocessor#

PLAIN16.2.1 in simple words#

1. Before the compiler looks at your program, another tool edits the text.
2. That tool is the preprocessor. It only understands lines starting #.
3. #include "file.h" means: delete this line and paste that whole file here.
4. #define TWO 2 means: everywhere the word TWO appears later, write 2.
5. #if and #ifdef mean: keep this block of text or throw it away.
6. That is all it does. It moves text around. It does not know what C is.
7. It does not know types. It does not know functions. It cannot count.
8. The compiler never sees your #include lines. It sees the result.

PLAIN16.2.2 a picture in your head#

1. Imagine a school essay where you are told to write see page 40 instead of copying a long definition.
2. Before the teacher marks it, a helper goes through and physically pastes page 40 in place of every see page 40.
3. The helper also has a list of shorthands: wherever you wrote WHO, write World Health Organization.
4. The helper does not read for meaning. If you wrote see page 40 inside a joke, page 40 gets pasted into the joke.
5. The teacher then marks one long essay with no shortcuts left in it.

Where this comparison breaks: the helper in this story is careful. The C preprocessor is not. It will happily paste text that produces nonsense, and it will report the error at the pasted line, not at your line. Macro expansion also happens repeatedly until nothing changes, which no human helper would do.

PLAIN16.2.3 a worked example#

Split our example into a header and a source file.

/* addh.h */
#ifndef ADD_H
#define ADD_H
#define TWO 2
#define THREE 3
int add(int a, int b);
#endif

/* main2.c */
#include "addh.h"
int main(void) { return add(TWO, THREE); }

Now run gcc -E main2.c. The real tail of the output is:

# 1 "main2.c"
# 1 "addh.h" 1

int add(int a, int b);
# 2 "main2.c" 2
int main(void) { return add(2, 3); }

1. The #include line has gone. The declaration from the header sits in its place.
2. TWO and THREE have become 2 and 3.
3. The #ifndef guard lines have gone. They produced no text.
4. The lines beginning # with numbers are line markers. They tell the compiler “the next line really came from file X, line N”, so error messages point at your file and not at the merged text.
5. The blank lines are the preprocessor keeping line numbers lined up.

Now a real size measurement, on the same machine:

$ printf '#include <stdio.h>\nint main(void){return 0;}\n' > hello.c
$ wc -l < hello.c
2
$ gcc -E hello.c | wc -l
815
$ gcc -E hello.c | wc -c
21292

1. Two lines of yours became 815 lines and about 21 kB of text.
2. It pulled in 29 distinct files.
3. In C++ it is far worse. #include <iostream> with GCC 13.3 on this machine expanded to 36,584 lines.

PLAIN16.2.4 what is really happening inside#

1. The preprocessor runs in phases defined by the C standard. The important ones, in order, are: join lines ending in a backslash, replace comments with a single space, then execute the # directives, then join adjacent string literals.
2. The header guard trick, #ifndef ADD_H / #define ADD_H / #endif, exists because a header may be included twice through different paths.
3. Without a guard, the second include pastes the same declarations again, which is an error for anything defined rather than merely declared.
4. With the guard, the second visit finds ADD_H already defined and skips the whole file, producing no text.
5. #pragma once does the same job in one line. It is not in the C or C++ standard, but every major compiler supports it. That makes it a convention, not a standard.
6. Conditional compilation, #if defined(_WIN32), is how one source file serves several operating systems. The text for the other systems never reaches the compiler at all.
7. Macros are textual, so they have famous traps. #define SQ(x) x*x then SQ(1+2) becomes 1+2*1+2, which is 5, not 9. Parentheses fix it: #define SQ(x) ((x)*(x)).

TECHNICAL16.2.5 the engineer’s version#

1. The C preprocessor is specified in the C standard, clause 6.10. It is a standard, not an implementation detail.
2. Translation phases 1 to 4 of the standard cover trigraph mapping, line splicing, comment removal and directive execution.
3. Predefined macros include __FILE__, __LINE__, __DATE__, __TIME__, __STDC__ and __STDC_VERSION__. __STDC_VERSION__ is 199901L for C99, 201112L for C11, 201710L for C17 and 202311L for C23.
4. #include <x.h> searches the system include path. #include "x.h" searches the current directory first, then the system path. gcc -I dir prepends a directory. gcc -E -v prints the search list actually used.
5. Macro expansion is not recursive on the macro currently being expanded, which is what stops #define X X from looping forever.
6. # in a function-like macro stringizes its argument. ## pastes tokens together. Both are standard.
7. Preprocessing cost is real. Header expansion is the main reason C++ builds are slow, and is the motivation for precompiled headers and for C++20 modules, standardized in ISO C++20 and still only partially implemented in toolchains as of 2026.

The honest version: saying “the preprocessor is a separate program” is a useful lie. It once was, as /lib/cpp. In GCC today it is a library linked into cc1, and Clang implements it as a token source feeding the lexer, so text is never fully materialized. You get the same answer either way, which is why the lie is safe.

WORDS16.2.6 remember these#

Preprocessor — the text editor that runs before the compiler — the phase that executes # directives, per C standard clause 6.10. Macro — a shorthand replaced by text — an object-like or function-like replacement list expanded during translation phase 4. Header guard — a trick to stop a file being pasted twice — an #ifndef / #define / #endif idiom giving idempotent inclusion. Translation unit — one source file plus everything it pasted in — the input the compiler proper actually sees. Conditional compilation — keeping or dropping blocks of text — #if, #ifdef, #elif, #else, #endif evaluated on preprocessing tokens.

16.3 Lexing: characters into tokens#

PLAIN16.3.1 in simple words#

1. After the text is glued together, it is still just a row of characters.
2. The lexer reads that row left to right and groups characters into words.
3. Each word it produces is a token: a small labelled piece.
4. int becomes a keyword token. add becomes an identifier token. 2 becomes a number token. + becomes an operator token.
5. Spaces, tabs, newlines and comments produce no tokens at all. They only separate things.
6. The lexer does not care about order. + + + ) is fine by the lexer. It is the next stage that objects.
7. The lexer’s only real skill is to always take the longest match. In a+++b it produces a, ++, +, b, not a, +, +, +, b.

PLAIN16.3.2 a picture in your head#

1. Imagine a long strip of paper with no spaces: THECATSATONTHEMAT.
2. Your job is to cut it into words and label each one: noun, verb, article.
3. You have a list of legal words. You scan from the left, and at each point you take the longest legal word you can.
4. You never look ahead at the sentence’s meaning. You never ask if the sentence is sensible. You just cut and label.
5. You hand the next person a stack of labelled cards, in order.

Where this comparison breaks: English needs meaning to cut correctly. C is designed so that cutting never needs meaning. That was a deliberate language design decision, and languages that break it, such as C++ with its >> in nested templates, cause real trouble for their own compilers.

PLAIN16.3.3 a worked example#

This is the real token stream for our file, from clang -Xclang -dump-tokens -fsyntax-only add.c, trimmed to the token and the text:

int 'int'              identifier 'main'
identifier 'add'       l_paren '('
l_paren '('            void 'void'
int 'int'              r_paren ')'
identifier 'a'         l_brace '{'
comma ','              return 'return'
int 'int'              identifier 'add'
identifier 'b'         l_paren '('
r_paren ')'            numeric_constant '2'
l_brace '{'            comma ','
return 'return'        numeric_constant '3'
identifier 'a'         r_paren ')'
plus '+'               semi ';'
identifier 'b'         r_brace '}'
semi ';'               eof ''
r_brace '}'

1. Read the left column top to bottom, then the right column. That is the whole file: 32 tokens, then an end-of-file marker.
2. The keywords int, void and return get their own token kinds.
3. add, main, a and b are all identifier. The lexer does not know that add is a function and a is a parameter. It has no idea what they are.
4. 2 and 3 are numeric_constant. The text is kept, not the value. Working out that 2 means the number two happens later.
5. Every space and every newline vanished.
6. Clang also records the exact line and column of every token. That is why its error messages can point a caret at one character.

PLAIN16.3.4 what is really happening inside#

1. A lexer is a machine with a small memory: a finite automaton.
2. It has a current state, it reads one character, and that character plus the state decides the next state. That is all the memory it has.
3. Start in state “nothing”. See a letter, go to state “reading an identifier”. Keep reading letters and digits. See something else, stop, and emit an identifier token.
4. Start in state “nothing”. See a digit, go to state “reading a number”. Keep reading digits. Stop at the first non-digit.
5. Because the memory is one state and nothing else, a lexer cannot count. It cannot check that brackets match. That job belongs to the parser.
6. After building an identifier, the lexer looks the text up in a fixed table of keywords. If int is in the table, it is a keyword. If add is not, it is an identifier. This is the standard trick.
7. Handling comments, string literals with escapes, and numeric suffixes such as 10UL are all extra states in the same machine.

TECHNICAL16.3.5 the engineer’s version#

1. Lexical structure is specified with regular expressions. Regular expressions and finite automata describe exactly the same class of languages, a result from Stephen Kleene’s work in 1951 and 1956.
2. The standard mechanical route is: regular expression -> nondeterministic finite automaton (NFA) by Thompson’s construction, 1968 -> deterministic finite automaton (DFA) by subset construction -> minimized DFA -> a table.
3. That construction is why generated lexers are fast. Each input character costs one table lookup, so lexing is linear in the input size.
4. Lex was written by Mike Lesk and Eric Schmidt at Bell Labs, described in a 1975 technical report. Flex, the free rewrite, was written by Vern Paxson starting in 1987 and is what most Unix systems ship today.
5. The rules in a .l file are pattern-action pairs. Flex resolves conflicts by two fixed rules: longest match wins, and among equal-length matches, the rule written earliest wins.
6. Production compilers usually hand-write the lexer instead. Clang’s Lexer.cpp and GCC’s libcpp are hand-written, because hand-written code handles error recovery, source locations and preprocessor interaction better.
7. The maximal munch rule is in the C standard: the next token is the longest character sequence that could form one. It is why C++11 needed a special case so >> can close two templates.

WORDS16.3.6 remember these#

Token — one labelled word of the program — the smallest unit the parser consumes, carrying a kind, spelling and source location. Lexer — the tool that cuts text into tokens — the scanner implementing the lexical grammar, usually as a DFA. Regular expression — a pattern for matching text shapes — a formula denoting a regular language, equivalent in power to a finite automaton. Finite automaton — a machine whose whole memory is which state it is in — a five-tuple of states, alphabet, transition function, start state and accepting states. Maximal munch — always take the longest legal word — the longest-match rule mandated by the C and C++ lexical grammars.

16.4 Parsing: tokens into a tree#

PLAIN16.4.1 in simple words#

1. A row of tokens has no shape. return a + b ; is a flat list.
2. The parser gives it shape by building a tree.
3. In the tree, + sits above a and b, because + is the thing being done and a and b are the things it is done to.
4. return sits above the +, because returning is done to the result of the addition.
5. The tree is called an abstract syntax tree, or AST.
6. It is called abstract because the brackets and semicolons disappear. Their only job was to tell the parser the shape, and now the shape is the tree.
7. A syntax error is the parser reaching a token that cannot legally follow what it has already seen.
8. That is all a syntax error is. It is not about meaning. It is about shape.

PLAIN16.4.2 a picture in your head#

1. Think of the sentence “the cat sat on the mat”.
2. A flat list of six words tells you nothing about who did what.
3. A tree tells you: the action is “sat”, the doer is “the cat”, the place is “on the mat”.
4. Now a rule set: a sentence is a noun phrase followed by a verb phrase. A noun phrase is an article followed by a noun. Follow the rules and the tree assembles itself.
5. A syntax error is “the cat sat on the”: you have run out of sentence while a rule still needs a noun.

Where this comparison breaks: English is ambiguous, so the same sentence can have several correct trees. “I saw the man with the telescope” has two. Real programming language grammars are designed hard to avoid this, and where it creeps in, the language adds a written tie-breaking rule, such as C’s “an else belongs to the nearest unmatched if”.

PLAIN16.4.3 a worked example#

The rules of a language are written in Backus-Naur Form. Here is a tiny slice, enough for our function:

function     ::= type identifier "(" params ")" block
block        ::= "{" statement* "}"
statement    ::= "return" expression ";"
expression   ::= expression "+" term | term
term         ::= identifier | number | call
call         ::= identifier "(" arglist ")"

Read ::= as “is made of”, | as “or”, * as “zero or more”. Now the real AST for our file. This is a redrawing of the actual output of clang -Xclang -ast-dump -fsyntax-only add.c:

TranslationUnit
 |
 +- FunctionDecl  add : int (int, int)
 |   +- ParmVarDecl  a : int
 |   +- ParmVarDecl  b : int
 |   +- CompoundStmt
 |       +- ReturnStmt
 |           +- BinaryOperator '+' : int
 |               +- DeclRefExpr a : int
 |               +- DeclRefExpr b : int
 |
 +- FunctionDecl  main : int (void)
     +- CompoundStmt
         +- ReturnStmt
             +- CallExpr : int
                 +- DeclRefExpr add : int (int, int)
                 +- IntegerLiteral 2 : int
                 +- IntegerLiteral 3 : int

1. TranslationUnit is the whole file.
2. Under it are exactly two things, our two functions.
3. CompoundStmt is the { ... } block. The braces themselves are gone.
4. BinaryOperator '+' has two children. That is the whole meaning of a + b.
5. CallExpr has three children: what to call, then each argument in order.
6. The semicolons are gone. The parentheses are gone. Nothing is lost, because the tree already says what they said.

And a real syntax error, from gcc -c synerr.c:

synerr.c:1:36: error: expected expression before ';' token
    1 | int add(int a, int b) { return a + ; }
      |                                    ^

The parser had read a and +, so its rule demanded another expression. It got ;. No rule allows that, so it stopped and reported the column.

PLAIN16.4.4 what is really happening inside#

1. There are two main families of parser: top-down and bottom-up.
2. Top-down starts from “this should be a function” and tries to prove it by matching smaller and smaller pieces.
3. Recursive descent is top-down written by hand. You write one function per grammar rule. parseStatement calls parseExpression, which calls parseTerm. The call stack of the compiler mirrors the tree being built.
4. Bottom-up does the opposite. It pushes tokens onto a stack, and whenever the top of the stack matches the right-hand side of a rule, it replaces those items with the left-hand side. That is called a reduce.
5. Bottom-up parsers are usually generated by a tool from a grammar file, because the tables are far too tedious to write by hand.
6. Precedence is the rule that 2 + 3 * 4 is 14, not 20. A hand-written parser gets it by layering: the + function calls the * function, so * binds tighter and sits deeper in the tree.
7. Associativity is the rule that a - b - c means (a - b) - c. It decides whether the tree leans left or right.

TECHNICAL16.4.5 the engineer’s version#

1. Programming language syntax is described by a context-free grammar (CFG), level 2 in the Chomsky hierarchy from Noam Chomsky’s 1956 classification.
2. Backus-Naur Form came from John Backus in 1959 and Peter Naur’s editing of the ALGOL 60 report in 1960. Donald Knuth proposed the name in 1964. Extended BNF adds *, +, ? and grouping.
3. LL(k) parsers read Left to right and build a Leftmost derivation, with k tokens of lookahead. Recursive descent is the hand-written form of LL(1).
4. LR(k) parsers read Left to right and build a Rightmost derivation in reverse. LALR(1) is the practical variant used by Yacc and Bison. LR grammars are strictly more powerful than LL grammars.
5. Yacc was written by Stephen C. Johnson at Bell Labs, published as a 1975 technical report. GNU Bison is the free replacement, from Robert Corbett in the mid-1980s. ANTLR, by Terence Parr from 1989, generates adaptive ALL(*) parsers.
6. Real compilers have moved back to hand-written recursive descent. GCC replaced its Bison C++ parser in GCC 3.4, 2004, and its C parser in GCC 4.1, 2006. Clang was recursive descent from the start. The reason is error messages and recovery, not speed.
7. Two classic grammar problems. The dangling else is settled by a rule in the C standard. The C typedef ambiguity makes (A)*b a cast or a multiplication depending on whether A is a type.
   1. C parsers settle the second by feeding symbol table facts back into the parser. That breaks the clean stage separation, and is called the lexer hack.
8. Operator precedence in C has 15 levels. Precedence climbing, also called Pratt parsing after Vaughan Pratt’s 1973 paper, handles all of them in one compact function instead of 15 nested ones.

WORDS16.4.6 remember these#

Parser — the part that finds the shape of the program — the syntax analyser that builds a parse tree or AST from a token stream. Abstract syntax tree — a tree of what the code does — a tree of language constructs with punctuation removed, the front end’s main data structure. Grammar — the written rules of the language’s shape — a context-free grammar, usually given in BNF or EBNF. Recursive descent — one function per grammar rule — a hand-written predictive top-down parser, normally LL(1) with local backtracking. Syntax error — the shape is wrong — no production allows the current token given the parser state; reported with the source location of that token.

16.5 Semantic analysis: does it make sense#

PLAIN16.5.1 in simple words#

1. A sentence can have correct shape and still be nonsense. “The number ate the Tuesday” is grammatical and meaningless.
2. Semantic analysis is the stage that catches the meaningless ones.
3. It asks: does this name exist here? Have you used it before declaring it? Have you declared it twice?
4. It asks: do the types fit? Can you add these two things? Can you pass this thing where that thing is expected?
5. It builds a symbol table: a list of every name, what it is, what type it has, and where it is visible.
6. Most of the errors a working programmer sees come from this stage, not from the parser.

PLAIN16.5.2 a picture in your head#

1. Imagine a hotel with a guest register at the front desk.
2. When somebody checks in, you write their name and room in the register.
3. When a letter arrives for “Mr Smith”, you look the name up. If he is not in the register, the letter cannot be delivered.
4. The hotel has floors. Each floor has its own small register. When looking up a name you check the floor you are on, then the floor below, then the ground floor register.
5. When a floor closes for the night, its small register is thrown away, and those names stop meaning anything.

Where this comparison breaks: a hotel register is one flat list per floor. A real symbol table also records types, storage class, linkage, whether the thing is a function or a variable, and how the compiler will refer to it later. And hotel names are unique; C deliberately lets an inner name hide an outer one.

PLAIN16.5.3 a worked example#

The symbol table for our file, after analysing it, holds these entries:

1. When the parser reaches a + b inside add, semantic analysis looks up a. It finds the parameter, whose type is int.
2. It looks up b. Also int.
3. It checks that + accepts two int values. It does. The result type of the whole expression is recorded as int.
4. It checks that the type being returned matches the function’s declared return type. int and int. Fine.
5. In main, it looks up add, finds a function of type int (int, int), checks the call has two arguments, and checks each argument’s type.

Now break it on purpose. Change the call to add(2, "three"). Real output from clang -c typeerr.c:

typeerr.c:2:32: error: incompatible pointer to integer
  conversion passing 'char[6]' to parameter of type 'int'
    2 | int main(void) { return add(2, "three"); }
      |                                ^~~~~~~
typeerr.c:1:20: note: passing argument to parameter 'b' here
    1 | int add(int a, int b) { return a + b; }
      |                    ^
1 error generated.

1. The shape of this program is perfectly legal. The parser was happy.
2. Only the type checker complains, and it can quote two places: the call and the declaration. It could only do that because the symbol table remembered where add was declared.
3. GCC 13.3 makes this a warning by default and still compiles. Clang 18 makes it an error. Experts disagree on default strictness; GCC 14 turned several such warnings into errors in 2024. Use -Werror to be strict.

PLAIN16.5.4 what is really happening inside#

1. The symbol table is usually a stack of hash tables, one per scope.
2. Entering a { pushes a new table. Leaving } pops it.
3. Looking up a name searches the top table, then the one below, and so on. The first hit wins. That is exactly why an inner variable hides an outer one.
4. Type checking walks the AST from the leaves upward. Each node computes its own type from its children’s types.
5. IntegerLiteral 2 says “I am int”. DeclRefExpr a asks the symbol table and says “I am int”. BinaryOperator + sees two ints and says “I am int”.
6. Where types nearly match, C inserts a silent conversion. The Clang AST for our file shows ImplicitCastExpr <LValueToRValue> around a and b. That node means “read the value out of the variable”. The compiler added it; you did not write it.
7. Type inference is the same walk in reverse: the compiler works out a type instead of checking a written one. In C++ auto x = 2 + 3; the type of x is deduced from the right-hand side.

TECHNICAL16.5.5 the engineer’s version#

1. Semantic analysis covers name resolution, scope and lifetime rules, type checking, implicit conversion insertion, constant expression evaluation, and language-specific rules such as C’s requirement that a case label be a constant.
2. C has four scopes in the standard: file, block, function prototype and function (labels only). Linkage is separate from scope: static at file level means internal linkage, no static means external linkage.
3. Clang stores this in a Sema object with an IdentifierResolver and a chain of DeclContexts. GCC uses binding_level structures. Both amount to a scoped hash table.
4. Full Hindley-Milner inference, from J. Roger Hindley in 1969 and Robin Milner in 1978, infers types for a whole program without annotations. ML, OCaml and Haskell use it. Rust and C++ use weaker local inference, so errors stay near the mistake.
5. The dividing line matters for error quality. Missing semicolon is a parse error. Undeclared identifier, wrong argument count, wrong argument type, assigning to a const, duplicate definition and returning the wrong type are all semantic errors.
6. Borrow checking in Rust and lifetime analysis are semantic analysis too, done on a control-flow graph after the AST. They are the reason rustc is slower than a C front end.
7. Useful flags: gcc -Wall -Wextra -Werror, gcc -fsyntax-only to stop after this stage, clang -Xclang -ast-dump to see the typed tree.

WORDS16.5.6 remember these#

Symbol table — the list of every name and what it means — a scoped mapping from identifier to declaration, type, storage class and linkage. Scope — the region where a name is visible — the block, file, prototype or function region defined by the language standard. Type checking — making sure the pieces fit — verifying every expression’s type against the operator or context that consumes it. Implicit conversion — a change the compiler adds silently — a cast node inserted into the AST, such as C’s integer promotions and lvalue-to-rvalue conversion. Name resolution — deciding which declaration a name refers to — lookup through the scope chain, obeying shadowing and linkage rules.

16.6 Intermediate representation#

PLAIN16.6.1 in simple words#

1. After the tree is checked, the compiler could write chip instructions straight away. Almost none do.
2. Instead they rewrite the program in a simple made-up language of their own. That is the intermediate representation, or IR.
3. The IR is deliberately boring. Every line does one tiny thing. No nesting, no shortcuts, no cleverness.
4. Boring is useful. It is much easier to spot a wasted step in a flat list of tiny operations than in a tree full of nested expressions.
5. It is also useful because the IR does not belong to any chip. The same IR can later be turned into instructions for many different chips.
6. And it does not belong to any language either. C, C++, Rust and Swift can all produce the same IR, and then share one optimizer and one code generator.

PLAIN16.6.2 a picture in your head#

1. Think of an international airport with one central hub.
2. There are many airlines flying in from many countries, and many destinations flying out.
3. Without a hub you would need a direct route from every origin to every destination. Ten origins and ten destinations means a hundred routes.
4. With a hub, every origin flies to the hub, and the hub flies to every destination. Ten plus ten. Twenty routes instead of a hundred.
5. The IR is the hub. Languages fly in, chips fly out.

Where this comparison breaks: a passenger arrives at the hub unchanged. A program does not. Most of the real work, and most of the compiler’s total running time, happens while the program is sitting in the hub being rewritten.

PLAIN16.6.3 a worked example#

Here is our add function in GCC’s IR, called GIMPLE, from gcc -O1 -fdump-tree-gimple=/dev/stdout -S add.c:

int add (int a, int b)
{
  int D.2746;
  D.2746 = a + b;
  return D.2746;
}

int main ()
{
  int D.2748;
  D.2748 = add (2, 3);
  return D.2748;
}

1. Notice the temporary name D.2746. The compiler invented it.
2. Every statement has at most one operator and at most three names: one destination and two sources. That is why this style is called three-address code.
3. Now the same thing in Static Single Assignment form, from gcc -O1 -fdump-tree-ssa=/dev/stdout -S add.c:

int add (int a, int b)
{
  int _3;
  <bb 2> :
  _3 = a_1(D) + b_2(D);
  return _3;
}

4. Every name now has a version number. a_1, b_2, _3.
5. <bb 2> is a basic block: a run of instructions with no branch in the middle. Control enters at the top and leaves at the bottom.
6. And here is our whole file in LLVM IR, real output from clang -O0 -S -emit-llvm add.c, with the attribute lines removed:

define dso_local i32 @add(i32 noundef %0, i32 noundef %1) {
  %3 = alloca i32, align 4
  %4 = alloca i32, align 4
  store i32 %0, ptr %3, align 4
  store i32 %1, ptr %4, align 4
  %5 = load i32, ptr %3, align 4
  %6 = load i32, ptr %4, align 4
  %7 = add nsw i32 %5, %6
  ret i32 %7
}

define dso_local i32 @main() {
  %1 = alloca i32, align 4
  store i32 0, ptr %1, align 4
  %2 = call i32 @add(i32 noundef 2, i32 noundef 3)
  ret i32 %2
}

7. i32 means a 32-bit integer. %0 and %1 are the two parameters.
8. alloca reserves space on the stack. At -O0 the compiler dutifully stores both parameters to the stack and loads them straight back. That is pointless, and the optimizer will delete it.
9. add nsw means add with “no signed wrap”: the compiler is allowed to assume signed overflow never happens. Hold on to that; it comes back in 16.7.

PLAIN16.6.4 what is really happening inside#

1. Static Single Assignment, or SSA, means every name is written exactly once in the whole function.
2. If your source assigns x three times, the IR has x_1, x_2 and x_3.
3. Why bother? Because now, if you see a use of x_2, there is exactly one place it could have come from. No searching. No guessing.
4. That single property makes constant propagation, dead code removal and value numbering enormously simpler and faster.
5. Branches create a problem: after an if, which version of x is live? SSA solves it with a phi node, written PHI, which says “take the version from whichever block we came from”.
6. Here is a real phi from a loop, for (i = 0; i < n; i++) s += i;, dumped by GCC with -fdump-tree-ssa:

  <bb 4> :
  # s_1 = PHI <s_3(2), s_8(3)>
  # i_2 = PHI <i_4(2), i_9(3)>
  if (i_2 < n_5(D))
    goto <bb 3>;
  else
    goto <bb 5>;

7. Read s_1 = PHI <s_3(2), s_8(3)> as: if we arrived from block 2, s_1 is s_3; if from block 3, it is s_8.
8. Phi nodes are not real instructions. Late in the back end they are removed by inserting copies into the predecessor blocks.

TECHNICAL16.6.5 the engineer’s version#

1. SSA was formalized by Ron Cytron, Jeanne Ferrante, Barry Rosen, Mark Wegman and Kenneth Zadeck in Efficiently computing static single assignment form and the control dependence graph, ACM TOPLAS, October 1991.
2. Placing phi nodes minimally requires dominance frontiers, computed by the Lengauer-Tarjan dominator algorithm of 1979 or Cooper, Harvey and Kennedy’s simpler 2001 method.
3. GCC uses two IRs in sequence. GIMPLE is a three-address, SSA-capable, tree-ish IR added in GCC 4.0, 2005. RTL, Register Transfer Language, is the older low-level IR used by the back end.
4. LLVM uses a single strongly typed SSA IR with three equivalent forms: an in-memory form, a human-readable .ll text form, and a compact .bc bitcode form. llvm-as and llvm-dis convert between text and bitcode.
5. LLVM IR is not a portable virtual machine. It embeds the target data layout and pointer sizes, visible in our dump as target triple = "x86_64-pc-linux-gnu". Shipping .bc and expecting it to run anywhere is a common misunderstanding.
6. The front-end / middle-end / back-end split is what makes the ecosystem work. Clang, Rust, Swift, Julia, Zig and flang all emit LLVM IR. LLVM 18 registers over 30 target backends, from x86 and AArch64 to RISC-V, WebAssembly, NVPTX and AVR.
7. Other IR designs exist. Java bytecode and CPython bytecode are stack machines, not three-address. WebAssembly is a structured stack machine. Cranelift, used by Wasmtime, uses its own SSA IR built for compile speed rather than peak output quality.

WORDS16.6.6 remember these#

Intermediate representation — the compiler’s own simple language — a program form between source and machine code, target and language neutral in the middle end. Three-address code — one operation, one result, two inputs per line — a linearized IR form of the shape t1 = a op b. SSA — every name written exactly once — static single assignment form, with phi functions merging values at control-flow joins. Basic block — a straight run with no branches inside — a maximal instruction sequence with a single entry and a single exit. Phi node — “take whichever value we came in with” — a pseudo-instruction at a join point selecting a value by predecessor block.

16.7 Optimization#

PLAIN16.7.1 in simple words#

1. The optimizer rewrites your program so it does less work but produces the same visible result.
2. It is allowed to change anything you cannot observe. It is not allowed to change what you can observe.
3. If the answer is always the same number, compute it now and store the number.
4. If a value never changes, replace the name with the value.
5. If a result is never used, delete the code that made it.
6. If the same sum is computed twice, compute it once.
7. If a function is tiny, paste its body into the caller instead of calling it.
8. Do all of these repeatedly, because each one exposes new chances for the others.

PLAIN16.7.2 a picture in your head#

1. Imagine editing a set of instructions for making tea for a guest.
2. Step 3 says “boil water”. Step 9 says “boil water” again. Delete step 9 and reuse the first pot. That is common subexpression elimination.
3. Step 5 says “count the sugar packets in the drawer” every time round the stirring loop, but nobody adds packets. Move it outside the loop. That is loop-invariant code motion.
4. Step 7 says “fetch a lemon” and no later step uses the lemon. Delete step 7. That is dead code elimination.
5. Step 2 says “look up the boiling point of water in the book”. You know it is
   100. Write 100. That is constant folding.
6. Step 8 says “consult the separate one-line card called stir”. Just write “stir” here. That is inlining.

Where this comparison breaks: you may delete “fetch a lemon” only if fetching lemons has no other effect. In a real program, a “useless” call might print something, write a file or set a flag another thread reads. Deciding whether a step is observable is the hard part, and it is most of what an optimizer does.

PLAIN16.7.3 a worked example#

This is the heart of the chapter. Compile our unchanged file two ways.

gcc -O0 -S add.c, the whole add function, with directives removed:

add:
    endbr64
    pushq   %rbp
    movq    %rsp, %rbp
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %edx
    movl    -8(%rbp), %eax
    addl    %edx, %eax
    popq    %rbp
    ret

main:
    endbr64
    pushq   %rbp
    movq    %rsp, %rbp
    movl    $3, %esi
    movl    $2, %edi
    call    add
    popq    %rbp
    ret

gcc -O2 -S add.c, the same file:

add:
    endbr64
    leal    (%rdi,%rsi), %eax
    ret

main:
    endbr64
    movl    $5, %eax
    ret

1. Seventeen instructions became five.
2. Why is add now one instruction? At -O0 the compiler stores both arguments to the stack and reloads them, because -O0 keeps every variable in memory for the debugger. At -O2 that is deleted.
3. leal (%rdi,%rsi), %eax computes rdi + rsi and puts it in eax. lea means load effective address: it does the address arithmetic but does not touch memory. It is used here as a free three-operand add.
4. Why is main now movl $5, %eax? Three optimizations in sequence.
   1. Inlining: add is tiny, so its body is pasted into main, giving return 2 + 3;.
   2. Constant folding: 2 + 3 is computed at compile time, giving return 5;.
   3. Dead code elimination: nothing else in main is needed, so the frame setup, the call, and the stack work all disappear.
5. add still exists as a separate function because it has external linkage: another file might call it. Mark it static and the whole function vanishes from the output.
6. The program still returns 5. ./a.out; echo $? prints 5. That is the only thing that had to stay true.

Other optimizations, each verified on this machine with GCC 13.3 at -O2:

1. Row one is constant folding: the whole expression is a compile-time constant.
2. Row two is strength reduction: multiply by 8 became a scaled address computation, which is cheaper than a general multiply.
3. Row three is dead code elimination: the multiply by 999 is gone.
4. Row four is common subexpression elimination: a*b was written twice and is computed once.

PLAIN16.7.4 what is really happening inside#

1. Loop unrolling copies a loop body several times so the loop test runs less often. Our recursive tail(n, acc) function was turned by GCC into a loop and then unrolled by a factor of two.
2. Tail call elimination is what made that possible. When the last thing a function does is call something and return its result, the call can reuse the current stack frame. A self tail call then becomes a jump, that is, a loop.
3. Even across separate files, GCC at -O2 turned call add; ret into a plain jmp add. That is a tail call: add’s own ret returns straight to main’s caller.
4. Vectorization does several elements at once. For for (i=0;i<n;i++) out[i] = in[i] * 2.0f; GCC at -O3 emitted movups and addps. addps is “add packed single”, four 32-bit floats in one instruction, using the 128-bit SSE registers.
5. Register allocation decides which values live in registers. x86-64 has 16 general purpose registers, a few reserved, so roughly 12 to 14 are usable. Values that do not fit must be spilled to the stack.
6. Chaitin’s method models this as graph colouring. Each value is a node, and two nodes are joined if they are live at the same moment. Colouring with k colours, k being the register count, is exactly a valid allocation.
7. Graph colouring is NP-complete in general, so compilers use heuristics: repeatedly remove any node with fewer than k neighbours, and if none exists, pick a node to spill and try again.

TECHNICAL16.7.5 the engineer’s version#

1. The legal limit on all of this is the as-if rule. An implementation may do anything, provided observable behaviour matches the abstract machine. The C standard defines that as volatile accesses, input and output, and the state at termination.
2. GCC optimization levels, as documented for GCC 13: -O0 none, -O1 about 47 passes, -O2 most non-size-increasing passes, -O3 adds vectorization and heavier inlining, -Os optimizes for size, -Ofast is -O3 plus -ffast-math, -Og keeps debugging usable.
3. Floating point is not associative. IEEE 754 arithmetic rounds each operation, so (a+b)+c and a+(b+c) can differ. Real run on this machine with a = 1e20f, b = -1e20f, c = 1.0f:

(a+b)+c = 1
a+(b+c) = 0

4. That is why compilers must not reassociate floating point by default. -ffast-math grants permission to reassociate, to assume no NaN or infinity, and to flush denormals. On this machine, adding 0.1f ten times prints 1.00000012, not 1.
5. Undefined behaviour lets the compiler assume the impossible never happens. Signed integer overflow is undefined in C. Real GCC 13.3 output at -O2:

int check(int x) { return x + 1 > x; }
check:
    movl    $1, %eax        # always true, folded
    ret

unsigned check_u(unsigned x) { return x + 1 > x; }
check_u:
    xorl    %eax, %eax      # real comparison kept
    cmpl    $-1, %edi
    setne   %al
    ret

6. The signed version was folded to a constant 1. The unsigned version was not, because unsigned overflow is defined to wrap, so x + 1 > x really is false when x is UINT_MAX.
7. Compiling the signed version with -fwrapv restores the comparison, against 2147483647. -fwrapv is a GCC and Clang extension defining signed overflow as wrapping. It is an implementation choice, not the C standard.
8. Undefined behaviour also erases null checks after a dereference, deletes infinite loops with no side effects, and assumes strict aliasing. Tools: -fsanitize=undefined, -fsanitize=address, and Clang’s -Rpass=inline to see what was inlined.

WORDS16.7.6 remember these#

Constant folding — do the sums now, not later — evaluating constant expressions at compile time. Inlining — paste the function body in — replacing a call with the callee’s body, enabling further optimization at the call site. Dead code elimination — delete what nobody uses — removing instructions whose results are not live and have no side effects. Spilling — running out of registers and using memory — storing a live value to the stack frame because the allocator could not colour it. As-if rule — you may change anything nobody can see — the standard’s permission to transform a program while preserving observable behaviour. Undefined behaviour — the standard gives no rules for this — a construct for which the standard imposes no requirements, letting the optimizer assume it never occurs.

16.8 Code generation#

PLAIN16.8.1 in simple words#

1. Now the compiler must write instructions for one actual chip.
2. Three jobs happen here, tangled together.
3. Instruction selection: pick which real instructions do what the IR said. The IR said “add”. The chip may offer add, lea or inc.
4. Instruction scheduling: pick the order. Some instructions wait for results; put unrelated work in the gap.
5. Register allocation: pick which of the chip’s few fast slots holds which value, and put the rest in memory.
6. There is also a rule book that everybody must obey: where arguments go, where the answer comes back, who is allowed to break which register.
7. That rule book is the calling convention. It is what lets a function compiled today call a library compiled ten years ago.

PLAIN16.8.2 a picture in your head#

1. Think of handing work to a colleague through a hatch with numbered trays.
2. Everyone in the building has agreed: the first thing you are passing goes in tray 1, the second in tray 2, and the answer comes back in tray 0.
3. Some trays are yours to scribble on; the colleague may empty them. Other trays they must hand back exactly as they found them.
4. If you both follow the agreement, neither of you needs to know anything about how the other works inside.
5. If you disagree about which tray is which, everything breaks in ways that look like random corruption.

Where this comparison breaks: real conventions also cover stack alignment, variable argument lists, structures too big for a register, floating point in separate registers, and where the return address lives. And there is no single agreement: Linux, Windows and ARM each chose different trays.

PLAIN16.8.3 a worked example#

Here is our -O0 add function again, and this time every line is annotated.

add:
    endbr64                 # landing pad for indirect jumps (CET)
    pushq   %rbp            # save caller's frame pointer
    movq    %rsp, %rbp      # this function's frame starts here
    movl    %edi, -4(%rbp)  # store arg 1 (a) into the frame
    movl    %esi, -8(%rbp)  # store arg 2 (b) into the frame
    movl    -4(%rbp), %edx  # load a back into edx
    movl    -8(%rbp), %eax  # load b back into eax
    addl    %edx, %eax      # eax = a + b
    popq    %rbp            # restore caller's frame pointer
    ret                     # jump back to the return address

1. %edi and %esi are the low 32 bits of rdi and rsi. On Linux those are the first two integer argument registers.
2. %eax holds the return value. The result of the addition is already there, so no extra move is needed.
3. The two stores and two loads are pure -O0 overhead, as explained in 16.7.
4. pushq %rbp and movq %rsp, %rbp are the prologue. popq %rbp and ret are the epilogue.
5. endbr64 is not part of the calling convention. It is Intel Control-flow Enforcement Technology, enabled by default on Ubuntu with -fcf-protection=full. It marks a legal target for an indirect jump.

And main:

main:
    endbr64
    pushq   %rbp            # prologue
    movq    %rsp, %rbp
    movl    $3, %esi        # second argument = 3
    movl    $2, %edi        # first argument  = 2
    call    add             # push return address, jump to add
    popq    %rbp            # epilogue; eax already holds 5
    ret                     # return to the C runtime

1. Arguments are loaded second-first here. That order is the compiler’s choice, not a rule. Only which register holds which argument is fixed.
2. call pushes the address of the next instruction onto the stack and jumps.
3. Nothing copies the result. add left it in eax and main returns it from eax.

The stack while add is running:

higher addresses
  +-----------------------------+
  | main's frame                |
  +-----------------------------+
  | return address into main    | <- pushed by call
  +-----------------------------+
  | saved rbp                   | <- pushed by prologue
  +-----------------------------+ <- rbp now points here
  | -4(%rbp)  copy of a         |
  | -8(%rbp)  copy of b         |
  +-----------------------------+ <- rsp
  | 128-byte red zone           |    usable without moving rsp
  +-----------------------------+
lower addresses

PLAIN16.8.4 what is really happening inside#

1. Instruction selection is usually done by tree pattern matching. The IR is covered with the cheapest set of instruction patterns that fits.
2. The cost model matters. imul by 8 costs about 3 cycles on many x86 cores; lea with a scale of 8 costs 1. That is why GCC chose lea.
3. Instruction scheduling matters most on machines that issue several instructions per cycle. Modern out-of-order x86 chips reorder anyway, so scheduling is worth less there than on an in-order core.
4. The same source compiled for AArch64 with clang --target=aarch64-linux-gnu -O2 gives:

add:
    add     w0, w1, w0
    ret
main:
    mov     w0, #5
    ret

5. Same structure, different names. w0 and w1 are the low 32 bits of x0 and x1, the first two AArch64 argument registers, and x0 is also the return register.
6. The same source targeting Windows with clang --target=x86_64-pc-windows-msvc -O0 stores from %ecx and %edx instead of %edi and %esi, because Windows chose different argument registers.
7. One source file, three sets of rules, all correct.

TECHNICAL16.8.5 the engineer’s version#

1. The three conventions side by side. All three are written specifications, not conventions in the loose sense: System V AMD64 ABI, Microsoft x64 calling convention, and Arm’s AAPCS64.

2. Callee-saved registers on System V AMD64 are rbx, rbp, r12, r13, r14, r15. A function that uses them must restore them. Everything else is caller-saved: if you need it after a call, save it yourself.
3. Stack alignment: System V AMD64 requires rsp + 8 to be 16-byte aligned at a call, so rsp is 16-byte aligned on entry after the return address is pushed. AAPCS64 requires sp 16-byte aligned at all public interfaces.
4. The red zone is 128 bytes below rsp that a leaf function may use without adjusting rsp. Signal handlers must not clobber it. Kernel code is compiled with -mno-red-zone for exactly this reason.
5. Structures larger than 16 bytes are passed in memory on System V AMD64; smaller ones are classified field by field into INTEGER and SSE classes. The classification algorithm in the ABI document is one of the fiddliest parts of the whole convention.
6. Register allocation in production: GCC uses IRA, an integrated regional allocator, plus LRA for reload, replacing the old reload pass in GCC 4.8,
   2013. LLVM’s default is a greedy allocator based on priority and live range splitting, not classical Chaitin colouring. Linear scan allocation, from Massimiliano Poletto and Vivek Sarkar in 1999, is preferred by JITs because it is far faster to run.
7. Useful commands: gcc -S -masm=intel for Intel syntax, objdump -d --no-show-raw-insn, perf annotate to see which instruction is hot, and llvm-mca to model instruction throughput on a named CPU.

WORDS16.8.6 remember these#

Calling convention — the shared rules about who puts what where — the ABI specification of argument registers, return registers, stack alignment and register preservation. Prologue — the few instructions that set up a function — saving the frame pointer and reserving stack space on entry. Epilogue — the few instructions that clean up — restoring saved registers and returning. Stack frame — one function’s private scratch area — the region between the frame pointer and the stack pointer holding locals, spills and saved registers. Callee-saved register — one you must hand back unchanged — a register the ABI requires the called function to preserve across the call. Instruction selection — choosing which real instructions to use — covering the IR with target patterns under a cost model.

16.9 The assembler#

PLAIN16.9.1 in simple words#

1. The compiler’s output is still text. addl %edx, %eax is nine characters.
2. The assembler turns each such line into the bytes the chip actually reads.
3. It is a much simpler program than the compiler. Mostly it is a lookup table plus arithmetic on addresses.
4. It also collects your program into named piles called sections.
5. Code goes in one pile. Numbers you gave starting values go in another. Numbers that start at zero go in a third that takes no file space at all.
6. It records every name you defined and every name you used but did not define.
7. Where an address is not yet known, it writes zeros and leaves a note. Those notes are called relocations.
8. Its output is an object file, ending .o on Unix and .obj on Windows.

PLAIN16.9.2 a picture in your head#

1. Think of typesetting a book chapter that refers to other chapters.
2. You can set every word of your own chapter into metal type immediately.
3. But “see chapter 9, page …” cannot be set, because you do not know the page number yet. Other people are still setting chapter 9.
4. So you leave a gap of the right size and write a note in the margin: “fill this gap with the start page of chapter 9”.
5. You hand the printer your typeset pages plus your list of margin notes.
6. Later, somebody assembling the whole book fills every gap.

Where this comparison breaks: some relocations are not simple substitutions. They store a difference between two addresses, or an offset from the current position, or an index into a table filled at program start. The note in the margin has a type, and there are dozens of types.

PLAIN16.9.3 a worked example#

Run gcc -c add.c -o add.o, then objdump -d add.o:

0000000000000000 <add>:
   0:  f3 0f 1e fa     endbr64
   4:  55              push   %rbp
   5:  48 89 e5        mov    %rsp,%rbp
   8:  89 7d fc        mov    %edi,-0x4(%rbp)
   b:  89 75 f8        mov    %esi,-0x8(%rbp)
   e:  8b 55 fc        mov    -0x4(%rbp),%edx
  11:  8b 45 f8        mov    -0x8(%rbp),%eax
  14:  01 d0           add    %edx,%eax
  16:  5d              pop    %rbp
  17:  c3              ret

0000000000000018 <main>:
  18:  f3 0f 1e fa     endbr64
  1c:  55              push   %rbp
  1d:  48 89 e5        mov    %rsp,%rbp
  20:  be 03 00 00 00  mov    $0x3,%esi
  25:  bf 02 00 00 00  mov    $0x2,%edi
  2a:  e8 00 00 00 00  call   2f <main+0x17>
  2f:  5d              pop    %rbp
  30:  c3              ret

1. The left column is the offset inside the section. The middle column is the actual bytes. The right column is the text form.
2. 01 d0 is two bytes. That is the entire add %edx,%eax instruction.
3. c3 is one byte: ret.
4. Look at offset 2a. The call is e8 followed by 00 00 00 00. The assembler did not know where add would end up, so it wrote four zero bytes.
5. objdump guesses the target as 2f, which is simply “the next instruction”, because the offset is zero. That is not the real target. It is a hole.
6. Now the note in the margin, from readelf -r add.o:

Relocation section '.rela.text':
  Offset        Type              Sym. Name + Addend
  00000000002b  R_X86_64_PLT32    add - 4

7. Read it as: at byte offset 0x2b, which is the four zero bytes, write the distance from here to add, minus 4.
8. nm add.o shows the symbols: 0000000000000000 T add and 0000000000000018 T main. T means defined in the text section.

PLAIN16.9.4 what is really happening inside#

1. The assembler makes two passes. Pass one measures every instruction and works out where each label lands. Pass two writes the bytes, using the label addresses from pass one.
2. Two passes are needed because of forward references: a jump to a label further down the file cannot be encoded until that label’s position is known.
3. Sections keep unlike things apart so the operating system can protect them differently:
   1. .text is machine code. It ends up readable and executable, not writable.
   2. .rodata is constants, such as string literals. Readable, not writable.
   3. .data is variables with a non-zero starting value. Readable and writable, and its contents occupy space in the file.
   4. .bss is variables starting at zero. Readable and writable, and it takes no file space at all: only a size is recorded.
4. readelf -S add.o on our file shows .text at 0x31 bytes and both .data and .bss at zero bytes, because our program has no global variables.
5. That is why a program declaring a 10 MB zeroed array does not have a 10 MB executable. The .bss entry says “10 MB of zeros” in a few bytes.

TECHNICAL16.9.5 the engineer’s version#

1. The object file format on Linux and most Unix systems is ELF, Executable and Linkable Format, introduced with UNIX System V Release 4 around 1988 and adopted by Linux in the mid-1990s, replacing a.out. macOS uses Mach-O, from NeXTSTEP. Windows uses PE/COFF.
2. Our add.o contains 13 section headers. The important ones are .text, .rela.text, .data, .bss, .symtab, .strtab, .shstrtab and .eh_frame.
3. .symtab is the symbol table, .strtab holds the symbol name strings, and .shstrtab holds the section name strings. Names are stored once and referenced by offset.
4. .eh_frame holds unwind information generated from the .cfi_* directives in the assembly. It is what lets a debugger produce a backtrace and what lets C++ exceptions unwind the stack. It is generated even for C.
5. Common x86-64 relocation types: R_X86_64_64 absolute 64-bit, R_X86_64_PC32 32-bit program-counter relative, R_X86_64_PLT32 call through the procedure linkage table, R_X86_64_GOTPCREL load through the global offset table. R_X86_64_RELATIVE is applied at load time for position-independent executables.
6. Symbol binding is LOCAL, GLOBAL or WEAK. nm prints T for a global text symbol, t for local, U for undefined, B for .bss, D for .data, W for weak.
7. Our whole object file is 169 bytes of text, data and bss combined, per size add.o. The linked executable reports 1302 bytes of text, because the C runtime start-up code has been added.

WORDS16.9.6 remember these#

Assembler — turns instruction text into bytes — a two-pass translator from assembly mnemonics to encoded machine instructions plus metadata. Object file — a half-finished program with holes — a relocatable ELF, Mach-O or COFF file containing sections, symbols and relocations. Section — one named pile of similar bytes — a named region such as .text, .data, .bss or .rodata with its own permissions. Relocation — a note saying “fill this hole later” — a record naming an offset, a symbol and a formula for computing the value to patch in. Symbol — a name the outside world can see — a named entry binding an identifier to a section and offset, with a binding and a visibility.

16.10 The linker#

PLAIN16.10.1 in simple words#

1. Real programs are many files. Each is compiled separately into an object file full of holes.
2. The linker puts them all together and fills every hole.
3. It stacks all the .text sections into one .text, all the .data into one .data, and so on.
4. Now every function has a final address, so every hole can be filled with a real number.
5. Then it checks that every name that was used somewhere is defined somewhere.
6. If a name is used and never defined, it stops and says undefined reference. That is the most famous error message in C.
7. It also pulls in code from libraries: bundles of ready-made object files.

PLAIN16.10.2 a picture in your head#

1. Think of assembling one book from chapters written by different authors.
2. Each author numbered their pages from 1. You must renumber so the whole book runs from 1 to 400.
3. Every “see page 12” inside chapter 3 must be adjusted by however much chapter 3 moved.
4. Every “see the chapter on rivers” must be turned into a real page number by looking up which chapter that is.
5. If somebody wrote “see the chapter on volcanoes” and no such chapter exists, the book cannot be finished. That is undefined reference.
6. A static library is a shelf of spare chapters. You copy in only the ones somebody referred to.
7. A dynamic library is a separate book that stays separate. Your book says “look this up in the other book”, and the reader must own that book.

Where this comparison breaks: the linker does more than renumber. It merges duplicate definitions of inline functions and templates, discards unused sections, can reorder functions for cache locality, and with link-time optimization can re-run the whole optimizer across chapter boundaries.

PLAIN16.10.3 a worked example#

Split our example across two files: main2.c calling add, and addonly.c defining it. Compile main2.c alone and try to link:

$ gcc main2.c -o prog2
/usr/bin/ld: /tmp/cckot5dw.o: in function `main':
main2.c:(.text+0x13): undefined reference to `add'
collect2: error: ld returned 1 exit status

1. The compiler was perfectly happy: the header declared add, so the call type checked.
2. The linker was not, because no object file defines add.
3. Now link both: gcc main2.o addonly.o -o prog2. It works, and returns 5.

Look at what relocation actually did. In add.o the call was e8 00 00 00 00. In the linked executable, objdump -d:

0000000000001129 <add>:
    1129:  f3 0f 1e fa   endbr64
    ...
0000000000001141 <main>:
    1141:  f3 0f 1e fa   endbr64
    ...
    1153:  e8 d1 ff ff ff   call   1129 <add>

4. The four zero bytes became d1 ff ff ff, which as a signed 32-bit little-endian number is -47.
5. The instruction after the call starts at 0x1158. And 0x1158 - 47 = 0x1129, which is exactly where add ended up.
6. That is the whole of relocation, in one number.

Now libraries. Real commands and real sizes on this machine:

$ ar rcs libadd.a addonly.o           # static library
$ gcc main2.c -L. -ladd -o prog_static

$ gcc -fPIC -shared addonly.c -o libadd.so   # shared library
$ gcc main2.c -L. -ladd -o prog_dyn -Wl,-rpath,'$ORIGIN'

Both programs return 5. In prog_static the add code is inside the executable. In prog_dyn it is not, and ldd prog_dyn lists libadd.so => /tmp/kb/./libadd.so.

PLAIN16.10.4 what is really happening inside#

1. A static library .a file is just an archive of object files, made by ar. ar -t libadd.a prints addonly.o.
2. The linker treats an archive specially: it does not include everything. It scans the archive and pulls in only the members that resolve a symbol still undefined at that moment.
3. That is why link order matters. The linker walks the command line left to right, keeping a set of currently undefined symbols.
4. Real proof on this machine. gcc -L. -ladd main2.c fails with “undefined reference to add”, while gcc main2.c -L. -ladd succeeds. Same files, different order.
5. The reason: when the library was scanned, nothing needed add yet, so no member was pulled in. main2.c came later and asked for a symbol nobody was still looking for. Put objects first and libraries last.
6. In C++ the situation is harder, because C++ allows several functions with the same name. The linker only handles plain names, so the compiler encodes the full signature into the name. That is name mangling.
7. Real output from nm on a C++ file, alongside nm -C which demangles:

_Z3addii          ->  add(int, int)
_Z3adddd          ->  add(double, double)
_ZN2kb1T3addEii   ->  kb::T::add(int, int)
add_c             ->  add_c

8. Read _Z3addii as: mangled name, 3-letter name add, arguments i, i. The last one is extern "C", which turns mangling off, which is exactly how C and C++ call each other.

TECHNICAL16.10.5 the engineer’s version#

1. Linker phases: read inputs, resolve symbols, assign section addresses via a layout script, apply relocations, write output, optionally strip.
2. Library naming, all conventions rather than standards: .a static and .so shared on Linux, .lib static and .dll dynamic on Windows, .a static and .dylib dynamic on macOS. Windows also uses an import .lib that describes a .dll without containing its code.
3. Symbol visibility controls what a shared library exports. GCC and Clang accept -fvisibility=hidden plus __attribute__((visibility("default"))) on the few symbols you mean to export. Smaller export tables mean faster loading and better optimization. Windows uses __declspec(dllexport) and __declspec(dllimport).
4. Shared library code must be position independent, built with -fPIC, because it can be mapped at different addresses in different processes. Most Linux distributions have built executables as position independent (PIE) by default since around 2017.
5. Link-time optimization keeps the IR in the object file instead of only machine code, so the optimizer can run across file boundaries at link time. Real measurement on this machine, with add in a separate file from main:
   1. gcc -O2 main2.c addonly.c gave main a tail call: mov $3,%esi; mov $2,%edi; jmp 1150 <add>.
   2. gcc -O2 -flto main2.c addonly.c gave main exactly mov $0x5,%eax; ret.
6. That is the same inline-then-fold sequence from 16.7, now working across translation units, which plain -O2 cannot do. GCC’s LTO arrived in GCC 4.5,
   2010. LLVM offers full LTO and ThinLTO, the latter published by Teresa Johnson and colleagues in 2017 for much better build parallelism.
7. Linker choices as of 2026: GNU ld, the original; gold, 2008, ELF only and dropped from recent binutils; LLVM lld, the default in many toolchains; and mold by Rui Ueyama, 1.0 in 2022, the fastest widely used linker for large C++ builds.
8. Weak symbols let a definition be overridden. __attribute__((weak)) is how a library provides a default that a program may replace.

WORDS16.10.6 remember these#

Linker — the tool that glues object files into a program — the program that merges sections, resolves symbols and applies relocations. Static library — a shelf of object files you copy from — an ar archive whose members are pulled in only to satisfy undefined symbols. Shared library — a separate file loaded at run time — a .so, .dll or .dylib mapped into the process by the dynamic linker. Name mangling — encoding the full signature into the symbol name — the compiler scheme that gives overloaded and namespaced C++ entities distinct linker names. Link-time optimization — optimizing across file boundaries — keeping IR in object files so the optimizer runs at link time. Undefined reference — somebody used a name nobody defined — an unresolved symbol remaining after all inputs have been scanned.

16.11 The loader and dynamic linking#

PLAIN16.11.1 in simple words#

1. A finished executable is a file on disk. It is not yet a running program.
2. When you type its name and press Enter, the operating system creates a process and puts the file’s contents into that process’s memory.
3. The part of the operating system that does this is the loader.
4. It does not copy the whole file. It maps it, meaning it says “this range of memory corresponds to this part of this file”, and lets the pages arrive when they are first touched.
5. If the program uses shared libraries, they are not inside it, so somebody must find them, load them too, and connect the calls.
6. That job belongs to a small program called the dynamic linker, which the loader starts first.
7. Only after all that does your main actually run.

PLAIN16.11.2 a picture in your head#

1. Think of a play. The script is the executable file. The performance is the process.
2. The stage manager, the loader, sets out the scenery from the script.
3. The script says “at this point, the orchestra plays the theme”. The orchestra is a shared library and is not in your script.
4. So before the curtain, an assistant goes and finds the orchestra, checks they have the right music, and writes their seat numbers into a small card at the side of the stage.
5. Every time the script says “orchestra”, an actor glances at the card to see where to look.
6. If the assistant is lazy, the card starts blank, and the first time the actor glances at it, the assistant is fetched to fill in that one entry.

Where this comparison breaks: the card, the global offset table, is per process, not per library, and it is normally made read-only after start-up for security. And the assistant is itself a shared library, loaded by a special path that does not need an assistant.

PLAIN16.11.3 a worked example#

readelf -l on our executable shows what the loader is told to do:

Elf file type is DYN (Position-Independent Executable)
Entry point 0x1040
  Type    VirtAddr    FileSiz  MemSiz  Flg  Align
  INTERP  0x00000318  0x00001c 0x00001c R    0x1
     [Requesting interpreter: /lib64/ld-linux-x86-64.so.2]
  LOAD    0x00000000  0x0005f0 0x0005f0 R    0x1000
  LOAD    0x00001000  0x000169 0x000169 R E  0x1000
  LOAD    0x00002000  0x0000ec 0x0000ec R    0x1000
  LOAD    0x00003df0  0x000220 0x000228 RW   0x1000

1. Four LOAD entries, four memory regions with different permissions.
2. The second is R E, readable and executable: that is your code.
3. The last is RW and its MemSiz (0x228) is larger than its FileSiz (0x220). The extra 8 bytes are .bss, zero-filled at load and stored in no file bytes at all.
4. INTERP names the dynamic linker. The kernel loads that, not your program.

Now watch it happen. strace -e trace=execve,openat,mmap ./prog_dyn, trimmed:

execve("./prog_dyn", ["./prog_dyn"], ...) = 0
openat(".../glibc-hwcaps/x86-64-v4/libadd.so") = -1 ENOENT
openat(".../glibc-hwcaps/x86-64-v3/libadd.so") = -1 ENOENT
openat("/tmp/kb/libadd.so", O_RDONLY|O_CLOEXEC) = 3
mmap(NULL,  16400, PROT_READ, ...)              = 0x7f88..
mmap(0x..1c, 4096, PROT_READ|PROT_EXEC, ...)
mmap(0x..1d, 4096, PROT_READ, ...)
mmap(0x..1e, 8192, PROT_READ|PROT_WRITE, ...)
openat("/etc/ld.so.cache", O_RDONLY|O_CLOEXEC)  = 3
openat("/lib/x86_64-linux-gnu/libc.so.6", ...)  = 3
+++ exited with 5 +++

5. It searched several CPU-feature-specific directories first, then found the library, then mapped it in four pieces with different permissions.
6. It consulted /etc/ld.so.cache, a prebuilt index of every library on the system, before touching the real directories, because scanning directories for every library on every program start would be slow.

PLAIN16.11.4 what is really happening inside#

1. Calls into a shared library do not jump directly. They jump to a small local stub. Real disassembly of main in prog_dyn:

    115b:  e8 f0 fe ff ff   call   1050 <add@plt>

0000000000001050 <add@plt>:
    1050:  f3 0f 1e fa      endbr64
    1054:  ff 25 76 2f 00 00  jmp *0x2f76(%rip)  # 3fd0

2. main calls a stub called add@plt. That stub jumps to whatever address is stored at 0x3fd0.
3. The table of such addresses is the global offset table, the GOT. The table of stubs is the procedure linkage table, the PLT.
4. readelf -r prog_dyn shows the note that fills slot 0x3fd0:

Relocation section '.rela.plt' contains 1 entry:
  Offset        Type               Sym. Name
  000000003fd0  R_X86_64_JUMP_SLO  add + 0

5. Lazy binding: by default, the GOT slot initially points back into the PLT, which calls the dynamic linker to resolve the symbol, patch the slot, and jump on. Every later call goes straight through.
6. Setting LD_BIND_NOW=1 resolves everything up front. On this machine, LD_DEBUG=statistics LD_BIND_NOW=1 ./prog_dyn reported 100 relocations and about 155,000 cycles of total dynamic loader start-up time.
7. Lazy binding trades a slightly slower first call for a faster start. Hardened builds turn it off, because a writable GOT is an attack target; -z now plus -z relro makes the GOT read-only after start-up.

TECHNICAL16.11.5 the engineer’s version#

1. Search order for a shared library on glibc: DT_RPATH if there is no DT_RUNPATH, then LD_LIBRARY_PATH, then DT_RUNPATH, then /etc/ld.so.cache, then the default directories /lib and /usr/lib with their architecture subdirectories.
2. DT_RPATH is deprecated in favour of DT_RUNPATH, because RUNPATH is overridable by LD_LIBRARY_PATH and RPATH is not. Our example used -Wl,-rpath,'$ORIGIN' and readelf -d shows RUNPATH Library runpath: [$ORIGIN]. $ORIGIN expands to the directory of the executable, which is how self-contained application bundles work.
3. Setting LD_LIBRARY_PATH globally in a shell profile is a well-known source of confusing bugs, because it affects every program you start. Prefer RUNPATH baked into the binary.
4. LD_PRELOAD loads a library before all others, letting you interpose on any function. It is the mechanism behind many profilers and sanitizer shims. For safety, it is ignored for set-user-ID programs.
5. Versioned sonames are how Linux avoids most DLL hell. A library records a SONAME such as libc.so.6, and glibc additionally versions individual symbols, so __libc_start_main@GLIBC_2.34 and an older version can coexist in one file. Our binary’s relocation table shows exactly that symbol.
6. Dependency hell is when two of your dependencies need incompatible versions of a third. DLL hell was the Windows form, where an installer overwrote a shared system32 DLL and broke other programs. Windows answered with side-by-side assemblies from Windows XP, 2001.
7. Static linking avoids all of it and costs disk space and the loss of shared library security updates. Go links statically by default; Rust links its own standard library statically but the system C library dynamically unless you choose a musl target.
8. This chapter has treated ELF, Mach-O and PE only as far as needed to explain linking and loading. Chapter 20 covers the file formats themselves in detail.

WORDS16.11.6 remember these#

Loader — the part of the OS that turns a file into a process — the execve path that maps PT_LOAD segments and transfers control to the entry point. Dynamic linker — the helper that finds and connects libraries — ld.so, named in the PT_INTERP segment, which maps dependencies and applies relocations. GOT — the little table of “where is it really” — the global offset table, an array of addresses patched at load or first use. PLT — the little stubs that read that table — the procedure linkage table, one trampoline per imported function. Lazy binding — only look it up the first time it is called — resolving PLT entries on first call rather than at start-up; disabled by -z now. RUNPATH — a search path baked into the program — the DT_RUNPATH dynamic entry, searched after LD_LIBRARY_PATH.

16.12 Interpreters and virtual machines#

PLAIN16.12.1 in simple words#

1. Compiling is not the only way to run a program.
2. An interpreter reads your program and does what it says, immediately, without ever producing machine code.
3. The simplest kind walks the syntax tree from 16.4. At a + node it evaluates the left child, evaluates the right child, and adds.
4. That is easy to write and slow to run, because it re-inspects the tree every single time round a loop.
5. So most real “interpreted” languages do something in between. They compile your program once into a simple made-up instruction set, then run those.
6. Those instructions are bytecode, and the program that runs them is a virtual machine.
7. Bytecode is not for any real chip. It is designed to be easy to produce and quick to run in a loop.

PLAIN16.12.2 a picture in your head#

1. Imagine a recipe in a foreign language and a cook who does not read it.
2. Option one: a translator stands beside the cook and translates each line aloud, every time, including every time round a repeated step. That is a tree interpreter.
3. Option two: the translator writes out the whole recipe in simple numbered steps first, and the cook then follows the numbered steps. Translation happens once. That is bytecode.
4. Option three: the translator rewrites the recipe into this exact kitchen’s own house notation, tuned for these exact pans, before anyone starts. That is ahead-of-time compilation.

Where this comparison breaks: option two’s numbered steps are still not what the kitchen’s machines understand. Somebody, the virtual machine, is still reading each numbered step and deciding what to do. That reading is the cost that a JIT, covered in 16.13, removes.

PLAIN16.12.3 a worked example#

Our example in Java, compiled with javac and disassembled with javap -c:

static int add(int, int);
  Code:
     0: iload_0
     1: iload_1
     2: iadd
     3: ireturn

public static void main(java.lang.String[]);
  Code:
     0: iconst_2
     1: iconst_3
     2: invokestatic  #7   // Method add:(II)I
     5: invokestatic  #13  // Method System.exit:(I)V
     8: return

1. This is a stack machine. iload_0 pushes local variable 0. iload_1 pushes local variable 1. iadd pops two and pushes their sum. ireturn pops and returns.
2. Every opcode is one byte, which is where the name bytecode comes from.
3. No registers are named. That is deliberate: the JVM does not know what chip it is on.
4. The first eight bytes of the .class file, from od -An -tx1 -N 8, are ca fe ba be 00 00 00 41. The first four are the magic number 0xCAFEBABE, chosen at Sun in the early 1990s. 0x41 is 65: Java 21.

And the same idea in CPython 3.11, from the dis module:

def add(a, b): return a + b
  LOAD_FAST     0 (a)
  LOAD_FAST     1 (b)
  BINARY_OP     0 (+)
  RETURN_VALUE

def main(): return add(2, 3)
  LOAD_GLOBAL   1 (NULL + add)
  LOAD_CONST    1 (2)
  LOAD_CONST    2 (3)
  PRECALL       2
  CALL          2
  RETURN_VALUE

5. Same shape: push, push, operate, return.
6. Python caches this in __pycache__/m.cpython-311.pyc, whose first four bytes here are a7 0d 0d 0a: a version magic, then a carriage return and newline chosen so that a text-mode file transfer corrupts the magic and the file is rejected rather than misread.
7. The huge difference is what the opcodes mean. iadd in Java adds two 32-bit integers, full stop. BINARY_OP + in Python must inspect both objects’ types at run time and find the right method. That is most of the speed gap.

PLAIN16.12.4 what is really happening inside#

1. A bytecode virtual machine is a loop: fetch the next opcode, jump to the code for it, do it, repeat.
2. The jump is usually a computed jump into a table of handler addresses. The cost per opcode is that jump plus the work.
3. The jump is hard for the CPU’s branch predictor, because the next opcode is essentially unpredictable. That mispredict cost is the main tax of interpretation.
4. Threaded code reduces it. Instead of one jump at the top of the loop, each handler ends with its own jump to the next handler, giving the predictor more context. CPython uses computed gotos on GCC and Clang for this reason.
5. Bytecode is portable because it names no registers, no addresses and no instruction encodings. One .class file runs on x86, AArch64 and anything else with a JVM.
6. It also starts fast, because there is nothing to compile at start-up if the bytecode is already cached, which is exactly what .pyc files are for.

TECHNICAL16.12.5 the engineer’s version#

1. Java was released by Sun Microsystems in January 1996. The JVM specification defines the class file format, the instruction set, verification rules and the memory model. It is a written standard.
2. The JVM has about 200 defined opcodes out of 256, leaving room reserved for internal use. Class file major versions map to releases: 52 is Java 8, 55 is Java 11, 61 is Java 17, 65 is Java 21.
3. Bytecode verification happens at class load. The verifier proves type safety and stack discipline before any code runs. That is a real security property, and it is why JVM bytecode is not simply machine code in disguise.
4. CPython compiles to bytecode at import and caches it. __pycache__ and the .pyc naming scheme were introduced in Python 3.2 by PEP 3147, 2010. The bytecode format is explicitly unstable between minor releases, which is why the file name includes cpython-311.
5. Python 3.11, October 2022, added a specializing adaptive interpreter, PEP 659, which rewrites hot opcodes into type-specialized versions at run time. The CPython team reported roughly 1.25 times faster on their benchmark suite versus 3.10.
6. Rough figures for an arithmetic loop, order of magnitude only, because the real ratio depends heavily on the workload. Treat these as approximate.
   1. A tree-walking interpreter: roughly 100 to 1000 times slower than C.
   2. A bytecode VM with no JIT: roughly 10 to 100 times slower.
   3. A good JIT: within about 1 to 3 times.

WORDS16.12.6 remember these#

Interpreter — a program that carries out your program directly — an evaluator that executes source or IR without emitting native code. Bytecode — compact instructions for a made-up machine — a serialized instruction set for a virtual machine, typically one byte per opcode. Virtual machine — the program that runs bytecode — an abstract machine specification plus its implementation, such as the JVM or CPython’s ceval loop. Stack machine — a machine with no named registers — an architecture where operands are pushed and popped on an operand stack. Dispatch — choosing which handler runs next — the fetch-decode-jump step of an interpreter loop, often implemented with computed gotos.

16.13 Just-in-time compilation#

PLAIN16.13.1 in simple words#

1. A just-in-time compiler, or JIT, compiles your program while it is already running.
2. It does not compile everything. Most code runs once or twice and is not worth the effort.
3. So the system counts. Every time a function is entered or a loop goes round, a counter goes up.
4. When a counter crosses a threshold, that code is hot, and the JIT compiles it to real machine instructions.
5. The next time it is reached, the fast version runs instead.
6. A JIT knows something an ordinary compiler cannot: what actually happened. It knows which types really turned up, which branch really got taken, and which function really got called.
7. So it compiles a specialized version based on those observations, and adds a cheap check that the observation still holds.
8. If the check ever fails, it throws that version away and goes back to the slow safe path. That is called deoptimization.

PLAIN16.13.2 a picture in your head#

1. Imagine a new receptionist at a large office. On day one they look up every visitor’s destination in the directory.
2. After a week they notice that nearly everyone who arrives asks for the third floor, so they start saying “third floor” before checking.
3. But they keep a quick glance at the visitor’s badge, in case somebody different turns up.
4. If a badge does not match, they stop guessing, go back to the directory, and look it up properly for that visitor.
5. Guessing is a huge win only because it is nearly always right and because being wrong is safe.

Where this comparison breaks: the receptionist keeps their memory. A real JIT must be able to abandon an optimized version mid-execution, reconstruct the exact state the slow interpreter would have had at that point, and resume. Getting that reconstruction correct is one of the hardest parts of JIT engineering.

PLAIN16.13.3 a worked example#

Take our add, but in a dynamic language, where a + b could mean anything.

1. First call: the interpreter runs BINARY_OP +. It looks at the type of a, looks at the type of b, finds both are whole numbers, and adds them.
2. The system records what it saw: two whole numbers, at this exact spot.
3. Calls two to about a thousand: the same thing, and the recording is confirmed each time.
4. The counter crosses the threshold. The JIT compiles this function assuming both arguments are whole numbers.
5. It emits something close to our -O2 output: a check, then one add instruction, then a return.
6. The check is a guard: “is a really a whole number, is b?” A few instructions, usually predicted correctly, essentially free.
7. Call 100,000: someone passes a string. The guard fails. The compiled version is abandoned for that call, the state is rebuilt, and the interpreter takes over from that exact point.
8. If it keeps failing, the compiled version is discarded and recompiled with the new information.

Real tiering in the HotSpot JVM, which is a written design, not a guess:

The exact thresholds are controlled by -XX:CompileThreshold and related flags and vary between JVM versions; treat the numbers as typical defaults rather than fixed values.

PLAIN16.13.4 what is really happening inside#

1. Compilation happens on a background thread, so the program keeps running on the old version while the new one is prepared.
2. On-stack replacement, or OSR, handles the awkward case of a loop that is already running and will not be entered again. The system swaps the running frame over to compiled code partway through.
3. Inline caching, invented for Smalltalk by L. Peter Deutsch and Allan Schiffman in 1984, remembers at each call site which method was called last time, so the lookup is skipped.
4. A polymorphic inline cache, from Urs Hölzle, Craig Chambers and David Ungar’s work on Self in 1991, remembers several possibilities at one site.
5. Hidden classes, also from Self, give dynamically shaped objects a fixed internal layout, so a field access can become a single load at a fixed offset instead of a dictionary lookup.
6. Those three ideas together are the reason JavaScript became fast. They were research results from the 1980s and 1990s that were finally applied to the web in the 2008 to 2012 period.

TECHNICAL16.13.5 the engineer’s version#

1. HotSpot came to Sun through the 1997 acquisition of Animorphic and shipped in
   1999. It introduced tiered compilation with the C1 client compiler and the C2 server compiler, plus deoptimization back to the interpreter.
2. Google’s V8 shipped with Chrome in September 2008, developed in Aarhus under Lars Bak, who had worked on Self and HotSpot. The lineage is direct.
3. V8’s pipeline as of 2026 is Ignition, a bytecode interpreter, then Sparkplug, a baseline compiler added in 2021, then Maglev, a mid-tier compiler added in 2023, then TurboFan. Ignition plus TurboFan replaced Crankshaft in Chrome 59, 2017.
4. Mozilla’s SpiderMonkey, the original JavaScript engine written by Brendan Eich in 1995, went through TraceMonkey in 2008, and now uses Baseline plus IonMonkey with WarpBuilder.
5. Deoptimization needs a precise mapping from optimized machine state back to interpreter state at every safepoint. This is stored as side tables and is a large part of why JIT compilers are hard to write correctly.
6. The trade against ahead-of-time compilation:
   1. JIT wins on peak speed for dynamic languages, because it can specialize on observed types and inline through virtual calls speculatively.
   2. AOT wins on start-up time, on memory, on predictable latency, and on platforms that forbid writable-and-executable memory, such as iOS.
   3. JIT costs memory for the compiler, the profiling data and the code cache.
   4. JIT hurts tail latency, because compilation and deoptimization happen at unpredictable moments. This matters for trading systems and for games.
7. Hybrid approaches now dominate. Java has AppCDS class data sharing and GraalVM native-image ahead-of-time compilation, first released 2019. Android moved from Dalvik’s pure JIT to ahead-of-time ART in Android 5.0, 2014, then to a profile-guided mix in Android 7.0, 2016.
8. Established fact: JIT reliably beats plain interpretation for long-running dynamic code. Active research: cheap start-up, predictable latency, and sharing profiles across runs. Marketing claim: any flat statement that a JIT language is “as fast as C”.

WORDS16.13.6 remember these#

JIT — compiling while the program runs — dynamic translation of hot code to native instructions, guided by run-time profiles. Hot path — the code that runs most — a method or loop whose execution counter has crossed a compilation threshold. Tiered compilation — several compilers of increasing quality — a pipeline from interpreter to baseline to optimizing compiler, per method. Deoptimization — abandoning fast code when a guess turns out wrong — reconstructing interpreter state at a safepoint and resuming in the slower tier. Inline cache — remembering what was called here last time — a per-call-site cache of receiver type to target method, monomorphic or polymorphic. On-stack replacement — swapping code under a running loop — transferring an active frame from interpreted to compiled code, or back.

16.14 Modern build reality#

PLAIN16.14.1 in simple words#

1. In real projects, nobody types gcc by hand.
2. A build system works out what needs rebuilding and runs the commands.
3. It does this by comparing times: if the source is newer than the output, the output is stale and must be rebuilt.
4. Anything that depended on that output is stale too, and so on up the chain.
5. Rebuilding only what changed is an incremental build, and it is the difference between a two-second edit-run cycle and a twenty-minute one.
6. A cross-compiler runs on one kind of machine and produces code for another. That is how phone apps are built on laptops.
7. A transpiler compiles from one high-level language to another, rather than to machine code.
8. A toolchain is the whole matched set: compiler, assembler, linker, standard library and headers for one target.

PLAIN16.14.2 a picture in your head#

1. Think of a kitchen preparing a large set menu.
2. Some dishes depend on a stock that takes an hour. Some depend on that stock’s sauce. Some depend on nothing.
3. A good kitchen keeps a chart of what depends on what.
4. If the stock is remade, everything downstream of it must be remade. If only a garnish changed, only the garnish is redone.
5. A busy kitchen also keeps a fridge of finished components labelled with exactly which ingredients went into them. If someone orders the same component again with identical ingredients, it comes out of the fridge. That is a build cache.

Where this comparison breaks: a kitchen can smell that the stock has gone off. A build system has only timestamps and hashes. If a timestamp lies, for example because clocks differ between machines or a file was restored from backup, the build system will confidently reuse something wrong. This is a real and common class of bug.

PLAIN16.14.3 a worked example#

Here is our two-file version, driven by make.

prog: main2.o addonly.o
    gcc main2.o addonly.o -o prog
main2.o: main2.c addh.h
    gcc -c main2.c -o main2.o
addonly.o: addonly.c
    gcc -c addonly.c -o addonly.o

Real session on this machine:

$ make
gcc -c main2.c -o main2.o
gcc -c addonly.c -o addonly.o
gcc main2.o addonly.o -o prog

$ make
make: 'prog' is up to date.

$ touch addonly.c && make
gcc -c addonly.c -o addonly.o
gcc main2.o addonly.o -o prog

$ touch addh.h && make
gcc -c main2.c -o main2.o
gcc main2.o addonly.o -o prog

1. The first build compiles both files.
2. The second build does nothing, because nothing is newer than its output.
3. Touching addonly.c rebuilds only that object, then relinks.
4. Touching the header rebuilds main2.o, because the rule lists addh.h as a dependency. That listing is the whole trick, and forgetting it is the classic cause of “it did not pick up my header change”. Generate it automatically with gcc -MMD.

PLAIN16.14.4 what is really happening inside#

1. Make builds a graph of files and rules, sorts it so dependencies come first, and runs any rule whose output is older than any of its inputs.
2. Modern build systems replace timestamps with content hashes, which is more reliable: the same input bytes plus the same command always give the same output.
3. That is what makes a build cache possible. Hash the compiler version, the flags and the preprocessed source; if that hash was seen before, reuse the stored object file. ccache does exactly this locally, and Bazel and Gradle do it across a whole team.
4. Cross-compilation works because the pipeline in 16.1 is already split. The front end does not care about the target. Only the back end, the assembler, the linker and the libraries do.
5. Our chapter already did it. clang --target=aarch64-linux-gnu -O2 -S add.c produced ARM instructions on an x86 machine, with no special install, because LLVM ships every backend in one binary.
6. To produce a runnable ARM binary you also need ARM headers and libraries. That is the difference between a compiler and a toolchain, and it is why cross-toolchain setup is more annoying than cross-compiling itself.

TECHNICAL16.14.5 the engineer’s version#

1. make was written by Stuart Feldman at Bell Labs in 1976, reportedly after losing a morning to a program that had failed to relink. Its tab-indentation rule has never been fixed for compatibility reasons.
2. CMake was created at Kitware around 2000 for the Insight Toolkit, funded by the US National Library of Medicine. It is a build generator: it does not build, it writes Makefiles, Ninja files or Visual Studio projects.
3. Ninja, written by Evan Martin for the Chrome build in the early 2010s, is deliberately not human-authored. Its input is machine-generated, its dependency handling is fast, and it is the usual back end for CMake and for Meson on large projects.
4. Gradle targets the JVM world, uses a Groovy or Kotlin domain-specific language, supports incremental and cached tasks, and reached 1.0 in 2012. Bazel is the open-sourced version of Google’s Blaze, released in 2015, and is built around hermetic, hash-keyed, remotely cacheable actions.
5. ccache, from Andrew Tridgell in the early 2000s, and distcc, from Martin Pool around the same time, remain the cheapest large wins for C and C++ projects that cannot adopt Bazel.
6. Transpilers: TypeScript, announced by Microsoft in October 2012 under Anders Hejlsberg, compiles to JavaScript. Babel, started as 6to5 by Sebastian McKenzie in 2014, compiles newer JavaScript to older JavaScript. The very first C++ implementation, Bjarne Stroustrup’s Cfront from 1983, was a transpiler to C.
7. WebAssembly is a portable compilation target with a formal specification. Its Core Specification 1.0 became a W3C Recommendation in December 2019.
   1. Our example built with clang --target=wasm32 -O2 -nostdlib -c add.c gave a 333-byte module.
   2. Its first eight bytes are 00 61 73 6d 01 00 00 00, that is \0asm followed by version 1.
8. Why build times matter: they set the length of the edit-compile-test loop, which sets how often a developer tries an idea. As a scale marker, a full Chromium build is commonly reported in hours on one workstation and minutes with a large distributed cache.

WORDS16.14.6 remember these#

Build system — the thing that decides what to recompile — a dependency graph executor keyed on timestamps or content hashes. Incremental build — rebuild only what changed — recomputing the minimal set of stale targets from the dependency graph. Build cache — reuse a result somebody already computed — a content-addressed store keyed on inputs, tool version and flags. Cross-compilation — building on one machine for another — using a toolchain whose target triple differs from the host triple. Transpiler — a compiler whose output is another language — a source-to-source translator, such as TypeScript to JavaScript. Toolchain — the whole matched set of tools — compiler, assembler, linker, headers and runtime libraries for one target.

16.15 The bootstrap problem and trusting trust#

PLAIN16.15.1 in simple words#

1. A C compiler is a program. Programs must be compiled. So what compiled the first C compiler?
2. This is the bootstrap problem, and there are only three honest answers.
3. One: write the first version in something else, such as assembly or another existing language.
4. Two: write a small, limited version by hand, then use it to compile a bigger version, then use that to compile a bigger one still.
5. Three: use a compiler on a different machine to produce code for yours. That is cross-compilation from 16.14.
6. A compiler written in the language it compiles is self-hosting. Almost every serious compiler ends up this way.
7. Self-hosting is a strong test: the compiler is its own largest and most demanding user.

PLAIN16.15.2 a picture in your head#

1. Imagine you want a workshop that can build any tool, including its own tools.
2. You cannot start there. You start with a rough hammer made by hand.
3. With the rough hammer you make a better hammer. With the better hammer you make a decent lathe. With the lathe you make precise tools.
4. Eventually the workshop can make every tool in it, including exact copies of its own machines.
5. The first rough hammer is then thrown away, and nobody alive has seen it.

Where this comparison breaks: a hammer’s shape is visible. A compiler can carry an invisible instruction inside it that is not written in any source file anybody keeps, and that instruction can copy itself into every tool the workshop makes. That is the whole point of the next block.

PLAIN16.15.3 a worked example#

1. Start with our own file. gcc add.c worked because a gcc binary already existed on this machine. That binary is itself written in C and C++, so some earlier compiler must have built it. Follow that chain back far enough and you reach the question of where the first one came from.
2. Around 1972 to 1973, Dennis Ritchie’s C compiler at Bell Labs was written in an earlier language, first B and then an intermediate step usually called NB or “new B”, and grew into C by stages, each version compiling the next.
3. In 1973 the Unix kernel was rewritten in C for Version 4 Unix, which is the moment portable operating systems become possible.
4. Corrado Böhm’s 1951 PhD thesis at ETH Zurich described the first compiler for a language written in that same language, so the idea is older than C by two decades.
5. Tim Hart and Mike Levin wrote a Lisp compiler in Lisp at MIT in 1962, then ran it through the Lisp interpreter to compile itself.
6. Modern examples: the Rust compiler became self-hosted in April 2011. Go removed the last of its C compiler in Go 1.5, August 2015, and has been written in Go since.
7. Today’s route for a brand-new C compiler is easier. Compile version one with GCC, compile version one with itself, compile once more, and check the last two outputs are byte-identical. That is a three-stage bootstrap, and GCC does it in its own build.

PLAIN16.15.4 what is really happening inside#

1. Now Ken Thompson’s argument, in plain words. He gave it in his 1984 Turing Award lecture, Reflections on Trusting Trust, printed in Communications of the ACM in August 1984. He and Dennis Ritchie shared the 1983 Turing Award.
2. Step one. Suppose you modify a C compiler so that when it notices it is compiling the login program, it silently adds a back door accepting a secret password.
3. That is easy but obvious: the extra code is right there in the compiler’s source, and any reviewer would see it.
4. Step two. So add a second rule: when the compiler notices it is compiling a C compiler, it silently inserts both rules into the output.
5. Now compile the compiler with the modified compiler. The new binary contains both rules.
6. Step three. Remove all of it from the source. Delete every line. The source is clean and reviewable and contains nothing suspicious.
7. But the compiled compiler still carries both rules, because it was built by a compiler that inserts them. Compile the clean source with that binary, and the new binary has them again.
8. The attack now lives only in the binary, reproducing itself forever, with no trace in any source file anybody reads.
9. Thompson’s conclusion: you cannot trust code you did not totally write yourself, and “totally” reaches all the way down through the compiler, the assembler, the linker, the loader, the operating system and the hardware.
10. He also noted that no amount of source-level inspection protects you, because the source is genuinely clean.

TECHNICAL16.15.5 the engineer’s version#

1. The paper’s technique is a quine-like self-reproducing program combined with two pattern-matching triggers. Thompson stated that he had actually built a working version, though it was never released.
2. The practical defence is diverse double-compiling, from David A. Wheeler’s 2005 paper and 2009 PhD dissertation. Compile the suspect compiler’s source with a second, independently written compiler, then use both binaries to compile that source again. Identical final binaries mean neither carries the attack.
3. This only works if the compiler is deterministic: the same source and flags must always give byte-identical output. That requirement is precisely the goal of the Reproducible Builds project, which began within Debian around 2013.
4. Sources of non-determinism that have to be removed: embedded build timestamps, build paths in debug information, file ordering from directory reads, random hash seeds and thread scheduling. GCC and Clang both accept SOURCE_DATE_EPOCH and -ffile-prefix-map to help.
5. As of 2026, Debian reports that the large majority of its source packages build reproducibly, and several distributions publish rebuild verification. Exact percentages move month to month, so treat any single figure as dated.
6. The related project Bootstrappable Builds attacks the other end: shrinking the trusted seed binary to something a human can audit. Its chain starts from a few hundred bytes of hand-checkable machine code and climbs through stage0, M2-Planet, TinyCC and GCC.
7. Established fact: the attack works and is well understood. Active research: verifying the whole chain from hardware upward, including proved compilers such as CompCert, machine-checked in Coq since 2008. Marketing claim: any product said to have solved supply-chain trust.
8. The honest version: reproducible builds and diverse double-compiling reduce the trusted base, they do not eliminate it. You still trust the CPU microcode, the firmware and the fabrication process. Thompson’s point survives; we have only made the untrusted part smaller.

WORDS16.15.6 remember these#

Bootstrapping — getting a compiler off the ground with no compiler — building a language’s compiler through successive stages from an existing toolchain. Self-hosting — a compiler written in its own language — a compiler that can compile its own source, usually verified by a multi-stage build. Three-stage bootstrap — build it three times and compare — stage 2 and stage 3 outputs must be byte-identical, a standard part of the GCC build. Trusting trust — the compiler can lie and the source will not show it — Thompson’s 1984 self-reproducing compiler back door. Reproducible build — same source in, same bytes out, every time — a build whose output is a deterministic function of its declared inputs. Diverse double-compiling — check one compiler using a different one — Wheeler’s method for detecting a trusting-trust attack in a deterministic compiler.

16.98 Common wrong ideas#

1. Wrong: the compiler translates your code line by line into machine code. Right: it goes through the whole chain of 16.1, and the optimizer may delete, merge, reorder and duplicate your lines. Our two-line file became three instructions with no call in it.

2. Wrong: #include imports a module the way Python’s import does. Right: it pastes the file’s text at that point. Two lines of C with #include <stdio.h> became 815 lines of text on this machine.

3. Wrong: a syntax error means the compiler does not understand what you meant. Right: a syntax error means no grammar rule allows the token it just saw. Meaning is checked later, in semantic analysis, and produces different errors.

4. Wrong: undefined reference is a compiler error. Right: it is a linker error. The compiler was satisfied by the declaration. The linker could not find a definition. That is why the fix is usually an extra object file or library, not a code change.

5. Wrong: -O2 makes your program do the same steps, faster. Right: it makes the program produce the same observable result by doing different steps. Our main never calls add at all after -O2.

6. Wrong: undefined behaviour means the program does something unpredictable at that point. Right: it means the compiler may assume it never happens, which can change code far away from the mistake. x + 1 > x folded to a constant 1 at -O2.

7. Wrong: floating point differences between -O0 and -O2 are compiler bugs. Right: they can be legitimate, especially with -ffast-math, because IEEE 754 addition is not associative. On this machine (a+b)+c gave 1 and a+(b+c) gave 0 for the same three values.

8. Wrong: interpreted languages are slow because interpreting is slow. Right: mostly they are slow because operations must decide their meaning at run time. Java bytecode is interpreted too and is far faster, because iadd already knows it is adding two 32-bit integers.

9. Wrong: a JIT is always faster than ahead-of-time compilation. Right: it wins on peak speed for dynamic code and loses on start-up time, memory use and latency predictability. That is why iOS forbids it and why GraalVM native-image exists.

10. Wrong: reading a compiler’s source proves it has no back door. Right: Thompson showed in 1984 that a compiler binary can carry an attack that appears in no source file. Diverse double-compiling, not reading, is the defence.

16.99 Chapter summary in 20 lines#

1. A compiler is a chain of stages, each turning one shape of information into a simpler one, from text to running process.
2. The preprocessor is a text editor: it pastes files in and substitutes macros, and it knows nothing about C.
3. The lexer cuts characters into labelled tokens using a finite automaton, and always takes the longest legal match.
4. The parser arranges tokens into an abstract syntax tree, guided by a context-free grammar written in Backus-Naur Form.
5. A syntax error means no grammar rule allows the current token. It is about shape, not meaning.
6. Semantic analysis builds a scoped symbol table, resolves names, checks types and inserts implicit conversions.
7. Compilers then rewrite the program into an intermediate representation: flat three-address code, usually in static single assignment form.
8. SSA gives every value exactly one definition, with phi nodes at joins, which makes most optimizations simple and fast.
9. The front-end, middle-end, back-end split lets many languages share one optimizer and one set of processor backends.
10. The optimizer may do anything that preserves observable behaviour: fold, propagate, delete, inline, unroll, vectorize, and eliminate tail calls.
11. Our int main(void) { return add(2,3); } became movl $5, %eax; ret through inlining, then constant folding, then dead code elimination.
12. Undefined behaviour lets the optimizer assume the impossible never happens, which is why x + 1 > x folds to 1 for signed integers but not unsigned.
13. Code generation performs instruction selection, scheduling and register allocation, and must obey a calling convention.
14. System V AMD64 passes the first two integers in rdi and rsi, Windows x64 uses rcx and rdx, AArch64 uses x0 and x1. All return in the first of those.
15. The assembler turns instruction text into bytes, groups them into sections, records symbols, and leaves relocations where addresses are unknown.
16. The linker merges sections, resolves symbols and patches relocations. Our e8 00 00 00 00 became e8 d1 ff ff ff, a relative jump of minus 47 bytes.
17. Library order on the command line matters, because archives are scanned once against the symbols still undefined at that moment.
18. At exec time the kernel maps segments and starts the dynamic linker, which loads shared libraries and fills the GOT, lazily by default.
19. Bytecode virtual machines trade speed for portability, and a JIT wins it back by compiling hot paths using types observed at run time, with deoptimization as the safety net.
20. Compilers bootstrap themselves, and Ken Thompson showed in 1984 that a compiler binary can hide a back door that no source file reveals, which is why reproducible and diverse builds matter.