Pointer induction (023): an inner count's access by a key affine in its round, in range for every round (its opening found it) and in a full list, reads its cell through a pointer, a phi at the loop's head: the column (read from the list) plus the key at round 0 times four where the loop opens, its key's step a round times four added at its latch. The key's nodes, in range, give up nowhere (no snapshot kept), so a key read by such accesses alone is not made; a list found by key alone with such an access is full where the tier begins (else the generic code runs the nest). matmul 23.0 to 14.2 ms (3.1x to 1.9x C)

module_tier's programs sweep lists by keys stepping with a round (in range or not, a list full or not)

3 files changed, 184 insertions, 9 deletions

diff --git a/core/module-jit.c b/core/module-jit.c
index e8858fb..43441b1 100644
--- a/core/module-jit.c
+++ b/core/module-jit.c
@@ -2965,14 +2965,15 @@ static void compile_ints(Block *k, unsigned li) {
 enum { R_NUM, R_INT, R_BOOL }; /* a value's register: d a number; x a whole number as an integer; x 0 or 1 */
 enum {
     T_CONST, T_IN, T_FIELD, T_PHI, T_COUNT, T_ADD, T_SUB, T_MUL, T_DIV, T_MIN, T_MAX, T_NEG, T_FLOOR,
-    T_LT, T_LE, T_GT, T_GE, T_EQ, T_NE, T_NOT, T_AND, T_OR, T_GET, T_FIND_GET, T_FIND, T_HAS, T_SET, T_MOVE, T_SPAN
+    T_LT, T_LE, T_GT, T_GE, T_EQ, T_NE, T_NOT, T_AND, T_OR, T_GET, T_FIND_GET, T_FIND, T_HAS, T_SET, T_MOVE, T_SPAN, T_STEP0, T_STRIDE
 };
 /* T_IN's variables past the locals, states and stack: the outermost loop's round, its rounds or items, its low value. */
 enum { V_ROUND0 = -10, V_COUNT0 = -11, V_LOW0 = -12 };
 /* What a number is to the code that reads it: a number, a bool, an index (of the list in list). */
 enum { K_NUM, K_BOOL, K_INDEX };
 /* A variable: a local (0-63), a state (64-95), a stack slot where ways meet (96-160). */
-enum { V_STATE = 64, V_STACK = 96, VARS = 96 + PURE_MODULE_STACK + 1 };
+/* Past them, a loop's pointer to a column (tier_steps): a phi at its head, no other code's variable. */
+enum { V_STATE = 64, V_STACK = 96, V_STEP = 96 + PURE_MODULE_STACK + 1, STEPS = 8, VARS = V_STEP + STEPS };
 
 typedef struct {
     uint8_t op, rep, kind;
@@ -2982,6 +2983,7 @@ typedef struct {
     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 step;          /* a list access: the pointer to its cell (a loop's phi, tier_steps), or -1 */
     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;
@@ -3091,7 +3093,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->retry = -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->step = -1;
     v->lo = -INFINITY, v->hi = INFINITY;
     int made = (int)t->val_count++;
     if (op == T_PHI) return made; /* bound at its merge */
@@ -3839,6 +3841,7 @@ static void tbound_nodes(Tier *t, int x, int l) {
     TVal *v = &t->vals[x];
     if (x == t->loops[l].k || !tin_loop(t, v->loop, l) || v->loop == -1) return;
     v->bounded = true;
+    v->snap = -1; /* nothing to give up: needed only where something reads it */
     tbound_nodes(t, v->a, l);
     tbound_nodes(t, v->b, l);
 }
@@ -4164,6 +4167,89 @@ static void tier_lists(Tier *t, TList *lists) {
     }
 }
 
+/* Each access of an inner count's own by a key or position its opening
+ * found in range for every round (tier_bounds), affine in its round, in a
+ * full list (the tier's code reads its cell at its key): a pointer to its
+ * cell, a phi at the loop's head (V_STEP), made as the loop opens (the
+ * column plus the key at round 0, times four: T_STEP0) and stepped at its
+ * latch (the key's step a round, times four: T_STRIDE). A list found by
+ * key alone with such an access is taken as full where the tier begins
+ * (else the generic code runs the nest). The access reads its pointer, not
+ * its key (dead unless read elsewhere), and gives up nowhere. */
+/* Whether affine x moves with loop l's round (its round in it). */
+static bool tvaries(const Tier *t, int x, int l) {
+    const TVal *v = &t->vals[x];
+    if (x == t->loops[l].k) return true;
+    if (!tin_loop(t, v->loop, l) || v->loop == -1) return false;
+    return (v->a >= 0 && tvaries(t, v->a, l)) || (v->b >= 0 && tvaries(t, v->b, l));
+}
+
+static void tier_steps(Tier *t) {
+    TList *lists = t->lists;
+    unsigned made = 0;
+    size_t values = t->val_count;
+    for (size_t i = 0; i < values && !t->failed; ++i) {
+        TVal *v = &t->vals[i];
+        int l = v->loop;
+        if (!v->proven || (v->op != T_GET && v->op != T_FIND_GET) || l <= 0 || t->loops[l].walk || !tvaries(t, v->a, l)) continue;
+        if (v->op == T_FIND_GET && !lists[v->list].full) { /* by key alone: full where the tier begins */
+            lists[v->list].full = true;
+            (void)tlist(t, lists, v->list, L_COUNT);
+        }
+        int key = v->a, column = v->c, phi = -1;
+        for (size_t j = values; j < t->val_count && phi < 0; ++j) /* one for a key and a column */
+            if (t->vals[j].op == T_PHI && t->vals[j].var >= V_STEP && t->vals[j].loop == l) {
+                const TVal *start = &t->vals[t->vals[j].in[0]];
+                if (start->a == key && start->b == column) phi = (int)j;
+            }
+        if (phi < 0) {
+            if (made == STEPS) continue;
+            TLoop *loop = &t->loops[l];
+            TMerge *head = &t->merges[loop->head];
+            size_t open = SIZE_MAX, latch = SIZE_MAX;
+            for (size_t k = 0; k < t->item_count; ++k) {
+                if (t->items[k].kind == I_OPEN && t->items[k].loop == l) open = k;
+                if (t->items[k].kind == I_LATCH && t->items[k].loop == l) latch = k;
+            }
+            if (open == SIZE_MAX || latch == SIZE_MAX || head->way_count != 2 || !head->phis) continue;
+            int saved = t->cur_loop;
+            t->cur_loop = -1; /* made with no item (placed below) */
+            int start = tval(t, T_STEP0, R_INT, key, column, l), stride = tval(t, T_STRIDE, R_INT, key, -1, l);
+            phi = tval(t, T_PHI, R_INT, -1, -1, -1);
+            int next = tval(t, T_ADD, R_INT, phi, stride, -1);
+            t->cur_loop = saved;
+            t->entry_count -= 3; /* (tval put three where the tier begins; the phi none) */
+            if (t->failed || !grow_array((void **)&t->items, &t->item_room, t->item_count + 3, sizeof(*t->items))) {
+                t->failed = true;
+                break;
+            }
+            int parent = loop->parent;
+            t->vals[start].loop = parent, t->vals[stride].loop = parent, t->vals[next].loop = l;
+            t->vals[phi].var = V_STEP + (int)made, t->vals[phi].label = loop->head, t->vals[phi].loop = l;
+            tphi_in(t, phi, start);
+            tphi_in(t, phi, next);
+            head->phis[V_STEP + made] = phi;
+            for (int w = start; w <= next; ++w) {
+                TVal *x = &t->vals[w];
+                x->whole = true, x->lo = 0, x->hi = 0x1p62, x->zero = false, x->rep = R_INT;
+            }
+            t->vals[stride].lo = -0x1p62; /* a key may step down */
+            t->vals[next].bounded = true; /* a pointer: no check of its own */
+            /* the latch's step before it; the start and stride after the opening (as it goes on: rounds to run) */
+            memmove(&t->items[latch + 1], &t->items[latch], (t->item_count - latch) * sizeof(TItem));
+            t->items[latch] = (TItem){I_VALUE, next, -1, l, -1, -1};
+            memmove(&t->items[open + 3], &t->items[open + 1], (t->item_count + 1 - open - 1) * sizeof(TItem));
+            t->items[open + 1] = (TItem){I_VALUE, start, -1, parent, -1, -1};
+            t->items[open + 2] = (TItem){I_VALUE, stride, -1, parent, -1, -1};
+            t->item_count += 3;
+            ++made;
+        }
+        v = &t->vals[i];
+        v->step = phi;
+        v->snap = -1; /* in range, in a full list: nothing to give up */
+    }
+}
+
 /* ---- The tier: where each value lives, and its register */
 
 /* Registers the tier gives values: x ones for integers and bools, d ones for numbers (x0, x1, x9, x10, x16, x17, d0-d3 scratch). */
@@ -4303,6 +4389,14 @@ static void tier_needed(Tier *t, bool *need) {
             NEED_SNAP(v->snap);
             continue;
         }
+        if (v->op == T_STEP0 || v->op == T_STRIDE) { /* the key's nodes made outside its loop, and the column */
+            tneed_affine(t, need, work, &top, v->a, v->c);
+            continue;
+        }
+        if (v->step >= 0) { /* an access by its pointer: its key, bits, column and limit not read */
+            NEED(v->step);
+            continue;
+        }
         NEED(v->a);
         NEED(v->b);
         NEED(v->c);
@@ -4339,6 +4433,14 @@ static bool tier_registers(Tier *t) {
         switch (it->kind) {
         case I_VALUE: {
             TVal *v = &t->vals[it->value];
+            if (v->op == T_STEP0 || v->op == T_STRIDE) {
+                tuse_affine(t, v->a, v->c, p);
+                break;
+            }
+            if (v->step >= 0) { /* by its pointer alone */
+                tuse(t, v->step, p);
+                break;
+            }
             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 */
@@ -4578,6 +4680,35 @@ static void tier_affine_at(Tier *t, int x, int l, unsigned kr, unsigned into, co
     tsmall_from_0(t, into, fail);
 }
 
+/* The step of an affine x (tier_bounds) a round of loop l: 1 for its round,
+ * 0 for what the loop does not make, a sum's or difference's of its sides',
+ * a product's its varying side's times the other. */
+static void tier_affine_step(Tier *t, int x, int l, unsigned into, const unsigned *temps) {
+    Emit *e = t->k->e;
+    const TVal *v = &t->vals[x];
+    if (x == t->loops[l].k) {
+        mov_imm(e, into, 1);
+        return;
+    }
+    if (!tin_loop(t, v->loop, l) || v->loop == -1) {
+        mov_imm(e, into, 0);
+        return;
+    }
+    if (v->op == T_MUL) {
+        bool a_out = !tin_loop(t, t->vals[v->a].loop, l) || t->vals[v->a].loop == -1;
+        int same = a_out ? v->a : v->b, varies = a_out ? v->b : v->a;
+        tier_affine_step(t, varies, l, into, temps);
+        if (t->vals[same].op == T_CONST) mov_imm(e, temps[0], (uint64_t)(int64_t)t->vals[same].num);
+        else mov_reg(e, temps[0], treg(t, same));
+        mul_reg(e, into, into, temps[0]);
+        return;
+    }
+    tier_affine_step(t, v->a, l, into, temps);
+    tier_affine_step(t, v->b, l, temps[0], temps + 1);
+    if (v->op == T_ADD) add_reg(e, into, into, temps[0]);
+    else sub_reg(e, into, into, temps[0]);
+}
+
 /* 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, less; } TMove; /* less: the source less one */
 static void tier_moves_as(Tier *t, int g, int way, int k, int next);
@@ -4884,6 +5015,10 @@ static void tier_value(Tier *t, int vi) {
     unsigned r = v->reg >= 0 ? (unsigned)v->reg : X16;
     int fail = v->snap >= 0 ? tfail(t, v->snap) : -1;
     const TVal *a = v->a >= 0 ? &t->vals[v->a] : NULL, *b2 = v->b >= 0 ? &t->vals[v->b] : NULL;
+    if (v->step >= 0 && (v->op == T_GET || v->op == T_FIND_GET)) { /* its cell where its pointer is (tier_steps) */
+        put(e, 0xB9400000 | treg(t, v->step) << 5 | r); /* LDR Wr, [pointer] */
+        return;
+    }
     switch (v->op) {
     case T_CONST:
         if (v->rep == R_INT) mov_imm(e, r, (uint64_t)(int64_t)v->num);
@@ -4979,6 +5114,21 @@ static void tier_value(Tier *t, int vi) {
         return;
     }
     case T_COUNT: mov_reg(e, r, treg(t, v->b)); return;
+    case T_STEP0: { /* a loop's pointer at its first round: the column (read from its list: no register kept for it) plus the key there, times four */
+        static const unsigned temps[] = {X16, X17, X9};
+        tier_affine_at(t, v->a, v->c, XZR, X0, temps, tfail(t, t->loops[v->c].open_snap));
+        const TVal *column = &t->vals[v->b];
+        load64(e, X16, tbase(t, B_LISTS, X16), (size_t)column->list * sizeof(PureList *));
+        load64(e, X16, X16, pure_list_layout[LIST_COLUMNS_AT] + column->field * sizeof(void *));
+        add_lsl(e, r, X16, X0, 2);
+        return;
+    }
+    case T_STRIDE: { /* its step a round, times four */
+        static const unsigned temps[] = {X16, X17, X9};
+        tier_affine_step(t, v->a, v->c, X0, temps);
+        lsl_imm(e, r, X0, 2);
+        return;
+    }
     case T_SPAN: { /* a count's rounds: its bounds whole within 2^53, else LIMIT */
         unsigned low = tx(t, v->a, X0, fail), high = tx(t, v->b, X1, fail);
         if (a->rep == R_NUM) tsmall_check(t, low, fail);
@@ -5408,7 +5558,7 @@ static int tier_input(const PureModule *m, PureBlock block) {
 /* The tier's values and items on stderr (PURE_TIER_DUMP), to read what it made. */
 static void tier_dump(const Tier *t) {
     static const char *ops[] = {"const", "in", "field", "phi", "count", "add", "sub", "mul", "div", "min", "max", "neg", "floor",
-                                "lt", "le", "gt", "ge", "eq", "ne", "not", "and", "or", "get", "find_get", "find", "has", "set", "move", "span"};
+                                "lt", "le", "gt", "ge", "eq", "ne", "not", "and", "or", "get", "find_get", "find", "has", "set", "move", "span", "step0", "stride"};
     static const char *items[] = {"value", "merge", "unless", "jump", "open", "latch", "break", "done"};
     for (size_t i = 0; i < t->val_count; ++i) {
         const TVal *v = &t->vals[i];
@@ -5458,6 +5608,8 @@ static Tier *tier_plan(Block *k, unsigned li) {
     if (!t->failed) tier_defer(t);
     const char *bounds = getenv("PURE_TIER_BOUNDS");
     if (!t->failed && !(bounds && !strcmp(bounds, "0"))) tier_bounds(t);
+    const char *steps = getenv("PURE_TIER_STEPS");
+    if (!t->failed && !(steps && !strcmp(steps, "0"))) tier_steps(t);
     if (t->failed || !tier_registers(t)) {
         if (getenv("PURE_TIER_DUMP")) {
             fprintf(stderr, "tier: nest %u not taken (%s)\n", li, t->why ? t->why : "built");
diff --git a/docs/design/023-optimizing-tier.md b/docs/design/023-optimizing-tier.md
index 6a4c23d..fa8065e 100644
--- a/docs/design/023-optimizing-tier.md
+++ b/docs/design/023-optimizing-tier.md
@@ -148,6 +148,14 @@ roots와 BFS만 기계어로 돈다. 나머지는 JIT의 값 모형이 거르거
   거의 공짜다. 그래서 순서는 **포인터 귀납 변수**(아핀 키의 칸 주소를 루프의 φ로) 다음에, 그래도 비트의 분기가 남으면 **꽉 찬
   경우의 사본**(키로만 찾는 리스트가 모두 꽉 찬 DENSE일 때의 루프 본문을 하나 더 내고 루프를 열 때 고른다). 같은 배열을 정적으로
   둔 C는 3.8 ms(바깥 루프를 벡터로 묶는다), `natural.h`의 C는 7.5.
+- **포인터 귀납 변수**(했다): 안쪽 셈 루프가 여는 곳에서 범위가 증명된 접근 중, 키가 그 루프의 회차와 함께 아핀으로 움직이고
+  리스트가 꽉 찬 것은 칸의 포인터를 루프 머리의 φ로 둔다. 시작은 루프를 열 때 열의 주소(리스트에서 읽는다: 열을 레지스터에 두지
+  않게) 더하기 회차 0의 키 곱하기 4, 보폭은 키를 회차로 미분한 값 곱하기 4(합과 차는 양쪽의, 곱은 움직이는 쪽의 것에 다른 쪽을
+  곱한다)이고, 래치에서 더한다. 접근은 키를 읽지 않으므로 키의 계산이 다른 곳에서 안 읽히면 죽는다(범위가 증명된 키의 노드는
+  스냅숏도 없다). 키로만 찾는 리스트에 이런 접근이 있으면 계층은 그 리스트를 꽉 찬 것으로 받는다: 꽉 차지 않았거나 HASHED면
+  계층이 시작하는 곳에서 일반 코드가 그 묶음을 돈다(읽는 키가 모두 있어도 다른 곳이 비면 그렇다: 그때는 느려진다. 루프를 열 때
+  읽을 키들만 있는지 보는 것이 다음이다). 행렬곱 23.0 ms에서
+  14.2(C의 1.9배), 안쪽 루프의 명령 14개.
 
 ### 6. 표현 (바닥이 가정한 것)
 
diff --git a/tests/check.py b/tests/check.py
index bb78bc6..5ed8e8b 100644
--- a/tests/check.py
+++ b/tests/check.py
@@ -1217,14 +1217,15 @@ def module_assumptions(aup, pure, work):
 def tier_program(rng):
     """A random handler for module_tier: loops over counts and a list,
     numbers in locals and states, a keyed list read and set by key, one
-    whose keys came out of order read by key alone (HASHED), ifs and
+    whose keys came out of order read by key alone (HASHED), one of small
+    keys read by key alone (full, or not where keys are left out), ifs and
     breaks, with what fails (a key not there, not whole, 0 divided by, a
     cell past its column's width) as likely as not."""
     names = iter('jklpqrxyz')
     def number(depth, loops):
         choices = ['const', 'const', 'loop', 'local', 'field']
         if depth < 3:
-            choices += ['add', 'sub', 'mul', 'div', 'floor', 'minmax', 'cell', 'add', 'sub', 'hashed']
+            choices += ['add', 'sub', 'mul', 'div', 'floor', 'minmax', 'cell', 'add', 'sub', 'hashed', 'keyed']
         kind = rng.choice(choices)
         if kind == 'const':
             return rng.choice(['0', '1', '2', '3', '7', '255', '256', '1000', '0.5', '2.25', '(0 - 3)', '(0 - 0)', '65536'])
@@ -1238,6 +1239,8 @@ def tier_program(rng):
             return f't[{key(depth + 1, loops)}].v' if rng.random() < 0.7 else 'c.v' if 'c' in loops else 's'
         if kind == 'hashed':
             return f'h[{hashed_key(depth + 1, loops)}].v'
+        if kind == 'keyed':  # g: read by key alone (by a pointer where the key steps with a loop's round)
+            return f'g[{key(depth + 1, loops)}].v'
         if kind == 'floor':
             return f'floor({number(depth + 1, loops)} / {rng.choice(["2", "3", "7", "go.q", "u"])})'
         if kind == 'minmax':
@@ -1264,7 +1267,7 @@ def tier_program(rng):
     def statements(depth, loops, indent, inside):
         lines = []
         for _ in range(rng.randint(1, 3)):
-            kind = rng.choice(['s', 's', 'u', 'acc', 'if', 'loop', 'walk', 'set', 'set', 'break'] if depth < 3 else ['s', 'u', 'set', 'break'])
+            kind = rng.choice(['s', 's', 'u', 'acc', 'if', 'loop', 'walk', 'set', 'set', 'break', 'sweep'] if depth < 3 else ['s', 'u', 'set', 'break'])
             pad = '  ' * indent
             if kind == 's':
                 lines.append(f'{pad}s = s + {number(1, loops)}')
@@ -1290,6 +1293,17 @@ def tier_program(rng):
                 lines.append(f'{pad}for {name} in {rng.choice(["0", "1", "go.q"])} .. {rng.choice(["3", "go.n", "go.m", name if False else "5"])} {{')
                 lines += statements(depth + 1, loops + [name], indent + 1, True)
                 lines.append(f'{pad}}}')
+            elif kind == 'sweep':  # keys stepping with a round: read by pointers (023), in range at both ends or not
+                name = next(names, None)
+                if not name:
+                    continue
+                low, high = rng.choice([('0', 'go.n'), ('1', 'go.n'), ('0', 'floor(go.n / 2)'), ('go.q', 'go.n'), ('0', 'go.n + 1')])
+                affine = rng.choice([name, f'{name} * 2', f'{name} + 3', f'go.n - 1 - {name}', f'{name} * 3 - {name}'])
+                lines.append(f'{pad}for {name} in {low} .. {high} {{')
+                lines.append(f'{pad}  s = s + {rng.choice(["g", "t", "g"])}[{affine}].v')
+                if rng.random() < 0.5:
+                    lines += statements(depth + 1, loops + [name], indent + 1, True)
+                lines.append(f'{pad}}}')
             elif kind == 'walk' and 'c' not in loops:
                 lines.append(f'{pad}for c in f {{')
                 lines += statements(depth + 1, loops + ['c'], indent + 1, True)
@@ -1299,9 +1313,10 @@ def tier_program(rng):
     return '\n'.join([
         'record Cell {', '  at = 0', '  v = 0', '}', 'state out = 0', 'state acc = 0',
         'input go = message {', '  n: u32', '  m: u32', '  q: u32', '}',
-        'on go {', '  let t: list of Cell by at', '  let f: list of Cell', '  let h: list of Cell by at',
+        'on go {', '  let t: list of Cell by at', '  let f: list of Cell', '  let h: list of Cell by at', '  let g: list of Cell by at',
         '  for i in 0 .. go.n {', f'    t.add(Cell {{ at: i, v: {rng.choice(["i", "0", "(i * 3)", "1"])} }})',
-        '    f.append(Cell { at: i * 2, v: i })', '    h.add(Cell { at: i * 7919 - floor(i * 7919 / 1009) * 1009 + 5000000, v: i * 5 })', '  }',
+        '    f.append(Cell { at: i * 2, v: i })', '    h.add(Cell { at: i * 7919 - floor(i * 7919 / 1009) * 1009 + 5000000, v: i * 5 })',
+        f'    g.add(Cell {{ at: {rng.choice(["i", "i", "i + floor(i / 40)"])}, v: i * 3 }})', '  }',
         '  let s = 0', '  let u = 1',
         '  for i in 0 .. go.m {', *body, '  }',
         '  out = s', '  acc = acc + u', '}', ''])