Description
I'm splitting this topic off gh-106529, notably see this comment: #106529 (comment).
The design we've arrived at adds a "counter" to all branch (== conditional jump) instructions in Tier 1, i.e., to POP_JUMP_IF_{TRUE,FALSE,NONE,NOT_NONE}. This counter is managed differently than most other counter cache entries. It should be initialized to a pattern of alternating ones and zeros. Whenever we execute a branch instruction, we shift the counter left by one position (losing the leftmost bit), and set the bottom bit to one if we jump, or zero if we don't.
When we get to the point where we're constructing a superblock, we look at the cache entry, and decide which is the more likely branch based on the number of bits in the counter (_Py_popcount32()). We then continue projecting along the more likely branch.
We can even get fancy and predict a percentage of correct predictions, and multiply the percentages together as we project through branches, and stop projecting altogether if the probability gets too low. E.g. after two branches with 50%, the probability would be 25%, which is probably too low to bother, so we stop. OTOH after one branch with 80% and one with 25%, we multiply together 0.8 and 0.75 (!), giving 0.6, which is still likely enough to keep going.