Are correct branch predictions free?

Question

Let's say you make some code that has an if statement and condition in that if statement always ends up being true for the entire run of your program, but that it can't be known at compile time that the condition is always true (maybe its specified on the command line)

In this case, you'd expect the cpu to be able to predict this and always choose the right path to take.

Does this mean that with branch prediction that the code is as fast as if there isn't an if statement there at all?

Or, are there real costs still?

I can imagine some costs that probably don't go away...

• The first call, where it might get wrong, or however long it takes for the branch predictor to always get it right.
• Maybe if the program is large, the knowledge of the branch gets lost as the instruction cache gets cleared?
• Maybe the fact that you have conditional code (and maybe an else) means that the instruction cache can't hold as much, so slows down your program in general
• I'm betting the verification that it took the right path can't be free, and that it eats up some amount of resources

Are those true? Are there any others?

Answer 1

You will have to execute the branch (after resolving all dependencies first), which would take execution resources (ports, queue entries, etc), although any alternative approach (such as conditional moves) would also require an equivalent effort at least. Even predictors must eventually check that they're right.

In addition, most out-of-order CPUs also employ dedicated queues to track branches, see for example the branch order buffer in Haswell - http://www.realworldtech.com/haswell-cpu/3/ . This could fill up and become a limitation if you have too many branches. Some micro-architectures may also impose other restrictions on the bandwidth of updating the branch predictor, ultimately limiting the rate at which you can process these braches (either by blocking execution or commit).

Regarding the code cacheability - yes, naturally you'd have some code for both paths, but again - if the branch has some functional purpose in the program, you can't really help but having this code. The branch may change the way the code is organized (depending on compiler optimizations), but that seems like a secondary effect. If the entire if condition is redundant, then the same applies for any code bloating you may have in your code.

Answer 2

Well, let me give the typical engineering answer; It depends.

Different processors do branch prediction differently. There are many many methods for doing branch prediction. Some of them will get every branch in your scenario correct, and some of them won't.

I don't know the details of any specific branch prediction implementation other than one I wrote at University for a computer architecture, but I know that branch prediction is not a standardized module. As long as it runs the code, you can implement as good or as bad of a branch predictor as you want.

Some methods will take up resources, some will not. Always selecting true is a branch predictor, bear in mind, it just isn't a very good one.

Branch predictors are one fascinating part of many in a processor, I encourage you to keep learning more, and try designing your own simple processor!

Answer 3

Some architectures can make correctly predicted branches more or less free. It's called branch folding. Basically what happens is that when the branch predictor in the front end sees a branch that it's encountered before and whose target is known, instead of sending the branch down the pipeline, it can send the instruction at the branch target instead. The front-end still has to see the branch, but the back-end never does, so if the back-end is even slightly behind, the bubbles balance out, and it's as if the branch never existed.

That isn't the whole story, though. A branch is likely as not to be mispredicted the first few times, and if it's a conditional branch, somehow the condition still has to be resolved.