gh-105481: add pseudo-instructions to the bytecodes DSL (#105506)

2 files changed, 111 insertions, 10 deletions

diff --git a/Tools/cases_generator/generate_cases.py b/Tools/cases_generator/generate_cases.py
index 9917261..49feb50 100644
--- a/Tools/cases_generator/generate_cases.py
+++ b/Tools/cases_generator/generate_cases.py
@@ -492,6 +492,15 @@ class MacroInstruction(SuperOrMacroInstruction):
 
 
 @dataclasses.dataclass
+class PseudoInstruction:
+    """A pseudo instruction."""
+
+    name: str
+    instr_fmt: str
+    targets: list[Instruction]
+
+
+@dataclasses.dataclass
 class OverriddenInstructionPlaceHolder:
     name: str
 
@@ -529,7 +538,8 @@ class Analyzer:
         self.errors += 1
 
     everything: list[
-        parser.InstDef | parser.Super | parser.Macro | OverriddenInstructionPlaceHolder
+        parser.InstDef | parser.Super | parser.Macro |
+        parser.Pseudo | OverriddenInstructionPlaceHolder
     ]
     instrs: dict[str, Instruction]  # Includes ops
     supers: dict[str, parser.Super]
@@ -537,6 +547,7 @@ class Analyzer:
     macros: dict[str, parser.Macro]
     macro_instrs: dict[str, MacroInstruction]
     families: dict[str, parser.Family]
+    pseudo_instrs: dict[str, PseudoInstruction]
 
     def parse(self) -> None:
         """Parse the source text.
@@ -550,6 +561,7 @@ class Analyzer:
         self.supers = {}
         self.macros = {}
         self.families = {}
+        self.pseudos = {}
 
         instrs_idx: dict[str, int] = dict()
 
@@ -623,6 +635,9 @@ class Analyzer:
                     self.everything.append(thing)
                 case parser.Family(name):
                     self.families[name] = thing
+                case parser.Pseudo(name):
+                    self.pseudos[name] = thing
+                    self.everything.append(thing)
                 case _:
                     typing.assert_never(thing)
         if not psr.eof():
@@ -633,7 +648,7 @@ class Analyzer:
 
         Raises SystemExit if there is an error.
         """
-        self.analyze_supers_and_macros()
+        self.analyze_supers_and_macros_and_pseudos()
         self.find_predictions()
         self.map_families()
         self.check_families()
@@ -745,14 +760,17 @@ class Analyzer:
             assert False, f"Unknown instruction {name!r}"
         return cache, input, output
 
-    def analyze_supers_and_macros(self) -> None:
-        """Analyze each super- and macro instruction."""
+    def analyze_supers_and_macros_and_pseudos(self) -> None:
+        """Analyze each super-, macro- and pseudo- instruction."""
         self.super_instrs = {}
         self.macro_instrs = {}
+        self.pseudo_instrs = {}
         for name, super in self.supers.items():
             self.super_instrs[name] = self.analyze_super(super)
         for name, macro in self.macros.items():
             self.macro_instrs[name] = self.analyze_macro(macro)
+        for name, pseudo in self.pseudos.items():
+            self.pseudo_instrs[name] = self.analyze_pseudo(pseudo)
 
     def analyze_super(self, super: parser.Super) -> SuperInstruction:
         components = self.check_super_components(super)
@@ -797,6 +815,14 @@ class Analyzer:
             macro.name, stack, initial_sp, final_sp, format, macro, parts
         )
 
+    def analyze_pseudo(self, pseudo: parser.Pseudo) -> PseudoInstruction:
+        targets = [self.instrs[target] for target in pseudo.targets]
+        assert targets
+        # Make sure the targets have the same fmt
+        fmts = list(set([t.instr_fmt for t in targets]))
+        assert(len(fmts) == 1)
+        return PseudoInstruction(pseudo.name, fmts[0], targets)
+
     def analyze_instruction(
         self, instr: Instruction, stack: list[StackEffect], sp: int
     ) -> tuple[Component, int]:
