Coding Tech WASM Open Source

The Tape

Joshua Tenner

Every compiler has a middle. The front end reads the program you wrote, and the back end produces code for the target machine. Between them is an intermediate representation, or IR: a version of the program designed to make analysis and optimization easier.

In the engine I work on, that representation is a tape.

A tape is a sequence of small, fixed-size nodes. Imagine frames on a film strip, lined up one after another. A compiler pass can walk the strip in order without following a tree of pointers. When it needs to change a computation, it can edit a node in place. It’s a simple shape for a complicated job.

The tape: a strip of small entries, read by walking it

Before looking at what each node represents, it helps to understand why the tape’s layout is useful.

Why this shape matters

First, neighbors.

Entries that influence each other are often close together on the tape. A processor has a small, fast memory called the L1 cache. Think of it as a shelf next to your desk, while main memory is a warehouse farther away.

Items on the shelf are quick to reach. Items in the warehouse require a trip.

When a compiler pass walks the tape, nearby entries are likely to arrive in the cache together. A tree-based representation can scatter nodes across memory, requiring more pointer lookups and cache misses.

The difference is simple: less time waiting for memory means more time doing useful work.

The L1 cache as a shelf by the desk, and the tape as nodes in a row

Second, the order is separate from the computation.

The tape describes each computation and its inputs. A separate list, called the scheduler, determines which values to materialize and in what order.

Materializing means making a computed value available for use.

To change the order, you move a node’s number in the scheduler. The node itself stays where it is. Nothing needs to be copied or renumbered. Such moves must still respect data dependencies and the required order of effects.

Some nodes also contain small, implied steps. The scheduler doesn’t need to list those steps separately. It only schedules the values that must be materialized.

The computation tape with numbered nodes, and the scheduler as a separate list of numbers

Third, removing a computation is a small edit.

Instead of removing a node and shifting everything after it, you replace the node with a Nop: an entry that does nothing.

The node keeps its position and number. Other nodes don’t need to move.

A node turned into a Nop, in place, with its number kept

Stable node numbers bring another benefit. Facts recorded about a node remain associated with it as other parts of the tape change. New nodes are appended to the end, so existing numbers stay the same.

Many optimization passes can work through this representation with a simple linear walk.

The layout makes those passes efficient. What each node represents helps make their changes safe.

Separate values from effects

An instruction can do two jobs: compute a value and cause an effect. A load reads a value, but it can also trap if the address is invalid. A store changes memory. A call may change state or trap.

On the tape, values and effects become separate entries. For a load, one entry represents the read, while a nearby guard holds the required checks: is the address in bounds, is the reference valid, and is it the right type?

The guard can stop the program. The read, once guarded, cannot. They travel together, but remain independent.

One instruction split into two entries: the read and the guard

That small separation changes what later passes can safely do.

Where facts live

The passes that walk the tape depend on facts, and those facts need a home.

A fact is a small statement known to be true about a value. A compiler can collect a great many of them, so it needs a store that keeps those facts available for later use.

That store has three jobs: find a fact quickly, keep related facts in order, and accept new facts without expensive rebuilding.

A hash set handles exact lookups well. A formula determines where each item belongs, deliberately mixing their order. That’s useful when the only question is whether an exact item exists.

But optimization also needs ordered queries. Which facts lie between two values? Which facts do two sets share? What is the strongest known fact about a value?

A hash set doesn’t naturally support those questions.

The store I use is a B-tree, a tree made of small pages that hold keys in order. Each internal page contains guide keys that tell the reader which branch to follow.

A card, a box of cards, and a guide box

To find a fact, the reader examines the guide keys and follows the correct branch. It repeats this until it reaches the page that holds the fact.

Because each page contains several keys, even a large tree can require only a few hops.

The guide box at the top, fact boxes below

Adding a fact follows the same path. The reader finds the correct page and inserts the new fact in order.

If a page is full, it splits. The middle key moves up, dividing the remaining keys between two pages. These operations keep the keys ordered and all leaf pages at the same depth.

Those rules are called invariants: properties that must remain true after every change.

An insert: hop to the box, put the fact in, and a full box splits

Pages also help with memory locality.

A page keeps related keys close together in memory. When the processor fetches a cache line, it may bring several nearby keys with it. Later comparisons can reuse that cached data instead of requesting each key separately.

The shelf and warehouse matter here, too.

A cache-line fetch brings several neighboring B-tree keys into L1, not the whole page

Facts are ordered first by value, then by kind. There are four kinds: what a value is, what it is not, its size, and its range.

This gives every value a run of related facts in key order. To ask what the compiler knows about a value, the reader scans that run rather than searching the entire store.

Facts about one value, ordered by kind, as one run

The store keeps the facts organized. The graph tells us where they apply.

Facts ride the graph

Programs have branches. One block of instructions might jump to another, and the next block depends on which path the program takes.

Connect those blocks with their possible jumps, and you get a control flow graph.

Blocks joined by jumps, with facts riding the edges

Facts move along the graph’s edges. When one block checks a value, later blocks can use that fact.

When two paths meet, the joined block can only trust facts that hold along both incoming paths.

Those facts help the compiler remove unnecessary work. If a later check repeats something already proven, and nothing has invalidated that proof, the second check can disappear.

No guessing is required. The proof travels from the first check to the place where it is needed.

This is where separating values from effects pays off again. Facts describe values, while the effects remain independent. The compiler can reason about one without accidentally removing the other.

Consider this small example in WebAssembly’s text format, called WAT:

(if (result i32)
  (i32.lt_u (local.get $i) (array.len (local.get $a)))
  (then
    (array.get $arr (local.get $a) (local.get $i)))
  (else
    (i32.const 0)))

In plain words: if the index is smaller than the array’s length, read the element at that index. Otherwise, return zero.

On the tape, that read has a guard beside it. But the branch condition has already established the bounds check. Once the compiler proves that this fact still holds, the redundant bounds check can be removed without removing any other required checks.

A branch proves the array bounds check unnecessary, leaving the read intact

Remove dead code without breaking the alarms

Dead code is work whose result is never used. It is common in programs after other optimizations have simplified their computations.

Removing it sounds simple, until an unused result comes from an instruction that still has effects.

A load might trap. A store might change memory. A call might do something important even when nobody uses its return value.

Delete the wrong instruction, and the program’s behavior changes.

This is why dead code elimination must distinguish computations from effects.

The split makes that distinction explicit.

Walk the tape backwards and count how many times each value is used. If a value has no remaining uses, its computation may be dead.

When that computation has no required effects, replace its node with a Nop. That also reduces the use counts of its inputs, which may reveal more dead computations.

One backward walk can eliminate entire chains of unnecessary work.

A read whose value is unused can disappear. But if the original operation required a guard, that guard stays.

It has its own entry and its own position in the execution order. It can still stop the program where the original operation would have stopped.

The work disappears. The alarm remains.

The backward walk: dead work crossed out, the guard kept

That’s the advantage of separating computations from their effects.

Facts tell the compiler what is already known. Use counts identify results that nobody needs. The scheduler preserves the required execution order, while dead values are removed and surviving computations are improved.

The compiler can change the work without changing the program’s meaning.

A tape is a humble shape. But humble shapes go a long way when you make the right split.

Joshua Tenner

Software developer building compilers and WebAssembly tools

Husband · Dad of three