10000 gh-114058: Foundations of the Tier2 redundancy eliminator (GH-115085) · python/cpython@7cce857 · GitHub
[go: up one dir, main page]
Skip to content

Commit 7cce857

Browse files
Fidget-SpinnermarkshannonJuliaPoogvanrossum
authored
gh-114058: Foundations of the Tier2 redundancy eliminator (GH-115085)
--------- Co-authored-by: Mark Shannon <9448417+markshannon@users.noreply.github.com> Co-authored-by: Jules <57632293+JuliaPoo@users.noreply.github.com> Co-authored-by: Guido van Rossum <gvanrossum@users.noreply.github.com>
1 parent ccc76c3 commit 7cce857

25 files changed

+3137
-140
lines changed

‎.gitattributes

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -94,6 +94,7 @@ Programs/test_frozenmain.h generated
9494
Python/Python-ast.c generated
9595
Python/executor_cases.c.h generated
9696
Python/generated_cases.c.h generated
97+
Python/tier2_redundancy_eliminator_bytecodes.c.h generated
9798
Python/opcode_targets.h generated
9899
Python/stdlib_module_names.h generated
99100
Tools/peg_generator/pegen/grammar_parser.py generated

‎Include/cpython/pystats.h

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -120,6 +120,9 @@ typedef struct _optimization_stats {
120120
uint64_t trace_length_hist[_Py_UOP_HIST_SIZE];
121121
uint64_t trace_run_length_hist[_Py_UOP_HIST_SIZE];
122122
uint64_t optimized_trace_length_hist[_Py_UOP_HIST_SIZE];
123+
uint64_t optimizer_attempts;
124+
uint64_t optimizer_successes;
125+
uint64_t optimizer_failure_reason_no_memory;
123126
} OptimizationStats;
124127

