Skip to content

gh-126835: Disable tuple folding in the AST optimizer #128802

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
tomasr8 wants to merge 23 commits into from
Closed

gh-126835: Disable tuple folding in the AST optimizer #128802

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
23 commits
Select commit Hold shift + click to select a range
2f475e1
Disable tuple folding in the AST optimizer
tomasr8 Jan 3, 2025
7a96d47
Provisionally fix tests
tomasr8 Jan 3, 2025
6d93343
Tweak tests
Eclips4 Jan 16, 2025
02a38a3
Merge branch 'main' into ast-tuple-folding
Eclips4 Jan 17, 2025
5c05d69
Restore UNPACK_SEQUENCE_TWO_TUPLE
Eclips4 Jan 21, 2025
05f3e62
Update Lib/test/test_peepholer.py
Eclips4 Jan 21, 2025
a3d9790
Merge branch 'main' into ast-tuple-folding
Eclips4 Jan 21, 2025
9f1feb4
Restore test_folding_op by changing const from tuple to a string
Eclips4 Jan 27, 2025
ac50aad
Fold set into frozenset in CFG
Eclips4 Jan 27, 2025
2b39a13
Merge branch 'main' into ast-tuple-folding
Eclips4 Feb 1, 2025
17dffaa
`for` target optimization (set/list -> frozenset/tuple)
Eclips4 Feb 1, 2025
46845f0
Fold list into a tuple as rhs in `for`/`in` operators
Eclips4 Feb 1, 2025
e9631d8
Fix tests
Eclips4 Feb 1, 2025
53dfa93
Merge branch 'main' into ast-tuple-folding
Eclips4 Feb 4, 2025
9754820
Merge branch 'main' into ast-tuple-folding
Eclips4 Feb 14, 2025
477c784
Fix merge artifacts
Eclips4 Feb 14, 2025
6731dfb
Merge branch 'main' into ast-tuple-folding
Eclips4 Feb 22, 2025
aad9fb3
Remove failing tests
Eclips4 Feb 22, 2025
be40093
Restore test_peepholer tests
Eclips4 Feb 22, 2025
5aec965
Add a few tests
Eclips4 Feb 22, 2025
ee69f0f
Restore test
Eclips4 Feb 22, 2025
0801463
Regenerate some files
Eclips4 Feb 22, 2025
a268315
Address review
Eclips4 Feb 23, 2025
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Address review
  • Loading branch information
@Eclips4
Eclips4 committed Feb 23, 2025
commit a268315f2d1503c88d25369a4701b883f25005cb
12 changes: 8 additions & 4 deletions Lib/test/test_builtin.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -555,7 +555,7 @@ def test_compile_async_generator(self):
self.assertEqual(type(glob['ticker']()), AsyncGeneratorType)

def test_compile_ast(self):
args = ("a*(1,2)", "f.py", "exec")
args = ("a*__debug__", "f.py", "exec")
raw = compile(*args, flags = ast.PyCF_ONLY_AST).body[0]
opt1 = compile(*args, flags = ast.PyCF_OPTIMIZED_AST).body[0]
opt2 = compile(ast.parse(args[0]), *args[1:], flags = ast.PyCF_OPTIMIZED_AST).body[0]
Expand All @@ -566,9 +566,13 @@ def test_compile_ast(self):
self.assertIsInstance(tree.value.left, ast.Name)
self.assertEqual(tree.value.left.id, 'a')

raw_right = raw.value.right # expect Tuple((1, 2))
self.assertIsInstance(raw_right, ast.Tuple)
self.assertListEqual([elt.value for elt in raw_right.elts], [1, 2])
raw_right = raw.value.right
self.assertIsInstance(raw_right, ast.Name)

for opt in [opt1, opt2]:
opt_right = opt.value.right
self.assertIsInstance(opt_right, ast.Constant)
self.assertEqual(opt_right.value, __debug__)

def test_delattr(self):
sys.spam = 1
Expand Down
8 changes: 8 additions & 0 deletions Lib/test/test_compile.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -793,6 +793,14 @@ def check_same_constant(const):
self.check_constant(f1, Ellipsis)
self.assertEqual(repr(f1()), repr(Ellipsis))

# Merge constants in tuple or frozenset
f1, f2 = lambda: "not a name", lambda: ("not a name",)
f3 = lambda x: x in {("not a name",)}
self.assertIs(f1.__code__.co_consts[0],
f2.__code__.co_consts[1][0])
self.assertIs(next(iter(f3.__code__.co_consts[1])),
f2.__code__.co_consts[1])

# {0} is converted to a constant frozenset({0}) by the peephole
# optimizer
f1, f2 = lambda x: x in {0}, lambda x: x in {0}
Expand Down
36 changes: 14 additions & 22 deletions Lib/test/test_peepholer.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -157,13 +157,27 @@ def test_folding_of_tuples_of_constants(self):
('a,b,c,d = 1,2,3,4', (1, 2, 3, 4)),
('(None, 1, None)', (None, 1, None)),
('((1, 2), 3, 4)', ((1, 2), 3, 4)),
('(1, 2, (3, 4))', (1, 2, (3, 4))),
('()', ()),
('(1, (2, (3, (4, (5,)))))', (1, (2, (3, (4, (5,)))))),
):
with self.subTest(line=line):
code = compile(line,'','single')
self.assertInBytecode(code, 'LOAD_CONST', elem)
self.assertNotInBytecode(code, 'BUILD_TUPLE')
self.check_lnotab(code)

