Week 2 study guide

Week 2 adds memory and turns your compiler into one that prints C. The ideas are few but strict: memory comes in versions, every access has to be provably in range, and the C you print must have no undefined behavior.

The week in one page

2.1 Buffers and views

A buffer is memory outside the program, given to the kernel by slot. An alloc is scratch memory inside it, zeroed. shrink makes a view: a window starting some elements in, either [k] elements or a single element (shape=[]). Memory is never an ALU operand, so you load it first.

2.2 Load, store, after

A store doesn't change a buffer in the graph. after %b %s is the new version with the write applied, and loads read whichever version they name. "Fully ordered" means one store per version, every store sequenced by an after, and every load of a version able to run before the store that overwrites it.

2.3 Proving bounds

Every view must be provably inside its parent, using week 1's intervals: the offset's interval needs lo ≥ 0 and hi + k ≤ n. A value loaded from memory could be anything, so you mask it (max, mod) into range before using it as an offset.

2.4 Rendering C

Rendering schedules the DAG into straight-line C: sources first, and loads of a version before the store that overwrites it. Each i32 op is written so C has no undefined behavior (wrap through uint32_t, guard INT_MIN / -1), f32 literals are printed as exact hex floats, and the grader forbids fused multiply-add.

2.5 The runtime

To run the C, write the kernel and a generated main to a temp folder, compile, run, and read the results back, printing f32 as raw bits so nothing is lost. It's optional this week, but kernels get timed from week 6.

2.6 Lab

run keeps its week 1 contract with memory added, and render prints a kernel the grader compiles with UB trapping and compares bit for bit against the oracle. The week 2 suite has 99 tests. Keep week 1 green too.

Cheat sheet

op	gives	remember
`buffer n dtype=D slot=S data=[...]`	memory (n,)	slots unique, and no data means zeros
`alloc n dtype=D`	memory (n,)	local, zeroed, and not an output. Each alloc is its own storage
`shrink m off shape=[k]` / `shape=[]`	a view	offsets of nested shrinks add up and must be provably in range
`load v`	a value	reads the version it's given
`store v x`	void	must be sequenced by exactly one `after`
`after m s`	memory	the version of m once s happened, where m is a whole version, not a view

rule	statement
one store per version	two stores into the same version are unordered, even into different elements
every store sequenced	a store no `after` names has no effect and is invalid
loads before stores	a load of version V runs before the store that makes the next version, even if its value is used much later. This is always possible, so it's never an error, but your C must schedule it that way
bounds	offset interval: `lo ≥ 0` and `hi + k ≤ n` (`k = 1` for `shape=[]`), and loaded values are full range
outputs	the final version of each buffer: the one no `after` builds on

rendering	write it as
i32 `add`, `mul`, `shl`	`(int32_t)((uint32_t)a + (uint32_t)b)`
i32 `div`, `mod`	guard `b == -1`: `INT_MIN / -1` is undefined in C
f32 constants	hex floats, e.g. `0x1.99999ap-4f`, plus `NAN` and `INFINITY`
f32 `max`	a same-file helper: NaN if either is NaN, `max(-0.0, 0.0) = +0.0` (not `fmaxf`)
grader flags	`clang -std=c11 -O2 -ffp-contract=off -fsanitize=undefined -fsanitize-trap=undefined`
allowed calls	`<math.h>` and non-recursive helpers defined in the same file, with no loops in week 2

Mistakes people make

Each was planted in the reference compiler and caught by the suite. The week 2 test guide lists every test with the bugs known to fail it.

Forgetting that nested shrink offsets add up. A view of a view starts at the sum of both offsets. Caught by view_shrink_of_shrink and the render test nested_view_offsets.
Letting two stores share a version. Even two stores into different elements of the same version are unordered. Caught by err_two_stores_one_version.
Allowing a store nothing sequences. Caught by err_unsequenced_store.
Treating every alloc as the same memory. Two allocs of the same size are separate storage. Caught by alloc_distinct and alloc_two_distinct.
Skipping the bounds proof for a loaded index. A raw loaded value can be anything. Caught by err_bounds_raw_loaded. The masked version passes in bounds_masked_offset.
Scheduling a store before a load of the version it overwrites. In C, memory is updated in place. Caught by swap, old_version_late_use and swap_schedule.
Printing plain signed C. a + b on int32_t traps under the grader's UB sanitizer. Caught by i32_add_wrap, i32_mul_wrap and i32_shl_wrap.
No -1 guard on div and mod. Caught by i32_div_mod_intmin. On Windows the unguarded version can hang instead of trapping.
Using fmaxf for max. fmaxf(NAN, 1.0f) is 1, but the course's max gives NaN. Caught by f32_max.
Printing f32 constants with too few digits. Six decimal digits can't round-trip every float. Caught by f32_exact_literals.

Stuck on the lab?

Build in this order. Each check is a tiny program to run through your compiler and through the oracle (python _reference/uirc.py run FILE, or render FILE).

