Aug 15, 2023 · Aug 2, 2023 · Aug 2, 2023 · Aug 2, 2023 · Aug 2, 2023 · Aug 2, 2023
diff --git a/Include/cpython/optimizer.h b/Include/cpython/optimizer.h
 typedef struct _PyOptimizerObject _PyOptimizerObject;

 /* Should return > 0 if a new executor is created. O if no executor is produced and < 0 if an error occurred. */
 typedef int (*optimize_func)(_PyOptimizerObject* self, PyCodeObject *code, _Py_CODEUNIT *instr, _PyExecutorObject **);
 typedef int (*optimize_func)(_PyOptimizerObject* self, PyCodeObject *code, _Py_CODEUNIT *instr, _PyExecutorObject **, int curr_stackentries);

 typedef struct _PyOptimizerObject {
    PyObject_HEAD
diff --git a/Include/internal/pycore_optimizer.h b/Include/internal/pycore_optimizer.h

 #include "pycore_uops.h"

 int _Py_uop_analyze_and_optimize(_PyUOpInstruction *trace, int trace_len);
 int _Py_uop_analyze_and_optimize(PyCodeObject *code,
    _PyUOpInstruction *trace, int trace_len, int curr_stackentries);


 #ifdef __cplusplus
 }
diff --git a/Python/optimizer.c b/Python/optimizer.c
    _PyOptimizerObject* self,
    PyCodeObject *code,
    _Py_CODEUNIT *instr,
    _PyExecutorObject **exec)
    _PyExecutorObject **exec,
    int Py_UNUSED(stack_entries))
 {
    PyErr_Format(PyExc_SystemError, "Should never call error_optimize");
    return -1;
    }
    _PyOptimizerObject *opt = interp->optimizer;
    _PyExecutorObject *executor = NULL;
    int err = opt->optimize(opt, code, dest, &executor);
    int err = opt->optimize(opt, code, dest, &executor, (int)(stack_pointer - _PyFrame_Stackbase(frame)));
    if (err <= 0) {
        assert(executor == NULL);
        if (err < 0) {
    _PyOptimizerObject* self,
    PyCodeObject *code,
    _Py_CODEUNIT *instr,
    _PyExecutorObject **exec_ptr)
    _PyExecutorObject **exec_ptr,
    int Py_UNUSED(curr_stackentries)
 )
 {
    _PyCounterExecutorObject *executor = (_PyCounterExecutorObject *)_PyObject_New(&CounterExecutor_Type);
    if (executor == NULL) {
    _PyOptimizerObject *self,
    PyCodeObject *code,
    _Py_CODEUNIT *instr,
    _PyExecutorObject **exec_ptr)
    _PyExecutorObject **exec_ptr,
    int curr_stackentries)
 {
    _PyUOpInstruction trace[_Py_UOP_MAX_TRACE_LENGTH];
    int trace_length = translate_bytecode_to_trace(code, instr, trace, _Py_UOP_MAX_TRACE_LENGTH);
        return -1;
    }
    executor->base.execute = _PyUopExecute;
    trace_length = _Py_uop_analyze_and_optimize(trace, trace_length);
    trace_length = _Py_uop_analyze_and_optimize(code,trace, trace_length, curr_stackentries);
    memcpy(executor->trace, trace, trace_length * sizeof(_PyUOpInstruction));
    if (trace_length < _Py_UOP_MAX_TRACE_LENGTH) {
        executor->trace[trace_length].opcode = 0;  // Sentinel
diff --git a/Python/optimizer_analysis.c b/Python/optimizer_analysis.c
 #include <stddef.h>
 #include "pycore_optimizer.h"

 // TYPENODE is a tagged pointer that uses the last 2 LSB as the tag
 #define _Py_PARTITIONNODE_t uintptr_t

 // PARTITIONNODE Tags
 typedef enum _Py_TypeNodeTags {
    // Node is unused
    TYPE_NULL = 0,
    // TYPE_ROOT_POSITIVE can point to a root struct or be a NULL
    TYPE_ROOT= 1,
    // TYPE_REF points to a TYPE_ROOT or a TYPE_REF
    TYPE_REF = 2,
 } _Py_TypeNodeTags;

 typedef struct _Py_PartitionRootNode {
    PyObject_HEAD
    // For partial evaluation
    uint8_t static_or_dyanmic;
    // For types (TODO)
 } _Py_PartitionRootNode;

 PyTypeObject _Py_PartitionRootNode_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    .tp_name = "uops abstract interpreter's root node",
    .tp_basicsize = sizeof(_Py_PartitionRootNode),
    .tp_dealloc = PyObject_Del,
    .tp_flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_DISALLOW_INSTANTIATION
 };

 static inline _Py_PARTITIONNODE_t
 partitionnode_get_tag(_Py_PARTITIONNODE_t node)
 {
    return node & 0b11;
 }

 static inline _Py_PARTITIONNODE_t
 partitionnode_clear_tag(_Py_PARTITIONNODE_t node)
 {
    return node & (~(uintptr_t)(0b11));
 }

 static inline _Py_PARTITIONNODE_t
 partitionnode_make_root(uint8_t static_or_dynamic)
 {
    _Py_PartitionRootNode *root = PyObject_New(_Py_PartitionRootNode, &_Py_PartitionRootNode_Type);
    if (root == NULL) {
        return 0;
    }
    root->static_or_dyanmic = static_or_dynamic;
    return (_Py_PARTITIONNODE_t)root;
 }

 static inline _Py_PARTITIONNODE_t
 partitionnode_make_ref(_Py_PARTITIONNODE_t node)
 {
    return partitionnode_clear_tag(node) | TYPE_REF;
 }

 static inline _Py_PARTITIONNODE_t
 partitionnode_null()
 {
    return 0;
 }


 // Tier 2 types meta interpreter
 typedef struct _Py_UOpsAbstractInterpContext {
    PyObject_HEAD
    // points to one element after the abstract stack
    _Py_PARTITIONNODE_t *stack_pointer;
    int stack_len;
    _Py_PARTITIONNODE_t *stack;
    int locals_len;
    _Py_PARTITIONNODE_t *locals;
 } _Py_UOpsAbstractInterpContext;

 static void
 abstractinterp_dealloc(PyObject *o)
 {
    _Py_UOpsAbstractInterpContext *self = (_Py_UOpsAbstractInterpContext *)o;
    PyMem_Free(self->stack);
    PyMem_Free(self->locals);
    // TODO traverse the nodes and decref all roots too.
    Py_TYPE(self)->tp_free((PyObject *)self);
 }

 PyTypeObject _Py_UOpsAbstractInterpContext_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    .tp_name = "uops abstract interpreter's context",
    .tp_basicsize = sizeof(_Py_UOpsAbstractInterpContext),
    .tp_dealloc = abstractinterp_dealloc,
    .tp_flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_DISALLOW_INSTANTIATION
 };

 _Py_UOpsAbstractInterpContext *
 _Py_UOpsAbstractInterpContext_New(int stack_len, int locals_len, int curr_stacklen)
 {
    _Py_UOpsAbstractInterpContext *self = (_Py_UOpsAbstractInterpContext *)PyType_GenericAlloc(
        (PyTypeObject *)&_Py_UOpsAbstractInterpContext_Type, 0);
    if (self == NULL) {
        return NULL;
    }

    // Setup
    self->stack_len = stack_len;
    self->locals_len = locals_len;

    _Py_PARTITIONNODE_t *locals_with_stack = PyMem_New(_Py_PARTITIONNODE_t, locals_len + stack_len);
    if (locals_with_stack == NULL) {
        Py_DECREF(self);
        return NULL;
    }


    for (int i = 0; i < locals_len + stack_len; i++) {
        locals_with_stack[i] = partitionnode_null();
    }

    self->locals = locals_with_stack;
    self->stack = locals_with_stack + locals_len;
    self->stack_pointer = self->stack + curr_stacklen;

    return self;
 }

 int
 _Py_uop_analyze_and_optimize(
    PyCodeObject *co,
    _PyUOpInstruction *trace,
    int trace_len
    int trace_len,
    int curr_stacklen
 )
 {
 #define STACK_LEVEL()     ((int)(stack_pointer - ctx->stack))
 #define STACK_SIZE()      (co->co_stacksize)
 #define BASIC_STACKADJ(n) (stack_pointer += n)

 #ifdef Py_DEBUG
 #define STACK_GROW(n)   do { \
                            assert(n >= 0); \
                            BASIC_STACKADJ(n); \
                            assert(STACK_LEVEL() <= STACK_SIZE()); \
                        } while (0)
 #define STACK_SHRINK(n) do { \
                            assert(n >= 0); \
                            assert(STACK_LEVEL() >= n); \
                            BASIC_STACKADJ(-(n)); \
                        } while (0)
 #else
 #define STACK_GROW(n)          BASIC_STACKADJ(n)
 #define STACK_SHRINK(n)        BASIC_STACKADJ(-(n))
 #endif
    _PyUOpInstruction *temp_writebuffer = PyMem_New(_PyUOpInstruction, trace_len);
    if (temp_writebuffer == NULL) {
        return trace_len;
    }

    _Py_UOpsAbstractInterpContext *ctx = _Py_UOpsAbstractInterpContext_New(co->co_stacksize, co->co_nlocals, curr_stacklen);
    if (ctx == NULL) {
        PyMem_Free(temp_writebuffer);
        return trace_len;
    }

    int oparg;
    int opcode;
    _Py_PARTITIONNODE_t *stack_pointer = ctx->stack_pointer;
    for (int i = 0; i < trace_len; i++) {
        oparg = trace[i].oparg;
        opcode = trace[i].opcode;
        switch (opcode) {
 #include "abstract_interp_cases.c.h"
        default:
            fprintf(stderr, "Unknown opcode in abstract interpreter\n");
            Py_UNREACHABLE();
        }
        ctx->stack_pointer = stack_pointer;

    }
    assert(STACK_SIZE() >= 0);
    return trace_len;
 }
