diff options
Diffstat (limited to 'research/experiments/045-proof-compiler')
16 files changed, 607 insertions, 0 deletions
diff --git a/research/experiments/045-proof-compiler/2026-10-19-break.jsonl b/research/experiments/045-proof-compiler/2026-10-19-break.jsonl new file mode 100644 index 0000000..07aef0d --- /dev/null +++ b/research/experiments/045-proof-compiler/2026-10-19-break.jsonl @@ -0,0 +1,10 @@ +{"what": "(a) instructions the executor runs, UAX #14 (ops-count.patch: by opcode, and reads of the same list, version, field and place within an event)", "code_points": 61285, "executed_per_point": 549.9, "moves_per_point": 205.5, "constants_per_point": 76.7, "same_reads_per_point": 16.4, "left_per_point": 251.3, "factor": 2.19, "bar": 4, "passed": false, "note": "the budget counts blocks as written: 1,774 a point; executed 549.9"} +{"what": "(b) the executor stitched (stitch.c, native-hook.patch: step() on each constant instruction, a function a basic block), cost.c (answers checked first)", "interpreted": {"instructions_per_point": 40702.7, "cycles_per_point": 15565.8}, "stitched": {"instructions_per_point": 28601.5, "cycles_per_point": 11849.9}, "instruction_factor": 1.42, "cycle_factor": 1.31, "bar": 3, "passed": false} +{"what": "Vega C (text/linebreak.c) on the same lines", "instructions_per_point": 220.2, "cycles_per_point": 82.4} +{"what": "machine instructions an executed instruction", "interpreted": 74.0, "stitched": 52.0, "dispatch_and_decode": 22.0} +{"what": "variants of the app (events.c, executor): machine instructions a code point", "empty_handler": 1583.2, "lists_built": 24233.7, "and_text_record": 27184.8, "whole": 40172.9} +{"what": "units (unit.c, units/*.aup): machine instructions an operation, PURE_JIT=0", "arith_loop_batches": 34.7, "arith_loop_executor": 248.0, "append_let_list_batches": 35.7, "stored_list_read_with_mod": 435.8, "stored_list_read": 330.8, "mod": 75.4, "block_fn_call": 1375.1} +{"mode":"interp","lines":18672,"code_points":61285,"rounds":3,"jit":"0","c_instructions_per_point":220.2,"c_cycles_per_point":81.9,"pure_instructions_per_point":40702.7,"pure_cycles_per_point":15591.7} +{"mode":"native","lines":18672,"code_points":61285,"rounds":3,"jit":"0","c_instructions_per_point":220.2,"c_cycles_per_point":82.7,"pure_instructions_per_point":28600.9,"pure_cycles_per_point":11868.1} +{"mode":"interp","lines":18672,"code_points":61285,"rounds":3,"jit":"0","c_instructions_per_point":220.2,"c_cycles_per_point":82.2,"pure_instructions_per_point":40702.7,"pure_cycles_per_point":15539.8} +{"mode":"native","lines":18672,"code_points":61285,"rounds":3,"jit":"0","c_instructions_per_point":220.2,"c_cycles_per_point":83.5,"pure_instructions_per_point":28602.1,"pure_cycles_per_point":11831.7} diff --git a/research/experiments/045-proof-compiler/cost.c b/research/experiments/045-proof-compiler/cost.c new file mode 100644 index 0000000..2b300a4 --- /dev/null +++ b/research/experiments/045-proof-compiler/cost.c @@ -0,0 +1,132 @@ +/* Research 045 (029's principle 1, its breaking experiment): what UAX #14 costs in machine instructions and cycles a + * code point, Vega's C (text/linebreak.c) and Pure's executor (aup's examples/linebreak.aup), on the lines + * 044's linebreak_check.py writes; user-mode counters (perf_event_open) around each, ROUNDS passes after one checked. + * + * cc -O2 -std=c17 -I../../../core -I../../../../vega/text cost.c ../../../../vega/text/linebreak.c \ + * ../../../../vega/text/unicode-data.c ../../../build/libpure.a -lm -pthread -o cost + * ./cost linebreak.pmod RANGES LINES ROUNDS + * + * One JSON line. */ +#define _GNU_SOURCE +#include "module.h" +#include "text.h" +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <time.h> +#include <linux/perf_event.h> +#include <sys/ioctl.h> +#include <sys/syscall.h> +#include <unistd.h> + +static double now_ns(void) { + struct timespec t; + clock_gettime(CLOCK_MONOTONIC, &t); + return (double)t.tv_sec * 1e9 + (double)t.tv_nsec; +} + +static int by_value(const void *a, const void *b) { + double x = *(const double *)a, y = *(const double *)b; + return (x > y) - (x < y); +} + +static unsigned char *whole(const char *path, size_t *size) { + FILE *f = fopen(path, "rb"); + if (!f) return NULL; + fseek(f, 0, SEEK_END); + *size = (size_t)ftell(f); + rewind(f); + unsigned char *bytes = malloc(*size ? *size : 1); + if (fread(bytes, 1, *size, f) != *size) { free(bytes); bytes = NULL; } + fclose(f); + return bytes; +} + +typedef struct { uint32_t count; const uint32_t *codes; const unsigned char *want; unsigned char *payload; } Line; + +/* A line's boundaries from Pure: the bytes state "breaks", compared as breaks or not with want. */ +typedef struct { const unsigned char *want; size_t at; bool same; } Compare; +static bool compare(void *context, PureSpan span) { + Compare *c = context; + for (size_t i = 0; i < span.size; ++i, ++c->at) c->same = c->same && (span.data[i] != 0) == c->want[c->at]; + return true; +} + + +static int counter(uint64_t config) { + struct perf_event_attr a; + memset(&a, 0, sizeof(a)); + a.size = sizeof(a), a.type = PERF_TYPE_HARDWARE, a.config = config, a.disabled = 1, a.exclude_kernel = 1, a.exclude_hv = 1; + return (int)syscall(SYS_perf_event_open, &a, 0, -1, -1, 0); +} + +static uint64_t read_counter(int fd) { + uint64_t v = 0; + if (read(fd, &v, sizeof(v)) != sizeof(v)) return 0; + return v; +} + +int main(int argc, char **argv) { + if (argc != 5) { fprintf(stderr, "usage: %s MODULE RANGES LINES ROUNDS\n", argv[0]); return 2; } + size_t ranges_size, lines_size; + unsigned char *ranges = whole(argv[2], &ranges_size), *bytes = whole(argv[3], &lines_size); + int rounds = atoi(argv[4]); + if (!ranges || !bytes) return 1; + static Line lines[1 << 16]; + size_t count = 0, points = 0; + for (size_t at = 0; at + 4 <= lines_size && count < sizeof(lines) / sizeof(*lines); ++count) { + Line *l = &lines[count]; + memcpy(&l->count, bytes + at, 4); + l->codes = (const uint32_t *)(bytes + at + 4); + l->want = bytes + at + 4 + 4 * (size_t)l->count; + at += 4 + 4 * (size_t)l->count + l->count + 1; + l->payload = malloc(8 * (size_t)l->count + 1); + for (uint32_t i = 0; i < l->count; ++i) { + double c = l->codes[i]; + memcpy(l->payload + 8 * i, &c, 8); + } + points += l->count; + } + PureModule module = {0}; + char error[160]; + if (pure_module_read(argv[1], &module, error, sizeof(error)) != PURE_OK) { fprintf(stderr, "%s\n", error); return 1; } + PureApp app; + if (pure_app_start(&app, &module, (PureData){0}) != PURE_OK) return 1; + int load = pure_module_input(&module, "load"), line = pure_module_input(&module, "line"); + if (pure_app_message(&app, (uint32_t)load, (PureSpan){ranges, ranges_size}) != PURE_OK) return 1; + static uint8_t got[4096]; + size_t right = 0; + for (size_t k = 0; k < count; ++k) { /* checked first: both give the test's boundaries */ + bool same = pure_app_message(&app, (uint32_t)line, (PureSpan){lines[k].payload, 8 * (size_t)lines[k].count}) == PURE_OK && + lines[k].count < sizeof(got) && vega_line_breaks(lines[k].codes, lines[k].count, got); + for (uint32_t i = 0; same && i <= lines[k].count; ++i) same = (got[i] != VEGA_BREAK_NONE) == lines[k].want[i]; + right += same; + } + if (right != count) { fprintf(stderr, "right %zu of %zu\n", right, count); return 1; } + int ins = counter(PERF_COUNT_HW_INSTRUCTIONS), cyc = counter(PERF_COUNT_HW_CPU_CYCLES); + if (ins < 0 || cyc < 0) { perror("perf_event_open"); return 1; } + volatile unsigned sink = 0; + ioctl(ins, PERF_EVENT_IOC_RESET, 0), ioctl(cyc, PERF_EVENT_IOC_RESET, 0); + ioctl(ins, PERF_EVENT_IOC_ENABLE, 0), ioctl(cyc, PERF_EVENT_IOC_ENABLE, 0); + for (int r = 0; r < rounds; ++r) + for (size_t k = 0; k < count; ++k) { + vega_line_breaks(lines[k].codes, lines[k].count, got); + sink += got[0]; + } + ioctl(ins, PERF_EVENT_IOC_DISABLE, 0), ioctl(cyc, PERF_EVENT_IOC_DISABLE, 0); + uint64_t c_ins = read_counter(ins), c_cyc = read_counter(cyc); + ioctl(ins, PERF_EVENT_IOC_RESET, 0), ioctl(cyc, PERF_EVENT_IOC_RESET, 0); + ioctl(ins, PERF_EVENT_IOC_ENABLE, 0), ioctl(cyc, PERF_EVENT_IOC_ENABLE, 0); + for (int r = 0; r < rounds; ++r) + for (size_t k = 0; k < count; ++k) + if (pure_app_message(&app, (uint32_t)line, (PureSpan){lines[k].payload, 8 * (size_t)lines[k].count}) != PURE_OK) return 1; + ioctl(ins, PERF_EVENT_IOC_DISABLE, 0), ioctl(cyc, PERF_EVENT_IOC_DISABLE, 0); + uint64_t p_ins = read_counter(ins), p_cyc = read_counter(cyc); + double n = (double)points * rounds; + const char *jit = getenv("PURE_JIT"); + printf("{\"lines\":%zu,\"code_points\":%zu,\"rounds\":%d,\"jit\":\"%s\",\"c_instructions_per_point\":%.1f,\"c_cycles_per_point\":%.1f," + "\"pure_instructions_per_point\":%.1f,\"pure_cycles_per_point\":%.1f}\n", + count, points, rounds, jit ? jit : "", c_ins / n, c_cyc / n, p_ins / n, p_cyc / n); + pure_app_stop(&app); + return 0; +} diff --git a/research/experiments/045-proof-compiler/events.c b/research/experiments/045-proof-compiler/events.c new file mode 100644 index 0000000..58dd0f1 --- /dev/null +++ b/research/experiments/045-proof-compiler/events.c @@ -0,0 +1,103 @@ +/* Research 045: where UAX #14's machine instructions go in Pure's executor. A variant of aup's examples/linebreak.aup + * (the patches in variants: v0 an empty handler, v1 the lists built, v2 and the Text record, the app itself all of it) on the + * lines 044's linebreak_check.py writes; machine instructions and cycles a code point (perf_event_open, user mode), + * Vega's C beside it. No answer checked (the variants answer nothing); cost.c checks the app itself. + * + * cc -O2 -std=c17 -I../../../core -I../../../../vega/text events.c ../../../../vega/text/linebreak.c \ + * ../../../../vega/text/unicode-data.c ../../../build/libpure.a -lm -pthread -o events + * ./events VARIANT.pmod RANGES LINES ROUNDS one JSON line */ +#define _GNU_SOURCE +#include "module.h" +#include "text.h" +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <linux/perf_event.h> +#include <sys/ioctl.h> +#include <sys/syscall.h> +#include <unistd.h> + +static unsigned char *whole(const char *path, size_t *size) { + FILE *f = fopen(path, "rb"); + if (!f) return NULL; + fseek(f, 0, SEEK_END); + *size = (size_t)ftell(f); + rewind(f); + unsigned char *bytes = malloc(*size ? *size : 1); + if (fread(bytes, 1, *size, f) != *size) { free(bytes); bytes = NULL; } + fclose(f); + return bytes; +} + +typedef struct { uint32_t count; const uint32_t *codes; const unsigned char *want; unsigned char *payload; } Line; + +static int counter(uint64_t config) { + struct perf_event_attr a; + memset(&a, 0, sizeof(a)); + a.size = sizeof(a), a.type = PERF_TYPE_HARDWARE, a.config = config, a.disabled = 1, a.exclude_kernel = 1, a.exclude_hv = 1; + return (int)syscall(SYS_perf_event_open, &a, 0, -1, -1, 0); +} + +static uint64_t read_counter(int fd) { + uint64_t v = 0; + if (read(fd, &v, sizeof(v)) != sizeof(v)) return 0; + return v; +} + +int main(int argc, char **argv) { + if (argc != 5) { fprintf(stderr, "usage: %s MODULE RANGES LINES ROUNDS\n", argv[0]); return 2; } + size_t ranges_size, lines_size; + unsigned char *ranges = whole(argv[2], &ranges_size), *bytes = whole(argv[3], &lines_size); + int rounds = atoi(argv[4]); + if (!ranges || !bytes) return 1; + static Line lines[1 << 16]; + size_t count = 0, points = 0; + for (size_t at = 0; at + 4 <= lines_size && count < sizeof(lines) / sizeof(*lines); ++count) { + Line *l = &lines[count]; + memcpy(&l->count, bytes + at, 4); + l->codes = (const uint32_t *)(bytes + at + 4); + l->want = bytes + at + 4 + 4 * (size_t)l->count; + at += 4 + 4 * (size_t)l->count + l->count + 1; + l->payload = malloc(8 * (size_t)l->count + 1); + for (uint32_t i = 0; i < l->count; ++i) { + double c = l->codes[i]; + memcpy(l->payload + 8 * i, &c, 8); + } + points += l->count; + } + PureModule module = {0}; + char error[160]; + if (pure_module_read(argv[1], &module, error, sizeof(error)) != PURE_OK) { fprintf(stderr, "%s\n", error); return 1; } + PureApp app; + if (pure_app_start(&app, &module, (PureData){0}) != PURE_OK) return 1; + int load = pure_module_input(&module, "load"), line = pure_module_input(&module, "line"); + if (pure_app_message(&app, (uint32_t)load, (PureSpan){ranges, ranges_size}) != PURE_OK) return 1; + static uint8_t got[4096]; + int ins = counter(PERF_COUNT_HW_INSTRUCTIONS), cyc = counter(PERF_COUNT_HW_CPU_CYCLES); + if (ins < 0 || cyc < 0) { perror("perf_event_open"); return 1; } + volatile unsigned sink = 0; + ioctl(ins, PERF_EVENT_IOC_RESET, 0), ioctl(cyc, PERF_EVENT_IOC_RESET, 0); + ioctl(ins, PERF_EVENT_IOC_ENABLE, 0), ioctl(cyc, PERF_EVENT_IOC_ENABLE, 0); + for (int r = 0; r < rounds; ++r) + for (size_t k = 0; k < count; ++k) { + vega_line_breaks(lines[k].codes, lines[k].count, got); + sink += got[0]; + } + (void)got; + ioctl(ins, PERF_EVENT_IOC_DISABLE, 0), ioctl(cyc, PERF_EVENT_IOC_DISABLE, 0); + uint64_t c_ins = read_counter(ins), c_cyc = read_counter(cyc); + ioctl(ins, PERF_EVENT_IOC_RESET, 0), ioctl(cyc, PERF_EVENT_IOC_RESET, 0); + ioctl(ins, PERF_EVENT_IOC_ENABLE, 0), ioctl(cyc, PERF_EVENT_IOC_ENABLE, 0); + for (int r = 0; r < rounds; ++r) + for (size_t k = 0; k < count; ++k) + if (pure_app_message(&app, (uint32_t)line, (PureSpan){lines[k].payload, 8 * (size_t)lines[k].count}) != PURE_OK) return 1; + ioctl(ins, PERF_EVENT_IOC_DISABLE, 0), ioctl(cyc, PERF_EVENT_IOC_DISABLE, 0); + uint64_t p_ins = read_counter(ins), p_cyc = read_counter(cyc); + double n = (double)points * rounds; + const char *jit = getenv("PURE_JIT"); + printf("{\"lines\":%zu,\"code_points\":%zu,\"rounds\":%d,\"jit\":\"%s\",\"c_instructions_per_point\":%.1f,\"c_cycles_per_point\":%.1f," + "\"pure_instructions_per_point\":%.1f,\"pure_cycles_per_point\":%.1f}\n", + count, points, rounds, jit ? jit : "", c_ins / n, c_cyc / n, p_ins / n, p_cyc / n); + pure_app_stop(&app); + return 0; +} diff --git a/research/experiments/045-proof-compiler/native-hook.patch b/research/experiments/045-proof-compiler/native-hook.patch new file mode 100644 index 0000000..a791e86 --- /dev/null +++ b/research/experiments/045-proof-compiler/native-hook.patch @@ -0,0 +1,25 @@ +diff --git a/core/module.c b/core/module.c +index 4b20e25..fd953e8 100644 +--- a/core/module.c ++++ b/core/module.c +@@ -4967,10 +4967,20 @@ static __attribute__((noinline, aligned(64))) PureResult run_batches(const PureM + return finish(&frame, how, result); + } + ++#ifdef PURE_NATIVE_INC /* research 045: the executor's steps stitched for one module */ ++#include PURE_NATIVE_INC ++#endif ++ + /* 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); ++#ifdef PURE_NATIVE_INC ++ static const PureModule *native_seen; ++ static bool native_ok; ++ if (m != native_seen) native_seen = m, native_ok = native_matches(m) && getenv("PURE_NATIVE"); ++ if (native_ok && m->runner == 2) return run_native(m, values, block, ev, result); ++#endif + if (m->runner) return m->runner == 2 ? run_calls(m, values, block, ev, result) : run_batches(m, values, block, ev, result); + Slot stack[PURE_MODULE_STACK]; + Loop loops[PURE_MODULE_NESTING]; diff --git a/research/experiments/045-proof-compiler/ops-count.patch b/research/experiments/045-proof-compiler/ops-count.patch new file mode 100644 index 0000000..616ad09 --- /dev/null +++ b/research/experiments/045-proof-compiler/ops-count.patch @@ -0,0 +1,62 @@ +diff --git a/core/module.c b/core/module.c +index 4b20e25..2205f77 100644 +--- a/core/module.c ++++ b/core/module.c +@@ -3902,7 +3902,57 @@ static __attribute__((noinline, cold)) int open_batches(Frame *frame, uint32_t p + #define STOPPED(why) do { frame->status = (why); return STEP_RETURN; } while (0) + + /* The instruction op at pc; *next the one to run after it. */ ++/* Research only (029's breaking experiment): the instructions the executor runs, by opcode. */ ++#include <stdio.h> ++static uint64_t research_ops[256], research_same[256]; ++static const char *const research_names[] = {"CONST", "LOAD", "ADD", "SUB", "MUL", "DIV", "NEG", "LT", "LE", "GT", "GE", "EQ", "NE", "AND", "OR", "NOT", "MIN", "MAX", "CLAMP", "STORE", "JZ", "JMP", "FIELD", "LEN", "REPLY", "REQUIRE", "TEXT_CONST", "TEXT_LOAD", "NUM_TEXT", "CONCAT", "CHARS", "LINES", "TEXT_BYTES", "ANCHOR_LOAD", "ANCHOR_START", "ANCHOR_END", "ANCHOR_MOVE", "ANCHOR_STORE", "TEXT_INSERT", "TEXT_REMOVE", "TEXT_LINE", "TEXT_SET", "TEXT_FROM", "BYTES_FROM", "ANCHOR_COUNT", "LIST_COUNT", "LIST_APPEND", "LIST_INSERT", "LIST_REMOVE", "ITEM_GET", "ITEM_SET", "ROW", "PICK", "SLIDE", "FOLD", "TEXT_COMPARE", "LIST_FIND", "LIST_HAS", "NOW", "FLOOR", "MOD", "SEND", "OUTER_ROW", "EACH", "LOCAL_LOAD", "LOCAL_STORE", "I64_ADD", "I64_SUB", "I64_MUL", "I64_DIV", "I64_MOD", "I64_NEG", "I64_COMPARE", "I64_MIN", "I64_MAX", "I64_FROM", "NUM_FROM", "LOOP", "BREAK", "I64_BITS", "BYTE_AT", "BYTES_OF", "ANCHOR_AT", "BYTES_SLICE", "BYTE", "BYTES_LOAD", "BYTES_STORE", "LIST_VALUE", "LIST_BIND", "APPEND_IN", "NUM_PARSE", "CALL", "RETURN", "CHAR_AT", "CHAR", "FLOORDIV", "CUR_LOAD", "CUR_START", "CUR_END", "CUR_MOVE", "CUR_STORE", "CUR_COUNT", "CUR_AT", "INDEX_LOAD", "INDEX_STORE", "INDEX_MOVE", "INDEX_FIRST", "INDEX_LAST", "INDEX_NUM", "INDEX_AT", "KEPT_GET", "KEPT_SET", "KEPT_APPEND", "KEPT_INSERT", "KEPT_APPEND_IN"}; ++static void research_reads(const Frame *frame, const PureOp *op); ++static void research_dump(void) { ++ const char *out = getenv("PURE_OPS_OUT"); ++ FILE *f = out ? fopen(out, "w") : stderr; ++ for (unsigned i = 0; i < 256; ++i) ++ if (research_ops[i]) fprintf(f, "%s %llu %llu\n", i < sizeof(research_names) / sizeof(*research_names) ? research_names[i] : "?", ++ (unsigned long long)research_ops[i], (unsigned long long)research_same[i]); ++ if (out) fclose(f); ++} ++/* Reads the proof makes the same: the same list (its address and version: a change makes another), field and place ++ * read again within an event (the event's work starts again at 0). Counted by opcode. */ ++static uint64_t research_last_work, research_keys[1 << 16]; ++static uint32_t research_key_count; ++static void research_reads(const Frame *frame, const PureOp *op) { ++ if (frame->app->work < research_last_work) memset(research_keys, 0, sizeof(research_keys)), research_key_count = 0; ++ research_last_work = frame->app->work; ++ uint64_t list = 0, version = 0, place = 0, id = 0; ++ switch (op->op) { ++ case PURE_OP_ITEM_GET: case PURE_OP_INDEX_AT: case PURE_OP_LIST_COUNT: { ++ uint32_t state = op->op == PURE_OP_ITEM_GET ? (op->arg & 0xFFFF) : op->arg; ++ if (state >= frame->app->laid && state < PURE_LIST_HEARD) return; ++ const PureList *l = frame->app->lists[state]; ++ if (!l) return; ++ pure_list_stamp(l, &id, &version); ++ list = (uint64_t)(uintptr_t)l; ++ if (op->op != PURE_OP_LIST_COUNT) memcpy(&place, &frame->stack[frame->sp - 1], sizeof(place)); ++ break; ++ } ++ case PURE_OP_LIST_BIND: { ++ list = 0x51ull << 56 | op->arg; ++ memcpy(&place, &frame->stack[frame->sp - 1], sizeof(place)); ++ version = 0; ++ break; ++ } ++ default: return; ++ } ++ uint64_t key = ((list * 0x9E3779B97F4A7C15ull) ^ (version * 0xC2B2AE3D27D4EB4Full) ^ (place * 0x165667B19E3779F9ull) ^ ++ ((uint64_t)op->op << 32 | op->arg)) | 1; ++ for (uint32_t i = (uint32_t)(key >> 40) & 0xFFFF, k = 0; k < 1 << 16; ++k, i = (i + 1) & 0xFFFF) { ++ if (research_keys[i] == key) { ++research_same[op->op]; return; } ++ if (!research_keys[i]) { if (research_key_count < (1 << 15)) research_keys[i] = key, ++research_key_count; return; } ++ } ++} ++__attribute__((constructor)) static void research_start(void) { atexit(research_dump); } + static inline __attribute__((always_inline)) int step(Frame *frame, const PureOp *op, uint32_t pc, uint32_t *next, bool batches) { ++ ++research_ops[op->op]; ++ research_reads(frame, op); + const PureModule *m = frame->m; + PureValue *values = frame->values; + Event *ev = frame->ev; diff --git a/research/experiments/045-proof-compiler/stitch.c b/research/experiments/045-proof-compiler/stitch.c new file mode 100644 index 0000000..8d690e0 --- /dev/null +++ b/research/experiments/045-proof-compiler/stitch.c @@ -0,0 +1,108 @@ +/* Research 045 (029's principle 1, experiment (b)): the executor's own instruction bodies stitched without dispatch. + * Reads a module as Pure loads it and writes C for Pure's core to include (native.inc): the module's code as a + * constant array; a function for each basic block calling the executor's step() on each of its constant instructions, + * so the C compiler specializes each body to its instruction alone (no fetch, no decode, no dispatch within a block); + * and run_native, run_calls's loop dispatching once a block. Calls, returns and the ends of loops go through + * run_calls's own code. The semantics are the executor's source, unchanged. + * + * cc -O2 -std=c17 -I../../../core stitch.c ../../../build/libpure.a -lm -pthread -o stitch + * ./stitch MODULE > native.inc (then core/module.c built with -DPURE_NATIVE_INC='"native.inc"') */ +#include "module.h" +#include <inttypes.h> +#include <stdio.h> + +int main(int argc, char **argv) { + if (argc != 2) { fprintf(stderr, "usage: %s MODULE\n", argv[0]); return 2; } + PureModule m = {0}; + char error[160]; + if (pure_module_read(argv[1], &m, error, sizeof(error)) != PURE_OK) { fprintf(stderr, "%s\n", error); return 1; } + uint32_t n = m.code_count; + printf("/* Stitched from %s: %u instructions (research 045). */\n", argv[1], n); + printf("enum { NATIVE_COUNT = %u, STEP_ENDED = 9 }; /* STEP_ENDED: a block reached its end (frame.end) */\n", n); + printf("static const PureOp native_code[NATIVE_COUNT] = {\n"); + for (uint32_t pc = 0; pc < n; ++pc) { + const PureOp *o = &m.code[pc]; + printf(" {.integer = INT64_C(%" PRId64 "), .arg = %" PRIu32 "u, .op = %u, .plan = %u, .shape = %u, .range = %u},\n", + o->integer, o->arg, o->op, o->plan, o->shape, o->range); + } + printf("};\n\n"); + printf("static bool native_matches(const PureModule *m) {\n" + " if (m->code_count != NATIVE_COUNT) return false;\n" + " for (uint32_t pc = 0; pc < NATIVE_COUNT; ++pc)\n" + " if (m->code[pc].op != native_code[pc].op || m->code[pc].arg != native_code[pc].arg ||\n" + " m->code[pc].integer != native_code[pc].integer || m->code[pc].plan != native_code[pc].plan)\n" + " return false;\n" + " return true;\n" + "}\n\n"); + /* Basic blocks: a leader at each block's and function's start, each jump's target, past each instruction that may + * go elsewhere (a branch, a loop's, a call, a return), and every 16 instructions. Each is a function of its own (one + * enormous function took the compiler past 3 GiB): stitched within, dispatched once a block. */ + static bool leader[1 << 16]; + for (uint32_t h = 0; h < m.handlers; ++h) leader[m.handler[h].code.start] = true; + for (uint32_t f = 0; f < m.functions; ++f) leader[m.function[f].code.start] = true; + for (uint32_t pc = 0; pc < n; ++pc) { + uint8_t op = m.code[pc].op; + bool control = op == PURE_OP_JZ || op == PURE_OP_JMP || op == PURE_OP_LOOP || op == PURE_OP_EACH || op == PURE_OP_BREAK || + op == PURE_OP_CALL || op == PURE_OP_RETURN || op == PURE_OP_FOLD; + if ((op == PURE_OP_JZ || op == PURE_OP_JMP) && m.code[pc].arg < n) leader[m.code[pc].arg] = true; + if (control && pc + 1 < n) leader[pc + 1] = true; + } + leader[0] = true; + for (uint32_t pc = 0, run = 0; pc < n; ++pc, ++run) { + if (leader[pc]) run = 0; + else if (run == 16) leader[pc] = true, run = 0; + } + for (uint32_t pc = 0; pc < n;) { + uint32_t end = pc + 1; + while (end < n && !leader[end]) ++end; + printf("static __attribute__((noinline)) int native_%u(Frame *frame, uint32_t *pc) {\n int how;\n", pc); + for (uint32_t k = pc; k < end; ++k) { + printf(" if (%uu >= frame->end) { *pc = %uu; return STEP_ENDED; }\n", k, k); + printf(" if ((how = step(frame, &native_code[%u], %uu, pc, true)) != STEP_NEXT || *pc != %uu) return how;\n", k, k, k + 1); + } + printf(" return STEP_NEXT;\n}\n"); + pc = end; + } + printf("typedef int (*NativeBlock)(Frame *, uint32_t *);\n"); + printf("static const NativeBlock native_blocks[NATIVE_COUNT] = {\n"); + for (uint32_t pc = 0; pc < n; ++pc) if (leader[pc]) printf(" [%u] = native_%u,\n", pc, pc); + printf("};\n\n"); + printf("static __attribute__((noinline)) PureResult run_native(const PureModule *m, PureValue *values, PureBlock block, Event *ev,\n" + " Slot *result) {\n" + " Slot stack[PURE_MODULE_STACK];\n" + " Loop few[PURE_MODULE_NESTING], *loops = m->nesting > PURE_MODULE_NESTING ? deep_loops(ev->app, m->nesting) : few;\n" + " if (!loops) return PURE_ALLOCATION;\n" + " Frame frame;\n" + " open_frame(&frame, m, values, block, ev, stack, loops);\n" + " Call *top = NULL;\n" + " int how = STEP_NEXT;\n" + " for (uint32_t pc = block.start;;) {\n" + " if (pc >= frame.end) {\n" + " if (!frame.depth || (how = iterate(&frame, &pc)) != STEP_NEXT) break;\n" + " continue;\n" + " }\n" + " NativeBlock b = pc < NATIVE_COUNT ? native_blocks[pc] : NULL;\n" + " how = b ? b(&frame, &pc) : step(&frame, &m->code[pc], pc, &pc, true);\n" + " if (how == STEP_NEXT || how == STEP_ENDED) continue;\n" + " if (how != STEP_CALL && how != STEP_BACK && how != STEP_BATCH) break;\n" + " Frame apart = frame;\n" + " if (how == STEP_CALL) how = enter_call(&apart, &top, &pc);\n" + " else if (how == STEP_BACK) how = leave_call(&apart, &top, &pc);\n" + " else {\n" + " uint32_t past = 0;\n" + " how = open_batches(&apart, pc - 1, &past);\n" + " pc = past;\n" + " }\n" + " frame = apart;\n" + " if (how != STEP_NEXT) break;\n" + " }\n" + " if (top) {\n" + " Frame apart = frame;\n" + " unwind_calls(&apart, top);\n" + " frame = apart;\n" + " }\n" + " return finish(&frame, how, result);\n" + "}\n"); + pure_module_release(&m); + return 0; +} diff --git a/research/experiments/045-proof-compiler/unit.c b/research/experiments/045-proof-compiler/unit.c new file mode 100644 index 0000000..f85a4d9 --- /dev/null +++ b/research/experiments/045-proof-compiler/unit.c @@ -0,0 +1,47 @@ +/* Research 045: an operation's cost in machine instructions and cycles, from small apps (the apps in units): each takes + * message go { n: u32 } and does its operation n times; MESSAGES messages, counted (perf_event_open, user mode). + * + * cc -O2 -std=c17 -I../../../core unit.c ../../../build/libpure.a -lm -pthread -o unit + * ./unit MODULE N MESSAGES one JSON line: instructions and cycles an operation */ +#define _GNU_SOURCE +#include "module.h" +#include <linux/perf_event.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <sys/ioctl.h> +#include <sys/syscall.h> +#include <unistd.h> + +static int counter(uint64_t config) { + struct perf_event_attr a; + memset(&a, 0, sizeof(a)); + a.size = sizeof(a), a.type = PERF_TYPE_HARDWARE, a.config = config, a.disabled = 1, a.exclude_kernel = 1, a.exclude_hv = 1; + return (int)syscall(SYS_perf_event_open, &a, 0, -1, -1, 0); +} + +int main(int argc, char **argv) { + if (argc != 4) { fprintf(stderr, "usage: %s MODULE N MESSAGES\n", argv[0]); return 2; } + uint32_t n = (uint32_t)atoi(argv[2]); + int messages = atoi(argv[3]); + PureModule module = {0}; + char error[160]; + if (pure_module_read(argv[1], &module, error, sizeof(error)) != PURE_OK) { fprintf(stderr, "%s\n", error); return 1; } + PureApp app; + if (pure_app_start(&app, &module, (PureData){0}) != PURE_OK) return 1; + int go = pure_module_input(&module, "go"); + unsigned char payload[4]; + memcpy(payload, &n, 4); + if (pure_app_message(&app, (uint32_t)go, (PureSpan){payload, 4}) != PURE_OK) { fprintf(stderr, "failed\n"); return 1; } + int ins = counter(PERF_COUNT_HW_INSTRUCTIONS), cyc = counter(PERF_COUNT_HW_CPU_CYCLES); + ioctl(ins, PERF_EVENT_IOC_ENABLE, 0), ioctl(cyc, PERF_EVENT_IOC_ENABLE, 0); + for (int k = 0; k < messages; ++k) + if (pure_app_message(&app, (uint32_t)go, (PureSpan){payload, 4}) != PURE_OK) return 1; + ioctl(ins, PERF_EVENT_IOC_DISABLE, 0), ioctl(cyc, PERF_EVENT_IOC_DISABLE, 0); + uint64_t i = 0, c = 0; + if (read(ins, &i, 8) != 8 || read(cyc, &c, 8) != 8) return 1; + double ops = (double)n * messages; + printf("{\"n\":%u,\"messages\":%d,\"instructions_per_op\":%.1f,\"cycles_per_op\":%.1f}\n", n, messages, i / ops, c / ops); + pure_app_stop(&app); + return 0; +} diff --git a/research/experiments/045-proof-compiler/units/append.aup b/research/experiments/045-proof-compiler/units/append.aup new file mode 100644 index 0000000..def7fa5 --- /dev/null +++ b/research/experiments/045-proof-compiler/units/append.aup @@ -0,0 +1,7 @@ +state t = 0 +input go = message { n: u32 } +on go { + let xs: list of number + for i in 0 .. go.n { xs.append(i) } + t = xs.count +} diff --git a/research/experiments/045-proof-compiler/units/arith.aup b/research/experiments/045-proof-compiler/units/arith.aup new file mode 100644 index 0000000..76f48dc --- /dev/null +++ b/research/experiments/045-proof-compiler/units/arith.aup @@ -0,0 +1,7 @@ +state t = 0 +input go = message { n: u32 } +on go { + let s = 0 + for i in 0 .. go.n { s = s + i * 2 } + t = s +} diff --git a/research/experiments/045-proof-compiler/units/call.aup b/research/experiments/045-proof-compiler/units/call.aup new file mode 100644 index 0000000..ef31ef6 --- /dev/null +++ b/research/experiments/045-proof-compiler/units/call.aup @@ -0,0 +1,11 @@ +state t = 0 +input go = message { n: u32 } +fn f(x) { + if x > 1000000 { return 0 } + return x + 1 +} +on go { + let s = 0 + for i in 0 .. go.n { s = s + f(i) } + t = s +} diff --git a/research/experiments/045-proof-compiler/units/mod.aup b/research/experiments/045-proof-compiler/units/mod.aup new file mode 100644 index 0000000..dfb0f98 --- /dev/null +++ b/research/experiments/045-proof-compiler/units/mod.aup @@ -0,0 +1,7 @@ +state t = 0 +input go = message { n: u32 } +on go { + let s = 0 + for i in 0 .. go.n { s = s + i % 1000 } + t = s +} diff --git a/research/experiments/045-proof-compiler/units/read-direct.aup b/research/experiments/045-proof-compiler/units/read-direct.aup new file mode 100644 index 0000000..8609a5e --- /dev/null +++ b/research/experiments/045-proof-compiler/units/read-direct.aup @@ -0,0 +1,14 @@ +record R { + start = 0 +} +state ranges: list of R +state t = 0 +input go = message { n: u32 } +on go { + if ranges.count == 0 { + for i in 0 .. 1000 { ranges.append(R { start: i }) } + } + let s = 0 + for i in 0 .. go.n { s = s + ranges[i].start } + t = s +} diff --git a/research/experiments/045-proof-compiler/units/read.aup b/research/experiments/045-proof-compiler/units/read.aup new file mode 100644 index 0000000..34828e7 --- /dev/null +++ b/research/experiments/045-proof-compiler/units/read.aup @@ -0,0 +1,14 @@ +record R { + start = 0 +} +state ranges: list of R +state t = 0 +input go = message { n: u32 } +on go { + if ranges.count == 0 { + for i in 0 .. 1000 { ranges.append(R { start: i }) } + } + let s = 0 + for i in 0 .. go.n { s = s + ranges[i % 1000].start } + t = s +} diff --git a/research/experiments/045-proof-compiler/variants/v0-empty.patch b/research/experiments/045-proof-compiler/variants/v0-empty.patch new file mode 100644 index 0000000..de5b3fc --- /dev/null +++ b/research/experiments/045-proof-compiler/variants/v0-empty.patch @@ -0,0 +1,34 @@ +--- linebreak.aup ++++ v0-empty.aup +@@ -153,30 +153,6 @@ + } + + on line { +- let codes, cls, eff, start, nonspace, ri, at: list of number +- let joined, numeric: list of bool +- for p in line.points { +- let i = codes.count +- let r = range(p.code) +- let c = ranges[r].class +- let mark = c == CM || c == ZWJ +- let previous = if i > 0 { eff[i - 1] } else { SP } +- let joins = mark && i > 0 && !end(previous) && previous != SP && previous != ZW # LB9, LB10 +- let e = if joins { previous } else if mark { AL } else { c } +- codes.append(p.code) +- cls.append(c) +- at.append(r) +- joined.append(joins) +- eff.append(e) +- start.append(if joins { start[i - 1] } else { i }) +- nonspace.append(if e != SP { start[i] } else if i > 0 { nonspace[i - 1] } else { -1 }) +- numeric.append(if joins { numeric[i - 1] } else { e == NU || ((e == SY || e == IS) && i > 0 && numeric[i - 1]) }) +- ri.append(if joins { ri[i - 1] } else if e == RI { (if i > 0 { ri[i - 1] } else { 0 }) + 1 } else { 0 }) +- } +- let t = Text { codes: codes, cls: cls, eff: eff, joined: joined, start: start, nonspace: nonspace, numeric: numeric, ri: ri, +- at: at } +- let out: list of i64 = [0] # LB2 +- for i in 1 .. codes.count { out.append(i64(decide(t, i))) } +- if codes.count > 0 { out.append(2) } # LB3 ++ let out: list of i64 = [0] + breaks = bytes(out) + } diff --git a/research/experiments/045-proof-compiler/variants/v1-lists.patch b/research/experiments/045-proof-compiler/variants/v1-lists.patch new file mode 100644 index 0000000..6b73004 --- /dev/null +++ b/research/experiments/045-proof-compiler/variants/v1-lists.patch @@ -0,0 +1,14 @@ +--- linebreak.aup ++++ v1-lists.aup +@@ -173,10 +173,6 @@ + numeric.append(if joins { numeric[i - 1] } else { e == NU || ((e == SY || e == IS) && i > 0 && numeric[i - 1]) }) + ri.append(if joins { ri[i - 1] } else if e == RI { (if i > 0 { ri[i - 1] } else { 0 }) + 1 } else { 0 }) + } +- let t = Text { codes: codes, cls: cls, eff: eff, joined: joined, start: start, nonspace: nonspace, numeric: numeric, ri: ri, +- at: at } +- let out: list of i64 = [0] # LB2 +- for i in 1 .. codes.count { out.append(i64(decide(t, i))) } +- if codes.count > 0 { out.append(2) } # LB3 ++ let out: list of i64 = [0] + breaks = bytes(out) + } diff --git a/research/experiments/045-proof-compiler/variants/v2-text.patch b/research/experiments/045-proof-compiler/variants/v2-text.patch new file mode 100644 index 0000000..2539f0c --- /dev/null +++ b/research/experiments/045-proof-compiler/variants/v2-text.patch @@ -0,0 +1,12 @@ +--- linebreak.aup ++++ v2-text.aup +@@ -175,8 +175,6 @@ + } + let t = Text { codes: codes, cls: cls, eff: eff, joined: joined, start: start, nonspace: nonspace, numeric: numeric, ri: ri, + at: at } +- let out: list of i64 = [0] # LB2 +- for i in 1 .. codes.count { out.append(i64(decide(t, i))) } +- if codes.count > 0 { out.append(2) } # LB3 ++ let out: list of i64 = [0] + breaks = bytes(out) + } |