python3.13/internal/pycore_optimizer.h

0001 #ifndef Py_INTERNAL_OPTIMIZER_H
0002 #define Py_INTERNAL_OPTIMIZER_H
0003 #ifdef __cplusplus
0004 extern "C" {
0005 #endif
0006
0007 #ifndef Py_BUILD_CORE
0008 #  error "this header requires Py_BUILD_CORE define"
0009 #endif
0010
0011 #include "pycore_uop_ids.h"
0012 #include <stdbool.h>
0013
0014
0015 typedef struct _PyExecutorLinkListNode {
0016     struct _PyExecutorObject *next;
0017     struct _PyExecutorObject *previous;
0018 } _PyExecutorLinkListNode;
0019
0020
0021 /* Bloom filter with m = 256
0022  * https://en.wikipedia.org/wiki/Bloom_filter */
0023 #define BLOOM_FILTER_WORDS 8
0024
0025 typedef struct _bloom_filter {
0026     uint32_t bits[BLOOM_FILTER_WORDS];
0027 } _PyBloomFilter;
0028
0029 typedef struct {
0030     uint8_t opcode;
0031     uint8_t oparg;
0032     uint8_t valid;
0033     uint8_t linked;
0034     int index;           // Index of ENTER_EXECUTOR (if code isn't NULL, below).
0035     _PyBloomFilter bloom;
0036     _PyExecutorLinkListNode links;
0037     PyCodeObject *code;  // Weak (NULL if no corresponding ENTER_EXECUTOR).
0038 } _PyVMData;
0039
0040 #define UOP_FORMAT_TARGET 0
0041 #define UOP_FORMAT_EXIT 1
0042 #define UOP_FORMAT_JUMP 2
0043 #define UOP_FORMAT_UNUSED 3
0044
0045 /* Depending on the format,
0046  * the 32 bits between the oparg and operand are:
0047  * UOP_FORMAT_TARGET:
0048  *    uint32_t target;
0049  * UOP_FORMAT_EXIT
0050  *    uint16_t exit_index;
0051  *    uint16_t error_target;
0052  * UOP_FORMAT_JUMP
0053  *    uint16_t jump_target;
0054  *    uint16_t error_target;
0055  */
0056 typedef struct {
0057     uint16_t opcode:14;
0058     uint16_t format:2;
0059     uint16_t oparg;
0060     union {
0061         uint32_t target;
0062         struct {
0063             union {
0064                 uint16_t exit_index;
0065                 uint16_t jump_target;
0066             };
0067             uint16_t error_target;
0068         };
0069     };
0070     uint64_t operand;  // A cache entry
0071 } _PyUOpInstruction;
0072
0073 static inline uint32_t uop_get_target(const _PyUOpInstruction *inst)
0074 {
0075     assert(inst->format == UOP_FORMAT_TARGET);
0076     return inst->target;
0077 }
0078
0079 static inline uint16_t uop_get_exit_index(const _PyUOpInstruction *inst)
0080 {
0081     assert(inst->format == UOP_FORMAT_EXIT);
0082     return inst->exit_index;
0083 }
0084
0085 static inline uint16_t uop_get_jump_target(const _PyUOpInstruction *inst)
0086 {
0087     assert(inst->format == UOP_FORMAT_JUMP);
0088     return inst->jump_target;
0089 }
0090
0091 static inline uint16_t uop_get_error_target(const _PyUOpInstruction *inst)
0092 {
0093     assert(inst->format != UOP_FORMAT_TARGET);
0094     return inst->error_target;
0095 }
0096
0097 typedef struct _exit_data {
0098     uint32_t target;
0099     _Py_BackoffCounter temperature;
0100     const struct _PyExecutorObject *executor;
0101 } _PyExitData;
0102
0103 typedef struct _PyExecutorObject {
0104     PyObject_VAR_HEAD
0105     const _PyUOpInstruction *trace;
0106     _PyVMData vm_data; /* Used by the VM, but opaque to the optimizer */
0107     uint32_t exit_count;
0108     uint32_t code_size;
0109     size_t jit_size;
0110     void *jit_code;
0111     void *jit_side_entry;
0112     _PyExitData exits[1];
0113 } _PyExecutorObject;
0114
0115 typedef struct _PyOptimizerObject _PyOptimizerObject;
0116
0117 /* Should return > 0 if a new executor is created. O if no executor is produced and < 0 if an error occurred. */
0118 typedef int (*optimize_func)(
0119     _PyOptimizerObject* self, struct _PyInterpreterFrame *frame,
0120     _Py_CODEUNIT *instr, _PyExecutorObject **exec_ptr,
0121     int curr_stackentries);
0122
0123 struct _PyOptimizerObject {
0124     PyObject_HEAD
0125     optimize_func optimize;
0126     /* Data needed by the optimizer goes here, but is opaque to the VM */
0127 };
0128
0129 /** Test support **/
0130 typedef struct {
0131     _PyOptimizerObject base;
0132     int64_t count;
0133 } _PyCounterOptimizerObject;
0134
0135 _PyOptimizerObject *_Py_SetOptimizer(PyInterpreterState *interp, _PyOptimizerObject* optimizer);
0136
0137 PyAPI_FUNC(int) _Py_SetTier2Optimizer(_PyOptimizerObject* optimizer);
0138
0139 PyAPI_FUNC(_PyOptimizerObject *) _Py_GetOptimizer(void);
0140
0141 PyAPI_FUNC(_PyExecutorObject *) _Py_GetExecutor(PyCodeObject *code, int offset);
0142
0143 void _Py_ExecutorInit(_PyExecutorObject *, const _PyBloomFilter *);
0144 void _Py_ExecutorDetach(_PyExecutorObject *);
0145 void _Py_BloomFilter_Init(_PyBloomFilter *);
0146 void _Py_BloomFilter_Add(_PyBloomFilter *bloom, void *obj);
0147 PyAPI_FUNC(void) _Py_Executor_DependsOn(_PyExecutorObject *executor, void *obj);
0148 /* For testing */
0149 PyAPI_FUNC(PyObject *) _PyOptimizer_NewCounter(void);
0150 PyAPI_FUNC(PyObject *) _PyOptimizer_NewUOpOptimizer(void);
0151
0152 #define _Py_MAX_ALLOWED_BUILTINS_MODIFICATIONS 3
0153 #define _Py_MAX_ALLOWED_GLOBALS_MODIFICATIONS 6
0154
0155 #ifdef _Py_TIER2
0156 PyAPI_FUNC(void) _Py_Executors_InvalidateDependency(PyInterpreterState *interp, void *obj, int is_invalidation);
0157 PyAPI_FUNC(void) _Py_Executors_InvalidateAll(PyInterpreterState *interp, int is_invalidation);
0158 #else
0159 #  define _Py_Executors_InvalidateDependency(A, B, C) ((void)0)
0160 #  define _Py_Executors_InvalidateAll(A, B) ((void)0)
0161 #endif
0162
0163
0164 // This is the length of the trace we project initially.
0165 #define UOP_MAX_TRACE_LENGTH 800
0166
0167 #define TRACE_STACK_SIZE 5
0168
0169 int _Py_uop_analyze_and_optimize(struct _PyInterpreterFrame *frame,
0170     _PyUOpInstruction *trace, int trace_len, int curr_stackentries,
0171     _PyBloomFilter *dependencies);
0172
0173 extern PyTypeObject _PyCounterExecutor_Type;
0174 extern PyTypeObject _PyCounterOptimizer_Type;
0175 extern PyTypeObject _PyDefaultOptimizer_Type;
0176 extern PyTypeObject _PyUOpExecutor_Type;
0177 extern PyTypeObject _PyUOpOptimizer_Type;
0178
0179 /* Symbols */
0180 /* See explanation in optimizer_symbols.c */
0181
0182 struct _Py_UopsSymbol {
0183     int flags;  // 0 bits: Top; 2 or more bits: Bottom
0184     PyTypeObject *typ;  // Borrowed reference
0185     PyObject *const_val;  // Owned reference (!)
0186 };
0187
0188 // Holds locals, stack, locals, stack ... co_consts (in that order)
0189 #define MAX_ABSTRACT_INTERP_SIZE 4096
0190
0191 #define TY_ARENA_SIZE (UOP_MAX_TRACE_LENGTH * 5)
0192
0193 // Need extras for root frame and for overflow frame (see TRACE_STACK_PUSH())
0194 #define MAX_ABSTRACT_FRAME_DEPTH (TRACE_STACK_SIZE + 2)
0195
0196 typedef struct _Py_UopsSymbol _Py_UopsSymbol;
0197
0198 struct _Py_UOpsAbstractFrame {
0199     // Max stacklen
0200     int stack_len;
0201     int locals_len;
0202
0203     _Py_UopsSymbol **stack_pointer;
0204     _Py_UopsSymbol **stack;
0205     _Py_UopsSymbol **locals;
0206 };
0207
0208 typedef struct _Py_UOpsAbstractFrame _Py_UOpsAbstractFrame;
0209
0210 typedef struct ty_arena {
0211     int ty_curr_number;
0212     int ty_max_number;
0213     _Py_UopsSymbol arena[TY_ARENA_SIZE];
0214 } ty_arena;
0215
0216 struct _Py_UOpsContext {
0217     PyObject_HEAD
0218     // The current "executing" frame.
0219     _Py_UOpsAbstractFrame *frame;
0220     _Py_UOpsAbstractFrame frames[MAX_ABSTRACT_FRAME_DEPTH];
0221     int curr_frame_depth;
0222
0223     // Arena for the symbolic types.
0224     ty_arena t_arena;
0225
0226     _Py_UopsSymbol **n_consumed;
0227     _Py_UopsSymbol **limit;
0228     _Py_UopsSymbol *locals_and_stack[MAX_ABSTRACT_INTERP_SIZE];
0229 };
0230
0231 typedef struct _Py_UOpsContext _Py_UOpsContext;
0232
0233 extern bool _Py_uop_sym_is_null(_Py_UopsSymbol *sym);
0234 extern bool _Py_uop_sym_is_not_null(_Py_UopsSymbol *sym);
0235 extern bool _Py_uop_sym_is_const(_Py_UopsSymbol *sym);
0236 extern PyObject *_Py_uop_sym_get_const(_Py_UopsSymbol *sym);
0237 extern _Py_UopsSymbol *_Py_uop_sym_new_unknown(_Py_UOpsContext *ctx);
0238 extern _Py_UopsSymbol *_Py_uop_sym_new_not_null(_Py_UOpsContext *ctx);
0239 extern _Py_UopsSymbol *_Py_uop_sym_new_type(
0240     _Py_UOpsContext *ctx, PyTypeObject *typ);
0241 extern _Py_UopsSymbol *_Py_uop_sym_new_const(_Py_UOpsContext *ctx, PyObject *const_val);
0242 extern _Py_UopsSymbol *_Py_uop_sym_new_null(_Py_UOpsContext *ctx);
0243 extern bool _Py_uop_sym_has_type(_Py_UopsSymbol *sym);
0244 extern bool _Py_uop_sym_matches_type(_Py_UopsSymbol *sym, PyTypeObject *typ);
0245 extern bool _Py_uop_sym_set_null(_Py_UopsSymbol *sym);
0246 extern bool _Py_uop_sym_set_non_null(_Py_UopsSymbol *sym);
0247 extern bool _Py_uop_sym_set_type(_Py_UopsSymbol *sym, PyTypeObject *typ);
0248 extern bool _Py_uop_sym_set_const(_Py_UopsSymbol *sym, PyObject *const_val);
0249 extern bool _Py_uop_sym_is_bottom(_Py_UopsSymbol *sym);
0250 extern int _Py_uop_sym_truthiness(_Py_UopsSymbol *sym);
0251 extern PyTypeObject *_Py_uop_sym_get_type(_Py_UopsSymbol *sym);
0252
0253
0254 extern int _Py_uop_abstractcontext_init(_Py_UOpsContext *ctx);
0255 extern void _Py_uop_abstractcontext_fini(_Py_UOpsContext *ctx);
0256
0257 extern _Py_UOpsAbstractFrame *_Py_uop_frame_new(
0258     _Py_UOpsContext *ctx,
0259     PyCodeObject *co,
0260     int curr_stackentries,
0261     _Py_UopsSymbol **args,
0262     int arg_len);
0263 extern int _Py_uop_frame_pop(_Py_UOpsContext *ctx);
0264
0265 PyAPI_FUNC(PyObject *) _Py_uop_symbols_test(PyObject *self, PyObject *ignored);
0266
0267 PyAPI_FUNC(int) _PyOptimizer_Optimize(struct _PyInterpreterFrame *frame, _Py_CODEUNIT *start, PyObject **stack_pointer, _PyExecutorObject **exec_ptr);
0268
0269 #ifdef __cplusplus
0270 }
0271 #endif
0272 #endif /* !Py_INTERNAL_OPTIMIZER_H */