Jan 13, 2024 · Jan 13, 2024 · Jan 13, 2024 · Jan 13, 2024 · Jan 14, 2024 · Jan 14, 2024
diff --git a/Lib/test/test_capi/test_opt.py b/Lib/test/test_capi/test_opt.py
        uops = {opname for opname, _, _ in ex}
        self.assertNotIn("_SHRINK_STACK", uops)

    def test_int_constant_propagation_many(self):
        def testfunc(loops):
            num = 0
            for _ in range(loops):
                x = 0
                y = 1
                a = x + y + x + y + x + y + x + y
            return a

        opt = _testinternalcapi.get_uop_optimizer()
        res = None
        with temporary_optimizer(opt):
            res = testfunc(64)

        ex = get_first_executor(testfunc)
        self.assertIsNotNone(ex)
        self.assertEqual(res, 4)
        binop_count = [opname for opname, _, _ in ex if opname == "_BINARY_OP_ADD_INT"]
        self.assertEqual(len(binop_count), 0)
        uops = {opname for opname, _, _ in ex}
        self.assertNotIn("_SHRINK_STACK", uops)

    def test_int_type_propagation(self):
        def testfunc(loops):
            num = 0
diff --git a/Python/optimizer_analysis.c b/Python/optimizer_analysis.c

 #define OVERALLOCATE_FACTOR 3

 #define PEEPHOLE_MAX_ATTEMPTS 10

 #ifdef Py_DEBUG
    static const char *const DEBUG_ENV = "PYTHON_OPT_DEBUG";
    #define DPRINTF(level, ...) \
    }
    PyMem_Free(self->t_arena.arena);
    PyMem_Free(self->s_arena.arena);
    PyMem_Free(self->frame_info.arena);
    Py_TYPE(self)->tp_free((PyObject *)self);
 }


 }

 int
 staticint
 uop_abstract_interpret(
    PyCodeObject *co,
    _PyUOpInstruction *trace,
    }
 }

 static void
 static inline bool
 op_is_zappable(int opcode)
 {
    switch(opcode) {
        case _SET_IP:
        case _CHECK_VALIDITY:
        case _LOAD_CONST_INLINE:
        case _LOAD_CONST:
        case _LOAD_FAST:
        case _LOAD_CONST_INLINE_BORROW:
            return true;
        default:
            return false;
    }
 }

 static inline bool
 op_is_load(int opcode)
 {
    return (opcode == _LOAD_CONST_INLINE ||
        opcode == _LOAD_CONST ||
        opcode == LOAD_FAST ||
        opcode == _LOAD_CONST_INLINE_BORROW);
 }

 static int
 peephole_optimizations(_PyUOpInstruction *buffer, int buffer_size)
 {
    bool done = true;
    for (int i = 0; i < buffer_size; i++) {
        _PyUOpInstruction *curr = buffer + i;
        int oparg = curr->oparg;
        switch(curr->opcode) {
            case _SHRINK_STACK: {
                // If all that precedes a _SHRINK_STACK is a bunch of LOAD_FAST,
                // then we can safely eliminate that without side effects.
                intload_fast_count = 0;
                intload_count = 0;
                _PyUOpInstruction *back = curr-1;
                while((back->opcode == _SET_IP ||
                    back->opcode == _CHECK_VALIDITY ||
                    back->opcode == LOAD_FAST) &&
                    load_fast_count < oparg) {
                    load_fast_count += back->opcode == LOAD_FAST;
                while(op_is_zappable(back->opcode) &&
                    load_count < oparg) {
                    load_count += op_is_load(back->opcode);
                    back--;
                }
                if (load_fast_count == oparg) {
                if (load_count == oparg) {
                    done = false;
                    curr->opcode = NOP;
                    back = curr-1;
                    load_fast_count = 0;
                    while((back->opcode == _SET_IP ||
                           back->opcode == _CHECK_VALIDITY ||
                           back->opcode == LOAD_FAST) &&
                          load_fast_count < oparg) {
                        load_fast_count += back->opcode == LOAD_FAST;
                    load_count = 0;
                    while(load_count < oparg) {
                        load_count += op_is_load(back->opcode);
                        back->opcode = NOP;
                        back--;
                    }
                break;
        }
    }
    return done;
 }


        goto error;
    }

    peephole_optimizations(temp_writebuffer, new_trace_len);
    for (int peephole_attempts = 0; peephole_attempts < PEEPHOLE_MAX_ATTEMPTS &&
        !peephole_optimizations(temp_writebuffer, new_trace_len);
         peephole_attempts++) {

    }

    remove_unneeded_uops(temp_writebuffer, new_trace_len);
Original file line number	Diff line number	Diff line change
Expand Up		@@ -566,6 +566,28 @@ def testfunc(loops):
		uops = {opname for opname, _, _ in ex}
		self.assertNotIn("_SHRINK_STACK", uops)

		def test_int_constant_propagation_many(self):
		def testfunc(loops):
		num = 0
		for _ in range(loops):
		x = 0
		y = 1
		a = x + y + x + y + x + y + x + y
		return a

		opt = _testinternalcapi.get_uop_optimizer()
		res = None
		with temporary_optimizer(opt):
		res = testfunc(64)

		ex = get_first_executor(testfunc)
		self.assertIsNotNone(ex)
		self.assertEqual(res, 4)
		binop_count = [opname for opname, _, _ in ex if opname == "_BINARY_OP_ADD_INT"]
		self.assertEqual(len(binop_count), 0)
		uops = {opname for opname, _, _ in ex}
		self.assertNotIn("_SHRINK_STACK", uops)

		def test_int_type_propagation(self):
		def testfunc(loops):
		num = 0
Expand Down
Original file line number	Diff line number	Diff line change
Expand Up		@@ -23,6 +23,8 @@

		#define OVERALLOCATE_FACTOR 3

		#define PEEPHOLE_MAX_ATTEMPTS 10

		#ifdef Py_DEBUG
		static const char *const DEBUG_ENV = "PYTHON_OPT_DEBUG";
		#define DPRINTF(level, ...) \
Expand DownExpand Up		@@ -227,6 +229,7 @@ abstractinterp_dealloc(PyObject *o)
		}
		PyMem_Free(self->t_arena.arena);
		PyMem_Free(self->s_arena.arena);
		PyMem_Free(self->frame_info.arena);
		Py_TYPE(self)->tp_free((PyObject *)self);
		}

Expand DownExpand Up		@@ -1207,7 +1210,7 @@ uop_abstract_interpret_single_inst(

		}

		int
		staticint
		uop_abstract_interpret(
		PyCodeObject *co,
		_PyUOpInstruction *trace,
Expand DownExpand Up		@@ -1323,34 +1326,56 @@ remove_unneeded_uops(_PyUOpInstruction *buffer, int buffer_size)
		}
		}

		static void
		static inline bool
		op_is_zappable(int opcode)
		{
		switch(opcode) {
		case _SET_IP:
Copy link Member gvanrossumJan 30, 2024 Choose a reason for hiding this comment The reason will be displayed to describe this comment to others.Learn more. I think this is missing`_NOP`. It seems a fine opcode to back over in the peepholer. :-) Copy link Member gvanrossumJan 31, 2024• edited Loading Choose a reason for hiding this comment The reason will be displayed to describe this comment to others.Learn more. Interestingly, after I do this, I believe we won't need to run the peepholer more than once. (I put in`assert(peephole_attempts == 0 \|\| done);` after the call and it didn't fail a thing.) SO that would simplify things a bit. I also have a more radical idea: we can move the two things that the peepholer currently does (`_SHRINK_STACK` and`_CHECK_PEP_523`) to hand-written cases in`uop_abstract_interpret_single_inst()`. Then we don't need the peepholer at all any more. Copy link Member gvanrossumJan 31, 2024 Choose a reason for hiding this comment The reason will be displayed to describe this comment to others.Learn more. Okay, so that doesn't work for`_SHRINK_STACK`, because it's beinggenerated by`uop_abstract_interpret_single_inst()`, not consumed. But it could probably be moved to`emit_const()` quite easily. The advantage of doing it on the fly instead of in a separate peephole pass is that we reduce the risk that we'll run out of buffer space -- the current code occasionally emits more instructions than the input (namely whenever it emits`_SHRINK_STACK`), whichpotentially (if we get very close to the limit) could cause the optimizer to fail even if, using a longer buffer, it would have succeeded and produced a shorter result. There would still be worst-case scenarios where we'd end up with many non-zappable`_SHRINK_STACK` uops, but in most cases the instant zapping would free up output space. Copy link MemberAuthor Fidget-SpinnerJan 31, 2024 Choose a reason for hiding this comment The reason will be displayed to describe this comment to others.Learn more. Right now actually the peepholer only needs to run once. I just let it run a few times just to be sure. My intuition why it can eliminate all`_SHRINK_STACK` on the first run is that since we are operating on a bytecode stack machine IR, which is operating forwards. Copy link Member gvanrossumJan 31, 2024 Choose a reason for hiding this comment The reason will be displayed to describe this comment to others.Learn more. But see mycounter-example of a walrus:`A + (X := B*C)`. Either way it seems we both agree that`_SHRINK_STACK` is a temporary crutch.
		case _CHECK_VALIDITY:
		case _LOAD_CONST_INLINE:
		case _LOAD_CONST:
		case _LOAD_FAST:
		case _LOAD_CONST_INLINE_BORROW:
		return true;
		default:
		return false;
		}
		}

		static inline bool
		op_is_load(int opcode)
		{
		return (opcode == _LOAD_CONST_INLINE \|\|
		opcode == _LOAD_CONST \|\|
		opcode == LOAD_FAST \|\|
		opcode == _LOAD_CONST_INLINE_BORROW);
		}

		static int
		peephole_optimizations(_PyUOpInstruction *buffer, int buffer_size)
		{
		bool done = true;
		for (int i = 0; i < buffer_size; i++) {
		_PyUOpInstruction *curr = buffer + i;
		int oparg = curr->oparg;
		switch(curr->opcode) {
		case _SHRINK_STACK: {
		// If all that precedes a _SHRINK_STACK is a bunch of LOAD_FAST,
		// then we can safely eliminate that without side effects.
		intload_fast_count = 0;
		intload_count = 0;
		_PyUOpInstruction *back = curr-1;
		while((back->opcode == _SET_IP \|\|
		back->opcode == _CHECK_VALIDITY \|\|
		back->opcode == LOAD_FAST) &&
		load_fast_count < oparg) {
		load_fast_count += back->opcode == LOAD_FAST;
		while(op_is_zappable(back->opcode) &&
		load_count < oparg) {
Fidget-Spinner marked this conversation as resolved. OutdatedShow resolvedHide resolved
		load_count += op_is_load(back->opcode);
		back--;
		}
		if (load_fast_count == oparg) {
		if (load_count == oparg) {
		done = false;
		curr->opcode = NOP;
		back = curr-1;
		load_fast_count = 0;
		while((back->opcode == _SET_IP \|\|
		back->opcode == _CHECK_VALIDITY \|\|
		back->opcode == LOAD_FAST) &&
		load_fast_count < oparg) {
		load_fast_count += back->opcode == LOAD_FAST;
		load_count = 0;
		while(load_count < oparg) {
		load_count += op_is_load(back->opcode);
		back->opcode = NOP;
		back--;
		}
Expand All		@@ -1368,6 +1393,7 @@ peephole_optimizations(_PyUOpInstruction *buffer, int buffer_size)
		break;
		}
		}
		return done;
		}


Expand DownExpand Up		@@ -1396,7 +1422,11 @@ _Py_uop_analyze_and_optimize(
		goto error;
		}

		peephole_optimizations(temp_writebuffer, new_trace_len);
		for (int peephole_attempts = 0; peephole_attempts < PEEPHOLE_MAX_ATTEMPTS &&
		!peephole_optimizations(temp_writebuffer, new_trace_len);
		peephole_attempts++) {

		}

		remove_unneeded_uops(temp_writebuffer, new_trace_len);

Expand Down