diff --git a/Tools/cases_generator/generate_cases.py b/Tools/cases_generator/generate_cases.py

 INSTR_FMT_PREFIX = "INSTR_FMT_"

 # @TODO generate all these after updating the DSL
 SPECIALLY_HANDLED_ABSTRACT_INSTR = {
    # "LOAD_FAST",
    # "LOAD_FAST_CHECK",
    # "LOAD_FAST_AND_CLEAR",
    # "LOAD_CONST",
    # "STORE_FAST",
    # "STORE_FAST_MAYBE_NULL",
    # "COPY",
 }

 arg_parser = argparse.ArgumentParser(
    description="Generate the code for the interpreter switch.",
    formatter_class=argparse.ArgumentDefaultsHelpFormatter,
                        self.write_overridden_instr_place_holder(thing)
                    case parsing.InstDef():
                        instr = AbstractInstruction(self.instrs[thing.name].inst)
                        self.out.emit("")
                        if instr.is_viable_uop():
                        if instr.is_viable_uop() and instr.name not in SPECIALLY_HANDLED_ABSTRACT_INSTR:
                            self.out.emit("")
                            with self.out.block(f"case {thing.name}:"):
                                instr.write(self.out, tier=TIER_TWO)
diff --git a/Tools/cases_generator/stacking.py b/Tools/cases_generator/stacking.py
                        poke.effect.cond,
                        poke.effect.size,
                    ),
                    StackEffect("NULL"),
                    StackEffect("partitionnode_null()"),
                )
