diff options
| -rw-r--r-- | core/module-batch.c | 178 | ||||
| -rw-r--r-- | tests/check.py | 15 |
2 files changed, 178 insertions, 15 deletions
diff --git a/core/module-batch.c b/core/module-batch.c index 04719be..5a339e2 100644 --- a/core/module-batch.c +++ b/core/module-batch.c @@ -26,7 +26,7 @@ #include <stdlib.h> enum { BATCH = 1024, BUFFERS = 24, MASKS = 32, SPLITS = 8, READS = 16, STORES = 8, APPENDS = 8, REDUCES = 8, RECURS = 4, UPDATES = 8, - RECORDS = 8, STEPS = 96, LOCALS = 256, LEAST = 16, FAILURES = 3 }; + RECORDS = 8, STEPS = 96, SUMS = 4, LOCALS = 256, LEAST = 16, FAILURES = 3 }; enum { UNIFORM, AFFINE, LANES, REDUCE }; /* REDUCE: x in x = x op e (value: its reduction) */ typedef struct { @@ -53,6 +53,12 @@ enum { S_NUMBER = 250, S_X, S_SLOT }; typedef struct { uint8_t op, x; double k; } Step; typedef struct { uint32_t from, set; unsigned x, first, count; } Update; typedef struct { uint32_t pc; unsigned x; double *lanes; } Record; +/* A sum into a cell, L[k].f = L[k].f + e: its statement's second k from + * again to resume (past its find and read, skipped), its ADD and its set; + * and as the pass leaves it, its rows and e in the lanes of mask, added at + * the end round by round. */ +typedef struct { uint32_t again, resume, add, set; } Sum; +typedef struct { uint32_t list, field, add, set; Val rows, e; Mask *mask; } Scatter; /* An item a LIST_APPEND at pc appends in the lanes of mask (NULL: all): its fields. */ typedef struct { uint32_t pc; Mask *mask; unsigned count; Val cells[PURE_RECORD_FIELDS]; } Append; /* Lanes a branch sent ahead (NULL: every lane): they run again at pc. */ @@ -108,6 +114,9 @@ typedef struct { Update updates[UPDATES]; Record records[RECORDS]; Step steps[STEPS]; + unsigned sum_count, scatter_count; + Sum sums[SUMS]; + Scatter scatters[SUMS]; } Batch; static _Thread_local Batch batch; @@ -993,17 +1002,27 @@ static bool recur(Batch *b) { unsigned sp = 0; for (unsigned i = up->first; i < up->first + up->count; ++i) { const Step *step = &b->steps[i]; - switch (step->op) { - case S_NUMBER: stack[sp++] = step->k; break; - case S_X: stack[sp++] = b->recur_value[step->x]; break; - case S_SLOT: stack[sp++] = slot; break; - case PURE_OP_NEG: stack[sp - 1] = -stack[sp - 1]; break; - case PURE_OP_NOT: stack[sp - 1] = stack[sp - 1] == 0; break; - case PURE_OP_FLOOR: stack[sp - 1] = floor(stack[sp - 1]); break; + double v; + switch (step->op) { /* as the executor computes each (a fault: not finite, or 0 divided by) */ + case S_NUMBER: stack[sp++] = step->k; continue; + case S_X: stack[sp++] = b->recur_value[step->x]; continue; + case S_SLOT: stack[sp++] = slot; continue; + case PURE_OP_NEG: stack[sp - 1] = -stack[sp - 1]; continue; + case PURE_OP_NOT: stack[sp - 1] = stack[sp - 1] == 0; continue; + case PURE_OP_FLOOR: stack[sp - 1] = floor(stack[sp - 1]); continue; + case PURE_OP_ADD: --sp, v = stack[sp - 1] + stack[sp]; break; + case PURE_OP_SUB: --sp, v = stack[sp - 1] - stack[sp]; break; + case PURE_OP_MUL: --sp, v = stack[sp - 1] * stack[sp]; break; + case PURE_OP_DIV: + if (stack[--sp] == 0) return false; + v = stack[sp - 1] / stack[sp]; + break; default: --sp; - if (!number_op(step->op, stack[sp - 1], stack[sp], &stack[sp - 1])) return false; /* its fault: the executor's */ + if (!number_op(step->op, stack[sp - 1], stack[sp], &v)) return false; } + if (not_finite(v)) return false; + stack[sp - 1] = v; } b->recur_value[up->x] = stack[0]; } @@ -1011,6 +1030,53 @@ static bool recur(Batch *b) { return true; } +/* ---- Sums into cells */ + +/* Whether instructions [a, a + n) and [b, b + n) are the same (a key computed twice). */ +static bool same_code(const PureModule *m, uint32_t a, uint32_t b, uint32_t n) { + for (uint32_t i = 0; i < n; ++i) + if (m->code[a + i].op != m->code[b + i].op || m->code[a + i].arg != m->code[b + i].arg || + m->code[a + i].integer != m->code[b + i].integer) + return false; + return true; +} + +/* Whether code [a, b) reads list (its cells or keys), branches or loops. */ +static bool touches(const PureModule *m, uint32_t a, uint32_t b, uint32_t list) { + for (uint32_t at = a; at < b; ++at) { + const PureOp *op = &m->code[at]; + if (op->op == PURE_OP_JZ || op->op == PURE_OP_JMP || op->op == PURE_OP_LOOP || op->op == PURE_OP_BREAK) return true; + if ((op->op == PURE_OP_ITEM_GET && list_of(op->arg) == list) || + ((op->op == PURE_OP_LIST_FIND || op->op == PURE_OP_LIST_HAS || op->op == PURE_OP_LIST_COUNT) && op->arg == list)) + return true; + } + return false; +} + +/* The block's statements L[k].f = L[k].f + e (k computed twice the same, + * reading no L; e reading no L; the set at k's row as its find found it). */ +static bool sums(Batch *b, uint32_t start, uint32_t end) { + const PureModule *m = b->m; + for (uint32_t set = start; set < end; ++set) { + const PureOp *op = &m->code[set]; + if (op->op == PURE_OP_LOOP) set += op->arg >> 16; + if (op->op != PURE_OP_ITEM_SET || !(op->plan & PLAN_ROW) || set < start + 4 || m->code[set - 1].op != PURE_OP_ADD) continue; + uint32_t list = list_of(op->arg), from = set; + while (from > start && m->height[from]) --from; /* the statement's start */ + uint32_t find = from; + while (find < set && !(m->code[find].op == PURE_OP_LIST_FIND && m->code[find].arg == list && m->height[find] == 1)) ++find; + uint32_t n = find - from, again = find + 1, read = again + n; + if (find == set || read + 2 > set - 1 || !(m->code[find].plan & PLAN_ROW) || m->height[from] || !same_code(m, from, again, n) || + m->code[read].op != PURE_OP_LIST_FIND || m->code[read].arg != list || !(m->code[read].plan & PLAN_JOINED) || + m->code[read + 1].op != PURE_OP_ITEM_GET || m->code[read + 1].arg != op->arg || touches(m, from, find, list) || + touches(m, read + 2, set - 1, list) || m->height[read + 2] != 2 || m->height[set - 1] != 3) + continue; + if (b->sum_count == SUMS) return false; + b->sums[b->sum_count++] = (Sum){again, read + 2, set - 1, set}; + } + return true; +} + /* ---- The pass */ static void nested(Batch *b, const PureOp *op, uint32_t pc); @@ -1029,7 +1095,25 @@ static bool pass(Batch *b, uint32_t start, uint32_t end) { pc = next; continue; } - unsigned u = 0; + unsigned u = 0, k = 0; + while (k < b->sum_count && b->sums[k].again != pc && b->sums[k].add != pc && b->sums[k].set != pc) ++k; + if (k < b->sum_count) { /* a sum into a cell: its row and e, kept for the end */ + const Sum *sum = &b->sums[k]; + if (pc == sum->again) pc = sum->resume; /* the key again, its find and the cell's read: not needed */ + else if (pc == sum->add) pc = sum->set; + else { + const PureOp *set = &m->code[pc++]; + if (b->scatter_count == SUMS) { + b->failed = true; + break; + } + Scatter *sc = &b->scatters[b->scatter_count++]; + sc->list = list_of(set->arg), sc->field = item_field(set->arg), sc->add = sum->add, sc->set = sum->set; + sc->e = b->stack[--b->sp], sc->rows = b->stack[--b->sp], sc->mask = b->active; + sc->e.temp = sc->rows.temp = false; + } + continue; + } while (u < b->update_count && b->updates[u].from != pc) ++u; if (u < b->update_count) { /* a recurrence's x = e: made ahead, round by round */ pc = b->updates[u].set + 1; @@ -1168,6 +1252,8 @@ static void sweep(Batch *b) { mark_val(kept, &b->stores[s].rows), mark_val(kept, &b->stores[s].value), mark_mask(b, kept, kept_mask, b->stores[s].mask); for (unsigned d = 0; d < b->sp; ++d) mark_val(kept, &b->stack[d]); for (unsigned r = 0; r < b->record_count; ++r) mark_lanes(kept, b->records[r].lanes); + for (unsigned i = 0; i < b->scatter_count; ++i) + mark_val(kept, &b->scatters[i].rows), mark_val(kept, &b->scatters[i].e), mark_mask(b, kept, kept_mask, b->scatters[i].mask); for (unsigned a = 0; a < b->append_count; ++a) { mark_mask(b, kept, kept_mask, b->appends[a].mask); for (unsigned f = 0; f < b->appends[a].count; ++f) mark_val(kept, &b->appends[a].cells[f]); @@ -1365,6 +1451,22 @@ static bool settle(Batch *b) { PureCells cells[STORES]; const uint32_t *mask[STORES]; if (!fold(b)) return false; + for (unsigned i = 0; i < b->scatter_count; ++i) { /* a sum's cells: an event's list's, read and set by nothing else in the batch */ + const Scatter *sc = &b->scatters[i]; + PureCells c; + if (!pure_list_cells(b->app->lists[sc->list], &c) || !c.owned || c.width[sc->field] == 255 || c.width[sc->field] == 0) return false; + Mask *saved = b->active; + b->active = sc->mask; + bool in = rows_in(b, &sc->rows, c.count); + b->active = saved; + if (!in) return false; + for (unsigned r = 0; r < b->read_count; ++r) + if (b->reads[r].list == sc->list && b->reads[r].field == sc->field) return false; + for (unsigned t = 0; t < b->store_count; ++t) + if (b->stores[t].list == sc->list && b->stores[t].field == sc->field) return false; + for (unsigned j = 0; j < i; ++j) + if (b->scatters[j].list == sc->list && b->scatters[j].field == sc->field) return false; + } for (unsigned i = 0; i < b->store_count; ++i) { Store *s = &b->stores[i]; PureList *list = b->app->lists[s->list]; @@ -1447,7 +1549,7 @@ int pure_batch_run(Frame *frame, Loop *loop, unsigned *done) { b->failed = b->none = b->items = false, b->active = NULL, b->nest = (Nest){0}, b->work = 0, b->var = NULL; b->sp = b->split_count = b->buffers = b->masks = b->read_count = b->store_count = b->spare_count = 0; b->mask_free_count = b->reduce_count = b->append_count = 0; - b->recur_count = b->update_count = b->record_count = b->step_count = 0; + b->recur_count = b->update_count = b->record_count = b->step_count = b->sum_count = b->scatter_count = 0; memset(b->sets, 0, sizeof(b->sets)); for (uint32_t pc = loop->start; pc < loop->end; ++pc) { /* the locals it sets (a nested loop's slot too), and whether it sets items */ const PureOp *op = &m->code[pc]; @@ -1458,7 +1560,8 @@ int pure_batch_run(Frame *frame, Loop *loop, unsigned *done) { b->state[at] = 0; } } - if (!recurrences(b, loop->start, loop->end) || !recur(b)) b->failed = true; /* the recurrences ahead, round by round */ + if (!recurrences(b, loop->start, loop->end) || !recur(b) || (b->items && !sums(b, loop->start, loop->end))) + b->failed = true; /* the recurrences ahead, round by round; the sums into cells */ if (!b->failed && 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 */ @@ -1467,12 +1570,63 @@ int pure_batch_run(Frame *frame, Loop *loop, unsigned *done) { if (b->state[at] == 2) mask_lanes(b, b->written[at]); } for (unsigned a = 0; a < b->append_count; ++a) mask_lanes(b, b->appends[a].mask); + for (unsigned i = 0; i < b->scatter_count; ++i) mask_lanes(b, b->scatters[i].mask); } uint64_t work = (n - 1) * per + b->work; /* the rounds after the first, and every round of their nested loops */ if (b->failed || work > budget - app->work || !settle(b)) { loop->resume = ++loop->failures >= FAILURES ? UINT64_MAX : loop->k + n; /* its rounds one by one, then batches again */ return STEP_NEXT; } + if (b->scatter_count) { /* the sums into cells round by round, as the executor adds and sets (each its own cells) */ + const double *rows[SUMS], *es[SUMS]; + const uint32_t *masks[SUMS]; + PureCells cells[SUMS]; + for (unsigned i = 0; i < b->scatter_count; ++i) { + const Scatter *sc = &b->scatters[i]; + rows[i] = numbers(b, &sc->rows), es[i] = numbers(b, &sc->e), masks[i] = mask_lanes(b, sc->mask); + pure_list_cells(b->app->lists[sc->list], &cells[i]); + if (!rows[i] || !es[i]) { /* no lanes left to make them: as the executor, round by round */ + loop->resume = ++loop->failures >= FAILURES ? UINT64_MAX : loop->k + n; + return STEP_NEXT; + } + } + for (unsigned r = 0; r < n; ++r) { + unsigned l = round_of(b, r); + for (unsigned i = 0; i < b->scatter_count; ++i) { + const Scatter *sc = &b->scatters[i]; + if (masks[i] && !masks[i][l]) continue; + size_t row = (size_t)rows[i][l]; + uint8_t width = cells[i].width[sc->field]; + void *column = cells[i].columns[sc->field]; + double cell, v; + if (width == 8) memcpy(&cell, (const double *)column + row, sizeof(cell)); + else cell = width == 4 ? ((const uint32_t *)column)[row] : ((const uint8_t *)column)[row]; + v = cell + es[i][l]; + if (!isfinite(v)) { /* its round's fault (the event undone) */ + app->work += (uint64_t)r * per; + frame->kind = PURE_FAULT_NON_FINITE, frame->fault_pc = sc->add; + return STEP_FAULT; + } + bool fits = width == 8 || (v >= 0 && v < (width == 4 ? 4294967296.0 : 256.0) && v == (double)(uint32_t)v && + !(v == 0 && signbit(v))); + uint8_t need = fits ? width : width_needed(v); + if (need > width) { /* wider: the column as the executor's set widens it */ + PureList *list = b->app->lists[sc->list]; + if (!pure_list_widen(list, sc->field, need)) { + app->work += (uint64_t)r * per; + frame->status = PURE_ALLOCATION, frame->fault_pc = sc->set; + return STEP_REFUSED; + } + pure_list_cells(list, &cells[i]); + column = cells[i].columns[sc->field], width = need; + } + if (width == 8) memcpy((double *)column + row, &v, sizeof(v)); + else if (width == 4) ((uint32_t *)column)[row] = (uint32_t)v; + else ((uint8_t *)column)[row] = (uint8_t)v; + } + } + for (unsigned i = 0; i < b->scatter_count; ++i) pure_list_touched(b->app->lists[b->scatters[i].list]); + } for (unsigned r = 0; r < n && b->append_count; ++r) { /* the appends round by round, each as the executor's step makes it */ unsigned l = round_of(b, r); for (unsigned i = 0; i < b->append_count; ++i) { diff --git a/tests/check.py b/tests/check.py index 08cf547..f439e73 100644 --- a/tests/check.py +++ b/tests/check.py @@ -1178,7 +1178,8 @@ on go { # 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. +# by one), keys going down with an if and an else, two sets of one field, +# sums into three cells in turn (the column widened as they grow). BATCH_SOURCE = """record Cell { at = 0 v = 0 @@ -1211,6 +1212,9 @@ on go { t[go.n - 1 - k].v = x + 1 } for k in 0 .. go.n { + t[k - floor(k / 3) * 3].v = t[k - floor(k / 3) * 3].v + k * 1000000 + } + for k in 0 .. go.n { t[k].w = 1000 / (k - go.q) } out = t[go.n - 1].v + t[0].w @@ -1519,8 +1523,11 @@ def tier_program(rng): lines.append(f'{pad} e.append(Cell {{ at: {at()}, v: {number(1, inner)} }})') elif pick < 0.3: lines.append(f'{pad} d.add(Cell {{ at: {rng.choice([name, f"{name} * 3", key(2, inner)])}, v: {number(1, inner)} }})') - elif pick < 0.6: + elif pick < 0.5: lines.append(f'{pad} t[{at()}].v = {number(1, inner)}') + elif pick < 0.6: # a sum into a cell (its rows read and set by the rounds in turn) + cell = at() + lines.append(f'{pad} t[{cell}].v = t[{cell}].v + {number(1, inner)}') else: lines.append(f'{pad} if {cond(1, inner)} {{ t[{at()}].v = {number(1, inner)} }}' + (f' else {{ t[{at()}].v = {number(1, inner)} }}' if rng.random() < 0.4 else '')) @@ -1564,8 +1571,10 @@ def tier_program(rng): lines.append(f'{pad} e.append(Cell {{ at: w{name}, v: x1 }})') elif pick < 0.6: lines.append(f'{pad} t[{rng.choice([name, f"w{name}", f"floor(x1 / 100)"])}].v = x1') - elif pick < 0.8: + elif pick < 0.7: lines.append(f'{pad} x1 = {step()}') + elif pick < 0.8: + lines.append(f'{pad} t[w{name}].v = t[w{name}].v + x1') else: lines.append(f'{pad} ra = ra + w{name}') lines.append(f'{pad}}}') |