Skip to content

bpo-46528: Simplify the VM's stack manipulations #30902

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

Merged
brandtbucher merged 10 commits into from
Jan 26, 2022
Merged

bpo-46528: Simplify the VM's stack manipulations #30902

Changes from 1 commit
Commits
Show all changes
10 commits
Select commit Hold shift + click to select a range
eb5ec74
Replace ROT*/DUP* with SWAP/COPY
brandtbucher Jan 25, 2022
415c9b2
Catch up with main
brandtbucher Jan 25, 2022
96f0ce5
Implement a "swaptimizer"
brandtbucher Jan 25, 2022
1ab5f21
Simplify things further
brandtbucher Jan 26, 2022
d85d65b
blurb add
brandtbucher Jan 26, 2022
1f67c08
Fix typo
brandtbucher Jan 26, 2022
c4ef99f
Clean up wording
brandtbucher Jan 26, 2022
6274309
Remove VLA usage
brandtbucher Jan 26, 2022
aa51caa
Apply feedback from code review
brandtbucher Jan 26, 2022
1537cda
Naming is hard
brandtbucher Jan 26, 2022
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
Next Next commit
Apply feedback from code review
  • Loading branch information
@brandtbucher
brandtbucher committed Jan 26, 2022
commit aa51caadf5d964c930d50bcde53aa1ae88e8a47a
34 changes: 21 additions & 13 deletions Python/compile.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -6243,7 +6243,7 @@ compiler_error_duplicate_store(struct compiler *c, identifier n)

// Duplicate the effect of 3.10's ROT_* instructions using SWAPs.
static int
pattern_helper_rotate(struct compiler *c, int count)
pattern_helper_rotate(struct compiler *c, Py_ssize_t count)
{
while (1 < count) {
ADDOP_I(c, SWAP, count--);
Expand Down Expand Up @@ -8456,17 +8456,19 @@ swaptimize(basicblock *block, int ix)
assert(instructions[0].i_opcode == SWAP);
int depth = instructions[0].i_oparg;
int len = 0;
int more = false;
while (++len < block->b_iused - ix) {
int opcode = instructions[len].i_opcode;
if (opcode == SWAP) {
depth = Py_MAX(depth, instructions[len].i_oparg);
more = true;
}
else if (opcode != NOP) {
break;
}
}
// It's already optimal if there's only one instruction:
if (len == 1) {
// It's already optimal if there's only one SWAP:
if (!more) {
return 0;
Comment thread
brandtbucher marked this conversation as resolved.
}
// Create an array with elements {0, 1, 2, ..., depth - 1}:
Expand All @@ -8492,28 +8494,30 @@ swaptimize(basicblock *block, int ix)
// though, we can efficiently *shuffle* it! For this reason, we will be
// replacing instructions starting from the *end* of the run. Since the
// solution is optimal, we don't need to worry about running out of space:
int i = len - 1;
for (int item = 0; item < depth; item++) {
int j = len - 1;
for (int i = 0; i < depth; i++) {
// Skip items that have already been visited, or just happen to be in
// the correct location:
if (stack[item] == VISITED || stack[item] == item) {
if (stack[i] == VISITED || stack[i] == i) {
continue;
}
// Okay, we've found an item that hasn't been visited. It forms a cycle
// with other items; traversing the cycle and swapping each item with
// the next will put them all in the correct place. The weird
// loop-and-a-half is necessary to insert 0 into every cycle, since
// we can only swap from that position.
// loop-and-a-half is necessary to insert 0 into every cycle, since we
// can only swap from that position.
int item = i;
while (true) {
// Skip the actual swap if our item is zero, since swapping the top
// item with itself is pointless.
if (item) {
assert(0 <= i);
assert(0 <= j);
// SWAPs are 1-indexed:
instructions[i].i_opcode = SWAP;
instructions[i--].i_oparg = item + 1;
instructions[j].i_opcode = SWAP;
instructions[j--].i_oparg = item + 1;
}
if (stack[item] == VISITED) {
assert(item == i);
break;
}
int next_item = stack[item];
Expand All @@ -8522,8 +8526,8 @@ swaptimize(basicblock *block, int ix)
}
}
// NOP out any unused instructions:
while (0 <= i) {
instructions[i--].i_opcode = NOP;
while (0 <= j) {
instructions[j--].i_opcode = NOP;
}
// Done! Return the number of optimized instructions:
PyMem_Free(stack);
Expand Down Expand Up @@ -8774,6 +8778,10 @@ optimize_basic_block(struct compiler *c, basicblock *bb, PyObject *consts)
}
break;
case SWAP:
if (oparg == 1) {
inst->i_opcode = NOP;
break;
}
i += swaptimize(bb, i);
break;
default:
Expand Down