Skip to content

n_popped, n_pushed is the wrong abstraction for stack effect #105034

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.

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
gvanrossum opened this issue May 28, 2023 · 6 comments
Closed

n_popped, n_pushed is the wrong abstraction for stack effect #105034

gvanrossum opened this issue May 28, 2023 · 6 comments
Assignees
Labels
type-bug An unexpected behavior, bug, or error

Comments

@gvanrossum
Copy link
Member

gvanrossum commented May 28, 2023

The code generator produces metadata for use by the compiler that tells it how many stack entries were pushed and popped by an opcode. These two quantities are subtracted to compute the net stack effect. (The metadata is in the form of functions _PyOpcode_num_popped and _PyOpcode_num_pushed in opcode_metadata.h.)

But what we really need to know, if we want accurate information about what an opcode (or micro-op) does to the stack, is three numbers: how low it goes, how high it goes, and where it ends. For example, if we have a micro-op that pops two entries and then pushes one, and another that pushes two and then pops one, and we combine them into a macro, the macro's net effect is zero, but the lowest point is two below the initial stack level, and the highest point is one above it.

There are various ways to express this, but there is no way to express all this information with just two numbers.

Note that the relevant calculation is already present in the generator, as part of analyze_macro().

@gvanrossum gvanrossum added the type-bug An unexpected behavior, bug, or error label May 28, 2023
@gvanrossum gvanrossum self-assigned this May 28, 2023
@gvanrossum
Copy link
Member Author

There are various ways to express this, but there is no way to express all this information with just two numbers.

I might be wrong here. I'm ending up doing the equivalent of

low = -popped
net = pushed - popped
high = max(0, net)

So two numbers (low an net) would seem to be enough...

@markshannon
Copy link
Member

Abstractly, each instruction, or op, pops some number of values, then either fails or pushes some other number of values.
Two numbers are sufficient.

For example, instruction I is composed of op A and op B. Op A pops 2 values, and pushes 1. Op B pops 2 values and pushes 2, the net effect is that I pops 3 values and pushes 2.

You need to model the stack, rather than just adding up values.

Operation Stack depth
Start 0
A pops -2
A pushes -1
B pops -3
B pushes -1

@gvanrossum
Copy link
Member Author

The tricky bits happen when the stack effect depends on oparg (e.g. BUILD_SET). The stack effect must then be represented symbolically. I don't know if there are any of those that need to be split up though -- will do an audit later.

@gvanrossum
Copy link
Member Author

Fortunately there are (as yet) no ops with variable-size stack effects. So in #104909 we can use Mark's algorithm.

There is a hypothetical case where the tuple (popped, pushed) isn't enough for the computation of maximum stack level needed: consider I composed of A+B+C, where A pushes 1, B pops 2, and C pushes 1. The net effect is 0, but we need to know that this requires at least one item on the stack at the beginning, and we also need to know that it requires room for an extra item. However, this case doesn't occur in practice.

@carljm
Copy link
Member

carljm commented May 30, 2023

we also need to know that it requires room for an extra item

Does it? Doesn't the cases generator convert temporaries pushed to the stack by one op and popped by the next into temporary variables, meaning the A+B+C example would not actually use any additional stack (though it would temporarily consume one item from the stack.)

@gvanrossum
Copy link
Member Author

Let's close this since we don't need it.

@gvanrossum gvanrossum closed this as not planned Won't fix, can't repro, duplicate, stale Jun 13, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
type-bug An unexpected behavior, bug, or error
Projects
None yet
Development

No branches or pull requests

3 participants