commit 2dadd8b01a1000932423b27d2625bf5b2ca8098d
parent 57e2c48627cc19d3dbce6cb00d2e5af18ad57ca6
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Tue, 16 Jun 2026 09:25:06 -0700
opt: fold single-use shift into consuming ALU op at O1 (O1-PATTERNS L7)
Add a shift rider to the optimizer's register operand (OptOperand.shift) and a
matching NativeLoc.shift, plus a NativeTarget capability hook
can_fold_shift_into_alu (true only for aa64).
When a binop (IADD/ISUB/AND/ORR/EOR) reads a second source register produced by
a single-use IR_BINOP SHL reg,imm (shift 1..4) at the same operand width,
mir_combine's try_fold_shift_into_alu rewrites the operand to the shift source
and stamps the rider; the aa64 backend emits the shifted-register form
(add/sub/and/orr/eor xD,xA,xS,lsl #k) in one instruction instead of
lsl xT,xS,#k; <op> xD,xA,xT. The dead SHL is retired by mir_dce.
Guards: single-use shift (dies at the binop), source unchanged since the shift,
source not aliasing the shift dst, and matching shift/binop result width (so an
inline shift never widens past the value the SHL produced). ISUB is sound
because the rider only sits on the second source (the subtrahend).
Gating is by target capability: x64/rv64 never receive a shift rider and keep
the unfolded (correct) form. The W5 compute-CSE operand-equality now compares
the shift rider so a ridered and riderless operand never alias.
aa64 done + validated (add/sub/and/orr/eor, 32- and 64-bit; multiply-used shift
correctly keeps the lsl). x64/rv64 gated off. test-opt + test-toy 1392/0 green.
Diffstat:
4 files changed, 155 insertions(+), 3 deletions(-)
diff --git a/src/arch/aa64/native.c b/src/arch/aa64/native.c
@@ -782,6 +782,32 @@ static u32 aa_add_lsl(u32 rd, u32 rn, u32 rm, u32 shift) {
.Rd = rd});
}
+/* L7 shifted-register ALU forms: rd = rn <op> (rm << shift). shift type is
+ * always LSL (the .shift field, 0); the shift amount is imm6. add/sub use the
+ * add/sub shifted-register family, and/orr/eor the logical shifted-register
+ * family. `sf` selects the 32- vs 64-bit operand width. */
+static u32 aa_addsub_lsl(u32 sf, u32 op, u32 rd, u32 rn, u32 rm, u32 shift) {
+ return aa64_addsubsr_pack((AA64AddSubSR){.sf = sf,
+ .op = op,
+ .S = 0,
+ .shift = 0,
+ .Rm = rm,
+ .imm6 = shift,
+ .Rn = rn,
+ .Rd = rd});
+}
+
+static u32 aa_logsr_lsl(u32 sf, u32 opc, u32 rd, u32 rn, u32 rm, u32 shift) {
+ return aa64_logsr_pack((AA64LogSR){.sf = sf,
+ .opc = opc,
+ .shift = 0,
+ .N = 0,
+ .Rm = rm,
+ .imm6 = shift,
+ .Rn = rn,
+ .Rd = rd});
+}
+
static u32 aa_cset(u32 sf, u32 rd, u32 cond) {
return aa64_csinc_enc(sf, rd, AA64_ZR, AA64_ZR, cond ^ 1u);
}
@@ -2908,6 +2934,33 @@ static void aa_binop(NativeTarget* t, BinOp op, NativeLoc dst, NativeLoc lhs,
aa_emit32(t->mc, aa64_eor_imm(sf, rd, rn, N, immr, imms));
return;
}
+ /* L7 shifted-register ALU: a single-use `lsl rm,#k` (k in 1..4) folded into
+ * this op's second source. Emit `<op> rd,rn,rm,lsl #k` in one instruction
+ * instead of `lsl rT,rm,#k; <op> rd,rn,rT`. Only an integer register rhs can
+ * carry a shift rider (immediates never do, and the recognition pass restricts
+ * it to add/sub/and/orr/eor). */
+ if (rhs.kind == NATIVE_LOC_REG && rhs.shift) {
+ u32 k = rhs.shift;
+ switch (op) {
+ case BO_IADD:
+ aa_emit32(t->mc, aa_addsub_lsl(sf, /*op=add*/ 0u, rd, rn, rm, k));
+ return;
+ case BO_ISUB:
+ aa_emit32(t->mc, aa_addsub_lsl(sf, /*op=sub*/ 1u, rd, rn, rm, k));
+ return;
+ case BO_AND:
+ aa_emit32(t->mc, aa_logsr_lsl(sf, AA64_LOG_AND_OPC, rd, rn, rm, k));
+ return;
+ case BO_OR:
+ aa_emit32(t->mc, aa_logsr_lsl(sf, AA64_LOG_ORR_OPC, rd, rn, rm, k));
+ return;
+ case BO_XOR:
+ aa_emit32(t->mc, aa_logsr_lsl(sf, AA64_LOG_EOR_OPC, rd, rn, rm, k));
+ return;
+ default:
+ aa_panic(aa_of(t), "shift rider on unsupported binop");
+ }
+ }
switch (op) {
case BO_IADD:
aa_emit32(t->mc, aa64_add(sf, rd, rn, rm));
diff --git a/src/arch/native_target.h b/src/arch/native_target.h
@@ -306,7 +306,13 @@ typedef struct NativeLoc {
* producers); the arch then falls back to the live cg_type_size query, so
* partial adoption stays byte-identical. */
u8 szinfo;
- u8 pad[1];
+ /* L7 shift rider (O1-PATTERNS): when nonzero on a register NativeLoc passed
+ * as the second source of a binop, the value is pre-shifted left by `shift`
+ * (1..4) and the backend emits the shifted-register ALU form
+ * (`add xD,xA,xS,lsl #shift`). 0 = use the register as-is. Only stamped when
+ * the target advertised can_fold_shift_into_alu, so a backend without the
+ * capability never sees it. */
+ u8 shift;
KitCgTypeId type;
union {
Reg reg;
@@ -746,7 +752,7 @@ static inline NativeLoc native_loc_from_reg(NativeRegLoc r) {
loc.kind = (u8)(r.is_imm ? NATIVE_LOC_IMM : NATIVE_LOC_REG);
loc.cls = r.cls;
loc.szinfo = r.szinfo;
- loc.pad[0] = 0;
+ loc.shift = 0; /* O1-only L7 rider; the -O0 NDT fast path never sets it */
loc.type = r.type;
if (r.is_imm)
loc.v.imm = r.v.imm;
diff --git a/src/opt/pass_combine.c b/src/opt/pass_combine.c
@@ -1246,6 +1246,84 @@ static int try_addr_synth(CombineCtx* ctx, Inst* in, i32 i) {
return any;
}
+/* ---- L7: fold a single-use left shift into the consuming ALU op ---- */
+
+/* True for the integer binops aa64 can emit as a shifted-register form
+ * (`<op> rd,rn,rm,lsl #k`). ISUB is included: it is non-commutative but the
+ * shifted operand is always the SECOND source (the subtrahend), which is
+ * exactly where the rider sits. IMUL/div/etc. have no shifted-register form. */
+static int binop_takes_shifted_rhs(BinOp op) {
+ switch (op) {
+ case BO_IADD:
+ case BO_ISUB:
+ case BO_AND:
+ case BO_OR:
+ case BO_XOR:
+ return 1;
+ default:
+ return 0;
+ }
+}
+
+/* L7 recognition. When `in` is one of the shifted-register-capable binops and
+ * its second source register is produced by a single-use `IR_BINOP SHL reg,imm`
+ * (shift 1..4) at the SAME operand width, fold the shift into the binop by
+ * rewriting opnds[2] to the shift's source register and stamping the shift
+ * rider. The aa64 backend then emits the one-instruction shifted form; the dead
+ * SHL is retired by mir_dce. Gated by the target capability so only a backend
+ * that emits the shifted form ever receives a rider. */
+static int try_fold_shift_into_alu(CombineCtx* ctx, Inst* in, i32 i) {
+ if ((IROp)in->op != IR_BINOP || in->nopnds != 3) return 0;
+ if (!binop_takes_shifted_rhs((BinOp)in->extra.imm)) return 0;
+ Operand* rhs = &in->opnds[2];
+ if (rhs->kind != OPK_REG || rhs->cls != RC_INT || rhs->shift != 0) return 0;
+ if (!ctx->target || !ctx->target->can_fold_shift_into_alu ||
+ !ctx->target->can_fold_shift_into_alu(ctx->target))
+ return 0;
+
+ i32 prod_idx = ctx_producer_of(ctx, RC_INT, rhs->v.reg);
+ if (prod_idx < 0 || prod_idx >= i) return 0;
+ Inst* prod = &ctx->bl->insts[prod_idx];
+ if ((IROp)prod->op != IR_BINOP || prod->nopnds != 3 ||
+ (BinOp)prod->extra.imm != BO_SHL || prod->opnds[0].kind != OPK_REG ||
+ prod->opnds[0].cls != RC_INT || prod->opnds[0].v.reg != rhs->v.reg ||
+ prod->opnds[1].kind != OPK_REG || prod->opnds[1].cls != RC_INT ||
+ prod->opnds[2].kind != OPK_IMM)
+ return 0;
+ i64 sh = prod->opnds[2].v.imm;
+ if (sh < 1 || sh > 4) return 0;
+
+ /* Width safety: the shifted-register operand shifts the rm register at the
+ * CONSUMING binop's width. If the SHL produced a narrower value (e.g. a
+ * 32-bit shift) than the binop reads (64-bit), the high bits of the source
+ * register are not the shift's, so the inline shift would be wrong. Require
+ * the shift's result width to equal the binop's result width. */
+ u32 shl_w = combine_scalar_width_bytes(ctx->f, prod->opnds[0].type);
+ u32 alu_w = combine_scalar_width_bytes(ctx->f, in->opnds[0].type);
+ if (!shl_w || !alu_w || shl_w != alu_w) return 0;
+
+ Operand prod_def = prod->opnds[0];
+ int killed = 0;
+ int uses_after =
+ count_uses_in_live_range(ctx->f, ctx->bl, prod_idx, &prod_def, &killed);
+ /* The shift def must be single-use (it dies at this binop); folding while
+ * other uses survive would leave the SHL live AND add a redundant inline
+ * shift. The source must be unchanged since the SHL and must not alias the
+ * SHL dst (else rewriting the operand to the source changes its value). */
+ if (uses_after != 1) return 0;
+ if (!killed && opt_block_live_out_has_phys_reg(ctx->f, ctx->hard_live,
+ ctx->bl->id, &prod_def))
+ return 0;
+ if (producer_def_aliases_source(&prod_def, &prod->opnds[1])) return 0;
+ if (ctx_def_changed_since(ctx, RC_INT, prod->opnds[1].v.reg, prod_idx))
+ return 0;
+
+ rhs->v.reg = prod->opnds[1].v.reg;
+ rhs->shift = (u8)sh;
+ ctx->block_change_p = 1;
+ return 1;
+}
+
/* ---- Rewrite 3: sink producer into single-use IR_COPY destination ---- */
static int try_sink(CombineCtx* ctx, Inst* in, i32 i) {
@@ -1874,7 +1952,10 @@ static int same_compute_operand(const Operand* a, const Operand* b) {
if (a->kind != b->kind) return 0;
switch (a->kind) {
case OPK_REG:
- return a->cls == b->cls && a->v.reg == b->v.reg;
+ /* The L7 shift rider is part of the operand's value: `x2` and `x2,lsl#2`
+ * are different inputs, so a ridered and a riderless operand must not be
+ * treated as the same compute (else CSE would drop the shift). */
+ return a->cls == b->cls && a->v.reg == b->v.reg && a->shift == b->shift;
case OPK_IMM:
return a->v.imm == b->v.imm && a->type == b->type;
default:
@@ -2176,6 +2257,12 @@ static int opt_combine_fold_block(Func* f, Block* bl,
try_fuse_cmp_branch(&ctx, in, i);
try_substitute(&ctx, in, i);
try_addr_synth(&ctx, in, i);
+ /* L7: fold a single-use left shift into this binop's shifted-register
+ * form. Run after substitution (so a copy-propagated rhs is resolved)
+ * and after addr-synth (address shifts go into the EA, not the ALU
+ * rider), and before the compute-CSE record below so the ridered operand
+ * shape is what gets recorded. */
+ try_fold_shift_into_alu(&ctx, in, i);
/* W5: same-block redundant-load + pure-compute reuse. Run after
* addr-synth so both the recorded entries and this lookup see the
* canonical (post-fold) address/operand shapes. Each turns the redundant
diff --git a/src/opt/pass_native_emit.c b/src/opt/pass_native_emit.c
@@ -948,6 +948,12 @@ static void emit_inst(NativeEmitCtx* e, u32 block, u32 order_index, Inst* in,
dst_reg, loc_avoid_reg(b), in->loc);
b = operand_imm_or_reg(e, &in->opnds[2], NATIVE_IMM_BINOP,
(u32)in->extra.imm, a.v.reg, dst_reg, in->loc);
+ /* L7 shift rider: a single-use SHL folded into this binop's second
+ * source. The rider only survives onto a register `b` (a shifted-reg
+ * ALU operand); an immediate `b` never carries one. The recognition
+ * pass only stamps it for targets advertising can_fold_shift_into_alu,
+ * so a backend ignoring NativeLoc.shift never receives a nonzero rider. */
+ if (b.kind == NATIVE_LOC_REG) b.shift = in->opnds[2].shift;
if (dst.kind != NATIVE_LOC_REG)
dst = scratch_loc(e, in->opnds[0].type,
class_for_type(e, in->opnds[0].type), a.v.reg,
