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 --- research/experiments/045-proof-compiler/where.py | 148 +++++++++++++++++++++++ 1 file changed, 148 insertions(+) create mode 100644 research/experiments/045-proof-compiler/where.py (limited to 'research/experiments/045-proof-compiler/where.py') 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