/* 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;
}