Week 2 · Lesson 6

The week 2 lab

Extend your week 1 compiler with memory: buffers, views, loads, stores and versions, checked for order and bounds. Then teach it to print C. You're done when every week 2 test passes, week 1 still passes, and you've written 10 new tests of your own.

What you're building

Warm up

One small program where rule 3 matters: a load of an old version that has to run before the store that overwrites it.

Rotate three elements

The starter is meant to rotate slot 0 left, so [a b c] becomes [b c a], but one load reads the wrong version. Fix it. Keep it valid: every store sequenced, one store per version.

The command-line contract

Week 1's run and simplify still apply, unchanged. Week 2 adds memory to run, and adds render.

commandresult
your.exe run FILESame exit codes and stderr lines as week 1: 0, 1 with assert failed: %name, or 2 with a line starting invalid:. Ordering violations, unprovable bounds and memory used as a value are all static errors (exit 2). You may interpret or compile, and the grader only sees the exit code and stderr.
your.exe render FILEPrint C to stdout that defines void kernel(T0 *b0, T1 *b1, ...), one pointer per buffer in slot order (float, int32_t, bool). Asserts are ignored. No for, while, do or goto, and no calls outside the file except <math.h> (non-recursive helpers you define in the same file are fine).

How render tests are graded

A render test is a valid program with a # render header. For each one, the grader:

  1. runs your.exe render FILE and fails the test on a nonzero exit;
  2. removes comments and string literals from your C and fails it if for, while, do or goto appears;
  3. writes its own main: one static array per buffer, filled with the data values (f32 copied in from exact bit patterns), then a call to your kernel in slot order, then one line per element (f32 as 8 hex digits of bits);
  4. compiles both files with clang -std=c11 -O2 -ffp-contract=off -fsanitize=undefined -fsanitize-trap=undefined ... -lm (with gcc, the equivalent trap flag);
  5. runs the program, and compares every element of every buffer with the oracle: i32 and bool exactly, f32 bit for bit, with any NaN matching any NaN.

A crash in step 5 almost always means undefined behavior that the sanitizer turned into a trap: signed overflow, INT_MIN / -1, a bad shift. One Windows quirk: a naive INT_MIN / -1 there tends to hang in the system error reporter instead of crashing, so you'll see "didn't finish" rather than "crashed". Check your div and mod first.

Running the suite

From the course repo root, and keep week 1 green while you work:

python tools/test.py --compiler "C:/path/to/your.exe" --week 2
python tools/test.py --compiler "C:/path/to/your.exe" --week 2 -k render -v   # just the render tests, with details
python tools/test.py --compiler "C:/path/to/your.exe" --week 1                # nothing from last week broke

Tests live in tests/week2/run/ and tests/week2/render/. Read a few before you start: they're short, and the file names say what each one checks.

Write your 10 tests

Same deal as week 1: 10 tests in <your compiler repo>/tests/week2/, each aimed at a rule someone will get wrong. Run tests use # expect: pass, assert_fail or invalid, and render tests use # render. Check them against the oracle:

python tools/test.py --check-tests <your compiler repo>/tests/week2

For a render test, --check-tests renders it with the oracle, compiles it with the same harness, and checks the buffers. Good targets: two stores into one version (invalid), a load of an old version after the store (a swap), an offset from a loaded value with and without a mod mask, a wrapping mul in a render test, and max on NaN and -0.0.

A build order that works

  1. Parse the new ops

    buffer and alloc take a size literal. buffer has slot= and optional data=[...], and shrink takes an offset operand and shape=[k] or shape=[]. Two allocs of the same size are different storage, so they must not hash cons into one node.

    Checkpoint: every file in tests/week2/run/ parses or is rejected with exit 2.

  2. Type memory

    Give every node an addrspace. Memory can be an operand of shrink, load, store and after, and nothing else.

    Checkpoint: the "memory used as a value" invalid tests exit 2.

  3. Bounds

    Reuse your week 1 intervals. A loaded value's interval is the full i32 range.

    Checkpoint: the masked-offset tests pass and the unmasked ones exit 2.

  4. Ordering checks

    Find each store's version by walking shrinks down to a buffer, alloc or after. Count stores per version and afters per store. Then try to schedule: if every load of V can't come before the store that overwrites V, the program is invalid.

    Checkpoint: all ordering invalid tests exit 2, and the swap tests pass.

  5. Interpret memory

    Versions are values: after produces a new array with one write applied. Copying is fine at this size.

    Checkpoint: every week 2 run test passes.

  6. Render ALU ops

    One function from op to C expression, with the safe spellings from lesson 4. Test it by rendering week 1 style arithmetic into a buffer.

    Checkpoint: render tests with only i32 math pass, including the wrapping ones.

  7. Render memory and the schedule

    Views become pointer plus offset, after prints nothing, loads of a version go before the store that overwrites it. Then f32: hex literals, NaN and infinities, the max helper.

    Checkpoint: every render test passes, bit for bit.

  8. Your 10 tests

    Write them, check them with --check-tests, and use them to break your compiler before the suite does.

Checklist

The AI policy, still

Your repo's AGENTS.md hasn't changed: an AI assistant may explain concepts, draw diagrams, and help you debug by asking questions, but must never write or rewrite compiler code. This week that includes your renderer and your runtime. Asking "why does my kernel trap on this test?" is fine. Asking for the C your renderer should print is not.

The oracle in _reference/ is still off limits to read. Running python _reference/uirc.py render FILE to see what it prints for one of your own tests is fine: it's the same as asking the oracle a question.

Slop compounds, again

Week 3 adds loops, and your renderer and runtime become the core of everything after that. A renderer built from string concatenation scattered across the type checker will be rewritten in two weeks. Keep one function per job: schedule, name, print.

Check yourself

Your render output starts every kernel with a for loop that zeroes a scratch array. What happens?

Look at step 2 of how render tests are graded.

The grader rejects any for, while, do or goto outside comments and strings. Zero an alloc with an initializer, = {0}, instead.

What exit code should run give?

%b  = buffer 2 dtype=i32 slot=0
%e  = shrink %b 0 shape=[]
%s1 = store %e 1
%s2 = store %e 2
%b1 = after %b %s1
%b2 = after %b1 %s2

Which version does %s2 write into? Count the stores into that version.

2. Both stores write through %e, a view of %b, so version %b has two stores, which is unordered. On top of that, after %b1 %s2 names %b1 while %s2 writes into %b. Either problem alone makes it invalid.

The grader says "your kernel crashed (exit ...)" on a test that only does i32 add and mul. What's the most likely cause?

The grader compiles with -fsanitize-trap=undefined. Which of these is undefined behavior in C?

Signed overflow. A missing include would fail to compile, not crash, and a rounding difference would show up as a wrong value. Wrap through uint32_t.

Which of these may you do this week?

Running the oracle is asking it a question. Reading its source, or getting compiler code written for you, isn't.

Running the oracle on your own tests is fine. Reading its source spoils the puzzle, and the AI policy rules out having your compiler code written for you.