Move uop optimizer to ceval.c so it can use static functions defined …

…there
gvanrossum · Jun 27, 2023 · Jun 17, 2023 · Jun 17, 2023 · Jun 18, 2023 · Jun 19, 2023
commit 8fd4a710f92f78ee32f48e4b1215b590f14271e5
@@ -2763,3 +2763,280 @@ void Py_LeaveRecursiveCall(void)
 {
     _Py_LeaveRecursiveCall();
 }
+
+///////////////////// Experimental UOp Interpreter /////////////////////
+
+typedef struct {
+    _PyOptimizerObject base;
+    int traces_executed;
+    int instrs_executed;
+} UOpOptimizerObject;
+
+#define MAX_TRACE_LENGTH 16
+
+// UOp opcodes are outside the range of bytecodes or pseudo ops
+#define EXIT_TRACE 512
+#define SET_IP 513
+// TODO: Generate these in Tools/cases_generator
+#define _BINARY_OP_MULTIPLY_FLOAT 514
+#define _BINARY_OP_ADD_FLOAT 515
+#define _BINARY_OP_SUBTRACT_FLOAT 516
+#define _BINARY_OP_MULTIPLY_INT 517
+#define _BINARY_OP_ADD_INT 518
+#define _BINARY_OP_SUBTRACT_INT 519
+#define _BINARY_OP_ADD_UNICODE 520
+#define _GUARD_BOTH_INT 521
+#define _GUARD_BOTH_FLOAT 522
+#define _GUARD_BOTH_UNICODE 523
+
+typedef struct {
+    int opcode;
+    int oparg;
+} uop_instruction;
+
+typedef struct {
+    _PyExecutorObject executor;  // Base
+    UOpOptimizerObject *optimizer;
+    uop_instruction trace[MAX_TRACE_LENGTH];  // TODO: variable length
+} UOpExecutorObject;
+
+static void
+uop_dealloc(UOpExecutorObject *self) {
+    Py_DECREF(self->optimizer);
+    PyObject_Free(self);
+}
+
+static PyTypeObject UOpExecutor_Type = {
+    PyVarObject_HEAD_INIT(&PyType_Type, 0)
+    .tp_name = "uop_executor",
+    .tp_basicsize = sizeof(UOpExecutorObject),
+    .tp_itemsize = 0,
+    .tp_flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_DISALLOW_INSTANTIATION,
+    .tp_dealloc = (destructor)uop_dealloc,
+};
+
+static _PyInterpreterFrame *
+uop_execute(_PyExecutorObject *executor, _PyInterpreterFrame *frame, PyObject **stack_pointer)
+{
+#ifdef LLTRACE
+    int lltrace = PyDict_Contains(GLOBALS(), &_Py_ID(__lltrace__));
+    char *uop_debug = Py_GETENV("PYTHON_UOP_DEBUG");
+    if (uop_debug != NULL && *uop_debug >= '2') {
+        lltrace = 2;
+    }
+#endif
+    UOpExecutorObject *self = (UOpExecutorObject *)executor;
+    self->optimizer->traces_executed++;
+    _Py_CODEUNIT *ip_offset = (_Py_CODEUNIT *)_PyFrame_GetCode(frame)->co_code_adaptive - 1;
+    int pc = 0;
+    int opcode;
+    int oparg;
+    for (;;) {
+        opcode = self->trace[pc].opcode;
+        oparg = self->trace[pc].oparg;
+#ifdef LLTRACE
+        if (lltrace) {
+            // TODO: Print line numbers; uop names.
+            const char *opname = opcode < 256 ? _PyOpcode_OpName[opcode] : "";
+            int stack_level = (int)(stack_pointer - _PyFrame_Stackbase(frame));
+            fprintf(stderr, "uop %s %d, oparg %d, stack_level %d\n",
+                    opname, opcode, oparg, stack_level);
+        }
+#endif
+        pc++;
+        self->optimizer->instrs_executed++;
+        switch (opcode) {
+
+#undef ENABLE_SPECIALIZATION
+#define ENABLE_SPECIALIZATION 0
+#include "executor_cases.c.h"
+
+            case SET_IP:
+            {
+                frame->prev_instr = ip_offset + oparg;
+                break;
+            }
+
+            case EXIT_TRACE:
+            {
+                _PyFrame_SetStackPointer(frame, stack_pointer);
+                Py_DECREF(self);
+                return frame;
+            }
+
+            default:
+            {
+                fprintf(stderr, "Unknown uop %d, oparg %d\n", opcode, oparg);
+                Py_FatalError("Unknown uop");
+                abort();  // Unreachable
+                for (;;) {}
+                // Really unreachable
+            }
+
+        }
+    }
+
+pop_4_error:
+    STACK_SHRINK(1);
+pop_3_error:
+    STACK_SHRINK(1);
+pop_2_error:
+    STACK_SHRINK(1);
+pop_1_error:
+    STACK_SHRINK(1);
+error:
+    // On ERROR_IF we return NULL as the frame.
+    // The caller recovers the frame from cframe.current_frame.
+#ifdef LLTRACE
+    if (lltrace) {
+        fprintf(stderr, "error: [Opcode %d, oparg %d]\n", opcode, oparg);
+    }
+#endif
+    _PyFrame_SetStackPointer(frame, stack_pointer);
+    Py_DECREF(self);
+    return NULL;
+
+PREDICTED(UNPACK_SEQUENCE)
+PREDICTED(COMPARE_OP)
+PREDICTED(LOAD_SUPER_ATTR)
+PREDICTED(STORE_SUBSCR)
+PREDICTED(BINARY_SUBSCR)
+PREDICTED(BINARY_OP)
+    // On DEOPT_IF we just repeat the last instruction.
+    // This presumes nothing was popped from the stack (nor pushed).
+#ifdef LLTRACE
+    if (lltrace) {
+        fprintf(stderr, "DEOPT: [Opcode %d, oparg %d]\n", opcode, oparg);
+    }
+#endif
+    _PyFrame_SetStackPointer(frame, stack_pointer);
+    Py_DECREF(self);
+    return frame;
+}
+
+static int
+translate_bytecode_to_trace(
+    PyCodeObject *code,
+    _Py_CODEUNIT *instr,
+    uop_instruction *trace,
+    int max_length)
+{
+#define ADD_TO_TRACE(OPCODE, OPARG) \
+        /* fprintf(stderr, "ADD_TO_TRACE(%d, %d)\n", (OPCODE), (OPARG)); */ \
+        trace[trace_length].opcode = (OPCODE); \
+        trace[trace_length].oparg = (OPARG); \
+        trace_length++;
+
+    int trace_length = 0;
+    // ALways reserve space for one uop, plus SET_UP, plus EXIT_TRACE
+    while (trace_length + 3 <= max_length) {
+        int opcode = instr->op.code;
+        int oparg = instr->op.arg;
+        switch (opcode) {
+            case LOAD_FAST_LOAD_FAST:
+            {
+                // Reserve space for two uops (+ SETUP + EXIT_TRACE)
+                if (trace_length + 4 > max_length) {
+                    goto done;
+                }
+                int oparg1 = oparg >> 4;
+                int oparg2 = oparg & 15;
+                ADD_TO_TRACE(LOAD_FAST, oparg1);
+                ADD_TO_TRACE(LOAD_FAST, oparg2);
+                break;
+            }
+            default:
+            {
+                if (OPCODE_IS_UOP(opcode)) {
+                    ADD_TO_TRACE(opcode, oparg);
+                    break;
+                }
+                // fprintf(stderr, "Unsupported opcode %d\n", opcode);
+                goto done;  // Break out of while loop
+            }
+        }
+        instr++;
+        // Add cache size for opcode
+        instr += _PyOpcode_Caches[_PyOpcode_Deopt[opcode]];
+        ADD_TO_TRACE(SET_IP, (int)(instr - (_Py_CODEUNIT *)code->co_code_adaptive));
+    }
+done:
+    if (trace_length > 0) {
+        ADD_TO_TRACE(EXIT_TRACE, 0);
+        // fprintf(stderr, "Created a new trace of length %d\n", trace_length);
+    }
+    return trace_length;
+
+#undef ADD_TO_TRACE
+}
+
+static int
+uop_optimize(
+    _PyOptimizerObject *self,
+    PyCodeObject *code,
+    _Py_CODEUNIT *instr,
+    _PyExecutorObject **exec_ptr)
+{
+    uop_instruction trace[MAX_TRACE_LENGTH];
+    int trace_length = translate_bytecode_to_trace(code, instr, trace, MAX_TRACE_LENGTH);
+    if (trace_length <= 0) {
+        // Error or nothing translated
+        return trace_length;
+    }
+    UOpExecutorObject *executor = (UOpExecutorObject *)_PyObject_New(&UOpExecutor_Type);
+    if (executor == NULL) {
+        return -1;
+    }
+#ifdef Py_DEBUG
+    char *uop_debug = Py_GETENV("PYTHON_UOP_DEBUG");
+    if (uop_debug != NULL && *uop_debug >= '1') {
+        fprintf(stderr, "Optimizing %s (%s:%d) at offset %ld -- %d uops\n",
+                PyUnicode_AsUTF8(code->co_qualname),
+                PyUnicode_AsUTF8(code->co_filename),
+                code->co_firstlineno,
+                (long)(instr - (_Py_CODEUNIT *)code->co_code_adaptive),
+                trace_length);
+    }
+#endif
+    executor->executor.execute = uop_execute;
+    Py_INCREF(self);
+    executor->optimizer = (UOpOptimizerObject *)self;
+    memcpy(executor->trace, trace, trace_length * sizeof(uop_instruction));
+    *exec_ptr = (_PyExecutorObject *)executor;
+    return 1;
+}
+
+static PyMemberDef uop_members[] = {
+    {"traces_executed", Py_T_INT, offsetof(UOpOptimizerObject, traces_executed), 0,
+     "Total number of traces executed since inception"},
+    {"instrs_executed", Py_T_INT, offsetof(UOpOptimizerObject, instrs_executed), 0,
+     "Total number of instructions executed since inception"},
+    {NULL}
+};
+
+static PyTypeObject UOpOptimizer_Type = {
+    PyVarObject_HEAD_INIT(&PyType_Type, 0)
+    .tp_name = "UOp Optimizer",
+    .tp_basicsize = sizeof(UOpOptimizerObject),
+    .tp_itemsize = 0,
+    .tp_flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_DISALLOW_INSTANTIATION,
+    .tp_members = uop_members,
+};
+
+PyObject *
+PyUnstable_Optimizer_NewUOpOptimizer(void)
+{
+    if (PyType_Ready(&UOpOptimizer_Type) < 0) {
+        return NULL;
+    }
+    UOpOptimizerObject *opt = (UOpOptimizerObject *)_PyObject_New(&UOpOptimizer_Type);
+    if (opt == NULL) {
+        return NULL;
+    }
+    opt->base.optimize = uop_optimize;
+    opt->base.resume_threshold = UINT16_MAX;
+    opt->base.backedge_threshold = 0;
+    opt->traces_executed = 0;
+    opt->instrs_executed = 0;
+    return (PyObject *)opt;
+}