gh-107557: Setup abstract interpretation (#107847)

Co-authored-by: Guido van Rossum <gvanrossum@users.noreply.github.com>
Co-authored-by: Jules <57632293+juliapoo@users.noreply.github.com>

3 files changed, 163 insertions, 1 deletions

diff --git a/Include/internal/pycore_opcode_metadata.h b/Include/internal/pycore_opcode_metadata.h
index c0a2e9d..df9b418 100644
--- a/Include/internal/pycore_opcode_metadata.h
+++ b/Include/internal/pycore_opcode_metadata.h
@@ -55,6 +55,7 @@
 #define _POP_JUMP_IF_FALSE 331
 #define _POP_JUMP_IF_TRUE 332
 #define JUMP_TO_TOP 333
+#define INSERT 334
 
 extern int _PyOpcode_num_popped(int opcode, int oparg, bool jump);
 #ifdef NEED_OPCODE_METADATA
@@ -118,18 +119,38 @@ int _PyOpcode_num_popped(int opcode, int oparg, bool jump)  {
             return 1;
         case UNARY_INVERT:
             return 1;
+        case _GUARD_BOTH_INT:
+            return 2;
+        case _BINARY_OP_MULTIPLY_INT:
+            return 2;
+        case _BINARY_OP_ADD_INT:
+            return 2;
+        case _BINARY_OP_SUBTRACT_INT:
+            return 2;
         case BINARY_OP_MULTIPLY_INT:
             return 2;
         case BINARY_OP_ADD_INT:
             return 2;
         case BINARY_OP_SUBTRACT_INT:
             return 2;
+        case _GUARD_BOTH_FLOAT:
+            return 2;
+        case _BINARY_OP_MULTIPLY_FLOAT:
+            return 2;
+        case _BINARY_OP_ADD_FLOAT:
+            return 2;
+        case _BINARY_OP_SUBTRACT_FLOAT:
+            return 2;
         case BINARY_OP_MULTIPLY_FLOAT:
             return 2;
         case BINARY_OP_ADD_FLOAT:
             return 2;
         case BINARY_OP_SUBTRACT_FLOAT:
             return 2;
+        case _GUARD_BOTH_UNICODE:
+            return 2;
+        case _BINARY_OP_ADD_UNICODE:
+            return 2;
         case BINARY_OP_ADD_UNICODE:
             return 2;
         case BINARY_OP_INPLACE_ADD_UNICODE:
@@ -226,14 +247,26 @@ int _PyOpcode_num_popped(int opcode, int oparg, bool jump)  {
             return 1;
         case DELETE_GLOBAL:
             return 0;
+        case _LOAD_LOCALS:
+            return 0;
         case LOAD_LOCALS:
             return 0;
+        case _LOAD_FROM_DICT_OR_GLOBALS:
+            return 1;
         case LOAD_NAME:
             return 0;
         case LOAD_FROM_DICT_OR_GLOBALS:
             return 1;
         case LOAD_GLOBAL:
             return 0;
+        case _GUARD_GLOBALS_VERSION:
+            return 0;
+        case _GUARD_BUILTINS_VERSION:
+            return 0;
+        case _LOAD_GLOBAL_MODULE:
+            return 0;
+        case _LOAD_GLOBAL_BUILTINS:
+            return 0;
         case LOAD_GLOBAL_MODULE:
             return 0;
         case LOAD_GLOBAL_BUILTIN:
@@ -294,6 +327,12 @@ int _PyOpcode_num_popped(int opcode, int oparg, bool jump)  {
             return 1;
         case LOAD_METHOD:
             return 1;
+        case _GUARD_TYPE_VERSION:
+            return 1;
+        case _CHECK_MANAGED_OBJECT_HAS_VALUES:
+            return 1;
+        case _LOAD_ATTR_INSTANCE_VALUE:
+            return 1;
         case LOAD_ATTR_INSTANCE_VALUE:
             return 1;
         case LOAD_ATTR_MODULE:
@@ -348,6 +387,8 @@ int _PyOpcode_num_popped(int opcode, int oparg, bool jump)  {
             return 1;
         case POP_JUMP_IF_TRUE:
             return 1;
+        case IS_NONE:
+            return 1;
         case POP_JUMP_IF_NONE:
             return 1;
         case POP_JUMP_IF_NOT_NONE:
@@ -372,10 +413,28 @@ int _PyOpcode_num_popped(int opcode, int oparg, bool jump)  {
             return 1;
         case INSTRUMENTED_FOR_ITER:
             return 0;
+        case _ITER_CHECK_LIST:
+            return 1;
+        case _IS_ITER_EXHAUSTED_LIST:
+            return 1;
+        case _ITER_NEXT_LIST:
+            return 1;
         case FOR_ITER_LIST:
             return 1;
+        case _ITER_CHECK_TUPLE:
+            return 1;
+        case _IS_ITER_EXHAUSTED_TUPLE:
+            return 1;
+        case _ITER_NEXT_TUPLE:
+            return 1;
         case FOR_ITER_TUPLE:
             return 1;
+        case _ITER_CHECK_RANGE:
+            return 1;
+        case _IS_ITER_EXHAUSTED_RANGE:
+            return 1;
+        case _ITER_NEXT_RANGE:
+            return 1;
         case FOR_ITER_RANGE:
             return 1;
         case FOR_ITER_GEN:
@@ -494,6 +553,18 @@ int _PyOpcode_num_popped(int opcode, int oparg, bool jump)  {
             return 0;
         case RESERVED:
             return 0;
+        case _POP_JUMP_IF_FALSE:
+            return 1;
+        case _POP_JUMP_IF_TRUE:
+            return 1;
+        case JUMP_TO_TOP:
+            return 0;
+        case SAVE_IP:
+            return 0;
+        case EXIT_TRACE:
+            return 0;
+        case INSERT:
+            return oparg + 1;
         default:
             return -1;
     }
@@ -562,18 +633,38 @@ int _PyOpcode_num_pushed(int opcode, int oparg, bool jump)  {
             return 1;
         case UNARY_INVERT:
             return 1;
+        case _GUARD_BOTH_INT:
+            return 2;
+        case _BINARY_OP_MULTIPLY_INT:
+            return 1;
+        case _BINARY_OP_ADD_INT:
+            return 1;
+        case _BINARY_OP_SUBTRACT_INT:
+            return 1;
         case BINARY_OP_MULTIPLY_INT:
             return 1;
         case BINARY_OP_ADD_INT:
             return 1;
         case BINARY_OP_SUBTRACT_INT:
             return 1;
+        case _GUARD_BOTH_FLOAT:
+            return 2;
+        case _BINARY_OP_MULTIPLY_FLOAT:
+            return 1;
+        case _BINARY_OP_ADD_FLOAT:
+            return 1;
+        case _BINARY_OP_SUBTRACT_FLOAT:
+            return 1;
         case BINARY_OP_MULTIPLY_FLOAT:
             return 1;
         case BINARY_OP_ADD_FLOAT:
             return 1;
         case BINARY_OP_SUBTRACT_FLOAT:
             return 1;
+        case _GUARD_BOTH_UNICODE:
+            return 2;
+        case _BINARY_OP_ADD_UNICODE:
+            return 1;
         case BINARY_OP_ADD_UNICODE:
             return 1;
         case BINARY_OP_INPLACE_ADD_UNICODE:
@@ -670,14 +761,26 @@ int _PyOpcode_num_pushed(int opcode, int oparg, bool jump)  {
             return 0;
         case DELETE_GLOBAL:
             return 0;
+        case _LOAD_LOCALS:
+            return 1;
         case LOAD_LOCALS:
             return 1;
+        case _LOAD_FROM_DICT_OR_GLOBALS:
+            return 1;
         case LOAD_NAME:
             return 1;
         case LOAD_FROM_DICT_OR_GLOBALS:
             return 1;
         case LOAD_GLOBAL:
             return ((oparg & 1) ? 1 : 0) + 1;
+        case _GUARD_GLOBALS_VERSION:
+            return 0;
+        case _GUARD_BUILTINS_VERSION:
+            return 0;
+        case _LOAD_GLOBAL_MODULE:
+            return ((oparg & 1) ? 1 : 0) + 1;
+        case _LOAD_GLOBAL_BUILTINS:
+            return ((oparg & 1) ? 1 : 0) + 1;
         case LOAD_GLOBAL_MODULE:
             return (oparg & 1 ? 1 : 0) + 1;
         case LOAD_GLOBAL_BUILTIN:
@@ -738,6 +841,12 @@ int _PyOpcode_num_pushed(int opcode, int oparg, bool jump)  {
             return ((oparg & 1) ? 1 : 0) + 1;
         case LOAD_METHOD:
             return ((oparg & 1) ? 1 : 0) + 1;
+        case _GUARD_TYPE_VERSION:
+            return 1;
+        case _CHECK_MANAGED_OBJECT_HAS_VALUES:
+            return 1;
+        case _LOAD_ATTR_INSTANCE_VALUE:
+            return ((oparg & 1) ? 1 : 0) + 1;
         case LOAD_ATTR_INSTANCE_VALUE:
             return (oparg & 1 ? 1 : 0) + 1;
         case LOAD_ATTR_MODULE:
@@ -792,6 +901,8 @@ int _PyOpcode_num_pushed(int opcode, int oparg, bool jump)  {
             return 0;
         case POP_JUMP_IF_TRUE:
             return 0;
+        case IS_NONE:
+            return 1;
         case POP_JUMP_IF_NONE:
             return 0;
         case POP_JUMP_IF_NOT_NONE:
@@ -816,10 +927,28 @@ int _PyOpcode_num_pushed(int opcode, int oparg, bool jump)  {
             return 2;
         case INSTRUMENTED_FOR_ITER:
             return 0;
+        case _ITER_CHECK_LIST:
+            return 1;
+        case _IS_ITER_EXHAUSTED_LIST:
+            return 2;
+        case _ITER_NEXT_LIST:
+            return 2;
         case FOR_ITER_LIST:
             return 2;
+        case _ITER_CHECK_TUPLE:
+            return 1;
+        case _IS_ITER_EXHAUSTED_TUPLE:
+            return 2;
+        case _ITER_NEXT_TUPLE:
+            return 2;
         case FOR_ITER_TUPLE:
             return 2;
+        case _ITER_CHECK_RANGE:
+            return 1;
+        case _IS_ITER_EXHAUSTED_RANGE:
+            return 2;
+        case _ITER_NEXT_RANGE:
+            return 2;
         case FOR_ITER_RANGE:
             return 2;
         case FOR_ITER_GEN:
@@ -938,6 +1067,18 @@ int _PyOpcode_num_pushed(int opcode, int oparg, bool jump)  {
             return 0;
         case RESERVED:
             return 0;
+        case _POP_JUMP_IF_FALSE:
+            return 0;
+        case _POP_JUMP_IF_TRUE:
+            return 0;
+        case JUMP_TO_TOP:
+            return 0;
+        case SAVE_IP:
+            return 0;
+        case EXIT_TRACE:
+            return 0;
+        case INSERT:
+            return oparg + 1;
         default:
             return -1;
     }
@@ -1393,5 +1534,6 @@ const char * const _PyOpcode_uop_name[OPCODE_UOP_NAME_SIZE] = {
     [_POP_JUMP_IF_FALSE] = "_POP_JUMP_IF_FALSE",
     [_POP_JUMP_IF_TRUE] = "_POP_JUMP_IF_TRUE",
     [JUMP_TO_TOP] = "JUMP_TO_TOP",
+    [INSERT] = "INSERT",
 };
 #endif // NEED_OPCODE_METADATA
diff --git a/Include/internal/pycore_optimizer.h b/Include/internal/pycore_optimizer.h
new file mode 100644
index 0000000..2ae657c
--- /dev/null
+++ b/Include/internal/pycore_optimizer.h
@@ -0,0 +1,20 @@
+#ifndef Py_INTERNAL_OPTIMIZER_H
+#define Py_INTERNAL_OPTIMIZER_H
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#ifndef Py_BUILD_CORE
+#  error "this header requires Py_BUILD_CORE define"
+#endif
+
+#include "pycore_uops.h"
+
+int _Py_uop_analyze_and_optimize(PyCodeObject *code,
+    _PyUOpInstruction *trace, int trace_len, int curr_stackentries);
+
+
+#ifdef __cplusplus
+}
+#endif
+#endif /* !Py_INTERNAL_OPTIMIZER_H */
diff --git a/Include/internal/pycore_uops.h b/Include/internal/pycore_uops.h
index 57a5970..254eeca 100644
--- a/Include/internal/pycore_uops.h
+++ b/Include/internal/pycore_uops.h
@@ -8,7 +8,7 @@ extern "C" {
 #  error "this header requires Py_BUILD_CORE define"
 #endif
 
-#define _Py_UOP_MAX_TRACE_LENGTH 32
+#define _Py_UOP_MAX_TRACE_LENGTH 64
 
 typedef struct {
     uint32_t opcode;