Week 3 · Lesson 5

Rendering loops

A program with ranges is still a graph: nothing in it says "this line goes inside that loop". Your renderer has to work that out. Every value gets a depth from the ranges it depends on, every end becomes a for loop, and the result is a nest of blocks you can print top to bottom.

Where does a value live?

Week 2's renderer printed one flat list. Now each value has to land inside the right loops. The rule from the spec is short:

A value is computed inside every loop whose range it depends on, and no deeper. Its depth is the deepest of its open ranges. A constant, or anything built only from constants and buffers, lives outside every loop.
A load is placed the same way, with one exception. If the innermost loop holding every use of it is deeper than the load's own place, and that loop stores into the version the load reads, the load moves into it and sees the current contents on every iteration. A use counts as inside a loop only if it's placed there itself. That's the accumulator from lesson 3.2.
An end is a loop. It sits in the block around its loop, and its loop body is a new block holding everything whose deepest range is the one it closes.

Those three rules turn the graph into nested blocks. Inside every block the week 2 order still applies: sources first, and loads of a version before the store that overwrites it. Step through the valid 1D convolution from lesson 4.

Hoisting comes for free

Because a value lives at the depth of its deepest range and no deeper, anything that doesn't change inside a loop is computed outside it. In the 2D convolution from lesson 4, oi*3 depends only on the outermost range, so it's computed once per oi, not once per tap:

for (int32_t r7 = 0; r7 < 3; r7++) {                    // oi
  int32_t v8 = (int32_t)((uint32_t)r7 * (uint32_t)3);    // oi*3: depends on oi only
  for (int32_t r9 = 0; r9 < 3; r9++) {                  // oj
    int32_t v10 = (int32_t)((uint32_t)v8 + (uint32_t)r9);// oi*3 + oj
    b2[v10] = 0;                                         // the reset: depends on oi, oj
    for (int32_t r15 = 0; r15 < 2; r15++) {             // ki
      int32_t v16 = (int32_t)((uint32_t)r7 + (uint32_t)r15);
      int32_t v17 = (int32_t)((uint32_t)v16 * (uint32_t)4);  // (oi + ki)*4: no kj
      int32_t v18 = (int32_t)((uint32_t)r15 * (uint32_t)2);  // ki*2: no kj
      for (int32_t r19 = 0; r19 < 2; r19++) {           // kj
        int32_t v20 = b2[v10];                           // the accumulator: placed by its use
        ...

A C compiler would hoist these too, at -O2. You still want to do it yourself: it's free once you have depths, it makes the C readable, and in week 6 your kernels get timed with your own code doing the work.

Which loop is outside?

The graph never says "loop oi is outside loop oj". You read it off the ends. %eoj = end %eki %oj closes oj, but its effect still depends on oi, so %eoj has oi open. Then %eoi = end %eoj %oi repeats that whole oj loop for every oi. In general, the ranges an end still has open after closing its own are exactly the loops around it.

So the loop order is a property you compute by walking the graph, and the placement of every node follows from it. The syllabus says this is the first week you'll likely want a rewrite engine to "order the ranges properly": a pass that, rule by rule, pushes each node into the loop where it belongs and pulls loop-invariant work out. You can also do it directly, by computing depths and building blocks as in the stepper. Either way, keep it in its own pass. Week 4's rangeify will create ranges for you, and a renderer that knows how to place nodes is what turns those into loops.

What the grader allows now

The render grader still removes comments and strings, then looks for loops. For a program that contains a range, for is allowed and while, do and goto are not. For a program with no ranges (every week 2 test), any loop at all fails the test, exactly as before.

Which loop does a node live in?

A toy graph has two kinds of node: Range (d, name), a loop counter at nesting depth d (1 is the outermost loop), and Op (name, srcs). Write depth : node -> int: the loop depth a node must be computed at, which is the deepest range it can reach through its sources, or 0 if it reaches none. Keep the type and the function name as given.

Print a loop nest

Write skeleton : (string * string) list -> string -> string. Given loops outermost first, each a variable and a bound, return C with one for (int32_t v = 0; v < bound; v++) { per loop, the body innermost, and a } per loop. Indent two spaces per level. Join lines with "\n", with no trailing newline. With no loops, return the body unchanged.

Check yourself

Loops nest i (outermost), then j, then k. A value is add %i %k. Where is it computed?

A value lives at the depth of its deepest open range.

It depends on k, the innermost range, so it's computed every k iteration, even though it doesn't use j.

Same nest. Where is mul %i 3 computed?

What's the deepest range it depends on?

Its only range is i, so it's hoisted out of j and k. Ordinary values stay at the depth of their ranges. Only a load whose uses sit in a deeper loop that writes the version it reads moves toward those uses.

The accumulator load %cur = load %yv0 depends on no range. Its only use is inside the k loop, and the k loop stores into the version it reads. Where does it run?

This is the one placement rule that isn't about open ranges.

A load runs in the innermost loop holding all its uses, and because that loop stores into the version it reads, it reloads every iteration and sees the running sum. Anywhere else, every iteration would add to the same starting value.

What exit code should run give?

%b  = buffer 4 dtype=i32 slot=0
%i  = range 4
%j  = range 2
%v  = shrink %b %i shape=[]
%s  = store %v 7
%e  = end %s %j
%b1 = after %b %e

Which range does the store depend on, and which one does the end close?

2. The store depends on i, but the end closes j, which its effect doesn't use. The oracle rejects it: "end closes a range its effects don't use".

One range %i is closed by two different ends, one around a store into slot 0 and one around a store into slot 1. Is that a valid program?

A range is the loop. How many loops can one loop be?

A range names one loop, so it gets one end. To write two buffers in the same loop, give that end both effects. The oracle accepts end %s0 %s1 %i and rejects the two-end version.

After this program, what's in c[2]?

%b  = buffer 3 dtype=i32 slot=0
%c  = buffer 3 dtype=i32 slot=1
%i  = range 3
%v  = shrink %b %i shape=[]
%s  = store %v %i
%w  = shrink %c %i shape=[]
%ii = mul %i %i
%s2 = store %w %ii
%e  = end %s %s2 %i
%b1 = after %b %e
%c1 = after %c %e

One loop runs both stores. What does the second store write at i = 2?

4: the loop writes i*i into c[i], so c = [0 1 4]. Both afters take the same end, one per buffer it wrote.

Your renderer prints a for loop to zero an alloc. On which render tests does that fail?

The grader decides per program.

The loop rule depends on the program: for is allowed only if the program contains a range. Zero an alloc with = {0} and the question never comes up.