Week 2 · Lesson 2

Load, store, after

A store changes memory, but a graph has no "now". This lesson shows how .uir says when a write happens without any statement order: every store makes a new version of the buffer, and every load names the version it reads.

Stores make versions

store v x writes the value x into the view v. Its result is void: a store is an event, not a value. To use the memory after the write, you name the new version with after:

%b  = buffer 4 dtype=i32 slot=0 data=[10 20 30 40]
%e  = shrink %b 1 shape=[]
%s  = store %e 99
%b1 = after %b %s          # "%b, once %s has happened"

%b never changes. %b1 is the same storage with the write applied. A load of %e (a view of %b) still reads 20. To see 99 you load through a view of %b1. Step through a chain of two stores:

The rule that keeps this honest: after m s must name the version the store writes into. after %b1 %s is invalid when %s wrote into %b.

The outputs of a program are the final version of each buffer: the one no after builds on. That's what a caller sees when the kernel returns.

Swap two elements in place

Slot 0 is a buffer of four i32s. Swap b[0] and b[1], and leave the other two alone. The starter does half the job.

The grader sets the buffer's data for each test and checks its final contents.

What "fully ordered" means

The syllabus says loads and stores "must be fully ordered for programs to be valid". In our format that comes down to three rules:

  1. One store per version. At most one store may write into any given version, through any of its views.
  2. Every store is sequenced. Each store is the s of exactly one after. A store nothing sequences has no effect anywhere, so it's an error, not a no-op.
  3. Old versions are read before they're overwritten. A load of version V has to be able to run before the store that makes V's successor.

Rule 1 is the interesting one. Two stores into the same version have no order between them, and with two writes, order is the whole answer:

A store with no after

It's tempting to write store and move on, the way you would in C. In a graph, a store that no after names is unreachable from the outputs, so nothing could ever observe it. The oracle rejects it: "a store that no after sequences has no effect".

The old-version trap

Rule 3 sounds like it can never fail, because a load of V doesn't depend on the store that comes after V. It can fail, though, when a load of the old version needs a value that only exists in the new one. Here the index into the old buffer is read from the new buffer:

%b  = buffer 2 dtype=i32 slot=0 data=[1 0]
%e0 = shrink %b 0 shape=[]
%s  = store %e0 0
%b1 = after %b %s
%n0 = shrink %b1 0 shape=[]
%i  = load %n0              # reads the NEW b[0]
%m  = max %i 0
%k  = mod %m 2
%v  = shrink %b %k shape=[] # ...to index the OLD %b
%y  = load %v

When your compiler renders C, every version of %b is the same array, written in place. So the load of old %b must run before the store. But it needs %i, which needs %b1, which needs the store. Step through the chain of "must come before":

No order satisfies every arrow, so the program is invalid: "a load of an old buffer version is needed after that version was overwritten". A compiler could save a copy of the old buffer to make it work, but that's a hidden allocation, and the course's rule is that the program has to say what memory it uses.

Running total in place

A buffer of three i32s. In place: set b[1] = b[0] + b[1], then b[2] = b[1] + b[2] using the new b[1]. The starter has one bug about which version it reads.

Check yourself

After this runs, what does %x hold?

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

Which version is %e a view of?

%e is a view of %b, the version before the store, and the buffer started as zeros. To read the 1, you'd load through shrink %b1 0 shape=[].

Two stores write different elements of %b, and each has its own after %b .... What happens?

Rule 1 counts stores per version, not per element.

The rule is one store per version, through any view. Even when the elements differ, there are now two "next versions" of %b, and neither builds on the other. Chain them instead: the second store goes into a view of the first store's after.

A program has %s = store %e 5 and no after mentions %s. What happens?

Rule 2.

Every store must be sequenced by exactly one after. A store nothing sequences can't affect any version, so the oracle rejects the program rather than guess what you meant.

%s1 writes into a view of %b. Which line is wrong?

after m s has to name the version the store wrote into.

%s1 wrote into %b, so only after %b %s1 is right. Loading either version is always allowed.

What are the final contents of the buffer?

%b  = buffer 2 dtype=i32 slot=0 data=[5 6]
%e  = shrink %b 0 shape=[]
%x  = load %e
%f  = shrink %b 1 shape=[]
%s  = store %f %x
%b1 = after %b %s

Read b[0], write it into b[1]. Is anything out of order here?

The load reads old %b, which is fine: it runs before the store. b[0] is 5, so b[1] becomes 5 too.

Why is the old-version example above invalid?

%k is masked with max and mod, and there's only one store. Follow the arrows in the figure.

It's a cycle: the old load must come before the store (it reads the version the store overwrites), and it also must come after it (its index is read from the new version). Loading a version that has a successor is fine on its own, as the previous question showed.