From 5160ac90388a29445743ba3c2208dcf2775b0b04 Mon Sep 17 00:00:00 2001 From: eunhhu Date: Mon, 5 Oct 2026 16:54:45 +0100 Subject: The tier's loops tighter: a latch's way out takes the round as the next less one (the round's register the next's: no move on the way back), a way's moves only for phis something needs, a number over a power of two times its reciprocal (the same number), a constant only numbers' arithmetic reads a number made where the tier begins, the 2^53 check in three instructions. roots 14.1 to 12.2 ms (1.78x C), knapsack 8.5 to 7.8 (1.26x) --- core/module-jit.c | 92 +++++++++++++++++++++++++++++++++++++++++++------------ 1 file changed, 72 insertions(+), 20 deletions(-) (limited to 'core') diff --git a/core/module-jit.c b/core/module-jit.c index 1c6de64..4e91a38 100644 --- a/core/module-jit.c +++ b/core/module-jit.c @@ -3959,6 +3959,17 @@ static void tier_reps(Tier *t) { const TVal *a = &t->vals[d->a], *b = &t->vals[d->b]; if (a->whole && b->whole && a->lo >= 0 && b->lo > 0) d->integers = true; } + size_t made = t->val_count; + for (size_t i = 0; i < made; ++i) { /* a number over a power of two: times its reciprocal (the same number, exactly) */ + TVal *v = &t->vals[i]; + if (v->op != T_DIV || v->integers || t->vals[v->b].op != T_CONST) continue; + double b = t->vals[v->b].num; + int exp; + if (fabs(frexp(b, &exp)) != 0.5 || !(fabs(b) >= 0x1p-1000 && fabs(b) <= 0x1p1000)) continue; + int c = tconst(t, 1 / b); /* where the tier begins */ + t->vals[c].uses = 1, --t->vals[v->b].uses; + t->vals[i].op = T_MUL, t->vals[i].b = c; + } tier_facts(t); for (unsigned l = 0; l < t->loop_count; ++l) /* a loop's round and rounds are integers */ if (!t->vals[t->loops[l].k].whole || !t->vals[t->loops[l].count].whole) t->failed = true, t->why = "rounds"; @@ -3971,6 +3982,27 @@ static void tier_reps(Tier *t) { if (v->op == T_SET) continue; v->rep = v->whole ? R_INT : R_NUM; } + for (size_t i = 0; i < t->val_count; ++i) { /* a constant only numbers' arithmetic reads: a number, made where the tier begins */ + TVal *c = &t->vals[i]; + if (c->op != T_CONST || c->rep != R_INT) continue; + bool numbers = c->uses > 0; + for (size_t j = 0; j < t->val_count && numbers; ++j) { + const TVal *w = &t->vals[j]; + bool reads = w->a == (int)i || w->b == (int)i || w->c == (int)i || w->d == (int)i; + for (unsigned k = 0; k < w->ins && !reads; ++k) reads = w->in[k] == (int)i; + numbers = !reads || (w->rep == R_NUM && w->op >= T_ADD && w->op <= T_MAX); + } + if (!numbers) continue; + c->rep = R_NUM; + if (c->loop < 0) continue; + size_t at = 0; + while (at < t->item_count && !(t->items[at].kind == I_VALUE && t->items[at].value == (int)i)) ++at; + if (at == t->item_count || !grow_array((void **)&t->entry, &t->entry_room, t->entry_count + 1, sizeof(*t->entry))) continue; + memmove(&t->items[at], &t->items[at + 1], (t->item_count - at - 1) * sizeof(TItem)); + --t->item_count; + t->entry[t->entry_count++] = (int)i; + c->loop = -1; + } } /* The values a list's part takes where the tier begins (made once). */ @@ -4079,17 +4111,28 @@ static void tuse_snap(Tier *t, int s, int at) { } } -/* A way into merge g read at at: its phis' inputs along it. */ -static void tuse_way(Tier *t, int g, int way, int at) { +/* A way into merge g read at at: the inputs along it of the phis something needs (value k read as next - 1 when k >= 0, tier_moves). */ +static void tuse_way(Tier *t, const bool *need, int g, int way, int at, int k, int next) { const TMerge *m = &t->merges[g]; if (way < 0 || !m->phis) return; - for (int var = 0; var < VARS; ++var) - if (m->phis[var] >= 0 && (unsigned)way < t->vals[m->phis[var]].ins) tuse(t, t->vals[m->phis[var]].in[way], at); + for (int var = 0; var < VARS; ++var) { + int phi = m->phis[var]; + if (phi < 0 || !need[phi] || (unsigned)way >= t->vals[phi].ins) continue; + tuse(t, k >= 0 && t->vals[phi].in[way] == k ? next : t->vals[phi].in[way], at); + } } /* Whether loop l's latch pays for its next round: the outermost count's (the generic code opened it); the others paid for all their rounds as they opened. */ static bool tlatch_pays(const Tier *t, int l) { return l == 0 && !t->loops[l].walk; } +/* A latch's round when its way out takes it as the next round less one (the + * round not read past the next then: its register the next's), or -1: a + * loop that does not pay there (the outermost count's work check reads it). */ +static int tlatch_k(const Tier *t, const TItem *it) { + const TLoop *l = &t->loops[it->loop]; + return !tlatch_pays(t, it->loop) && t->vals[l->k].rep == R_INT && t->vals[it->value].rep == R_INT ? l->k : -1; +} + /* Whether item it leaves its loop early (a break): to its exit. */ static bool tbreaks(const Tier *t, const TItem *it) { return it->kind == I_JUMP && it->loop > 0 && it->merge == t->loops[it->loop].exit; } @@ -4194,13 +4237,13 @@ static bool tier_registers(Tier *t) { } case I_UNLESS: tuse(t, it->value, p); /* fall through */ case I_JUMP: - tuse_way(t, it->merge, it->way, p); + tuse_way(t, need, it->merge, it->way, p, -1, -1); if (tbreaks(t, it)) tuse(t, t->loops[it->loop].count, p), tuse(t, t->loops[it->loop].k, p); break; case I_OPEN: { const TLoop *l = &t->loops[it->loop]; tuse(t, l->count, p); - tuse_way(t, it->merge, it->way, p); + tuse_way(t, need, it->merge, it->way, p, -1, -1); tuse_snap(t, it->snap, p); for (unsigned b = 0; b < l->bound_count; ++b) tuse_affine(t, l->bounds[b][0], it->loop, p), tuse(t, l->bounds[b][1], p); break; @@ -4208,8 +4251,8 @@ static bool tier_registers(Tier *t) { case I_LATCH: { const TLoop *l = &t->loops[it->loop]; tuse(t, it->value, p), tuse(t, l->count, p); - tuse_way(t, l->head, (int)t->merges[l->head].way_count - 1, p); - tuse_way(t, it->merge == l->head ? l->exit : it->merge, it->way, p); + tuse_way(t, need, l->head, (int)t->merges[l->head].way_count - 1, p, -1, -1); + tuse_way(t, need, it->merge == l->head ? l->exit : it->merge, it->way, p, tlatch_k(t, it), it->value); if (tlatch_pays(t, it->loop)) tuse_snap(t, it->snap, p); break; } @@ -4379,12 +4422,11 @@ static int tfail(Tier *t, int snap) { } /* An integer below 2^53 in size in r, else to fail (from 0: its bits past 53 none). */ -static void tsmall_check(Tier *t, unsigned r, int fail) { +static void tsmall_check(Tier *t, unsigned r, int fail) { /* from -2^53 below 2^53: its bits from 53 up its sign's */ Emit *e = t->k->e; - mov_imm(e, X9, UINT64_C(1) << 53); - add_reg(e, X10, r, X9); - cmp_lsl(e, X10, X9, 1); - b_cond(e, HS, fail); + put(e, 0x9340FC00 | 53u << 16 | r << 5 | X10); /* ASR x10, r, #53 */ + cmp_asr(e, X10, r, 63); + b_cond(e, NE, fail); } static void tsmall_from_0(Tier *t, unsigned r, int fail) { @@ -4428,8 +4470,12 @@ static void tier_affine_at(Tier *t, int x, int l, unsigned kr, unsigned into, co } /* The moves a way into merge g makes: each phi given its input (a parallel move: what a move would overwrite is moved first, a cycle through scratch). */ -typedef struct { unsigned src, dst; bool src_d, dst_d, convert_bool; } TMove; -static void tier_moves(Tier *t, int g, int way) { +typedef struct { unsigned src, dst; bool src_d, dst_d, convert_bool, less; } TMove; /* less: the source less one */ +static void tier_moves_as(Tier *t, int g, int way, int k, int next); +static void tier_moves(Tier *t, int g, int way) { tier_moves_as(t, g, way, -1, -1); } + +/* Value k (a latch's round, tlatch_k) taken as next - 1. */ +static void tier_moves_as(Tier *t, int g, int way, int k, int next) { Emit *e = t->k->e; const TMerge *m = &t->merges[g]; TMove moves[VARS]; @@ -4439,10 +4485,12 @@ static void tier_moves(Tier *t, int g, int way) { int phi = m->phis[var]; if (phi < 0 || t->vals[phi].reg < 0 || (unsigned)way >= t->vals[phi].ins) continue; const TVal *p = &t->vals[phi], *in = &t->vals[p->in[way]]; + bool less = k >= 0 && p->in[way] == k; + if (less) in = &t->vals[next]; if (in->reg < 0) continue; bool src_d = in->rep == R_NUM, dst_d = p->rep == R_NUM; - if (src_d == dst_d && in->reg == p->reg) continue; - moves[n++] = (TMove){(unsigned)in->reg, (unsigned)p->reg, src_d, dst_d, in->rep == R_BOOL}; + if (!less && src_d == dst_d && in->reg == p->reg) continue; + moves[n++] = (TMove){(unsigned)in->reg, (unsigned)p->reg, src_d, dst_d, in->rep == R_BOOL, less}; } while (n) { bool done = false; @@ -4452,7 +4500,11 @@ static void tier_moves(Tier *t, int g, int way) { blocked = j != i && moves[j].src == moves[i].dst && moves[j].src_d == moves[i].dst_d; if (blocked) continue; TMove mv = moves[i]; - if (mv.src_d && mv.dst_d) put(e, 0x1E604000 | mv.src << 5 | mv.dst); /* FMOV Dd, Dn */ + if (mv.less && mv.dst_d) { /* a round, as a number */ + sub_imm(e, X17, mv.src, 1); + fp2(e, SCVTF_X, mv.dst, X17); + } else if (mv.less) sub_imm(e, mv.dst, mv.src, 1); + else if (mv.src_d && mv.dst_d) put(e, 0x1E604000 | mv.src << 5 | mv.dst); /* FMOV Dd, Dn */ else if (!mv.src_d && !mv.dst_d) mov_reg(e, mv.dst, mv.src); else if (!mv.src_d) fp2(e, mv.convert_bool ? UCVTF_X : SCVTF_X, mv.dst, mv.src); else fp2(e, FCVTZS_X, mv.dst, mv.src); /* a whole number's (its phi an integer's) */ @@ -5086,7 +5138,7 @@ static void tier_emit(Tier *t, int entry, int fallback) { cmp_reg(e, treg(t, it->value), treg(t, l->count)); if (!tlatch_pays(t, it->loop) && !tier_has_moves(t, l->head, back)) { b_cond(e, LO, t->merges[l->head].label); - tier_moves(t, l->exit, it->way); + tier_moves_as(t, l->exit, it->way, tlatch_k(t, it), it->value); break; } b_cond(e, HS, out); @@ -5104,7 +5156,7 @@ static void tier_emit(Tier *t, int entry, int fallback) { tier_moves(t, l->head, back); b(e, t->merges[l->head].label); bind(e, out); - tier_moves(t, l->exit, it->way); + tier_moves_as(t, l->exit, it->way, tlatch_k(t, it), it->value); break; } case I_BREAK: { /* the outermost loop's: what changed written, the generic code breaks it */ -- cgit v1.2.3