Week 3 · Lesson 1

Ranges and ends

Week 2 programs touch every element by hand: one view, one store, one after per element. That's fine for four elements and hopeless for a thousand. This lesson adds the two ops that make a loop, range and end, and the one property your compiler has to track to place them: the set of open ranges.

A range is a counter

%i = range 4 is an i32 value that takes the values 0, 1, 2 and 3. The statement's name is the range's name. Anything computed from %i is computed once per value of %i:

%b  = buffer 4 dtype=i32 slot=0
%i  = range 4
%sq = mul %i %i             # i * i, for each i
%v  = shrink %b %i shape=[] # element i
%s  = store %v %sq          # b[i] = i * i
%e  = end %s %i             # repeat %s for i = 0, 1, 2, 3
%b1 = after %b %e           # the buffer after the whole loop

end %s %i says "run the store once for every value of %i, in order". After the loop, %b1 holds 0, 1, 4, 9. A range on its own doesn't loop anything. The loop exists only where an end closes it.

The bound can be any i32 expression that doesn't depend on another range. range 0 (or anything 0 or below) runs zero times. Because the bound can't depend on another range, every loop nest in week 3 is a rectangle: no triangular loops yet.

Open ranges

Every UOp has a set of open ranges: the ranges it depends on that no end has closed yet. A range is open in itself. Any other op takes the union of its operands' sets. An end removes the range it closes. Step through the program above:

The open ranges tell your compiler where each value lives: a value with {i} open is computed inside the i loop, and a value with nothing open is computed once, outside every loop. That's the whole placement rule for ordinary values. Loads get one more rule, in lesson 3.2.

Square every element

Slot 0 holds six i32s. Write out[i] = in[i] * in[i] into slot 1 for every i from 0 to 5. The starter handles only i = 0. Turn it into a loop.

The grader sets both buffers' data for each test and checks slot 1's final contents.

Nesting

Two ranges make a loop nest. The order of the ends decides which loop is outside. Here the store depends on both %i and %j. %j is closed first, so it's the inner loop:

%b  = buffer 6 dtype=i32 slot=0
%i  = range 2
%j  = range 3
%i3 = mul %i 3
%o  = add %i3 %j            # row-major offset i*3 + j
%v  = shrink %b %o shape=[]
%s  = store %v %o
%ej = end %s %j             # inner loop: j
%ei = end %ej %i            # outer loop: i
%b1 = after %b %ei

loop i (end %ei)

%i3 = mul %i 3

loop j (end %ej)

%o = add %i3 %j

%s = store ...

for (int32_t r3 = 0; r3 < 2; r3++) {
  int32_t v4 = r3 * 3;      /* i*3: outside the j loop */
  for (int32_t r5 = 0; r5 < 3; r5++) {
    int32_t v6 = v4 + r5;
    b0[v6] = v6;
  }
}

The C is the oracle's rendering, with the wraparound casts trimmed for reading.

Notice where %i3 went. It depends only on %i, so it's computed in the i loop, not the j loop. That's open ranges doing the hoisting for free. Swap the two ends and you get the same answers with the loops the other way round. Lesson 3.3 shows why that choice matters.

Reverse into a second buffer

Copy slot 0 (five i32s) into slot 1 backwards: out[i] = in[4 - i]. There's no subtract op, and the view has to pass the bounds check.

What makes a loop invalid

The oracle checks these statically. Each one is a mistake that would otherwise produce C that means something different from your graph:

Closing a range the effect doesn't use. end %s %j when %s doesn't depend on %j is an error, not a pointless loop.
A bound that depends on a range. %j = range %i is rejected in week 3.
An open range where none is allowed. assert, call and a range's bound must have nothing open. An assert inside a loop would have to pass once per iteration, which the format doesn't say how to report.
Closing a range twice. Each range has exactly one end, so each range is exactly one loop.
Out of bounds. A range's interval is [0, n-1], and week 2's bounds check uses it. shrink %b %i with %i = range 5 on a four-element buffer is invalid.

Open ranges on a toy graph

Here's a five-constructor toy version of the graph. Write opens: the sorted, duplicate-free names of the ranges a node depends on that no End has closed. This is the property your compiler computes for every UOp.

Check yourself

After the first program on this page runs, what does %b1 hold?

The store writes i * i into element i, for i from 0 to 3.

The loop runs the store four times: b[0] = 0, b[1] = 1, b[2] = 4, b[3] = 9. The oracle agrees.

In the loop-nest example, which loop computes %i3 = mul %i 3?

Where a value lives depends on what it depends on, not on who uses it.

%i3 has open ranges {i}, so it's computed once per value of i, in the i loop, outside the j loop. Its user %o has {i, j} open and lives in the j loop.

%s stores into shrink %b %i shape=[], with %i = range 4 and %j = range 2. What does %e = end %s %j do?

Does %s depend on %j?

%s doesn't use %j, and closing a range the effect doesn't use is an error: "end closes a range its effects don't use". Repeating a store that doesn't change is almost always a bug in the graph, so the format refuses it.

The bound of a range is add 0 0. What happens to a buffer that loop stores into?

The spec says what n ≤ 0 does.

A range with bound 0 or below runs zero times, so the store never happens and the buffer's final version holds its initial data. The oracle runs that program with exit 0.

A buffer has 4 elements, and %v = shrink %b %i shape=[] with %i = range 5. What exit code does run give?

What's the interval of %i?

%i is in [0, 4], so the view could start at element 4 of a four-element buffer. The bounds check fails, and the program is invalid: exit 2.

Why must an assert have no open ranges?

What would "the first failing assert" mean for an assert that runs four times?

An assert produces one pass or fail. Inside a loop it would produce one per iteration. To check something about every iteration, store it into a buffer inside the loop and assert on the buffer after the loop.