Editing Branch (computer science) (section)

== Improving performance by reducing stalls from branches ==
Several techniques improve speed by reducing stalls from conditional branches.

=== Branch prediction hints ===
Historically, branch prediction took statistics, and used the result to optimize code.  A programmer would compile a test version of a program, and run it with test data.  The test code counted how the branches were actually taken. The statistics from the test code were then used by the compiler to optimize the branches of released code. The optimization would arrange that the fastest branch direction (taken or not) would always be the most frequently taken control flow path. To permit this, CPUs must be designed with (or at least have) predictable branch timing. Some CPUs have instruction sets (such as the [[Power ISA]]) that were designed with "branch hints" so that a compiler can tell a CPU how each branch is to be taken.

The problem with software branch prediction is that it requires a complex software development process.

=== Hardware branch predictors ===
To run any software, hardware [[branch predictor]]s moved the statistics into the electronics. Branch predictors are parts of a processor that guess the outcome of a conditional branch. Then the processor's logic gambles on the guess by beginning to execute the expected instruction flow. An example of a simple hardware branch prediction scheme is to assume that all backward branches (i.e. to a smaller program counter) are taken (because they are part of a loop), and all forward branches (to a larger program counter) are not taken (because they leave a loop). Better branch predictors are developed and validated statistically by running them in simulation on a variety of test programs.  Good predictors usually count the outcomes of previous executions of a branch. Faster, more expensive computers can then run faster by investing in better branch prediction electronics. In a CPU with hardware branch prediction, branch hints let the compiler's presumably superior branch prediction override the hardware's more simplistic branch prediction.

=== Branch-free code ===
Some logic can be written without branches or with fewer branches. It is often possible to use [[bitwise operation]]s, [[conditional move]]s or other [[Predication (computer architecture)|predication]] instead of branches.<ref>{{cite book |first=Donald |last=Knuth |author-link=Donald Knuth |title=[[The Art of Computer Programming]] |volume=4, Pre-fascicle 1A |edition=Revision 6 |year=2008 |pages=48–49}}</ref><ref>{{cite web |title=Avoiding Branches |url=https://www.chessprogramming.org/Avoiding_Branches |website=Chessprogramming wiki}}</ref> In fact, branch-free code is a must for cryptography due to [[timing attack]]s.<ref>{{cite web |title=Constant-Time Crypto |url=https://www.bearssl.org/constanttime.html |website=BearSSL}}</ref>

=== Delay slot ===
{{Main|Delay slot}}

Another technique is a [[Delay slot|branch delay slot]]. In this approach, at least one instruction following a branch is always executed, with some exceptions such like the legacy [[MIPS architecture]] likely/unlikely branch instruction. Therefore, the computer can use this instruction to do useful work whether or not its pipeline stalls. This approach was historically popular in [[RISC]] computers. In a family of compatible CPUs, it complicates multicycle CPUs (with no pipeline), faster CPUs with longer-than-expected pipelines, and superscalar CPUs (which can execute instructions out of order.)