aboutsummaryrefslogtreecommitdiffstats
path: root/core
diff options
context:
space:
mode:
Diffstat (limited to 'core')
-rw-r--r--core/module-batch.c985
-rw-r--r--core/module-list.c18
-rw-r--r--core/module-list.h13
-rw-r--r--core/module-run.h72
-rw-r--r--core/module.c194
-rw-r--r--core/module.h1
6 files changed, 1227 insertions, 56 deletions
diff --git a/core/module-batch.c b/core/module-batch.c
new file mode 100644
index 0000000..dd9df1a
--- /dev/null
+++ b/core/module-batch.c
@@ -0,0 +1,985 @@
+/* Loops a batch of rounds at a time (docs/design/024). A count's loop
+ * (LOOP) whose block the load planned PLAN_BATCH runs, when the executor
+ * runs it, up to BATCH rounds as one pass over its block: each instruction
+ * once for all of them, a value one per round (a lane). A value is the same
+ * for every round (uniform), a whole number moving by a whole step from
+ * round to round (affine: its first value and its step), or one per round
+ * (lanes: numbers, or whole numbers below 2^32 kept in four bytes each). A
+ * branch on lanes runs both ways, each for its own lanes (the lanes running
+ * an instruction are its mask).
+ *
+ * The pass computes what the rounds would, and changes nothing while it
+ * does: its ITEM_SETs wait for its end, and happen then only when no round
+ * reads a cell an earlier round of the batch sets. A round that would fault,
+ * a value or a list it has no form for, or such a read, and the batch does
+ * not happen: nothing changed, and the executor runs its rounds one by one
+ * (faulting where it would), then batches resume past them, until FAILURES
+ * batches failed in the loop. A fault in a lane a branch left out is no
+ * fault (that round does not run the instruction).
+ *
+ * Work counts as the executor counts it: a round's block and its LOOP, for
+ * each round, and a batch takes no more rounds than the work left pays for.
+ * A local the block sets is left as the last round to set it left it, and
+ * the loop's slot as its last round left it. The lanes and masks are the
+ * thread's (a block a batch runs runs no other block). */
+#include "module-run.h"
+#include <stdlib.h>
+
+enum { BATCH = 1024, BUFFERS = 16, MASKS = 12, SPLITS = 8, READS = 16, STORES = 8, LOCALS = 256, LEAST = 16, FAILURES = 3 };
+
+enum { UNIFORM, AFFINE, LANES };
+typedef struct {
+ uint8_t kind;
+ bool u32; /* lanes: whole numbers below 2^32 in four bytes each (else numbers) */
+ bool temp; /* lanes the stack alone holds: an instruction may leave its result in them */
+ uint16_t owner; /* a position's list (a slot's bytes.owner) */
+ double value, step;
+ void *lane;
+} Val;
+
+/* Lanes running: a 1 or 0 per lane (made when first needed: its parent's
+ * but its sibling's), the lanes a branch split it from (NULL: every lane)
+ * and the other part of that split, and how many run. */
+typedef struct Mask { const uint32_t *lanes; const struct Mask *parent; struct Mask *sibling; unsigned count; } Mask;
+/* An item's field read at rows (known: else any row), and one set: what it sets and in which lanes (NULL: all). */
+typedef struct { uint32_t list, field; bool known; Val rows; } Read;
+typedef struct { uint32_t list, field; Val rows, value; Mask *mask; } Store;
+/* Lanes a branch sent ahead (NULL: every lane): they run again at pc. */
+typedef struct { uint32_t pc; Mask *mask; } Split;
+
+typedef struct {
+ Frame *frame;
+ const PureModule *m;
+ PureApp *app;
+ Event *ev;
+ uint32_t slot;
+ unsigned n;
+ double first; /* the loop's value in the batch's first round */
+ bool reverse; /* lane l runs round n - 1 - l (else round l) */
+ int backward; /* the list accesses whose rows go down from lane to lane, less those going up */
+ bool failed;
+ Val stack[PURE_MODULE_STACK];
+ unsigned sp;
+ uint64_t sets[LOCALS / 64]; /* the locals the block sets */
+ uint8_t state[LOCALS]; /* each this pass: 0 not set yet, 1 set in every lane, 2 in those of written */
+ Mask *written[LOCALS];
+ Val local[LOCALS];
+ Mask *active; /* the lanes running here (NULL: every lane) */
+ Mask mask[MASKS];
+ bool none; /* no lane runs here */
+ Split splits[SPLITS];
+ unsigned split_count, buffers, masks, read_count, store_count, spare_count;
+ void *spare[BUFFERS]; /* lanes no value holds any more */
+ Read reads[READS];
+ Store stores[STORES];
+} Batch;
+
+static _Thread_local Batch batch;
+static _Thread_local double buffer[BUFFERS][BATCH + 24]; /* not 2^k apart: lanes of different buffers in different sets of the cache */
+static const uint32_t no_lanes[BATCH]; /* a mask's when there were no lanes left to make it (the batch failed) */
+
+/* ---- Values */
+
+static Val uniform(double value, uint16_t owner) { return (Val){.kind = UNIFORM, .value = value, .owner = owner}; }
+
+/* Whole, within 2^52 and not -0: what an affine value's parts are (each lane's value then exact, and as the rounds compute it). */
+static bool whole(double x) { return x == floor(x) && fabs(x) <= 0x1p52 && !(x == 0 && signbit(x)); }
+static bool whole32(double x) { return x >= 0 && x < 4294967296.0 && x == floor(x) && !(x == 0 && signbit(x)); }
+
+static bool affine_of(Batch *b, double value, double step, Val *out) {
+ if (!whole(value) || !whole(step) || !whole(value + step * (b->n - 1))) return false;
+ *out = step ? (Val){.kind = AFFINE, .value = value, .step = step} : uniform(value, 0);
+ return true;
+}
+
+static void *fresh(Batch *b) {
+ if (b->spare_count) return b->spare[--b->spare_count];
+ if (b->buffers == BUFFERS) {
+ b->failed = true;
+ return NULL;
+ }
+ return buffer[b->buffers++];
+}
+
+/* A value the stack held alone, gone: its lanes for others. */
+static void release(Batch *b, const Val *v) {
+ if (v->kind == LANES && v->temp) b->spare[b->spare_count++] = v->lane;
+}
+
+static Mask *new_mask(Batch *b, const uint32_t *lanes, const Mask *parent, unsigned count) {
+ if (b->masks == MASKS) {
+ b->failed = true;
+ return NULL;
+ }
+ Mask *m = &b->mask[b->masks++];
+ *m = (Mask){lanes, parent, NULL, count};
+ return m;
+}
+
+/* A mask's lanes (NULL: every lane). */
+static const uint32_t *mask_lanes(Batch *b, Mask *m) {
+ if (!m || m->lanes) return m ? m->lanes : NULL;
+ const uint32_t *parent = mask_lanes(b, (Mask *)m->parent), *other = mask_lanes(b, m->sibling);
+ uint32_t *out = fresh(b);
+ if (!out) return no_lanes;
+ if (parent) for (unsigned l = 0; l < b->n; ++l) out[l] = parent[l] & (other[l] ^ 1);
+ else for (unsigned l = 0; l < b->n; ++l) out[l] = other[l] ^ 1;
+ return m->lanes = out;
+}
+
+static const uint32_t *running(Batch *b) { return mask_lanes(b, b->active); }
+
+/* Lanes of either (two parts of a split: what it split). */
+static Mask *union_of(Batch *b, Mask *x, Mask *y) {
+ if (!x || !y) return NULL;
+ if (x->sibling == y) return (Mask *)x->parent;
+ const uint32_t *xs = mask_lanes(b, x), *ys = mask_lanes(b, y);
+ uint32_t *out = fresh(b);
+ if (!out) return NULL;
+ unsigned count = 0;
+ for (unsigned l = 0; l < b->n; ++l) out[l] = xs[l] | ys[l], count += out[l];
+ return new_mask(b, out, NULL, count);
+}
+
+static inline double lane_of(const Val *v, unsigned l) {
+ return v->kind == UNIFORM ? v->value : v->kind == AFFINE ? v->value + v->step * l
+ : v->u32 ? ((const uint32_t *)v->lane)[l] : ((const double *)v->lane)[l];
+}
+
+/* v as numbers, one per lane (lanes of its own, or new ones); NULL when no lanes are left. */
+static const double *numbers(Batch *b, const Val *v) {
+ if (v->kind == LANES && !v->u32) return v->lane;
+ double *out = fresh(b);
+ if (out)
+ for (unsigned l = 0; l < b->n; ++l) out[l] = lane_of(v, l);
+ return out;
+}
+
+/* v as whole numbers below 2^32 in four bytes each, or NULL: not all are (or a uniform: its value is). */
+static const uint32_t *words(Batch *b, const Val *v) {
+ if (v->kind == LANES) return v->u32 ? v->lane : NULL;
+ if (v->kind == UNIFORM || !whole32(v->value) || !whole32(v->value + v->step * (b->n - 1))) return NULL;
+ uint32_t *out = fresh(b);
+ if (out)
+ for (unsigned l = 0; l < b->n; ++l) out[l] = (uint32_t)(v->value + v->step * l);
+ return out;
+}
+
+static Val lanes_val(void *lane, bool u32) { return (Val){.kind = LANES, .u32 = u32, .temp = true, .lane = lane}; }
+
+/* Whether a running lane has a bad one (bad: a byte per lane). */
+static bool any_running(Batch *b, const uint8_t *bad) {
+ const uint32_t *run = running(b);
+ uint32_t any = 0;
+ if (!run)
+ for (unsigned l = 0; l < b->n; ++l) any |= bad[l];
+ else
+ for (unsigned l = 0; l < b->n; ++l) any |= bad[l] & run[l];
+ return any != 0;
+}
+
+/* Whether every running lane's number is finite (as the executor checks each result). */
+static bool finite_running(Batch *b, const double *x) {
+ const uint32_t *run = running(b);
+ uint32_t bad = 0;
+ if (!run)
+ for (unsigned l = 0; l < b->n; ++l) bad |= !isfinite(x[l]);
+ else
+ for (unsigned l = 0; l < b->n; ++l) bad |= (uint32_t)!isfinite(x[l]) & run[l];
+ return !bad;
+}
+
+/* ---- Arithmetic */
+
+/* x op y as an affine value: sums and differences of affine and uniform whole numbers, and products by a positive one. */
+static bool affine_op(Batch *b, uint8_t op, Val *x, const Val *y) {
+ if (x->kind == LANES || y->kind == LANES || (x->kind == UNIFORM && !whole(x->value)) || (y->kind == UNIFORM && !whole(y->value)))
+ return false;
+ double xs = x->kind == AFFINE ? x->step : 0, ys = y->kind == AFFINE ? y->step : 0;
+ switch (op) {
+ case PURE_OP_ADD: return affine_of(b, x->value + y->value, xs + ys, x);
+ case PURE_OP_SUB: return affine_of(b, x->value - y->value, xs - ys, x);
+ case PURE_OP_MUL:
+ if (x->kind == UNIFORM && x->value > 0) return affine_of(b, x->value * y->value, x->value * ys, x);
+ if (y->kind == UNIFORM && y->value > 0) return affine_of(b, x->value * y->value, xs * y->value, x);
+ return false;
+ default: return false;
+ }
+}
+
+/* Each form of operands its own loop (a uniform's value, or lanes), over
+ * lanes apart from the result's: the compiler makes vector code of each. */
+#define EACH(type, expr) \
+ do { \
+ if (ux) for (unsigned l = 0; l < n; ++l) { type a = xk, c = ys[l]; out[l] = (expr); } \
+ else if (uy) for (unsigned l = 0; l < n; ++l) { type a = xs[l], c = yk; out[l] = (expr); } \
+ else for (unsigned l = 0; l < n; ++l) { type a = xs[l], c = ys[l]; out[l] = (expr); } \
+ } while (0)
+
+/* x op y over whole numbers below 2^32 in four bytes (xs or the uniform xk, ys or yk): false past them (as numbers then). */
+static bool words_op(uint8_t op, uint32_t *restrict out, const uint32_t *restrict xs, uint32_t xk, bool ux,
+ const uint32_t *restrict ys, uint32_t yk, bool uy, unsigned n) {
+ uint32_t over = 0;
+ switch (op) {
+ case PURE_OP_ADD: /* past 2^32: the sum below an operand */
+ if (ux) for (unsigned l = 0; l < n; ++l) { uint32_t sum = xk + ys[l]; out[l] = sum, over |= sum < xk; }
+ else if (uy) for (unsigned l = 0; l < n; ++l) { uint32_t sum = xs[l] + yk; out[l] = sum, over |= sum < yk; }
+ else for (unsigned l = 0; l < n; ++l) { uint32_t sum = xs[l] + ys[l]; out[l] = sum, over |= sum < xs[l]; }
+ break;
+ case PURE_OP_SUB:
+ EACH(uint32_t, a - c);
+ if (ux) for (unsigned l = 0; l < n; ++l) over |= xk < ys[l];
+ else if (uy) for (unsigned l = 0; l < n; ++l) over |= xs[l] < yk;
+ else for (unsigned l = 0; l < n; ++l) over |= xs[l] < ys[l];
+ break;
+ case PURE_OP_MIN: EACH(uint32_t, a < c ? a : c); break;
+ case PURE_OP_MAX: EACH(uint32_t, a > c ? a : c); break;
+ case PURE_OP_LT: EACH(uint32_t, a < c); break;
+ case PURE_OP_LE: EACH(uint32_t, a <= c); break;
+ case PURE_OP_GT: EACH(uint32_t, a > c); break;
+ case PURE_OP_GE: EACH(uint32_t, a >= c); break;
+ case PURE_OP_EQ: EACH(uint32_t, a == c); break;
+ case PURE_OP_NE: EACH(uint32_t, a != c); break;
+ case PURE_OP_AND: EACH(uint32_t, a != 0 && c != 0); break;
+ default: EACH(uint32_t, a != 0 || c != 0); break;
+ }
+ return !over;
+}
+
+/* x op y as numbers, as the executor computes each; whether a result may be not finite (then checked). */
+static bool numbers_op(uint8_t op, double *restrict out, const double *restrict xs, double xk, bool ux,
+ const double *restrict ys, double yk, bool uy, unsigned n) {
+ switch (op) {
+ case PURE_OP_ADD: EACH(double, a + c); return true;
+ case PURE_OP_SUB: EACH(double, a - c); return true;
+ case PURE_OP_MUL: EACH(double, a * c); return true;
+ case PURE_OP_DIV: EACH(double, a / c); return true; /* by 0: not finite, as the executor's fault */
+ case PURE_OP_MOD:
+ for (unsigned l = 0; l < n; ++l) {
+ double a = ux ? xk : xs[l], c = uy ? yk : ys[l], value = fmod(a, c);
+ if (value != 0 && (value < 0) != (c < 0)) value += c;
+ else if (value == 0) value = copysign(0.0, c);
+ out[l] = value;
+ }
+ return true;
+ case PURE_OP_MIN: EACH(double, minimum(a, c)); return false;
+ case PURE_OP_MAX: EACH(double, maximum(a, c)); return false;
+ case PURE_OP_LT: EACH(double, a < c); return false;
+ case PURE_OP_LE: EACH(double, a <= c); return false;
+ case PURE_OP_GT: EACH(double, a > c); return false;
+ case PURE_OP_GE: EACH(double, a >= c); return false;
+ case PURE_OP_EQ: EACH(double, a == c); return false;
+ case PURE_OP_NE: EACH(double, a != c); return false;
+ case PURE_OP_AND: EACH(double, a != 0 && c != 0); return false;
+ default: EACH(double, a != 0 || c != 0); return false;
+ }
+}
+#undef EACH
+
+static bool word_form(uint8_t op) {
+ switch (op) {
+ case PURE_OP_ADD: case PURE_OP_SUB: case PURE_OP_MIN: case PURE_OP_MAX: case PURE_OP_LT: case PURE_OP_LE:
+ case PURE_OP_GT: case PURE_OP_GE: case PURE_OP_EQ: case PURE_OP_NE: case PURE_OP_AND: case PURE_OP_OR: return true;
+ default: return false;
+ }
+}
+
+/* x op y over whole numbers below 2^32, when both are such: false when one is not, or the result would not be. */
+static bool word_op(Batch *b, uint8_t op, Val *x, const Val *y) {
+ if (!word_form(op) || (x->kind == UNIFORM && !whole32(x->value)) || (y->kind == UNIFORM && !whole32(y->value)) ||
+ (x->kind == LANES && !x->u32) || (y->kind == LANES && !y->u32))
+ return false;
+ unsigned spares = b->spare_count, buffers = b->buffers;
+ bool ux = x->kind == UNIFORM, uy = y->kind == UNIFORM;
+ const uint32_t *xs = ux ? NULL : words(b, x), *ys = uy ? NULL : words(b, y);
+ uint32_t *out = (ux || xs) && (uy || ys) ? fresh(b) : NULL;
+ if (!out || !words_op(op, out, xs, ux ? (uint32_t)x->value : 0, ux, ys, uy ? (uint32_t)y->value : 0, uy, b->n)) {
+ b->spare_count = spares, b->buffers = buffers; /* lanes it took back: past 2^32 or below 0 in some lane, as numbers */
+ b->failed = false;
+ return false;
+ }
+ if (xs && xs != x->lane) b->spare[b->spare_count++] = (void *)xs; /* an affine value's lanes, made for this */
+ if (ys && ys != y->lane) b->spare[b->spare_count++] = (void *)ys;
+ release(b, x), release(b, y);
+ *x = lanes_val(out, true);
+ return true;
+}
+
+/* x op y as numbers. */
+static void number_lanes(Batch *b, uint8_t op, Val *x, const Val *y) {
+ bool ux = x->kind == UNIFORM, uy = y->kind == UNIFORM;
+ const double *xs = ux ? NULL : numbers(b, x), *ys = uy ? NULL : numbers(b, y);
+ double *out = (ux || xs) && (uy || ys) ? fresh(b) : NULL;
+ if (!out) return;
+ if (numbers_op(op, out, xs, x->value, ux, ys, y->value, uy, b->n) && !finite_running(b, out)) b->failed = true;
+ if (xs && xs != x->lane) b->spare[b->spare_count++] = (void *)xs; /* numbers made for this */
+ if (ys && ys != y->lane) b->spare[b->spare_count++] = (void *)ys;
+ release(b, x), release(b, y);
+ *x = lanes_val(out, false);
+}
+
+static void binary(Batch *b, uint8_t op) {
+ Val y = b->stack[--b->sp], *x = &b->stack[b->sp - 1];
+ if (x->kind == UNIFORM && y.kind == UNIFORM) {
+ double value = 0;
+ if (!number_op(op, x->value, y.value, &value)) b->failed = true; /* every running lane faults */
+ *x = uniform(value, 0);
+ return;
+ }
+ if (affine_op(b, op, x, &y) || word_op(b, op, x, &y)) return;
+ number_lanes(b, op, x, &y);
+}
+
+/* NEG, NOT, FLOOR of the top. */
+static void unary(Batch *b, uint8_t op) {
+ Val *x = &b->stack[b->sp - 1];
+ if (x->kind == UNIFORM) {
+ *x = uniform(op == PURE_OP_NEG ? -x->value : op == PURE_OP_NOT ? x->value == 0 : floor(x->value), 0);
+ return;
+ }
+ if (op == PURE_OP_FLOOR && (x->kind == AFFINE || x->u32)) { /* whole already */
+ x->owner = 0;
+ return;
+ }
+ if (op == PURE_OP_NOT && x->u32) {
+ uint32_t *out = fresh(b);
+ if (!out) return;
+ for (unsigned l = 0; l < b->n; ++l) out[l] = ((const uint32_t *)x->lane)[l] == 0;
+ release(b, x);
+ *x = lanes_val(out, true);
+ return;
+ }
+ const double *xs = numbers(b, x);
+ double *out = xs ? fresh(b) : NULL;
+ if (!out) return;
+ if (op == PURE_OP_NEG) for (unsigned l = 0; l < b->n; ++l) out[l] = -xs[l];
+ else if (op == PURE_OP_NOT) for (unsigned l = 0; l < b->n; ++l) out[l] = xs[l] == 0;
+ else for (unsigned l = 0; l < b->n; ++l) out[l] = floor(xs[l]);
+ if (xs != x->lane) b->spare[b->spare_count++] = (void *)xs;
+ release(b, x);
+ *x = lanes_val(out, false);
+}
+
+/* CLAMP and INDEX_MOVE: lane by lane as the executor computes them. */
+static void clamp(Batch *b) {
+ Val high = b->stack[--b->sp], low = b->stack[--b->sp], *x = &b->stack[b->sp - 1];
+ double *out = fresh(b);
+ if (!out) return;
+ uint8_t bad[BATCH];
+ for (unsigned l = 0; l < b->n; ++l) {
+ double lo = lane_of(&low, l), hi = lane_of(&high, l);
+ bad[l] = lo > hi;
+ out[l] = maximum(lo, minimum(lane_of(x, l), hi));
+ }
+ if (any_running(b, bad)) b->failed = true;
+ *x = lanes_val(out, false);
+}
+
+static void index_move(Batch *b) {
+ Val by = b->stack[--b->sp], *x = &b->stack[b->sp - 1];
+ size_t count = pure_list_count(b->app->lists[x->owner]);
+ double last = count ? (double)(count - 1) : 0, *out = fresh(b);
+ if (!out) return;
+ uint8_t bad[BATCH];
+ for (unsigned l = 0; l < b->n; ++l) {
+ double step = lane_of(&by, l);
+ bad[l] = step != floor(step);
+ out[l] = maximum(0, minimum(lane_of(x, l) + step, last));
+ }
+ if (any_running(b, bad)) b->failed = true;
+ uint16_t owner = x->owner;
+ *x = lanes_val(out, false);
+ x->owner = owner;
+}
+
+/* ---- Lists */
+
+/* Rows of positions in [0, count) for every running lane (whole: positions are). */
+static bool rows_in(Batch *b, const Val *rows, size_t count) {
+ if (rows->kind == UNIFORM) return rows->value >= 0 && rows->value < (double)count;
+ if (rows->kind == AFFINE) { /* in range at both ends: in every lane */
+ double end = rows->value + rows->step * (b->n - 1);
+ if (rows->value >= 0 && rows->value < (double)count && end >= 0 && end < (double)count) return true;
+ if (!b->active) return false;
+ }
+ uint8_t bad[BATCH];
+ for (unsigned l = 0; l < b->n; ++l) {
+ double at = lane_of(rows, l);
+ bad[l] = !(at >= 0 && at < (double)count);
+ }
+ return !any_running(b, bad);
+}
+
+/* A row a lane reads: its own, or 0 for a lane that does not run (its row may be any). */
+static inline size_t row_of(const Val *rows, unsigned l, size_t count) {
+ double at = lane_of(rows, l);
+ return at >= 0 && at < (double)count ? (size_t)at : 0;
+}
+
+/* Field of cells at rows (all in range for running lanes) as a value. */
+static Val cells_at(Batch *b, const PureCells *cells, unsigned field, const Val *rows) {
+ uint8_t width = cells->width[field];
+ const void *column = cells->columns[field];
+ if (!width) return *rows; /* a DENSE list's key: its row */
+ unsigned n = b->n;
+ double end = rows->value + rows->step * (n - 1);
+ if (rows->kind == AFFINE && rows->value >= 0 && rows->value < (double)cells->count && end >= 0 && end < (double)cells->count) {
+ /* in range in every lane */
+ ptrdiff_t first = (ptrdiff_t)rows->value, step = (ptrdiff_t)rows->step;
+ b->backward += step < 0 ? 1 : -1;
+ if (width == 8) {
+ double *out = fresh(b);
+ if (!out) return *rows;
+ const double *from = (const double *)column + first;
+ if (step == 1) memcpy(out, from, n * sizeof(*out));
+ else for (unsigned l = 0; l < n; ++l) out[l] = from[(ptrdiff_t)l * step];
+ return lanes_val(out, false);
+ }
+ uint32_t *out = fresh(b);
+ if (!out) return *rows;
+ if (width == 4) {
+ const uint32_t *from = (const uint32_t *)column + first;
+ if (step == 1) memcpy(out, from, n * sizeof(*out));
+ else if (step == -1) for (unsigned l = 0; l < n; ++l) out[l] = from[-(ptrdiff_t)l];
+ else for (unsigned l = 0; l < n; ++l) out[l] = from[(ptrdiff_t)l * step];
+ } else {
+ const uint8_t *from = (const uint8_t *)column + first;
+ if (step == 1) for (unsigned l = 0; l < n; ++l) out[l] = from[l];
+ else if (step == -1) for (unsigned l = 0; l < n; ++l) out[l] = from[-(ptrdiff_t)l];
+ else for (unsigned l = 0; l < n; ++l) out[l] = from[(ptrdiff_t)l * step];
+ }
+ return lanes_val(out, true);
+ }
+ void *out = fresh(b);
+ if (!out) return *rows;
+ for (unsigned l = 0; l < n; ++l) {
+ size_t at = row_of(rows, l, cells->count);
+ if (width == 8) memcpy((double *)out + l, (const double *)column + at, sizeof(double));
+ else ((uint32_t *)out)[l] = width == 4 ? ((const uint32_t *)column)[at] : ((const uint8_t *)column)[at];
+ }
+ return lanes_val(out, width != 8);
+}
+
+/* Whether the block set field of list before here (a read of it then would not see that). */
+static bool stored(const Batch *b, uint32_t list, uint32_t field) {
+ for (unsigned s = 0; s < b->store_count; ++s)
+ if (b->stores[s].list == list && b->stores[s].field == field) return true;
+ return false;
+}
+
+static void read_of(Batch *b, uint32_t list, uint32_t field, bool known, const Val *rows) {
+ if (b->read_count == READS) {
+ b->failed = true;
+ return;
+ }
+ Read *r = &b->reads[b->read_count++];
+ r->list = list, r->field = field, r->known = known, r->rows = *rows;
+ if (rows->kind == LANES) b->reads[b->read_count - 1].rows.temp = false;
+}
+
+/* ITEM_GET: field of the items at the top's positions. */
+static void item_get(Batch *b, uint32_t list, uint32_t field) {
+ Val *x = &b->stack[b->sp - 1];
+ PureList *items = b->app->lists[list];
+ size_t count = pure_list_count(items);
+ if (stored(b, list, field) || !rows_in(b, x, count)) {
+ b->failed = true; /* past the items: the executor's fault */
+ return;
+ }
+ if (x->kind == LANES) x->temp = false; /* the read keeps its rows */
+ read_of(b, list, field, true, x);
+ if (x->kind == UNIFORM) {
+ *x = uniform(pure_list_get(items, (size_t)x->value, field).num, 0);
+ return;
+ }
+ PureCells cells;
+ if (pure_list_cells(items, &cells) && cells.width[field] != 255) {
+ *x = cells_at(b, &cells, field, x);
+ x->owner = 0;
+ return;
+ }
+ double *out = fresh(b); /* a tree, or HASHED: the item at each lane's position */
+ if (!out) return;
+ for (unsigned l = 0; l < b->n; ++l) out[l] = pure_list_get(items, row_of(x, l, count), field).num;
+ *x = lanes_val(out, false);
+}
+
+/* LIST_FIND and LIST_HAS at pc, as the executor finds (a FIND joined to its ITEM_GET: the field too); false: it faulted. */
+static bool find(Batch *b, const PureOp *op, uint32_t pc) {
+ const PureModule *m = b->m;
+ uint32_t list = op->arg, key = m->state_key[list] - 1u, field = 0;
+ PureList *keyed = b->app->lists[list];
+ bool has = op->op == PURE_OP_LIST_HAS, joined = !has && op->plan & PLAN_JOINED, found;
+ if (joined) field = item_field(m->code[pc + 1].arg);
+ if (joined && stored(b, list, field)) return false;
+ Val *x = &b->stack[b->sp - 1];
+ PureCells cells;
+ bool dense = pure_list_cells(keyed, &cells) && cells.width[key] == 0; /* DENSE with every key below its count: a key its row */
+ if (x->kind == UNIFORM) {
+ PureCell cell = {.num = x->value};
+ if (joined) {
+ PureCell value;
+ if (!pure_list_lookup(keyed, key, cell, field, &value)) return false;
+ Val rows = uniform(x->value, 0);
+ read_of(b, list, field, dense, &rows);
+ *x = uniform(value.num, 0);
+ return true;
+ }
+ if (has && pure_list_contains(keyed, cell.num, &found)) {
+ *x = uniform(found, 0);
+ return true;
+ }
+ size_t at = op->plan & PLAN_ROW ? pure_list_find_row(keyed, key, cell, &found) : pure_list_seek(keyed, key, cell, &found);
+ if (has) {
+ *x = uniform(found, 0);
+ return true;
+ }
+ if (!found) return false;
+ *x = uniform((double)at, (uint16_t)list);
+ return true;
+ }
+ if (dense) { /* a key its row, if whole and below the count */
+ if (has) {
+ uint32_t *out = fresh(b);
+ if (!out) return true;
+ for (unsigned l = 0; l < b->n; ++l) {
+ double k = lane_of(x, l);
+ out[l] = k >= 0 && k < (double)cells.count && k == floor(k);
+ }
+ *x = lanes_val(out, true);
+ return true;
+ }
+ if (x->kind == LANES) {
+ uint8_t bad[BATCH];
+ for (unsigned l = 0; l < b->n; ++l) {
+ double k = lane_of(x, l);
+ bad[l] = !(k >= 0 && k < (double)cells.count && k == floor(k));
+ }
+ if (any_running(b, bad)) return false;
+ if (!x->u32) { /* the rows: -0 is the key 0's */
+ double *rows = fresh(b);
+ if (!rows) return true;
+ for (unsigned l = 0; l < b->n; ++l) rows[l] = ((const double *)x->lane)[l] + 0.0;
+ *x = lanes_val(rows, false);
+ }
+ } else if (!rows_in(b, x, cells.count))
+ return false;
+ x->owner = (uint16_t)list;
+ if (joined) {
+ read_of(b, list, field, true, x);
+ *x = cells_at(b, &cells, field, x);
+ x->owner = 0;
+ }
+ return true;
+ }
+ double *out = fresh(b); /* any other: each lane's key found as the executor finds it */
+ const uint32_t *run = running(b);
+ if (!out) return true;
+ uint8_t bad[BATCH];
+ for (unsigned l = 0; l < b->n; ++l) {
+ PureCell cell = {.num = lane_of(x, l)}, value = {0};
+ size_t at = 0;
+ found = false;
+ if (!run || run[l]) {
+ if (joined) found = pure_list_lookup(keyed, key, cell, field, &value);
+ else if (!(has && pure_list_contains(keyed, cell.num, &found)))
+ at = op->plan & PLAN_ROW ? pure_list_find_row(keyed, key, cell, &found) : pure_list_seek(keyed, key, cell, &found);
+ }
+ bad[l] = !has && !found;
+ out[l] = joined ? value.num : has ? found : (double)at;
+ }
+ if (!has && any_running(b, bad)) return false;
+ if (joined) {
+ Val rows = {.kind = UNIFORM};
+ read_of(b, list, field, false, &rows);
+ }
+ *x = lanes_val(out, false);
+ if (!has && !joined) x->owner = (uint16_t)list;
+ return true;
+}
+
+/* ITEM_SET: kept for the end (the value's lanes kept with it). */
+static void item_set(Batch *b, uint32_t list, uint32_t field) {
+ Val value = b->stack[--b->sp], rows = b->stack[--b->sp];
+ if (b->store_count == STORES || (int)field == b->m->state_key[list] - 1) {
+ b->failed = true;
+ return;
+ }
+ if (value.kind == LANES) value.temp = false;
+ if (rows.kind == LANES) rows.temp = false;
+ b->stores[b->store_count++] = (Store){list, field, rows, value, b->active};
+}
+
+/* ---- Locals and branches */
+
+static void local_store(Batch *b, uint32_t arg) {
+ unsigned at = arg & 0xFF;
+ Val v = b->stack[--b->sp];
+ if (at == b->slot) {
+ b->failed = true;
+ return;
+ }
+ if (v.kind == LANES) v.temp = false;
+ if (!b->active) {
+ b->local[at] = v, b->state[at] = 1;
+ return;
+ }
+ if (!b->state[at]) { /* its first set this pass: in the running lanes */
+ b->local[at] = v, b->state[at] = 2, b->written[at] = b->active;
+ return;
+ }
+ const uint32_t *run = running(b);
+ double *out = fresh(b); /* the running lanes' new, the others' as they were */
+ if (!out) return;
+ for (unsigned l = 0; l < b->n; ++l) out[l] = run[l] ? lane_of(&v, l) : lane_of(&b->local[at], l);
+ b->local[at] = lanes_val(out, false);
+ b->local[at].temp = false;
+ if (b->state[at] == 2 && !(b->written[at] = union_of(b, b->written[at], b->active))) b->state[at] = 1;
+}
+
+static void local_load(Batch *b, uint32_t arg) {
+ unsigned at = arg & 0xFF;
+ Val v;
+ if (at == b->slot) {
+ double start = b->reverse ? b->first + (b->n - 1) : b->first, step = b->reverse ? -1 : 1;
+ if (!affine_of(b, start, step, &v)) {
+ double *out = fresh(b);
+ if (!out) return;
+ for (unsigned l = 0; l < b->n; ++l) out[l] = start + step * l;
+ v = lanes_val(out, false);
+ }
+ } else if (!(b->sets[at / 64] >> (at % 64) & 1)) v = uniform(b->ev->locals[at].num, (uint16_t)(arg >> 16));
+ else if (b->state[at] == 1) v = b->local[at];
+ else { /* set this pass in some lanes: every running lane must have (else its value is an earlier round's) */
+ const uint32_t *run = running(b), *set = b->state[at] == 2 ? mask_lanes(b, b->written[at]) : NULL;
+ uint32_t missing = !set || !run;
+ for (unsigned l = 0; !missing && l < b->n; ++l) missing |= run[l] & (set[l] ^ 1);
+ if (missing) {
+ b->failed = true;
+ return;
+ }
+ v = b->local[at];
+ }
+ v.owner = (uint16_t)(arg >> 16);
+ b->stack[b->sp++] = v;
+}
+
+/* Lanes (mask: NULL every lane) sent to pc. */
+static void send(Batch *b, uint32_t pc, Mask *mask) {
+ if (b->split_count == SPLITS) {
+ b->failed = true;
+ return;
+ }
+ b->splits[b->split_count++] = (Split){pc, mask};
+}
+
+/* The lanes sent to pc join those running into it. */
+static void arrive(Batch *b, uint32_t pc) {
+ for (unsigned s = 0; s < b->split_count;) {
+ if (b->splits[s].pc != pc) {
+ ++s;
+ continue;
+ }
+ Mask *mask = b->splits[s].mask;
+ b->splits[s] = b->splits[--b->split_count];
+ if (b->none) b->active = mask, b->none = false;
+ else b->active = union_of(b, b->active, mask);
+ }
+ if (b->active && b->active->count == b->n) b->active = NULL; /* every lane again */
+}
+
+/* JZ to pc: the lanes whose top is 0 go there. */
+static void branch(Batch *b, uint32_t pc) {
+ Val c = b->stack[--b->sp];
+ if (c.kind == UNIFORM) {
+ if (c.value == 0) send(b, pc, b->active), b->none = true;
+ return;
+ }
+ const uint32_t *parent = running(b), *on;
+ if (c.kind == LANES && c.u32 && !parent) on = c.lane; /* a comparison's 1s and 0s: the lanes going on */
+ else {
+ uint32_t *out = fresh(b);
+ if (!out) return;
+ for (unsigned l = 0; l < b->n; ++l) out[l] = (parent ? parent[l] : 1) & (lane_of(&c, l) != 0);
+ release(b, &c);
+ on = out;
+ }
+ unsigned count = 0;
+ for (unsigned l = 0; l < b->n; ++l) count += on[l];
+ Mask *yes = new_mask(b, on, b->active, count), *no = new_mask(b, NULL, b->active, (b->active ? b->active->count : b->n) - count);
+ if (!yes || !no) return;
+ yes->sibling = no, no->sibling = yes;
+ if (no->count) send(b, pc, no);
+ if (count) b->active = yes;
+ else b->none = true;
+}
+
+/* ---- The pass */
+
+/* The block from start to end once for the batch's lanes: false where it failed. */
+static bool pass(Batch *b, uint32_t start, uint32_t end) {
+ const PureModule *m = b->m;
+ Event *ev = b->ev;
+ PureApp *app = b->app;
+ for (uint32_t pc = start; pc < end && !b->failed;) {
+ arrive(b, pc);
+ if (b->none) { /* no lane here: on to where one goes */
+ uint32_t next = end;
+ for (unsigned s = 0; s < b->split_count; ++s)
+ if (b->splits[s].pc < next) next = b->splits[s].pc;
+ pc = next;
+ continue;
+ }
+ const PureOp *op = &m->code[pc];
+ uint32_t arg = op->arg;
+ ++pc;
+ switch (op->op) {
+ case PURE_OP_CONST: b->stack[b->sp++] = uniform(op->value, 0); break;
+ case PURE_OP_LOAD: b->stack[b->sp++] = uniform(b->frame->values[arg].num, 0); break;
+ case PURE_OP_FIELD: {
+ const PureField *field = &m->field[ev->shape->field_start + arg];
+ const unsigned char *given = (ev->arguments ? app->arguments.data : app->payload.data) + field->offset;
+ b->stack[b->sp++] = uniform(field->type == PURE_FIELD_U32 ? read32(given) : field->type == PURE_FIELD_BOOL ? given[0]
+ : read_double(given), 0);
+ break;
+ }
+ case PURE_OP_INDEX_LOAD: b->stack[b->sp++] = uniform(b->frame->values[arg].num, m->state_ref[arg]); break;
+ case PURE_OP_ROW: b->stack[b->sp++] = uniform((double)ev->row, (uint16_t)arg); break;
+ case PURE_OP_OUTER_ROW: b->stack[b->sp++] = uniform((double)ev->outer, (uint16_t)arg); break;
+ case PURE_OP_LIST_COUNT: b->stack[b->sp++] = uniform((double)pure_list_count(app->lists[arg]), 0); break;
+ case PURE_OP_INDEX_FIRST: case PURE_OP_INDEX_LAST: {
+ size_t count = op->op == PURE_OP_INDEX_LAST ? pure_list_count(app->lists[arg]) : 0;
+ b->stack[b->sp++] = uniform(count ? (double)(count - 1) : 0, (uint16_t)arg);
+ break;
+ }
+ case PURE_OP_INDEX_NUM: break;
+ case PURE_OP_PICK: {
+ Val *v = &b->stack[b->sp - 1 - arg];
+ v->temp = false;
+ b->stack[b->sp++] = *v;
+ break;
+ }
+ case PURE_OP_SLIDE:
+ for (unsigned d = b->sp - 1 - arg; d + 1 < b->sp; ++d) release(b, &b->stack[d]);
+ b->stack[b->sp - 1 - arg] = b->stack[b->sp - 1], b->sp -= arg;
+ break;
+ case PURE_OP_LOCAL_LOAD: local_load(b, arg); break;
+ case PURE_OP_LOCAL_STORE: local_store(b, arg); break;
+ case PURE_OP_NEG: case PURE_OP_NOT: case PURE_OP_FLOOR: unary(b, op->op); break;
+ case PURE_OP_CLAMP: clamp(b); break;
+ case PURE_OP_INDEX_MOVE: index_move(b); break;
+ case PURE_OP_ITEM_GET: item_get(b, list_of(arg), item_field(arg)); break;
+ case PURE_OP_ITEM_SET: item_set(b, list_of(arg), item_field(arg)); break;
+ case PURE_OP_LIST_FIND: case PURE_OP_LIST_HAS:
+ if (!find(b, op, pc - 1)) b->failed = true;
+ else if (op->op == PURE_OP_LIST_FIND && op->plan & PLAN_JOINED) ++pc; /* its ITEM_GET with it */
+ break;
+ case PURE_OP_JZ: branch(b, arg); break;
+ case PURE_OP_JMP: send(b, arg, b->active), b->none = true; break;
+ case PURE_OP_ADD: case PURE_OP_SUB: case PURE_OP_MUL: case PURE_OP_DIV: case PURE_OP_MOD: case PURE_OP_MIN:
+ case PURE_OP_MAX: case PURE_OP_LT: case PURE_OP_LE: case PURE_OP_GT: case PURE_OP_GE: case PURE_OP_EQ:
+ case PURE_OP_NE: case PURE_OP_AND: case PURE_OP_OR: binary(b, op->op); break;
+ default: b->failed = true; /* no batch form (the load plans none such) */
+ }
+ }
+ return !b->failed;
+}
+
+/* ---- The end: the sets, if no read of the batch would have seen one */
+
+/* A lane's round in the batch. */
+static inline unsigned round_of(const Batch *b, unsigned l) { return b->reverse ? b->n - 1 - l : l; }
+
+/* Whether a store at rows (in the lanes of mask: NULL all) sets in a round the row a later round's read reads. */
+static bool reads_set(const Batch *b, const Read *r, const Store *s, const uint32_t *mask) {
+ if (!r->known) return true;
+ unsigned n = b->n;
+ if (r->rows.kind == UNIFORM) { /* read once, before any set: set in a round before the last */
+ for (unsigned l = 0; l < n; ++l)
+ if (round_of(b, l) + 1 < n && (!mask || mask[l]) && lane_of(&s->rows, l) == r->rows.value) return true;
+ return false;
+ }
+ if (s->rows.kind == UNIFORM) { /* one row: read in a round after the first to set it */
+ unsigned first = n;
+ for (unsigned l = 0; l < n; ++l)
+ if ((!mask || mask[l]) && round_of(b, l) < first) first = round_of(b, l);
+ for (unsigned l = 0; l < n; ++l)
+ if (round_of(b, l) > first && lane_of(&r->rows, l) == s->rows.value) return true;
+ return false;
+ }
+ if (r->rows.kind == AFFINE && s->rows.kind == AFFINE && r->rows.step == s->rows.step) { /* lane l reads what lane l + d sets */
+ double d = (r->rows.value - s->rows.value) / s->rows.step;
+ return d == floor(d) && fabs(d) < n && (b->reverse ? d > 0 : d < 0);
+ }
+ if (r->rows.kind == AFFINE && s->rows.kind == AFFINE) { /* lane l reads what lane (r0 - s0 + rs l) / ss sets */
+ for (unsigned l = 0; l < n; ++l) {
+ double w = (r->rows.value + r->rows.step * l - s->rows.value) / s->rows.step;
+ if (w >= 0 && w < n && w == floor(w) && round_of(b, (unsigned)w) < round_of(b, l) && (!mask || mask[(unsigned)w]))
+ return true;
+ }
+ return false;
+ }
+ return true; /* lanes of rows: not looked into yet */
+}
+
+/* Whether two stores of the same cells (a before b in the block, each in the
+ * lanes of its mask) set a row in rounds the other way round: b's in an
+ * earlier round than a's (the rounds leave a's, the batch b's). */
+static bool sets_cross(const Batch *b, const Store *x, const uint32_t *xm, const Store *y, const uint32_t *ym) {
+ unsigned n = b->n;
+ if (x->rows.kind == AFFINE && y->rows.kind == AFFINE && x->rows.step == y->rows.step) { /* y's lane l sets x's lane l + d's row */
+ double d = (y->rows.value - x->rows.value) / x->rows.step;
+ return d == floor(d) && fabs(d) < n && (b->reverse ? d < 0 : d > 0);
+ }
+ if (x->rows.kind == LANES || y->rows.kind == LANES) return true; /* not looked into yet */
+ unsigned last = 0; /* the last round x sets its row in (x uniform) */
+ for (unsigned k = 0; x->rows.kind == UNIFORM && k < n; ++k)
+ if ((!xm || xm[k]) && round_of(b, k) > last) last = round_of(b, k);
+ for (unsigned l = 0; l < n; ++l) { /* y's row in each of its lanes: set by x in a later round? */
+ if (ym && !ym[l]) continue;
+ double row = lane_of(&y->rows, l);
+ if (x->rows.kind == UNIFORM) {
+ if (row == x->rows.value && last > round_of(b, l)) return true;
+ continue;
+ }
+ double k = (row - x->rows.value) / x->rows.step;
+ if (k >= 0 && k < n && k == floor(k) && (!xm || xm[(unsigned)k]) && round_of(b, (unsigned)k) > round_of(b, l)) return true;
+ }
+ return false;
+}
+
+/* Lanes' values set at rows to + step × lane, those of mask (NULL: all). */
+static void put_words(uint32_t *to, ptrdiff_t step, const uint32_t *from, const uint32_t *mask, unsigned n) {
+ if (!mask && step == 1) memcpy(to, from, n * sizeof(*to));
+ else if (!mask && step == -1) for (unsigned l = 0; l < n; ++l) to[-(ptrdiff_t)l] = from[l];
+ else if (!mask) for (unsigned l = 0; l < n; ++l) to[(ptrdiff_t)l * step] = from[l];
+ else if (step == 1) for (unsigned l = 0; l < n; ++l) to[l] = mask[l] ? from[l] : to[l];
+ else if (step == -1) for (unsigned l = 0; l < n; ++l) to[-(ptrdiff_t)l] = mask[l] ? from[l] : to[-(ptrdiff_t)l];
+ else for (unsigned l = 0; l < n; ++l) if (mask[l]) to[(ptrdiff_t)l * step] = from[l];
+}
+
+static void put_numbers(double *to, ptrdiff_t step, const double *from, const uint32_t *mask, unsigned n) {
+ if (!mask && step == 1) memcpy(to, from, n * sizeof(*to));
+ else for (unsigned l = 0; l < n; ++l) if (!mask || mask[l]) to[(ptrdiff_t)l * step] = from[l];
+}
+
+/* Whether a number goes into a column of width bytes as it is (else: the width it needs). */
+static uint8_t width_needed(double v) {
+ if (!(v >= 0 && v == floor(v)) || (v == 0 && signbit(v))) return 8;
+ return v < 256 ? 1 : v < 4294967296.0 ? 4 : 8;
+}
+
+static bool settle(Batch *b) {
+ PureCells cells[STORES];
+ const uint32_t *mask[STORES];
+ for (unsigned i = 0; i < b->store_count; ++i) {
+ Store *s = &b->stores[i];
+ PureList *list = b->app->lists[s->list];
+ if (!pure_list_cells(list, &cells[i]) || !cells[i].owned || cells[i].width[s->field] == 255 || cells[i].width[s->field] == 0)
+ return false;
+ Mask *saved = b->active;
+ b->active = s->mask;
+ bool in = rows_in(b, &s->rows, cells[i].count);
+ b->active = saved;
+ mask[i] = mask_lanes(b, s->mask);
+ if (!in || b->failed) return false;
+ for (unsigned r = 0; r < b->read_count; ++r)
+ if (b->reads[r].list == s->list && b->reads[r].field == s->field && reads_set(b, &b->reads[r], s, mask[i])) return false;
+ for (unsigned j = 0; j < i; ++j)
+ if (b->stores[j].list == s->list && b->stores[j].field == s->field && sets_cross(b, &b->stores[j], mask[j], s, mask[i]))
+ return false;
+ }
+ for (unsigned i = 0; i < b->store_count; ++i) { /* columns wide enough: wider changes no item */
+ Store *s = &b->stores[i];
+ uint8_t need = 1, width = cells[i].width[s->field];
+ if (width == 8 || (s->value.u32 && width == 4)) continue;
+ for (unsigned l = 0; l < b->n && need < 8; ++l)
+ if (!mask[i] || mask[i][l]) {
+ uint8_t lane = width_needed(lane_of(&s->value, l));
+ need = lane > need ? lane : need;
+ }
+ if (need > width) {
+ if (!pure_list_widen(b->app->lists[s->list], s->field, need)) return false;
+ for (unsigned j = 0; j < b->store_count; ++j) /* its columns as they are now */
+ if (b->stores[j].list == s->list) pure_list_cells(b->app->lists[s->list], &cells[j]);
+ }
+ }
+ for (unsigned i = 0; i < b->store_count; ++i) { /* each lane's, in the rounds' order */
+ Store *s = &b->stores[i];
+ void *column = cells[i].columns[s->field];
+ uint8_t width = cells[i].width[s->field];
+ pure_list_touched(b->app->lists[s->list]);
+ if (s->rows.kind == AFFINE && s->value.kind == LANES && (width == 8 ? !s->value.u32 : s->value.u32 && width == 4)) {
+ ptrdiff_t first = (ptrdiff_t)s->rows.value, step = (ptrdiff_t)s->rows.step; /* distinct rows: set each as its lane runs */
+ b->backward += step < 0 ? 1 : -1;
+ if (width == 4) put_words((uint32_t *)column + first, step, s->value.lane, mask[i], b->n);
+ else put_numbers((double *)column + first, step, s->value.lane, mask[i], b->n);
+ continue;
+ }
+ for (unsigned r = 0; r < b->n; ++r) {
+ unsigned l = round_of(b, r);
+ if (mask[i] && !mask[i][l]) continue;
+ size_t at = (size_t)lane_of(&s->rows, l);
+ double v = lane_of(&s->value, l);
+ if (width == 8) memcpy((double *)column + at, &v, sizeof(v));
+ else if (width == 4) ((uint32_t *)column)[at] = (uint32_t)v;
+ else ((uint8_t *)column)[at] = (uint8_t)v;
+ }
+ }
+ return true;
+}
+
+unsigned pure_batch_run(Frame *frame, Loop *loop) {
+ PureApp *app = frame->app;
+ const PureModule *m = frame->m;
+ uint64_t per = (uint64_t)(loop->end - loop->start) + 1, left = loop->count - loop->k;
+ uint64_t budget = app->work_budget ? app->work_budget : PURE_WORK_DEFAULT, paid = 1 + (budget - app->work) / per;
+ if (left < LEAST || loop->integer) {
+ loop->resume = UINT64_MAX;
+ return 0;
+ }
+ unsigned n = (unsigned)(left < BATCH ? left : BATCH);
+ if (paid < n) n = (unsigned)paid;
+ double first = loop->slot->num;
+ if (n < 2 || (first == 0 && signbit(first))) { /* the work left pays for one round, or the loop counts from -0: one round by the executor */
+ loop->resume = loop->k + 1;
+ return 0;
+ }
+ Batch *b = &batch;
+ b->frame = frame, b->m = m, b->app = app, b->ev = frame->ev, b->n = n, b->first = first;
+ b->reverse = loop->reverse, b->backward = 0;
+ b->slot = (uint32_t)(loop->slot - frame->ev->locals);
+ b->failed = b->none = false, b->active = NULL;
+ b->sp = b->split_count = b->buffers = b->masks = b->read_count = b->store_count = b->spare_count = 0;
+ memset(b->sets, 0, sizeof(b->sets));
+ for (uint32_t pc = loop->start; pc < loop->end; ++pc)
+ if (m->code[pc].op == PURE_OP_LOCAL_STORE) {
+ unsigned at = m->code[pc].arg & 0xFF;
+ b->sets[at / 64] |= UINT64_C(1) << (at % 64);
+ b->state[at] = 0;
+ }
+ if (pass(b, loop->start, loop->end)) {
+ arrive(b, loop->end);
+ for (unsigned w = 0; w < LOCALS / 64; ++w) /* the lanes each local was set in, made before anything changes */
+ for (uint64_t bits = b->sets[w]; bits; bits &= bits - 1) {
+ unsigned at = w * 64 + (unsigned)__builtin_ctzll(bits);
+ if (b->state[at] == 2) mask_lanes(b, b->written[at]);
+ }
+ }
+ if (b->failed || !settle(b)) {
+ loop->resume = ++loop->failures >= FAILURES ? UINT64_MAX : loop->k + n; /* its rounds one by one, then batches again */
+ return 0;
+ }
+ app->work += (n - 1) * per;
+ for (unsigned w = 0; w < LOCALS / 64; ++w) /* each local the block set: as the last round to set it left it */
+ for (uint64_t bits = b->sets[w]; bits; bits &= bits - 1) {
+ unsigned at = w * 64 + (unsigned)__builtin_ctzll(bits), last = n - 1;
+ if (!b->state[at]) continue;
+ const uint32_t *set = b->state[at] == 2 ? mask_lanes(b, b->written[at]) : NULL;
+ while (set && last && !set[round_of(b, last)]) --last;
+ if (!set || set[round_of(b, last)]) frame->ev->locals[at].num = lane_of(&b->local[at], round_of(b, last));
+ }
+ loop->slot->num = first + (double)(n - 1);
+ if (b->backward > 0) loop->reverse = !loop->reverse; /* rows going down from lane to lane: the next batch's lanes the other way */
+ return n;
+}
diff --git a/core/module-list.c b/core/module-list.c
index 442dc80..6da4a43 100644
--- a/core/module-list.c
+++ b/core/module-list.c
@@ -1798,6 +1798,24 @@ bool pure_list_arrays(PureList *list) {
unsigned pure_list_form(const PureList *list) { return list->form; }
+bool pure_list_cells(PureList *list, PureCells *out) {
+ if (list->form != FLAT && !(list->form == DENSE && pure_list_full(list))) return false;
+ const Layout *l = &list->layout;
+ out->count = list->count;
+ out->owned = list->arrays && !list->pack && !list->copy;
+ for (unsigned f = 0; f < l->fields; ++f) {
+ out->columns[f] = list->columns[f];
+ out->width[f] = list->width[f] == 0 || ((l->kinds[f] == PURE_CELL_NUMBER || l->kinds[f] == PURE_CELL_BOOL) &&
+ (list->width[f] == 1 || list->width[f] == 4 || list->width[f] == 8))
+ ? list->width[f] : 255;
+ }
+ return true;
+}
+
+bool pure_list_widen(PureList *list, unsigned field, uint8_t bytes) { return widen(list, field, bytes); }
+
+void pure_list_touched(PureList *list) { ++list->version; }
+
bool pure_list_settle(PureList *list) {
if (list->pack || list->copy || list->arrays || list->form != TREE || list->layout.key < 0 || list->count < PACK_ITEMS ||
list->searched_version != list->version || list->searched < list->count / PACK_SEARCHES)
diff --git a/core/module-list.h b/core/module-list.h
index 369e8ed..28c1936 100644
--- a/core/module-list.h
+++ b/core/module-list.h
@@ -173,6 +173,19 @@ size_t pure_list_extra(const PureList *);
* gets allow; a clear makes it FLAT again. Answers are the tree's. False
* when the list cannot (it stays a tree). */
bool pure_list_arrays(PureList *);
+/* A list's cells as a batch reads and sets them (docs/design/024): FLAT (a
+ * position its row) or DENSE with every key below its count (a key its
+ * position and its row); each field's column and its cells' bytes (0: a
+ * DENSE list's key, the row itself; 1 or 4: whole numbers; 8: numbers; 255:
+ * neither, a text or an i64); owned when a batch may set them in place (an
+ * event's list, not a pack's). false when it is neither form. */
+typedef struct { size_t count; void *columns[16]; uint8_t width[16]; bool owned; } PureCells;
+bool pure_list_cells(PureList *, PureCells *);
+/* Field's column of an owned list's cells widened to bytes (wider than it
+ * is) before a batch sets cells that need it; false without memory (as it was). */
+bool pure_list_widen(PureList *, unsigned field, uint8_t bytes);
+/* A batch set cells of it in place: it changed (its version). */
+void pure_list_touched(PureList *);
/* What it keeps its items in now: 0 a tree, 1 FLAT arrays, 2 DENSE (for tests and counts). */
unsigned pure_list_form(const PureList *);
/* Field of the item whose key_field is key, in a list ordered by key_field
diff --git a/core/module-run.h b/core/module-run.h
index fac77a4..1e48072 100644
--- a/core/module-run.h
+++ b/core/module-run.h
@@ -4,9 +4,59 @@
* (module-jit.c): their frame, and the steps the compiled code calls. Not a
* public interface. */
#include "module.h"
+#include <math.h>
+#include <string.h>
-/* An item's or a key's op->plan: its cell a text; a FIND joined to the ITEM_GET after it. */
-enum { PLAN_TEXT = 1, PLAN_JOINED = 2, PLAN_ROW = 4 };
+/* Read from a message's bytes (little-endian). */
+static inline uint32_t read32(const unsigned char *p) {
+ return (uint32_t)p[0] | (uint32_t)p[1] << 8 | (uint32_t)p[2] << 16 | (uint32_t)p[3] << 24;
+}
+
+static inline double read_double(const unsigned char *p) {
+ uint64_t bits = read32(p) | (uint64_t)read32(p + 4) << 32;
+ double value;
+ memcpy(&value, &bits, sizeof(value));
+ return value;
+}
+
+static inline double minimum(double a, double b) { return a < b || (a == b && signbit(a)) ? a : b; }
+static inline double maximum(double a, double b) { return a > b || (a == b && !signbit(a)) ? a : b; }
+
+/* a op b as run computes it; false where run faults. */
+static inline bool number_op(uint8_t op, double a, double b, double *out) {
+ double value;
+ switch (op) {
+ case PURE_OP_ADD: value = a + b; break;
+ case PURE_OP_SUB: value = a - b; break;
+ case PURE_OP_MUL: value = a * b; break;
+ case PURE_OP_DIV:
+ if (b == 0) return false;
+ value = a / b;
+ break;
+ case PURE_OP_LT: value = a < b; break;
+ case PURE_OP_LE: value = a <= b; break;
+ case PURE_OP_GT: value = a > b; break;
+ case PURE_OP_GE: value = a >= b; break;
+ case PURE_OP_EQ: value = a == b; break;
+ case PURE_OP_NE: value = a != b; break;
+ case PURE_OP_AND: value = a != 0 && b != 0; break;
+ case PURE_OP_OR: value = a != 0 || b != 0; break;
+ case PURE_OP_MIN: value = minimum(a, b); break;
+ case PURE_OP_MOD:
+ if (b == 0) return false;
+ value = fmod(a, b);
+ if (value != 0 && (value < 0) != (b < 0)) value += b;
+ else if (value == 0) value = copysign(0.0, b);
+ break;
+ default: value = maximum(a, b); break;
+ }
+ *out = value;
+ return isfinite(value);
+}
+
+/* An item's or a key's op->plan: its cell a text; a FIND joined to the ITEM_GET after it; a FIND whose row an ITEM_SET
+ * takes; a LOOP whose block a batch may run (module-batch.c). */
+enum { PLAN_TEXT = 1, PLAN_JOINED = 2, PLAN_ROW = 4, PLAN_BATCH = 8 };
/* An item instruction's argument: its list and its field. */
static inline uint32_t list_of(uint32_t arg) { return arg & 0xFFFF; }
@@ -20,7 +70,8 @@ typedef struct { uint32_t list; size_t at, end; bool removed; } Walk;
/* A loop that runs in its block's run (LOOP, EACH): its block and where
* the code around it ends, the arena as it began, a walk's walk and the
* event's walk and row around it, a count's values (low + k of count) and
- * slot. */
+ * slot, and the round from which batches may run its rounds (UINT64_MAX:
+ * none), how many failed and which way their lanes run. */
typedef struct {
uint32_t start, end, outer;
size_t mark;
@@ -29,6 +80,9 @@ typedef struct {
size_t row;
uint64_t count, k;
PureValue low, *slot;
+ uint64_t resume;
+ unsigned failures;
+ bool reverse; /* a batch's lanes run its rounds backwards */
} Loop;
typedef struct {
PureApp *app;
@@ -83,8 +137,9 @@ static inline uint32_t after(const PureOp *op, uint32_t pc) {
* instruction but a branch or a loop's (how; the next is after()); a walk or
* a loop opened at pc (STEP_NEXT: its block next, STEP_SKIP: none, past its
* block); BREAK; a loop's block ran once (STEP_NEXT: again, STEP_DONE: the
- * loop ended). */
-enum { STEP_SKIP = 4, STEP_DONE = 5 };
+ * loop ended). STEP_BATCH: step leaves a LOOP planned PLAN_BATCH to its
+ * caller (module.c). */
+enum { STEP_SKIP = 4, STEP_DONE = 5, STEP_BATCH = 6 };
int pure_run_step(Frame *, uint32_t pc);
int pure_run_each(Frame *, uint32_t pc);
int pure_run_loop(Frame *, uint32_t pc);
@@ -101,6 +156,13 @@ int pure_run_item(Frame *, uint32_t pc);
* stopped. */
int pure_run_rest(Frame *, uint32_t pc);
+/* Loops a batch of rounds at a time (module-batch.c, docs/design/024): the
+ * innermost loop's rounds from loop->k (set up and counted; its LOOP
+ * planned PLAN_BATCH) run as one batch: how many (0: none ran, its block
+ * runs round by round next, at least until round loop->resume), the frame
+ * left as the last of them leaves it, their work counted. */
+unsigned pure_batch_run(Frame *, Loop *);
+
/* Where a list keeps what compiled code reads of it (module-list.c owns the
* layout and says where): its item count, its key set (the words, how many,
* whether they are bits), its form (pure_list_form), its arrays and the rows
diff --git a/core/module.c b/core/module.c
index 2228725..c6eb9be 100644
--- a/core/module.c
+++ b/core/module.c
@@ -142,20 +142,11 @@ static const struct { unsigned char pops, in[3], out; unsigned short where; unsi
static uint32_t read16(const unsigned char *p) { return (uint32_t)p[0] | (uint32_t)p[1] << 8; }
-static uint32_t read32(const unsigned char *p) {
- return (uint32_t)p[0] | (uint32_t)p[1] << 8 | (uint32_t)p[2] << 16 | (uint32_t)p[3] << 24;
-}
static void write32(unsigned char *p, uint32_t value) {
for (unsigned i = 0; i < 4; ++i) p[i] = (unsigned char)(value >> (8 * i));
}
-static double read_double(const unsigned char *p) {
- uint64_t bits = read32(p) | (uint64_t)read32(p + 4) << 32;
- double value;
- memcpy(&value, &bits, sizeof(value));
- return value;
-}
static void write_double(unsigned char *p, double value) {
uint64_t bits;
@@ -695,11 +686,59 @@ PURE_COLD static bool block_has_lanes(const PureModule *m, PureBlock block, int
return true;
}
+/* A count's loop whose block has batch forms throughout runs a batch of its
+ * rounds at a time (module-batch.c, docs/design/024): lane forms, a local
+ * set (a number, an index or a bool) and read only after every round sets
+ * it, a branch with nothing else on the stack to a place in the block, and
+ * a number or bool set in an item (not its key). PURE_BATCH=0 in the
+ * environment: none does (the executor alone, to measure it). */
+PURE_COLD static bool loop_batches(const PureModule *m, uint32_t pc, int input) {
+ static int off = -1;
+ if (off < 0) {
+ const char *batches = getenv("PURE_BATCH");
+ off = batches && !strcmp(batches, "0");
+ }
+ const PureOp *loop = &m->code[pc];
+ uint32_t start = pc + 1, end = start + (loop->arg >> 16), arms = start;
+ if (off || loop->arg & PURE_LOOP_INTEGER || start >= end || m->height[start]) return false;
+ uint64_t set[4] = {0}, sure[4] = {0}; /* the locals the block sets; set before here in every round */
+ for (uint32_t at = start; at < end; ++at)
+ if (m->code[at].op == PURE_OP_LOCAL_STORE) set[(m->code[at].arg & 0xFF) / 64] |= UINT64_C(1) << (m->code[at].arg & 63);
+ for (uint32_t at = start; at < end; ++at) { /* a local read before a round sets it: an earlier round's (no batch has it) */
+ const PureOp *op = &m->code[at];
+ unsigned local = op->arg & 0xFF;
+ if ((op->op == PURE_OP_JZ || op->op == PURE_OP_JMP) && op->arg > arms) arms = op->arg; /* code before arms: in a branch's way */
+ if (op->op == PURE_OP_LOCAL_STORE && at >= arms) sure[local / 64] |= UINT64_C(1) << (local % 64);
+ if (op->op == PURE_OP_LOCAL_LOAD && (set[local / 64] & ~sure[local / 64]) >> (local % 64) & 1) return false;
+ }
+ for (uint32_t at = start; at < end; ++at) {
+ const PureOp *op = &m->code[at];
+ switch (op->op) {
+ case PURE_OP_LOCAL_STORE:
+ if (local_type(op->arg) == T_I64) return false;
+ break;
+ case PURE_OP_JZ: case PURE_OP_JMP:
+ if (op->arg > end || m->height[at] != (op->op == PURE_OP_JZ)) return false;
+ break;
+ case PURE_OP_ITEM_SET: {
+ unsigned char type = field_type(m, list_of(op->arg), item_field(op->arg));
+ if ((type != T_NUM && type != T_BOOL) || item_field(op->arg) == m->state_key[list_of(op->arg)] - 1u) return false;
+ break;
+ }
+ default:
+ if (!has_lanes(m, op, input)) return false;
+ }
+ }
+ return true;
+}
+
/* A fold in a verified block whose own block has lane forms throughout runs
- * a leaf of its list at a time. */
+ * a leaf of its list at a time; a count's loop so planned, a batch of its
+ * rounds. */
PURE_COLD static void plan_folds(PureModule *m, PureBlock block, int input) {
for (uint32_t pc = block.start; pc < block.start + block.length; ++pc) {
PureOp *op = &m->code[pc];
+ if (op->op == PURE_OP_LOOP && (op->plan = loop_batches(m, pc, input) ? PLAN_BATCH : 0)) m->batches = true;
if (op->op != PURE_OP_FOLD) continue;
op->plan = !(op->arg & PURE_FOLD_INTEGER) && block_has_lanes(m, (PureBlock){pc + 1, op->arg >> 16}, input);
pc += op->arg >> 16;
@@ -1018,6 +1057,7 @@ PURE_COLD PureResult pure_module_read(const char *path, PureModule *out, char *e
void pure_module_release(PureModule *m) {
pure_jit_free(m->jit);
m->jit = NULL;
+ m->batches = false;
free(m->height);
m->height = NULL;
free(m->storage);
@@ -1546,8 +1586,6 @@ int pure_module_column(const PureModule *m, uint32_t table, const char *name) {
/* ---- Execution ------------------------------------------------------ */
/* IEEE 754-2019 minimum/maximum on finite values: -0 orders below +0. */
-static double minimum(double a, double b) { return a < b || (a == b && signbit(a)) ? a : b; }
-static double maximum(double a, double b) { return a > b || (a == b && !signbit(a)) ? a : b; }
/* Whether two values that order as order (below zero: the first below) are related as a relation says (PureRelation). */
@@ -1813,37 +1851,6 @@ static const double *lanes_of(const Lanes *v, double *scratch, const PureRun *it
return scratch;
}
-/* a op b as run computes it; false where run faults. */
-static bool number_op(uint8_t op, double a, double b, double *out) {
- double value;
- switch (op) {
- case PURE_OP_ADD: value = a + b; break;
- case PURE_OP_SUB: value = a - b; break;
- case PURE_OP_MUL: value = a * b; break;
- case PURE_OP_DIV:
- if (b == 0) return false;
- value = a / b;
- break;
- case PURE_OP_LT: value = a < b; break;
- case PURE_OP_LE: value = a <= b; break;
- case PURE_OP_GT: value = a > b; break;
- case PURE_OP_GE: value = a >= b; break;
- case PURE_OP_EQ: value = a == b; break;
- case PURE_OP_NE: value = a != b; break;
- case PURE_OP_AND: value = a != 0 && b != 0; break;
- case PURE_OP_OR: value = a != 0 || b != 0; break;
- case PURE_OP_MIN: value = minimum(a, b); break;
- case PURE_OP_MOD:
- if (b == 0) return false;
- value = fmod(a, b);
- if (value != 0 && (value < 0) != (b < 0)) value += b;
- else if (value == 0) value = copysign(0.0, b);
- break;
- default: value = maximum(a, b); break;
- }
- *out = value;
- return isfinite(value);
-}
/* a op b for every item into out: a loop per operation, reading a value for
* all with stride 0. false where run faults for some item. */
@@ -2586,13 +2593,69 @@ static inline __attribute__((always_inline)) int iterate(Frame *frame, uint32_t
return STEP_NEXT;
}
+/* A loop planned PLAN_BATCH from its round loop->k (set up and counted)
+ * on: batches while they run (module-batch.c), the rounds of one that failed
+ * one by one, then batches again, until the loop ends or batches stop
+ * (then *next its block: the rest of it as any loop's). STEP_NEXT with *next
+ * past its block when it ended here, or how a round stopped. */
+static __attribute__((noinline, cold)) int batches(Frame *frame, Loop *loop, uint32_t *next) {
+ unsigned depth = frame->depth;
+ for (;;) {
+ unsigned done = pure_batch_run(frame, loop);
+ if (done) {
+ if ((loop->k += done) >= loop->count) { /* it ended */
+ frame->arena->used = loop->mark;
+ frame->end = loop->outer;
+ --frame->depth;
+ *next = loop->end;
+ return STEP_NEXT;
+ }
+ if (!charge(frame->app, (uint64_t)(loop->end - loop->start) + 1)) {
+ frame->kind = PURE_FAULT_WORK;
+ frame->fault_pc = loop->start - 1;
+ return STEP_FAULT;
+ }
+ loop->slot->num = loop->low.num + (double)loop->k;
+ continue;
+ }
+ if (loop->resume == UINT64_MAX) break;
+ while (loop->k < loop->resume) { /* a failed batch's rounds */
+ int how = pure_run_rest(frame, loop->start);
+ if (how == STEP_SKIP) { /* it left the loop */
+ *next = loop->end;
+ return STEP_NEXT;
+ }
+ if (how != STEP_NEXT) return how;
+ uint32_t pc = loop->end;
+ if ((how = iterate(frame, &pc)) != STEP_NEXT) return how;
+ if (frame->depth < depth) {
+ *next = loop->end;
+ return STEP_NEXT;
+ }
+ }
+ }
+ *next = loop->start;
+ return STEP_NEXT;
+}
+
+/* A LOOP planned PLAN_BATCH the executor runs (step leaves it to its
+ * caller): opened, then in batches. */
+static __attribute__((noinline, cold)) int open_batches(Frame *frame, uint32_t pc, uint32_t *next) {
+ unsigned depth = frame->depth;
+ int how = enter_loop(frame, &frame->m->code[pc], pc, next);
+ if (how != STEP_NEXT || frame->depth == depth) return how;
+ Loop *loop = &frame->loops[depth];
+ loop->resume = 0, loop->failures = 0, loop->reverse = false;
+ return batches(frame, loop, next);
+}
+
#define NEXT do { frame->sp = sp; return STEP_NEXT; } while (0)
#define FAILED do { frame->sp = sp; frame->kind = kind; frame->fault_pc = pc; return STEP_FAULT; } while (0)
#define REFUSED do { frame->sp = sp; frame->status = status; frame->fault_pc = pc; return STEP_REFUSED; } while (0)
#define STOPPED(why) do { frame->status = (why); return STEP_RETURN; } while (0)
/* The instruction op at pc; *next the one to run after it. */
-static inline __attribute__((always_inline)) int step(Frame *frame, const PureOp *op, uint32_t pc, uint32_t *next) {
+static inline __attribute__((always_inline)) int step(Frame *frame, const PureOp *op, uint32_t pc, uint32_t *next, bool batches) {
const PureModule *m = frame->m;
PureValue *values = frame->values;
Event *ev = frame->ev;
@@ -2612,7 +2675,7 @@ static inline __attribute__((always_inline)) int step(Frame *frame, const PureOp
return STEP_NEXT;
case PURE_OP_JMP: *next = arg; return STEP_NEXT;
case PURE_OP_EACH: return enter_each(frame, op, pc, next);
- case PURE_OP_LOOP: return enter_loop(frame, op, pc, next);
+ case PURE_OP_LOOP: return batches && op->plan & PLAN_BATCH ? STEP_BATCH : enter_loop(frame, op, pc, next);
case PURE_OP_BREAK: *next = leave_loop(frame); return STEP_NEXT;
case PURE_OP_CONST: stack[sp++].i64 = op->integer; NEXT; /* the bits: a number's, a bool's or an i64's */
case PURE_OP_LOAD: stack[sp++].i64 = values[arg].i64; NEXT;
@@ -3073,7 +3136,7 @@ static inline __attribute__((always_inline)) PureResult finish(Frame *frame, int
/* The steps compiled code calls (module-run.h). */
int pure_run_step(Frame *frame, uint32_t pc) {
uint32_t next;
- return step(frame, &frame->m->code[pc], pc, &next);
+ return step(frame, &frame->m->code[pc], pc, &next, false);
}
int pure_run_each(Frame *frame, uint32_t pc) {
@@ -3105,7 +3168,7 @@ int pure_run_item(Frame *frame, uint32_t pc) {
for (unsigned f = 0; f < 16; ++f) frame->run.columns[f] = run.column[f].numbers;
}
uint32_t next;
- return step(frame, op, pc, &next);
+ return step(frame, op, pc, &next, false);
}
int pure_run_rest(Frame *frame, uint32_t pc) {
@@ -3118,7 +3181,7 @@ int pure_run_rest(Frame *frame, uint32_t pc) {
if (how != STEP_NEXT) return how;
continue;
}
- int how = step(frame, &frame->m->code[pc], pc, &pc);
+ int how = step(frame, &frame->m->code[pc], pc, &pc, false);
if (how != STEP_NEXT) return how;
}
}
@@ -3135,7 +3198,7 @@ int pure_run_iterate(Frame *frame) {
static inline __attribute__((always_inline)) void open_frame(Frame *frame, const PureModule *m, PureValue *values, PureBlock block,
Event *ev, Slot *stack, Loop *loops) {
frame->m = m, frame->values = values, frame->ev = ev, frame->app = ev->app, frame->arena = ev->arena;
- frame->stack = stack, frame->sp = 0, frame->loops = loops, frame->depth = 0;
+ frame->stack = stack, frame->sp = 0, frame->loops = loops, frame->depth = 0, frame->kind = PURE_FAULT_NONE;
frame->end = block.start + block.length;
}
@@ -3150,9 +3213,38 @@ static __attribute__((noinline)) PureResult run_compiled(PureCompiled code, cons
return finish(&frame, code(&frame), result);
}
-static PureResult run(const PureModule *m, PureValue *values, PureBlock block, Event *ev, Slot *result) {
+/* The executor's run of a block of a module with loops planned PLAN_BATCH:
+ * run's, those loops in batches (module-batch.c). Its own copy of the
+ * steps: in run's, a batch's way among them would cost every instruction
+ * registers (research 126). */
+static __attribute__((noinline, aligned(64))) PureResult run_batches(const PureModule *m, PureValue *values, PureBlock block, Event *ev,
+ Slot *result) {
+ Slot stack[PURE_MODULE_STACK];
+ Loop loops[PURE_MODULE_NESTING];
+ Frame frame;
+ open_frame(&frame, m, values, block, ev, stack, loops);
+ int how = STEP_NEXT;
+ for (uint32_t pc = block.start;;) {
+ if (pc >= frame.end) {
+ if (!frame.depth || (how = iterate(&frame, &pc)) != STEP_NEXT) break;
+ continue;
+ }
+ if ((how = step(&frame, &m->code[pc], pc, &pc, true)) == STEP_NEXT) continue;
+ if (how != STEP_BATCH) break;
+ Frame apart = frame; /* the frame's copy (no call sees the frame itself: its fields stay in registers) */
+ uint32_t past = 0;
+ how = open_batches(&apart, pc - 1, &past);
+ frame = apart, pc = past;
+ if (how != STEP_NEXT) break;
+ }
+ return finish(&frame, how, result);
+}
+
+/* At a cache line's start: the steps' branches land where they would (research 126: else 10% more cycles, as many instructions). */
+static __attribute__((aligned(64))) PureResult run(const PureModule *m, PureValue *values, PureBlock block, Event *ev, Slot *result) {
PureCompiled code = m->jit ? pure_jit_code(m->jit, block) : NULL;
if (code) return run_compiled(code, m, values, block, ev, result);
+ if (m->batches) return run_batches(m, values, block, ev, result);
Slot stack[PURE_MODULE_STACK];
Loop loops[PURE_MODULE_NESTING];
Frame frame;
@@ -3163,7 +3255,7 @@ static PureResult run(const PureModule *m, PureValue *values, PureBlock block, E
if (!frame.depth || (how = iterate(&frame, &pc)) != STEP_NEXT) break;
continue;
}
- if ((how = step(&frame, &m->code[pc], pc, &pc)) != STEP_NEXT) break;
+ if ((how = step(&frame, &m->code[pc], pc, &pc, false)) != STEP_NEXT) break;
}
return finish(&frame, how, result);
}
diff --git a/core/module.h b/core/module.h
index 9b425b2..4f9e4a3 100644
--- a/core/module.h
+++ b/core/module.h
@@ -257,6 +257,7 @@ typedef struct {
bool state_indexed[PURE_MODULE_STATES]; /* list: an index state refers to it (set at load) */
uint8_t *height; /* the operand stack's height at each instruction, from its block's start (the verifier's) */
struct PureJit *jit; /* its blocks compiled (module-jit.c, docs/design/021), or NULL */
+ bool batches; /* a loop of it is planned to run in batches (module-batch.c, docs/design/024) */
PureInputShape input[PURE_MODULE_INPUTS];
PureField field[PURE_MODULE_FIELDS];
PureValue initial[PURE_MODULE_STATES];
generated by cgit v1.2.3 (git 2.46.0) at 2026-10-20 13:40:02 +0000