Thread: Why the compiler creates a label and jumps for the code in the "else" block?

I a lot of cases branch prediction is cunning rather than smart.

- It has to be fast - it must give the answer quickly

- It has to be simple as it will need to be implemented in H/W at a high clock rate

- It doesn't have to be perfect, just right most of the time.

One common technique is a 2-bit saturating counter associated with the branch instruction. Each time a branch is taken the counter is incremented (if it isn't already 3) and each time it isn't taken it is decremented (it it isn't already 0). The upper bit of the counter is used as the prediction.

If the upper bit of the counter is '1' (so count 2 or 3) then it predicts that the branch will be taken, if the bit is a '0' it predicts that the branch will not be taken.

This simple implementation works surprisingly good with loops (where the branch taken on the exit condition doesn't upset the prediction for the next time the loop is entered) and pretty good on 'if' branches, when one option is usually taken.

It also makes a simple but good mental model if you want to roughly judge how well branch prediction will work on a given bit of code.

Originally Posted by hamster_nz

I a lot of cases branch prediction is cunning rather than smart.

- It has to be fast - it must give the answer quickly

- It has to be simple as it will need to be implemented in H/W at a high clock rate

- It doesn't have to be perfect, just right most of the time.

One common technique is a 2-bit saturating counter associated with the branch instruction. Each time a branch is taken the counter is incremented (if it isn't already 3) and each time it isn't taken it is decremented (it it isn't already 0). The upper bit of the counter is used as the prediction.

If the upper bit of the counter is '1' (so count 2 or 3) then it predicts that the branch will be taken, if the bit is a '0' it predicts that the branch will not be taken.

This simple implementation works surprisingly good with loops (where the branch taken on the exit condition doesn't upset the prediction for the next time the loop is entered) and pretty good on 'if' branches, when one option is usually taken.

It also makes a simple but good mental model if you want to roughly judge how well branch prediction will work on a given bit of code.

Thanks a lot for the info! It really helps!

hamster_nz, what you described is valid for indirect jumps. For conditional jumps the algorithm is simplier: forward jumps are assumed as NOT taken and backward jumps are assumed as taken.

Originally Posted by flp1969

hamster_nz, what you described is valid for indirect jumps. For conditional jumps the algorithm is simplier: forward jumps are assumed as NOT taken and backward jumps are assumed as taken.

From a recent CPU instruction set spec:

Software should also assume that backwardbranches will be predicted taken and forward branches as not taken, at least the first time they areencountered. Dynamic predictors should quickly learn any predictable branch behavior.

"at least the first time they are encountered" is doing a lot of the heavy lifting there. For anything but a low-end CPU, behind that is a branch predictor.

Originally Posted by hamster_nz

From a recent CPU instruction set spec:

Software should also assume that backwardbranches will be predicted taken and forward branches as not taken, at least the first time they areencountered. Dynamic predictors should quickly learn any predictable branch behavior.

"at least the first time they are encountered" is doing a lot of the heavy lifting there. For anything but a low-end CPU, behind that is a branch predictor.

This is talking about "dynamic predictors", not static ones... Instructions as Jcc use "static" branch preditor algorithms. Only indirect jumps use dynamic...

Originally Posted by flp1969

This is talking about "dynamic predictors", not static ones... Instructions as Jcc use "static" branch preditor algorithms. Only indirect jumps use dynamic...

If that is the case we are talking different CPU architectures. That quote if from the RISC-V conditional branches section (BEQ/BNE and so on).

... and it is all CPU/design implementation dependent, and I was just providing a first approximation that is simple to understand, provides a reasonably accurate insight as how branch prediction could work, and is actually used in some CPU designs.

Intel x86 follows the "backward will be taken, forward will not" heuristic/assumption when it first encounters a conditional branch, but my vague understanding is that if it is mis-predicted it gets put in the Branch Target Buffer to help get it right the next time. I haven't looked into it deeply for a long time but am pretty sure that is the case.