commit e98cc403a4f37c11bd4e087cccf9cefdc5b428e9
parent 8d02200922ca9a783e34528570d43c1acbef7124
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Wed, 17 Jun 2026 12:46:15 -0700
arm32: fix O1 ADD/SUB-immediate emit truncating the negate-trick constant
The -O1 jump-table bounds/index `idx = sel - vmin` was miscompiled when vmin is
negative (signed switch with negative cases, e.g. case -3..3): the SUB of the
32-bit constant 0xFFFFFFFD (-3) emitted `subw r5, r0, #4093` — the immediate
silently truncated to its low 12 bits (0xFFFFFFFD & 0xFFF = 4093). Every
selector then mapped outside [0,span) and fell to default, so
6_8_29_switch_signed_negative returned 99 from every pick → s=495, s-197=298,
mod 256 = 42 (want 100).
Root cause: arm_imm_legal accepted `SUB #imm` whenever thumb_expand_imm_encode(
-imm) succeeded (the "subtract -3 = add 3" trick), but arm_binop's emit never
implemented that trick — it only tried thumb_expand(+imm) then fell through to
SUBW with a 12-bit-masked immediate. Legality and emit were inconsistent.
Fix: a single shared resolver, arm_resolve_addsub_imm, maps `rd = ra (+|-) imm`
to a concrete non-negative (is_sub, magnitude), trying both the addend and its
negation so a small negative constant folds into the opposite operation
(SUB #3 for `+ -3`, ADD #3 for `- -3`) and only succeeding when the magnitude is
a Thumb modified-immediate or fits the 12-bit ADDW/SUBW field. Both arm_imm_legal
and the new arm_emit_alu_imm route through it, so a constant can never be
legalized yet mis-encoded. The raw 12-bit fallback now only ever sees a magnitude
that fits. As a side benefit, `x + (negative const)` now folds to a single SUB.
arm32 toy corpus unchanged at 423/0/2; the signed-negative switch passes O0+O1.
Diffstat:
1 file changed, 74 insertions(+), 25 deletions(-)
diff --git a/src/arch/arm32/native.c b/src/arch/arm32/native.c
@@ -306,6 +306,34 @@ static const NativeRegInfo arm_reg_info = {
/* ============================ legality ============================ */
+/* Resolve `rd = ra <ADD|SUB> imm` into a concrete non-negative (is_sub, mag)
+ * immediate. Adding `imm` equals subtracting `-imm` and vice versa (modulo
+ * 2^32), so a small negative constant folds into the opposite operation: SUB #3
+ * for `+ -3`, ADD #3 for `- -3`. Returns 1 (and fills is_sub/mag) when the
+ * magnitude is a Thumb modified-immediate OR fits the 12-bit ADDW/SUBW field;
+ * 0 when the constant must be materialized into a register first. The emit path
+ * (arm_emit_alu_imm) and the legality predicate (arm_imm_legal) BOTH route
+ * through this, so a value can never be accepted as legal yet mis-encoded —
+ * the bug where `SUB #-3` legalized via the -imm trick but emitted SUBW with a
+ * 12-bit-truncated 0xFFFFFFFD. */
+static int arm_resolve_addsub_imm(BinOp op, i64 imm, int* is_sub, u32* mag) {
+ /* k = the value actually added to ra (subtracting imm adds -imm). */
+ u32 k = (u32)(op == BO_ISUB ? (u64)0 - (u64)imm : (u64)imm);
+ u32 nk = (u32)((u64)0 - (u64)k); /* the magnitude of the SUB alternative */
+ u32 enc;
+ if (thumb_expand_imm_encode(k, &enc) || k <= 0xfffu) {
+ *is_sub = 0;
+ *mag = k;
+ return 1;
+ }
+ if (thumb_expand_imm_encode(nk, &enc) || nk <= 0xfffu) {
+ *is_sub = 1;
+ *mag = nk;
+ return 1;
+ }
+ return 0;
+}
+
static int arm_imm_legal(NativeTarget* t, NativeImmUse use, u32 op,
KitCgTypeId type, i64 imm) {
u32 enc;
@@ -319,10 +347,11 @@ static int arm_imm_legal(NativeTarget* t, NativeImmUse use, u32 op,
case NATIVE_IMM_BINOP:
switch ((BinOp)op) {
case BO_IADD:
- case BO_ISUB:
- if (thumb_expand_imm_encode((u32)(op == BO_ISUB ? -imm : imm), &enc))
- return 1;
- return imm >= 0 && imm <= 0xfff; /* ADDW/SUBW raw 12-bit */
+ case BO_ISUB: {
+ int is_sub;
+ u32 mag;
+ return arm_resolve_addsub_imm((BinOp)op, imm, &is_sub, &mag);
+ }
case BO_AND:
case BO_OR:
case BO_XOR:
@@ -784,6 +813,35 @@ static void arm_load_addr(NativeTarget* t, NativeLoc dst, NativeAddr addr) {
/* ============================ ALU ============================ */
+/* Emit `rd = ra (+|-) mag` in the densest legal Thumb-2 encoding: the 16-bit
+ * ADDS/SUBS imm3/imm8 (flag-dead) when the magnitude is small and both registers
+ * are low, else the 32-bit modified-immediate form, else the 12-bit ADDW/SUBW
+ * raw form. `mag` is guaranteed by arm_resolve_addsub_imm to fit a modified
+ * immediate or the 12-bit field, so the raw fallback never truncates. */
+static void arm_emit_alu_imm(MCEmitter* mc, int is_sub, u32 rd, u32 ra,
+ u32 mag) {
+ u32 enc;
+ if (!is_sub) {
+ if (arm_low_reg(rd) && arm_low_reg(ra) && arm_uimm_fits(mag, 3u))
+ arm_emit_t16(mc, arm_adds_imm3(rd, ra, mag));
+ else if (rd == ra && arm_low_reg(rd) && arm_uimm_fits(mag, 8u))
+ arm_emit_t16(mc, arm_adds_imm8(rd, mag));
+ else if (thumb_expand_imm_encode(mag, &enc))
+ arm_emit_t32(mc, arm_dp_imm(8u, 0u, rd, ra, enc));
+ else
+ arm_emit_t32(mc, arm_add_imm12(rd, ra, mag & 0xfffu));
+ } else {
+ if (arm_low_reg(rd) && arm_low_reg(ra) && arm_uimm_fits(mag, 3u))
+ arm_emit_t16(mc, arm_subs_imm3(rd, ra, mag));
+ else if (rd == ra && arm_low_reg(rd) && arm_uimm_fits(mag, 8u))
+ arm_emit_t16(mc, arm_subs_imm8(rd, mag));
+ else if (thumb_expand_imm_encode(mag, &enc))
+ arm_emit_t32(mc, arm_dp_imm(13u, 0u, rd, ra, enc));
+ else
+ arm_emit_t32(mc, arm_sub_imm12(rd, ra, mag & 0xfffu));
+ }
+}
+
static void arm_binop(NativeTarget* t, BinOp op, NativeLoc dst, NativeLoc a_loc,
NativeLoc b) {
Arm32NativeTarget* a = arm_of(t);
@@ -815,18 +873,13 @@ static void arm_binop(NativeTarget* t, BinOp op, NativeLoc dst, NativeLoc a_loc,
switch (op) {
case BO_IADD:
if (b_imm) {
- /* ADDS rd,rn,#imm3 (low regs) / ADDS rdn,#imm8 (in-place, low reg) —
- * flag-dead 16-bit forms. The .W modified-imm/ADDW fallbacks below stay
- * for high regs and wider immediates. */
- u32 v = (u32)b.v.imm;
- if (arm_low_reg(rd) && arm_low_reg(ra) && arm_uimm_fits(v, 3u))
- arm_emit_t16(mc, arm_adds_imm3(rd, ra, v));
- else if (rd == ra && arm_low_reg(rd) && arm_uimm_fits(v, 8u))
- arm_emit_t16(mc, arm_adds_imm8(rd, v));
- else if (thumb_expand_imm_encode(v, &enc))
- arm_emit_t32(mc, arm_dp_imm(8u, 0u, rd, ra, enc));
- else
- arm_emit_t32(mc, arm_add_imm12(rd, ra, v & 0xfffu));
+ /* Fold the constant into ADD/SUB (a negative addend becomes SUB) via the
+ * shared resolver; arm_emit_alu_imm picks the densest legal encoding. */
+ int is_sub;
+ u32 mag;
+ if (!arm_resolve_addsub_imm(BO_IADD, b.v.imm, &is_sub, &mag))
+ arm_panic(a, "add immediate not encodable");
+ arm_emit_alu_imm(mc, is_sub, rd, ra, mag);
} else if (arm_low_reg(rd) && arm_low_reg(ra) && arm_low_reg(rb)) {
arm_emit_t16(mc, arm_adds_reg16(rd, ra, rb)); /* flag-dead */
} else {
@@ -835,15 +888,11 @@ static void arm_binop(NativeTarget* t, BinOp op, NativeLoc dst, NativeLoc a_loc,
return;
case BO_ISUB:
if (b_imm) {
- u32 v = (u32)b.v.imm;
- if (arm_low_reg(rd) && arm_low_reg(ra) && arm_uimm_fits(v, 3u))
- arm_emit_t16(mc, arm_subs_imm3(rd, ra, v));
- else if (rd == ra && arm_low_reg(rd) && arm_uimm_fits(v, 8u))
- arm_emit_t16(mc, arm_subs_imm8(rd, v));
- else if (thumb_expand_imm_encode(v, &enc))
- arm_emit_t32(mc, arm_dp_imm(13u, 0u, rd, ra, enc));
- else
- arm_emit_t32(mc, arm_sub_imm12(rd, ra, v & 0xfffu));
+ int is_sub;
+ u32 mag;
+ if (!arm_resolve_addsub_imm(BO_ISUB, b.v.imm, &is_sub, &mag))
+ arm_panic(a, "sub immediate not encodable");
+ arm_emit_alu_imm(mc, is_sub, rd, ra, mag);
} else if (arm_low_reg(rd) && arm_low_reg(ra) && arm_low_reg(rb)) {
arm_emit_t16(mc, arm_subs_reg16(rd, ra, rb)); /* flag-dead */
} else {
