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.

loading core…

Self-running — four panels bubble-sort, then reshuffle and sort again.

Click the screen, then play. (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.

Compiler bug this demo guards against

Patch 0016 — a fully generic gap present in every build mode (default 8-bit included — nothing to do with the 16-bit-accumulator feature): the C "spaceship" three-way-compare idiom (x>y)-(x<y), which libc qsort comparators commonly use, canonicalizes to a G_SCMP/G_UCMP machine-IR opcode that the backend's legalizer had zero rule for, at any width — an unable to legalize abort, in every mode, with or without LTO.

Fix: One line: mark G_SCMP/G_UCMP as .lower(), routing them through LLVM's existing built-in three-way-compare expansion — no new codegen needed.

This demo re-stresses the fix at int8/16/32/64 key widths via qsort callbacks, reaching widths the original discovery demo never exercised.

View the fix commit →

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.