Three-Way Merge Diff

Algorithms & Data

A merge of two sorted streams where the C “spaceship” compare (a>b)-(a<b) — yielding −1 / 0 / +1 — selects the branch: advance-left, advance-right, or emit-both. This is compiler stress-test #99: it consumes the three-way-compare result as control flow rather than a sort key, confirming the llvm-mos lowering (patch 0016) is correct whatever reads its output — at 32 and 64 bits.

loading core…

Self-running — teal = advance-left, orange = advance-right, gold = emit-both.

Click the screen to focus, then watch. Tab away and it pauses.

What it is

Merging two already-sorted lists is a staple of mergesort and diff tools. The choice at each step — which side to take, or whether the heads are equal — is exactly a three-way decision, and this demo makes that decision with the spaceship compare, then branches on its sign.

// merge two sorted streams; the THREE-WAY compare picks the branch
int cmp(int32_t a, int32_t b) { return (a > b) - (a < b); }  // -1 / 0 / +1

while (i < nl && j < nr) {
    int c = cmp(L[i], R[j]);
    if      (c < 0) out[k++] = L[i++];              // advance left
    else if (c > 0) out[k++] = R[j++];              // advance right
    else          { out[k++] = L[i++];              // c == 0:
                    out[k++] = R[j++]; }            //   emit BOTH
}

The streams are centred on zero (so the compare sees both signs) and collide periodically (so the equal branch fires). Each screen row is one merge round at a shifting offset; the gate folds the merged outputs into a CRC. The picture is the proof: a wrong branch would tear the ordering and change the CRC.

Compiler stress-test #99 — Round 6: hardening the fixes

Item	What it exercises
the spaceship result as control flow	The three-way compare (a>b)-(a<b) yields −1, 0, or +1. Earlier demos handed that value to qsort, which compares it to zero. Here the value itself selects among three code paths: take the left element, take the right, or — when they are equal — emit both. It is a branch selector, not a sort key.
the emit-both branch	The equal case (0) is the one a two-way if/else would miss. Because the two streams are built to collide periodically, the equal branch really fires — you can see it as the third colour in the braid. This is the branch that makes the demo a genuine three-way test rather than a disguised pair of comparisons.
both widths	The merge runs on 32-bit and 64-bit signed values, forcing the three-way compare at each width as a branch. The 64-bit compare-and-branch is the sharpest — a full-width three-way decision the backend lowers to compares and selects.
the bug this guards (#46, patch 0016)	The three-way-compare idiom once crashed the 65816 backend, which had no rule to lower the generic opcode. Patch 0016 routes it through LLVM’s compare-and-select lowering. The sort-gallery and rank-field demos consumed the result as a sort return; this one consumes it as control flow — confirming the lowering is correct no matter what reads its output.
why a separate comparator function	Written inline, ((a>b)-(a<b)) < 0 folds straight back to a < b and the three-way intrinsic disappears — untested. Keeping the comparator in its own non-inlined function forces it to actually produce the −1/0/+1 value, which the merge then branches on. An IR probe confirms the intrinsic is present at both widths, including 64-bit.
result: bit-exact, and the visual	Merging sorted streams is a deterministic reordering, so the merged sequence is identical on host and SNES: host == default == +mos-a16 == +mos-xy16 on both MAME and bsnes-jg, -verify-machineinstrs clean. Each screen row is one merge round; every output cell is coloured by the branch that produced it — teal for left, orange for right, gold for emit-both — so the −1/0/+1 decisions braid down the field as the streams shift.

Written in C with the llvm-mos 65816 toolchain and verified against bsnes-jg and MAME. Hit Verify fidelity to reproduce the build gate's WRAM assert (gate CRC 0xCCCC — a fold of the merged s32/s64 streams) live in this tab. No far pointers — host == default == +mos-a16 == +mos-xy16, -verify clean.