Overview

This is the first stage of a project to generate the interpreter, in particular the cases of the main switch. The references below explain the why. This PR introduces the following:

• Two new files in the Python subdirectory, bytecodes.c and generated_cases.c.h. (UPDATE: cases.h -> generated_cases.c.h.)

  • bytecodes.c contains instruction definitions. These almost look like the old switch cases, but instead of TARGET(INAME) { ... } they have inst(INAME, stack_effect) { ... }, and the DISPATCH() macro call at the end of the block can be omitted. (The stack effect is not yet used by the generator, and it is not always correct.) At the top and bottom of bytecodes.c is some dummy C code that makes look like valid C code to editors like VS Code.
  • generated_cases.c.h is a generated file containing the switch cases. It is currently identical to the switch cases in ceval.c.

• A new bunch of tooling, in Tools/cases_generator. This includes:

  • A temporary script, extract_cases.py, that extracts the cases from ceval.c and writes them, in the form of instruction definitions, to bytecodes.c.
  • A script, generate_cases.py, that reads the instruction definitions from bytecodes.c and regenerates the cases, writing them to generated_cases.c.h.
  • A parser for a subset of C that turns blocks of C code into an AST, so we can do transformations at the AST level. (There is currently one example of this -- the function always_exits() determines recursively whether a block is guaranteed to exit, using a custom definition of "exit" that includes macro calls like DISPATCH() and GO_TO_INSTRUCTION().)

• Changes to ceval.c so that it uses #include "generated_cases.c.h". For now I've left the original switch cases in ceval.c, inside #else ... #endif, so that we can compare the original switch cases to the generated switch cases to validate the toolchain. However, I plan to rip these out either once the PR is (nearly) approved, or perhaps in a quick follow-up PR.

• A new target in Makefile.pre.in to auto-generate generated_cases.c.h from bytecodes.c, using make regen-cases.

  • Currently missing is similar tooling on Windows. For now, you can only regenerate the cases on UNIX. They are checked into the repo, so Windows should still compile.

References

• Generating code for the ceval loop/switch faster-cpython/ideas#5
• Super-instructions faster-cpython/ideas#16
• Define opcodes in terms of smaller "micro-ops" faster-cpython/ideas#454
• Change the interpreter definition DSL to be legal C syntax faster-cpython/ideas#477
• Mechanics of interpreter generation from DSL faster-cpython/ideas#479
• Stack effect of jumping -- how to express in DSL faster-cpython/ideas#481

Metadata

• Issue: Generate the interpreter #98831