One More Loop, and the Binary Snapshot Looks Like a Different Program

Series contents · Resources and Scheduling · 阅读中文版

“This test passed a moment ago. It still passes on its own, but the output changes after the rest of the suite.”

“Could it be the random seed?”

“There are no random numbers. Just a static counter.”

Compiler nondeterminism does not always come from a complicated parallel algorithm. Sometimes it comes from a global state so ordinary that it is easy to overlook: a counter that numbers loop labels. The first test consumes some numbers, so the second starts at a higher value. Change the execution order, and the assembly text changes again.

Who should own a label?

A label identifies a control-flow target within one generation unit. Its natural lifetime is therefore that unit: labels must not collide within one instruction stream, but independent streams have no reason to share a numbering space.

The verified changes replace static loop counters inside several kernels with a label-allocation interface owned by the generator object. Arithmetic broadcast loops, composite loops, and recurrent-state kernels all obtain labels from the same generator.

This establishes two separate properties. First, when several kernels are generated consecutively into one instruction stream, their labels no longer collide as a result of kernels choosing names locally. Second, when two fresh generators process identical input, their label numbers no longer depend on how many programs the process generated earlier.

The changes also remove these static counters as points of shared mutation during concurrent calls. That does not mean several threads can safely use the same generator object. In the new tests, each thread creates an independent generator. What they test is isolation between independent objects.

Loop correctness has four layers

The first is counting. A count of 1 should execute once, without accidentally advancing an address one extra time. For a count of 0, the interface must define whether it is unsupported or produces an empty loop. In a structure that executes the body before decrementing, accepting 0 can cause an enormous loop through counter wraparound.

The second is addressing. Each inner iteration advances by one stride, while the end of an outer iteration may require a different boundary adjustment. Checking iteration counts alone cannot reveal that the next row incorrectly continues from the end of the previous row.

The third is control flow. Branch destinations, backward-branch distances, and instruction lengths after pseudo-instruction expansion must agree. A correct label in the text does not guarantee a correct displacement in the final encoding.

The fourth is resources. Registers for nested counters must not overwrite each other. Internal events must be released on exit, and generating several kernels consecutively must not leave live state behind.

These four layers are related, but “the loop test passed” cannot stand in for all of them.

Align the concepts with a teaching example

Consider processing a 3×5 grid:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

outer = 3
outer_begin:
    inner = 5
inner_begin:
    process_one_tile()
    inner -= 1
    if inner == 0: goto inner_done
    advance_inner_address()
    goto inner_begin
inner_done:
    outer -= 1
    if outer == 0: goto all_done
    advance_outer_boundary()
    goto outer_begin
all_done:

The address advance is deliberately placed after the exit check, so it is skipped on the final iteration. Some descriptor models do not allow advancing to an out-of-bounds address after processing has finished. A real implementation may use another valid approach, but its tests must follow its addressing protocol.

If the outer counter’s register is reused when initializing the inner loop, even this small example may never reach all_done. That is why the resource leases in Registers and RAII must be designed together with the loop structure.

What evidence can golden tests provide?

The relevant commit adds fixed binary references covering no loop, a single iteration, an inner loop, nested loops, composite operations, multistep recurrent state, and some combinations of modes. The tests compare actual assembly, pseudo-assembly, and binary output. They also check label uniqueness, agreement between incremental and complete output, exhaustion after repeated incremental reads, and the absence of leftover dependency resources.

The same cases are also run in reverse order and reconstructed in independent generators across multiple threads. This broadens the focus from “one generation produced the right output” to “the result does not depend on what other cases did first.”

That is useful engineering coverage, but it has limits. A binary golden value can preserve an existing bug. Comparing every byte detects changes; it cannot automatically explain why a change is correct or incorrect.

When reviewing a golden-file update, “the new output has been regenerated” is therefore insufficient. Explain whether register selection changed, label scope changed, a control-flow displacement was corrected, or operation semantics actually changed. Reference data should support that explanation, not replace it.

Stable text and stable machine code are different properties

Different label names can resolve to identical branch displacements, so unstable assembly text may still produce identical machine code. Conversely, even with stable-looking text labels, a change in the number of expanded pseudo-instructions can change the encoded branch target.

That is the value of checking all three representations. Pseudo-assembly preserves higher-level intent, actual assembly shows the expansion, and binary output confirms field encoding. Identifying the first level that changes often narrows the investigation.

Incremental output also has its own state concerns. If one stage reads newly added assembly and another reads newly added binary data, their cursors must each follow their own protocol. Comparing complete and incremental output, and checking that a second read is empty, tests consumption behavior as well as generated content.

Validating loop parameters depends on whether the loop is enabled

The changes also check positive counts and field representability for configurations with broadcast loops enabled. They retain the existing behavior of ignoring invalid loop-count fields when looping is disabled.

There is no contradiction here. The presence of a field in a configuration object does not mean every mode uses it. If the ordinary nonlooping path never reads loop_count, requiring it to be positive may break existing callers. Once looping is enabled, however, an invalid count must be rejected before instructions are emitted.

Checks at several broadcast entry points do not automatically cover every composite or recurrent kernel. Each entry point still needs its own parameter contract. The existence of a common validation helper does not prove that every path is protected.

Trace a small example before updating the golden file

Faced with a long sequence of changed machine words, it is tempting to replace the entire reference output. A more informative process starts by tracing a small loop: what is the counter each time execution reaches the loop head, which tile is processed, where does the address point, and how many tiles have been processed at exit?

For the teaching example with two nested loops, first check the first tile, the last tile of an inner loop, the first tile after an outer-loop transition, and the final tile overall. These four points quickly expose many stride-reset and exit-condition errors. An interpreter can then enumerate the complete trace to catch intermediate changes that manual inspection may miss.

If only register numbers changed, the trace should stay the same. If an instruction expansion gained an instruction, label names may remain unchanged, but branch distances must be recalculated. If an address update was removed, explain whether it originally occurred after the final valid access. Classifying the differences gives a golden-file update a reviewable justification.

Apply the same reasoning to concurrent determinism. Independent tasks producing identical results from identical inputs provide evidence of object isolation. What happens when multiple tasks share one object belongs to a separate interface contract. The presence of a threaded test does not justify declaring every usage thread-safe. How the test constructs its objects often says more about what it proves than the test’s name does.

Regression coverage and experiments not yet run

A useful extension would be a teaching interpreter supporting only the scalar instructions needed by these loops. It could check execution counts and address traces. Generate code for small random loops, then compare it with a high-level loop simulation. This complements golden testing: the interpreter checks abstract behavior, while the golden tests stabilize concrete encoding.

For performance, distinguish compiler throughput under concurrent generation from device loop performance. Removing shared counters helps make independent generation more reproducible, but it does not establish a device speedup. Whether nested loops outperform unrolling depends on code size, branch overhead, descriptor updates, and instruction-cache pressure.

The next time a test “passes on its own,” look beyond thread locks. Ask why this program’s labels remember that another program came before it.

Back to series contents · Previous · Next

• ← Previous Post
• Next Post →