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

1 files changed, 148 insertions, 0 deletions

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()