Week 2 · Lesson 4

Rendering C

Rendering turns a graph into straight-line C: put the nodes in an order the memory rules allow, give every value a name, and print each one as a C statement that means exactly what the .uir op means. That last part is harder than it sounds, because C has undefined behavior and .uir doesn't.

Three jobs: schedule, name, print

Your renderer gets a checked program and prints one C function, void kernel(...), with one pointer parameter per buffer in slot order. Inside it, three things happen:

Schedule. Pick a line-by-line order. Every node comes after its sources, and every load of a buffer version comes before the store that overwrites that version.
Name. Each value node becomes one C variable, printed once even if ten nodes use it. Constants go inline. Memory nodes don't become variables, with one exception: an alloc becomes a zero-initialized local array (int32_t a4[1] = {0};). Otherwise a buffer is a parameter, a shrink is that pointer plus an offset, and an after is the same memory as before.
Print. Each op becomes a C expression with the same meaning: the same wraparound, the same rounding, the same answer for -0.0 and nan.

Step through a small program. It adds two elements into a third, then doubles that result into the first element. The names v0, v1 are arbitrary. Any unique names work.

Loads before the store that overwrites them

In the graph, memory is immutable: %b1 = after %b %st is a new version, and %b still exists. In C, there's only one array, and a store changes it in place. So the moment the renderer prints b0[2] = v2;, version %b is gone. Every load of %b has to be printed before that line.

That's the one extra edge the scheduler adds: store into version V depends on every load of V. With it, an ordinary topological sort gives a correct order. Week 2's checker already rejects the one program shape where no such order exists: a load of an old version whose offset depends on a newer version.

Reading the old version is legal

A program may load from %b after %b1 exists. That isn't a bug, it's a swap. The renderer just has to hoist that load above the store. If your scheduler emits stores as soon as their value is ready, a swap silently becomes a copy.

C is not .uir: undefined behavior

In .uir, add on i32 wraps around. In C, signed overflow is undefined behavior: the compiler may assume it never happens and optimize as if it can't. The grader compiles your C with -fsanitize=undefined -fsanitize-trap=undefined, so undefined behavior crashes the test instead of quietly working on your machine. Every i32 op needs a spelling with no undefined cases:

op	naive C	the problem	safe C
`add`, `mul`	`a + b`	signed overflow is undefined	`(int32_t)((uint32_t)a + (uint32_t)b)`. Unsigned arithmetic wraps by definition. Converting back is implementation-defined, and every compiler you'll use wraps.
`shl`	`a << b`	shifting a negative number, or into the sign bit, is undefined	shift as `uint32_t`, then convert back. .uir already guarantees `0 ≤ b ≤ 31`.
`div`	`a / b`	`INT_MIN / -1` overflows (it traps on x86)	handle `b == -1` separately, as a wrapping negation
`mod`	`a % b`	`INT_MIN % -1` is undefined too	when `b == -1` the answer is `0`
`cast` f32 to i32	`(int32_t)x`	out of range or NaN is undefined	never happens in render tests: in .uir it's a runtime error, and render tests have none

Division without undefined behavior

Write int32_t c_div(int32_t a, int32_t b) and int32_t c_mod(int32_t a, int32_t b) with .uir's semantics: truncate toward zero, remainder takes the dividend's sign, INT_MIN / -1 = INT_MIN and INT_MIN mod -1 = 0. b is never 0. No undefined behavior.

If you try the naive version first: on Windows, INT_MIN / -1 can hang the test until the runner times it out, rather than crashing straight away.

Floats: the same rounding, every time

f32 is easier, because C's float on x86-64 and ARM64 already rounds to binary32 after every operation, exactly like .uir. One compiler habit can break that: contraction. Given a * b + c, the compiler may emit one fused multiply-add instruction that rounds once instead of twice. That's usually more accurate, and it's still the wrong answer for us:

a = 0x1.001p+0f, b = 0x1.001p+0f, c = -0x1.002p+0f
two roundings: (a * b) rounds to 0x1.002p+0, plus c gives 0
one rounding:  fmaf(a, b, c) gives 0x1p-24

-ffp-contract=off forbids that fusion, so the C rounds after every op like the oracle does. The grader passes it for you. If you build your own runtime, pass it too: clang contracts within an expression by default on targets with fused multiply-add, which includes every Apple Silicon Mac.

Literals that mean exactly one float

