Compiler hangs during jump elimination

[brandtbucher]

BPO	45773
Nosy	@markshannon, @pablogsal, @miss-islington, @brandtbucher
PRs	bpo-45773: Stop "optimizing" certain jump patterns #29505 [3.10] bpo-45773: Stop "optimizing" certain jump patterns (GH-29505) #29526 bpo-45773: Remove invalid peephole optimizations #31066 [3.10] bpo-45773: Remove invalid peephole optimizations (GH-31066) #31101

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/brandtbucher'
closed_at = <Date 2022-02-03.16:04:53.162>
created_at = <Date 2021-11-09.19:56:22.487>
labels = ['interpreter-core', 'type-bug', '3.11']
title = 'Compiler hangs during jump elimination'
updated_at = <Date 2022-02-03.16:04:53.162>
user = 'https://github.com/brandtbucher'

bugs.python.org fields:

activity = <Date 2022-02-03.16:04:53.162>
actor = 'brandtbucher'
assignee = 'brandtbucher'
closed = True
closed_date = <Date 2022-02-03.16:04:53.162>
closer = 'brandtbucher'
components = ['Interpreter Core']
creation = <Date 2021-11-09.19:56:22.487>
creator = 'brandtbucher'
dependencies = []
files = []
hgrepos = []
issue_num = 45773
keywords = ['patch']
message_count = 6.0
messages = ['406046', '406174', '406179', '412318', '412433', '412447']
nosy_count = 4.0
nosy_names = ['Mark.Shannon', 'pablogsal', 'miss-islington', 'brandtbucher']
pr_nums = ['29505', '29526', '31066', '31101']
priority = None
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue45773'
versions = ['Python 3.11']

[brandtbucher]

The following code hangs during compilation on 3.11 and 3.10:

>> while True or spam: pass

Our peepholer gets stuck in a loop, repeatedly "optimizing" instruction 4 (POP_JUMP_IF_TRUE -> JUMP_ABSOLUTE):

1 0 JUMP_ABSOLUTE 0 (to 0)
2 LOAD_NAME 0 (spam)
4 POP_JUMP_IF_TRUE 0 (to 0)

After optimizing jumps to jumps like these, we always back up and attempt to optimize the same instruction again (which makes it possible to optimize three or more chained jumps on the same line). The issue is that this particular optimization doesn't actually change the instruction, since both jumps target the same exact block. Since nothing changes, we loop forever.

The fix is really simple: just skip the optimization if instr->i_target == target->i_target. We already do this for several other types of jumps; it just looks like POP_JUMP_IF_TRUE and POP_JUMP_IF_FALSE might have been missed.

I'll have a PR up soon.

[brandtbucher]

New changeset 27b69e6 by Brandt Bucher in branch 'main':
bpo-45773: Stop "optimizing" certain jump patterns (GH-29505)
27b69e6

[brandtbucher]

New changeset a89bbde by Brandt Bucher in branch '3.10':
[3.10] bpo-45773: Stop "optimizing" certain jump patterns (GH-29526)
a89bbde

[brandtbucher]

My fix for this seems to have erroneously added two invalid new jump threads:

POP_JUMP_IF_FALSE(a) to JUMP_IF_FALSE_OR_POP(b) is folded into POP_JUMP_IF_FALSE(b)
POP_JUMP_IF_TRUE(a) to JUMP_IF_TRUE_OR_POP(b) is folded into POP_JUMP_IF_TRUE(b)

The good news is that I can't get the compiler to actually emit these particular jump sequences. It still needs to be fixed ASAP, though.

[markshannon]

New changeset e0433c1 by Brandt Bucher in branch 'main':
bpo-45773: Remove invalid peephole optimizations (GH-31066)
e0433c1

[miss-islington]

New changeset ff6948b by Miss Islington (bot) in branch '3.10':
bpo-45773: Remove invalid peephole optimizations (GH-31066)
ff6948b