What kind of instructions does the branch predictor speculatively execute?

Question

I was reading about branch prediction, and I'm wondering if the branch predictor will execute any kind of instruction "speculatively". In particular, I'm wondering if it will, for example, communicate with hardware.

Let's suppose you have something like this:

while (true) {
   if (condition)
      SendPacketOverNetwork()
   DoSomethingElse()
}

(and at the assembly level, the first instruction after the if raises an interrupt, or communicates with hardware). What would happen in this case if the branch predictor happens to "guess wrong"? If this can't happen, why? What kind of instructions will the branch predictor execute? Am I misunderstanding what the branch predictor does?

Leeor Leeor · Accepted Answer · 2014-05-15T14:21:31

First of all - the branch predictor doesn't execute anything, it just tells the CPU what is the next instruction to fetch and perform. The CPU will then fetch and insert the next set of instructions into its pipelines, and start performing them.

All operations that carry any impact on the external world (i.e. are observable outside the core), are performed only after the respective instruction is retired and committed. Some minor exceptions may exist in cases where the CPU has some dedicated buffering outside of the core to protect against speculative state leaking out, but the effect is the same - even if the operation is performed internally, it can't be observed until the point where it's committed. Stores to memory, portouts, breakpoints, or any other observable action are all included.

Upon branch misprediction, the speculative state is flushed and any bogus result in the machine, including all operations younger than the mispredicted branch are rolled back (on out-of-order CPUs that is usually managed through ordering buffers). The exact details depend of course on the actual micro-architecture. Since the commits are performed in-order (even when execution is done out-of-order), they function as a point of convergence - the execution of the mispredicted branch will be necessarily done prior to that point in the pipeline, and therefore prior to the retirement and commit of any younger instruction (they're often considered to be "in the shadow" of that branch). As a result, any operation that is externally observable could not have been performed yet, unless it's older than the mispredicted branch.

Example (on an out of order machine, since that's the more interesting case):

op1   |         exec          retire     
op2   |    exec                 retire    
branch|            exec           retire   
op3   |   exec                      retire 
op4   |          exec                 retire
store |                                 retire    dispatch
        ---------------------------> Time

If the branch discovered at execution that its prediction was wrong, the next instructions are guaranteed to be flushed prior to their retirement/commit or anything later along the pipe (including performing any younger store). In an in-order machine that's much simpler, the execution itself is ordered, so the branch will be performed (and the branch resolution will be known) ahead of any younger instruction execution.

What kind of instructions does the branch predictor speculatively execute?

1 Answers