From 10a50dd20abe8542d6ed6487d2c46d964af59c75 Mon Sep 17 00:00:00 2001 From: eunhhu Date: Mon, 5 Oct 2026 22:53:09 +0100 Subject: Batch executor stage 1 (024): a count's loop whose block has batch forms (lane forms, locals set before read in every round, ifs, numbers set in items) runs, in the executor, up to 1024 rounds at a time: values uniform, affine or lanes (numbers, or whole numbers in four bytes), branches as masks, cells read by affine rows as strided columns, sets kept to the batch's end and made only when no round reads an earlier round's; a fault, a form it lacks or such a read gives the rounds back to the executor one by one, work counted as written. Planned at load (PURE_BATCH=0: none); the executor of a module without such loops is the same code (run aligned to 64: as many instructions and cycles), with one its own copy. knapsack with PURE_JIT=0: 1,056 to 13.7 ms. module_tier compares batches with the executor alone and makes loops of rounds apart; BATCH_SOURCE: widened columns, -0, a fault mid-batch, rounds reading the last's sets --- Makefile | 4 +- core/module-batch.c | 985 ++++++++++++++++++++++++++++++++++++++++++++++++++++ core/module-list.c | 18 + core/module-list.h | 13 + core/module-run.h | 72 +++- core/module.c | 194 ++++++++--- core/module.h | 1 + tests/check.py | 93 ++++- 8 files changed, 1316 insertions(+), 64 deletions(-) create mode 100644 core/module-batch.c diff --git a/Makefile b/Makefile index 368b311..c01744b 100644 --- a/Makefile +++ b/Makefile @@ -23,7 +23,7 @@ BUILD ?= build # store/test-log.c, link/test-link.c, serve/test-message-json.c); # tests/check.py checks the hosts end to end. INCLUDES = -Icore -MODEL = core/module.c core/module-jit.c core/module-list.c core/module-save.c core/module-text.c core/module-store.c core/flow.c +MODEL = core/module.c core/module-batch.c core/module-jit.c core/module-list.c core/module-save.c core/module-text.c core/module-store.c core/flow.c STORE = store/store-tree.c store/store-log.c LINK = link/link-protocol.c link/link.c link/sending.c link/crypto.c SERVE = serve/serve.c serve/deliver.c serve/message-json.c serve/sha256.c @@ -43,6 +43,8 @@ $(BUILD)/obj/%.o: %.c $(HEADERS) # (docs/design/020: 8% of a breadth first search). LIST_OPTIMIZE ?= -O3 $(BUILD)/obj/core/module-list.o: CFLAGS += $(LIST_OPTIMIZE) +# A batch's instructions are loops over its lanes: vector instructions too (docs/design/024). +$(BUILD)/obj/core/module-batch.o: CFLAGS += $(LIST_OPTIMIZE) # The links know nothing of the core: they build without its headers. $(BUILD)/obj/link/%.o: link/%.c $(wildcard link/*.h) 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 + +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 +#include -/* 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]; diff --git a/tests/check.py b/tests/check.py index 5ed8e8b..f330bae 100644 --- a/tests/check.py +++ b/tests/check.py @@ -1173,6 +1173,52 @@ on go { } """ +# Loops a batch runs (Pure docs/design/024) where it must give its rounds +# back or change a list's form (BATCH_SOURCE): cells past a byte and past +# four, a fraction and -0 set in the middle of a batch (the columns widened), +# 0 divided by at round q (a fault halfway through a batch: the executor's, +# at its round), each round reading the last one's set (not apart: run one +# by one), keys going down with an if and an else, two sets of one field. +BATCH_SOURCE = """record Cell { + at = 0 + v = 0 + w = 0 +} +state out = 0 +state low = 0 +input go = message { + n: u32 + q: u32 +} +on go { + let t: list of Cell by at + for i in 0 .. go.n { + t.add(Cell { at: i }) + } + for k in 0 .. go.n { + t[k].v = k * k * 1000 + t[k].w = k * (0 - 1) + } + for k in 0 .. go.n { + if k == go.q { t[k].v = 0.25 } else { t[k].w = t[k].w + 1 } + } + for k in 1 .. go.n { + t[k].v = t[k - 1].v + 1 + } + for k in 0 .. go.n { + let x = t[go.n - 1 - k].v + if x > 5000 { t[go.n - 1 - k].w = x - 5000 } else { t[go.n - 1 - k].w = 7 } + t[go.n - 1 - k].v = x + 1 + } + for k in 0 .. go.n { + t[k].w = 1000 / (k - go.q) + } + out = t[go.n - 1].v + t[0].w + low = t[floor(go.n / 2)].w +} +""" + + 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, @@ -1211,6 +1257,19 @@ def module_assumptions(aup, pure, work): 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)) + source, program = work / 'batch.aup', work / 'batch.pmod' # batches against the executor's rounds one by one + source.write_text(BATCH_SOURCE) + compile_module(aup, source, program) + given = ''.join(f'message go {struct.pack("