1 files changed, 80 insertions, 42 deletions
diff --git a/Python/optimizer_symbols.c b/Python/optimizer_symbols.c
index e8a4f87031b..25de5d83166 100644
--- a/Python/optimizer_symbols.c
+++ b/Python/optimizer_symbols.c
@@ -13,22 +13,46 @@
 #include <stdint.h>
 #include <stddef.h>
 
-/* Symbols
-   =======
-
-   See the diagram at
-   https://github.com/faster-cpython/ideas/blob/main/3.13/redundancy_eliminator.md
-
-   We represent the nodes in the diagram as follows
-   (the flag bits are only defined in optimizer_symbols.c):
-   - Top: no flag bits, typ and const_val are NULL.
-   - NULL: IS_NULL flag set, type and const_val NULL.
-   - Not NULL: NOT_NULL flag set, type and const_val NULL.
-   - None/not None: not used. (None could be represented as any other constant.)
-   - Known type: NOT_NULL flag set and typ set; const_val is NULL.
-   - Known constant: NOT_NULL flag set, type set, const_val set.
-   - Bottom: IS_NULL and NOT_NULL flags set, type and const_val NULL.
- */
+/*
+
+Symbols
+=======
+
+https://github.com/faster-cpython/ideas/blob/main/3.13/redundancy_eliminator.md
+
+Logically, all symbols begin as UNKNOWN, and can transition downwards along the
+edges of the lattice, but *never* upwards (see the diagram below). The UNKNOWN
+state represents no information, and the BOTTOM state represents contradictory
+information. Though symbols logically progress through all intermediate nodes,
+we often skip in-between states for convenience:
+
+   UNKNOWN
+   |     |
+NULL     |
+|        |                <- Anything below this level is an object.
+|        NON_NULL
+|        |      |         <- Anything below this level has a known type version.
+| TYPE_VERSION  |
+| |             |         <- Anything below this level has a known type.
+| KNOWN_CLASS   |
+| |         |   |         <- Anything below this level has a known truthiness.
+| |         |  TRUTHINESS
+| |         |  |
+| TUPLE     |  |
+|     |     |  |          <- Anything below this level is a known constant.
+|    KNOWN_VALUE
+|    |                    <- Anything below this level is unreachable.
+BOTTOM
+
+For example, after guarding that the type of an UNKNOWN local is int, we can
+narrow the symbol to KNOWN_CLASS (logically progressing though NON_NULL and
+TYPE_VERSION to get there). Later, we may learn that it is falsey based on the
+result of a truth test, which would allow us to narrow the symbol to KNOWN_VALUE
+(with a value of integer zero). If at any point we encounter a float guard on
+the same symbol, that would be a contradiction, and the symbol would be set to
+BOTTOM (indicating that the code is unreachable).
+
+*/
 
 #ifdef Py_DEBUG
 static inline int get_lltrace(void) {
@@ -200,6 +224,10 @@ _Py_uop_sym_set_type(JitOptContext *ctx, JitOptSymbol *sym, PyTypeObject *typ)
 bool
 _Py_uop_sym_set_type_version(JitOptContext *ctx, JitOptSymbol *sym, unsigned int version)
 {
+    PyTypeObject *type = _PyType_LookupByVersion(version);
+    if (type) {
+        _Py_uop_sym_set_type(ctx, sym, type);
+    }
     JitSymType tag = sym->tag;
     switch(tag) {
         case JIT_SYM_NULL_TAG:
@@ -215,18 +243,24 @@ _Py_uop_sym_set_type_version(JitOptContext *ctx, JitOptSymbol *sym, unsigned int
                 return true;
             }
         case JIT_SYM_KNOWN_VALUE_TAG:
-            Py_CLEAR(sym->value.value);
-            sym_set_bottom(ctx, sym);
-            return false;
+            if (Py_TYPE(sym->value.value)->tp_version_tag != version) {
+                Py_CLEAR(sym->value.value);
+                sym_set_bottom(ctx, sym);
+                return false;
+            };
+            return true;
         case JIT_SYM_TUPLE_TAG:
-            sym_set_bottom(ctx, sym);
-            return false;
+            if (PyTuple_Type.tp_version_tag != version) {
+                sym_set_bottom(ctx, sym);
+                return false;
+            };
+            return true;
         case JIT_SYM_TYPE_VERSION_TAG:
-            if (sym->version.version == version) {
-                return true;
+            if (sym->version.version != version) {
+                sym_set_bottom(ctx, sym);
+                return false;
             }
-            sym_set_bottom(ctx, sym);
-            return false;
+            return true;
         case JIT_SYM_BOTTOM_TAG:
             return false;
         case JIT_SYM_NON_NULL_TAG:
@@ -266,6 +300,18 @@ _Py_uop_sym_set_const(JitOptContext *ctx, JitOptSymbol *sym, PyObject *const_val
             }
             return;
         case JIT_SYM_TUPLE_TAG:
+            if (PyTuple_CheckExact(const_val)) {
+                Py_ssize_t len = _Py_uop_sym_tuple_length(sym);
+                if (len == PyTuple_GET_SIZE(const_val)) {
+                    for (Py_ssize_t i = 0; i < len; i++) {
+                        JitOptSymbol *sym_item = _Py_uop_sym_tuple_getitem(ctx, sym, i);
+                        PyObject *item = PyTuple_GET_ITEM(const_val, i);
+                        _Py_uop_sym_set_const(ctx, sym_item, item);
+                    }
+                    make_const(sym, const_val);
+                    return;
+                }
+            }
             sym_set_bottom(ctx, sym);
             return;
         case JIT_SYM_TYPE_VERSION_TAG:
@@ -398,7 +444,6 @@ _Py_uop_sym_get_type(JitOptSymbol *sym)
     JitSymType tag = sym->tag;
     switch(tag) {
         case JIT_SYM_NULL_TAG:
-        case JIT_SYM_TYPE_VERSION_TAG:
         case JIT_SYM_BOTTOM_TAG:
         case JIT_SYM_NON_NULL_TAG:
         case JIT_SYM_UNKNOWN_TAG:
@@ -407,6 +452,8 @@ _Py_uop_sym_get_type(JitOptSymbol *sym)
             return sym->cls.type;
         case JIT_SYM_KNOWN_VALUE_TAG:
             return Py_TYPE(sym->value.value);
+        case JIT_SYM_TYPE_VERSION_TAG:
+            return _PyType_LookupByVersion(sym->version.version);
         case JIT_SYM_TUPLE_TAG:
             return &PyTuple_Type;
         case JIT_SYM_TRUTHINESS_TAG:
@@ -442,21 +489,7 @@ _Py_uop_sym_get_type_version(JitOptSymbol *sym)
 bool
 _Py_uop_sym_has_type(JitOptSymbol *sym)
 {
-    JitSymType tag = sym->tag;
-    switch(tag) {
-        case JIT_SYM_NULL_TAG:
-        case JIT_SYM_TYPE_VERSION_TAG:
-        case JIT_SYM_BOTTOM_TAG:
-        case JIT_SYM_NON_NULL_TAG:
-        case JIT_SYM_UNKNOWN_TAG:
-            return false;
-        case JIT_SYM_KNOWN_CLASS_TAG:
-        case JIT_SYM_KNOWN_VALUE_TAG:
-        case JIT_SYM_TUPLE_TAG:
-        case JIT_SYM_TRUTHINESS_TAG:
-            return true;
-    }
-    Py_UNREACHABLE();
+    return _Py_uop_sym_get_type(sym) != NULL;
 }
 
 bool
@@ -554,7 +587,7 @@ _Py_uop_sym_tuple_getitem(JitOptContext *ctx, JitOptSymbol *sym, int item)
     else if (sym->tag == JIT_SYM_TUPLE_TAG && item < sym->tuple.length) {
         return allocation_base(ctx) + sym->tuple.items[item];
     }
-    return _Py_uop_sym_new_unknown(ctx);
+    return _Py_uop_sym_new_not_null(ctx);
 }
 
 int
@@ -841,6 +874,11 @@ _Py_uop_symbols_test(PyObject *Py_UNUSED(self), PyObject *Py_UNUSED(ignored))
         _Py_uop_sym_get_const(ctx, _Py_uop_sym_tuple_getitem(ctx, sym, 1)) == val_43,
         "tuple item does not match value used to create tuple"
     );
+    sym = _Py_uop_sym_new_type(ctx, &PyTuple_Type);
+    TEST_PREDICATE(
+        _Py_uop_sym_is_not_null(_Py_uop_sym_tuple_getitem(ctx, sym, 42)),
+        "Unknown tuple item is not narrowed to non-NULL"
+    );
     JitOptSymbol *value = _Py_uop_sym_new_type(ctx, &PyBool_Type);
     sym = _Py_uop_sym_new_truthiness(ctx, value, false);
     TEST_PREDICATE(_Py_uop_sym_matches_type(sym, &PyBool_Type), "truthiness is not boolean");