Week 1 · Lesson 4

Symbolic simplification

Constant folding needs every input to be known. Symbolic simplification works on values you don't know yet, like a param. It uses algebra and ranges to prove things like "this compare is always true".

Unknowns

Inside a function body, param 0 (the input in slot 0, see lesson 1.2's params box) could be any i32. You can't fold add %x 0 by computing it, but you can still prove it equals %x for every possible x. That's what makes a rule symbolic: it holds for all inputs, so it doesn't need the input.

The simplify subcommand (your compiler's second command, after run from lesson 1.2: it reads a file defining %out and prints a smaller equivalent program) is graded exactly this way. Your output has to compute the same value as the original for every input where the original doesn't error. The grader checks that on every edge value in every param slot (a few hundred cases), including nasty ones like INT_MIN, -0.0 and nan, and it compares f32 results bit for bit, so -0.0 and 0.0 count as different there (all NaNs count as equal). Each test also has a max_ops budget, so leaving the graph untouched won't pass either.

i32 is a ring. f32 is not.

i32 arithmetic is arithmetic mod 2³². Wraparound sounds messy, but it makes i32 a ring: addition and multiplication are associative and commutative, and multiplication distributes over addition, exactly like the integers you learned in school. Every identity built only from + and × holds, even when the values overflow.

f32 has none of that. Every op rounds, and the special values inf, -inf, nan and -0.0 break identities you'd expect to hold.

rule	i32	f32	why
`mul(x, 1) → x`	valid	valid	Multiplying by one is exact, even for `nan`, `inf` and `-0.0`.
`mul(x, 0) → 0`	valid	wrong	`nan × 0 = nan` and `inf × 0 = nan`.
`add(x, 0) → x`	valid	wrong	`-0.0 + 0.0 = +0.0`, so x changes from `-0.0` to `+0.0`. `recip` can tell them apart (`-inf` vs `inf`), and so can the simplify grader, which compares f32 bit for bit. `add(x, -0.0) → x` is valid: adding `-0.0` changes nothing.
`add(add(x, c1), c2) → add(x, c1 + c2)`	valid	wrong	i32 addition is associative mod 2³². f32 rounds after each add, so regrouping changes the result.
`xor(x, x) → 0`	valid	n/a	xor only takes i32 and bool.
`cmplt(x, x) → false`	valid	valid	Nothing is less than itself, and `nan` compares false anyway.
`where(c, a, a) → a`	valid	valid	Both branches are the same node.
`div(mul(x, c), c) → x`	only with bounds	n/a	`mul` can wrap, and `div` can't undo a wrap: `(2³⁰ × 2) / 2` is `INT_MIN / 2`, not `2³⁰`. Safe when bounds prove the product fits, and always safe for `c = 1` or `c = -1`. See the trap below.

f32 identities

When a rule "obviously" holds, try it on nan, inf, -inf and -0.0 before you trust it on f32. If you're not sure, don't add the rule. A missing rule costs you some ops. A wrong rule costs you correctness.

Simplify by hand

You are the rewrite engine. The starter computes ((3 + x) + x * 0) + 5 in four ops. Rewrite %out so it computes the same i32 value for every x, using at most one op.

Which rules from the table did you just apply? Is the answer still right when x = INT_MAX?

The f32 zero trap

Same job, now on f32: %out = (x * 1.0) * 0.0. Use at most one op. The tests feed in nan, inf, -inf and negative numbers, and the oracle prints -0.0 as -0.0.

Bounds: what range can this value be in?

Some facts don't follow from algebra alone. cmplt (mod %k 8) 8 is always true, but only because you know a remainder by 8 is at most 7. That calls for bounds analysis (also called interval analysis): give every i32 node a range [lo, hi] that its value is guaranteed to stay inside. Ranges are worked out sources first, just like rewriting. Below, a.lo and a.hi are the two ends of operand a's range:

const c is [c, c]. A param is the full range [INT_MIN, INT_MAX].
add: [a.lo + b.lo, a.hi + b.hi], but only if neither end overflows. If one could wrap, fall back to the full range.
max: [max(a.lo, b.lo), max(a.hi, b.hi)].
mod x c with c > 0: [0, c-1] if x ≥ 0, otherwise [-(c-1), c-1], because the sign follows x.
cast from bool: [0, 1].

Ranges are conservative. Reporting a range that's too wide is always safe, because it just proves fewer things. Reporting one that's too narrow is a bug.

%x   = param 0 dtype=i32
%m   = max %x 0
%k   = mod %m 8
%out = cmplt %k 8

Rules powered by bounds

cmplt(a, b) → true      if a.hi < b.lo
cmplt(a, b) → false     if a.lo ≥ b.hi
max(a, b)   → a         if a.lo ≥ b.hi
mod(x, c)   → x         if 0 ≤ x.lo and x.hi < c
div(x, c)   → 0         if 0 ≤ x.lo and x.hi < c

These rules matter for real. When week 3 adds loops, every index carries a range, and these rules are how bounds checks and index math disappear.

(x * 2) / 2 is not x

It's tempting to cancel the 2s. In i32, mul wraps and div doesn't undo the wrap:

x	x * 2	(x * 2) / 2	equals x?
`3`	`6`	`3`	yes
`-5`	`-10`	`-5`	yes
`1073741824` (2³⁰)	`-2147483648` (wrapped)	`-1073741824`	no

So div(mul(x, c), c) → x is only valid when bounds prove mul(x, c) can't wrap. With %x = cast %b dtype=i32 (range [0, 1]) it's safe, and the oracle simplifies (x * 2) / 2 down to the cast. With a raw param it must stay. The grader's edge-case inputs include 2³⁰ precisely to catch this.

Code it

Interval arithmetic for i32

Bounds analysis needs two operations on ranges. Write add_range a b and mul_range a b: the tightest { lo; hi } that contains every x + y (or x * y) with x in a and y in b.

The catch is wraparound. If any value in the result could fall outside the i32 range, the real i32 operation might wrap, so you know nothing: return full.

Do the math in OCaml's 63-bit int, then check against int_min and int_max.
For mul, the smallest and largest products can come from any pair of ends: [-3, 2] * [-5, 4] is [-12, 15].

Does 63 bits always hold the product?

Almost. Two i32 values multiply to at most 2⁶², and that one product (INT_MIN * INT_MIN) is one past OCaml's max_int, so it wraps to a negative int. Work out whether that breaks your answer for full * full. There's a test for it.

Check yourself

Which rule is valid for f32?

Try each rule on the awkward floats: nan, inf, and -0.0.

Only multiplying by one is exact for every float. nan × 0 is nan, regrouping changes rounding, and -0.0 + 0.0 is +0.0.

What are the bounds of %k? Write them as [lo, hi].

%x = param 0 dtype=i32
%m = max %x 0
%k = mod %m 8

First find the range of %m. Can max %x 0 ever be negative?

mod by a positive constant on a value that is never negative lands in [0, divisor - 1].

%m is [0, INT_MAX], which is never negative, so mod 8 gives [0, 7].

Now drop the max. What does %out simplify to? (x is any i32.)

%x   = param 0 dtype=i32
%k   = mod %x 8
%out = cmplt %k 8

Without the max, x can be negative, and the sign of mod follows x. Which end of the range moved, and does that end matter for < 8?

Still true. A negative x makes the range [-7, 7], but the top is still 7, and 7 < 8. Only the low end changed.

Predict %out for %x = 1073741824.

%m   = mul %x 2
%out = div %m 2

Work out 1073741824 * 2 first. Does 2³¹ fit in i32?

When a product passes INT_MAX, it wraps to a negative number. Then divide that by 2, truncating toward zero.

2³¹ doesn't fit in i32, so it wraps to -2147483648. Halving that gives -1073741824, not x.

Why is add(add(x, 3), 4) → add(x, 7) valid in i32, even when x + 3 overflows?

Think about what kind of arithmetic i32 wraparound is. Does regrouping change anything when everything is computed mod 2³²?

i32 is the ring of integers mod 2³². In a ring, grouping doesn't matter. Overflow here is defined wrapping, not undefined behavior like in C.

After simplifying, what's the fewest ops %out can use?

%x   = param 0 dtype=i32
%a   = add %x 3
%out = add %a 4

Fold the two constants into one. How many adds are left, and would it vanish if the constants summed to 0?

One: add %x 7. (With -3 instead of 4, it would be zero ops, since add %x 0 becomes %x.)

Here %x = cast %b dtype=i32 with %b a bool param. Can div(mul(%x, 2), 2) simplify to %x?

A bool cast to i32 is always 0 or 1. What range does %x * 2 have, and can that wrap?

The rule is valid whenever bounds prove the multiply doesn't wrap. The oracle reduces this to a single cast.