Where Online Learning is simpler!
The C and C++ Include Header Files
cat -n /usr/include/python3.14/internal/pycore_optimizer.h
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 */
