Week 4 · Lesson 3

Rangeify

The syllabus puts it in one line: "rangeify removes shapes from all ops." Your run can evaluate vectors directly, but your render can't unroll a 4096-element vector into 4096 lines of C. It has to turn every vector back into a loop, and the way to do that is to ask each value one question: what is your element at index i?

One question per value

Pick an index variable i. Every vector value can answer "what is my element at i" with a scalar graph, and the answers are short:

value	its element at `i`
an elementwise op `add %a %b`	`add` of a's element at i and b's element at i
`load` of a view at offset o	a scalar load of `shrink view i shape=[]`, element `o + i`
`expand %s shape=[n]`	`%s` itself: the index doesn't matter
`stack a b c`	`index` of the stack at i

The answers recurse: asking the add asks both operands, with the same i. Elementwise is what makes that work. Element i of the result never needs element i + 1 of anything, so one index flows down the whole graph and every shape disappears on the way.

Two things consume a vector and produce a scalar or an effect, and those are where the loops come from:

A rank-1 store becomes a loop: range n, then store element i of the value into element i of the view, then end.
A reduce becomes an accumulator loop, exactly week 3's pattern: seed a one-element alloc with the element at 0, loop over 1 to n-1 folding in the element at each index, and load the result after the loop.

That's the oracle's real output for store %y (mul (load %x) (expand 2.0)) on four floats: one loop, with the constant folded right into the loop body because expand's element at any index is just 2.0. In the C, 0x1.0000000000000p+1f is 2.0 written as a hex float, which round-trips exactly (lesson 2.4).

reduce becomes an accumulator loop

Here's what the oracle renders for reduce (load %x) op=add on four floats, stored into a one-element buffer. Compare it with lesson 3.2's accumulator:

float a4[1] = {0};
float v7 = b0[0];                /* the element at 0 seeds the fold */
a4[0] = v7;
for (int32_t r14 = 0; r14 < 3; r14++) {
  float v15 = a4[0];             /* loop-carried: reloaded every iteration */
  int32_t v16 = (int32_t)((uint32_t)r14 + (uint32_t)1);
  int32_t v17 = (v16 % 4);       /* decoding the flat counter; always equal to v16 here */
  float v19 = b0[v17];           /* the element at r + 1 */
  float v20 = (v15 + v19);
  a4[0] = v20;
}
float v24 = a4[0];
b1[0] = v24;

The % 4 line comes from decoding a flat loop counter back into an index. Here r + 1 is always below 4, so it's provably redundant. Lesson 5.5 shows how a simplifier removes lines like it.

The loop runs n-1 times over indices 1 to n-1, so the fold is left to right from x[0], as the spec requires. The accumulator's load sits inside the loop because of week 3's placement rule: its only use is in the loop, and the loop stores into the version it reads.

Rangeify reuses everything you built

After rangeify, the graph has no vector values left: only scalars, range, end, alloc, loads and stores. That's a week 3 program, and your week 3 renderer already knows how to place each value at the right loop depth and print it. Week 4's new work is entirely in the lowering.

The element at index i

On a toy type of vector expressions (buffers, broadcasts, adds and multiplies), write at e i: the scalar expression for element i of e. The printer is given.

Why the C must be small

Week 4 render tests include vectors of 4096 floats, and the grader rejects rendered C over 20,000 bytes. A renderer that kept vectors as C arrays and unrolled every elementwise op would emit thousands of lines, but a rangeified one emits a few loops no matter how big n is. The x / sum(x) example from lesson 4.2, on 4096 floats, renders to about 800 bytes (801 with the current oracle) with two loops: the reduce's 4095 iterations, then the 4096-iteration store.

The reduce loop in C

Write float sum_left(const float *x, int n) (with n ≥ 1) so that it computes exactly what reduce op=add does: start from x[0], then add x[1] to x[n-1] in order. The starter is right for every input but one kind. The tests compare the 32 bits of your result, printed in hex, so -0.0 (80000000) and 0.0 (00000000) differ.

Check yourself

What is the element at i of add %a %b, where both are vectors?

What does "elementwise" promise about which elements an op reads?

An elementwise op's element i depends only on its operands' elements i, so the same index flows down to both operands.

What is the element at i of expand %s shape=[4096]?

Does the answer depend on i at all?

Every element of a broadcast is the same scalar, so its element at any index is %s. That's why a broadcast costs nothing in the generated loop.

How many for loops does the oracle render for x / sum(x) (reduce, recip, expand, mul, then a rank-1 store) on 4096 floats?

Which two ops turn into loops?

The reduce becomes one loop and the rank-1 store another. The recip is a scalar, computed once between them, and the expand disappears into the store loop.

In that rendering, how many iterations does the reduce loop run?

Where does the fold start, and what's left to add?

The accumulator is seeded with element 0, so the loop folds in elements 1 to 4095: 4095 iterations.

Why does the grader cap rendered C at 20,000 bytes in week 4?

What does a renderer that doesn't rangeify emit for a 4096-element vector?

Unrolled vector code grows with n, but rangeified code doesn't. The cap is a simple way to check that your renderer really turns shapes into loops. It doesn't force one loop: x / sum(x) needs two.

After rangeify, which of these can still appear in the graph your renderer prints?

"Removes shapes from all ops."

Rangeify lowers every vector op into scalar ops inside loops. What's left is week 3 material: ranges, ends, allocs, scalar loads and stores.