Branch Predicting

Question

Possible Duplicate:
Is it possible to tell the branch predictor how likely it is to follow the branch?

So, if branch predicting plays such a great role ("Branch predictors play a critical role in achieving high effective performance in many modern pipelined microprocessor architectures such as x86." ^wiki), it makes sense that there must be a way to optimize and help it, right?

I'll ask my question in a straightforward manner:
Can you tell the branch predictor what route you're most likely to take?

I'll offer an example:

My program checks every time it loads if this is the first time the user runs it. Most likely the branch that should be cached is the one that's labeled "it's not the first time".

In this example it's not a big deal, and maybe the algorithms can figure out what route to take, but in complicated applications with lots of branches, I'm not so sure the algorithms would score 10 out of 10.

Can we optimize this somehow? maybe mark a branch for caching?
By the way I'm asking for educational purposes, and maybe one day for time-critical programs.

According to that question, though, there is a branch hint instruction, but it's a NOP on post-Netburst architectures. — Colin Valliant, Dec 23 '12 at 18:42
C and assembly both get turned into machine instructions eventually. — Carl Norum, Dec 23 '12 at 18:59
@CarlNorum Yes with compilation. I don't know how to compile the code there by myself. — MasterMastic, Dec 23 '12 at 19:07

score 2 · Accepted Answer · answered Dec 23 '12 at 18:47

It's for C. I'm asking for ASM

Which means that you'll have to implement the semantics of __builtin_expect yourself. It isn't difficult, just awkward. If the branch predictor doesn't have history for the branch then it will assume that the branch is taken when the branch is backwards and not taken when it is forward.

So you may have to restructure your code, using the opposite condition in the branch instruction and move code to accommodate that. An unconditional forward jump with a conditional backward branch is common, the way a C compiler implements a for() loop for example.

score 2 · Answer 2 · answered Dec 23 '12 at 19:44

"In the event that a branch hint is necessary, the following instruction prefixes can be added before a branch instruction to change the way the static predictor behaves: 0x3E – statically predict a branch as taken 0x2E – statically predict a branch as not taken"

http://software.intel.com/en-us/articles/branch-and-loop-reorganization-to-prevent-mispredicts

score 1 · Answer 3 · answered Dec 23 '12 at 18:46

The simplest heuristic is to use the branch instruction which matches the most common path. If, for example, you are coding a loop it is usually best to have the branch instruction follow the looping path rather than the exit condition. The goal is to use the branch instruction which evaluates to true most frequently.

If you choose exactly the wrong instruction, let's say you code a loop that almost always exits immediately, the processor may cache that the sense of this branch is backwards and adjust it's prediction. This is only likely to happen for heavily used code though.

score 1 · Answer 4 · answered Dec 23 '12 at 19:11

Some important assembly branch prediction optimization, Source: wiki

There is a one-cycle stall in instruction fetch when a branch is predicted taken. It is therefore referable to structure code so that the most likely code path is the one where the branch is not taken.

Unconditional branches may be mispredicted, and load instructions which follow branches may be decoded and cause cache accesses. Avoid placing load instructions after branches unless you intend the CPU to prefetch the addresses they reference.

Although instructions are decoded in pairs, the branch predictor can only predict one branch target per cycle. If you have a conditional branch which is immediately followed by another branch, and the first branch is likely to be taken, place a no-operation instruction between the branches to prevent decoding and prediction of the second branch. Inserting NOPs is detrimental if the first branch is infrequently taken.

Branch Predicting

4 Answers4