Nikaia
Menu
v0.0.1343pre-alpha GitHub

ADR-379: An Unconditional Write Is Emitted Before the ifs Beside It That Cannot Tell

Status: Accepted Date: October 22, 2026 Answers: whether the compiler may write a statement of a block in another place than the one it is written in, and when (issue #781) Related: Part I 8.1.1 (statement order is the written order), ADR-306 D18, D19 (a proved check), ADR-376 (unsafe { assume(…) }), ADR-378 (the emitted code’s unsafe), ADR-377 (the 1BRC programs)

1. Context

A loop that adds a row to a slot reads naturally as

if v < slot.min { slot.min = v }
if v > slot.max { slot.max = v }
slot.sum += v
slot.count += 1

LLVM turns slot.sum += v into one instruction that adds into memory only where the load, the add and the store stand in one basic block. The two ifs end that block, so the load is taken before them and the store after: six instructions where two do, in every turn. The same four lines with the two writes first cost four instructions a row less, in Rust as in Nikaia; the Rust that rustc gets from Nikaia, with only those lines swapped, counts the same difference. LLVM’s own passes do not move the writes across the branches, even where the overflow check is already gone; and where it is not, they could not, not knowing that nothing between can stop the program.

The compiler knows it. It knows which places a statement reads and writes, that slot.sum and slot.min are different fields, and which checks are proved. A programmer should not have to know how a code generator forms its blocks to write the natural order.

Other compilers: C and Rust compilers move memory writes freely under the as-if rule where nothing can observe the difference; GCC’s and LLVM’s store motion stops at anything that may trap or call out. Java’s JIT does the same with its own knowledge of which operations can throw.

2. Decision

D1 — A write that runs unconditionally is emitted before the ifs in front of it, where no program can tell.

In a block, a statement S that assigns to a place (p = e, p op= e) is emitted before an if T that stands directly in front of it, or in front of it with only such ifs between, when all of these hold:

  1. T neither reads nor writes p: every place T names differs from p in a field, or is a local other than p’s root;
  2. S reads nothing T writes;
  3. neither calls a function that is not pure, does input or output, pauses, takes a lock or spawns: T and S touch only memory;
  4. neither T nor S can stop the program: every check in them (an index, an overflow, a division) is proved, and neither holds a panic, an assert or a call that can throw;
  5. T does not leave: its arms hold only assignments and such ifs, no break, continue, return or throw, so S runs after it on every path, as it does before it.

The block’s last statement, its value, is not moved.

Nothing else is moved, and nothing moves past a statement that is not such an if.

Why this is the written order still (Part I 8.1.1). A program sees a statement’s effects through what it reads later, through another task, or through what it leaves when it stops. Condition 1 and 2 keep every read seeing the value it saw. Condition 3 keeps another task from seeing anything between the two: it meets this one only at a pause, a lock or a spawn, and none moves. Condition 5 keeps S running exactly when it ran. Condition 4 keeps a stop from falling between them: were one side able to stop, a drop in the teardown or the panic hook could see the other side’s write done or not done, and where both could, which stops first would change.

D2 — In every build, the same.

The order is chosen from the program and from what is proved, not from the build’s profile or from remove-*: a debug build runs the statements in the order the release build runs them, so a fault that the order exposes is found in the debugger. Each statement keeps its own source line; a debugger steps from the moved write to the if before it, as in any optimised code.

D3 — A test holds where it moves and where it does not.

The emitted order is tested for a case that moves and for each condition of D1 that keeps a case from moving: the if reads p; it writes what e reads; one side calls an impure function; one side has a check that is not proved; the if leaves.

3. Rejected alternatives

4. Consequences

This site is open source. Improve this page.