Width-Sweep Sort Gallery
Algorithms & Data
Four bar-chart panels sort in lockstep, each driven by the C spaceship comparator
(a>b)−(a<b) at a different key width — 8, 16, 32 and 64 bits. Modern
llvm-mos folds that idiom to a single
three-way-compare node (G_SCMP); this is compiler stress-test #97, re-running
the fix that first taught the 65816 to lower it — now at the 32- and 64-bit widths the
original demo never reached.
Self-running — four panels bubble-sort, then reshuffle and sort again.
Click the screen to focus, then watch. Tab away and it pauses.
What it is
The build gate sorts four arrays — int8_t, int16_t,
int32_t, int64_t — with libc qsort, each using its
own spaceship comparator, and folds the sorted values into a checksum. The on-screen panels
animate the same idea: four columns of bars settling under the three-way comparison.
// the C "spaceship" three-way comparator, at four key widths
int cmp8 (const void *a, const void *b) { int8_t x=*..a, y=*..b; return (x>y)-(x<y); }
int cmp16(const void *a, const void *b) { int16_t x=*..a, y=*..b; return (x>y)-(x<y); }
int cmp32(const void *a, const void *b) { int32_t x=*..a, y=*..b; return (x>y)-(x<y); }
int cmp64(const void *a, const void *b) { int64_t x=*..a, y=*..b; return (x>y)-(x<y); }
qsort(arr8, N, 1, cmp8); qsort(arr16, N, 2, cmp16);
qsort(arr32, N, 4, cmp32); qsort(arr64, N, 8, cmp64); // → G_SCMP at s16/s32/s64 Compiler stress-test #97 — Round 6: hardening the fixes
| Item | What it exercises |
|---|---|
| the spaceship operator | (a>b)-(a<b) evaluates to −1, 0, or +1 — "less / equal / greater" in one expression. It is the classic C comparator body (and the shape C++20's <=> compiles to). Modern LLVM recognizes it and folds it to a single generic three-way-compare node, G_SCMP, rather than two separate comparisons. |
| G_SCMP and the bug it once hit (#46) | The 65816 backend originally had no rule to lower G_SCMP, so any program that sorted with a spaceship comparator failed to build ("unable to legalize G_SCMP"). Demo #46 caught that crash; the one-line fix routes G_SCMP through LLVM's standard icmp+select expansion. But #46 only ever exercised it at 16-bit keys. |
| why four widths (the escalation) | This gallery qsorts int8, int16, int32 and int64 arrays, each with its own spaceship comparator — forcing G_SCMP at the distinct widths s16, s32 and s64. The 32- and 64-bit legs are paths #46 never reached; a 64-bit three-way compare (a full-width icmp + select) had never been lowered on this target until now. |
| why qsort, not an inline sort | A direct if ((a>b)-(a<b) > 0) would let the compiler cancel the three-way compare back into a plain a > b — the G_SCMP would vanish and nothing would be tested. Passing the comparator to qsort as an opaque function pointer forces it to genuinely return the −1/0/+1 value, so the three-way compare survives. The build gate confirms it (the s64 intrinsic is present in the emitted IR). |
| result: correct at every width | Sorting is deterministic — the sorted sequence of values is identical on the host and on the SNES. The gate folds all four sorted arrays into a CRC; host == default == +mos-a16 == +mos-xy16 on both MAME and bsnes-jg, -verify-machineinstrs clean. The three-way-compare lowering is correct at s16/s32/s64 — a clean positive, now a permanent regression guard. |
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 0xF20F — a fold of four sorted arrays) live in this tab.
No far pointers — host == default == +mos-a16 == +mos-xy16,
-verify clean.