kit

kit
git clone https://git.ryansepassi.com/git/kit.git
Log | Files | Refs | README

commit afb4cccb5119f51e1af693d59e161745019087ce
parent 3594417c5b6b345d722d1e63dd096cf59f6ec5ab
Author: Ryan Sepassi <rsepassi@gmail.com>
Date:   Fri, 15 May 2026 07:49:27 -0700

cg: defer integer compares for branch fusion

Diffstat:
Msrc/api/cg.c | 326+++++++++++++++++++++++++++++++++++++++++++++++++++----------------------------
1 file changed, 210 insertions(+), 116 deletions(-)

diff --git a/src/api/cg.c b/src/api/cg.c @@ -992,9 +992,18 @@ typedef enum SResidency { RES_SPILLED, } SResidency; +typedef enum ApiSValueKind { + SV_OPERAND, + SV_CMP, +} ApiSValueKind; + typedef struct ApiSValue { Operand op; + Operand cmp_a; + Operand cmp_b; CfreeCgTypeId type; + CmpOp cmp_op; + u8 kind; u8 res; u8 pinned; u8 lvalue; @@ -1225,6 +1234,7 @@ static u8 api_residency_for(const Operand *o) { static ApiSValue api_make_sv(Operand op, CfreeCgTypeId ty) { ApiSValue sv; memset(&sv, 0, sizeof sv); + sv.kind = SV_OPERAND; sv.op = op; sv.type = ty; sv.res = api_residency_for(&op); @@ -1238,6 +1248,20 @@ static ApiSValue api_make_lv(Operand op, CfreeCgTypeId ty) { return sv; } +static ApiSValue api_make_cmp(CmpOp op, Operand a, Operand b, + CfreeCgTypeId result_ty) { + ApiSValue sv; + memset(&sv, 0, sizeof sv); + sv.kind = SV_CMP; + sv.type = result_ty; + sv.cmp_op = op; + sv.cmp_a = a; + sv.cmp_b = b; + sv.res = RES_INHERENT; + sv.spill_slot = FRAME_SLOT_NONE; + return sv; +} + static CfreeCgTypeId api_sv_type(const ApiSValue *sv) { return sv->type ? sv->type : sv->op.type; } @@ -1247,6 +1271,15 @@ static int api_operand_can_address(const Operand *o) { o->kind == OPK_INDIRECT; } +static int api_sv_op_is(const ApiSValue *sv, OpKind kind) { + return sv->kind == SV_OPERAND && sv->op.kind == kind; +} + +static int api_sv_op_is_reg_or_imm(const ApiSValue *sv) { + return sv->kind == SV_OPERAND && + (sv->op.kind == OPK_IMM || sv->op.kind == OPK_REG); +} + static int api_is_lvalue_sv(const ApiSValue *sv) { return sv->lvalue && api_operand_can_address(&sv->op); } @@ -1317,6 +1350,8 @@ static CfreeCgTypeId api_slot_type(CfreeCg *g, FrameSlot slot) { /* ---- register class helpers ---- */ static u8 api_class_of_sv(const ApiSValue *sv) { + if (sv->kind == SV_CMP) + return RC_INT; if (sv->op.kind == OPK_INDIRECT) return RC_INT; if (sv->op.kind == OPK_IMM || sv->op.kind == OPK_REG) @@ -1531,6 +1566,62 @@ static MemAccess api_mem_for_spill(CfreeCg *g, const ApiSValue *sv) { return m; } +static void api_release_operand_reg(CfreeCg *g, Operand op) { + if (op.kind == OPK_REG) + api_free_reg(g, op.v.reg, op.cls); +} + +static void api_release_cmp(CfreeCg *g, ApiSValue *sv) { + api_release_operand_reg(g, sv->cmp_a); + if (sv->cmp_b.kind != OPK_REG || sv->cmp_a.kind != OPK_REG || + sv->cmp_b.v.reg != sv->cmp_a.v.reg || sv->cmp_b.cls != sv->cmp_a.cls) { + api_release_operand_reg(g, sv->cmp_b); + } + memset(&sv->cmp_a, 0, sizeof sv->cmp_a); + memset(&sv->cmp_b, 0, sizeof sv->cmp_b); + sv->kind = SV_OPERAND; +} + +static void api_materialize_cmp_to(CfreeCg *g, ApiSValue *sv, Operand dst) { + g->target->cmp(g->target, sv->cmp_op, dst, sv->cmp_a, sv->cmp_b); + if (sv->cmp_a.kind == OPK_REG && + (sv->cmp_a.v.reg != dst.v.reg || sv->cmp_a.cls != dst.cls)) { + api_release_operand_reg(g, sv->cmp_a); + } + if (sv->cmp_b.kind == OPK_REG && + (sv->cmp_b.v.reg != dst.v.reg || sv->cmp_b.cls != dst.cls)) { + api_release_operand_reg(g, sv->cmp_b); + } + memset(&sv->cmp_a, 0, sizeof sv->cmp_a); + memset(&sv->cmp_b, 0, sizeof sv->cmp_b); + sv->kind = SV_OPERAND; + sv->op = dst; + sv->type = dst.type; + sv->res = RES_REG; + sv->lvalue = 0; +} + +static int api_materialize_cmp_victim(CfreeCg *g, u8 cls) { + if (cls != RC_INT) + return 0; + for (u32 i = 0; i < g->sp; ++i) { + ApiSValue *sv = &g->stack[i]; + Operand dst; + if (sv->kind != SV_CMP || sv->pinned) + continue; + if (sv->cmp_a.kind == OPK_REG && sv->cmp_a.cls == RC_INT) { + dst = api_op_reg(sv->cmp_a.v.reg, api_sv_type(sv)); + } else if (sv->cmp_b.kind == OPK_REG && sv->cmp_b.cls == RC_INT) { + dst = api_op_reg(sv->cmp_b.v.reg, api_sv_type(sv)); + } else { + continue; + } + api_materialize_cmp_to(g, sv, dst); + return 1; + } + return 0; +} + static Reg api_alloc_reg_or_spill(CfreeCg *g, u8 cls, CfreeCgTypeId ty) { CGTarget *T = g->target; Reg r; @@ -1540,6 +1631,12 @@ static Reg api_alloc_reg_or_spill(CfreeCg *g, u8 cls, CfreeCgTypeId ty) { return r; ApiSValue *victim = api_pick_victim(g, cls); + if (!victim && api_materialize_cmp_victim(g, cls)) { + r = api_alloc_reg(g, cls); + if (r != (Reg)REG_NONE) + return r; + victim = api_pick_victim(g, cls); + } if (victim) { FrameSlot slot = api_take_spill_slot(g, cls); CfreeCgTypeId rty = api_owned_reg_type(g, victim); @@ -1565,6 +1662,22 @@ static Reg api_alloc_reg_or_spill(CfreeCg *g, u8 cls, CfreeCgTypeId ty) { } static void api_ensure_reg(CfreeCg *g, ApiSValue *sv) { + if (sv->kind == SV_CMP) { + CfreeCgTypeId ty = api_sv_type(sv); + Operand dst; + if (sv->cmp_a.kind == OPK_REG && sv->cmp_a.cls == RC_INT) { + dst = api_op_reg(sv->cmp_a.v.reg, ty); + } else if (sv->cmp_b.kind == OPK_REG && sv->cmp_b.cls == RC_INT) { + dst = api_op_reg(sv->cmp_b.v.reg, ty); + } else { + Reg r = + api_alloc_reg_or_spill(g, RC_INT, + ty ? ty : builtin_id(CFREE_CG_BUILTIN_I32)); + dst = api_op_reg(r, ty); + } + api_materialize_cmp_to(g, sv, dst); + return; + } if (sv->res != RES_SPILLED) return; CGTarget *T = g->target; @@ -1610,13 +1723,15 @@ static Operand api_force_reg(CfreeCg *g, ApiSValue *v, CfreeCgTypeId ty) { static Operand api_force_reg_unless_imm(CfreeCg *g, ApiSValue *v, CfreeCgTypeId ty) { - if (v->op.kind == OPK_IMM) + if (api_sv_op_is(v, OPK_IMM)) return v->op; return api_force_reg(g, v, ty); } static void api_release(CfreeCg *g, ApiSValue *sv) { - if (sv->res == RES_REG) { + if (sv->kind == SV_CMP) { + api_release_cmp(g, sv); + } else if (sv->res == RES_REG) { api_free_reg(g, (Reg)api_reg_of_sv(sv), api_class_of_sv(sv)); } else if (sv->res == RES_SPILLED) { api_return_spill_slot(g, sv->spill_slot, api_class_of_sv(sv)); @@ -1750,6 +1865,40 @@ static CmpOp api_map_fp_cmp(CfreeCgFpCmpOp op) { return CMP_EQ; } +static CmpOp api_invert_cmp(CmpOp op) { + switch (op) { + case CMP_EQ: + return CMP_NE; + case CMP_NE: + return CMP_EQ; + case CMP_LT_S: + return CMP_GE_S; + case CMP_LE_S: + return CMP_GT_S; + case CMP_GT_S: + return CMP_LE_S; + case CMP_GE_S: + return CMP_LT_S; + case CMP_LT_U: + return CMP_GE_U; + case CMP_LE_U: + return CMP_GT_U; + case CMP_GT_U: + return CMP_LE_U; + case CMP_GE_U: + return CMP_LT_U; + case CMP_LT_F: + return CMP_GE_F; + case CMP_LE_F: + return CMP_GT_F; + case CMP_GT_F: + return CMP_LE_F; + case CMP_GE_F: + return CMP_LT_F; + } + return CMP_EQ; +} + static AtomicOp api_map_atomic_op(CfreeCgAtomicOp op) { switch (op) { case CFREE_CG_ATOMIC_XCHG: @@ -2424,11 +2573,11 @@ void cfree_cg_load(CfreeCg *g, CfreeCgMemAccess access) { if (!g) return; v = api_pop(g); - api_ensure_reg(g, &v); if (!api_is_lvalue_sv(&v)) { api_push(g, v); return; } + api_ensure_reg(g, &v); ty = resolve_type(g->c, access.type); if (!ty) ty = api_sv_type(&v); @@ -2499,7 +2648,7 @@ void cfree_cg_store(CfreeCg *g, CfreeCgMemAccess access) { ty = resolve_type(g->c, access.type); if (!ty) ty = api_sv_type(&lv); - if (rv.op.kind == OPK_IMM || rv.op.kind == OPK_REG) { + if (api_sv_op_is_reg_or_imm(&rv)) { src = rv.op; } else { src = api_force_reg(g, &rv, api_sv_type(&rv)); @@ -2638,6 +2787,10 @@ static void api_cg_cmp(CfreeCg *g, CmpOp cop) { ra = api_force_reg_unless_imm(g, &a, opty); rb = api_force_reg_unless_imm(g, &b, opty); + if (api_type_class(opty) != RC_FP) { + api_push(g, api_make_cmp(cop, ra, rb, i32)); + return; + } rr = api_alloc_reg_or_spill(g, RC_INT, i32); dst = api_op_reg(rr, i32); T->cmp(T, cop, dst, ra, rb); @@ -2886,7 +3039,7 @@ void cfree_cg_intrinsic(CfreeCg *g, CfreeCgIntrinsic intrin, uint32_t nargs, CfreeCgTypeId aty; svs[idx] = api_pop(g); aty = api_sv_type(&svs[idx]); - if (svs[idx].op.kind == OPK_IMM && + if (api_sv_op_is(&svs[idx], OPK_IMM) && (intrin == CFREE_CG_INTRIN_EXPECT || intrin == CFREE_CG_INTRIN_ASSUME_ALIGNED || intrin == CFREE_CG_INTRIN_PREFETCH)) { @@ -3004,7 +3157,7 @@ void cfree_cg_atomic_store(CfreeCg *g, CfreeCgMemAccess access, if (!val_ty) val_ty = api_atomic_pointee(g, pty, "CfreeCg: atomic_store"); addr = api_force_reg(g, &ptr, pty); - src = (val.op.kind == OPK_IMM || val.op.kind == OPK_REG) + src = api_sv_op_is_reg_or_imm(&val) ? val.op : api_force_reg(g, &val, val_ty); g->target->atomic_store(g->target, addr, src, api_mem_for_atomic(g, val_ty), @@ -3028,7 +3181,7 @@ void cfree_cg_atomic_rmw(CfreeCg *g, CfreeCgMemAccess access, if (!val_ty) val_ty = api_atomic_pointee(g, pty, "CfreeCg: atomic_rmw"); addr = api_force_reg(g, &ptr, pty); - vop = (val.op.kind == OPK_IMM || val.op.kind == OPK_REG) + vop = api_sv_op_is_reg_or_imm(&val) ? val.op : api_force_reg(g, &val, val_ty); rr = api_alloc_reg_or_spill(g, api_type_class(val_ty), val_ty); @@ -3060,10 +3213,10 @@ void cfree_cg_atomic_cmpxchg(CfreeCg *g, CfreeCgMemAccess access, val_ty = api_atomic_pointee(g, pty, "CfreeCg: atomic_cmpxchg"); int_ty = builtin_id(CFREE_CG_BUILTIN_I32); addr = api_force_reg(g, &ptr, pty); - exp_op = (expected.op.kind == OPK_IMM || expected.op.kind == OPK_REG) + exp_op = api_sv_op_is_reg_or_imm(&expected) ? expected.op : api_force_reg(g, &expected, val_ty); - des_op = (desired.op.kind == OPK_IMM || desired.op.kind == OPK_REG) + des_op = api_sv_op_is_reg_or_imm(&desired) ? desired.op : api_force_reg(g, &desired, val_ty); pr = api_alloc_reg_or_spill(g, api_type_class(val_ty), val_ty); @@ -3281,8 +3434,9 @@ void cfree_cg_inline_asm(CfreeCg *g, CfreeCgInlineAsm asm_block) { continue; } bound = out_ops[matched]; - if (in_svs[i].op.kind == OPK_REG && in_svs[i].op.v.reg == bound.v.reg) { - } else if (in_svs[i].op.kind == OPK_IMM) { + if (api_sv_op_is(&in_svs[i], OPK_REG) && + in_svs[i].op.v.reg == bound.v.reg) { + } else if (api_sv_op_is(&in_svs[i], OPK_IMM)) { T->load_imm(T, bound, in_svs[i].op.v.imm); } else { Operand src = api_force_reg(g, &in_svs[i], ity); @@ -3292,13 +3446,13 @@ void cfree_cg_inline_asm(CfreeCg *g, CfreeCgInlineAsm asm_block) { } else if (s[0] == 'r') { in_ops[i] = api_force_reg(g, &in_svs[i], ity); } else if (s[0] == 'i') { - if (in_svs[i].op.kind != OPK_IMM) { + if (!api_sv_op_is(&in_svs[i], OPK_IMM)) { compiler_panic(g->c, g->cur_loc, "CfreeCg: asm 'i' constraint requires an immediate"); } in_ops[i] = in_svs[i].op; } else if (s[0] == 'm') { - if (in_svs[i].op.kind == OPK_INDIRECT) { + if (api_sv_op_is(&in_svs[i], OPK_INDIRECT)) { in_ops[i] = in_svs[i].op; } else if (api_is_lvalue_sv(&in_svs[i])) { CfreeCgTypeId pty = @@ -3445,50 +3599,48 @@ void cfree_cg_jump(CfreeCg *g, CfreeCgLabel label) { g->target->jump(g->target, (Label)label); } -void cfree_cg_branch_true(CfreeCg *g, CfreeCgLabel label) { - ApiSValue v; +static void api_branch_if(CfreeCg *g, ApiSValue *v, int branch_when_true, + Label label) { CGTarget *T; CfreeCgTypeId ty; if (!g) return; T = g->target; - v = api_pop(g); - ty = v.type ? v.type : builtin_id(CFREE_CG_BUILTIN_I32); - if (v.op.kind == OPK_IMM) { - if (v.op.v.imm != 0) - T->jump(T, (Label)label); - api_release(g, &v); + ty = v->type ? v->type : builtin_id(CFREE_CG_BUILTIN_I32); + if (v->op.kind == OPK_IMM && v->kind == SV_OPERAND) { + if ((v->op.v.imm != 0) == !!branch_when_true) + T->jump(T, label); + api_release(g, v); + return; + } + if (v->kind == SV_CMP) { + CmpOp op = branch_when_true ? v->cmp_op : api_invert_cmp(v->cmp_op); + T->cmp_branch(T, op, v->cmp_a, v->cmp_b, label); + api_release(g, v); return; } { - Operand a = api_force_reg(g, &v, ty); + Operand a = api_force_reg(g, v, ty); Operand zero = api_op_imm(0, ty); - T->cmp_branch(T, CMP_NE, a, zero, (Label)label); - api_release(g, &v); + T->cmp_branch(T, branch_when_true ? CMP_NE : CMP_EQ, a, zero, label); + api_release(g, v); } } -void cfree_cg_branch_false(CfreeCg *g, CfreeCgLabel label) { +void cfree_cg_branch_true(CfreeCg *g, CfreeCgLabel label) { ApiSValue v; - CGTarget *T; - CfreeCgTypeId ty; if (!g) return; - T = g->target; v = api_pop(g); - ty = v.type ? v.type : builtin_id(CFREE_CG_BUILTIN_I32); - if (v.op.kind == OPK_IMM) { - if (v.op.v.imm == 0) - T->jump(T, (Label)label); - api_release(g, &v); + api_branch_if(g, &v, 1, (Label)label); +} + +void cfree_cg_branch_false(CfreeCg *g, CfreeCgLabel label) { + ApiSValue v; + if (!g) return; - } - { - Operand a = api_force_reg(g, &v, ty); - Operand zero = api_op_imm(0, ty); - T->cmp_branch(T, CMP_EQ, a, zero, (Label)label); - api_release(g, &v); - } + v = api_pop(g); + api_branch_if(g, &v, 0, (Label)label); } void cfree_cg_switch(CfreeCg *g, CfreeCgSwitch sw) { @@ -3593,7 +3745,7 @@ static void api_scope_store_result(CfreeCg *g, ApiCgScope *s, if (!api_scope_has_result(s)) return; dst = api_op_local(s->result_slot, s->result_type); - src = (result->op.kind == OPK_IMM || result->op.kind == OPK_REG) + src = api_sv_op_is_reg_or_imm(result) ? result->op : api_force_reg(g, result, s->result_type); g->target->store(g->target, dst, src, @@ -3692,96 +3844,64 @@ void cfree_cg_break(CfreeCg *g, CfreeCgScope scope) { void cfree_cg_break_true(CfreeCg *g, CfreeCgScope scope) { ApiCgScope *s; ApiSValue cond; - CGTarget *T; - CfreeCgTypeId ty; if (!g || scope == 0) return; s = api_scope_from_handle(g, scope, 0, "CfreeCg: break_true"); if (!s) return; - T = g->target; cond = api_pop(g); - ty = cond.type ? cond.type : builtin_id(CFREE_CG_BUILTIN_I32); if (api_scope_has_result(s)) { ApiSValue result = api_pop(g); - if (cond.op.kind == OPK_IMM) { + if (cond.kind == SV_OPERAND && cond.op.kind == OPK_IMM) { if (cond.op.v.imm != 0) { api_scope_store_result(g, s, &result); - T->jump(T, s->break_lbl); + g->target->jump(g->target, s->break_lbl); } else { api_release(g, &result); } api_release(g, &cond); } else { - Label skip = T->label_new(T); - Operand a = api_force_reg(g, &cond, ty); - Operand zero = api_op_imm(0, ty); - T->cmp_branch(T, CMP_EQ, a, zero, skip); - api_release(g, &cond); + Label skip = g->target->label_new(g->target); + api_branch_if(g, &cond, 0, skip); api_scope_store_result(g, s, &result); - T->jump(T, s->break_lbl); - T->label_place(T, skip); + g->target->jump(g->target, s->break_lbl); + g->target->label_place(g->target, skip); } } else { - if (cond.op.kind == OPK_IMM) { - if (cond.op.v.imm != 0) - T->jump(T, s->break_lbl); - api_release(g, &cond); - } else { - Operand a = api_force_reg(g, &cond, ty); - Operand zero = api_op_imm(0, ty); - T->cmp_branch(T, CMP_NE, a, zero, s->break_lbl); - api_release(g, &cond); - } + api_branch_if(g, &cond, 1, s->break_lbl); } } void cfree_cg_break_false(CfreeCg *g, CfreeCgScope scope) { ApiCgScope *s; ApiSValue cond; - CGTarget *T; - CfreeCgTypeId ty; if (!g || scope == 0) return; s = api_scope_from_handle(g, scope, 0, "CfreeCg: break_false"); if (!s) return; - T = g->target; cond = api_pop(g); - ty = cond.type ? cond.type : builtin_id(CFREE_CG_BUILTIN_I32); if (api_scope_has_result(s)) { ApiSValue result = api_pop(g); - if (cond.op.kind == OPK_IMM) { + if (cond.kind == SV_OPERAND && cond.op.kind == OPK_IMM) { if (cond.op.v.imm == 0) { api_scope_store_result(g, s, &result); - T->jump(T, s->break_lbl); + g->target->jump(g->target, s->break_lbl); } else { api_release(g, &result); } api_release(g, &cond); } else { - Label skip = T->label_new(T); - Operand a = api_force_reg(g, &cond, ty); - Operand zero = api_op_imm(0, ty); - T->cmp_branch(T, CMP_NE, a, zero, skip); - api_release(g, &cond); + Label skip = g->target->label_new(g->target); + api_branch_if(g, &cond, 1, skip); api_scope_store_result(g, s, &result); - T->jump(T, s->break_lbl); - T->label_place(T, skip); + g->target->jump(g->target, s->break_lbl); + g->target->label_place(g->target, skip); } } else { - if (cond.op.kind == OPK_IMM) { - if (cond.op.v.imm == 0) - T->jump(T, s->break_lbl); - api_release(g, &cond); - } else { - Operand a = api_force_reg(g, &cond, ty); - Operand zero = api_op_imm(0, ty); - T->cmp_branch(T, CMP_EQ, a, zero, s->break_lbl); - api_release(g, &cond); - } + api_branch_if(g, &cond, 0, s->break_lbl); } } @@ -3795,51 +3915,25 @@ void cfree_cg_continue(CfreeCg *g, CfreeCgScope scope) { void cfree_cg_continue_true(CfreeCg *g, CfreeCgScope scope) { ApiCgScope *s; ApiSValue v; - CGTarget *T; - CfreeCgTypeId ty; if (!g || scope == 0) return; s = api_scope_from_handle(g, scope, 0, "CfreeCg: continue_true"); if (!s) return; - T = g->target; v = api_pop(g); - ty = v.type ? v.type : builtin_id(CFREE_CG_BUILTIN_I32); - if (v.op.kind == OPK_IMM) { - if (v.op.v.imm != 0) - T->jump(T, s->continue_lbl); - api_release(g, &v); - } else { - Operand a = api_force_reg(g, &v, ty); - Operand zero = api_op_imm(0, ty); - T->cmp_branch(T, CMP_NE, a, zero, s->continue_lbl); - api_release(g, &v); - } + api_branch_if(g, &v, 1, s->continue_lbl); } void cfree_cg_continue_false(CfreeCg *g, CfreeCgScope scope) { ApiCgScope *s; ApiSValue v; - CGTarget *T; - CfreeCgTypeId ty; if (!g || scope == 0) return; s = api_scope_from_handle(g, scope, 0, "CfreeCg: continue_false"); if (!s) return; - T = g->target; v = api_pop(g); - ty = v.type ? v.type : builtin_id(CFREE_CG_BUILTIN_I32); - if (v.op.kind == OPK_IMM) { - if (v.op.v.imm == 0) - T->jump(T, s->continue_lbl); - api_release(g, &v); - } else { - Operand a = api_force_reg(g, &v, ty); - Operand zero = api_op_imm(0, ty); - T->cmp_branch(T, CMP_EQ, a, zero, s->continue_lbl); - api_release(g, &v); - } + api_branch_if(g, &v, 0, s->continue_lbl); } /* ============================================================ @@ -3862,7 +3956,7 @@ void cfree_cg_alloca(CfreeCg *g, uint32_t align, if (!pty) pty = cg_type_ptr_to(g->c, builtin_id(CFREE_CG_BUILTIN_VOID)); sz_op = - (sz.op.kind == OPK_IMM) ? sz.op : api_force_reg(g, &sz, api_sv_type(&sz)); + api_sv_op_is(&sz, OPK_IMM) ? sz.op : api_force_reg(g, &sz, api_sv_type(&sz)); rr = api_alloc_reg_or_spill(g, RC_INT, pty); dst = api_op_reg(rr, pty); T->alloca_(T, dst, sz_op, align ? align : 16);