Week 1 study guide

Week 1 builds the core everything else stands on: the hash-consed UOp, a type checker, an interpreter, and a rewrite engine that simplifies programs. This page recaps it, collects the rules worth memorizing, and walks the lab one step at a time.

The week in one page

1.1 The UOp

A program is a DAG of UOp(op, src, arg) nodes, each with a dtype and a shape. Hash consing makes two structurally equal nodes the same node, so equality is one comparison and shared work is computed once. Without sharing, a 300-level doubling DAG would take 2³⁰⁰ steps.

1.2 .uir and interpreting

Each line is %name = op operands attrs. Every statement is type checked first. Then asserts run in file order, and the first failure or runtime error stops the program. i32 wraps, division truncates like C, and every f32 op rounds to f32.

1.3 Rewrites and folding

A rewrite rule is a pattern and a replacement, like add(x, 0) → x. The engine visits sources first, applies rules until none fire, and repeats passes until nothing changes. Constant folding is the rule family "all inputs are constants, so compute it now", and it must never fold away a runtime error.

1.4 Symbolic simplification

i32 is a ring mod 2³², so reassociation is always safe. f32 isn't, so x * 0.0 and x + 0.0 can't simplify. Bounds analysis gives each i32 value an interval, which proves rules like cmplt(mod(max(x, 0), 8), 8) → true.

1.5 CALL, PARAM, STACK, INDEX

A call binds argument i to param i in its body. Bodies are closed: substitution stops at a nested call's body but goes into its arguments. A param's value depends on which call is evaluating it, so values are cached per call, not globally.

1.6 Lab

Your compiler takes run FILE (exit 0, 1 or 2, with exact stderr lines) and simplify FILE (print a smaller equivalent %out). The suite has 142 tests, and every bug planted in the reference compiler to test them fails at least one.

Cheat sheet

op	operand dtypes	result	remember
`add`, `mul`	i32 or f32, same	same	i32 wraps, f32 rounds
`max`	i32 or f32	same	NaN if either is NaN, and `max(-0.0, 0.0) = +0.0`
`div`, `mod`	i32	i32	truncate toward zero, mod takes the dividend's sign, by 0 is a runtime error, and `INT_MIN / -1 = INT_MIN`
`shl`	i32	i32	wraps, and a shift outside 0..31 is a runtime error
`xor`	i32 or bool	same	bitwise / logical
`cmplt`	i32 or f32	bool	any NaN gives false
`where c a b`	bool, then same	a's	strict: both branches evaluated
`cast a dtype=D`	any but void	D	f32→i32 truncates, and NaN, inf, or out of range is a runtime error
`recip`	f32	f32	`recip 0.0 = inf`, `recip -0.0 = -inf`
`assert a b`	same	void	f32 by value: `0.0 == -0.0`, NaN equals NaN

exit	stderr must contain	when
0	anything	every assert passed
1	exactly one line `assert failed: %name`	the first failing assert, in file order
2	a line starting `invalid:`	parse or type error anywhere, or a runtime error in a value an assert needs

simplify rule	i32	f32
`x + 0 → x`	yes	no (`-0.0 + 0.0 = +0.0`), but `x + -0.0 → x` is fine
`x * 1 → x`	yes	yes
`x * 0 → 0`	yes	no (`nan * 0.0 = nan`)
`(x + c1) + c2 → x + (c1 + c2)`	yes (a ring)	no (rounding)
`(x * c) / c → x`	only when bounds prove no wrap	no

python tools/test.py --compiler YOUR_COMPILER --week 1           # grade
python tools/test.py --compiler YOUR_COMPILER -k call -v         # one topic, details
python _reference/uirc.py run FILE                               # what should this do?

YOUR_COMPILER is the command that runs your compiler: the wrapper script from lesson 0.7, such as "C:/path/to/my-ml-compiler/mlc.cmd" on Windows or ~/my-ml-compiler/mlc on macOS and Linux.the path to the main.exe that dune built.

Mistakes people make

Each of these is a bug that was planted in the reference compiler to prove the suite catches it. The week 1 test guide lists every test with the bugs known to fail it.

Using your language's native int for i32. Python's ints never overflowOCaml's is 63 bits, so 2147483647 + 1 never wraps. Caught by i32_wrap_add and i32_wrap_mul.
Dividing like Python's //. Floor division gives -7 / 2 = -4, but the spec says -3. Caught by i32_div_trunc and i32_mod_sign.
Doing f32 math in doubles without rounding. Every op must round to f32, including the literals. Caught by f32_tenths, f32_rounding_step and f32_literals.
Evaluating without memoization. A tree walk of a shared DAG is exponential. Caught by dag_sharing_300 (it times out).
One global cache across calls. The same body called with 3 and with 4 then returns the same thing twice. Caught by call_memo_per_call.
Substituting into a nested call's body. Bodies are closed. Caught by call_closed_body and the simplify test trap_nested_call.
Type checking lazily. A bad line no assert uses still makes the program invalid. Caught by err_type_static and err_call_missing_arg_unused.
Checking asserts out of order, or stopping at the wrong error. Caught by fail_first_in_order, fail_before_error and error_before_fail.
Simplifying f32 like i32. x * 0.0 → 0.0 and x + 0.0 → x are wrong. Caught by trap_mul_zero_f32 and trap_add_zero_f32.
Letting an uncaught exception decide your exit code. In OCaml, Fatal error: exception Division_by_zero exits 2 but has no invalid: lineIn Python, a ZeroDivisionError traceback exits 1, which looks like a failed assert with no assert failed: line, so every invalid test fails. Catch your exceptions, print a diagnosis starting invalid:, and exit 2.

Stuck on the lab?