125128
typedef struct _rare_event_stats {

‎Include/internal/pycore_opcode_metadata.h

Lines changed: 5 additions & 5 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎Include/internal/pycore_optimizer.h

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,13 @@ extern "C" {
88
# error "this header requires Py_BUILD_CORE define"
99
#endif
1010

11+
#include "pycore_uop_ids.h"
12+
13+
// This is the length of the trace we project initially.
14+
#define UOP_MAX_TRACE_LENGTH 512
15+
16+
#define TRACE_STACK_SIZE 5
17+
1118
int _Py_uop_analyze_and_optimize(_PyInterpreterFrame *frame,
1219
_PyUOpInstruction *trace, int trace_len, int curr_stackentries,
1320
_PyBloomFilter *dependencies);

‎Include/internal/pycore_uop_metadata.h

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -16,7 +16,7 @@ extern const char * const _PyOpcode_uop_name[MAX_UOP_ID+1];
1616

1717
#ifdef NEED_OPCODE_METADATA
1818
const uint16_t _PyUop_Flags[MAX_UOP_ID+1] = {
19-
[_NOP] = 0,
19+
[_NOP] = HAS_PURE_FLAG,
2020
[_RESUME_CHECK] = HAS_DEOPT_FLAG,
2121
[_LOAD_FAST_CHECK] = HAS_ARG_FLAG | HAS_LOCAL_FLAG | HAS_ERROR_FLAG,
2222
[_LOAD_FAST] = HAS_ARG_FLAG | HAS_LOCAL_FLAG | HAS_PURE_FLAG,
@@ -202,10 +202,10 @@ const uint16_t _PyUop_Flags[MAX_UOP_ID+1] = {
202202
[_SAVE_RETURN_OFFSET] = HAS_ARG_FLAG,
203203
[_EXIT_TRACE] = HAS_DEOPT_FLAG,
204204
[_CHECK_VALIDITY] = HAS_DEOPT_FLAG,
205-
[_LOAD_CONST_INLINE] = 0,
206-
[_LOAD_CONST_INLINE_BORROW] = 0,
207-
[_LOAD_CONST_INLINE_WITH_NULL] = 0,
208-
[_LOAD_CONST_INLINE_BORROW_WITH_NULL] = 0,
205+
[_LOAD_CONST_INLINE] = HAS_PURE_FLAG,
206+
[_LOAD_CONST_INLINE_BORROW] = HAS_PURE_FLAG,
207+
[_LOAD_CONST_INLINE_WITH_NULL] = HAS_PURE_FLAG,
208+
[_LOAD_CONST_INLINE_BORROW_WITH_NULL] = HAS_PURE_FLAG,
209209
[_CHECK_GLOBALS] = HAS_DEOPT_FLAG,
210210
[_CHECK_BUILTINS] = HAS_DEOPT_FLAG,
211211
[_INTERNAL_INCREMENT_OPT_COUNTER] = 0,

‎Lib/test/test_capi/test_opt.py

Lines changed: 209 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,7 @@
33
import sys
44
import textwrap
55
import unittest
6+
import gc
67

78
import _testinternalcapi
89

@@ -556,6 +557,214 @@ def testfunc(n):
556557
# too much already.
557558
self.assertEqual(count, 1)
558559

560+
class TestUopsOptimization(unittest.TestCase):
561+
< 10000 /td>562+
def test_int_type_propagation(self):
563+
def testfunc(loops):
564+
num = 0
565+
while num < loops:
566+
x = num + num
567+
a = x + 1
568+
num += 1
569+
return a
570+
571+
opt = _testinternalcapi.get_uop_optimizer()
572+
res = None
573+
with temporary_optimizer(opt):
574+
res = testfunc(32)
575+
576+
ex = get_first_executor(testfunc)
577+
self.assertIsNotNone(ex)
578+
self.assertEqual(res, 63)
579+
binop_count = [opname for opname, _, _ in ex if opname == "_BINARY_OP_ADD_INT"]
580+
guard_both_int_count = [opname for opname, _, _ in ex if opname == "_GUARD_BOTH_INT"]
581+
self.assertGreaterEqual(len(binop_count), 3)
582+
self.assertLessEqual(len(guard_both_int_count), 1)
583+
584+
def test_int_type_propagation_through_frame(self):
585+
def double(x):
586+
return x + x
587+
def testfunc(loops):
588+
num = 0
589+
while num < loops:
590+
x = num + num
591+
a = double(x)
592+
num += 1
593+
return a
594+
595+
opt = _testinternalcapi.get_uop_optimizer()
596+
res = None
597+
with temporary_optimizer(opt):
598+
res = testfunc(32)
599+
600+
ex = get_first_executor(testfunc)
601+
self.assertIsNotNone(ex)
602+
self.assertEqual(res, 124)
603+
binop_count = [opname for opname, _, _ in ex if opname == "_BINARY_OP_ADD_INT"]
604+
guard_both_int_count = [opname for opname, _, _ in ex if opname == "_GUARD_BOTH_INT"]
605+
self.assertGreaterEqual(len(binop_count), 3)
606+
self.assertLessEqual(len(guard_both_int_count), 1)
607+
608+
def test_int_type_propagation_from_frame(self):
609+
def double(x):
610+
return x + x
611+
def testfunc(loops):
612+
num = 0
613+
while num < loops:
614+
a = double(num)
615+
x = a + a
616+
num += 1
617+
return x
618+
619+
opt = _testinternalcapi.get_uop_optimizer()
620+
res = None
621+
with temporary_optimizer(opt):
622+
res = testfunc(32)
623+
624+
ex = get_first_executor(testfunc)
625+
self.assertIsNotNone(ex)
626+
self.assertEqual(res, 124)
627+
binop_count = [opname for opname, _, _ in ex if opname == "_BINARY_OP_ADD_INT"]
628+
guard_both_int_count = [opname for opname, _, _ in ex if opname == "_GUARD_BOTH_INT"]
629+
self.assertGreaterEqual(len(binop_count), 3)
630+
self.assertLessEqual(len(guard_both_int_count), 1)
631+
632+
def test_int_impure_region(self):
633+
def testfunc(loops):
634+
num = 0
635+
while num < loops:
636+
x = num + num
637+
y = 1
638+
x // 2
639+
a = x + y
640+
num += 1
641+
return a
642+
643+
opt = _testinternalcapi.get_uop_optimizer()
644+
res = None
645+
with temporary_optimizer(opt):
646+
res = testfunc(64)
647+
648+
ex = get_first_executor(testfunc)
649+
self.assertIsNotNone(ex)
650+
binop_count = [opname for opname, _, _ in ex if opname == "_BINARY_OP_ADD_INT"]
651+
self.assertGreaterEqual(len(binop_count), 3)
652+
653+
def test_call_py_exact_args(self):
654+
def testfunc(n):
655+
def dummy(x):
656+
return x+1
657+
for i in range(n):
658+
dummy(i)
659+
660+
opt = _testinternalcapi.get_uop_optimizer()
661+
with temporary_optimizer(opt):
662+
testfunc(20)
663+
664+
ex = get_first_executor(testfunc)
665+
self.assertIsNotNone(ex)
666+
uops = {opname for opname, _, _ in ex}
667+
self.assertIn("_PUSH_FRAME", uops)
668+
self.assertIn("_BINARY_OP_ADD_INT", uops)
669+
self.assertNotIn("_CHECK_PEP_523", uops)
670+
671+
def test_int_type_propagate_through_range(self):
672+
def testfunc(n):
673+
674+
for i in range(n):
675+
x = i + i
676+
return x
677+
678+
opt = _testinternalcapi.get_uop_optimizer()
679+
with temporary_optimizer(opt):
680+
res = testfunc(20)
681+
682+
ex = get_first_executor(testfunc)
683+
self.assertEqual(res, 19 * 2)
684+
self.assertIsNotNone(ex)
685+
uops = {opname for opname, _, _ in ex}
686+
self.assertNotIn("_GUARD_BOTH_INT", uops)
687+
688+
def test_int_value_numbering(self):
689+
def testfunc(n):
690+
691+
y = 1
692+
for i in range(n):
693+
x = y
694+
z = x
695+
a = z
696+
b = a
697+
res = x + z + a + b
698+
return res
699+
700+
opt = _testinternalcapi.get_uop_optimizer()
701+
with temporary_optimizer(opt):
702+
res = testfunc(20)
703+
704+
ex = get_first_executor(testfunc)
705+
self.assertEqual(res, 4)
706+
self.assertIsNotNone(ex)
707+
uops = {opname for opname, _, _ in ex}
708+
self.assertIn("_GUARD_BOTH_INT", uops)
709+
guard_count = [opname for opname, _, _ in ex if opname == "_GUARD_BOTH_INT"]
710+
self.assertEqual(len(guard_count), 1)
711+
712+
def test_comprehension(self):
713+
def testfunc(n):
714+
for _ in range(n):
715+
return [i for i in range(n)]
716+
717+
opt = _testinternalcapi.get_uop_optimizer()
718+
with temporary_optimizer(opt):
719+
testfunc(20)
720+
721+
ex = get_first_executor(testfunc)
722+
self.assertIsNotNone(ex)
723+
uops = {opname for opname, _, _ in ex}
724+
self.assertNotIn("_BINARY_OP_ADD_INT", uops)
725+
726+
def test_call_py_exact_args_disappearing(self):
727+
def dummy(x):
728+
return x+1
729+
730+
def testfunc(n):
731+
for i in range(n):
732+
dummy(i)
733+
734+
opt = _testinternalcapi.get_uop_optimizer()
735+
# Trigger specialization
736+
testfunc(8)
737+
with temporary_optimizer(opt):
738+
del dummy
739+
gc.collect()
740+
741+
def dummy(x):
742+
return x + 2
743+
testfunc(10)
744+
745+
ex = get_first_executor(testfunc)
746+
# Honestly as long as it doesn't crash it's fine.
747+
# Whether we get an executor or not is non-deterministic,
748+
# because it's decided by when the function is freed.
749+
# This test is a little implementation specific.
750+
751+
def test_promote_globals_to_constants(self):
752+
def testfunc(n):
753+
for i in range(n):
754+
x = range(i)
755+
return x
756+
757+
opt = _testinternalcapi.get_uop_optimizer()
758+
with temporary_optimizer(opt):
759+
testfunc(20)
760+
761+
ex = get_first_executor(testfunc)
762+
self.assertIsNotNone(ex)
763+
uops = {opname for opname, _, _ in ex}
764+
self.assertNotIn("_LOAD_GLOBAL_BUILTIN", uops)
765+
self.assertIn("_LOAD_CONST_INLINE_BORROW_WITH_NULL", uops)
766+
767+
559768

560769
if __name__ == "__main__":
561770
unittest.main()

0 commit comments

Comments
 (0)
0