llvm-mos: experimental native 16-bit accumulator codegen (65816) — +native-16bit-accumulator

llvm-mos-native16.md

llvm-mos: experimental native 16-bit accumulator codegen (65816)

A small, flag-gated addition to the llvm-mos backend that makes the compiler emit native 16-bit accumulator code for the WDC 65816 — int16/uint16 add/sub/and/or/xor become REP #$20 … SEP #$20 regions instead of byte-at-a-time sequences.

The feature (+native-16bit-accumulator) is off by default and no CPU implies it. The existing C ABI, pointer model, 8-bit X/Y, banking, and the 8-bit accumulator at function boundaries are all unchanged, so feature-enabled and stock objects interoperate.

Pinned to upstream commit c798c31416f72b395c658b5502d281a162387ab1.

Source: gingerbeardman/llvm-mos@mos-native-16bit-accumulator · commit b5dd6ee · diff vs upstream (16 files incl. 2 tests, ~550 lines — about half is the profitability pass and its comments). Relates to llvm-mos issues #321 (16-bit register mode) and #32 (65816 support).

Why

The 65816 can run its accumulator in 16-bit mode (M=0). For chains of 16-bit integer work that is far cheaper than the 8-bit-at-a-time code the backend emits today. A feasibility kernel that is one long i16 chain (65535 iterations, measured on bsnes/Mesen) ran in 26% less time and 55% less code than the stock backend. This change is the compiler-side path toward that, behind a flag.

The win is two axes, not just speed: that kernel is also 55% smaller, and on a ROM-bank-constrained 65816 target smaller hot code is itself valuable (more fits per bank, fewer cross-bank trampolines).

But the win is conditional on chain length and does not generalize to scattered i16 code — so the feature is gated by a profitability heuristic (see Measured impact) that keeps native only the i16 ops that actually amortize the mode switch, and narrows the rest to the stock byte-split.

How it works

• No register-bank change — the MOS register-bank info already maps operands by size, so i16 gets a valid mapping.
• No new instructions — REP/SEP and the *_ZeroPage forms already exist; in M=0 the very same ZeroPage opcode operates on 16 bits. i16 constants are materialized into imaginary-register pairs and the reg-reg form is used.
• Per-op pseudos, then region merging — each i16 op is first selected to an Imag16-tied pseudo whose post-RA expansion is a self-contained REP #$20 … SEP #$20 region (so M=0 never escapes a single instruction — no cross-block / call / interrupt mode-state proof needed). A late peephole then deletes the STA / SEP / REP / LDA between adjacent same-slot regions (a store-then-reload around a mode toggle that nets to nothing), threading the value through the 16-bit accumulator and leaving one REP at the head and one SEP at the tail of the whole chain.

Each pseudo clobbers A and the flags so the register allocator keeps nothing live in A across it.

• Profitability heuristic (pre-selection) — a pre-legalizer pass measures, per i16 op, the longest single-use data-flow chain it belongs to, and keeps an op native only when that chain is ≥ -mos-native16-min-chain (default 3, the REP/SEP break-even). It rewrites just those ops to new target-generic opcodes G_NATIVE16_{ADD,SUB,AND,OR,XOR}; every other i16 op stays plain and the legalizer narrows it to the stock register-resident byte-split — including the i16 ops the legalizer itself emits for pointer arithmetic. The decision must be pre-selection: after register allocation even a one-op native region is already smaller than a memory byte-split, so only the legalizer's normal narrowing recovers the cheap register-resident split. The G_NATIVE16_* opcodes are target generics (like G_SBC), hence not isPreISelGenericOpcode, so the legalizer and its verifier pass them through untouched and the selector lowers them in C++ to the Imag16 pseudos.

Example

unsigned short chain(unsigned short a, unsigned short b, unsigned short c) {
    return ((a + b) ^ c) & 0x7fff | 0x0100;
}

chain:
    ; ... pack args / materialize constants ...
    rep #32          ; enter 16-bit accumulator (once)
    clc
    lda __rc2
    adc __rc6        ; + b
    eor __rc4        ; ^ c
    and __rc8        ; & 0x7fff
    ora __rc10       ; | 0x0100
    sta __rc2
    sep #32          ; back to 8-bit (once)
    ldx __rc3        ; 8-bit A/X return ABI, unchanged
    lda __rc2
    rts

Measured impact

OFF vs ON differ only by -mattr=+native-16bit-accumulator at the llc step (same bitcode), so the delta is purely the feature.

Wins on long chains (the kernel above, 65535 calls, on hardware):

(65535 calls)	frames @ 60 Hz	per call	code
stock	425 = 7.08 s	108 µs	98 B
native16	314 = 5.23 s	80 µs	44 B
	−26.1%	−28 µs	−55%

Loses on scattered single ops — blanket. On a real fixed-point game core (per-TU, identical bitcode, only -mattr differs), total hot .text grew +17% (e.g. one physics TU 17926→20844 bytes, 350 native regions) and a full -O2 LTO build overflowed its ROM bank by ~4 KB: the code is mostly isolated i16 ops — plus the i16 adds the legalizer emits for pointer arithmetic — each paying a full REP/SEP (+ load/store) that region merging can't fuse. Applied blanket, native16 doesn't just run slower, it doesn't fit.

