1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
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()
|
