The tier's numbers' arithmetic in a run, each read by the next alone (constants between), checks only the last is finite, giving up at the run's first snapshot (the executor makes the run again and fails where it does); a snapshot's constants written as the constants they are, not kept in registers; the generic code's append in a loop keeping its books puts into a HASHED list as append does (its headroom kept). roots 12.2 to 10.9 ms (1.59x C), join 84 to 74 (2.5x)

module_assumptions: a run of products and sums past the largest number (CHAIN_SOURCE)

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))