Debian Codegraph @

Tools/cases_generator/interpreter_definition.md

raw
1 # A higher level definition of the bytecode interpreter
2
3 ## Abstract
4
5 The CPython interpreter is defined in C, meaning that the semantics of the
6 bytecode instructions, the dispatching mechanism, error handling, and
7 tracing and instrumentation are all intermixed.
8
9 This document proposes defining a custom C-like DSL for defining the
10 instruction semantics and tools for generating the code deriving from
11 the instruction definitions.
12
13 These tools would be used to:
14 * Generate the main interpreter (done)
15 * Generate the tier 2 interpreter
16 * Generate documentation for instructions
17 * Generate metadata about instructions, such as stack use (done).
18 * Generate the tier 2 optimizer's abstract interpreter.
19
20 Having a single definition file ensures that there is a single source
21 of truth for bytecode semantics.
22
23 Other tools that operate on bytecodes, like `frame.setlineno`
24 and the `dis` module, will be derived from the common semantic
25 definition, reducing errors.
26
27 ## Motivation
28
29 The bytecode interpreter of CPython has traditionally been defined as standard
30 C code, but with a lot of macros.
31 The presence of these macros and the nature of bytecode interpreters means
32 that the interpreter is effectively defined in a domain specific language (DSL).
33
34 Rather than using an ad-hoc DSL embedded in the C code for the interpreter,
35 a custom DSL should be defined and the semantics of the bytecode instructions,
36 and the instructions defined in that DSL.
37
38 Generating the interpreter decouples low-level details of dispatching
39 and error handling from the semantics of the instructions, resulting
40 in more maintainable code and a potentially faster interpreter.
41
42 It also provides the ability to create and check optimizers and optimization
43 passes from the semantic definition, reducing errors.
44
45 ## Rationale
46
47 As we improve the performance of CPython, we need to optimize larger regions
48 of code, use more complex optimizations and, ultimately, translate to machine
49 code.
50
51 All of these steps introduce the possibility of more bugs, and require more code
52 to be written. One way to mitigate this is through the use of code generators.
53 Code generators decouple the debugging of the code (the generator) from checking
54 the correctness (the DSL input).
55
56 For example, we are likely to want a new interpreter for the tier 2 optimizer
57 to be added in 3.12. That interpreter will have a different API, a different
58 set of instructions and potentially different dispatching mechanism.
59 But the instructions it will interpret will be built from the same building
60 blocks as the instructions for the tier 1 (PEP 659) interpreter.
61
62 Rewriting all the instructions is tedious and error-prone, and changing the
63 instructions is a maintenance headache as both versions need to be kept in sync.
64
65 By using a code generator and using a common source for the instructions, or
66 parts of instructions, we can reduce the potential for errors considerably.
67
68
69 ## Specification
70
71 This specification is a work in progress.
72 We update it as the need arises.
73
74 ### Syntax
75
76 Each op definition has a kind, a name, a stack and instruction stream effect,
77 and a piece of C code describing its semantics:
78
79 ```
80 file:
81 (definition | family | pseudo)+
82
83 definition:
84 "inst" "(" NAME "," stack_effect ")" "{" C-code "}"
85 |
86 "op" "(" NAME "," stack_effect ")" "{" C-code "}"
87 |
88 "macro" "(" NAME ")" "=" uop ("+" uop)* ";"
89
90 stack_effect:
91 "(" [inputs] "--" [outputs] ")"
92
93 inputs:
94 input ("," input)*
95
96 outputs:
97 output ("," output)*
98
99 input:
100 object | stream | array
101
102 output:
103 object | array
104
105 uop:
106 NAME | stream
107
108 object:
109 NAME [":" type] [ "if" "(" C-expression ")" ]
110
111 type:
112 NAME ["*"]
113
114 stream:
115 NAME "/" size
116
117 size:
118 INTEGER
119
120 array:
121 object "[" C-expression "]"
122
123 family:
124 "family" "(" NAME ")" = "{" NAME ("," NAME)+ [","] "}" ";"
125
126 pseudo:
127 "pseudo" "(" NAME "," stack_effect ["," "(" flags ")"]")" = "{" NAME ("," NAME)+ [","] "}" ";"
128
129 flags:
130 flag ("|" flag)*
131
132 flag:
133 HAS_ARG | HAS_DEOPT | etc..
134 ```
135
136 The following definitions may occur:
137
138 * `inst`: A normal instruction, as previously defined by `TARGET(NAME)` in `ceval.c`.
139 * `op`: A part instruction from which macros can be constructed.
140 * `macro`: A bytecode instruction constructed from ops and cache effects.
141
142 `NAME` can be any ASCII identifier that is a C identifier and not a C or Python keyword.
143 `foo_1` is legal. `$` is not legal, nor is `struct` or `class`.
144
145 The optional `type` in an `object` is the C type. It defaults to `PyObject *`.
146 The objects before the "--" are the objects on top of the stack at the start of
147 the instruction. Those after the "--" are the objects on top of the stack at the
148 end of the instruction.
149
150
151 An `inst` without `stack_effect` is a transitional form to allow the original C code
152 definitions to be copied. It lacks information to generate anything other than the
153 interpreter, but is useful for initial porting of code.
154
155 Stack effect names may be `unused`, indicating the space is to be reserved
156 but no use of it will be made in the instruction definition.
157 This is useful to ensure that all instructions in a family have the same
158 stack effect.
159
160 The number in a `stream` define how many codeunits are consumed from the
161 instruction stream. It returns a 16, 32 or 64 bit value.
162 If the name is `unused` the size can be any value and that many codeunits
163 will be skipped in the instruction stream.
164
165 By convention cache effects (`stream`) must precede the input effects.
166
167 The name `oparg` is pre-defined as a 32 bit value fetched from the instruction stream.
168
169 ### Special instruction annotations
170
171 Instruction headers may be prefixed by one or more annotations. The non-exhaustive
172 list of annotations and their meanings are as follows:
173
174 * `override`. For external use by other interpreter definitions to override the current
175 instruction definition.
176 * `pure`. This instruction has no side effects.
177 * 'tierN'. This instruction is only used by the tier N interpreter.
178
179 ### Special functions/macros
180
181 The C code may include special functions and macros that are understood by the tools as
182 part of the DSL.
183
184 Those include:
185
186 * `DEOPT_IF(cond, instruction)`. Deoptimize if `cond` is met.
187 * `ERROR_IF(cond)`. Jump to error handler if `cond` is true.
188 * `DECREF_INPUTS()`. Generate `Py_DECREF()` calls for the input stack effects.
189 * `SYNC_SP()`. Synchronizes the physical stack pointer with the stack effects.
190 * `INSTRUCTION_SIZE`. Replaced with the size of the instruction which is equal
191 to `1 + INLINE_CACHE_ENTRIES`.
192
193 Note that the use of `DECREF_INPUTS()` is optional -- manual calls
194 to `Py_DECREF()` or other approaches are also acceptable
195 (e.g. calling an API that "steals" a reference).
196
197 Variables can either be defined in the input, output, or in the C code.
198 Variables defined in the input may not be assigned in the C code.
199 If an `ERROR_IF` occurs, all values will be removed from the stack;
200 they must already be `DECREF`'ed by the code block.
201 If a `DEOPT_IF` occurs, no values will be removed from the stack or
202 the instruction stream; no values must have been `DECREF`'ed or created.
203
204 These requirements result in the following constraints on the use of
205 `DEOPT_IF` and `ERROR_IF` in any instruction's code block:
206
207 1. Until the last `DEOPT_IF`, no objects may be allocated, `INCREF`ed,
208 or `DECREF`ed.
209 2. Before the first `ERROR_IF`, all input values must be `DECREF`ed,
210 and no objects may be allocated or `INCREF`ed, with the exception
211 of attempting to create an object and checking for success using
212 `ERROR_IF(result == NULL)`. (TODO: Unclear what to do with
213 intermediate results.)
214 3. No `DEOPT_IF` may follow an `ERROR_IF` in the same block.
215
216 (There is some wiggle room: these rules apply to dynamic code paths,
217 not to static occurrences in the source code.)
218
219 If code detects an error condition before the first `DECREF` of an input,
220 two idioms are valid:
221
222 - Use `goto error`.
223 - Use a block containing the appropriate `DECREF` calls ending in
224 `ERROR_IF(true)`.
225
226 An example of the latter would be:
227 ```cc
228 res = PyObject_Add(left, right);
229 if (res == NULL) {
230 DECREF_INPUTS();
231 ERROR_IF(true);
232 }
233 ```
234
235 ### Semantics
236
237 The underlying execution model is a stack machine.
238 Operations pop values from the stack, and push values to the stack.
239 They also can look at, and consume, values from the instruction stream.
240
241 All members of a family
242 (which represents a specializable instruction and its specializations)
243 must have the same stack and instruction stream effect.
244
245 The same is true for all members of a pseudo instruction
246 (which is mapped by the bytecode compiler to one of its members).
247
248 ## Examples
249
250 (Another source of examples can be found in the
251 [tests](https://github.com/python/cpython/blob/main/Lib/test/test_generated_cases.py).)
252
253 Some examples:
254
255 ### Output stack effect
256 ```C
257 inst ( LOAD_FAST, (-- value) ) {
258 value = frame->f_localsplus[oparg];
259 Py_INCREF(value);
260 }
261 ```
262 This would generate:
263 ```C
264 TARGET(LOAD_FAST) {
265 PyObject *value;
266 value = frame->f_localsplus[oparg];
267 Py_INCREF(value);
268 PUSH(value);
269 DISPATCH();
270 }
271 ```
272
273 ### Input stack effect
274 ```C
275 inst ( STORE_FAST, (value --) ) {
276 SETLOCAL(oparg, value);
277 }
278 ```
279 This would generate:
280 ```C
281 TARGET(STORE_FAST) {
282 PyObject *value = PEEK(1);
283 SETLOCAL(oparg, value);
284 STACK_SHRINK(1);
285 DISPATCH();
286 }
287 ```
288
289 ### Input stack effect and cache effect
290 ```C
291 op ( CHECK_OBJECT_TYPE, (owner, type_version/2 -- owner) ) {
292 PyTypeObject *tp = Py_TYPE(owner);
293 assert(type_version != 0);
294 DEOPT_IF(tp->tp_version_tag != type_version);
295 }
296 ```
297 This might become (if it was an instruction):
298 ```C
299 TARGET(CHECK_OBJECT_TYPE) {
300 PyObject *owner = PEEK(1);
301 uint32 type_version = read32(next_instr);
302 PyTypeObject *tp = Py_TYPE(owner);
303 assert(type_version != 0);
304 DEOPT_IF(tp->tp_version_tag != type_version);
305 next_instr += 2;
306 DISPATCH();
307 }
308 ```
309
310 ### More examples
311
312 For explanations see "Generating the interpreter" below.
313 ```C
314 op ( CHECK_HAS_INSTANCE_VALUES, (owner -- owner) ) {
315 PyDictOrValues dorv = *_PyObject_DictOrValuesPointer(owner);
316 DEOPT_IF(!_PyDictOrValues_IsValues(dorv));
317 }
318 ```
319 ```C
320 op ( LOAD_INSTANCE_VALUE, (owner, index/1 -- null if (oparg & 1), res) ) {
321 res = _PyDictOrValues_GetValues(dorv)->values[index];
322 DEOPT_IF(res == NULL);
323 Py_INCREF(res);
324 null = NULL;
325 Py_DECREF(owner);
326 }
327 ```
328 ```C
329 macro ( LOAD_ATTR_INSTANCE_VALUE ) =
330 counter/1 + CHECK_OBJECT_TYPE + CHECK_HAS_INSTANCE_VALUES +
331 LOAD_INSTANCE_VALUE + unused/4 ;
332 ```
333 ```C
334 op ( LOAD_SLOT, (owner, index/1 -- null if (oparg & 1), res) ) {
335 char *addr = (char *)owner + index;
336 res = *(PyObject **)addr;
337 DEOPT_IF(res == NULL);
338 Py_INCREF(res);
339 null = NULL;
340 Py_DECREF(owner);
341 }
342 ```
343 ```C
344 macro ( LOAD_ATTR_SLOT ) = counter/1 + CHECK_OBJECT_TYPE + LOAD_SLOT + unused/4;
345 ```
346 ```C
347 inst ( BUILD_TUPLE, (items[oparg] -- tuple) ) {
348 tuple = _PyTuple_FromArraySteal(items, oparg);
349 ERROR_IF(tuple == NULL);
350 }
351 ```
352 ```C
353 inst ( PRINT_EXPR ) {
354 PyObject *value = POP();
355 PyObject *hook = _PySys_GetAttr(tstate, &_Py_ID(displayhook));
356 PyObject *res;
357 if (hook == NULL) {
358 _PyErr_SetString(tstate, PyExc_RuntimeError,
359 "lost sys.displayhook");
360 Py_DECREF(value);
361 goto error;
362 }
363 res = PyObject_CallOneArg(hook, value);
364 Py_DECREF(value);
365 ERROR_IF(res == NULL);
366 Py_DECREF(res);
367 }
368 ```
369
370 ### Defining an instruction family
371
372 A _family_ maps a specializable instruction to its specializations.
373
374 Example: These opcodes all share the same instruction format:
375 ```C
376 family(load_attr) = { LOAD_ATTR, LOAD_ATTR_INSTANCE_VALUE, LOAD_SLOT };
377 ```
378
379 ### Defining a pseudo instruction
380
381 A _pseudo instruction_ is used by the bytecode compiler to represent a set of possible concrete instructions.
382
383 Example: `JUMP` may expand to `JUMP_FORWARD` or `JUMP_BACKWARD`:
384 ```C
385 pseudo(JUMP) = { JUMP_FORWARD, JUMP_BACKWARD };
386 ```
387
388
389 ## Generating the interpreter
390
391 The generated C code for a single instruction includes a preamble and dispatch at the end
392 which can be easily inserted. What is more complex is ensuring the correct stack effects
393 and not generating excess pops and pushes.
394
395 For example, in `CHECK_HAS_INSTANCE_VALUES`, `owner` occurs in the input, so it cannot be
396 redefined. Thus, it doesn't need to be written and can be read without adjusting the stack pointer.
397 The C code generated for `CHECK_HAS_INSTANCE_VALUES` would look something like:
398
399 ```C
400 {
401 PyObject *owner = stack_pointer[-1];
402 PyDictOrValues dorv = *_PyObject_DictOrValuesPointer(owner);
403 DEOPT_IF(!_PyDictOrValues_IsValues(dorv));
404 }
405 ```
406
407 When combining ops to form instructions, temporary values should be used,
408 rather than popping and pushing, such that `LOAD_ATTR_SLOT` would look something like:
409
410 ```C
411 case LOAD_ATTR_SLOT: {
412 PyObject *s1 = stack_pointer[-1];
413 /* CHECK_OBJECT_TYPE */
414 {
415 PyObject *owner = s1;
416 uint32_t type_version = read32(next_instr + 1);
417 PyTypeObject *tp = Py_TYPE(owner);
418 assert(type_version != 0);
419 if (tp->tp_version_tag != type_version) goto deopt;
420 }
421 /* LOAD_SLOT */
422 {
423 PyObject *owner = s1;
424 uint16_t index = *(next_instr + 1 + 2);
425 char *addr = (char *)owner + index;
426 PyObject *null;
427 PyObject *res = *(PyObject **)addr;
428 if (res == NULL) goto deopt;
429 Py_INCREF(res);
430 null = NULL;
431 Py_DECREF(owner);
432 if (oparg & 1) {
433 stack_pointer[0] = null;
434 stack_pointer += 1;
435 }
436 s1 = res;
437 }
438 next_instr += (1 + 1 + 2 + 1 + 4);
439 stack_pointer[-1] = s1;
440 DISPATCH();
441 }
442 ```
443
444 ## Other tools
445
446 From the instruction definitions we can generate the stack marking code used in `frame.set_lineno()`,
447 and the tables for use by disassemblers.