Parse the new ops. Done when buffer, alloc, shrink, load, store and after parse with their attributes. Check: %b = buffer 3 dtype=i32 slot=0 data=[1 2 3], %v = shrink %b 1 shape=[2], %l = load %v, %e = index %l 1, %t = assert %e 3 exits 0.
Type memory. Done when memory can't be used as a value. Check: %b = buffer 2 dtype=i32 slot=0, %a = add %b 1, %t = assert 1 1 must exit 2.
Bounds. Done when views are proven with week 1's intervals. Check: an offset of mod (max %x 0) 4 with shape=[2] passes on a 5-element buffer and fails on a 4-element one (the interval is [0, 3], and 3 + 2 must be at most n). If both pass, you aren't checking at all. If both fail, your mod interval is too wide.
Ordering checks. Done when two stores into one version, or an unsequenced store, exit 2. Check: %b = buffer 2 dtype=i32 slot=0, %e = shrink %b 0 shape=[], %s1 = store %e 1, %t = assert 1 1 must exit 2.
Interpret memory. Done when versions behave. Check: with %b holding [10 20], load element 0 as %x, store 5 into it, take %b1 = after %b %s, load element 0 of %b1 as %y. Then add %x %y must be 15. If you get 10, your load of %b saw the store.
Render ALU ops. Done when every op prints UB-free C. Check: python tools/test.py --compiler PATH --week 2 -k i32_ -v. A crash with exit code 132 or similar means the sanitizer trapped undefined behavior.
Render memory and the schedule. Done when loads come before the stores that overwrite their version. Check: -k swap -v. A swap that copies the same value into both slots means a store was printed too early.

When a test fails and none of this fits

Rerun it alone with -v, shrink it to the fewest lines that still fail, and compare with the oracle's output. For render tests, python _reference/uirc.py render FILE shows the C the oracle would print. The debugging guide has the full routine.

Check yourself

What does %e hold?

%b = buffer 3 dtype=i32 slot=0 data=[1 2 3]
%v = shrink %b 1 shape=[2]
%l = load %v
%e = index %l 1

The view starts at element 1 and is 2 long. Index 1 of the view is which element of the buffer?

The view covers buffer elements 1 and 2, so it holds [2 3], and index 1 is 3.

An offset is mod (max %x 0) 4 with %x loaded from memory, and the view is shape=[2]. What's the smallest buffer size for which the view is provably in bounds?

The offset's interval is [0, 3]. The rule is hi + k ≤ n.

3 + 2 = 5, so n must be at least 5. On a 4-element buffer the oracle reports "offset in [0, 3], 2 element(s), parent has 4".

With %b holding [10 20], what is %z?

%e  = shrink %b 0 shape=[]
%x  = load %e
%s  = store %e 5
%b1 = after %b %s
%e1 = shrink %b1 0 shape=[]
%y  = load %e1
%z  = add %x %y

Which version does each load name?

%x reads the original version (10) and %y reads the version after the store (5), so 15.

Two stores write to different elements of the same buffer version, and one after sequences the first. What does run exit with?

The rule is about versions, not elements.

Two stores into one version are unordered no matter which elements they touch, and the second store isn't sequenced either. The oracle exits 2.

Which line is safe C for an i32 add under the grader's flags?

Which of these can overflow a signed type? A cast only acts on the value it's given.

Unsigned arithmetic wraps by definition, and converting back to int32_t wraps on every compiler you'll use. Option a overflows a signed int, which traps under -fsanitize-trap. Option c is the same signed add: the cast comes after the overflow, too late to help.

Why does the grader compile with -ffp-contract=off?

A fused multiply-add rounds once instead of twice.

The spec rounds after every op. A fused multiply-add skips the rounding of the product, which can change the last bit and fail a bit-exact comparison.

What does run exit with?

%b = buffer 2 dtype=i32 slot=0
%e = shrink %b 0 shape=[]
%s1 = store %e 1
%t = assert 1 1

Is the store sequenced by anything?

No after names %s1, so it has no effect, which the spec makes an error: exit 2.

What does C's fmaxf(NAN, 1.0f) return, and what must your rendered max return for the same inputs?

fmaxf treats NaN as "missing data".

fmaxf returns the other operand when one is NaN. The course's max propagates NaN, so you need your own helper.

More practice: the week 2 quiz review.

Go deeper

Clang's UndefinedBehaviorSanitizer. What the grader's -fsanitize=undefined catches, and what it doesn't.
A Guide to Undefined Behavior in C and C++ (John Regehr). Why a compiler is allowed to break code with signed overflow.
What Every Computer Scientist Should Know About Floating-Point Arithmetic. The background for fused multiply-add, rounding, and exact literals.
tinygrad. Its renderers print C (and GPU code) from UOps much as you're doing this week. Reading how it names values and orders memory operations is a good comparison.
Interval arithmetic. The theory behind the bounds proofs, and why they're sound.
float.hex and subprocess. Exact hex float literals for your C, and running clang and your kernel with a timeout.
Printf, for %h hex floats, and Real World OCaml: Functors, for organizing passes as modules.
Python and OCaml, deeper. This week's idioms in your language: a C emitter, exact literals, bounds, and the runtime.

Challenges

Smallest correct C. Make your renderer skip the -1 guard when the divisor is a constant that isn't -1, and skip the uint32_t casts when bounds prove an add can't overflow. Check that every render test still passes.
A program the ordering rules reject but C could run. Find one, and explain which rule rejects it and why the rule is still worth having. Use python _reference/uirc.py run FILE to confirm it's rejected.
Tighter bounds through where. where (cmplt %i 4) %i 0 is in [0, 3] when %i ≥ 0, but the interval of a where is the union of its branches. Sketch an analysis that uses the condition, and find a program it would accept that the oracle rejects.