Repository navigation
Add tier 2 partial evaluation pass. #120619
Description
Once an optimization pass is in place, it enables external contributors to make improvements.
It happened with the tier 1 specializer and is happening now with the tier 2 optimizer and JIT.
We should add the partial evaluation pass, so that external contributors can help with that.
The aim of the partial evaluation pass is to do computation, allocation and deallocation during optimization, so it doesn't need to be done at runtime.
We should add this pass, starting with a few very simple optimizations as placeholders for the full pass to be added later.
These optimizations should include:
- Float unboxing
- Temporary tuple elimination
We can start with the very simple optimization : BUILD_TUPLE 2; _RETURN_VALUE; UNPACK 2 -> _RETURN_PAIR before adding more complex optimizations in the future.
Linked PRs
- GH-120619: Clean up
RETURN_VALUEinstruction #120624 - gh-120619: Tier 2 partial evaluation pass foundations #123652
- gh-120619: Optimize through
_Py_FRAME_GENERAL#124518 - gh-120619: Strength reduce function guards, support 2-operand instruction forms #124846
- gh-120619: Tier 2 partial evaluator foundations #124910
- gh-126902: Strength reduce _CHECK_FUNCTION #126856
Activity
GH-120619: Clean up `RETURN_VALUE` instruction (GH-120624)
pythonGH-120619: Clean up `RETURN_VALUE` instruction (pythonGH-120624)
pythonGH-120619: Clean up `RETURN_VALUE` instruction (pythonGH-120624)
Fidget-Spinner commentedon Jul 16, 2024
@markshannon do you mind if I assign myself to this?
pythonGH-120619: Clean up `RETURN_VALUE` instruction (pythonGH-120624)
markshannon commentedon Jul 18, 2024
This is a fairly large feature, so I'd like to do some reasonably detailed design work before we start implementing this.
Fell free to add any thoughts you have about the design here, or in https://github.com/faster-cpython/ideas, but I'd advise against starting coding just yet.
Fidget-Spinner commentedon Sep 1, 2024
I propose this algorithm, starting with the simplest optimization: LOAD_FAST; POP_TOP -> _NOP, or constant propagation.
faster-cpython/ideas#561 (comment)
gh-120619: Optimize through `_Py_FRAME_GENERAL` (GH-124518)
gh-120619: Strength reduce function guards, support 2-operand uop for…
pythongh-120619: Strength reduce function guards, support 2-operand u…
pythongh-120619: Strength reduce function guards, support 2-operand u…
Fidget-Spinner commentedon Feb 14, 2026
Design
Required background knowledge:
Design:
Mark's PhD theses showed that partial evaluation in Python is almost useless without specialization, which provides type information. I thus propose the following design:
a. This is not new art, as PyPy already runs its analysis in lockstep fashion for every instruction.
a. We supply all the type information we already have in the first pass to the second pass. In the literature, this is known as the cardinal product of 2 abstract domains. The abstract domains we are combining are the types lattice and the "shape"/object one). The key benefit is to reduce duplicated code and also increase the power of the second domain. For example, to perform a scalar replacement of tuples, we would need to know anyways that it's a tuple of size n, a type that we already have information about in the types specialization pass.
b. By defining them as two separate domains, we ensure that they remain conceptually separate and clear.
We should discuss the design further and refine it. @reidenong is likely taking the initial implementation up.
Future direction
Currently, we just stick the guards onto the end of the trace during the final phase when the executor prepares for execution.
Unfortunately, if we are to do more complicated optimizations, we will need to reconstruct state before bailing to the interpreter.
Mainly, we need some way to say "this is the state we need to restore at X point of execution upon exiting", and write the instructions to restore that state then.
Instead, the optimizer should be able to know what instructions it needs to emit to restore the state. We can have a "guard arena" that stores each guard fragment, so during uop optimization it should look like this:
After that pass and during the prepare for execution pass, we merge the guard buffer and main trace into one single buffer, and insert the final _EXIT_TRACE and _DEOPT instructions for each guard fragment while doing so.