A constant in your graph is an exact f32. Printing it in decimal invites trouble: printf("%g", FLT_MAX) prints 3.40282e+38, and C reads that back as a different float. %.9g is enough digits for any f32, but there's a cleaner way: a hex float writes the bits directly. 0.1f is 0x1.99999ap-4f, a mantissa in hex and a power of two. Trailing zeros are fine (0x1.99999a0000000p-4f is the same number).

Three values have no literal: use NAN, INFINITY and (-INFINITY) from <math.h>. Negative zero needs its sign: -0x0p+0f.

An f32 as an exact C literal

Write c_float : float -> string. The input is already an f32 value. Return NAN for any NaN, INFINITY, (-INFINITY), and otherwise what Printf.sprintf "%h" prints, followed by f.

max is not fmaxf

C has fmaxf, and it's the wrong function. fmaxf(NAN, 1.0f) returns 1.0f: C's rule is "ignore a NaN". .uir's max returns NaN if either side is NaN, and returns +0.0 for max(-0.0, 0.0) in either order. So write a small helper function in the C you print, test it against those cases, and call it for every f32 max. That's allowed: the C may call <math.h> and non-recursive helpers defined in the same file, and nothing else.

Naming, and printing each node once

Your graph is hash consed, so a value used five times is one node. Print it once, as one variable, and refer to the name everywhere else. Keep a table from node to name, keyed on node identity. Without it, the 300-level doubling DAG from week 1 prints 2³⁰⁰ lines. With it, 300.

Code it

Emit straight-line C

A toy expression type stands in for your graph: type e = Lit of int | Var of string | Add of e * e | Mul of e * e. Write emit : e -> string list * string, returning the C lines and the expression for the result.

Lit n prints inline as n, except -2147483648, which prints as (-2147483647 - 1). Var s prints inline as s.
Add (a, b) and Mul (a, b): emit a, then b, then one line int32_t vK = (int32_t)((uint32_t)A + (uint32_t)B); (* for Mul), where K is the number of lines emitted before it. The result is vK.
A node that is physically the same (==) as one you've already emitted reuses its name and adds no line.

Check yourself

The graph loads b0[2] from version %b, and separately stores into b0[2] to make %b1. Which C order is correct?

The graph has two versions. The C array has only one. What's in b0[2] right after the store runs?

The load. C stores in place, so once b0[2] = ... runs, version %b's value is overwritten. That's why the scheduler makes every store depend on all loads of the version it overwrites.

What does this C expression evaluate to, on every compiler you'll use?

(int32_t)((uint32_t)INT32_MAX + 1u)

Unsigned addition wraps modulo 2³². What bit pattern is 2³¹, and what is it as a signed 32-bit number?

-2147483648. The unsigned sum is 2³¹, bit pattern 0x80000000, which converts back to INT_MIN. That's .uir's i32 wraparound, spelled without undefined behavior.

What does the C standard say INT_MIN / -1 evaluates to?

The true quotient is 2³¹. Does that fit in a signed 32-bit int, and what does C say about signed results that don't fit?

Undefined behavior. The quotient doesn't fit, and C doesn't define the result. On x86 it raises a hardware exception. .uir defines it as INT_MIN, so your renderer must handle b == -1 without dividing.

What does printf("%g", FLT_MAX) print?

%g uses 6 significant digits by default. FLT_MAX is about 3.4028234663852886 × 10³⁸.

3.40282e+38, and C reads that back as a slightly smaller float (bits 0x7f7fffee, not 0x7f7fffff). Short decimal output loses bits, which is why the renderer prints hex floats.

Why can't the renderer print every f32 max as fmaxf(a, b)?

Look up what C's fmax family does when one argument is NaN, and compare it with the spec's row for max.

C's fmaxf ignores a NaN argument and returns the other one. .uir propagates NaN, and pins max(-0.0, 0.0) to +0.0, which fmaxf doesn't promise. A small helper gets both right.

What does -ffp-contract=off prevent?

"Contract" here means combining two operations into one. Which two float ops have a combined hardware instruction?

Contraction into a fused multiply-add. It skips the rounding after the multiply, so the result can differ from .uir's round-after-every-op semantics (0 versus 0x1p-24 in the example above).

How many lines of C does an after node produce?

An after is a new version of the same storage. In C, where does that storage live, and did anything need to be copied?

0. The store already changed the array in place. after only tells the scheduler and later loads which version they're reading. In C it's the same pointer.