diff options
| -rw-r--r-- | core/module-jit.c | 75 | ||||
| -rw-r--r-- | docs/design/023-optimizing-tier.md | 7 | ||||
| -rw-r--r-- | tests/check.py | 25 |
3 files changed, 92 insertions, 15 deletions
diff --git a/core/module-jit.c b/core/module-jit.c index 2732b6a..e8858fb 100644 --- a/core/module-jit.c +++ b/core/module-jit.c @@ -1354,6 +1354,8 @@ static void store_tagged(Block *k, unsigned h, unsigned col, unsigned at, int sl * its room and its bits' reach), the count or the items added counted in * their register, the event's headroom less the item's bytes; nothing else * written until a call or the nest's end (books_back). */ +static void append(Block *k, const PureOp *op, uint32_t pc, unsigned height); + static void append_books(Block *k, const PureOp *op, uint32_t pc, unsigned height) { Emit *e = k->e; const PureModule *m = k->m; @@ -1374,7 +1376,8 @@ static void append_books(Block *k, const PureOp *op, uint32_t pc, unsigned heigh } unsigned some = key == 1 ? columns[1] : columns[0]; /* a column kept: 0 when the list is not in that form */ size_t bytes = row_bytes(m, list); - cbz_x(e, some, slow); + int other = new_label(e), done = new_label(e); /* a keyed list not DENSE (HASHED): as append does it, the headroom kept */ + cbz_x(e, some, key ? other : slow); if (!key) { load64(e, X16, X24, list * sizeof(PureList *)); load64(e, X17, X16, pure_list_layout[LIST_ROOM_AT]); @@ -1408,6 +1411,12 @@ static void append_books(Block *k, const PureOp *op, uint32_t pc, unsigned heigh add_imm(e, pending, pending, 1); } slow_back(k, s, V_MEM, 0); + if (key) { + b(e, done); + bind(e, other); + append(k, op, pc, height); + } + bind(e, done); } /* A key's bits in a HASHED list's table (module-list.c's key_bits: -0 as +0) into x17. */ @@ -2972,6 +2981,8 @@ typedef struct { bool bounded; /* an integer its loop's opening bounds (its ends checked there: no check of its own) */ bool proven; /* a list access whose key or position its loop's opening found in range */ bool fused; /* a comparison only the branch right after it reads: its flags, no register */ + bool deferred; /* a number's arithmetic whose finiteness its one reader, right after it, checks (tier_defer) */ + int retry; /* where its finiteness check gives up, the first of such a run's snapshot; or -1: its own */ bool aliased; /* a full list's position found: its key's register (they are equal) */ uint16_t list, field; int a, b, c, d; /* operands: values, or -1 */ @@ -3080,7 +3091,7 @@ static int tval(Tier *t, unsigned op, unsigned rep, int a, int b, int c) { TVal *v = &t->vals[t->val_count]; memset(v, 0, sizeof(*v)); v->op = (uint8_t)op, v->rep = (uint8_t)rep, v->a = a, v->b = b, v->c = c; - v->snap = -1, v->loop = t->cur_loop, v->var = -1, v->label = -1, v->reg = -1, v->d = -1; + v->snap = -1, v->loop = t->cur_loop, v->var = -1, v->label = -1, v->reg = -1, v->d = -1, v->retry = -1; v->lo = -INFINITY, v->hi = INFINITY; int made = (int)t->val_count++; if (op == T_PHI) return made; /* bound at its merge */ @@ -4008,6 +4019,29 @@ static void tier_facts(Tier *t) { if (t->vals[i].lo > t->vals[i].hi && t->vals[i].rep != R_BOOL) t->vals[i].lo = -INFINITY, t->vals[i].hi = INFINITY, t->vals[i].whole = false, t->vals[i].zero = true; } +/* A run of numbers' arithmetic each read by the next alone, right after it + * (no other code between but constants): only the last checks it is finite. A number not + * finite stays not finite through an add, a sub, a mul, or as what a + * division divides; where it is not, the code gives up at the run's first + * snapshot, so the executor makes the run again and fails where the + * executor does. */ +static void tier_defer(Tier *t) { + for (size_t i = 0; i + 1 < t->item_count; ++i) { + size_t next = i + 1; /* the next value but constants (made as they are: no check, nothing changed) */ + while (next < t->item_count && t->items[next].kind == I_VALUE && t->vals[t->items[next].value].op == T_CONST) ++next; + if (t->items[i].kind != I_VALUE || next == t->item_count || t->items[next].kind != I_VALUE) continue; + TVal *v = &t->vals[t->items[i].value], *w = &t->vals[t->items[next].value]; + int vi = t->items[i].value; + bool arith = v->rep == R_NUM && v->op >= T_ADD && v->op <= T_DIV && v->snap >= 0 && v->uses == 1; + bool reads = w->rep == R_NUM && w->snap >= 0 && w->loop == v->loop && + (((w->op == T_ADD || w->op == T_SUB || w->op == T_MUL) && (w->a == vi || w->b == vi)) || + (w->op == T_DIV && w->a == vi && w->b != vi && (t->vals[w->b].lo > 0 || t->vals[w->b].hi < 0))); + if (!arith || !reads || tfinite(v) || tfinite(w)) continue; + v->deferred = true; + w->retry = v->retry >= 0 ? v->retry : v->snap; + } +} + /* Each value's register: a whole number an integer, else a number (a bool's as made). Uses counted. */ static void tier_reps(Tier *t) { for (size_t i = 0; i < t->val_count; ++i) { @@ -4169,8 +4203,9 @@ static void tuse_affine(Tier *t, int x, int l, int at) { static void tuse_snap(Tier *t, int s, int at) { if (s < 0) return; const TSnap *snap = &t->snaps[s]; - for (int var = 0; var < VARS; ++var) - if (var < V_STACK ? tchanged(t, var, snap->vars[var]) : snap->vars[var] >= 0) tuse(t, snap->vars[var], at); + for (int var = 0; var < VARS; ++var) /* (a constant written as the constant it is) */ + if ((var < V_STACK ? tchanged(t, var, snap->vars[var]) : snap->vars[var] >= 0) && t->vals[snap->vars[var]].op != T_CONST) + tuse(t, snap->vars[var], at); for (int l = snap->loop; l >= 0; l = t->loops[l].parent) { /* the open loops: their rounds, counts and lows */ tuse(t, t->loops[l].k, at), tuse(t, t->loops[l].count, at); if (t->loops[l].low >= 0 && t->vals[t->loops[l].low].op != T_CONST) tuse(t, t->loops[l].low, at); /* a constant written as one */ @@ -4228,7 +4263,8 @@ static void tier_needed(Tier *t, bool *need) { } #define NEED(v) do { int v_ = (v); if (v_ >= 0 && !need[v_]) need[v_] = true, work[top++] = v_; } while (0) #define NEED_SNAP(s) do { if ((s) >= 0) { const TSnap *sn = &t->snaps[s]; \ - for (int var = 0; var < VARS; ++var) if (var < V_STACK ? tchanged(t, var, sn->vars[var]) : sn->vars[var] >= 0) NEED(sn->vars[var]); \ + for (int var = 0; var < VARS; ++var) if ((var < V_STACK ? tchanged(t, var, sn->vars[var]) : sn->vars[var] >= 0) && \ + t->vals[sn->vars[var]].op != T_CONST) NEED(sn->vars[var]); \ for (int l = sn->loop; l >= 0; l = t->loops[l].parent) { NEED(t->loops[l].k); NEED(t->loops[l].count); \ if (t->loops[l].low >= 0 && t->vals[t->loops[l].low].op != T_CONST) NEED(t->loops[l].low); } } } while (0) for (size_t i = 0; i < t->item_count; ++i) { @@ -4272,6 +4308,7 @@ static void tier_needed(Tier *t, bool *need) { NEED(v->c); NEED(v->d); NEED_SNAP(v->snap); + NEED_SNAP(v->retry); for (unsigned w = 0; w < v->ins; ++w) NEED(v->in[w]); } #undef NEED @@ -4304,6 +4341,7 @@ static bool tier_registers(Tier *t) { TVal *v = &t->vals[it->value]; tuse(t, v->a, p), tuse(t, v->b, p), tuse(t, v->c, p), tuse(t, v->d, p); tuse_snap(t, v->snap, p); + tuse_snap(t, v->retry, p); /* the run's first snapshot: given up to from here */ break; } case I_UNLESS: tuse(t, it->value, p); /* fall through */ @@ -4605,6 +4643,19 @@ static bool tier_has_moves(const Tier *t, int g, int way) { return false; } +/* A value a snapshot holds as a number in d0 (or its own d register): a + * constant made there, as the constant it is (its register, if it has one, + * not kept for the snapshot: another value's by then). */ +static unsigned tsnap_d(Tier *t, int v) { + const TVal *x = &t->vals[v]; + if (x->op != T_CONST) return td(t, v, D0); + uint64_t bits; + memcpy(&bits, &x->num, sizeof(bits)); + mov_imm(t->k->e, X9, bits); + fp2(t->k->e, FMOV_DX, D0, X9); + return D0; +} + /* What the tier changed, back where the executor keeps it: the variables * whose values differ from memory's (in vars: a snapshot's or the end's), * the work, the lists it set (their versions). */ @@ -4615,8 +4666,8 @@ static void tier_write(Tier *t, const int *vars) { tbase(t, B_VALUES, X16); for (int var = 0; var < V_STACK; ++var) { int v = vars[var]; - if (!tchanged(t, var, v) || t->vals[v].reg < 0) continue; - unsigned d = td(t, v, D0); + if (!tchanged(t, var, v) || (t->vals[v].reg < 0 && t->vals[v].op != T_CONST)) continue; + unsigned d = tsnap_d(t, v); if (var < V_STATE) store_d(e, d, X17, (size_t)var * sizeof(PureValue)); else store_d(e, d, X16, (size_t)(var - V_STATE) * sizeof(PureValue)); } @@ -4738,8 +4789,8 @@ static void tier_stub(Tier *t, int s) { tbase(t, B_STACK, X17); for (unsigned h = l0->base; h < snap->height; ++h) { int v = snap->vars[V_STACK + h]; - if (v < 0 || t->vals[v].reg < 0) continue; - store_d(e, td(t, v, D0), X17, AT(h)); + if (v < 0 || (t->vals[v].reg < 0 && t->vals[v].op != T_CONST)) continue; + store_d(e, tsnap_d(t, v), X17, AT(h)); if (t->vals[v].kind == K_INDEX) { mov_w(e, X9, (uint32_t)t->vals[v].list & 0xFFFF); store_h(e, X9, X17, AT(h) + OWNER); @@ -5000,7 +5051,8 @@ static void tier_value(Tier *t, int vi) { unsigned x = td(t, v->a, D0), y = td(t, v->b, D1); uint32_t fop = v->op == T_ADD ? FADD : v->op == T_SUB ? FSUB : v->op == T_MUL ? FMUL : v->op == T_MIN ? FMIN : FMAX; fp3(e, fop, r, x, y); - if (fail >= 0 && (v->op == T_ADD || v->op == T_SUB || v->op == T_MUL) && !tfinite(v)) tfinite_check(t, r, fail); + if (fail >= 0 && (v->op == T_ADD || v->op == T_SUB || v->op == T_MUL) && !tfinite(v) && !v->deferred) + tfinite_check(t, r, v->retry >= 0 ? tfail(t, v->retry) : fail); return; } case T_DIV: @@ -5015,7 +5067,7 @@ static void tier_value(Tier *t, int vi) { b_cond(e, EQ, fail); } fp3(e, FDIV, r, x, y); - if (!tfinite(v)) tfinite_check(t, r, fail); + if (!tfinite(v) && !v->deferred) tfinite_check(t, r, v->retry >= 0 ? tfail(t, v->retry) : fail); return; } case T_NEG: @@ -5403,6 +5455,7 @@ static Tier *tier_plan(Block *k, unsigned li) { const char *hoist = getenv("PURE_TIER_HOIST"); if (!t->failed && !(hoist && !strcmp(hoist, "0"))) tier_hoist(t); if (!t->failed) tier_reps(t); + if (!t->failed) tier_defer(t); const char *bounds = getenv("PURE_TIER_BOUNDS"); if (!t->failed && !(bounds && !strcmp(bounds, "0"))) tier_bounds(t); if (t->failed || !tier_registers(t)) { diff --git a/docs/design/023-optimizing-tier.md b/docs/design/023-optimizing-tier.md index 2003af5..78a4591 100644 --- a/docs/design/023-optimizing-tier.md +++ b/docs/design/023-optimizing-tier.md @@ -125,6 +125,9 @@ roots와 BFS만 기계어로 돈다. 나머지는 JIT의 값 모형이 거르거 키의 수와 같으면) 그 리스트의 키 비트 검사는 키가 [0, 닿는 범위) 안인지로 바뀌고, 그것도 귀납 변수로 묶이면 루프 앞에서 한 번. - 루프 안의 덧붙이기나 고치기가 리스트를 바꿀 수 있으면, 그 리스트에 대한 사실은 그 명령 뒤에서 다시 확인한다(022의 규칙). - 끌어낸 검사가 실패하면 그 루프를 검사가 제자리에 있는 코드(지금의 JIT, 또는 실행기)로 돈다. 결함은 위의 원칙대로 실행기가 낸다. +- 수의 산수가 줄을 이어 하나씩 다음 것만 읽으면(사이에 상수 말고 다른 코드 없이) 유한 검사는 마지막 것만 한다(했다). 유한하지 않은 + 수는 더하기, 빼기, 곱하기, 나누는 수로서 그대로 유한하지 않으므로, 마지막이 유한하지 않으면 줄의 첫 스냅숏으로 물러나 실행기가 줄을 + 다시 하고 실행기가 내는 자리에서 결함을 낸다. 스냅숏의 상수는 레지스터에 두지 않고 그 상수로 쓴다. roots 12.2 ms에서 10.9. ### 4. 작업량과 메모리 몫을 루프마다 @@ -142,7 +145,7 @@ roots와 BFS만 기계어로 돈다. 나머지는 JIT의 값 모형이 거르거 ### 6. 표현 (바닥이 가정한 것) - **희소한 키로 둔 이벤트의 리스트**(HASHED, 했다): 수 키가 차례를 어기고 작은 정수가 아니면, 항목의 셀을 키 집합(열린 주소, - 키의 비트, 칸의 4/5까지: 표가 L3에 들게; 절반까지면 조인 112 ms, 4/5면 84)의 그 키의 칸에 둔다. DENSE가 키의 자리에 두듯 해서, 키로 찾기는 칸의 키와 셀을 같은 번호로 읽는다(C의 해시 + 키의 비트, 칸의 4/5까지: 표가 L3에 들게; 절반까지면 조인 112 ms, 4/5면 84; 일반 코드의 장부 루프에서도 HASHED에 바로 넣으면 74)의 그 키의 칸에 둔다. DENSE가 키의 자리에 두듯 해서, 키로 찾기는 칸의 키와 셀을 같은 번호로 읽는다(C의 해시 표처럼 두 미스가 겹친다; 넣은 차례로 두고 칸에 위치를 두면 미스가 줄을 선다: 조인 129 ms에서 108). 차례가 필요할 때(걷기, 위치, 찾은 위치, 되돌리기, 공유, 저장) 칸들을 키의 비트 순서로 여덟 비트씩 기수 정렬해 FLAT이 된다. 지우기까지 두 번이고, 그다음은 FLAT이나 트리다(오가며 정렬하지 않게). 일반 코드의 APPEND도 표가 자라지 않는 한 칸을 바로 찾아 넣는다(sort 58 ms에서 37). 계층은 키로만 찾는 리스트의 비트 열 1번 비트로 HASHED를 알고(한계는 모두 1: 키의 경계 검사가 @@ -153,7 +156,7 @@ roots와 BFS만 기계어로 돈다. 나머지는 JIT의 값 모형이 거르거 키 집합이 아니므로 버린다. - **찾은 자리에 쓰기**(PLAN_ROW, 했다): `counts[w].n = counts[w].n + 1`처럼 FIND가 낸 위치를 ITEM_SET만 받고 그 사이가 한 줄(뛰어 들거나 나가지 않음)이며 리스트를 키로 찾기(합친 FIND, HAS) 말고 건드리지 않으면, 로더가 둘을 묶는다. HASHED 리스트는 위치 대신 - 칸에 쓴다(위치를 내면 정렬된다). words 453 ms에서 217. + 칸에 쓴다(위치를 내면 정렬된다). words 453 ms에서 211–219. 남은 것은 실행기다: 루프가 텍스트를 만들어(`"w{n}"`을 세 번, aup의 let은 텍스트를 담지 못한다) 일반 코드로 가지 못한다. - 텍스트 보간의 정수는 정수의 자릿수로 바로 쓴다(지금의 수→텍스트가 정수에서 내는 것과 같은 바이트). - 저장된 리스트는 022 그대로(트리, 많이 찾으면 편 배열). diff --git a/tests/check.py b/tests/check.py index 30ee5f0..bb78bc6 100644 --- a/tests/check.py +++ b/tests/check.py @@ -1153,6 +1153,26 @@ on go { } """ +# Numbers' arithmetic in a run, each read by the next alone: only the last +# checks it is finite, giving up at the run's first snapshot (023); the +# product passes the largest number at the 56th round. +CHAIN_SOURCE = """state out = 0 +state steps = 0 +input go = message { + n: u32 +} +on go { + let s = 1 + let c = 0 + for i in 0 .. go.n { + s = (s * 1000000 + i) / 3 * 2 + 1 + c = c + 1 + } + out = s + steps = c +} +""" + def module_assumptions(aup, pure, work): """The compiled code's integers (Pure docs/design/022) where they stop holding: a loop whose columns hold small whole numbers until, halfway, @@ -1182,11 +1202,12 @@ def module_assumptions(aup, pure, work): assert outputs['all'] == outputs['0'], next((a, b) for a, b in zip(outputs['all'].splitlines(), outputs['0'].splitlines()) if a != b) assert all(json.loads(line)['fault'] == 'none' for line in outputs['0'].splitlines()) messages = ''.join(f'message go {struct.pack("<III", n, m, q).hex()}\nwork\n' for n, m, q in ((70, 40, 3), (130, 25, 2))) - for name, text in (('merges', MERGES_SOURCE), ('budget', BUDGET_SOURCE)): # the tier's, as the executor: states, faults, work + for name, text in (('merges', MERGES_SOURCE), ('budget', BUDGET_SOURCE), ('chain', CHAIN_SOURCE)): # the tier's, as the executor source, program = work / f'{name}.aup', work / f'{name}.pmod' source.write_text(text) compile_module(aup, source, program) - outputs = {jit: subprocess.run([str(pure / 'build/pure-run'), str(program)], input=messages + 'budget 1201\n' + messages, + given = ''.join(f'message go {struct.pack("<I", n).hex()}\nwork\n' for n in (3, 50, 60, 100)) if name == 'chain' else messages + outputs = {jit: subprocess.run([str(pure / 'build/pure-run'), str(program)], input=given + 'budget 1201\n' + given, capture_output=True, text=True, timeout=120, env=dict(os.environ, PURE_JIT=jit)).stdout for jit in ('all', '0')} assert outputs['all'] == outputs['0'], (name, next((a, b) for a, b in zip(outputs['all'].splitlines(), outputs['0'].splitlines()) if a != b)) |