Build in this order, and don't move on until the check passes. Each check is a tiny program: save it, run it through your compiler and through the oracle (python _reference/uirc.py run FILE), and compare exit codes.

Parse and print. Done when you can print every statement back in .uir form. Check: %a = add 2 3 / %t = assert %a 5 should exit 0. If a later test reports a parse error, look at literals first: 1., .5 and 1E5 are floats, +1 and 0x10 are not.
The hash-consed UOp. Done when building the same node twice gives back the identical node. Check: the suite's dag_sharing_300 runs in milliseconds. If it hangs, your table key hashes or compares whole subtrees instead of child ids or identities.
Types. Done when every type error is reported before anything runs. Check: %a = add 1 1.0 / %t = assert 1 1 must exit 2 with an invalid: line, even though no assert uses %a.
Interpreter. Done when asserts pass and fail correctly. Check: %a = div -7 2 / %t = assert %a -3 / %b = mod -7 2 / %u = assert %b -1 exits 0. If it exits 1, your division floors.
call and param. Done when bodies are closed and values are cached per call. Check: %p0 = param 0 dtype=i32, %p1 = param 1 dtype=i32, %inner = add %p0 100, %outer = call %inner %p1, %r = call %outer 1 2, %t = assert %r 102 exits 0. If you get 101, substitution went into the nested body.
The rewrite engine. Done when simplify folds constants. Check: %x = param 0 dtype=i32, %k = mul 3 4, %out = add %k %x should print a program whose %out is add of the param and 12, one op.
Symbolic rules and bounds. Done when cmplt (mod (max %x 0) 10) 10 simplifies to true but cmplt (mod (max %x 0) 10) 9 does not (written as separate statements). If the second also folds, your comparison is off by one.

When a test fails and none of this fits

Rerun it alone with -k NAME -v, copy the test file, delete lines until it still fails, and compare with the oracle on the smallest version. The debugging guide walks through it.

Check yourself

What does %a = shl 3 30 give in .uir (i32)?

3 · 2³⁰ = 3,221,225,472, which is more than INT_MAX. Subtract 2³².

3221225472 - 4294967296 = -1073741824. shl wraps like add and mul.

What does %a = cast 2.9999999 dtype=i32 give?

The literal is rounded to f32 before the cast. How close to 3 can an f32 get?

Near 3, f32 values are about 0.00000024 apart, so 2.9999999 rounds to exactly 3.0, and truncating 3.0 gives 3. A cast of a value that really is below 3 would give 2.

What does %a = mod 2147483647 -2 give?

In C-style mod, the sign of the result follows the left operand.

INT_MAX is odd and positive, so the remainder is 1. The divisor's sign doesn't matter.

This program has an unused division by zero and a failing assert. What does run exit with?

%a = div 1 0
%t = assert 1 2

Runtime errors only matter in values an assert depends on.

No assert uses %a, so the division never runs. The assert fails, so the exit is 1.

What does %r evaluate to?

%p0    = param 0 dtype=i32
%inner = add %p0 1
%outer = call %inner 10
%r     = call %outer 5

What does %outer's body depend on? Does it use any param of its own?

%outer's body is call %inner 10, which is 11 and uses no param of %outer. The 5 is an extra argument and is ignored.

With hash consing, how many distinct nodes does this program build, counting the constants?

%a = add 1 2
%b = add 1 2
%c = mul %a %b
%d = mul %b %a

Which statements are the same node? Once %a and %b are one node, what are %c and %d?

The constants 1 and 2 (two nodes), one add, and one mul of that add with itself: %c and %d are the same node. Four in total.

Which simplification is wrong for an f32 %x?

Try each with x = -0.0, and remember the grader compares f32 bit for bit.

-0.0 + 0.0 = +0.0, so the result changes sign. Adding -0.0 keeps every value's bits, including -0.0.

Can bounds analysis simplify cmplt (mod (max %x 0) 10) 9?

What interval does mod (max %x 0) 10 have?

The interval is [0, 9]. Values 0 to 8 are less than 9 and 9 is not, so the comparison depends on %x. Against 10 it would fold to true.

More practice: the week 1 quiz review.

Go deeper

tinygrad and its documentation. The UOp, rewrite rules and symbolic simplification here follow tinygrad's design, and reading its pattern matcher shows the production version.
The 10-411 technical syllabus. The source this course is built from.
Hash consing. The idea, its history, and where else it's used.
Interval arithmetic. The math behind bounds analysis, including why it's always safe but sometimes loose.
The Floating-Point Guide, then What Every Computer Scientist Should Know About Floating-Point Arithmetic (Goldberg). Short first, thorough second: why f32 rewrites are so restricted.
Crafting Interpreters. A free book on parsing and tree-walking interpreters, a gentle companion to lessons 1.2 and 1.3.
PEP 636: Structural Pattern Matching tutorial. How match with class patterns works, the natural way to write rewrite rules in Python.
Real World OCaml: Maps and Hash Tables. Hash tables with your own key module, the tool behind hash consing.
Python and OCaml, deeper. This week's idioms in your language: hash-consing keys, rewrite rules as matches, and i32 and f32 by hand.

Challenges

Tighter mod bounds. The oracle widens mod x c to [-(c-1), c-1] when x can be negative. Find a program where a tighter rule would let simplify remove one more op, and check your rule never changes a value by running both versions through the oracle with a few params.
A rule the oracle doesn't have. Find a valid i32 identity the reference simplifier misses (for example something with xor or max). Write it as a simplify test with a smaller max_ops and check that python tools/test.py --check-tests DIR (the folder holding your test) rejects it, which proves the oracle doesn't reach it yet.
Break the grader. Write a wrong simplification that you think the grader's edge-case inputs won't catch. If you find one, you've found a hole in the course: the cross product covers every edge value in every slot, so think about values that aren't edges.