JIT: Introducing a fitness/exit quality control mechanism for the trace frontend

[cocolato]

Feature or enhancement

Background

See: #146073

Proposal

Fitness

Decreases monotonically from an initial value, with additional consumption in specific scenarios:

• Each bytecode instruction: Minor deduction (e.g., 2)
• Conditional branches: The amount deducted is determined by the bias of RECORD_BRANCH_TAKEN—branches that are fully predictable incur almost no deduction, while 50%/50% branches incur a significant deduction
• Backward jumps (JUMP_BACKWARD series): Significant deduction, as a backward jump means the trace enters the second iteration of a loop, and the benefits diminish as it continues
• Function Call Inlining: Should be depth-dependent; deeper nesting incurs heavier penalties

Root traces and side traces should have different initial values—since side traces are derived from exits, they should be allocated fewer “stamina” points.

Exit Quality

Evaluates how good this location would be as an exit point if the tracer were to stop here:

• ENTER_EXECUTOR position (Best): A compiled executor is already available; stopping here allows for direct execution.
• Ordinary bytecode location (Normal): Neither particularly good nor particularly bad
• Specializable instruction (Poor): Stopping here means the tracer must re-specialize the instruction the next time it reaches this point

Decision Rule

fitness < exit_quality

Last Known Good Exit

The tracer should continuously record the best exit encountered during tracing. When it needs to stop, it should prioritize reverting to that position rather than stopping at the current location, which might be suboptimal.

This mechanism can also improve existing unsupported and trace_too_long paths—when these situations occur, the tracer can revert to a previously encountered good position.

Implementation

Phase 1: Core Mechanism

Minimum viable version, enabling the tracer to “actively stop at good positions”:

• Implement structures for fitness, best exit, frame depth, etc.
• Implement update_trace_fitness() — decrement per frame + branch bias penalty + back-edge penalty
• Termination check: fitness < exit_quality
• Record best exit + fallback via try_best_exit_fallback()
• Implement frame depth tracking (detect frame changes to increment/decrement)

Phase 2: Tuning and Enhancement

Further optimization based on real-world data from Phase 1:

• Parameter tuning: Adjust fitness constants based on results from pyperformance and custom benchmarks

Phase 3: Long-Term Evolution

• Merge point: Once the bytecode compiler supports it, assign a higher exit quality at CFG merge points
• Per-executor adaptive parameters: Dynamically adjust fitness parameters based on runtime feedback

Has this already been discussed elsewhere?

No response given

Links to previous discussion of this feature:

No response