diff options
author | Mark Shannon <mark@hotpy.org> | 2023-12-20 14:27:25 (GMT) |
---|---|---|
committer | GitHub <noreply@github.com> | 2023-12-20 14:27:25 (GMT) |
commit | e96f26083bff31e86c068aa22542e91f38293ea3 (patch) | |
tree | 3b351f4fc54eff3c08caf811edbcd7c9fcb40c5d /Tools/cases_generator | |
parent | a545a86ec64fbab325db101bdd8964f524a89790 (diff) | |
download | cpython-e96f26083bff31e86c068aa22542e91f38293ea3.zip cpython-e96f26083bff31e86c068aa22542e91f38293ea3.tar.gz cpython-e96f26083bff31e86c068aa22542e91f38293ea3.tar.bz2 |
GH-111485: Generate instruction and uop metadata (GH-113287)
Diffstat (limited to 'Tools/cases_generator')
-rw-r--r-- | Tools/cases_generator/analyzer.py | 162 | ||||
-rw-r--r-- | Tools/cases_generator/cwriter.py | 35 | ||||
-rw-r--r-- | Tools/cases_generator/generate_cases.py | 1 | ||||
-rw-r--r-- | Tools/cases_generator/generators_common.py | 45 | ||||
-rw-r--r-- | Tools/cases_generator/opcode_id_generator.py | 112 | ||||
-rw-r--r-- | Tools/cases_generator/opcode_metadata_generator.py | 386 | ||||
-rw-r--r-- | Tools/cases_generator/py_metadata_generator.py | 97 | ||||
-rw-r--r-- | Tools/cases_generator/stack.py | 40 | ||||
-rw-r--r-- | Tools/cases_generator/tier1_generator.py | 1 | ||||
-rw-r--r-- | Tools/cases_generator/tier2_generator.py | 11 | ||||
-rw-r--r-- | Tools/cases_generator/uop_id_generator.py | 60 | ||||
-rw-r--r-- | Tools/cases_generator/uop_metadata_generator.py | 73 |
12 files changed, 849 insertions, 174 deletions
diff --git a/Tools/cases_generator/analyzer.py b/Tools/cases_generator/analyzer.py index e077eb0..d7aca50 100644 --- a/Tools/cases_generator/analyzer.py +++ b/Tools/cases_generator/analyzer.py @@ -11,11 +11,16 @@ class Properties: deopts: bool oparg: bool jumps: bool + eval_breaker: bool ends_with_eval_breaker: bool needs_this: bool always_exits: bool stores_sp: bool tier_one_only: bool + uses_co_consts: bool + uses_co_names: bool + uses_locals: bool + has_free: bool def dump(self, indent: str) -> None: print(indent, end="") @@ -30,11 +35,16 @@ class Properties: deopts=any(p.deopts for p in properties), oparg=any(p.oparg for p in properties), jumps=any(p.jumps for p in properties), + eval_breaker=any(p.eval_breaker for p in properties), ends_with_eval_breaker=any(p.ends_with_eval_breaker for p in properties), needs_this=any(p.needs_this for p in properties), always_exits=any(p.always_exits for p in properties), stores_sp=any(p.stores_sp for p in properties), tier_one_only=any(p.tier_one_only for p in properties), + uses_co_consts=any(p.uses_co_consts for p in properties), + uses_co_names=any(p.uses_co_names for p in properties), + uses_locals=any(p.uses_locals for p in properties), + has_free=any(p.has_free for p in properties), ) @@ -44,11 +54,16 @@ SKIP_PROPERTIES = Properties( deopts=False, oparg=False, jumps=False, + eval_breaker=False, ends_with_eval_breaker=False, needs_this=False, always_exits=False, stores_sp=False, tier_one_only=False, + uses_co_consts=False, + uses_co_names=False, + uses_locals=False, + has_free=False, ) @@ -142,6 +157,12 @@ class Uop: return False return True + def is_super(self) -> bool: + for tkn in self.body: + if tkn.kind == "IDENTIFIER" and tkn.text == "oparg1": + return True + return False + Part = Uop | Skip @@ -153,6 +174,7 @@ class Instruction: _properties: Properties | None is_target: bool = False family: Optional["Family"] = None + opcode: int = -1 @property def properties(self) -> Properties: @@ -171,16 +193,30 @@ class Instruction: def size(self) -> int: return 1 + sum(part.size for part in self.parts) + def is_super(self) -> bool: + if len(self.parts) != 1: + return False + uop = self.parts[0] + if isinstance(uop, Uop): + return uop.is_super() + else: + return False + @dataclass class PseudoInstruction: name: str targets: list[Instruction] flags: list[str] + opcode: int = -1 def dump(self, indent: str) -> None: print(indent, self.name, "->", " or ".join([t.name for t in self.targets])) + @property + def properties(self) -> Properties: + return Properties.from_list([i.properties for i in self.targets]) + @dataclass class Family: @@ -198,12 +234,15 @@ class Analysis: uops: dict[str, Uop] families: dict[str, Family] pseudos: dict[str, PseudoInstruction] + opmap: dict[str, int] + have_arg: int + min_instrumented: int def analysis_error(message: str, tkn: lexer.Token) -> SyntaxError: # To do -- support file and line output # Construct a SyntaxError instance from message and token - return lexer.make_syntax_error(message, "", tkn.line, tkn.column, "") + return lexer.make_syntax_error(message, tkn.filename, tkn.line, tkn.column, "") def override_error( @@ -238,6 +277,11 @@ def analyze_caches(inputs: list[parser.InputEffect]) -> list[CacheEntry]: caches: list[parser.CacheEffect] = [ i for i in inputs if isinstance(i, parser.CacheEffect) ] + for cache in caches: + if cache.name == "unused": + raise analysis_error( + "Unused cache entry in op. Move to enclosing macro.", cache.tokens[0] + ) return [CacheEntry(i.name, int(i.size)) for i in caches] @@ -300,17 +344,28 @@ def always_exits(op: parser.InstDef) -> bool: def compute_properties(op: parser.InstDef) -> Properties: + has_free = ( + variable_used(op, "PyCell_New") + or variable_used(op, "PyCell_GET") + or variable_used(op, "PyCell_SET") + ) return Properties( escapes=makes_escaping_api_call(op), infallible=is_infallible(op), deopts=variable_used(op, "DEOPT_IF"), oparg=variable_used(op, "oparg"), jumps=variable_used(op, "JUMPBY"), + eval_breaker=variable_used(op, "CHECK_EVAL_BREAKER"), ends_with_eval_breaker=eval_breaker_at_end(op), needs_this=variable_used(op, "this_instr"), always_exits=always_exits(op), stores_sp=variable_used(op, "STORE_SP"), tier_one_only=variable_used(op, "TIER_ONE_ONLY"), + uses_co_consts=variable_used(op, "FRAME_CO_CONSTS"), + uses_co_names=variable_used(op, "FRAME_CO_NAMES"), + uses_locals=(variable_used(op, "GETLOCAL") or variable_used(op, "SETLOCAL")) + and not has_free, + has_free=has_free, ) @@ -417,6 +472,95 @@ def add_pseudo( ) +def assign_opcodes( + instructions: dict[str, Instruction], + families: dict[str, Family], + pseudos: dict[str, PseudoInstruction], +) -> tuple[dict[str, int], int, int]: + """Assigns opcodes, then returns the opmap, + have_arg and min_instrumented values""" + instmap: dict[str, int] = {} + + # 0 is reserved for cache entries. This helps debugging. + instmap["CACHE"] = 0 + + # 17 is reserved as it is the initial value for the specializing counter. + # This helps catch cases where we attempt to execute a cache. + instmap["RESERVED"] = 17 + + # 149 is RESUME - it is hard coded as such in Tools/build/deepfreeze.py + instmap["RESUME"] = 149 + + # This is an historical oddity. + instmap["BINARY_OP_INPLACE_ADD_UNICODE"] = 3 + + instmap["INSTRUMENTED_LINE"] = 254 + + instrumented = [name for name in instructions if name.startswith("INSTRUMENTED")] + + # Special case: this instruction is implemented in ceval.c + # rather than bytecodes.c, so we need to add it explicitly + # here (at least until we add something to bytecodes.c to + # declare external instructions). + instrumented.append("INSTRUMENTED_LINE") + + specialized: set[str] = set() + no_arg: list[str] = [] + has_arg: list[str] = [] + + for family in families.values(): + specialized.update(inst.name for inst in family.members) + + for inst in instructions.values(): + name = inst.name + if name in specialized: + continue + if name in instrumented: + continue + if inst.properties.oparg: + has_arg.append(name) + else: + no_arg.append(name) + + # Specialized ops appear in their own section + # Instrumented opcodes are at the end of the valid range + min_internal = 150 + min_instrumented = 254 - (len(instrumented) - 1) + assert min_internal + len(specialized) < min_instrumented + + next_opcode = 1 + + def add_instruction(name: str) -> None: + nonlocal next_opcode + if name in instmap: + return # Pre-defined name + while next_opcode in instmap.values(): + next_opcode += 1 + instmap[name] = next_opcode + next_opcode += 1 + + for name in sorted(no_arg): + add_instruction(name) + for name in sorted(has_arg): + add_instruction(name) + # For compatibility + next_opcode = min_internal + for name in sorted(specialized): + add_instruction(name) + next_opcode = min_instrumented + for name in instrumented: + add_instruction(name) + + for name in instructions: + instructions[name].opcode = instmap[name] + + for op, name in enumerate(sorted(pseudos), 256): + instmap[name] = op + pseudos[name].opcode = op + + return instmap, len(no_arg), min_instrumented + + def analyze_forest(forest: list[parser.AstNode]) -> Analysis: instructions: dict[str, Instruction] = {} uops: dict[str, Uop] = {} @@ -460,10 +604,20 @@ def analyze_forest(forest: list[parser.AstNode]) -> Analysis: continue if target.text in instructions: instructions[target.text].is_target = True - # Hack + # Special case BINARY_OP_INPLACE_ADD_UNICODE + # BINARY_OP_INPLACE_ADD_UNICODE is not a normal family member, + # as it is the wrong size, but we need it to maintain an + # historical optimization. if "BINARY_OP_INPLACE_ADD_UNICODE" in instructions: - instructions["BINARY_OP_INPLACE_ADD_UNICODE"].family = families["BINARY_OP"] - return Analysis(instructions, uops, families, pseudos) + inst = instructions["BINARY_OP_INPLACE_ADD_UNICODE"] + inst.family = families["BINARY_OP"] + families["BINARY_OP"].members.append(inst) + opmap, first_arg, min_instrumented = assign_opcodes( + instructions, families, pseudos + ) + return Analysis( + instructions, uops, families, pseudos, opmap, first_arg, min_instrumented + ) def analyze_files(filenames: list[str]) -> Analysis: diff --git a/Tools/cases_generator/cwriter.py b/Tools/cases_generator/cwriter.py index 67b1c9a..069f017 100644 --- a/Tools/cases_generator/cwriter.py +++ b/Tools/cases_generator/cwriter.py @@ -1,5 +1,6 @@ +import contextlib from lexer import Token -from typing import TextIO +from typing import TextIO, Iterator class CWriter: @@ -44,9 +45,12 @@ class CWriter: def maybe_indent(self, txt: str) -> None: parens = txt.count("(") - txt.count(")") - if parens > 0 and self.last_token: - offset = self.last_token.end_column - 1 - if offset <= self.indents[-1] or offset > 40: + if parens > 0: + if self.last_token: + offset = self.last_token.end_column - 1 + if offset <= self.indents[-1] or offset > 40: + offset = self.indents[-1] + 4 + else: offset = self.indents[-1] + 4 self.indents.append(offset) if is_label(txt): @@ -54,6 +58,7 @@ class CWriter: else: braces = txt.count("{") - txt.count("}") if braces > 0: + assert braces == 1 if 'extern "C"' in txt: self.indents.append(self.indents[-1]) else: @@ -114,6 +119,28 @@ class CWriter: self.newline = True self.last_token = None + @contextlib.contextmanager + def header_guard(self, name: str) -> Iterator[None]: + self.out.write( + f""" +#ifndef {name} +#define {name} +#ifdef __cplusplus +extern "C" {{ +#endif + +""" + ) + yield + self.out.write( + f""" +#ifdef __cplusplus +}} +#endif +#endif /* !{name} */ +""" + ) + def is_label(txt: str) -> bool: return not txt.startswith("//") and txt.endswith(":") diff --git a/Tools/cases_generator/generate_cases.py b/Tools/cases_generator/generate_cases.py index 50bc14a..bb027f3 100644 --- a/Tools/cases_generator/generate_cases.py +++ b/Tools/cases_generator/generate_cases.py @@ -840,7 +840,6 @@ def main() -> None: a.assign_opcode_ids() a.write_opcode_targets(args.opcode_targets_h) - a.write_metadata(args.metadata, args.pymetadata) a.write_abstract_interpreter_instructions( args.abstract_interpreter_cases, args.emit_line_directives ) diff --git a/Tools/cases_generator/generators_common.py b/Tools/cases_generator/generators_common.py index 1b565bf..5a42a05 100644 --- a/Tools/cases_generator/generators_common.py +++ b/Tools/cases_generator/generators_common.py @@ -2,14 +2,11 @@ from pathlib import Path from typing import TextIO from analyzer import ( - Analysis, Instruction, Uop, - Part, analyze_files, + Properties, Skip, - StackItem, - analysis_error, ) from cwriter import CWriter from typing import Callable, Mapping, TextIO, Iterator @@ -25,14 +22,16 @@ def root_relative_path(filename: str) -> str: try: return Path(filename).absolute().relative_to(ROOT).as_posix() except ValueError: + # Not relative to root, just return original path. return filename -def write_header(generator: str, sources: list[str], outfile: TextIO) -> None: + +def write_header(generator: str, sources: list[str], outfile: TextIO, comment: str = "//") -> None: outfile.write( - f"""// This file is generated by {root_relative_path(generator)} -// from: -// {", ".join(root_relative_path(src) for src in sources)} -// Do not edit! + f"""{comment} This file is generated by {root_relative_path(generator)} +{comment} from: +{comment} {", ".join(root_relative_path(src) for src in sources)} +{comment} Do not edit! """ ) @@ -186,3 +185,31 @@ def emit_tokens( replacement_functions[tkn.text](out, tkn, tkn_iter, uop, stack, inst) else: out.emit(tkn) + + +def cflags(p: Properties) -> str: + flags: list[str] = [] + if p.oparg: + flags.append("HAS_ARG_FLAG") + if p.uses_co_consts: + flags.append("HAS_CONST_FLAG") + if p.uses_co_names: + flags.append("HAS_NAME_FLAG") + if p.jumps: + flags.append("HAS_JUMP_FLAG") + if p.has_free: + flags.append("HAS_FREE_FLAG") + if p.uses_locals: + flags.append("HAS_LOCAL_FLAG") + if p.eval_breaker: + flags.append("HAS_EVAL_BREAK_FLAG") + if p.deopts: + flags.append("HAS_DEOPT_FLAG") + if not p.infallible: + flags.append("HAS_ERROR_FLAG") + if p.escapes: + flags.append("HAS_ESCAPES_FLAG") + if flags: + return " | ".join(flags) + else: + return "0" diff --git a/Tools/cases_generator/opcode_id_generator.py b/Tools/cases_generator/opcode_id_generator.py index ddbb409..dbea3d0 100644 --- a/Tools/cases_generator/opcode_id_generator.py +++ b/Tools/cases_generator/opcode_id_generator.py @@ -24,111 +24,23 @@ from typing import TextIO DEFAULT_OUTPUT = ROOT / "Include/opcode_ids.h" -def generate_opcode_header(filenames: list[str], analysis: Analysis, outfile: TextIO) -> None: +def generate_opcode_header( + filenames: list[str], analysis: Analysis, outfile: TextIO +) -> None: write_header(__file__, filenames, outfile) out = CWriter(outfile, 0, False) - out.emit("\n") - instmap: dict[str, int] = {} + with out.header_guard("Py_OPCODE_IDS_H"): + out.emit("/* Instruction opcodes for compiled code */\n") - # 0 is reserved for cache entries. This helps debugging. - instmap["CACHE"] = 0 + def write_define(name: str, op: int) -> None: + out.emit(f"#define {name:<38} {op:>3}\n") - # 17 is reserved as it is the initial value for the specializing counter. - # This helps catch cases where we attempt to execute a cache. - instmap["RESERVED"] = 17 + for op, name in sorted([(op, name) for (name, op) in analysis.opmap.items()]): + write_define(name, op) - # 149 is RESUME - it is hard coded as such in Tools/build/deepfreeze.py - instmap["RESUME"] = 149 - instmap["INSTRUMENTED_LINE"] = 254 - - instrumented = [ - name for name in analysis.instructions if name.startswith("INSTRUMENTED") - ] - - # Special case: this instruction is implemented in ceval.c - # rather than bytecodes.c, so we need to add it explicitly - # here (at least until we add something to bytecodes.c to - # declare external instructions). - instrumented.append("INSTRUMENTED_LINE") - - specialized: set[str] = set() - no_arg: list[str] = [] - has_arg: list[str] = [] - - for family in analysis.families.values(): - specialized.update(inst.name for inst in family.members) - - for inst in analysis.instructions.values(): - name = inst.name - if name in specialized: - continue - if name in instrumented: - continue - if inst.properties.oparg: - has_arg.append(name) - else: - no_arg.append(name) - - # Specialized ops appear in their own section - # Instrumented opcodes are at the end of the valid range - min_internal = 150 - min_instrumented = 254 - (len(instrumented) - 1) - assert min_internal + len(specialized) < min_instrumented - - next_opcode = 1 - - def add_instruction(name: str) -> None: - nonlocal next_opcode - if name in instmap: - return # Pre-defined name - while next_opcode in instmap.values(): - next_opcode += 1 - instmap[name] = next_opcode - next_opcode += 1 - - for name in sorted(no_arg): - add_instruction(name) - for name in sorted(has_arg): - add_instruction(name) - # For compatibility - next_opcode = min_internal - for name in sorted(specialized): - add_instruction(name) - next_opcode = min_instrumented - for name in instrumented: - add_instruction(name) - - for op, name in enumerate(sorted(analysis.pseudos), 256): - instmap[name] = op - - assert 255 not in instmap.values() - - out.emit( - """#ifndef Py_OPCODE_IDS_H -#define Py_OPCODE_IDS_H -#ifdef __cplusplus -extern "C" { -#endif - -/* Instruction opcodes for compiled code */ -""" - ) - - def write_define(name: str, op: int) -> None: - out.emit(f"#define {name:<38} {op:>3}\n") - - for op, name in sorted([(op, name) for (name, op) in instmap.items()]): - write_define(name, op) - - out.emit("\n") - write_define("HAVE_ARGUMENT", len(no_arg)) - write_define("MIN_INSTRUMENTED_OPCODE", min_instrumented) - - out.emit("\n") - out.emit("#ifdef __cplusplus\n") - out.emit("}\n") - out.emit("#endif\n") - out.emit("#endif /* !Py_OPCODE_IDS_H */\n") + out.emit("\n") + write_define("HAVE_ARGUMENT", analysis.have_arg) + write_define("MIN_INSTRUMENTED_OPCODE", analysis.min_instrumented) arg_parser = argparse.ArgumentParser( diff --git a/Tools/cases_generator/opcode_metadata_generator.py b/Tools/cases_generator/opcode_metadata_generator.py new file mode 100644 index 0000000..427bb54 --- /dev/null +++ b/Tools/cases_generator/opcode_metadata_generator.py @@ -0,0 +1,386 @@ +"""Generate uop metedata. +Reads the instruction definitions from bytecodes.c. +Writes the metadata to pycore_uop_metadata.h by default. +""" + +import argparse +import os.path +import sys + +from analyzer import ( + Analysis, + Instruction, + analyze_files, + Skip, + Uop, +) +from generators_common import ( + DEFAULT_INPUT, + ROOT, + write_header, + cflags, + StackOffset, +) +from cwriter import CWriter +from typing import TextIO +from stack import get_stack_effect + +# Constants used instead of size for macro expansions. +# Note: 1, 2, 4 must match actual cache entry sizes. +OPARG_KINDS = { + "OPARG_FULL": 0, + "OPARG_CACHE_1": 1, + "OPARG_CACHE_2": 2, + "OPARG_CACHE_4": 4, + "OPARG_TOP": 5, + "OPARG_BOTTOM": 6, + "OPARG_SAVE_RETURN_OFFSET": 7, + # Skip 8 as the other powers of 2 are sizes + "OPARG_REPLACED": 9, +} + +FLAGS = [ + "ARG", + "CONST", + "NAME", + "JUMP", + "FREE", + "LOCAL", + "EVAL_BREAK", + "DEOPT", + "ERROR", + "ESCAPES", +] + + +def generate_flag_macros(out: CWriter) -> None: + for i, flag in enumerate(FLAGS): + out.emit(f"#define HAS_{flag}_FLAG ({1<<i})\n") + for i, flag in enumerate(FLAGS): + out.emit( + f"#define OPCODE_HAS_{flag}(OP) (_PyOpcode_opcode_metadata[OP].flags & (HAS_{flag}_FLAG))\n" + ) + out.emit("\n") + + +def generate_oparg_macros(out: CWriter) -> None: + for name, value in OPARG_KINDS.items(): + out.emit(f"#define {name} {value}\n") + out.emit("\n") + + +def emit_stack_effect_function( + out: CWriter, direction: str, data: list[tuple[str, str]] +) -> None: + out.emit(f"extern int _PyOpcode_num_{direction}(int opcode, int oparg);\n") + out.emit("#ifdef NEED_OPCODE_METADATA\n") + out.emit(f"int _PyOpcode_num_{direction}(int opcode, int oparg) {{\n") + out.emit("switch(opcode) {\n") + for name, effect in data: + out.emit(f"case {name}:\n") + out.emit(f" return {effect};\n") + out.emit("default:\n") + out.emit(" return -1;\n") + out.emit("}\n") + out.emit("}\n\n") + out.emit("#endif\n\n") + + +def generate_stack_effect_functions(analysis: Analysis, out: CWriter) -> None: + popped_data: list[tuple[str, str]] = [] + pushed_data: list[tuple[str, str]] = [] + for inst in analysis.instructions.values(): + stack = get_stack_effect(inst) + popped = (-stack.base_offset).to_c() + pushed = (stack.top_offset - stack.base_offset).to_c() + popped_data.append((inst.name, popped)) + pushed_data.append((inst.name, pushed)) + emit_stack_effect_function(out, "popped", sorted(popped_data)) + emit_stack_effect_function(out, "pushed", sorted(pushed_data)) + + +def generate_is_pseudo(analysis: Analysis, out: CWriter) -> None: + """Write the IS_PSEUDO_INSTR macro""" + out.emit("\n\n#define IS_PSEUDO_INSTR(OP) ( \\\n") + for op in analysis.pseudos: + out.emit(f"((OP) == {op}) || \\\n") + out.emit("0") + out.emit(")\n\n") + + +def get_format(inst: Instruction) -> str: + if inst.properties.oparg: + format = "INSTR_FMT_IB" + else: + format = "INSTR_FMT_IX" + if inst.size > 1: + format += "C" + format += "0" * (inst.size - 2) + return format + + +def generate_instruction_formats(analysis: Analysis, out: CWriter) -> None: + # Compute the set of all instruction formats. + formats: set[str] = set() + for inst in analysis.instructions.values(): + formats.add(get_format(inst)) + # Generate an enum for it + out.emit("enum InstructionFormat {\n") + next_id = 1 + for format in sorted(formats): + out.emit(f"{format} = {next_id},\n") + next_id += 1 + out.emit("};\n\n") + + +def generate_deopt_table(analysis: Analysis, out: CWriter) -> None: + out.emit("extern const uint8_t _PyOpcode_Deopt[256];\n") + out.emit("#ifdef NEED_OPCODE_METADATA\n") + out.emit("const uint8_t _PyOpcode_Deopt[256] = {\n") + deopts: list[tuple[str, str]] = [] + for inst in analysis.instructions.values(): + deopt = inst.name + if inst.family is not None: + deopt = inst.family.name + deopts.append((inst.name, deopt)) + deopts.append(("INSTRUMENTED_LINE", "INSTRUMENTED_LINE")) + for name, deopt in sorted(deopts): + out.emit(f"[{name}] = {deopt},\n") + out.emit("};\n\n") + out.emit("#endif // NEED_OPCODE_METADATA\n\n") + + +def generate_cache_table(analysis: Analysis, out: CWriter) -> None: + out.emit("extern const uint8_t _PyOpcode_Caches[256];\n") + out.emit("#ifdef NEED_OPCODE_METADATA\n") + out.emit("const uint8_t _PyOpcode_Caches[256] = {\n") + for inst in analysis.instructions.values(): + if inst.family and inst.family.name != inst.name: + continue + if inst.name.startswith("INSTRUMENTED"): + continue + if inst.size > 1: + out.emit(f"[{inst.name}] = {inst.size-1},\n") + out.emit("};\n") + out.emit("#endif\n\n") + + +def generate_name_table(analysis: Analysis, out: CWriter) -> None: + table_size = 256 + len(analysis.pseudos) + out.emit(f"extern const char *_PyOpcode_OpName[{table_size}];\n") + out.emit("#ifdef NEED_OPCODE_METADATA\n") + out.emit(f"const char *_PyOpcode_OpName[{table_size}] = {{\n") + names = list(analysis.instructions) + list(analysis.pseudos) + names.append("INSTRUMENTED_LINE") + for name in sorted(names): + out.emit(f'[{name}] = "{name}",\n') + out.emit("};\n") + out.emit("#endif\n\n") + + +def generate_metadata_table(analysis: Analysis, out: CWriter) -> None: + table_size = 256 + len(analysis.pseudos) + out.emit("struct opcode_metadata {\n") + out.emit("uint8_t valid_entry;\n") + out.emit("int8_t instr_format;\n") + out.emit("int16_t flags;\n") + out.emit("};\n\n") + out.emit( + f"extern const struct opcode_metadata _PyOpcode_opcode_metadata[{table_size}];\n" + ) + out.emit("#ifdef NEED_OPCODE_METADATA\n") + out.emit( + f"const struct opcode_metadata _PyOpcode_opcode_metadata[{table_size}] = {{\n" + ) + for inst in sorted(analysis.instructions.values(), key=lambda t: t.name): + out.emit( + f"[{inst.name}] = {{ true, {get_format(inst)}, {cflags(inst.properties)} }},\n" + ) + for pseudo in sorted(analysis.pseudos.values(), key=lambda t: t.name): + flags = cflags(pseudo.properties) + for flag in pseudo.flags: + if flags == "0": + flags = f"{flag}_FLAG" + else: + flags += f" | {flag}_FLAG" + out.emit(f"[{pseudo.name}] = {{ true, -1, {flags} }},\n") + out.emit("};\n") + out.emit("#endif\n\n") + + +def generate_expansion_table(analysis: Analysis, out: CWriter) -> None: + expansions_table: dict[str, list[tuple[str, int, int]]] = {} + for inst in sorted(analysis.instructions.values(), key=lambda t: t.name): + offset: int = 0 # Cache effect offset + expansions: list[tuple[str, int, int]] = [] # [(name, size, offset), ...] + if inst.is_super(): + pieces = inst.name.split("_") + assert len(pieces) == 4, f"{inst.name} doesn't look like a super-instr" + name1 = "_".join(pieces[:2]) + name2 = "_".join(pieces[2:]) + assert name1 in analysis.instructions, f"{name1} doesn't match any instr" + assert name2 in analysis.instructions, f"{name2} doesn't match any instr" + instr1 = analysis.instructions[name1] + instr2 = analysis.instructions[name2] + assert ( + len(instr1.parts) == 1 + ), f"{name1} is not a good superinstruction part" + assert ( + len(instr2.parts) == 1 + ), f"{name2} is not a good superinstruction part" + expansions.append((instr1.parts[0].name, OPARG_KINDS["OPARG_TOP"], 0)) + expansions.append((instr2.parts[0].name, OPARG_KINDS["OPARG_BOTTOM"], 0)) + elif not is_viable_expansion(inst): + continue + else: + for part in inst.parts: + size = part.size + if part.name == "_SAVE_RETURN_OFFSET": + size = OPARG_KINDS["OPARG_SAVE_RETURN_OFFSET"] + if isinstance(part, Uop): + # Skip specializations + if "specializing" in part.annotations: + continue + if "replaced" in part.annotations: + size = OPARG_KINDS["OPARG_REPLACED"] + expansions.append((part.name, size, offset if size else 0)) + offset += part.size + expansions_table[inst.name] = expansions + max_uops = max(len(ex) for ex in expansions_table.values()) + out.emit(f"#define MAX_UOP_PER_EXPANSION {max_uops}\n") + out.emit("struct opcode_macro_expansion {\n") + out.emit("int nuops;\n") + out.emit( + "struct { int16_t uop; int8_t size; int8_t offset; } uops[MAX_UOP_PER_EXPANSION];\n" + ) + out.emit("};\n") + out.emit( + "extern const struct opcode_macro_expansion _PyOpcode_macro_expansion[256];\n\n" + ) + out.emit("#ifdef NEED_OPCODE_METADATA\n") + out.emit("const struct opcode_macro_expansion\n") + out.emit("_PyOpcode_macro_expansion[256] = {\n") + for inst_name, expansions in expansions_table.items(): + uops = [ + f"{{ {name}, {size}, {offset} }}" for (name, size, offset) in expansions + ] + out.emit( + f'[{inst_name}] = {{ .nuops = {len(expansions)}, .uops = {{ {", ".join(uops)} }} }},\n' + ) + out.emit("};\n") + out.emit("#endif // NEED_OPCODE_METADATA\n\n") + + +def is_viable_expansion(inst: Instruction) -> bool: + "An instruction can be expanded if all its parts are viable for tier 2" + for part in inst.parts: + if isinstance(part, Uop): + # Skip specializing and replaced uops + if "specializing" in part.annotations: + continue + if "replaced" in part.annotations: + continue + if part.properties.tier_one_only or not part.is_viable(): + return False + return True + + +def generate_extra_cases(analysis: Analysis, out: CWriter) -> None: + out.emit("#define EXTRA_CASES \\\n") + valid_opcodes = set(analysis.opmap.values()) + for op in range(256): + if op not in valid_opcodes: + out.emit(f" case {op}: \\\n") + out.emit(" ;\n") + + +def generate_pseudo_targets(analysis: Analysis, out: CWriter) -> None: + table_size = len(analysis.pseudos) + max_targets = max(len(pseudo.targets) for pseudo in analysis.pseudos.values()) + out.emit("struct pseudo_targets {\n") + out.emit(f"uint8_t targets[{max_targets + 1}];\n") + out.emit("};\n") + out.emit( + f"extern const struct pseudo_targets _PyOpcode_PseudoTargets[{table_size}];\n" + ) + out.emit("#ifdef NEED_OPCODE_METADATA\n") + out.emit( + f"const struct pseudo_targets _PyOpcode_PseudoTargets[{table_size}] = {{\n" + ) + for pseudo in analysis.pseudos.values(): + targets = ["0"] * (max_targets + 1) + for i, target in enumerate(pseudo.targets): + targets[i] = target.name + out.emit(f"[{pseudo.name}-256] = {{ {{ {', '.join(targets)} }} }},\n") + out.emit("};\n\n") + out.emit("#endif // NEED_OPCODE_METADATA\n") + out.emit("static inline bool\n") + out.emit("is_pseudo_target(int pseudo, int target) {\n") + out.emit(f"if (pseudo < 256 || pseudo >= {256+table_size}) {{\n") + out.emit(f"return false;\n") + out.emit("}\n") + out.emit( + f"for (int i = 0; _PyOpcode_PseudoTargets[pseudo-256].targets[i]; i++) {{\n" + ) + out.emit( + f"if (_PyOpcode_PseudoTargets[pseudo-256].targets[i] == target) return true;\n" + ) + out.emit("}\n") + out.emit(f"return false;\n") + out.emit("}\n\n") + + +def generate_opcode_metadata( + filenames: list[str], analysis: Analysis, outfile: TextIO +) -> None: + write_header(__file__, filenames, outfile) + out = CWriter(outfile, 0, False) + with out.header_guard("Py_CORE_OPCODE_METADATA_H"): + out.emit("#ifndef Py_BUILD_CORE\n") + out.emit('# error "this header requires Py_BUILD_CORE define"\n') + out.emit("#endif\n\n") + out.emit("#include <stdbool.h> // bool\n") + out.emit('#include "opcode_ids.h"\n') + generate_is_pseudo(analysis, out) + out.emit('#include "pycore_uop_ids.h"\n') + generate_stack_effect_functions(analysis, out) + generate_instruction_formats(analysis, out) + table_size = 256 + len(analysis.pseudos) + out.emit("#define IS_VALID_OPCODE(OP) \\\n") + out.emit(f" (((OP) >= 0) && ((OP) < {table_size}) && \\\n") + out.emit(" (_PyOpcode_opcode_metadata[(OP)].valid_entry))\n\n") + generate_flag_macros(out) + generate_oparg_macros(out) + generate_metadata_table(analysis, out) + generate_expansion_table(analysis, out) + generate_name_table(analysis, out) + generate_cache_table(analysis, out) + generate_deopt_table(analysis, out) + generate_extra_cases(analysis, out) + generate_pseudo_targets(analysis, out) + + +arg_parser = argparse.ArgumentParser( + description="Generate the header file with opcode metadata.", + formatter_class=argparse.ArgumentDefaultsHelpFormatter, +) + + +DEFAULT_OUTPUT = ROOT / "Include/internal/pycore_uop_metadata.h" + + +arg_parser.add_argument( + "-o", "--output", type=str, help="Generated code", default=DEFAULT_OUTPUT +) + +arg_parser.add_argument( + "input", nargs=argparse.REMAINDER, help="Instruction definition file(s)" +) + +if __name__ == "__main__": + args = arg_parser.parse_args() + if len(args.input) == 0: + args.input.append(DEFAULT_INPUT) + data = analyze_files(args.input) + with open(args.output, "w") as outfile: + generate_opcode_metadata(args.input, data, outfile) diff --git a/Tools/cases_generator/py_metadata_generator.py b/Tools/cases_generator/py_metadata_generator.py new file mode 100644 index 0000000..43811fd --- /dev/null +++ b/Tools/cases_generator/py_metadata_generator.py @@ -0,0 +1,97 @@ +"""Generate uop metedata. +Reads the instruction definitions from bytecodes.c. +Writes the metadata to pycore_uop_metadata.h by default. +""" + +import argparse + +from analyzer import ( + Analysis, + analyze_files, +) +from generators_common import ( + DEFAULT_INPUT, + ROOT, + root_relative_path, + write_header, +) +from cwriter import CWriter +from typing import TextIO + + + +DEFAULT_OUTPUT = ROOT / "Lib/_opcode_metadata.py" + + +def get_specialized(analysis: Analysis) -> set[str]: + specialized: set[str] = set() + for family in analysis.families.values(): + for member in family.members: + specialized.add(member.name) + return specialized + + +def generate_specializations(analysis: Analysis, out: CWriter) -> None: + out.emit("_specializations = {\n") + for family in analysis.families.values(): + out.emit(f'"{family.name}": [\n') + for member in family.members: + out.emit(f' "{member.name}",\n') + out.emit("],\n") + out.emit("}\n\n") + + +def generate_specialized_opmap(analysis: Analysis, out: CWriter) -> None: + out.emit("_specialized_opmap = {\n") + names = [] + for family in analysis.families.values(): + for member in family.members: + if member.name == family.name: + continue + names.append(member.name) + for name in sorted(names): + out.emit(f"'{name}': {analysis.opmap[name]},\n") + out.emit("}\n\n") + + +def generate_opmap(analysis: Analysis, out: CWriter) -> None: + specialized = get_specialized(analysis) + out.emit("opmap = {\n") + for inst, op in analysis.opmap.items(): + if inst not in specialized: + out.emit(f"'{inst}': {analysis.opmap[inst]},\n") + out.emit("}\n\n") + + +def generate_py_metadata( + filenames: list[str], analysis: Analysis, outfile: TextIO +) -> None: + write_header(__file__, filenames, outfile, "#") + out = CWriter(outfile, 0, False) + generate_specializations(analysis, out) + generate_specialized_opmap(analysis, out) + generate_opmap(analysis, out) + out.emit(f"HAVE_ARGUMENT = {analysis.have_arg}\n") + out.emit(f"MIN_INSTRUMENTED_OPCODE = {analysis.min_instrumented}\n") + + +arg_parser = argparse.ArgumentParser( + description="Generate the Python file with opcode metadata.", + formatter_class=argparse.ArgumentDefaultsHelpFormatter, +) + +arg_parser.add_argument( + "-o", "--output", type=str, help="Generated code", default=DEFAULT_OUTPUT +) + +arg_parser.add_argument( + "input", nargs=argparse.REMAINDER, help="Instruction definition file(s)" +) + +if __name__ == "__main__": + args = arg_parser.parse_args() + if len(args.input) == 0: + args.input.append(DEFAULT_INPUT) + data = analyze_files(args.input) + with open(args.output, "w") as outfile: + generate_py_metadata(args.input, data, outfile) diff --git a/Tools/cases_generator/stack.py b/Tools/cases_generator/stack.py index 0b31ce4..94fb82d 100644 --- a/Tools/cases_generator/stack.py +++ b/Tools/cases_generator/stack.py @@ -1,5 +1,5 @@ import sys -from analyzer import StackItem +from analyzer import StackItem, Instruction, Uop from dataclasses import dataclass from formatting import maybe_parenthesize from cwriter import CWriter @@ -15,13 +15,16 @@ def var_size(var: StackItem) -> str: else: return var.size - +@dataclass class StackOffset: "The stack offset of the virtual base of the stack from the physical stack pointer" - def __init__(self) -> None: - self.popped: list[str] = [] - self.pushed: list[str] = [] + popped: list[str] + pushed: list[str] + + @staticmethod + def empty() -> "StackOffset": + return StackOffset([], []) def pop(self, item: StackItem) -> None: self.popped.append(var_size(item)) @@ -29,6 +32,15 @@ class StackOffset: def push(self, item: StackItem) -> None: self.pushed.append(var_size(item)) + def __sub__(self, other: "StackOffset") -> "StackOffset": + return StackOffset( + self.popped + other.pushed, + self.pushed + other.popped + ) + + def __neg__(self) -> "StackOffset": + return StackOffset(self.pushed, self.popped) + def simplify(self) -> None: "Remove matching values from both the popped and pushed list" if not self.popped or not self.pushed: @@ -88,9 +100,9 @@ class SizeMismatch(Exception): class Stack: def __init__(self) -> None: - self.top_offset = StackOffset() - self.base_offset = StackOffset() - self.peek_offset = StackOffset() + self.top_offset = StackOffset.empty() + self.base_offset = StackOffset.empty() + self.peek_offset = StackOffset.empty() self.variables: list[StackItem] = [] self.defined: set[str] = set() @@ -166,3 +178,15 @@ class Stack: def as_comment(self) -> str: return f"/* Variables: {[v.name for v in self.variables]}. Base offset: {self.base_offset.to_c()}. Top offset: {self.top_offset.to_c()} */" + + +def get_stack_effect(inst: Instruction) -> Stack: + stack = Stack() + for uop in inst.parts: + if not isinstance(uop, Uop): + continue + for var in reversed(uop.stack.inputs): + stack.pop(var) + for i, var in enumerate(uop.stack.outputs): + stack.push(var) + return stack diff --git a/Tools/cases_generator/tier1_generator.py b/Tools/cases_generator/tier1_generator.py index 49cede9..aba36ec 100644 --- a/Tools/cases_generator/tier1_generator.py +++ b/Tools/cases_generator/tier1_generator.py @@ -190,6 +190,7 @@ def generate_tier1_from_files( with open(outfilename, "w") as outfile: generate_tier1(filenames, data, outfile, lines) + if __name__ == "__main__": args = arg_parser.parse_args() if len(args.input) == 0: diff --git a/Tools/cases_generator/tier2_generator.py b/Tools/cases_generator/tier2_generator.py index a22fb6d..7897b89 100644 --- a/Tools/cases_generator/tier2_generator.py +++ b/Tools/cases_generator/tier2_generator.py @@ -103,13 +103,6 @@ TIER2_REPLACEMENT_FUNCTIONS["ERROR_IF"] = tier2_replace_error TIER2_REPLACEMENT_FUNCTIONS["DEOPT_IF"] = tier2_replace_deopt -def is_super(uop: Uop) -> bool: - for tkn in uop.body: - if tkn.kind == "IDENTIFIER" and tkn.text == "oparg1": - return True - return False - - def write_uop(uop: Uop, out: CWriter, stack: Stack) -> None: try: out.start_line() @@ -123,7 +116,7 @@ def write_uop(uop: Uop, out: CWriter, stack: Stack) -> None: for cache in uop.caches: if cache.name != "unused": if cache.size == 4: - type = cast ="PyObject *" + type = cast = "PyObject *" else: type = f"uint{cache.size*16}_t " cast = f"uint{cache.size*16}_t" @@ -156,7 +149,7 @@ def generate_tier2( for name, uop in analysis.uops.items(): if uop.properties.tier_one_only: continue - if is_super(uop): + if uop.is_super(): continue if not uop.is_viable(): out.emit(f"/* {uop.name} is not a viable micro-op for tier 2 */\n\n") diff --git a/Tools/cases_generator/uop_id_generator.py b/Tools/cases_generator/uop_id_generator.py index 277da25..633249f 100644 --- a/Tools/cases_generator/uop_id_generator.py +++ b/Tools/cases_generator/uop_id_generator.py @@ -24,50 +24,32 @@ from typing import TextIO DEFAULT_OUTPUT = ROOT / "Include/internal/pycore_uop_ids.h" -OMIT = {"_CACHE", "_RESERVED", "_EXTENDED_ARG"} - - def generate_uop_ids( filenames: list[str], analysis: Analysis, outfile: TextIO, distinct_namespace: bool ) -> None: write_header(__file__, filenames, outfile) out = CWriter(outfile, 0, False) - out.emit( - """#ifndef Py_CORE_UOP_IDS_H -#define Py_CORE_UOP_IDS_H -#ifdef __cplusplus -extern "C" { -#endif - -""" - ) - - next_id = 1 if distinct_namespace else 300 - # These two are first by convention - out.emit(f"#define _EXIT_TRACE {next_id}\n") - next_id += 1 - out.emit(f"#define _SET_IP {next_id}\n") - next_id += 1 - PRE_DEFINED = {"_EXIT_TRACE", "_SET_IP"} - - for uop in analysis.uops.values(): - if uop.name in PRE_DEFINED: - continue - # TODO: We should omit all tier-1 only uops, but - # generate_cases.py still generates code for those. - if uop.name in OMIT: - continue - if uop.implicitly_created and not distinct_namespace: - out.emit(f"#define {uop.name} {uop.name[1:]}\n") - else: - out.emit(f"#define {uop.name} {next_id}\n") - next_id += 1 - - out.emit("\n") - out.emit("#ifdef __cplusplus\n") - out.emit("}\n") - out.emit("#endif\n") - out.emit("#endif /* !Py_OPCODE_IDS_H */\n") + with out.header_guard("Py_CORE_UOP_IDS_H"): + next_id = 1 if distinct_namespace else 300 + # These two are first by convention + out.emit(f"#define _EXIT_TRACE {next_id}\n") + next_id += 1 + out.emit(f"#define _SET_IP {next_id}\n") + next_id += 1 + PRE_DEFINED = {"_EXIT_TRACE", "_SET_IP"} + + for uop in analysis.uops.values(): + if uop.name in PRE_DEFINED: + continue + if uop.properties.tier_one_only: + continue + if uop.implicitly_created and not distinct_namespace: + out.emit(f"#define {uop.name} {uop.name[1:]}\n") + else: + out.emit(f"#define {uop.name} {next_id}\n") + next_id += 1 + + out.emit(f"#define MAX_UOP_ID {next_id-1}\n") arg_parser = argparse.ArgumentParser( diff --git a/Tools/cases_generator/uop_metadata_generator.py b/Tools/cases_generator/uop_metadata_generator.py new file mode 100644 index 0000000..d4f3a09 --- /dev/null +++ b/Tools/cases_generator/uop_metadata_generator.py @@ -0,0 +1,73 @@ +"""Generate uop metedata. +Reads the instruction definitions from bytecodes.c. +Writes the metadata to pycore_uop_metadata.h by default. +""" + +import argparse + +from analyzer import ( + Analysis, + analyze_files, +) +from generators_common import ( + DEFAULT_INPUT, + ROOT, + write_header, + cflags, +) +from cwriter import CWriter +from typing import TextIO + + +DEFAULT_OUTPUT = ROOT / "Include/internal/pycore_uop_metadata.h" + + +def generate_names_and_flags(analysis: Analysis, out: CWriter) -> None: + out.emit("extern const uint16_t _PyUop_Flags[MAX_UOP_ID+1];\n") + out.emit("extern const char * const _PyOpcode_uop_name[MAX_UOP_ID+1];\n\n") + out.emit("#ifdef NEED_OPCODE_METADATA\n") + out.emit("const uint16_t _PyUop_Flags[MAX_UOP_ID+1] = {\n") + for uop in analysis.uops.values(): + if uop.is_viable() and not uop.properties.tier_one_only: + out.emit(f"[{uop.name}] = {cflags(uop.properties)},\n") + + out.emit("};\n\n") + out.emit("const char *const _PyOpcode_uop_name[MAX_UOP_ID+1] = {\n") + for uop in sorted(analysis.uops.values(), key=lambda t: t.name): + if uop.is_viable() and not uop.properties.tier_one_only: + out.emit(f'[{uop.name}] = "{uop.name}",\n') + out.emit("};\n") + out.emit("#endif // NEED_OPCODE_METADATA\n\n") + + +def generate_uop_metadata( + filenames: list[str], analysis: Analysis, outfile: TextIO +) -> None: + write_header(__file__, filenames, outfile) + out = CWriter(outfile, 0, False) + with out.header_guard("Py_CORE_UOP_METADATA_H"): + out.emit("#include <stdint.h>\n") + out.emit('#include "pycore_uop_ids.h"\n') + generate_names_and_flags(analysis, out) + + +arg_parser = argparse.ArgumentParser( + description="Generate the header file with uop metadata.", + formatter_class=argparse.ArgumentDefaultsHelpFormatter, +) + +arg_parser.add_argument( + "-o", "--output", type=str, help="Generated code", default=DEFAULT_OUTPUT +) + +arg_parser.add_argument( + "input", nargs=argparse.REMAINDER, help="Instruction definition file(s)" +) + +if __name__ == "__main__": + args = arg_parser.parse_args() + if len(args.input) == 0: + args.input.append(DEFAULT_INPUT) + data = analyze_files(args.input) + with open(args.output, "w") as outfile: + generate_uop_metadata(args.input, data, outfile) |