@@ -875,7 +901,7 @@ class Analyzer:
         return stack, -lowest
 
     def get_stack_effect_info(
-        self, thing: parser.InstDef | parser.Super | parser.Macro
+        self, thing: parser.InstDef | parser.Super | parser.Macro | parser.Pseudo
     ) -> tuple[AnyInstruction | None, str, str]:
         def effect_str(effects: list[StackEffect]) -> str:
             if getattr(thing, "kind", None) == "legacy":
@@ -932,6 +958,24 @@ class Analyzer:
                     self.error("Macro has virtual stack growth", thing)
                 popped = str(-low)
                 pushed = str(sp - low)
+            case parser.Pseudo():
+                instr = self.pseudos[thing.name]
+                popped = pushed = None
+                # Calculate stack effect, and check that it's the the same
+                # for all targets.
+                for target in self.pseudos[thing.name].targets:
+                    target_instr = self.instrs.get(target)
+                    # Currently target is always an instr. This could change
+                    # in the future, e.g., if we have a pseudo targetting a
+                    # macro instruction.
+                    assert target_instr
+                    target_popped = effect_str(target_instr.input_effects)
+                    target_pushed = effect_str(target_instr.output_effects)
+                    if popped is None and pushed is None:
+                        popped, pushed = target_popped, target_pushed
+                    else:
+                        assert popped == target_popped
+                        assert pushed == target_pushed
             case _:
                 typing.assert_never(thing)
         return instr, popped, pushed
@@ -992,6 +1036,15 @@ class Analyzer:
                     format = self.super_instrs[thing.name].instr_fmt
                 case parser.Macro():
                     format = self.macro_instrs[thing.name].instr_fmt
+                case parser.Pseudo():
+                    format = None
+                    for target in self.pseudos[thing.name].targets:
+                        target_instr = self.instrs.get(target)
+                        assert target_instr
+                        if format is None:
+                            format = target_instr.instr_fmt
+                        else:
+                            assert format == target_instr.instr_fmt
                 case _:
                     typing.assert_never(thing)
             all_formats.add(format)
@@ -1007,6 +1060,7 @@ class Analyzer:
             self.out.write_raw(self.from_source_files())
             self.out.write_raw(f"// Do not edit!\n")
 
+            self.write_pseudo_instrs()
 
             self.write_stack_effect_functions()
 
@@ -1018,12 +1072,17 @@ class Analyzer:
                 self.out.emit("enum InstructionFormat instr_format;")
             self.out.emit("};")
             self.out.emit("")
+            self.out.emit("#define OPCODE_METADATA_FMT(OP) "
+                          "(_PyOpcode_opcode_metadata[(OP)].instr_format)")
+            self.out.emit("#define SAME_OPCODE_METADATA(OP1, OP2) \\")
+            self.out.emit("        (OPCODE_METADATA_FMT(OP1) == OPCODE_METADATA_FMT(OP2))")
+            self.out.emit("")
 
             # Write metadata array declaration
             self.out.emit("#ifndef NEED_OPCODE_METADATA")
-            self.out.emit("extern const struct opcode_metadata _PyOpcode_opcode_metadata[256];")
+            self.out.emit("extern const struct opcode_metadata _PyOpcode_opcode_metadata[512];")
             self.out.emit("#else")
-            self.out.emit("const struct opcode_metadata _PyOpcode_opcode_metadata[256] = {")
+            self.out.emit("const struct opcode_metadata _PyOpcode_opcode_metadata[512] = {")
 
             # Write metadata for each instruction
             for thing in self.everything:
@@ -1037,6 +1096,8 @@ class Analyzer:
                         self.write_metadata_for_super(self.super_instrs[thing.name])
                     case parser.Macro():
                         self.write_metadata_for_macro(self.macro_instrs[thing.name])
+                    case parser.Pseudo():
+                        self.write_metadata_for_pseudo(self.pseudo_instrs[thing.name])
                     case _:
                         typing.assert_never(thing)
 
@@ -1044,6 +1105,13 @@ class Analyzer:
             self.out.emit("};")
             self.out.emit("#endif")
 
