 | This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Branch" computer science – news ·newspapers ·books ·scholar ·JSTOR(June 2009) (Learn how and when to remove this message) |
| Machine code |
|---|
| General concepts |
| Instructions |
Abranch,jump ortransfer is an instruction in acomputer program that can cause a computer to begin executing a different instruction sequence and thus deviate from its default behavior of executing instructions in order.[a]Branch (orbranching,branched) may also refer to the act of switching execution to a different instruction sequence as a result of executing a branch instruction. Branch instructions are used to implementcontrol flow in program loops and conditionals (i.e., executing a particular sequence of instructions only if certain conditions are satisfied).
A branch instruction can be either anunconditional branch, which always results in branching, or aconditional branch, which may or may not cause branching depending on some condition. Also, depending on how it specifies the address of the new instruction sequence (the "target" address), a branch instruction is generally classified asdirect,indirect orrelative, meaning that the instruction contains the target address, or it specifies where the target address is to be found (e.g., a register or memory location), or it specifies the difference between the current and target addresses.
Branch instructions can alter the contents of theCPU'sprogram counter (PC) (or instruction pointer on Intel microprocessors). The program counter maintains the memory address of the next machine instruction to be fetched and executed. Therefore, a branch, if executed, causes the CPU to execute code from a new memory address, changing the program logic according to the algorithm planned by the programmer.
One type of machine level branch is thejump instruction. These may or may not result in the PC being loaded or modified with some new, different value other than what it ordinarily would have been (being incremented past the current instruction to point to the following, next instruction). Jumps typically haveunconditional andconditional forms where the latter may betaken ornot taken (the PC is modified or not) depending on some condition.
The second type of machine level branch is thecall instruction which is used to implementsubroutines. Like jump instructions, calls may or may not modify the PC according to condition codes, however, additionally areturn address is saved in a secure place in memory (usually in a memory resident data structure called astack). Upon completion of the subroutine, this return address is restored to the PC, and so program execution resumes with the instruction following the call instruction.
The third type of machine level branch is thereturn instruction. This "pops" a return address off the stack and loads it into the PC register, thus returning control to the calling routine. Return instructions may also be conditionally executed. This description pertains to ordinary practice; however, the machine programmer has considerable powers to manipulate the return address on the stack, and so redirect program execution in any number of different ways.
Depending on the processor, jump and call instructions may alter the contents of the PC register in different ways. An absolute address may be loaded, or the current contents of the PC may have some value (or displacement) added or subtracted from its current value, making the destination address relative to the current place in the program. The source of the displacement value may vary, such as an immediate value embedded within the instruction, or the contents of a processor register or memory location, or the contents of some location added to an index value.
The termbranch can also be used when referring to programs inhigh-level programming languages. In these branches usually take the form ofconditional statements of various forms that encapsulate the instruction sequence that will be executed if the conditions are satisfied. Unconditional branch instructions such asGOTO are used to unconditionally jump to a different instruction sequence. If the algorithm requires a conditional branch, the GOTO (or GOSUB subroutine call) is preceded by anIF-THEN statement specifying the condition(s). All high level languages support algorithms that can re-use code as aloop, a control structure that repeats a sequence of instructions until some condition is satisfied that causes the loop to terminate. Loops also qualify as branch instructions. At the machine level, loops are implemented as ordinary conditional jumps that redirect execution to repeating code.
In CPUs withflag registers, an earlier instruction sets a condition in the flag register. The earlier instruction may bearithmetic, or a logic instruction. It is often close to the branch, though not necessarily the instructionimmediately before the branch. The stored condition is then used in a branch such asjump if overflow-flag set. This temporary information is often stored in a flag register but may also be located elsewhere. A flag register design is simple in slower, simple computers. In fast computers a flag register can place a bottleneck on speed, because instructions that could otherwise operate in parallel (in severalexecution units) need to set the flag bits in a particular sequence.
There are also machines (or particular instructions) where the condition may be checked by the jump instruction itself, such asbranch <label> if register X negative. In simple computer designs, comparison branches execute more arithmetic and can use more power than flag register branches. In fast computer designs comparison branches can run faster than flag register branches, because comparison branches can access the registers with more parallelism, using the same CPU mechanisms as a calculation.
Some early and simple CPU architectures, still found in microcontrollers, may not implement a conditional jump, but rather only a conditional "skip the next instruction" operation. A conditional jump or call is thus implemented as a conditional skip of an unconditional jump or call instruction.
Depending on thecomputer architecture, theassembly languagemnemonic for a jump instruction is typically some shortened form of the wordjump or the wordbranch, often along with other informative letters (or an extra parameter) representing the condition. Sometimes other details are included as well, such as the range of the jump (the offset size) or a special addressing mode that should be used to locate the actual effective offset.
This table lists the machine level branch or jump instructions found in several well-known architectures:
| condition or result | x86 | PDP-11, VAX | ARM (partly 6502) | equation |
|---|---|---|---|---|
| zero (implies equal for sub/cmp) | JZ; JNZ | BEQ; BNE | BEQ; BNE | zero; not zero |
| negative (N), sign (S), or minus (M) | JS; JNS | BMI; BPL | BMI; BPL | negative; not negative |
| arithmetic overflow (flag called O or V) | JO; JNO | BVS; BVC | BVS; BVC | overflow; not overflow |
| carry (from add, cmp, shift, etc.) | JC; JNC | BCS; BCC | BCS; BCC | carry; not carry |
| unsigned below (lower) | JB | BLO | BLO* | borrow |
| unsigned below or equal (lower or same) | JBE | BLOS | BLS* | borrow or zero |
| unsigned above or equal (higher or same) | JAE | BHIS | BHS* | not borrow |
| unsigned above (higher) | JA | BHI | BHI* | not borrow and not zero |
| signed less than | JL | BLT | BLT | sign≠overflow |
| signed less or equal | JLE | BLE | BLE | (sign≠overflow) or zero |
| signed greater or equal | JGE | BGE | BGE | sign=overflow |
| signed greater than | JG | BGT | BGT | (sign=overflow) and not zero |
* x86, the PDP-11, VAX, and some others, set the carry-flag to signalborrow and clear the carry-flag to signalno borrow. ARM,6502, the PIC, and some others, do the opposite for subtractive operations. This inverted function of the carry flag for certain instructions is marked by (*), that is,borrow=not carry in some parts of the table, but if not otherwise noted, borrow≡carry. However, carry on additive operations are handled the same way by most architectures.
To achieve high performance, modern processors arepipelined. They consist of multiple parts that each partially process an instruction, feed their results to the next stage in the pipeline, and start working on the next instruction in the program. This design expects instructions to execute in a particular unchanging sequence. Conditional branch instructions make it impossible to know this sequence. So conditional branches can cause "stalls" in which the pipeline has to be restarted on a different part of the program.
Several techniques improve speed by reducing stalls from conditional branches.
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 thePower 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.
To run any software, hardwarebranch predictors 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.
Some logic can be written without branches or with fewer branches. It is often possible to usebitwise operations,conditional moves or otherpredication instead of branches.[1][2] In fact, branch-free code is a must for cryptography due totiming attacks.[3]
Another technique is abranch delay slot. In this approach, at least one instruction following a branch is always executed, with some exceptions such like the legacyMIPS 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 inRISC 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.)