Branch confidence decay in Tier 2 translator

[gvanrossum]

This is a follow-up to gh-109039 (and to a lesser extent gh-111848). (I'm sure I read about it somewhere on https://github.com/faster-cpython/ideas/issues too, but I can't find the relevant issue, so I'll describe the idea from scratch here.)

When we translate a branch instruction (e.g. POP_JUMP_IF_TRUE), Tier 1 has a 16-bit shift register tracking how often we branched in the past 16 times this instruction was reached. During Tier 2 translation, if the bit count indicates that we've taken the branch more often than not, we continue the trace at the branch destination; otherwise, we continue following the branch instruction.

What we should also do in the translator have a variable (for the entire trace) indicating how likely we are still "on trace". This "confidence factor" starts off at 100%. If we translate a branch that is taken X% of the time, for X >= 50%, we should multiply the confidence by X%. If the confidence ends too low (say, below 33%) we should end the trace at this point, generating an _EXIT_TRACE uop.

UPDATE: Ideally we should also adjust the confidence each time we generate a guard. But what factor should we use there? Most guards fail rarely. I propose to punt on this now; later we can add code to adjust the same variable on deoptimization exits.

Linked PRs

• gh-112320: Implement on-trace confidence tracking for branches #112321

[hugovk]

Closing because the PR has been merged. Please re-open if there's more needed here.

[gvanrossum]

Thanks, and sorry. I usually forget to use the "fixes gh-blahblah" magic phrase. :-(