for expr, length in (
('(1, a)', 2),
('(a, b, c)', 3),
('(a, (b, c))', 2),
('(1, [], {})', 3),
):
with self.subTest(expr=expr, length=length):
code = compile(expr, '', 'single')
self.assertInBytecode(code, 'BUILD_TUPLE', length)
self.check_lnotab(code)

# Long tuples should be folded too, but their length should not
# exceed the `STACK_USE_GUIDELINE`
Copy link
Copy Markdown
Member Author

@tomasr8 tomasr8 Feb 22, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Should we perhaps add a test that tuples longer than STACK_USE_GUIDELINE are in fact not folded?

Copy link
Copy Markdown
Member

@Eclips4 Eclips4 Feb 23, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Not sure about it. At the moment, for constant tuples which are longer than STACK_USE_GUIDELINE will be generated following bytecode:

BUILD_LIST 0
Pairs of LOAD_CONST + LIST_APPEND
CALL_INTRINSIC_1 (INTRINSIC_LIST_TO_TUPLE)

Shall we assert that this intrinsic is presented in bytecode?

code = compile(repr(tuple(range(30))),'','single')
Comment on lines +181 to +183
Copy link
Copy Markdown
Contributor

@WolframAlph WolframAlph Feb 22, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

How much of a concern is that we can no longer create constant tuples beyond length of STACK_USE_GUIDELINE? @iritkatriel

Copy link
Copy Markdown
Member Author

@tomasr8 tomasr8 Feb 24, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It's probably not ideal in case you have some kind of large constant lookup table for instance. As Kirill pointed out, this would get compiled to a bunch of LOAD_CONST + LIST_APPEND which is probably much slower

Copy link
Copy Markdown
Contributor

@WolframAlph WolframAlph Feb 24, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It is not a hard pattern to detect, right? Maybe we could fold it anyway? @Eclips4

Copy link
Copy Markdown
Member Author

@tomasr8 tomasr8 Feb 24, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It seems quite predictable:

>>> def foo():                                                                                                                                                                                                                                                
...     return (1,2,3, ... ,31)                                                                                                                                                          
...  
>>> dis.dis(foo)                                                                                                                                                                                                                                              
  1           RESUME                   0                                                                                                                                                                                                                      
                                                                                                                                                                                                                                                              
  2           BUILD_LIST               0                                                                                                                                                                                                                      
              LOAD_SMALL_INT           1                                                                                                                                                                                                                      
              LIST_APPEND              1                                                                                                                                                                                                                      
              LOAD_SMALL_INT           2                                                                                                                                                                                                                      
              LIST_APPEND              1                                                                                                                                                                                                                      
              ...
              LOAD_SMALL_INT          31
              LIST_APPEND              1
              CALL_INTRINSIC_1         6 (INTRINSIC_LIST_TO_TUPLE)

(Could also be LOAD_CONST instead of LOAD_SMALL_INT here I suppose)

Copy link
Copy Markdown
Contributor

@WolframAlph WolframAlph Feb 24, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Exactly. I think we can easily fold it.

Copy link
Copy Markdown
Member Author

@tomasr8 tomasr8 Feb 24, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Maybe we could check with is_const_tuple if the tuple is constant and if it is, ignore STACK_USE_GUIDELINE because we know it'll be folded by flowgraph anyway.

Copy link
Copy Markdown
Contributor

@WolframAlph WolframAlph Feb 24, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I don't think it's a good idea. We would be creating dependency between both.

Copy link
Copy Markdown
Contributor

@WolframAlph WolframAlph Feb 24, 2025 •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

So if we are going to fold constant tuple beyond STACK_USE_GUIDELINE, maybe we could also add this optimization to literal lists & sets? It would be consistent with previous Python version as we are not folding these cases anymore after we migrated them to CFG.

Expand Down Expand Up @@ -346,28 +360,6 @@ def negzero():
self.assertInBytecode(code, opname)
self.check_lnotab(code)

def test_folding_of_tuples_on_constants(self):
tests =[
('()', True, 0),
('(1, 2, 3)', True, 3),
('("a", "b", "c")', True, 3),
('(1, a)', False, 2),
('(a, b, c)', False, 3),
('(1, (2, 3))', True, 2),
('(a, (b, c))', False, 2),
('(1, [], {})', False, 3),
(repr(tuple(range(30))), True, 30),
('(1, (2, (3, (4, (5)))))', True, 2)
]
for expr, is_const, length in tests:
with self.subTest(expr=expr, is_const=is_const, length=length):
code = compile(expr, '', 'eval')
if is_const:
self.assertNotInBytecode(code, 'BUILD_TUPLE', length)
self.assertInBytecode(code, 'LOAD_CONST', eval(expr))
else:
self.assertInBytecode(code, 'BUILD_TUPLE', length)

def test_elim_extra_return(self):
# RETURN LOAD_CONST None RETURN --> RETURN
def f(x):
Expand Down
Loading