Week 0 · Lesson 3
Compilers and IRs
A compiler is a program that reads a program and writes a different program that means the same thing. In the middle it holds the program as a data structure called an IR. This course is about designing that data structure well.
The pipeline
A classic compiler goes through stages. Each one turns the program into a new representation that's easier to work with for the next job. Step through what happens to one small expression.
Trees repeat themselves, DAGs share
A tree is the obvious way to store an expression: every operator node points at its operands. But (a + b) * (a + b) has the same subexpression twice, and a tree stores it twice. If you compile the tree naively, you compute a + b twice.
A DAG (directed acyclic graph) lets two parents point at the same child. You build it by keeping a table of every node you've made, keyed by "what op, which operands" (a hash table, which is a dictionary: give it a key and it quickly gives back the stored value). Before you build a node, you look it up. If it's already there, you reuse it. That trick is called hash consing, and it's how the course's IR works from day one. Two nodes with the same op and the same inputs are not just equal, they're the same object.
Sharing isn't a small saving. Take x1 = x0 + x0, x2 = x1 + x1, and so on up to x30. As a DAG that's 31 nodes. As a tree it's over a billion. Any code that walks your IR without remembering what it already visited will treat the DAG like a tree, and it'll never finish. The week 1 tests include a deeper version of this case (300 levels).
Code quiz: how big is the tree?
e0 = a + b is a tree of 3 nodes. e(k+1) = e(k) * e(k), stored as a tree with no sharing, so both operands are full copies. Write long long tree_nodes(int k) returning the node count of e(k), for 0 <= k <= 60. The same thing as a DAG has just k + 3 nodes.
From a DAG to lines of C: toposort
C runs top to bottom, so to print C from a DAG you need an order where every node comes after the nodes it uses. That order is a topological sort. A depth-first walk gives you one: visit a node's inputs first, then emit the node, and skip anything you've already emitted.
Each emitted node becomes one line of C that assigns a fresh temporary. Leaves (inputs and constants) don't need a line of their own.
You'll write this toposort yourself in OCaml at the end of lesson 0.6, once you've seen the language.
Evaluate postfix with a stack
Postfix (also called RPN, reverse Polish notation) writes each operator after its operands, so "23+4*" means (2 + 3) * 4. That's a toposort of the expression tree: every operator comes after the operands it uses. No parentheses or precedence rules are needed, because a stack does all the work. (A stack is a list you only add to, "push", and take from, "pop", at the top.)
Write int rpn(const char *s) for single digits 0 to 9 and the ops + - *. A digit pushes its value. An op pops b, then a, and pushes a op b. Return the one value left at the end. Inputs are always valid and at most 64 characters.
A C string is an array of characters that ends with a zero byte, so for (int i = 0; s[i] != '\0'; i++) visits every character.
Rewriting, a first look
Most of what a compiler does between parsing and printing is rewriting: find a pattern in the graph and replace it with something simpler that means the same thing. The simplest example is x * 1 → x.
That looks trivial, but "means the same thing" hides real questions. Is x * 0 → 0 safe? For integers, yes. For floats, no, because inf * 0 and nan * 0 are both nan, and -3.0 * 0.0 is -0.0, not 0.0. Week 1 is all about rules like this: which ones are safe, how to apply them until nothing changes, and how to prove the rules you wrote didn't break anything.
What makes a good IR
- Small. Every op you add is one more case for every rewrite and every backend (the part of the compiler that prints C or GPU code). The course's IR has a few dozen ops by the end, and that's enough to train an LLM.
- Uniform. Every node is the same shape: an op, a tuple of source nodes, and an argument (extra data that isn't a node, like the number inside a constant). One rewrite engine handles all of it.
- Shared. Hash consing means equal things are the same object, so "are these equal?" is a pointer comparison.
Check yourself
Drawn as a tree, how many + nodes does (a + b) * (a + b) have?
A tree never shares. Count each written occurrence of a + b.
Two. A tree gives each occurrence its own node.
Drawn as a hash-consed DAG, how many + nodes does it have?
Hash consing means asking the table before building a node. What happens the second time you build a + b?
One. The second a + b looks up the table, finds the first one, and reuses it.
What property must the order of lines in the generated C have?
The C compiler reads top to bottom. What has to already exist before a line that uses t1?
That's what makes it a topological order. Any order with this property gives correct C.
Let m = x * 2, s = m * m, out = s + s, all hash consed. Emitting one C line per non-leaf node, how many lines do you get?
Shared nodes are emitted once. List the distinct non-leaf nodes.
Three: m, s, out. x and 2 are leaves.
Same expression, but now as a tree. How many operator nodes (* or +)?
Unshare from the top: out uses s twice, and each s uses m twice.
1 + 2 + 4.
out is 1, it has two copies of s (2), and each s has two copies of m (4). 1 + 2 + 4 = 7. Each level of sharing doubles the tree.
Apply x * 1 → x everywhere it matches in (a * 1) + (b * 1). What's left?
The rule removes a multiply by 1. How many times does x * 1 appear?
a + b. The rule matches twice, once for each side.
Which of these rewrites is not safe for 32-bit floats?
Try the special float values: what is nan * 0.0? What is inf * 0.0?
nan * 0.0 is nan and inf * 0.0 is nan, so the rewrite changes the answer for those inputs. The other two hold for every float, NaN included.