+    def write_pseudo_instrs(self) -> None:
+        """Write the IS_PSEUDO_INSTR macro"""
+        self.out.emit("\n\n#define IS_PSEUDO_INSTR(OP)  \\")
+        for op in self.pseudos:
+            self.out.emit(f"    ((OP) == {op}) || \\")
+        self.out.emit(f"    0")
+
     def write_metadata_for_inst(self, instr: Instruction) -> None:
         """Write metadata for a single instruction."""
         self.out.emit(
@@ -1062,6 +1130,12 @@ class Analyzer:
             f"    [{mac.name}] = {{ true, {INSTR_FMT_PREFIX}{mac.instr_fmt} }},"
         )
 
+    def write_metadata_for_pseudo(self, ps: PseudoInstruction) -> None:
+        """Write metadata for a macro-instruction."""
+        self.out.emit(
+            f"    [{ps.name}] = {{ true, {INSTR_FMT_PREFIX}{ps.instr_fmt} }},"
+        )
+
     def write_instructions(self) -> None:
         """Write instructions to output file."""
         with open(self.output_filename, "w") as f:
@@ -1077,6 +1151,7 @@ class Analyzer:
             n_instrs = 0
             n_supers = 0
             n_macros = 0
+            n_pseudos = 0
             for thing in self.everything:
                 match thing:
                     case OverriddenInstructionPlaceHolder():
@@ -1091,12 +1166,14 @@ class Analyzer:
                     case parser.Macro():
                         n_macros += 1
                         self.write_macro(self.macro_instrs[thing.name])
+                    case parser.Pseudo():
+                        n_pseudos += 1
                     case _:
                         typing.assert_never(thing)
 
         print(
-            f"Wrote {n_instrs} instructions, {n_supers} supers, "
-            f"and {n_macros} macros to {self.output_filename}",
+            f"Wrote {n_instrs} instructions, {n_supers} supers, {n_macros}"
+            f" macros and {n_pseudos} pseudos to {self.output_filename}",
             file=sys.stderr,
         )
 
diff --git a/Tools/cases_generator/parser.py b/Tools/cases_generator/parser.py
index 7bf45a3..56920f2 100644
--- a/Tools/cases_generator/parser.py
+++ b/Tools/cases_generator/parser.py
@@ -136,10 +136,15 @@ class Family(Node):
     size: str  # Variable giving the cache size in code units
     members: list[str]
 
+@dataclass
+class Pseudo(Node):
+    name: str
+    targets: list[str]  # opcodes this can be replaced by
+
 
 class Parser(PLexer):
     @contextual
-    def definition(self) -> InstDef | Super | Macro | Family | None:
+    def definition(self) -> InstDef | Super | Macro | Family | Pseudo | None:
         if inst := self.inst_def():
             return inst
         if super := self.super_def():
@@ -148,6 +153,8 @@ class Parser(PLexer):
             return macro
         if family := self.family_def():
             return family
+        if pseudo := self.pseudo_def():
+            return pseudo
 
     @contextual
     def inst_def(self) -> InstDef | None:
@@ -364,6 +371,23 @@ class Parser(PLexer):
                                     )
         return None
 
+    @contextual
+    def pseudo_def(self) -> Pseudo | None:
+        if (tkn := self.expect(lx.IDENTIFIER)) and tkn.text == "pseudo":
+            size = None
+            if self.expect(lx.LPAREN):
+                if tkn := self.expect(lx.IDENTIFIER):
+                    if self.expect(lx.RPAREN):
+                        if self.expect(lx.EQUALS):
+                            if not self.expect(lx.LBRACE):
+                                raise self.make_syntax_error("Expected {")
+                            if members := self.members():
+                                if self.expect(lx.RBRACE) and self.expect(lx.SEMI):
+                                    return Pseudo(
+                                        tkn.text, members
+                                    )
+        return None
+
     def members(self) -> list[str] | None:
         here = self.getpos()
         if tkn := self.expect(lx.IDENTIFIER):