Skip to content

GH-98831: Implement super-instruction generation #99084

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 6 commits into from
Nov 6, 2022
Merged

GH-98831: Implement super-instruction generation #99084

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
6 commits
Select commit Hold shift + click to select a range
55816fd
Implement super-instruction generation
gvanrossum Nov 4, 2022
0d746d2
Update NEWS for issue 98831
gvanrossum Nov 4, 2022
7998877
Apply suggestions from CAM's review to NEWS
gvanrossum Nov 4, 2022
9072291
Fix whitespace
gvanrossum Nov 4, 2022
b84ee0a
Merge branch 'main' into super-instrs
gvanrossum Nov 4, 2022
b5fe9fa
Remove debug print
gvanrossum Nov 4, 2022
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
10 changes: 9 additions & 1 deletion Misc/NEWS.d/next/Build/2022-10-28-22-24-26.gh-issue-98831.IXRCRX.rst
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1 +1,9 @@
We have new tooling, in ``Tools/cases_generator``, to generate the interpreter switch from a list of opcode definitions.
Add new tooling, in ``Tools/cases_generator``,
to generate the interpreter switch statement from a list of opcode definitions.
This only affects adding, modifying or removing instruction definitions.
The instruction definitions now live in ``Python/bytecodes.c``,
in the form of a `custom DSL (under development)
<https://github.com/faster-cpython/ideas/blob/main/3.12/interpreter_definition.md>`__.
The tooling reads this file and writes ``Python/generated_cases.c.h``,
which is then included by ``Python/ceval.c`` to provide most of the cases
of the main interpreter switch.
67 changes: 6 additions & 61 deletions Python/bytecodes.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -34,6 +34,7 @@ void _PyUnicode_ExactDealloc(PyObject *);
#define GETLOCAL(i) (frame->localsplus[i])

#define inst(name) case name:
#define super(name) static int SUPER_##name
#define family(name) static int family_##name

#define NAME_ERROR_MSG \
Expand Down Expand Up @@ -123,67 +124,11 @@ dummy_func(
SETLOCAL(oparg, value);
}

// stack effect: ( -- __0, __1)
inst(LOAD_FAST__LOAD_FAST) {
PyObject *value = GETLOCAL(oparg);
assert(value != NULL);
NEXTOPARG();
next_instr++;
Py_INCREF(value);
PUSH(value);
value = GETLOCAL(oparg);
assert(value != NULL);
Py_INCREF(value);
PUSH(value);
}

// stack effect: ( -- __0, __1)
inst(LOAD_FAST__LOAD_CONST) {
PyObject *value = GETLOCAL(oparg);
assert(value != NULL);
NEXTOPARG();
next_instr++;
Py_INCREF(value);
PUSH(value);
value = GETITEM(consts, oparg);
Py_INCREF(value);
PUSH(value);
}

// stack effect: ( -- )
inst(STORE_FAST__LOAD_FAST) {
PyObject *value = POP();
SETLOCAL(oparg, value);
NEXTOPARG();
next_instr++;
value = GETLOCAL(oparg);
assert(value != NULL);
Py_INCREF(value);
PUSH(value);
}

// stack effect: (__0, __1 -- )
inst(STORE_FAST__STORE_FAST) {
PyObject *value = POP();
SETLOCAL(oparg, value);
NEXTOPARG();
next_instr++;
value = POP();
SETLOCAL(oparg, value);
}

// stack effect: ( -- __0, __1)
inst(LOAD_CONST__LOAD_FAST) {
PyObject *value = GETITEM(consts, oparg);
NEXTOPARG();
next_instr++;
Py_INCREF(value);
PUSH(value);
value = GETLOCAL(oparg);
assert(value != NULL);
Py_INCREF(value);
PUSH(value);
}
super(LOAD_FAST__LOAD_FAST) = LOAD_FAST + LOAD_FAST;
super(LOAD_FAST__LOAD_CONST) = LOAD_FAST + LOAD_CONST;
super(STORE_FAST__LOAD_FAST) = STORE_FAST + LOAD_FAST;
super(STORE_FAST__STORE_FAST) = STORE_FAST + STORE_FAST;
super (LOAD_CONST__LOAD_FAST) = LOAD_CONST + LOAD_FAST;

