Branch Prediction and Division By Zero

Question

I was writing code that looked like the following...

if(denominator == 0){     return false; } int result = value / denominator; 

... when I thought about branching behavior in the CPU.

https://stackoverflow.com/a/11227902/620863 This answer says that the CPU will try to correctly guess which way a branch will go, and head down that branch only to stop if it discovers it guessed the branch incorrectly.

But if the CPU predicts the branch above incorrectly, it would divide by zero in the following instructions. This doesn't happen though, and I was wondering why? Does the CPU actually execute a division by zero and wait to see if the branch is correct before doing anything, or can it tell that it shouldn't continue in these situations? What's going on?

Answer 1

The CPU is free to do whatever it wants, when speculatively executing a branch based on a prediction. But it needs to do so in a way that's transparent to the user. So it may stage a "division by zero" fault, but this should be invisible if the branch prediction turns out wrong. By the same logic, it may stage writes to memory, but it may not actually commit them.

As a CPU designer, I wouldn't bother predicting past such a fault. That's probably not worth it. The fault probably means a bad prediction, and that will resolve itself soon enough.

This freedom is a good thing. Consider a simple std::accumulate loop. The branch predictor will correctly predict a lot of jumps (for (auto current = begin, current != end; ++current) which usually jumps back to the begin of loop), and there are a lot of memory reads which may potentially fault (sum += *current). But a CPU that would refuse to read a memory value until the previous branch has been resolved would be a lot slower. And yet a mispredicted jump at the end of the loop might very well cause a harmless memory fault, as the predicted branch tries to read past the buffer. This needs to be resolved without a visible fault.

Answer 2

Not exactly. The system is not allowed to execute the instructions in the wrong branch even if it does a bad guess, or more exactly if it does it must not be visible. The basic is :

• there is a test somewhere in the machine code.
• the processor loads it pipeline with instructions on one of the possible paths and possibly executes them internally - according to MSalters, some processor could even execute both paths (*)
• if it made a good guess, fine, the following instruction have been preloaded in processor cache or already executed, and all goes as fast as possible
• if it made a wrong guess, it just have to clean everything and restart on the correct branch.

For the analogy with the referenced post, the train has to stop immediately at the junction if the switch was not in correct position, it cannot go to next station on the wrong path, or if it cannot stop before that, no passengers shall be allowed to go in or out of the train

(*) Itanium processors would be able to process many paths in parallel. Intel's logic was that they can build wide processors (which do a lot in parallel) but they were struggling with the effective instruction rate. By speculatively executing both branches, they used a lot of hardware (I think they could do it several levels deep, running 2^N branches) but it did help the apparent single core speed as it in effect always predicted the correct branch in one HW unit - Credits should go to MSalters for that precision