From bbe04c13e58f884d25a933b785b052558c66118b Mon Sep 17 00:00:00 2001 From: eunhhu Date: Mon, 19 Oct 2026 12:06:33 +0100 Subject: 045: where the machine instructions go, by mechanism (where.c samples the address every 100,003 user instructions from perf_event_open's ring, the answers checked first; where.py names each by addr2line's inlined chain: the step() case its line is in, or the function outside): the app's 40,236 a code point are dispatch 30.6% (the switch and run_calls' loop), lists built 17.3%, numbers 13.5%, lists read 13.0%, moves 9.0%, calls 7.1%, malloc 4.0%; no mechanism near most; range()'s binary search alone 14,489 a point (36%, variant v0r): 11.4 rounds of about 1,270, of which floor division with fmod 186 and a stored read 240 --- .../045-proof-compiler/2026-10-19-break.jsonl | 3 + .../045-proof-compiler/2026-10-19-where-app.txt | 101 ++++++++++++++ .../045-proof-compiler/2026-10-19-where-range.txt | 95 +++++++++++++ .../045-proof-compiler/variants/v0r-range.patch | 36 +++++ research/experiments/045-proof-compiler/where.c | 131 ++++++++++++++++++ research/experiments/045-proof-compiler/where.py | 148 +++++++++++++++++++++ 6 files changed, 514 insertions(+) create mode 100644 research/experiments/045-proof-compiler/2026-10-19-where-app.txt create mode 100644 research/experiments/045-proof-compiler/2026-10-19-where-range.txt create mode 100644 research/experiments/045-proof-compiler/variants/v0r-range.patch create mode 100644 research/experiments/045-proof-compiler/where.c create mode 100644 research/experiments/045-proof-compiler/where.py diff --git a/research/experiments/045-proof-compiler/2026-10-19-break.jsonl b/research/experiments/045-proof-compiler/2026-10-19-break.jsonl index 07aef0d..f70a825 100644 --- a/research/experiments/045-proof-compiler/2026-10-19-break.jsonl +++ b/research/experiments/045-proof-compiler/2026-10-19-break.jsonl @@ -8,3 +8,6 @@ {"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} +{"what": "variant v0r: the empty handler and range(p.code) a point (events.c, PURE_JIT=0)", "empty_handler": 1562.6, "range_only": 16051.7, "lists_built": 24211.2, "range_per_point": 14489.1, "range_iterations_per_point": 11.4} +{"what": "mechanisms, the app (where.c and where.py: 246,581 samples every 100,003 user instructions, 10 rounds, answers checked)", "machine_instructions_per_point": 40236, "dispatch": 12298, "list_build": 6953, "compute": 5416, "list_read": 5238, "moves": 3601, "call": 2847, "memory": 1609, "unplaced": 1213, "event": 947, "loop": 113} +{"what": "mechanisms, variant v0r (range only)", "machine_instructions_per_point": 16089, "dispatch": 6038, "compute": 3697, "list_read": 2729, "moves": 1521, "unplaced": 713, "list_build": 451, "call": 360, "memory": 247, "event": 190, "loop": 144, "floor_divide_and_fmod": 2121} diff --git a/research/experiments/045-proof-compiler/2026-10-19-where-app.txt b/research/experiments/045-proof-compiler/2026-10-19-where-app.txt new file mode 100644 index 0000000..c94e9cd --- /dev/null +++ b/research/experiments/045-proof-compiler/2026-10-19-where-app.txt @@ -0,0 +1,101 @@ +40,236 machine instructions a code point, 246,581 samples + +by mechanism: + 12,298 30.6% dispatch + 6,953 17.3% list build + 5,416 13.5% compute + 5,238 13.0% list read + 3,601 9.0% moves + 2,847 7.1% call + 1,609 4.0% memory + 1,213 3.0% unknown + 947 2.4% event + 113 0.3% loop + +in step(), by the case its line is in (code the compiler shares between cases goes to one of them): + 9,445 (fetch, decode) + 2,295 LIST_APPEND + 2,030 LOCAL_LOAD + 1,152 ARITH + 869 CONST + 725 INDEX_AT + 706 FLOORDIV + 678 JZ + 545 LOCAL_STORE + 399 ITEM_GET + 393 NE + 350 LIST_FIND + 316 JMP + 208 LIST_BIND + 205 BYTES_OF + 171 NOT + 153 SUB + 144 TEXT_INSERT + 95 LIST_VALUE + 94 PICK + 80 LIST_COUNT + 78 LOOP + 63 SLIDE + 61 MOD + 28 CALL + 24 BREAK + 19 ROW + 18 AND + 9 EACH + 5 I64_FROM + 4 OR + 3 BYTES_SLICE + +outside step(), by function as linked: + 2,853 run_calls + 2,615 pure_list_get + 1,581 enter_call + 1,150 pure_list_insert + 971 restore_lists + 884 floor_divide + 865 pure_list_clear + 726 fmodf64 + 678 arrays_free + 488 states_next + 457 free + 435 arrays_fit + 356 pure_list_changes + 318 ?? + 310 __xpg_strerror_r + 295 message + 270 calloc + 255 pure_list_settle + 238 clear_rows + 227 __default_morecore + 206 pure_list_free + 199 __aarch64_ldadd8_relax + 187 pure_list_new + 183 pure_list_count + 172 close_burst + 160 mark_event + 147 pure_list_copied + 141 malloc + 122 reserve + 112 open_burst + +no mechanism: + 270 ?? (where:0) < ?? + 87 states_count (module.c:4749) < call_keeps + 69 pure_list_extra (module-list.c:1790) < pure_list_extra + 62 pure_list_size (module-list.c:2284) < pure_list_size + 55 pure_undo_size (module-list.c:3054) < pure_undo_size + 49 decode_cell (module-list.c:2132) < decode_cell + 48 ?? (??:0) < ?? + 39 prepare_extras (module-list.c:625) < prepare_extras + 30 decode_item (module-list.c:2344) < pure_list_read + 16 place (module-list.c:729) < place + 14 move_items (module-list.c:337) < place + 14 pure_app_save (module.c:5121) < pure_app_save + 13 grows (module.c:2451) < grows + 13 place (module-list.c:689) < place + 12 decode_cell (module-list.c:2130) < decode_cell + 11 leaf_bytes (store-tree.c:453) < leaf_bytes + 10 retire (module-list.c:370) < let_go_tree + 10 pure_app_checkpoint (module-save.c:725) < pure_app_checkpoint + 10 pure_app_checkpoint (module-save.c:727) < pure_app_checkpoint + 9 move_items (module-list.c:336) < place diff --git a/research/experiments/045-proof-compiler/2026-10-19-where-range.txt b/research/experiments/045-proof-compiler/2026-10-19-where-range.txt new file mode 100644 index 0000000..97d6e20 --- /dev/null +++ b/research/experiments/045-proof-compiler/2026-10-19-where-range.txt @@ -0,0 +1,95 @@ +16,089 machine instructions a code point, 98,601 samples + +by mechanism: + 6,038 37.5% dispatch + 3,697 23.0% compute + 2,729 17.0% list read + 1,521 9.5% moves + 713 4.4% unknown + 451 2.8% list build + 360 2.2% call + 247 1.5% memory + 190 1.2% event + 144 0.9% loop + +in step(), by the case its line is in (code the compiler shares between cases goes to one of them): + 4,478 (fetch, decode) + 1,002 LOCAL_LOAD + 723 ARITH + 514 FLOORDIV + 285 CONST + 277 INDEX_AT + 234 LOCAL_STORE + 189 JZ + 163 ITEM_GET + 160 NE + 145 NOT + 141 LIST_FIND + 122 SUB + 115 JMP + 78 MOD + 72 LOOP + 70 LIST_APPEND + 52 BREAK + 35 TEXT_INSERT + 26 BYTES_OF + 21 CALL + 17 EACH + 17 LIST_COUNT + 8 I64_FROM + 6 ROW + 0 BYTE_AT + +outside step(), by function as linked: + 2,064 pure_list_get + 1,560 run_calls + 891 floor_divide + 716 fmodf64 + 201 enter_call + 134 ?? + 122 arrays_free + 101 free + 99 pure_list_insert + 89 place + 71 message + 64 decode_cell + 55 pure_list_count + 55 pure_list_read + 54 clear_rows + 51 malloc + 47 __default_morecore + 46 prepare_extras + 44 leave_call + 42 restore_lists + 40 __xpg_strerror_r + 36 open_burst + 34 call_keeps + 30 pure_list_clear + 29 chunk_bytes + 27 pure_list_settle + 26 give_back + 25 collect + 24 timer_settime + 23 close_burst + +no mechanism: + 95 ?? (where:0) < ?? + 43 prepare_extras (module-list.c:625) < prepare_extras + 39 decode_cell (module-list.c:2132) < decode_cell + 39 ?? (??:0) < ?? + 32 states_count (module.c:4749) < call_keeps + 24 decode_item (module-list.c:2344) < pure_list_read + 16 move_items (module-list.c:337) < place + 13 place (module-list.c:689) < place + 12 place (module-list.c:729) < place + 12 sum_path (module-list.c:591) < sum_path + 11 pure_list_read (module-list.c:2358) < pure_list_read + 10 leaf_bytes (store-tree.c:453) < leaf_bytes + 9 take (store-tree.c:602) < chunk_bytes + 9 own (module-list.c:552) < own + 9 sum (module-list.c:521) < sum + 8 own (module-list.c:563) < own + 8 pure_draft_size (store-tree.c:1530) < pure_draft_size + 8 decode_cell (module-list.c:2130) < decode_cell + 8 pure_list_read (module-list.c:2352) < pure_list_read + 7 pure_app_checkpoint (module-save.c:725) < pure_app_checkpoint diff --git a/research/experiments/045-proof-compiler/variants/v0r-range.patch b/research/experiments/045-proof-compiler/variants/v0r-range.patch new file mode 100644 index 0000000..79b0636 --- /dev/null +++ b/research/experiments/045-proof-compiler/variants/v0r-range.patch @@ -0,0 +1,36 @@ +--- linebreak.aup ++++ v0r-range.aup +@@ -153,30 +153,8 @@ + } + + 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 s = 0 ++ for p in line.points { s = s + range(p.code) } ++ let out: list of i64 = [i64(s % 2)] + breaks = bytes(out) + } diff --git a/research/experiments/045-proof-compiler/where.c b/research/experiments/045-proof-compiler/where.c new file mode 100644 index 0000000..0764443 --- /dev/null +++ b/research/experiments/045-proof-compiler/where.c @@ -0,0 +1,131 @@ +/* Research 045: where Pure's machine instructions go on UAX #14, by mechanism. The app (aup's examples/linebreak.aup) + * on the lines 044's linebreak_check.py writes, its answers checked first; then ROUNDS passes with a user-mode + * instruction counter sampling its address every PERIOD instructions (perf_event_open, PERF_SAMPLE_IP, read from its + * ring after each line). Built without PIE, so where.py can give the addresses to addr2line as they are. + * + * cc -O2 -g -no-pie -std=c17 -I../../../core -I../../../../vega/text where.c ../../../../vega/text/linebreak.c \ + * ../../../../vega/text/unicode-data.c ../../../build/libpure.a -lm -pthread -o where + * ./where MODULE RANGES LINES ROUNDS PERIOD > samples.txt "instructions N points N" then "ADDRESS COUNT" lines, + * the maps on stderr + * WHERE_VARIANT=1: a variant (events.c's), whose answers are not the test's. */ +#define _GNU_SOURCE +#include "module.h" +#include "text.h" +#include +#include +#include +#include +#include +#include +#include +#include + +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; + +/* Addresses sampled, counted in an open table. */ +enum { SLOTS = 1 << 20, PAGES = 64 }; +static uint64_t address[SLOTS], hits[SLOTS]; + +static void count_address(uint64_t ip) { + for (uint64_t k = (ip * 0x9E3779B97F4A7C15u) >> 44;; k = (k + 1) & (SLOTS - 1)) { + if (address[k] == ip) { ++hits[k]; return; } + if (!address[k]) { address[k] = ip, hits[k] = 1; return; } + } +} + +/* The samples the ring holds: a header and the address each (PERF_SAMPLE_IP); lost records skipped. */ +static void drain(struct perf_event_mmap_page *head, size_t data_size) { + uint64_t end = __atomic_load_n(&head->data_head, __ATOMIC_ACQUIRE), at = head->data_tail; + const unsigned char *data = (const unsigned char *)head + head->data_offset; + while (at < end) { + struct perf_event_header h; + for (size_t i = 0; i < sizeof(h); ++i) ((unsigned char *)&h)[i] = data[(at + i) % data_size]; + if (h.type == PERF_RECORD_SAMPLE) { + uint64_t ip; + for (size_t i = 0; i < sizeof(ip); ++i) ((unsigned char *)&ip)[i] = data[(at + sizeof(h) + i) % data_size]; + count_address(ip); + } + at += h.size; + } + __atomic_store_n(&head->data_tail, at, __ATOMIC_RELEASE); +} + +int main(int argc, char **argv) { + if (argc != 6) { fprintf(stderr, "usage: %s MODULE RANGES LINES ROUNDS PERIOD\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]); + uint64_t period = strtoull(argv[5], NULL, 10); + 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: Pure gives 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 && !getenv("WHERE_VARIANT")) { fprintf(stderr, "right %zu of %zu\n", right, count); return 1; } + struct perf_event_attr a; + memset(&a, 0, sizeof(a)); + a.size = sizeof(a), a.type = PERF_TYPE_HARDWARE, a.config = PERF_COUNT_HW_INSTRUCTIONS, a.disabled = 1, + a.exclude_kernel = 1, a.exclude_hv = 1, a.sample_period = period, a.sample_type = PERF_SAMPLE_IP; + int fd = (int)syscall(SYS_perf_event_open, &a, 0, -1, -1, 0); + if (fd < 0) { perror("perf_event_open"); return 1; } + size_t page = (size_t)sysconf(_SC_PAGESIZE), data_size = PAGES * page; + struct perf_event_mmap_page *head = mmap(NULL, page + data_size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0); + if (head == MAP_FAILED) { perror("mmap"); return 1; } + ioctl(fd, PERF_EVENT_IOC_RESET, 0); + for (int r = 0; r < rounds; ++r) + for (size_t k = 0; k < count; ++k) { + ioctl(fd, PERF_EVENT_IOC_ENABLE, 0); + PureResult did = pure_app_message(&app, (uint32_t)line, (PureSpan){lines[k].payload, 8 * (size_t)lines[k].count}); + ioctl(fd, PERF_EVENT_IOC_DISABLE, 0); + if (did != PURE_OK) return 1; + drain(head, data_size); + } + uint64_t total = 0; + if (read(fd, &total, sizeof(total)) != sizeof(total)) return 1; + printf("instructions %llu points %llu\n", (unsigned long long)total, (unsigned long long)points * (unsigned long long)rounds); + for (size_t k = 0; k < SLOTS; ++k) + if (address[k]) printf("%llx %llu\n", (unsigned long long)address[k], (unsigned long long)hits[k]); + FILE *maps = fopen("/proc/self/maps", "r"); /* to stderr: where the shared libraries were (libc's malloc, memcpy) */ + for (int c; maps && (c = fgetc(maps)) != EOF;) fputc(c, stderr); + if (maps) fclose(maps); + pure_app_stop(&app); + return 0; +} diff --git a/research/experiments/045-proof-compiler/where.py b/research/experiments/045-proof-compiler/where.py new file mode 100644 index 0000000..74463cf --- /dev/null +++ b/research/experiments/045-proof-compiler/where.py @@ -0,0 +1,148 @@ +#!/usr/bin/env python3 +"""Research 045: where.c's samples by mechanism. Each sampled address is given to addr2line (-i: the functions inlined +there, innermost first). A sample whose chain passes through the executor's step() is the instruction whose case +holds that line (core/module.c, the case labels read from the source); one outside it is its function, named by the +binary's symbols or, in a shared library, by the library's (the maps where.c writes). Instructions go to mechanisms +(OPS and FUNCTIONS below). + +where.py BINARY SAMPLES MAPS SOURCE tables: machine instructions a code point""" +import bisect +import collections +import re +import subprocess +import sys + +# What each instruction's body does, for the mechanisms; an instruction not named is 'compute'. +OPS = { + 'dispatch': {'(fetch, decode)'}, + 'moves': {'CONST', 'LOAD', 'STORE', 'LOCAL_LOAD', 'LOCAL_STORE', 'PICK', 'SLIDE'}, + 'list read': {'ITEM_GET', 'INDEX_AT', 'LIST_COUNT', 'ROW', 'FIELD', 'LEN', 'LIST_FIND', 'LIST_HAS', 'OUTER_ROW', + 'KEPT_GET', 'INDEX_LOAD', 'INDEX_NUM', 'INDEX_FIRST', 'INDEX_LAST'}, + 'list build': {'LIST_APPEND', 'LIST_VALUE', 'LIST_BIND', 'APPEND_IN', 'LIST_INSERT', 'LIST_REMOVE', 'ITEM_SET', + 'KEPT_SET', 'KEPT_APPEND', 'KEPT_INSERT', 'KEPT_APPEND_IN', 'BYTES_OF', 'BYTES_FROM'}, + 'call': {'CALL', 'RETURN'}, + 'loop': {'LOOP', 'BREAK', 'EACH', 'FOLD'}, +} +# Functions outside step() (not inlined into it), by mechanism; matched on the name before any '.' suffix. +FUNCTIONS = { + 'list read': {'pure_list_get', 'leaf_of', 'child', 'child_at', 'cell_in', 'array_cell', 'pure_list_count', + 'pure_states_has', 'cell_out', 'width_of'}, + 'list build': {'pure_list_insert', 'flat_insert', 'pure_list_new', 'pure_list_clear', 'arrays_free', 'arrays_fit', + 'pure_list_changes', 'pure_list_settle', 'pure_list_free', 'clear_rows', 'pure_list_copied', + 'pure_list_append', 'pure_list_set'}, + 'call': {'enter_call', 'leave_call', 'states_next', 'restore_lists', 'give_back', 'unbind', 'kept_apart', + 'frame_room', 'unwind_calls', 'list_held'}, + 'loop': {'iterate', 'charge', 'enter_loop', 'enter_each', 'leave_loop'}, + 'event': {'message', 'close_burst', 'mark_event', 'pure_app_message', 'open_frame', 'finish', 'run', 'open_burst', + 'reserve', 'nest', 'timer_settime'}, + 'compute': {'floor_divide', 'floor', 'fmod', 'fmodf64', 'copysign'}, + 'memory': {'malloc', 'free', 'calloc', 'realloc', 'memset', 'memcpy', 'memmove', '_int_malloc', '_int_free', + 'cfree', 'malloc_consolidate', '__aarch64_ldadd8_relax', '__aarch64_cas8_acq_rel', + '__xpg_strerror_r', '__default_morecore'}, # nm's nearest names for malloc's own (static) functions in libc +} + + +def cases(source): + """Line ranges of step()'s cases: [(first line, instruction)], sorted; lines before the first case are dispatch.""" + lines = open(source).read().splitlines() + start = next(i for i, l in enumerate(lines) if re.match(r'static .*\bint step\(Frame \*frame', l)) + 1 + end = next(i for i in range(start, len(lines)) if lines[i] == '}') + 1 + marks = [(start, '(fetch, decode)')] + second = False + for n in range(start, end + 1): + l = lines[n - 1] + found = re.findall(r'case PURE_OP_(\w+)', l) + if found: + marks.append((n, found[0])) + elif re.match(r'\s+default: break;', l): + second = True + elif second and re.match(r'\s+double b = stack\[--sp\]\.num', l): + marks.append((n, 'ARITH')) # the second switch: the numbers' binary instructions + second = False + return start, end, marks + + +def resolve(binary, addresses, maps): + """{address: [(function, file, line)] innermost first}.""" + regions = [] + for l in open(maps): + part = l.split() + if len(part) >= 6 and 'x' in part[1] and part[5].startswith('/'): + lo, hi = (int(x, 16) for x in part[0].split('-')) + regions.append((lo, hi, int(part[2], 16), part[5])) + out = subprocess.run(['addr2line', '-a', '-f', '-i', '-e', binary], input='\n'.join(addresses) + '\n', + capture_output=True, text=True, check=True).stdout.splitlines() + result, current = {}, None + for line in out: + if re.fullmatch(r'0x[0-9a-f]+', line): + current = int(line, 16) + result[current] = [] + else: + result[current].append(line) + chain = {} + symbols = {} + for a, l in result.items(): + pairs = [(l[i].split('.')[0], *(l[i + 1].split(' ')[0].rsplit(':', 1) + ['0'])[:2]) for i in range(0, len(l) - 1, 2)] + if pairs and pairs[0][0] != '??': + chain[a] = [(f, p.split('/')[-1], int(n) if n.isdigit() else 0) for f, p, n in pairs] + continue + region = next((r for r in regions if r[0] <= a < r[1]), None) + if not region: + chain[a] = [('??', '??', 0)] + continue + lo, _, offset, path = region + if path not in symbols: + listed = subprocess.run(['nm', '-D', '--defined-only', path], capture_output=True, text=True).stdout.split('\n') + table = sorted((int(p[0], 16), p[2]) for p in (x.split() for x in listed) if len(p) == 3 and p[1] in 'TtWi') + symbols[path] = ([t[0] for t in table], [t[1] for t in table]) + at, names = symbols[path] + k = bisect.bisect_right(at, a - lo + offset) - 1 + chain[a] = [(names[k].split('@')[0] if k >= 0 else '??', path.split('/')[-1], 0)] + return chain + + +def main(): + binary, samples, maps, source = sys.argv[1:5] + with open(samples) as f: + head = f.readline().split() + total, points = int(head[1]), int(head[3]) + counts = {int(a, 16): int(n) for a, n in (l.split() for l in f)} + start, end, marks = cases(source) + firsts = [m[0] for m in marks] + chains = resolve(binary, [hex(a) for a in counts], maps) + n = sum(counts.values()) + scale = total / points / n + by_op, by_function, mechanism, rest = (collections.Counter() for _ in range(4)) + for a, c in counts.items(): + chain = chains[a] + at = next((x for x in chain if x[0] == 'step' and x[1] == 'module.c' and start <= x[2] <= end), None) + if at: + op = marks[bisect.bisect_right(firsts, at[2]) - 1][1] + by_op[op] += c + mechanism[next((k for k, v in OPS.items() if op in v), 'compute')] += c + continue + name = chain[-1][0] # the function as linked: what an outside call shows + inner = chain[0][0] + by_function[name] += c + kind = 'dispatch' if name == 'run_calls' else next((k for k, v in FUNCTIONS.items() if inner in v or name in v), None) + mechanism[kind or 'unknown'] += c + if not kind: + rest[f'{inner} ({chain[0][1]}:{chain[0][2]}) < {name}'] += c + print(f'{total / points:,.0f} machine instructions a code point, {n:,} samples') + print('\nby mechanism:') + for k, c in mechanism.most_common(): + print(f' {c * scale:8,.0f} {100 * c / n:5.1f}% {k}') + print('\nin step(), by the case its line is in (code the compiler shares between cases goes to one of them):') + for op, c in by_op.most_common(40): + print(f' {c * scale:8,.0f} {op}') + print('\noutside step(), by function as linked:') + for name, c in by_function.most_common(30): + print(f' {c * scale:8,.0f} {name}') + if rest: + print('\nno mechanism:') + for name, c in rest.most_common(20): + print(f' {c * scale:8,.0f} {name}') + + +if __name__ == '__main__': + main() -- cgit v1.2.3