Merge remote-tracking branch 'upstream/main' into tier2_abstract_inte…

…rpreter
python · Fidget-Spinner · Jan 13, 2024 · Jan 13, 2024 · Jan 13, 2024 · Jan 13, 2024
commit 50154ad69b36f151a8dbabb09ec9657b199c370b
diff --git a/Include/internal/pycore_optimizer.h b/Include/internal/pycore_optimizer.h
@@ -10,8 +10,9 @@ extern "C" {
 
 #define TRACE_STACK_SIZE 5
 
-int _Py_uop_analyze_and_optimize(PyCodeObject *code,
-    _PyUOpInstruction *trace, int trace_len, int curr_stackentries);
+int _Py_uop_analyze_and_optimize(_PyInterpreterFrame *frame,
+    _PyUOpInstruction *trace, int trace_len, int curr_stackentries,
+    _PyBloomFilter *dependencies);
 
 extern PyTypeObject _PyCounterExecutor_Type;
 extern PyTypeObject _PyCounterOptimizer_Type;

diff --git a/Include/internal/pycore_uop_ids.h b/Include/internal/pycore_uop_ids.h
@@ -850,14 +850,14 @@ uop_optimize(
     _PyBloomFilter dependencies;
     _Py_BloomFilter_Init(&dependencies);
     _PyUOpInstruction buffer[UOP_MAX_TRACE_WORKING_LENGTH];
-    int err = translate_bytecode_to_trace(code, instr, buffer, UOP_MAX_TRACE_LENGTH, &dependencies);
+    int err = translate_bytecode_to_trace(frame, instr, buffer, UOP_MAX_TRACE_LENGTH, &dependencies);
     if (err <= 0) {
         // Error or nothing translated
         return err;
     }
     OPT_STAT_INC(traces_created);
-    // This clears its errors, so if it fails it just doesn't optimize.
-    err = _Py_uop_analyze_and_optimize(code, buffer, UOP_MAX_TRACE_WORKING_LENGTH, curr_stackentries);
+    err = _Py_uop_analyze_and_optimize(frame, buffer,
+                                        UOP_MAX_TRACE_WORKING_LENGTH, curr_stackentries, &dependencies);
     if (err <= 0) {
         return err;
     }

@@ -10,6 +10,8 @@
  *
  * */
 #include "Python.h"
+#include "opcode.h"
+#include "pycore_dict.h"
 #include "pycore_interp.h"
 #include "pycore_opcode_metadata.h"
 #include "pycore_opcode_utils.h"
@@ -152,13 +154,6 @@ typedef struct _Py_UOpsAbstractInterpContext {
     _Py_UOpsSymType *locals_and_stack[MAX_ABSTRACT_INTERP_SIZE];
 } _Py_UOpsAbstractInterpContext;
 
-static int
-get_mutations(PyObject* dict) {
-    assert(PyDict_CheckExact(dict));
-    PyDictObject *d = (PyDictObject *)dict;
-    return (d->ma_version_tag >> DICT_MAX_WATCHERS) & ((1 << DICT_WATCHED_MUTATION_BITS)-1);
-}
-
 static void
 abstractinterp_dealloc(_Py_UOpsAbstractInterpContext *self)
 {
@@ -981,6 +976,208 @@ uop_abstract_interpret_single_inst(
 
 }
 
+
+
+static int
+get_mutations(PyObject* dict) {
+    assert(PyDict_CheckExact(dict));
+    PyDictObject *d = (PyDictObject *)dict;
+    return (d->ma_version_tag >> DICT_MAX_WATCHERS) & ((1 << DICT_WATCHED_MUTATION_BITS)-1);
+}
+
+static void
+increment_mutations(PyObject* dict) {
+    assert(PyDict_CheckExact(dict));
+    PyDictObject *d = (PyDictObject *)dict;
+    d->ma_version_tag += (1 << DICT_MAX_WATCHERS);
+}
+
+static int
+globals_watcher_callback(PyDict_WatchEvent event, PyObject* dict,
+                         PyObject* key, PyObject* new_value)
+{
+    if (event == PyDict_EVENT_CLONED) {
+        return 0;
+    }
+    uint64_t watched_mutations = get_mutations(dict);
+    if (watched_mutations < _Py_MAX_ALLOWED_GLOBALS_MODIFICATIONS) {
+        _Py_Executors_InvalidateDependency(_PyInterpreterState_GET(), dict);
+        increment_mutations(dict);
+    }
+    else {
+        PyDict_Unwatch(1, dict);
+    }
+    return 0;
+}
+
+
+static void
+global_to_const(_PyUOpInstruction *inst, PyObject *obj)
+{
+    assert(inst->opcode == _LOAD_GLOBAL_MODULE || inst->opcode == _LOAD_GLOBAL_BUILTINS);
+    assert(PyDict_CheckExact(obj));
+    PyDictObject *dict = (PyDictObject *)obj;
+    assert(dict->ma_keys->dk_kind == DICT_KEYS_UNICODE);
+    PyDictUnicodeEntry *entries = DK_UNICODE_ENTRIES(dict->ma_keys);
+    assert(inst->operand <= UINT16_MAX);
+    PyObject *res = entries[inst->operand].me_value;
+    if (res == NULL) {
+        return;
+    }
+    if (_Py_IsImmortal(res)) {
+        inst->opcode = (inst->oparg & 1) ? _LOAD_CONST_INLINE_BORROW_WITH_NULL : _LOAD_CONST_INLINE_BORROW;
+    }
+    else {
+        inst->opcode = (inst->oparg & 1) ? _LOAD_CONST_INLINE_WITH_NULL : _LOAD_CONST_INLINE;
+    }
+    inst->operand = (uint64_t)res;
+}
+
+static int
+incorrect_keys(_PyUOpInstruction *inst, PyObject *obj)
+{
+    if (!PyDict_CheckExact(obj)) {
+        return 1;
+    }
+    PyDictObject *dict = (PyDictObject *)obj;
+    if (dict->ma_keys->dk_version != inst->operand) {
+        return 1;
+    }
+    return 0;
+}
+
+/* The first two dict watcher IDs are reserved for CPython,
+ * so we don't need to check that they haven't been used */
+#define BUILTINS_WATCHER_ID 0
+#define GLOBALS_WATCHER_ID  1
+
+/* Returns 1 if successfully optimized
+ *         0 if the trace is not suitable for optimization (yet)
+ *        -1 if there was an error. */
+static int
+remove_globals(_PyInterpreterFrame *frame, _PyUOpInstruction *buffer,
+               int buffer_size, _PyBloomFilter *dependencies)
+{
+    PyInterpreterState *interp = _PyInterpreterState_GET();
+    PyObject *builtins = frame->f_builtins;
+    if (builtins != interp->builtins) {
+        return 1;
+    }
+    PyObject *globals = frame->f_globals;
+    assert(PyFunction_Check(((PyFunctionObject *)frame->f_funcobj)));
+    assert(((PyFunctionObject *)frame->f_funcobj)->func_builtins == builtins);
+    assert(((PyFunctionObject *)frame->f_funcobj)->func_globals == globals);
+    /* In order to treat globals as constants, we need to
+     * know that the globals dict is the one we expected, and
+     * that it hasn't changed
+     * In order to treat builtins as constants,  we need to
+     * know that the builtins dict is the one we expected, and
+     * that it hasn't changed and that the global dictionary's
+     * keys have not changed */
+
+    /* These values represent stacks of booleans (one bool per bit).
+     * Pushing a frame shifts left, popping a frame shifts right. */
+    uint32_t builtins_checked = 0;
+    uint32_t builtins_watched = 0;
+    uint32_t globals_checked = 0;
+        uint32_t globals_watched = 0;
+    if (interp->dict_state.watchers[1] == NULL) {
+        interp->dict_state.watchers[1] = globals_watcher_callback;
+    }
+    for (int pc = 0; pc < buffer_size; pc++) {
+        _PyUOpInstruction *inst = &buffer[pc];
+        int opcode = inst->opcode;
+        switch(opcode) {
+            case _GUARD_BUILTINS_VERSION:
+                if (incorrect_keys(inst, builtins)) {
+                    return 0;
+                }
+                if (interp->rare_events.builtin_dict >= _Py_MAX_ALLOWED_BUILTINS_MODIFICATIONS) {
+                    continue;
+                }
+                if ((builtins_watched & 1) == 0) {
+                    PyDict_Watch(BUILTINS_WATCHER_ID, builtins);
+                    builtins_watched |= 1;
+                }
+                if (builtins_checked & 1) {
+                    buffer[pc].opcode = NOP;
+                }
+                else {
+                    buffer[pc].opcode = _CHECK_BUILTINS;
+                    buffer[pc].operand = (uintptr_t)builtins;
+                    builtins_checked |= 1;
+                }
+                break;
+            case _GUARD_GLOBALS_VERSION:
+                if (incorrect_keys(inst, globals)) {
+                    return 0;
+                }
+                uint64_t watched_mutations = get_mutations(globals);
+                if (watched_mutations >= _Py_MAX_ALLOWED_GLOBALS_MODIFICATIONS) {
+                    continue;
+                }
+                if ((globals_watched & 1) == 0) {
+                    PyDict_Watch(GLOBALS_WATCHER_ID, globals);
+                    _Py_BloomFilter_Add(dependencies, globals);
+                    globals_watched |= 1;
+                }
+                if (globals_checked & 1) {
+                    buffer[pc].opcode = NOP;
+                }
+                else {
+                    buffer[pc].opcode = _CHECK_GLOBALS;
+                    buffer[pc].operand = (uintptr_t)globals;
+                    globals_checked |= 1;
+                }
+                break;
+            case _LOAD_GLOBAL_BUILTINS:
+                if (globals_checked & builtins_checked & globals_watched & builtins_watched & 1) {
+                    global_to_const(inst, builtins);
+                }
+                break;
+            case _LOAD_GLOBAL_MODULE:
+                if (globals_checked & globals_watched & 1) {
+                    global_to_const(inst, globals);
+                }
+                break;
+            case _PUSH_FRAME:
+            {
+                globals_checked <<= 1;
+                globals_watched <<= 1;
+                builtins_checked <<= 1;
+                builtins_watched <<= 1;
+                PyFunctionObject *func = (PyFunctionObject *)buffer[pc].operand;
+                if (func == NULL) {
+                    return 1;
+                }
+                assert(PyFunction_Check(func));
+                globals = func->func_globals;
+                builtins = func->func_builtins;
+                if (builtins != interp->builtins) {
+                    return 1;
+                }
+                break;
+            }
+            case _POP_FRAME:
+            {
+                globals_checked >>= 1;
+                globals_watched >>= 1;
+                builtins_checked >>= 1;
+                builtins_watched >>= 1;
+                PyFunctionObject *func = (PyFunctionObject *)buffer[pc].operand;
+                assert(PyFunction_Check(func));
+                globals = func->func_globals;
+                builtins = func->func_builtins;
+                break;
+            }
+            case _JUMP_TO_TOP:
+            case _EXIT_TRACE:
+                return 1;
+        }
+    }
+    return 0;
+}
+
 static int
 uop_abstract_interpret(
     PyCodeObject *co,
@@ -1132,9 +1329,6 @@ remove_unneeded_uops(_PyUOpInstruction *buffer, int buffer_size)
     }
 }
 
-//  0 - failure, no error raised, just fall back to Tier 1
-// -1 - failure, and raise error
-//  1 - optimizer success
 int
 _Py_uop_analyze_and_optimize(
     _PyInterpreterFrame *frame,
@@ -1152,9 +1346,14 @@ _Py_uop_analyze_and_optimize(
         goto error;
     }
 
+    int err = remove_globals(frame, buffer, buffer_size, dependencies);
+    if (err <= 0) {
+        return err;
+    }
+
     // Pass: Abstract interpretation and symbolic analysis
     int new_trace_len = uop_abstract_interpret(
-        co, buffer, temp_writebuffer,
+        (PyCodeObject *)frame->f_executable, buffer, temp_writebuffer,
         buffer_size, curr_stacklen);
 
     if (new_trace_len < 0) {