bpo-45609: Specialize STORE_SUBSCR (GH-29242)

* Specialize STORE_SUBSCR for list[int], and dict[object]

* Adds _PyDict_SetItem_Take2 which consumes references to the key and values.

10 files changed, 241 insertions, 71 deletions

diff --git a/Include/internal/pycore_code.h b/Include/internal/pycore_code.h
index 6563f7b..194af46 100644
--- a/Include/internal/pycore_code.h
+++ b/Include/internal/pycore_code.h
@@ -268,6 +268,7 @@ int _Py_Specialize_StoreAttr(PyObject *owner, _Py_CODEUNIT *instr, PyObject *nam
 int _Py_Specialize_LoadGlobal(PyObject *globals, PyObject *builtins, _Py_CODEUNIT *instr, PyObject *name, SpecializedCacheEntry *cache);
 int _Py_Specialize_LoadMethod(PyObject *owner, _Py_CODEUNIT *instr, PyObject *name, SpecializedCacheEntry *cache);
 int _Py_Specialize_BinarySubscr(PyObject *sub, PyObject *container, _Py_CODEUNIT *instr, SpecializedCacheEntry *cache);
+int _Py_Specialize_StoreSubscr(PyObject *container, PyObject *sub, _Py_CODEUNIT *instr);
 int _Py_Specialize_CallFunction(PyObject *callable, _Py_CODEUNIT *instr, int nargs, SpecializedCacheEntry *cache, PyObject *builtins);
 void _Py_Specialize_BinaryOp(PyObject *lhs, PyObject *rhs, _Py_CODEUNIT *instr,
                              SpecializedCacheEntry *cache);
diff --git a/Include/internal/pycore_dict.h b/Include/internal/pycore_dict.h
index 13cb7cc..2f05368 100644
--- a/Include/internal/pycore_dict.h
+++ b/Include/internal/pycore_dict.h
@@ -22,6 +22,8 @@ typedef struct {
  */
 Py_ssize_t _Py_dict_lookup(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr);
 
+/* Consumes references to key and value */
+int _PyDict_SetItem_Take2(PyDictObject *op, PyObject *key, PyObject *value);
 
 #define DKIX_EMPTY (-1)
 #define DKIX_DUMMY (-2)  /* Used internally */
diff --git a/Include/opcode.h b/Include/opcode.h
index 2367064..3ec89bd 100644
--- a/Include/opcode.h
+++ b/Include/opcode.h
@@ -125,35 +125,38 @@ extern "C" {
 #define BINARY_SUBSCR_LIST_INT           23
 #define BINARY_SUBSCR_TUPLE_INT          24
 #define BINARY_SUBSCR_DICT               26
-#define CALL_FUNCTION_ADAPTIVE           27
-#define CALL_FUNCTION_BUILTIN_O          28
-#define CALL_FUNCTION_BUILTIN_FAST       29
-#define CALL_FUNCTION_LEN                34
-#define CALL_FUNCTION_ISINSTANCE         36
-#define CALL_FUNCTION_PY_SIMPLE          38
-#define JUMP_ABSOLUTE_QUICK              39
-#define LOAD_ATTR_ADAPTIVE               40
-#define LOAD_ATTR_INSTANCE_VALUE         41
-#define LOAD_ATTR_WITH_HINT              42
-#define LOAD_ATTR_SLOT                   43
-#define LOAD_ATTR_MODULE                 44
-#define LOAD_GLOBAL_ADAPTIVE             45
-#define LOAD_GLOBAL_MODULE               46
-#define LOAD_GLOBAL_BUILTIN              47
-#define LOAD_METHOD_ADAPTIVE             48
-#define LOAD_METHOD_CACHED               55
-#define LOAD_METHOD_CLASS                56
-#define LOAD_METHOD_MODULE               57
-#define LOAD_METHOD_NO_DICT              58
-#define STORE_ATTR_ADAPTIVE              59
-#define STORE_ATTR_INSTANCE_VALUE        62
-#define STORE_ATTR_SLOT                  63
-#define STORE_ATTR_WITH_HINT             64
-#define LOAD_FAST__LOAD_FAST             65
-#define STORE_FAST__LOAD_FAST            66
-#define LOAD_FAST__LOAD_CONST            67
-#define LOAD_CONST__LOAD_FAST            75
-#define STORE_FAST__STORE_FAST           76
+#define STORE_SUBSCR_ADAPTIVE            27
+#define STORE_SUBSCR_LIST_INT            28
+#define STORE_SUBSCR_DICT                29
+#define CALL_FUNCTION_ADAPTIVE           34
+#define CALL_FUNCTION_BUILTIN_O          36
+#define CALL_FUNCTION_BUILTIN_FAST       38
+#define CALL_FUNCTION_LEN                39
+#define CALL_FUNCTION_ISINSTANCE         40
+#define CALL_FUNCTION_PY_SIMPLE          41
+#define JUMP_ABSOLUTE_QUICK              42
+#define LOAD_ATTR_ADAPTIVE               43
+#define LOAD_ATTR_INSTANCE_VALUE         44
+#define LOAD_ATTR_WITH_HINT              45
+#define LOAD_ATTR_SLOT                   46
+#define LOAD_ATTR_MODULE                 47
+#define LOAD_GLOBAL_ADAPTIVE             48
+#define LOAD_GLOBAL_MODULE               55
+#define LOAD_GLOBAL_BUILTIN              56
+#define LOAD_METHOD_ADAPTIVE             57
+#define LOAD_METHOD_CACHED               58
+#define LOAD_METHOD_CLASS                59
+#define LOAD_METHOD_MODULE               62
+#define LOAD_METHOD_NO_DICT              63
+#define STORE_ATTR_ADAPTIVE              64
+#define STORE_ATTR_INSTANCE_VALUE        65
+#define STORE_ATTR_SLOT                  66
+#define STORE_ATTR_WITH_HINT             67
+#define LOAD_FAST__LOAD_FAST             75
+#define STORE_FAST__LOAD_FAST            76
+#define LOAD_FAST__LOAD_CONST            77
+#define LOAD_CONST__LOAD_FAST            78
+#define STORE_FAST__STORE_FAST           79
 #define DO_TRACING                      255
 #ifdef NEED_OPCODE_JUMP_TABLES
 static uint32_t _PyOpcode_RelativeJump[8] = {
diff --git a/Lib/opcode.py b/Lib/opcode.py
index 1df192b..3603bb4 100644
--- a/Lib/opcode.py
+++ b/Lib/opcode.py
@@ -238,6 +238,9 @@ _specialized_instructions = [
     "BINARY_SUBSCR_LIST_INT",
     "BINARY_SUBSCR_TUPLE_INT",
     "BINARY_SUBSCR_DICT",
+    "STORE_SUBSCR_ADAPTIVE",
+    "STORE_SUBSCR_LIST_INT",
+    "STORE_SUBSCR_DICT",
     "CALL_FUNCTION_ADAPTIVE",
     "CALL_FUNCTION_BUILTIN_O",
     "CALL_FUNCTION_BUILTIN_FAST",
diff --git a/Lib/test/test_dict.py b/Lib/test/test_dict.py
index 32ffd38..66f5d56 100644
--- a/Lib/test/test_dict.py
+++ b/Lib/test/test_dict.py
@@ -892,6 +892,14 @@ class DictTest(unittest.TestCase):
         gc.collect()
         self.assertTrue(gc.is_tracked(t), t)
 
+    def test_string_keys_can_track_values(self):
+        # Test that this doesn't leak.
+        for i in range(10):
+            d = {}
+            for j in range(10):
+                d[str(j)] = j
+            d["foo"] = d
+
     @support.cpython_only
     def test_track_literals(self):
         # Test GC-optimization of dict literals
diff --git a/Misc/NEWS.d/next/Core and Builtins/2021-10-27-21-00-49.bpo-45609.L1GKPX.rst b/Misc/NEWS.d/next/Core and Builtins/2021-10-27-21-00-49.bpo-45609.L1GKPX.rst
new file mode 100644
index 0000000..f7df7d4
--- /dev/null
+++ b/Misc/NEWS.d/next/Core and Builtins/2021-10-27-21-00-49.bpo-45609.L1GKPX.rst
@@ -0,0 +1 @@
+Specialized the ``STORE_SUBSCR`` opcode using the PEP 659 machinery.
\ No newline at end of file
diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index 6dcd5a1..475d92d 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -1055,6 +1055,7 @@ insert_into_dictkeys(PyDictKeysObject *keys, PyObject *name)
 Internal routine to insert a new item into the table.
 Used both by the internal resize routine and by the public insert routine.
 Returns -1 if an error occurred, or 0 on success.
+Consumes key and value references.
 */
 static int
 insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value)
@@ -1062,8 +1063,6 @@ insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value)
     PyObject *old_value;
     PyDictKeyEntry *ep;
 
-    Py_INCREF(key);
-    Py_INCREF(value);
     if (mp->ma_values != NULL && !PyUnicode_CheckExact(key)) {
         if (insertion_resize(mp) < 0)
             goto Fail;
@@ -1138,6 +1137,7 @@ Fail:
 }
 
 // Same to insertdict but specialized for ma_keys = Py_EMPTY_KEYS.
+// Consumes key and value references.
 static int
 insert_to_emptydict(PyDictObject *mp, PyObject *key, Py_hash_t hash,
                     PyObject *value)
@@ -1146,6 +1146,8 @@ insert_to_emptydict(PyDictObject *mp, PyObject *key, Py_hash_t hash,
 
     PyDictKeysObject *newkeys = new_keys_object(PyDict_LOG_MINSIZE);
     if (newkeys == NULL) {
+        Py_DECREF(key);
+        Py_DECREF(value);
         return -1;
     }
     if (!PyUnicode_CheckExact(key)) {
@@ -1155,8 +1157,6 @@ insert_to_emptydict(PyDictObject *mp, PyObject *key, Py_hash_t hash,
     mp->ma_keys = newkeys;
     mp->ma_values = NULL;
 
-    Py_INCREF(key);
-    Py_INCREF(value);
     MAINTAIN_TRACKING(mp, key, value);
 
     size_t hashpos = (size_t)hash & (PyDict_MINSIZE-1);
@@ -1529,32 +1529,24 @@ _PyDict_LoadGlobal(PyDictObject *globals, PyDictObject *builtins, PyObject *key)
     return value;
 }
 
-/* CAUTION: PyDict_SetItem() must guarantee that it won't resize the
- * dictionary if it's merely replacing the value for an existing key.
- * This means that it's safe to loop over a dictionary with PyDict_Next()
- * and occasionally replace a value -- but you can't insert new keys or
- * remove them.
- */
+/* Consumes references to key and value */
 int
-PyDict_SetItem(PyObject *op, PyObject *key, PyObject *value)
+_PyDict_SetItem_Take2(PyDictObject *mp, PyObject *key, PyObject *value)
 {
-    PyDictObject *mp;
-    Py_hash_t hash;
-    if (!PyDict_Check(op)) {
-        PyErr_BadInternalCall();
-        return -1;
-    }
     assert(key);
     assert(value);
-    mp = (PyDictObject *)op;
+    assert(PyDict_Check(mp));
+    Py_hash_t hash;
     if (!PyUnicode_CheckExact(key) ||
         (hash = ((PyASCIIObject *) key)->hash) == -1)
     {
         hash = PyObject_Hash(key);
-        if (hash == -1)
+        if (hash == -1) {
+            Py_DECREF(key);
+            Py_DECREF(value);
             return -1;
+        }
     }
-
     if (mp->ma_keys == Py_EMPTY_KEYS) {
         return insert_to_emptydict(mp, key, hash, value);
     }
@@ -1562,6 +1554,26 @@ PyDict_SetItem(PyObject *op, PyObject *key, PyObject *value)
     return insertdict(mp, key, hash, value);
 }
 
+/* CAUTION: PyDict_SetItem() must guarantee that it won't resize the
+ * dictionary if it's merely replacing the value for an existing key.
+ * This means that it's safe to loop over a dictionary with PyDict_Next()
+ * and occasionally replace a value -- but you can't insert new keys or
+ * remove them.
+ */
+int
+PyDict_SetItem(PyObject *op, PyObject *key, PyObject *value)
+{
+    if (!PyDict_Check(op)) {
+        PyErr_BadInternalCall();
+        return -1;
+    }
+    assert(key);
+    assert(value);
+    Py_INCREF(key);
+    Py_INCREF(value);
+    return _PyDict_SetItem_Take2((PyDictObject *)op, key, value);
+}
+
 int
 _PyDict_SetItem_KnownHash(PyObject *op, PyObject *key, PyObject *value,
                          Py_hash_t hash)
@@ -1577,6 +1589,8 @@ _PyDict_SetItem_KnownHash(PyObject *op, PyObject *key, PyObject *value,
     assert(hash != -1);
     mp = (PyDictObject *)op;
 
+    Py_INCREF(key);
+    Py_INCREF(value);
     if (mp->ma_keys == Py_EMPTY_KEYS) {
         return insert_to_emptydict(mp, key, hash, value);
     }
@@ -1917,6 +1931,8 @@ _PyDict_FromKeys(PyObject *cls, PyObject *iterable, PyObject *value)
             }
 
             while (_PyDict_Next(iterable, &pos, &key, &oldvalue, &hash)) {
+                Py_INCREF(key);
+                Py_INCREF(value);
                 if (insertdict(mp, key, hash, value)) {
                     Py_DECREF(d);
                     return NULL;
@@ -1936,6 +1952,8 @@ _PyDict_FromKeys(PyObject *cls, PyObject *iterable, PyObject *value)
             }
 
             while (_PySet_NextEntry(iterable, &pos, &key, &hash)) {
+                Py_INCREF(key);
+                Py_INCREF(value);
                 if (insertdict(mp, key, hash, value)) {
                     Py_DECREF(d);
                     return NULL;
@@ -2562,11 +2580,16 @@ dict_merge(PyObject *a, PyObject *b, int override)
                 int err = 0;
                 Py_INCREF(key);
                 Py_INCREF(value);
-                if (override == 1)
+                if (override == 1) {
+                    Py_INCREF(key);
+                    Py_INCREF(value);
                     err = insertdict(mp, key, hash, value);
+                }
                 else {
                     err = _PyDict_Contains_KnownHash(a, key, hash);
                     if (err == 0) {
+                        Py_INCREF(key);
+                        Py_INCREF(value);
                         err = insertdict(mp, key, hash, value);
                     }
                     else if (err > 0) {
@@ -2967,7 +2990,10 @@ PyDict_SetDefault(PyObject *d, PyObject *key, PyObject *defaultobj)
         if (hash == -1)
             return NULL;
     }
+
     if (mp->ma_keys == Py_EMPTY_KEYS) {
+        Py_INCREF(key);
+        Py_INCREF(defaultobj);
         if (insert_to_emptydict(mp, key, hash, defaultobj) < 0) {
             return NULL;
         }
diff --git a/Python/ceval.c b/Python/ceval.c
index 2b7b31c..9d3ff74 100644
--- a/Python/ceval.c
+++ b/Python/ceval.c
@@ -2279,6 +2279,8 @@ check_eval_breaker:
         }
 
         TARGET(STORE_SUBSCR) {
+            PREDICTED(STORE_SUBSCR);
+            STAT_INC(STORE_SUBSCR, unquickened);
             PyObject *sub = TOP();
             PyObject *container = SECOND();
             PyObject *v = THIRD();
@@ -2294,6 +2296,64 @@ check_eval_breaker:
             DISPATCH();
         }
 
+        TARGET(STORE_SUBSCR_ADAPTIVE) {
+            if (oparg == 0) {
+                PyObject *sub = TOP();
+                PyObject *container = SECOND();
+                next_instr--;
+                if (_Py_Specialize_StoreSubscr(container, sub, next_instr) < 0) {
+                    goto error;
+                }
+                DISPATCH();
+            }
+            else {
+                STAT_INC(STORE_SUBSCR, deferred);
+                // oparg is the adaptive cache counter
+                UPDATE_PREV_INSTR_OPARG(next_instr, oparg - 1);
+                STAT_DEC(STORE_SUBSCR, unquickened);
+                JUMP_TO_INSTRUCTION(STORE_SUBSCR);
+            }
+        }
+
+        TARGET(STORE_SUBSCR_LIST_INT) {
+            PyObject *sub = TOP();
+            PyObject *list = SECOND();
+            PyObject *value = THIRD();
+            DEOPT_IF(!PyLong_CheckExact(sub), STORE_SUBSCR);
+            DEOPT_IF(!PyList_CheckExact(list), STORE_SUBSCR);
+
+            // Ensure nonnegative, zero-or-one-digit ints.
+            DEOPT_IF(((size_t)Py_SIZE(sub)) > 1, STORE_SUBSCR);
+            Py_ssize_t index = ((PyLongObject*)sub)->ob_digit[0];
+            // Ensure index < len(list)
+            DEOPT_IF(index >= PyList_GET_SIZE(list), STORE_SUBSCR);
+            STAT_INC(STORE_SUBSCR, hit);
+
+            PyObject *old_value = PyList_GET_ITEM(list, index);
+            PyList_SET_ITEM(list, index, value);
+            STACK_SHRINK(3);
+            assert(old_value != NULL);
+            Py_DECREF(old_value);
+            Py_DECREF(sub);
+            Py_DECREF(list);
+            DISPATCH();
+        }
+
+        TARGET(STORE_SUBSCR_DICT) {
+            PyObject *sub = TOP();
+            PyObject *dict = SECOND();
+            PyObject *value = THIRD();
+            DEOPT_IF(!PyDict_CheckExact(dict), STORE_SUBSCR);
+            STACK_SHRINK(3);
+            STAT_INC(STORE_SUBSCR, hit);
+            int err = _PyDict_SetItem_Take2((PyDictObject *)dict, sub, value);
+            Py_DECREF(dict);
+            if (err != 0) {
+                goto error;
+            }
+            DISPATCH();
+        }
+
         TARGET(DELETE_SUBSCR) {
             PyObject *sub = TOP();
             PyObject *container = SECOND();
@@ -3374,15 +3434,13 @@ check_eval_breaker:
             PyObject *value = TOP();
             PyObject *key = SECOND();
             PyObject *map;
-            int err;
             STACK_SHRINK(2);
             map = PEEK(oparg);                      /* dict */
             assert(PyDict_CheckExact(map));
-            err = PyDict_SetItem(map, key, value);  /* map[key] = value */
-            Py_DECREF(value);
-            Py_DECREF(key);
-            if (err != 0)
+            /* map[key] = value */
+            if (_PyDict_SetItem_Take2((PyDictObject *)map, key, value) != 0) {
                 goto error;
+            }
             PREDICT(JUMP_ABSOLUTE);
             DISPATCH();
         }
@@ -4909,6 +4967,22 @@ opname ## _miss: \
         JUMP_TO_INSTRUCTION(opname); \
     }
 
+#define MISS_WITH_OPARG_COUNTER(opname) \
+opname ## _miss: \
+    { \
+        STAT_INC(opname, miss); \
+        uint8_t oparg = _Py_OPARG(next_instr[-1])-1; \
+        UPDATE_PREV_INSTR_OPARG(next_instr, oparg); \
+        assert(_Py_OPARG(next_instr[-1]) == oparg); \
+        if (oparg == 0) /* too many cache misses */ { \
+            oparg = ADAPTIVE_CACHE_BACKOFF; \
+            next_instr[-1] = _Py_MAKECODEUNIT(opname ## _ADAPTIVE, oparg); \
+            STAT_INC(opname, deopt); \
+        } \
+        STAT_DEC(opname, unquickened); \
+        JUMP_TO_INSTRUCTION(opname); \
+    }
+
 MISS_WITH_CACHE(LOAD_ATTR)
 MISS_WITH_CACHE(STORE_ATTR)
 MISS_WITH_CACHE(LOAD_GLOBAL)
@@ -4916,6 +4990,7 @@ MISS_WITH_CACHE(LOAD_METHOD)
 MISS_WITH_CACHE(CALL_FUNCTION)
 MISS_WITH_CACHE(BINARY_OP)
 MISS_WITH_CACHE(BINARY_SUBSCR)
+MISS_WITH_OPARG_COUNTER(STORE_SUBSCR)
 
 binary_subscr_dict_error:
         {
diff --git a/Python/opcode_targets.h b/Python/opcode_targets.h
index 4703255..903b967 100644
--- a/Python/opcode_targets.h
+++ b/Python/opcode_targets.h
@@ -26,17 +26,20 @@ static void *opcode_targets[256] = {
     &&TARGET_BINARY_SUBSCR_TUPLE_INT,
     &&TARGET_BINARY_SUBSCR,
     &&TARGET_BINARY_SUBSCR_DICT,
-    &&TARGET_CALL_FUNCTION_ADAPTIVE,
-    &&TARGET_CALL_FUNCTION_BUILTIN_O,
-    &&TARGET_CALL_FUNCTION_BUILTIN_FAST,
+    &&TARGET_STORE_SUBSCR_ADAPTIVE,
+    &&TARGET_STORE_SUBSCR_LIST_INT,
+    &&TARGET_STORE_SUBSCR_DICT,
     &&TARGET_GET_LEN,
     &&TARGET_MATCH_MAPPING,
     &&TARGET_MATCH_SEQUENCE,
     &&TARGET_MATCH_KEYS,
-    &&TARGET_CALL_FUNCTION_LEN,
+    &&TARGET_CALL_FUNCTION_ADAPTIVE,
     &&TARGET_PUSH_EXC_INFO,
-    &&TARGET_CALL_FUNCTION_ISINSTANCE,
+    &&TARGET_CALL_FUNCTION_BUILTIN_O,
     &&TARGET_POP_EXCEPT_AND_RERAISE,
+    &&TARGET_CALL_FUNCTION_BUILTIN_FAST,
+    &&TARGET_CALL_FUNCTION_LEN,
+    &&TARGET_CALL_FUNCTION_ISINSTANCE,
     &&TARGET_CALL_FUNCTION_PY_SIMPLE,
     &&TARGET_JUMP_ABSOLUTE_QUICK,
     &&TARGET_LOAD_ATTR_ADAPTIVE,
@@ -45,28 +48,25 @@ static void *opcode_targets[256] = {
     &&TARGET_LOAD_ATTR_SLOT,
     &&TARGET_LOAD_ATTR_MODULE,
     &&TARGET_LOAD_GLOBAL_ADAPTIVE,
-    &&TARGET_LOAD_GLOBAL_MODULE,
-    &&TARGET_LOAD_GLOBAL_BUILTIN,
-    &&TARGET_LOAD_METHOD_ADAPTIVE,
     &&TARGET_WITH_EXCEPT_START,
     &&TARGET_GET_AITER,
     &&TARGET_GET_ANEXT,
     &&TARGET_BEFORE_ASYNC_WITH,
     &&TARGET_BEFORE_WITH,
     &&TARGET_END_ASYNC_FOR,
+    &&TARGET_LOAD_GLOBAL_MODULE,
+    &&TARGET_LOAD_GLOBAL_BUILTIN,
+    &&TARGET_LOAD_METHOD_ADAPTIVE,
     &&TARGET_LOAD_METHOD_CACHED,
     &&TARGET_LOAD_METHOD_CLASS,
+    &&TARGET_STORE_SUBSCR,
+    &&TARGET_DELETE_SUBSCR,
     &&TARGET_LOAD_METHOD_MODULE,
     &&TARGET_LOAD_METHOD_NO_DICT,
     &&TARGET_STORE_ATTR_ADAPTIVE,
-    &&TARGET_STORE_SUBSCR,
-    &&TARGET_DELETE_SUBSCR,
     &&TARGET_STORE_ATTR_INSTANCE_VALUE,
     &&TARGET_STORE_ATTR_SLOT,
     &&TARGET_STORE_ATTR_WITH_HINT,
-    &&TARGET_LOAD_FAST__LOAD_FAST,
-    &&TARGET_STORE_FAST__LOAD_FAST,
-    &&TARGET_LOAD_FAST__LOAD_CONST,
     &&TARGET_GET_ITER,
     &&TARGET_GET_YIELD_FROM_ITER,
     &&TARGET_PRINT_EXPR,
@@ -74,13 +74,13 @@ static void *opcode_targets[256] = {
     &&TARGET_YIELD_FROM,
     &&TARGET_GET_AWAITABLE,
     &&TARGET_LOAD_ASSERTION_ERROR,
+    &&TARGET_LOAD_FAST__LOAD_FAST,
+    &&TARGET_STORE_FAST__LOAD_FAST,
+    &&TARGET_LOAD_FAST__LOAD_CONST,
     &&TARGET_LOAD_CONST__LOAD_FAST,
     &&TARGET_STORE_FAST__STORE_FAST,
     &&_unknown_opcode,
     &&_unknown_opcode,
-    &&_unknown_opcode,
-    &&_unknown_opcode,
-    &&_unknown_opcode,
     &&TARGET_LIST_TO_TUPLE,
     &&TARGET_RETURN_VALUE,
     &&TARGET_IMPORT_STAR,
diff --git a/Python/specialize.c b/Python/specialize.c
index 06b0764..130da00 100644
--- a/Python/specialize.c
+++ b/Python/specialize.c
@@ -125,6 +125,7 @@ _Py_GetSpecializationStats(void) {
     err += add_stat_dict(stats, LOAD_GLOBAL, "load_global");
     err += add_stat_dict(stats, LOAD_METHOD, "load_method");
     err += add_stat_dict(stats, BINARY_SUBSCR, "binary_subscr");
+    err += add_stat_dict(stats, STORE_SUBSCR, "store_subscr");
     err += add_stat_dict(stats, STORE_ATTR, "store_attr");
     err += add_stat_dict(stats, CALL_FUNCTION, "call_function");
     err += add_stat_dict(stats, BINARY_OP, "binary_op");
@@ -182,6 +183,7 @@ _Py_PrintSpecializationStats(void)
     print_stats(out, &_specialization_stats[LOAD_GLOBAL], "load_global");
     print_stats(out, &_specialization_stats[LOAD_METHOD], "load_method");
     print_stats(out, &_specialization_stats[BINARY_SUBSCR], "binary_subscr");
+    print_stats(out, &_specialization_stats[STORE_SUBSCR], "store_subscr");
     print_stats(out, &_specialization_stats[STORE_ATTR], "store_attr");
     print_stats(out, &_specialization_stats[CALL_FUNCTION], "call_function");
     print_stats(out, &_specialization_stats[BINARY_OP], "binary_op");
@@ -233,6 +235,7 @@ static uint8_t adaptive_opcodes[256] = {
     [LOAD_GLOBAL] = LOAD_GLOBAL_ADAPTIVE,
     [LOAD_METHOD] = LOAD_METHOD_ADAPTIVE,
     [BINARY_SUBSCR] = BINARY_SUBSCR_ADAPTIVE,
+    [STORE_SUBSCR] = STORE_SUBSCR_ADAPTIVE,
     [CALL_FUNCTION] = CALL_FUNCTION_ADAPTIVE,
     [STORE_ATTR] = STORE_ATTR_ADAPTIVE,
     [BINARY_OP] = BINARY_OP_ADAPTIVE,
@@ -244,6 +247,7 @@ static uint8_t cache_requirements[256] = {
     [LOAD_GLOBAL] = 2, /* _PyAdaptiveEntry and _PyLoadGlobalCache */
     [LOAD_METHOD] = 3, /* _PyAdaptiveEntry, _PyAttrCache and _PyObjectCache */
     [BINARY_SUBSCR] = 2, /* _PyAdaptiveEntry, _PyObjectCache */
+    [STORE_SUBSCR] = 0,
     [CALL_FUNCTION] = 2, /* _PyAdaptiveEntry and _PyObjectCache/_PyCallCache */
     [STORE_ATTR] = 2, /* _PyAdaptiveEntry and _PyAttrCache */
     [BINARY_OP] = 1,  // _PyAdaptiveEntry
@@ -1228,6 +1232,53 @@ success:
     return 0;
 }
 
+int
+_Py_Specialize_StoreSubscr(PyObject *container, PyObject *sub, _Py_CODEUNIT *instr)
+{
+    PyTypeObject *container_type = Py_TYPE(container);
+    if (container_type == &PyList_Type) {
+        if (PyLong_CheckExact(sub)) {
+            if ((Py_SIZE(sub) == 0 || Py_SIZE(sub) == 1)
+                && ((PyLongObject *)sub)->ob_digit[0] < PyList_GET_SIZE(container))
+            {
+                *instr = _Py_MAKECODEUNIT(STORE_SUBSCR_LIST_INT,
+                                          initial_counter_value());
+                goto success;
+            }
+            else {
+                SPECIALIZATION_FAIL(STORE_SUBSCR, SPEC_FAIL_OUT_OF_RANGE);
+                goto fail;
+            }
+        }
+        else if (PySlice_Check(sub)) {
+            SPECIALIZATION_FAIL(STORE_SUBSCR, SPEC_FAIL_LIST_SLICE);
+            goto fail;
+        }
+        else {
+            SPECIALIZATION_FAIL(STORE_SUBSCR, SPEC_FAIL_OTHER);
+            goto fail;
+        }
+    }
+    else if (container_type == &PyDict_Type) {
+        *instr = _Py_MAKECODEUNIT(STORE_SUBSCR_DICT,
+                                  initial_counter_value());
+         goto success;
+    }
+    else {
+        SPECIALIZATION_FAIL(STORE_SUBSCR, SPEC_FAIL_OTHER);
+        goto fail;
+    }
+fail:
+    STAT_INC(STORE_SUBSCR, specialization_failure);
+    assert(!PyErr_Occurred());
+    *instr = _Py_MAKECODEUNIT(_Py_OPCODE(*instr), ADAPTIVE_CACHE_BACKOFF);
+    return 0;
+success:
+    STAT_INC(STORE_SUBSCR, specialization_success);
+    assert(!PyErr_Occurred());
+    return 0;
+}
+
 static int
 specialize_class_call(
     PyObject *callable, _Py_CODEUNIT *instr,