Debian Codegraph @

Include/internal/pycore_optimizer.h

raw
1 #ifndef Py_INTERNAL_OPTIMIZER_H
2 #define Py_INTERNAL_OPTIMIZER_H
3 #ifdef __cplusplus
4 extern "C" {
5 #endif
6
7 #ifndef Py_BUILD_CORE
8 # error "this header requires Py_BUILD_CORE define"
9 #endif
10
11 #include "pycore_typedefs.h" // _PyInterpreterFrame
12 #include "pycore_uop_ids.h"
13 #include <stdbool.h>
14
15
16 typedef struct _PyExecutorLinkListNode {
17 struct _PyExecutorObject *next;
18 struct _PyExecutorObject *previous;
19 } _PyExecutorLinkListNode;
20
21
22 /* Bloom filter with m = 256
23 * https://en.wikipedia.org/wiki/Bloom_filter */
24 #define _Py_BLOOM_FILTER_WORDS 8
25
26 typedef struct {
27 uint32_t bits[_Py_BLOOM_FILTER_WORDS];
28 } _PyBloomFilter;
29
30 typedef struct {
31 uint8_t opcode;
32 uint8_t oparg;
33 uint8_t valid:1;
34 uint8_t linked:1;
35 uint8_t chain_depth:6; // Must be big enough for MAX_CHAIN_DEPTH - 1.
36 bool warm;
37 int index; // Index of ENTER_EXECUTOR (if code isn't NULL, below).
38 _PyBloomFilter bloom;
39 _PyExecutorLinkListNode links;
40 PyCodeObject *code; // Weak (NULL if no corresponding ENTER_EXECUTOR).
41 } _PyVMData;
42
43 /* Depending on the format,
44 * the 32 bits between the oparg and operand are:
45 * UOP_FORMAT_TARGET:
46 * uint32_t target;
47 * UOP_FORMAT_JUMP
48 * uint16_t jump_target;
49 * uint16_t error_target;
50 */
51 typedef struct {
52 uint16_t opcode:15;
53 uint16_t format:1;
54 uint16_t oparg;
55 union {
56 uint32_t target;
57 struct {
58 uint16_t jump_target;
59 uint16_t error_target;
60 };
61 };
62 uint64_t operand0; // A cache entry
63 uint64_t operand1;
64 #ifdef Py_STATS
65 uint64_t execution_count;
66 #endif
67 } _PyUOpInstruction;
68
69 typedef struct {
70 uint32_t target;
71 _Py_BackoffCounter temperature;
72 struct _PyExecutorObject *executor;
73 } _PyExitData;
74
75 typedef struct _PyExecutorObject {
76 PyObject_VAR_HEAD
77 const _PyUOpInstruction *trace;
78 _PyVMData vm_data; /* Used by the VM, but opaque to the optimizer */
79 uint32_t exit_count;
80 uint32_t code_size;
81 size_t jit_size;
82 void *jit_code;
83 void *jit_side_entry;
84 _PyExitData exits[1];
85 } _PyExecutorObject;
86
87 /* If pending deletion list gets large enough, then scan,
88 * and free any executors that aren't executing
89 * i.e. any that aren't a thread's current_executor. */
90 #define EXECUTOR_DELETE_LIST_MAX 100
91
92 // Export for '_opcode' shared extension (JIT compiler).
93 PyAPI_FUNC(_PyExecutorObject*) _Py_GetExecutor(PyCodeObject *code, int offset);
94
95 void _Py_ExecutorInit(_PyExecutorObject *, const _PyBloomFilter *);
96 void _Py_ExecutorDetach(_PyExecutorObject *);
97 void _Py_BloomFilter_Init(_PyBloomFilter *);
98 void _Py_BloomFilter_Add(_PyBloomFilter *bloom, void *obj);
99 PyAPI_FUNC(void) _Py_Executor_DependsOn(_PyExecutorObject *executor, void *obj);
100
101 #define _Py_MAX_ALLOWED_BUILTINS_MODIFICATIONS 3
102 #define _Py_MAX_ALLOWED_GLOBALS_MODIFICATIONS 6
103
104 #ifdef _Py_TIER2
105 PyAPI_FUNC(void) _Py_Executors_InvalidateDependency(PyInterpreterState *interp, void *obj, int is_invalidation);
106 PyAPI_FUNC(void) _Py_Executors_InvalidateAll(PyInterpreterState *interp, int is_invalidation);
107 PyAPI_FUNC(void) _Py_Executors_InvalidateCold(PyInterpreterState *interp);
108
109 #else
110 # define _Py_Executors_InvalidateDependency(A, B, C) ((void)0)
111 # define _Py_Executors_InvalidateAll(A, B) ((void)0)
112 # define _Py_Executors_InvalidateCold(A) ((void)0)
113
114 #endif
115
116 // Used as the threshold to trigger executor invalidation when
117 // trace_run_counter is greater than this value.
118 #define JIT_CLEANUP_THRESHOLD 100000
119
120 // This is the length of the trace we project initially.
121 #define UOP_MAX_TRACE_LENGTH 800
122
123 #define TRACE_STACK_SIZE 5
124
125 int _Py_uop_analyze_and_optimize(_PyInterpreterFrame *frame,
126 _PyUOpInstruction *trace, int trace_len, int curr_stackentries,
127 _PyBloomFilter *dependencies);
128
129 extern PyTypeObject _PyUOpExecutor_Type;
130
131
132 #define UOP_FORMAT_TARGET 0
133 #define UOP_FORMAT_JUMP 1
134
135 static inline uint32_t uop_get_target(const _PyUOpInstruction *inst)
136 {
137 assert(inst->format == UOP_FORMAT_TARGET);
138 return inst->target;
139 }
140
141 static inline uint16_t uop_get_jump_target(const _PyUOpInstruction *inst)
142 {
143 assert(inst->format == UOP_FORMAT_JUMP);
144 return inst->jump_target;
145 }
146
147 static inline uint16_t uop_get_error_target(const _PyUOpInstruction *inst)
148 {
149 assert(inst->format != UOP_FORMAT_TARGET);
150 return inst->error_target;
151 }
152
153 // Holds locals, stack, locals, stack ... co_consts (in that order)
154 #define MAX_ABSTRACT_INTERP_SIZE 4096
155
156 #define TY_ARENA_SIZE (UOP_MAX_TRACE_LENGTH * 5)
157
158 // Need extras for root frame and for overflow frame (see TRACE_STACK_PUSH())
159 #define MAX_ABSTRACT_FRAME_DEPTH (TRACE_STACK_SIZE + 2)
160
161 // The maximum number of side exits that we can take before requiring forward
162 // progress (and inserting a new ENTER_EXECUTOR instruction). In practice, this
163 // is the "maximum amount of polymorphism" that an isolated trace tree can
164 // handle before rejoining the rest of the program.
165 #define MAX_CHAIN_DEPTH 4
166
167 /* Symbols */
168 /* See explanation in optimizer_symbols.c */
169
170
171 typedef enum _JitSymType {
172 JIT_SYM_UNKNOWN_TAG = 1,
173 JIT_SYM_NULL_TAG = 2,
174 JIT_SYM_NON_NULL_TAG = 3,
175 JIT_SYM_BOTTOM_TAG = 4,
176 JIT_SYM_TYPE_VERSION_TAG = 5,
177 JIT_SYM_KNOWN_CLASS_TAG = 6,
178 JIT_SYM_KNOWN_VALUE_TAG = 7,
179 JIT_SYM_TUPLE_TAG = 8,
180 JIT_SYM_TRUTHINESS_TAG = 9,
181 } JitSymType;
182
183 typedef struct _jit_opt_known_class {
184 uint8_t tag;
185 uint32_t version;
186 PyTypeObject *type;
187 } JitOptKnownClass;
188
189 typedef struct _jit_opt_known_version {
190 uint8_t tag;
191 uint32_t version;
192 } JitOptKnownVersion;
193
194 typedef struct _jit_opt_known_value {
195 uint8_t tag;
196 PyObject *value;
197 } JitOptKnownValue;
198
199 #define MAX_SYMBOLIC_TUPLE_SIZE 7
200
201 typedef struct _jit_opt_tuple {
202 uint8_t tag;
203 uint8_t length;
204 uint16_t items[MAX_SYMBOLIC_TUPLE_SIZE];
205 } JitOptTuple;
206
207 typedef struct {
208 uint8_t tag;
209 bool invert;
210 uint16_t value;
211 } JitOptTruthiness;
212
213 typedef union _jit_opt_symbol {
214 uint8_t tag;
215 JitOptKnownClass cls;
216 JitOptKnownValue value;
217 JitOptKnownVersion version;
218 JitOptTuple tuple;
219 JitOptTruthiness truthiness;
220 } JitOptSymbol;
221
222
223
224 struct _Py_UOpsAbstractFrame {
225 // Max stacklen
226 int stack_len;
227 int locals_len;
228
229 JitOptSymbol **stack_pointer;
230 JitOptSymbol **stack;
231 JitOptSymbol **locals;
232 };
233
234 typedef struct _Py_UOpsAbstractFrame _Py_UOpsAbstractFrame;
235
236 typedef struct ty_arena {
237 int ty_curr_number;
238 int ty_max_number;
239 JitOptSymbol arena[TY_ARENA_SIZE];
240 } ty_arena;
241
242 typedef struct _JitOptContext {
243 char done;
244 char out_of_space;
245 bool contradiction;
246 // The current "executing" frame.
247 _Py_UOpsAbstractFrame *frame;
248 _Py_UOpsAbstractFrame frames[MAX_ABSTRACT_FRAME_DEPTH];
249 int curr_frame_depth;
250
251 // Arena for the symbolic types.
252 ty_arena t_arena;
253
254 JitOptSymbol **n_consumed;
255 JitOptSymbol **limit;
256 JitOptSymbol *locals_and_stack[MAX_ABSTRACT_INTERP_SIZE];
257 } JitOptContext;
258
259 extern bool _Py_uop_sym_is_null(JitOptSymbol *sym);
260 extern bool _Py_uop_sym_is_not_null(JitOptSymbol *sym);
261 extern bool _Py_uop_sym_is_const(JitOptContext *ctx, JitOptSymbol *sym);
262 extern PyObject *_Py_uop_sym_get_const(JitOptContext *ctx, JitOptSymbol *sym);
263 extern JitOptSymbol *_Py_uop_sym_new_unknown(JitOptContext *ctx);
264 extern JitOptSymbol *_Py_uop_sym_new_not_null(JitOptContext *ctx);
265 extern JitOptSymbol *_Py_uop_sym_new_type(
266 JitOptContext *ctx, PyTypeObject *typ);
267 extern JitOptSymbol *_Py_uop_sym_new_const(JitOptContext *ctx, PyObject *const_val);
268 extern JitOptSymbol *_Py_uop_sym_new_null(JitOptContext *ctx);
269 extern bool _Py_uop_sym_has_type(JitOptSymbol *sym);
270 extern bool _Py_uop_sym_matches_type(JitOptSymbol *sym, PyTypeObject *typ);
271 extern bool _Py_uop_sym_matches_type_version(JitOptSymbol *sym, unsigned int version);
272 extern void _Py_uop_sym_set_null(JitOptContext *ctx, JitOptSymbol *sym);
273 extern void _Py_uop_sym_set_non_null(JitOptContext *ctx, JitOptSymbol *sym);
274 extern void _Py_uop_sym_set_type(JitOptContext *ctx, JitOptSymbol *sym, PyTypeObject *typ);
275 extern bool _Py_uop_sym_set_type_version(JitOptContext *ctx, JitOptSymbol *sym, unsigned int version);
276 extern void _Py_uop_sym_set_const(JitOptContext *ctx, JitOptSymbol *sym, PyObject *const_val);
277 extern bool _Py_uop_sym_is_bottom(JitOptSymbol *sym);
278 extern int _Py_uop_sym_truthiness(JitOptContext *ctx, JitOptSymbol *sym);
279 extern PyTypeObject *_Py_uop_sym_get_type(JitOptSymbol *sym);
280 extern bool _Py_uop_sym_is_immortal(JitOptSymbol *sym);
281 extern JitOptSymbol *_Py_uop_sym_new_tuple(JitOptContext *ctx, int size, JitOptSymbol **args);
282 extern JitOptSymbol *_Py_uop_sym_tuple_getitem(JitOptContext *ctx, JitOptSymbol *sym, int item);
283 extern int _Py_uop_sym_tuple_length(JitOptSymbol *sym);
284 extern JitOptSymbol *_Py_uop_sym_new_truthiness(JitOptContext *ctx, JitOptSymbol *value, bool truthy);
285
286 extern void _Py_uop_abstractcontext_init(JitOptContext *ctx);
287 extern void _Py_uop_abstractcontext_fini(JitOptContext *ctx);
288
289 extern _Py_UOpsAbstractFrame *_Py_uop_frame_new(
290 JitOptContext *ctx,
291 PyCodeObject *co,
292 int curr_stackentries,
293 JitOptSymbol **args,
294 int arg_len);
295 extern int _Py_uop_frame_pop(JitOptContext *ctx);
296
297 PyAPI_FUNC(PyObject *) _Py_uop_symbols_test(PyObject *self, PyObject *ignored);
298
299 PyAPI_FUNC(int) _PyOptimizer_Optimize(_PyInterpreterFrame *frame, _Py_CODEUNIT *start, _PyExecutorObject **exec_ptr, int chain_depth);
300
301 static inline int is_terminator(const _PyUOpInstruction *uop)
302 {
303 int opcode = uop->opcode;
304 return (
305 opcode == _EXIT_TRACE ||
306 opcode == _JUMP_TO_TOP
307 );
308 }
309
310 PyAPI_FUNC(int) _PyDumpExecutors(FILE *out);
311 #ifdef _Py_TIER2
312 extern void _Py_ClearExecutorDeletionList(PyInterpreterState *interp);
313 #endif
314
315 #ifdef __cplusplus
316 }
317 #endif
318 #endif /* !Py_INTERNAL_OPTIMIZER_H */