Debian Codegraph @

Tools/cases_generator/opcode_metadata_generator.py

raw
1 """Generate opcode metadata.
2 Reads the instruction definitions from bytecodes.c.
3 Writes the metadata to pycore_opcode_metadata.h by default.
4 """
5
6 import argparse
7
8 from analyzer import (
9 Analysis,
10 Instruction,
11 PseudoInstruction,
12 analyze_files,
13 Uop,
14 )
15 from generators_common import (
16 DEFAULT_INPUT,
17 ROOT,
18 write_header,
19 cflags,
20 )
21 from cwriter import CWriter
22 from dataclasses import dataclass
23 from typing import TextIO
24 from stack import get_stack_effect
25
26 # Constants used instead of size for macro expansions.
27 # Note: 1, 2, 4 must match actual cache entry sizes.
28 OPARG_KINDS = {
29 "OPARG_SIMPLE": 0,
30 "OPARG_CACHE_1": 1,
31 "OPARG_CACHE_2": 2,
32 "OPARG_CACHE_4": 4,
33 "OPARG_TOP": 5,
34 "OPARG_BOTTOM": 6,
35 "OPARG_SAVE_RETURN_OFFSET": 7,
36 # Skip 8 as the other powers of 2 are sizes
37 "OPARG_REPLACED": 9,
38 "OPERAND1_1": 10,
39 "OPERAND1_2": 11,
40 "OPERAND1_4": 12,
41 }
42
43 FLAGS = [
44 "ARG",
45 "CONST",
46 "NAME",
47 "JUMP",
48 "FREE",
49 "LOCAL",
50 "EVAL_BREAK",
51 "DEOPT",
52 "ERROR",
53 "ESCAPES",
54 "EXIT",
55 "PURE",
56 "PASSTHROUGH",
57 "OPARG_AND_1",
58 "ERROR_NO_POP",
59 "NO_SAVE_IP",
60 ]
61
62
63 def generate_flag_macros(out: CWriter) -> None:
64 for i, flag in enumerate(FLAGS):
65 out.emit(f"#define HAS_{flag}_FLAG ({1<<i})\n")
66 for i, flag in enumerate(FLAGS):
67 out.emit(
68 f"#define OPCODE_HAS_{flag}(OP) (_PyOpcode_opcode_metadata[OP].flags & (HAS_{flag}_FLAG))\n"
69 )
70 out.emit("\n")
71
72
73 def generate_oparg_macros(out: CWriter) -> None:
74 for name, value in OPARG_KINDS.items():
75 out.emit(f"#define {name} {value}\n")
76 out.emit("\n")
77
78
79 def emit_stack_effect_function(
80 out: CWriter, direction: str, data: list[tuple[str, str]]
81 ) -> None:
82 out.emit(f"extern int _PyOpcode_num_{direction}(int opcode, int oparg);\n")
83 out.emit("#ifdef NEED_OPCODE_METADATA\n")
84 out.emit(f"int _PyOpcode_num_{direction}(int opcode, int oparg) {{\n")
85 out.emit("switch(opcode) {\n")
86 for name, effect in data:
87 out.emit(f"case {name}:\n")
88 out.emit(f" return {effect};\n")
89 out.emit("default:\n")
90 out.emit(" return -1;\n")
91 out.emit("}\n")
92 out.emit("}\n\n")
93 out.emit("#endif\n\n")
94
95
96 def generate_stack_effect_functions(analysis: Analysis, out: CWriter) -> None:
97 popped_data: list[tuple[str, str]] = []
98 pushed_data: list[tuple[str, str]] = []
99
100 def add(inst: Instruction | PseudoInstruction) -> None:
101 stack = get_stack_effect(inst)
102 popped = (-stack.base_offset).to_c()
103 pushed = (stack.logical_sp - stack.base_offset).to_c()
104 popped_data.append((inst.name, popped))
105 pushed_data.append((inst.name, pushed))
106
107 for inst in analysis.instructions.values():
108 add(inst)
109 for pseudo in analysis.pseudos.values():
110 add(pseudo)
111
112 emit_stack_effect_function(out, "popped", sorted(popped_data))
113 emit_stack_effect_function(out, "pushed", sorted(pushed_data))
114
115
116 def generate_is_pseudo(analysis: Analysis, out: CWriter) -> None:
117 """Write the IS_PSEUDO_INSTR macro"""
118 out.emit("\n\n#define IS_PSEUDO_INSTR(OP) ( \\\n")
119 for op in analysis.pseudos:
120 out.emit(f"((OP) == {op}) || \\\n")
121 out.emit("0")
122 out.emit(")\n\n")
123
124
125 def get_format(inst: Instruction) -> str:
126 if inst.properties.oparg:
127 format = "INSTR_FMT_IB"
128 else:
129 format = "INSTR_FMT_IX"
130 if inst.size > 1:
131 format += "C"
132 format += "0" * (inst.size - 2)
133 return format
134
135
136 def generate_instruction_formats(analysis: Analysis, out: CWriter) -> None:
137 # Compute the set of all instruction formats.
138 formats: set[str] = set()
139 for inst in analysis.instructions.values():
140 formats.add(get_format(inst))
141 # Generate an enum for it
142 out.emit("enum InstructionFormat {\n")
143 next_id = 1
144 for format in sorted(formats):
145 out.emit(f"{format} = {next_id},\n")
146 next_id += 1
147 out.emit("};\n\n")
148
149
150 def generate_deopt_table(analysis: Analysis, out: CWriter) -> None:
151 out.emit("extern const uint8_t _PyOpcode_Deopt[256];\n")
152 out.emit("#ifdef NEED_OPCODE_METADATA\n")
153 out.emit("const uint8_t _PyOpcode_Deopt[256] = {\n")
154 deopts: list[tuple[str, str]] = []
155 for inst in analysis.instructions.values():
156 deopt = inst.name
157 if inst.family is not None:
158 deopt = inst.family.name
159 deopts.append((inst.name, deopt))
160 defined = set(analysis.opmap.values())
161 for i in range(256):
162 if i not in defined:
163 deopts.append((f'{i}', f'{i}'))
164
165 assert len(deopts) == 256
166 assert len(set(x[0] for x in deopts)) == 256
167 for name, deopt in sorted(deopts):
168 out.emit(f"[{name}] = {deopt},\n")
169 out.emit("};\n\n")
170 out.emit("#endif // NEED_OPCODE_METADATA\n\n")
171
172
173 def generate_cache_table(analysis: Analysis, out: CWriter) -> None:
174 out.emit("extern const uint8_t _PyOpcode_Caches[256];\n")
175 out.emit("#ifdef NEED_OPCODE_METADATA\n")
176 out.emit("const uint8_t _PyOpcode_Caches[256] = {\n")
177 for inst in analysis.instructions.values():
178 if inst.family and inst.family.name != inst.name:
179 continue
180 if inst.name.startswith("INSTRUMENTED"):
181 continue
182 if inst.size > 1:
183 out.emit(f"[{inst.name}] = {inst.size-1},\n")
184 out.emit("};\n")
185 out.emit("#endif\n\n")
186
187
188 def generate_name_table(analysis: Analysis, out: CWriter) -> None:
189 table_size = 256 + len(analysis.pseudos)
190 out.emit(f"extern const char *_PyOpcode_OpName[{table_size}];\n")
191 out.emit("#ifdef NEED_OPCODE_METADATA\n")
192 out.emit(f"const char *_PyOpcode_OpName[{table_size}] = {{\n")
193 names = list(analysis.instructions) + list(analysis.pseudos)
194 for name in sorted(names):
195 out.emit(f'[{name}] = "{name}",\n')
196 out.emit("};\n")
197 out.emit("#endif\n\n")
198
199
200 def generate_metadata_table(analysis: Analysis, out: CWriter) -> None:
201 table_size = 256 + len(analysis.pseudos)
202 out.emit("struct opcode_metadata {\n")
203 out.emit("uint8_t valid_entry;\n")
204 out.emit("uint8_t instr_format;\n")
205 out.emit("uint16_t flags;\n")
206 out.emit("};\n\n")
207 out.emit(
208 f"extern const struct opcode_metadata _PyOpcode_opcode_metadata[{table_size}];\n"
209 )
210 out.emit("#ifdef NEED_OPCODE_METADATA\n")
211 out.emit(
212 f"const struct opcode_metadata _PyOpcode_opcode_metadata[{table_size}] = {{\n"
213 )
214 for inst in sorted(analysis.instructions.values(), key=lambda t: t.name):
215 out.emit(
216 f"[{inst.name}] = {{ true, {get_format(inst)}, {cflags(inst.properties)} }},\n"
217 )
218 for pseudo in sorted(analysis.pseudos.values(), key=lambda t: t.name):
219 flags = cflags(pseudo.properties)
220 for flag in pseudo.flags:
221 if flags == "0":
222 flags = f"{flag}_FLAG"
223 else:
224 flags += f" | {flag}_FLAG"
225 out.emit(f"[{pseudo.name}] = {{ true, -1, {flags} }},\n")
226 out.emit("};\n")
227 out.emit("#endif\n\n")
228
229
230 def generate_expansion_table(analysis: Analysis, out: CWriter) -> None:
231 expansions_table: dict[str, list[tuple[str, str, int]]] = {}
232 for inst in sorted(analysis.instructions.values(), key=lambda t: t.name):
233 offset: int = 0 # Cache effect offset
234 expansions: list[tuple[str, str, int]] = [] # [(name, size, offset), ...]
235 if inst.is_super():
236 pieces = inst.name.split("_")
237 assert len(pieces) % 2 == 0, f"{inst.name} doesn't look like a super-instr"
238 parts_per_piece = int(len(pieces) / 2)
239 name1 = "_".join(pieces[:parts_per_piece])
240 name2 = "_".join(pieces[parts_per_piece:])
241 assert name1 in analysis.instructions, f"{name1} doesn't match any instr"
242 assert name2 in analysis.instructions, f"{name2} doesn't match any instr"
243 instr1 = analysis.instructions[name1]
244 instr2 = analysis.instructions[name2]
245 assert (
246 len(instr1.parts) == 1
247 ), f"{name1} is not a good superinstruction part"
248 assert (
249 len(instr2.parts) == 1
250 ), f"{name2} is not a good superinstruction part"
251 expansions.append((instr1.parts[0].name, "OPARG_TOP", 0))
252 expansions.append((instr2.parts[0].name, "OPARG_BOTTOM", 0))
253 elif not is_viable_expansion(inst):
254 continue
255 else:
256 for part in inst.parts:
257 size = part.size
258 if isinstance(part, Uop):
259 # Skip specializations
260 if "specializing" in part.annotations:
261 continue
262 # Add the primary expansion.
263 fmt = "OPARG_SIMPLE"
264 if part.name == "_SAVE_RETURN_OFFSET":
265 fmt = "OPARG_SAVE_RETURN_OFFSET"
266 elif part.caches:
267 fmt = str(part.caches[0].size)
268 if "replaced" in part.annotations:
269 fmt = "OPARG_REPLACED"
270 expansions.append((part.name, fmt, offset))
271 if len(part.caches) > 1:
272 # Add expansion for the second operand
273 internal_offset = 0
274 for cache in part.caches[:-1]:
275 internal_offset += cache.size
276 expansions.append((part.name, f"OPERAND1_{part.caches[-1].size}", offset+internal_offset))
277 offset += part.size
278 expansions_table[inst.name] = expansions
279 max_uops = max(len(ex) for ex in expansions_table.values())
280 out.emit(f"#define MAX_UOP_PER_EXPANSION {max_uops}\n")
281 out.emit("struct opcode_macro_expansion {\n")
282 out.emit("int nuops;\n")
283 out.emit(
284 "struct { int16_t uop; int8_t size; int8_t offset; } uops[MAX_UOP_PER_EXPANSION];\n"
285 )
286 out.emit("};\n")
287 out.emit(
288 "extern const struct opcode_macro_expansion _PyOpcode_macro_expansion[256];\n\n"
289 )
290 out.emit("#ifdef NEED_OPCODE_METADATA\n")
291 out.emit("const struct opcode_macro_expansion\n")
292 out.emit("_PyOpcode_macro_expansion[256] = {\n")
293 for inst_name, expansions in expansions_table.items():
294 uops = [
295 f"{{ {name}, {size}, {offset} }}" for (name, size, offset) in expansions
296 ]
297 out.emit(
298 f'[{inst_name}] = {{ .nuops = {len(expansions)}, .uops = {{ {", ".join(uops)} }} }},\n'
299 )
300 out.emit("};\n")
301 out.emit("#endif // NEED_OPCODE_METADATA\n\n")
302
303
304 def is_viable_expansion(inst: Instruction) -> bool:
305 "An instruction can be expanded if all its parts are viable for tier 2"
306 for part in inst.parts:
307 if isinstance(part, Uop):
308 # Skip specializing and replaced uops
309 if "specializing" in part.annotations:
310 continue
311 if "replaced" in part.annotations:
312 continue
313 if part.properties.tier == 1 or not part.is_viable():
314 return False
315 return True
316
317
318 def generate_extra_cases(analysis: Analysis, out: CWriter) -> None:
319 out.emit("#define EXTRA_CASES \\\n")
320 valid_opcodes = set(analysis.opmap.values())
321 for op in range(256):
322 if op not in valid_opcodes:
323 out.emit(f" case {op}: \\\n")
324 out.emit(" ;\n")
325
326
327 def generate_pseudo_targets(analysis: Analysis, out: CWriter) -> None:
328 table_size = len(analysis.pseudos)
329 max_targets = max(len(pseudo.targets) for pseudo in analysis.pseudos.values())
330 out.emit("struct pseudo_targets {\n")
331 out.emit(f"uint8_t as_sequence;\n")
332 out.emit(f"uint8_t targets[{max_targets + 1}];\n")
333 out.emit("};\n")
334 out.emit(
335 f"extern const struct pseudo_targets _PyOpcode_PseudoTargets[{table_size}];\n"
336 )
337 out.emit("#ifdef NEED_OPCODE_METADATA\n")
338 out.emit(
339 f"const struct pseudo_targets _PyOpcode_PseudoTargets[{table_size}] = {{\n"
340 )
341 for pseudo in analysis.pseudos.values():
342 as_sequence = "1" if pseudo.as_sequence else "0"
343 targets = ["0"] * (max_targets + 1)
344 for i, target in enumerate(pseudo.targets):
345 targets[i] = target.name
346 out.emit(f"[{pseudo.name}-256] = {{ {as_sequence}, {{ {', '.join(targets)} }} }},\n")
347 out.emit("};\n\n")
348 out.emit("#endif // NEED_OPCODE_METADATA\n")
349 out.emit("static inline bool\n")
350 out.emit("is_pseudo_target(int pseudo, int target) {\n")
351 out.emit(f"if (pseudo < 256 || pseudo >= {256+table_size}) {{\n")
352 out.emit(f"return false;\n")
353 out.emit("}\n")
354 out.emit(
355 f"for (int i = 0; _PyOpcode_PseudoTargets[pseudo-256].targets[i]; i++) {{\n"
356 )
357 out.emit(
358 f"if (_PyOpcode_PseudoTargets[pseudo-256].targets[i] == target) return true;\n"
359 )
360 out.emit("}\n")
361 out.emit(f"return false;\n")
362 out.emit("}\n\n")
363
364
365 def generate_opcode_metadata(
366 filenames: list[str], analysis: Analysis, outfile: TextIO
367 ) -> None:
368 write_header(__file__, filenames, outfile)
369 out = CWriter(outfile, 0, False)
370 with out.header_guard("Py_CORE_OPCODE_METADATA_H"):
371 out.emit("#ifndef Py_BUILD_CORE\n")
372 out.emit('# error "this header requires Py_BUILD_CORE define"\n')
373 out.emit("#endif\n\n")
374 out.emit("#include <stdbool.h> // bool\n")
375 out.emit('#include "opcode_ids.h"\n')
376 generate_is_pseudo(analysis, out)
377 out.emit('#include "pycore_uop_ids.h"\n')
378 generate_stack_effect_functions(analysis, out)
379 generate_instruction_formats(analysis, out)
380 table_size = 256 + len(analysis.pseudos)
381 out.emit("#define IS_VALID_OPCODE(OP) \\\n")
382 out.emit(f" (((OP) >= 0) && ((OP) < {table_size}) && \\\n")
383 out.emit(" (_PyOpcode_opcode_metadata[(OP)].valid_entry))\n\n")
384 generate_flag_macros(out)
385 generate_oparg_macros(out)
386 generate_metadata_table(analysis, out)
387 generate_expansion_table(analysis, out)
388 generate_name_table(analysis, out)
389 generate_cache_table(analysis, out)
390 generate_deopt_table(analysis, out)
391 generate_extra_cases(analysis, out)
392 generate_pseudo_targets(analysis, out)
393
394
395 arg_parser = argparse.ArgumentParser(
396 description="Generate the header file with opcode metadata.",
397 formatter_class=argparse.ArgumentDefaultsHelpFormatter,
398 )
399
400
401 DEFAULT_OUTPUT = ROOT / "Include/internal/pycore_opcode_metadata.h"
402
403
404 arg_parser.add_argument(
405 "-o", "--output", type=str, help="Generated code", default=DEFAULT_OUTPUT
406 )
407
408 arg_parser.add_argument(
409 "input", nargs=argparse.REMAINDER, help="Instruction definition file(s)"
410 )
411
412 if __name__ == "__main__":
413 args = arg_parser.parse_args()
414 if len(args.input) == 0:
415 args.input.append(DEFAULT_INPUT)
416 data = analyze_files(args.input)
417 with open(args.output, "w") as outfile:
418 generate_opcode_metadata(args.input, data, outfile)