Original file line number	Diff line number	Diff line change
Expand Up		@@ -22,7 +22,7 @@ typedef struct _PyExecutorObject {
		typedef struct _PyOptimizerObject _PyOptimizerObject;

		/* Should return > 0 if a new executor is created. O if no executor is produced and < 0 if an error occurred. */
		typedef int (optimize_func)(_PyOptimizerObject self, PyCodeObject code, _Py_CODEUNIT instr, _PyExecutorObject **);
		typedef int (optimize_func)(_PyOptimizerObject self, PyCodeObject code, _Py_CODEUNIT instr, _PyExecutorObject **, int curr_stackentries);

		typedef struct _PyOptimizerObject {
		PyObject_HEAD
Expand Down
Original file line number	Diff line number	Diff line change
Expand Up		@@ -10,7 +10,9 @@ extern "C" {

		#include "pycore_uops.h"

		int _Py_uop_analyze_and_optimize(_PyUOpInstruction *trace, int trace_len);
		int _Py_uop_analyze_and_optimize(PyCodeObject *code,
		_PyUOpInstruction *trace, int trace_len, int curr_stackentries);


		#ifdef __cplusplus
		}
Expand Down
Original file line number	Diff line number	Diff line change
Expand Up		@@ -104,7 +104,8 @@ error_optimize(
		_PyOptimizerObject* self,
		PyCodeObject *code,
		_Py_CODEUNIT *instr,
		_PyExecutorObject **exec)
		_PyExecutorObject **exec,
		int Py_UNUSED(stack_entries))
		{
		PyErr_Format(PyExc_SystemError, "Should never call error_optimize");
		return -1;
Expand DownExpand Up		@@ -165,7 +166,7 @@ _PyOptimizer_BackEdge(_PyInterpreterFrame frame, _Py_CODEUNIT src, _Py_CODEUNI
		}
		_PyOptimizerObject *opt = interp->optimizer;
		_PyExecutorObject *executor = NULL;
		int err = opt->optimize(opt, code, dest, &executor);
		int err = opt->optimize(opt, code, dest, &executor, (int)(stack_pointer - _PyFrame_Stackbase(frame)));
		if (err <= 0) {
		assert(executor == NULL);
		if (err < 0) {
Expand DownExpand Up		@@ -255,7 +256,9 @@ counter_optimize(
		_PyOptimizerObject* self,
		PyCodeObject *code,
		_Py_CODEUNIT *instr,
		_PyExecutorObject **exec_ptr)
		_PyExecutorObject **exec_ptr,
		int Py_UNUSED(curr_stackentries)
		)
		{
		_PyCounterExecutorObject executor = (_PyCounterExecutorObject )_PyObject_New(&CounterExecutor_Type);
		if (executor == NULL) {
Expand DownExpand Up		@@ -691,7 +694,8 @@ uop_optimize(
		_PyOptimizerObject *self,
		PyCodeObject *code,
		_Py_CODEUNIT *instr,
		_PyExecutorObject **exec_ptr)
		_PyExecutorObject **exec_ptr,
		int curr_stackentries)
		{
		_PyUOpInstruction trace[_Py_UOP_MAX_TRACE_LENGTH];
		int trace_length = translate_bytecode_to_trace(code, instr, trace, _Py_UOP_MAX_TRACE_LENGTH);
Expand All		@@ -705,7 +709,7 @@ uop_optimize(
		return -1;
		}
		executor->base.execute = _PyUopExecute;
		trace_length = _Py_uop_analyze_and_optimize(trace, trace_length);
		trace_length = _Py_uop_analyze_and_optimize(code,trace, trace_length, curr_stackentries);
		memcpy(executor->trace, trace, trace_length * sizeof(_PyUOpInstruction));
		if (trace_length < _Py_UOP_MAX_TRACE_LENGTH) {
		executor->trace[trace_length].opcode = 0; // Sentinel
Expand Down
Original file line number	Diff line number	Diff line change
Expand Up		@@ -12,11 +12,183 @@
		#include <stddef.h>
		#include "pycore_optimizer.h"

		// TYPENODE is a tagged pointer that uses the last 2 LSB as the tag
		#define _Py_PARTITIONNODE_t uintptr_t

		// PARTITIONNODE Tags
		typedef enum _Py_TypeNodeTags {
		// Node is unused
		TYPE_NULL = 0,
		// TYPE_ROOT_POSITIVE can point to a root struct or be a NULL
		TYPE_ROOT= 1,
		// TYPE_REF points to a TYPE_ROOT or a TYPE_REF
		TYPE_REF = 2,
		} _Py_TypeNodeTags;

		typedef struct _Py_PartitionRootNode {
		PyObject_HEAD
		// For partial evaluation
		uint8_t static_or_dyanmic;
		// For types (TODO)
		} _Py_PartitionRootNode;

		PyTypeObject _Py_PartitionRootNode_Type = {
		PyVarObject_HEAD_INIT(&PyType_Type, 0)
		.tp_name = "uops abstract interpreter's root node",
		.tp_basicsize = sizeof(_Py_PartitionRootNode),
		.tp_dealloc = PyObject_Del,
		.tp_flags = Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_DISALLOW_INSTANTIATION
		};

		static inline _Py_PARTITIONNODE_t
		partitionnode_get_tag(_Py_PARTITIONNODE_t node)
		{
		return node & 0b11;
		}

		static inline _Py_PARTITIONNODE_t
		partitionnode_clear_tag(_Py_PARTITIONNODE_t node)
		{
		return node & (~(uintptr_t)(0b11));
		}

		static inline _Py_PARTITIONNODE_t
		partitionnode_make_root(uint8_t static_or_dynamic)
		{
		_Py_PartitionRootNode *root = PyObject_New(_Py_PartitionRootNode, &_Py_PartitionRootNode_Type);
		if (root == NULL) {
		return 0;
		}
		root->static_or_dyanmic = static_or_dynamic;
		return (_Py_PARTITIONNODE_t)root;
		}

		static inline _Py_PARTITIONNODE_t
		partitionnode_make_ref(_Py_PARTITIONNODE_t node)
		{
		return partitionnode_clear_tag(node) \| TYPE_REF;
		}

		static inline _Py_PARTITIONNODE_t
		partitionnode_null()
		{
		return 0;
		}


		// Tier 2 types meta interpreter
		typedef struct _Py_UOpsAbstractInterpContext {
		PyObject_HEAD
		// points to one element after the abstract stack
		_Py_PARTITIONNODE_t *stack_pointer;
		int stack_len;
		_Py_PARTITIONNODE_t *stack;
		int locals_len;
		_Py_PARTITIONNODE_t *locals;
		} _Py_UOpsAbstractInterpContext;

		static void
		abstractinterp_dealloc(PyObject *o)
		{
		_Py_UOpsAbstractInterpContext self = (_Py_UOpsAbstractInterpContext )o;
		PyMem_Free(self->stack);
		PyMem_Free(self->locals);
		// TODO traverse the nodes and decref all roots too.
		Py_TYPE(self)->tp_free((PyObject *)self);
		}

		PyTypeObject _Py_UOpsAbstractInterpContext_Type = {
		PyVarObject_HEAD_INIT(&PyType_Type, 0)
		.tp_name = "uops abstract interpreter's context",
		.tp_basicsize = sizeof(_Py_UOpsAbstractInterpContext),
		.tp_dealloc = abstractinterp_dealloc,
		.tp_flags = Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_DISALLOW_INSTANTIATION
		};

		_Py_UOpsAbstractInterpContext *
		_Py_UOpsAbstractInterpContext_New(int stack_len, int locals_len, int curr_stacklen)
		{
		_Py_UOpsAbstractInterpContext self = (_Py_UOpsAbstractInterpContext )PyType_GenericAlloc(
		(PyTypeObject *)&_Py_UOpsAbstractInterpContext_Type, 0);
		if (self == NULL) {
		return NULL;
		}

		// Setup
		self->stack_len = stack_len;
		self->locals_len = locals_len;

		_Py_PARTITIONNODE_t *locals_with_stack = PyMem_New(_Py_PARTITIONNODE_t, locals_len + stack_len);
		if (locals_with_stack == NULL) {
		Py_DECREF(self);
		return NULL;
		}


		for (int i = 0; i < locals_len + stack_len; i++) {
		locals_with_stack[i] = partitionnode_null();
		}

		self->locals = locals_with_stack;
		self->stack = locals_with_stack + locals_len;
		self->stack_pointer = self->stack + curr_stacklen;

		return self;
		}

		int
		_Py_uop_analyze_and_optimize(
		PyCodeObject *co,
		_PyUOpInstruction *trace,
		int trace_len
		int trace_len,
		int curr_stacklen
		)
		{
		#define STACK_LEVEL() ((int)(stack_pointer - ctx->stack))
		#define STACK_SIZE() (co->co_stacksize)
		#define BASIC_STACKADJ(n) (stack_pointer += n)

		#ifdef Py_DEBUG
		#define STACK_GROW(n) do { \
		assert(n >= 0); \
		BASIC_STACKADJ(n); \
		assert(STACK_LEVEL() <= STACK_SIZE()); \
		} while (0)
		#define STACK_SHRINK(n) do { \
		assert(n >= 0); \
		assert(STACK_LEVEL() >= n); \
		BASIC_STACKADJ(-(n)); \
		} while (0)
		#else
		#define STACK_GROW(n) BASIC_STACKADJ(n)
		#define STACK_SHRINK(n) BASIC_STACKADJ(-(n))
		#endif
		_PyUOpInstruction *temp_writebuffer = PyMem_New(_PyUOpInstruction, trace_len);
		if (temp_writebuffer == NULL) {
		return trace_len;
		}

		_Py_UOpsAbstractInterpContext *ctx = _Py_UOpsAbstractInterpContext_New(co->co_stacksize, co->co_nlocals, curr_stacklen);
		if (ctx == NULL) {
		PyMem_Free(temp_writebuffer);
		return trace_len;
		}

		int oparg;
		int opcode;
		_Py_PARTITIONNODE_t *stack_pointer = ctx->stack_pointer;
		for (int i = 0; i < trace_len; i++) {
		oparg = trace[i].oparg;
		opcode = trace[i].opcode;
		switch (opcode) {
		#include "abstract_interp_cases.c.h"
		default:
		fprintf(stderr, "Unknown opcode in abstract interpreter\n");
		Py_UNREACHABLE();
		}
		ctx->stack_pointer = stack_pointer;

		}
		assert(STACK_SIZE() >= 0);
		return trace_len;
		}
Original file line number	Diff line number	Diff line change
Expand Up		@@ -61,6 +61,17 @@

		INSTR_FMT_PREFIX = "INSTR_FMT_"

		# @TODO generate all these after updating the DSL
Fidget-Spinner marked this conversation as resolved. OutdatedShow resolvedHide resolved
		SPECIALLY_HANDLED_ABSTRACT_INSTR = {
		# "LOAD_FAST",
		# "LOAD_FAST_CHECK",
		# "LOAD_FAST_AND_CLEAR",
		# "LOAD_CONST",
		# "STORE_FAST",
		# "STORE_FAST_MAYBE_NULL",
		# "COPY",
		}

		arg_parser = argparse.ArgumentParser(
		description="Generate the code for the interpreter switch.",
		formatter_class=argparse.ArgumentDefaultsHelpFormatter,
Expand DownExpand Up		@@ -628,8 +639,7 @@ def write_abstract_interpreter_instructions(
		self.write_overridden_instr_place_holder(thing)
		case parsing.InstDef():
		instr = AbstractInstruction(self.instrs[thing.name].inst)
		self.out.emit("")
		if instr.is_viable_uop():
		if instr.is_viable_uop() and instr.name not in SPECIALLY_HANDLED_ABSTRACT_INSTR:
		self.out.emit("")
		with self.out.block(f"case {thing.name}:"):
		instr.write(self.out, tier=TIER_TWO)
Copy link Member gvanrossumAug 13, 2023 Choose a reason for hiding this comment The reason will be displayed to describe this comment to others.Learn more. Note that ingh-107760 I'm removing`Instruction.write` altogether.
Expand Down
Original file line number	Diff line number	Diff line change
Expand Up		@@ -432,5 +432,5 @@ def _write_components_for_abstract_interp(
		poke.effect.cond,
		poke.effect.size,
		),
		StackEffect("NULL"),
		StackEffect("partitionnode_null()"),
		)