// stack effect: (__0 -- )
inst(POP_TOP) {
Expand Down
144 changes: 82 additions & 62 deletions Python/generated_cases.c.h
View file
Open in desktop

Some generated files are not rendered by default. Learn more about how customized files appear on GitHub.

44 changes: 34 additions & 10 deletions Tools/cases_generator/generate_cases.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -10,7 +10,7 @@
import sys

import parser
from parser import InstDef
from parser import InstDef # TODO: Use parser.InstDef

arg_parser = argparse.ArgumentParser()
arg_parser.add_argument("-i", "--input", type=str, default="Python/bytecodes.c")
Expand All @@ -28,19 +28,24 @@ def eopen(filename: str, mode: str = "r"):
return open(filename, mode)


def parse_cases(src: str, filename: str|None = None) -> tuple[list[InstDef], list[parser.Family]]:
def parse_cases(
src: str, filename: str|None = None
) -> tuple[list[InstDef], list[parser.Super], list[parser.Family]]:
psr = parser.Parser(src, filename=filename)
instrs: list[InstDef] = []
supers: list[parser.Super] = []
families: list[parser.Family] = []
while not psr.eof():
if inst := psr.inst_def():
assert inst.block
instrs.append(InstDef(inst.name, inst.inputs, inst.outputs, inst.block))
instrs.append(inst)
elif sup := psr.super_def():
supers.append(sup)
elif fam := psr.family_def():
families.append(fam)
else:
raise psr.make_syntax_error(f"Unexpected token")
return instrs, families
return instrs, supers, families


def always_exits(block: parser.Block) -> bool:
Expand All @@ -61,16 +66,18 @@ def always_exits(block: parser.Block) -> bool:
return line.startswith(("goto ", "return ", "DISPATCH", "GO_TO_", "Py_UNREACHABLE()"))


def write_cases(f: io.TextIOBase, instrs: list[InstDef]):
def write_cases(f: io.TextIOBase, instrs: list[InstDef], supers: list[parser.Super]):
predictions = set()
for inst in instrs:
for target in re.findall(r"(?:PREDICT|GO_TO_INSTRUCTION)\((\w+)\)", inst.block.text):
predictions.add(target)
indent = " "
f.write("// This file is generated by Tools/scripts/generate_cases.py\n")
f.write("// Do not edit!\n")
instr_index: dict[str, InstDef] = {}
for instr in instrs:
assert isinstance(instr, InstDef)
instr_index[instr.name] = instr
f.write(f"\n{indent}TARGET({instr.name}) {{\n")
if instr.name in predictions:
f.write(f"{indent} PREDICTED({instr.name});\n")
Expand Down Expand Up @@ -101,6 +108,22 @@ def write_cases(f: io.TextIOBase, instrs: list[InstDef]):
# Write trailing '}'
f.write(f"{indent}}}\n")

for sup in supers:
assert isinstance(sup, parser.Super)
components = [instr_index[name] for name in sup.ops]
f.write(f"\n{indent}TARGET({sup.name}) {{\n")
for i, instr in enumerate(components):
if i > 0:
f.write(f"{indent} NEXTOPARG();\n")
f.write(f"{indent} next_instr++;\n")
text = instr.block.to_text(-4)
textlines = text.splitlines(True)
textlines = [line for line in textlines if not line.strip().startswith("PREDICTED(")]
text = "".join(textlines)
f.write(f"{indent} {text.strip()}\n")
f.write(f"{indent} DISPATCH();\n")
f.write(f"{indent}}}\n")


def main():
args = arg_parser.parse_args()
Expand All @@ -109,21 +132,22 @@ def main():
begin = srclines.index("// BEGIN BYTECODES //")
end = srclines.index("// END BYTECODES //")
src = "\n".join(srclines[begin+1 : end])
instrs, families = parse_cases(src, filename=args.input)
ninstrs = nfamilies = 0
instrs, supers, families = parse_cases(src, filename=args.input)
ninstrs = nsupers = nfamilies = 0
if not args.quiet:
ninstrs = len(instrs)
nsupers = len(supers)
nfamilies = len(families)
print(
f"Read {ninstrs} instructions "
f"Read {ninstrs} instructions, {nsupers} supers, "
f"and {nfamilies} families from {args.input}",
file=sys.stderr,
)
with eopen(args.output, "w") as f:
write_cases(f, instrs)
write_cases(f, instrs, supers)
if not args.quiet:
print(
f"Wrote {ninstrs} instructions to {args.output}",
f"Wrote {ninstrs + nsupers} instructions to {args.output}",
file=sys.stderr,
)

Expand Down
Loading