Week 4 · Lesson 6

The week 4 lab

Teach your compiler to take whole-vector programs and turn them into loops itself: rank-1 ALU, reduce, expand and stage in the type checker and interpreter, and a rangeify pass in front of your week 3 renderer. You're done when every week 4 test passes, weeks 1 to 3 still pass, and you've written 10 new tests of your own.

What you're building

Warm up

A dot product is a whole-vector program in two ops.

Warm-up: a dot product

Slots 0 and 1 are a and b (4 f32 each). Write their dot product, the left fold of a[i] * b[i], into the one-element buffer in slot 2. No hand-written range.

The command-line contract

Nothing new on the command line. What changes is which programs the commands accept and what render may print.

commandweek 4 changes
your.exe run FILEPrograms may use rank-1 ALU, expand, reduce and stage. A shape mismatch, an expand that grows an axis that isn't size 1, a reduce of a scalar or with a missing or unknown op, or a rank-1 value that depends on an open range from a hand-written loop is a static error: exit 2 with an invalid: line.
your.exe render FILEThe C must be at most 20,000 bytes. It may use for loops when the program contains a range, a reduce, an expand, a stage, an elementwise op on a rank-1 value, or any rank-1 value with more than 32 elements (so a plain 4096-element copy may loop too). Otherwise it stays loopless, as in week 2.

How render tests are graded

For each # render test, the grader goes through five steps in order:

  1. Runs your.exe render FILE and fails the test on a nonzero exit.
  2. Fails the test if your output is over 20,000 bytes (counted as UTF-8).
  3. Parses the program with the oracle to decide whether loops are allowed (the rule in the table above), strips comments and string literals from your C, and fails the test if it finds while, do or goto, or for when loops aren't allowed.
  4. Writes its own main and compiles both files with clang -std=c11 -O2 -ffp-contract=off -fsanitize=undefined -fsanitize-trap=undefined ... -lm.
  5. Runs it and compares every element of every buffer with the oracle: i32 and bool exactly, f32 bit for bit, any NaN matching any NaN.

The bit-for-bit comparison is what makes the fold order matter. A reduce that folds right to left turns 1e8, 1, -1e8, 1 into 0 instead of 1, and one that starts from 0.0f turns a lone -0.0 into +0.0. Either way the bits differ and the test fails.

Running the suite

From the course repo root, and keep every earlier week green:

python tools/test.py --compiler "C:/path/to/your.exe" --week 4
python tools/test.py --compiler "C:/path/to/your.exe" --week 4 -k render -v   # the render tests, with details
python tools/test.py --compiler "C:/path/to/your.exe" --week 3
python tools/test.py --compiler "C:/path/to/your.exe" --week 2
python tools/test.py --compiler "C:/path/to/your.exe" --week 1

Pass the built executable, not dune exec: the grader runs tests in parallel.the same wrapper script as in week 1. Tests live in tests/week4/run/ and tests/week4/render/.

Write your 10 tests

Ten tests in path/to/your-repo/tests/week4/, each aimed at a rule someone will get wrong. Check them against the oracle:

python tools/test.py --check-tests path/to/your-repo/tests/week4

Good targets: a reduce whose bits depend on the fold order, a one-element reduce, and reduce op=max over a vector containing NaN. Also try an add of a vector and a scalar without expand (invalid), and a value used by a reduce and a store, once with stage and once without (same answer). Finish with a render test with a vector long enough that unrolling breaks the size limit.

A build order that works

  1. Shapes on ALU ops

    Change the ALU type rule from "every operand is a scalar" to "every operand has the same shape". The result has that shape.

    Checkpoint: the shape-mismatch tests exit 2, and every week 1 test still passes.

  2. Parse and type expand, reduce, stage

    expand needs a scalar and shape=[n] (week 5 widens it to grow size-1 axes). reduce needs a vector and op=, and stage keeps its operand's type. Rank-1 values may not depend on an open range.

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

  3. Vectors in run

    Evaluate rank-1 values as arrays: elementwise ops per element, expand as n copies, stage as the identity, and reduce as a left fold seeded with element 0, rounding after every step.

    Checkpoint: every week 4 run test passes.

  4. The element at an index

    Write the lowering as two mutually recursive functions: one that rebuilds scalars and effects, and one that answers "your element at index i" for a vector. Memoize both, so a value asked twice at the same index is built once.

    Checkpoint: print the lowered graph for store %y (mul %v (expand 2.0)) and find no rank-1 nodes in it.

  5. Stores and reduces become loops

    A rank-1 store becomes range n, a scalar store at the index, and end. A reduce becomes a seeded one-element accumulator and a loop over 1..n-1, exactly week 3's pattern.

    Checkpoint: the small render tests pass bit for bit.

  6. Stage becomes a temp

    A staged vector gets its own alloc, filled once in its own loop. Its element at an index is a load from that temp.

    Checkpoint: staged and unstaged versions of the same program leave identical bits.

  7. Check the size

    Render the 4096-element tests and measure them. If the output grows with n, something reached the printer without being rangeified.

    Checkpoint: every render test passes, and your largest kernel is around a kilobyte, whatever n is.

  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. That includes your rangeify pass. "Why does my staged program give different bits from the unstaged one?" is a fine question. "Write my element-at-index function" is not.

The oracle in _reference/ stays closed. Running python _reference/uirc.py render FILE on your own test to see the loops it produces is fine.

Check yourself

Your renderer passes every small week 4 render test but fails the 4096-element ones with a size error. What's the likely cause?

Which kind of code grows with n?

Only unrolled code grows with the vector length. Fold order would show up as wrong bits, and stage never changes the result or makes the code grow with n.

May the rendered C for this program contain a for loop?

%x = buffer 4 dtype=f32 slot=0
%y = buffer 4 dtype=f32 slot=1
%v = load %x
%t = mul %v %v
%s = store %y %t
%y1 = after %y %s

Read the loop rule in the contract table.

mul %v %v is an ALU op on a (4,) value, which is enough for the grader to allow for loops. The size threshold in the rule is 32 elements, not 16, and it applies to any rank-1 value even without an ALU op.

What exit code should run give?

%x = buffer 4 dtype=f32 slot=0
%v = load %x
%w = add %v 1.0
%s = reduce %w op=add
%t = assert %s 4.0

What shapes does the add see?

2. %v is (4,) and 1.0 is a scalar, and there is no implicit broadcast, so the add is a type error. It needs expand 1.0 shape=[4].

Your staged and unstaged versions of the same program give different bits. Where is the bug?

Lesson 4.4: what can stage change?

Stage changes work and memory traffic, never the result. Different bits mean your two lowerings compute different things, often a reduce that folds the temp in a different order than the recomputed value.