The heuristic fixes both. Re-measured with the chain gate on, the same game core is byte-identical to feature-off (+0%) — it has no i16 chains ≥3, so every op narrows and the +17% / bank overflow are gone — while the long-chain kernel stays native (1.35× / −55% retained). A blanket build (forced via -mos-native16-min-chain=1) still overflows, confirming the gate is what makes it fit.

So for this program 16-bit-A nets to a safe no-op: it can no longer hurt, and it pays off only where chains actually occur. A chain-heavy program gets both the speed and the code-size/bank win. The verdict from the kernel — "16-bit mode is faster" — is true but narrow; the profitability heuristic is what makes the feature shippable by default rather than a foot-gun.

Build

Prerequisites: git, cmake ≥ 3.20, ninja, a host C++ compiler, ~20 GB disk.

git clone https://github.com/llvm-mos/llvm-mos.git
cd llvm-mos
git checkout c798c31416f72b395c658b5502d281a162387ab1
# apply the patch / cherry-pick the commit from the branch, then:
cmake -G Ninja -S llvm -B build \
  -C clang/cmake/caches/MOS.cmake \
  -DCMAKE_BUILD_TYPE=Release -DLLVM_PARALLEL_LINK_JOBS=4
ninja -C build clang lld llc FileCheck

The platform libraries (mos-platform) are unchanged by this feature; an existing llvm-mos SDK's mos-platform can be reused for linking.

Use

clang honours the feature directly (and through -flto), as long as the whole toolchain is rebuilt — rebuilding only llc relinks llc but not clang/lld, which then silently use a stale codegen library:

clang -mcpu=mosw65816 -O2 -Xclang -target-feature -Xclang +native-16bit-accumulator -c file.c
# or, applied globally at the llc step:
clang -mcpu=mosw65816 -O2 -emit-llvm -S file.c -o file.ll
llc   -mcpu=mosw65816 -O2 -mattr=+native-16bit-accumulator file.ll -o file.s

Verify

# Compiler tests (a long chain forms one native region; the heuristic narrows
# isolated/short runs and respects -mos-native16-min-chain):
llc -mcpu=mosw65816 -mattr=+native-16bit-accumulator -verify-machineinstrs \
  < llvm/test/CodeGen/MOS/native-16bit-accumulator.ll \
  | FileCheck llvm/test/CodeGen/MOS/native-16bit-accumulator.ll
llc -mcpu=mosw65816 -mattr=+native-16bit-accumulator -verify-machineinstrs \
  < llvm/test/CodeGen/MOS/native-16bit-profitability.ll \
  | FileCheck llvm/test/CodeGen/MOS/native-16bit-profitability.ll

This change was additionally validated by running native16-compiled kernels on bsnes/Mesen and comparing the results to a host oracle across carry, borrow, and sign cases (all match); and by confirming that with the feature off the backend output is byte-identical to the stock compiler.

Scope and limitations

• First slice: reg-reg add/sub/and/or/xor (constants materialized into pairs, which covers inc/dec, offsets and masking). CMP, shifts and INC/DEC-as- instructions are follow-ups. Native 16-bit shifts are a win for small shift counts but a regression for >> 8-style fixed-point (where a byte move beats eight LSRs), so shifts should be applied selectively, not blanket.
• 8-bit X/Y, near pointers and banking (the bank registers / 24-bit address space) are unchanged and out of scope — this is purely the M flag. The only lever it has on the bank budget is code size, which shrinks only on chains.
• Profitability heuristic is implemented (see Measured impact): the chain gate keeps native only the i16 runs that amortize the mode switch, so the feature is a net win where chains exist and a safe no-op elsewhere, and the whole-game build fits. Remaining op coverage (CMP, shifts, INC/DEC) is follow-up; native 16-bit shifts in particular need their own selectivity (a win for small counts, a regression for >>8-style fixed-point where a byte move beats eight LSRs).
• The heuristic's chain metric is a single-use SSA proxy for "will the late merger fuse this." An SSA chain ≥ N whose ops don't end up adjacent post-RA would be kept native yet not merge (small regression); raise the threshold if that appears.
• Two earlier "blockers" turned out otherwise: the clang/LTO "feature not honoured" was a stale clang/lld build (rebuilding only llc doesn't relink them) — with all rebuilt, clang and the LTO link both emit native16; and an i16-legal × G_UNMERGE_VALUES s64→s16 interaction in a soft-float libcall is now avoided entirely by the heuristic's design (plain i16 always narrows; only the G_NATIVE16_* opcodes stay 16-bit, and they bypass the legalizer).
• expandNative16 must give the bracketing CLC/SEC an implicit-def of the carry register, or the post-expansion machine verifier flags the ADC/SBC carry use as undefined (the region-merge peephole runs after that checkpoint).
• If native code runs with NMI enabled, the interrupt vector prologue must save the full 16-bit accumulator and force M=1/X=1 before running the 8-bit C handler; a prologue that assumes 8-bit width will corrupt the stack/accumulator if an NMI lands inside a 16-bit region.