8000 bpo-46528: Attempt SWAPs at compile-time (GH-30970) · python/cpython@78ae4cc · GitHub
[go: up one dir, main page]
Skip to content

Commit 78ae4cc

Browse files
brandtbucherbrandtbucher
authored
bpo-46528: Attempt SWAPs at compile-time (GH-30970)
1 parent 5a3f972 commit 78ae4cc

File tree

3 files changed

+136
-0
lines changed

3 files changed

+136
-0
lines changed

‎Lib/test/test_peepholer.py

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,25 @@
11
import dis
22
from itertools import combinations, product
3+
import textwrap
34
import unittest
45

56
from test.support.bytecode_helper import BytecodeTestCase
67

78

9+
def compile_pattern_with_fast_locals(pattern):
10+
source = textwrap.dedent(
11+
f"""
12+
def f(x):
13+
match x:
14+
case {pattern}:
15+
pass
16+
"""
17+
)
18+
namespace = {}
19+
exec(source, namespace)
20+
return namespace["f"].__code__
21+
22+
823
def count_instr_recursively(f, opname):
924
count = 0
1025
for instr in dis.get_instructions(f):
@@ -580,6 +595,58 @@ def test_format_errors(self):
580595
'not all arguments converted during string formatting'):
581596
eval("'%s, %s' % (x, *y)", {'x': 1, 'y': [2, 3]})
582597

598+
def test_static_swaps_unpack_two(self):
599+
def f(a, b):
600+
a, b = a, b
601+
b, a = a, b
602+
self.assertNotInBytecode(f, "SWAP")
603+
604+
def test_static_swaps_unpack_three(self):
605+
def f(a, b, c):
606+
a, b, c = a, b, c
607+
a, c, b = a, b, c
608+
b, a, c = a, b, c
609+
b, c, a = a, b, c
610+
c, a, b = a, b, c
611+
c, b, a = a, b, c
612+
self.assertNotInBytecode(f, "SWAP")
613+
614+
def test_static_swaps_match_mapping(self):
615+
for a, b, c in product("_a", "_b", "_c"):
616+
pattern = f"{{'a': {a}, 'b': {b}, 'c': {c}}}"
617+
with self.subTest(pattern):
618+
code = compile_pattern_with_fast_locals(pattern)
619+
self.assertNotInBytecode(code, "SWAP")
620+
621+
def test_static_swaps_match_class(self):
622+
forms = [
623+
"C({}, {}, {})",
624+
"C({}, {}, c={})",
625+
"C({}, b={}, c={})",
626+
"C(a={}, b={}, c={})"
627+
]
628+
for a, b, c in product("_a", "_b", "_c"):
629+
for form in forms:
630+
pattern = form.format(a, b, c)
631+
with self.subTest(pattern):
632+
code = compile_pattern_with_fast_locals(pattern)
633+
self.assertNotInBytecode(code, "SWAP")
634+
635+
def test_static_swaps_match_sequence(self):
636+
swaps = {"*_, b, c", "a, *_, c", "a, b, *_"}
637+
forms = ["{}, {}, {}", "{}, {}, *{}", "{}, *{}, {}", "*{}, {}, {}"]
638+
for a, b, c in product("_a", "_b", "_c"):
639+
for form in forms:
640+
pattern = form.format(a, b, c)
641+
with self.subTest(pattern):
642+
code = compile_pattern_with_fast_locals(pattern)
643+
if pattern in swaps:
644+
# If this fails... great! Remove this pattern from swaps
645+
# to prevent regressing on any improvement:
646+
self.assertInBytecode(code, "SWAP")
647+
else:
648+
self.assertNotInBytecode(code, "SWAP")
649+
583650

584651
class TestBuglets(unittest.TestCase):
585652

‎Misc/NEWS.d/next/Core and Builtins/2022-01-27-14-20-18.bpo-45828.kzk4fl.rst

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,2 @@
1+
The bytecode compiler now attempts to apply runtime stack manipulations at
2+
compile-time (whenever it is feasible to do so).

‎Python/compile.c

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8472,6 +8472,72 @@ swaptimize(basicblock *block, int *ix)
84728472
return 0;
84738473
}
84748474

8475+
// This list is pretty small, since it's only okay to reorder opcodes that:
8476+
// - can't affect control flow (like jumping or raising exceptions)
8477+
// - can't invoke arbitrary code (besides finalizers)
8478+
// - only touch the TOS (and pop it when finished)
8479+
#define SWAPPABLE(opcode) \
8480+
((opcode) == STORE_FAST || (opcode) == POP_TOP)
8481+
8482+
static int
8483+
next_swappable_instruction(basicblock *block, int i, int lineno)
8484+
{
8485+
while (++i < block->b_iused) {
8486+
struct instr *instruction = &block->b_instr[i];
8487+
if (0 <= lineno && instruction->i_lineno != lineno) {
8488+
// Optimizing across this instruction could cause user-visible
8489+
// changes in the names bound between line tracing events!
8490+
return -1;
8491+
}
8492+
if (instruction->i_opcode == NOP) {
8493+
continue;
8494+
}
8495+
if (SWAPPABLE(instruction->i_opcode)) {
8496+
return i;
8497+
}
8498+
return -1;
8499+
}
8500+
return -1;
8501+
}
8502+
8503+
// Attempt to apply SWAPs statically by swapping *instructions* rather than
8504+
// stack items. For example, we can replace SWAP(2), POP_TOP, STORE_FAST(42)
8505+
// with the more efficient NOP, STORE_FAST(42), POP_TOP.
8506+
static void
8507+
apply_static_swaps(basicblock *block, int i)
8508+
{
8509+
// SWAPs are to our left, and potential swaperands are to our right:
8510+
for (; 0 <= i; i--) {
8511+
assert(i < block->b_iused);
8512+
struct instr *swap = &block->b_instr[i];
8513+
if (swap->i_opcode != SWAP) {
8514+
if (swap->i_opcode == NOP || SWAPPABLE(swap->i_opcode)) {
8515+
// Nope, but we know how to handle these. Keep looking:
8516+
continue;
8517+
}
8518+
// We can't reason about what this instruction does. Bail:
8519+
return;
8520+
}
8521+
int j = next_swappable_instruction(block, i, -1);
8522+
if (j < 0) {
8523+
return;
8524+
}
8525+
int k = j;
8526+
int lineno = block->b_instr[j].i_lineno;
8527+
for (int count = swap->i_oparg - 1; 0 < count; count--) {
8528+
k = next_swappable_instruction(block, k, lineno);
8529+
if (k < 0) {
8530+
return;
8531+
}
8532+
}
8533+
// Success!
8534+
swap->i_opcode = NOP;
8535+
struct instr temp = block->b_instr[j];
8536+
block->b_instr[j] = block->b_instr[k];
8537+
block->b_instr[k] = temp;
8538+
}
8539+
}
8540+
84758541
// Attempt to eliminate jumps to jumps by updating inst to jump to
84768542
// target->i_target using the provided opcode. Return whether or not the
84778543
// optimization was successful.
@@ -8714,6 +8780,7 @@ optimize_basic_block(struct compiler *c, basicblock *bb, PyObject *consts)
87148780
if (swaptimize(bb, &i)) {
87158781
goto error;
87168782
}
8783+
apply_static_swaps(bb, i);
87178784
break;
87188785
case KW_NAMES:
87198786
break;

0 commit comments

Comments
 (0)
0