Branch (computer science)

For other uses, see Branch (disambiguation).

A branch is an instruction in a computer 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.[lower-alpha 1] Branch (or branching, branched) may also refer to the act of switching execution to a different instruction sequence as a result of executing a branch instruction. A branch instruction can be either an unconditional branch, which always results in branching, or a conditional branch, which may or may not cause branching, depending on some condition. Branch instructions are used to implement control flow in program loops and conditionals (i.e., executing a particular sequence of instructions only if certain conditions are satisfied).

Implementation

The term branch can be used when referring to programs in high level languages as well as program written in machine code or assembly language. In high-level programming languages, branches usually take the form of conditional statements of various forms that encapsulate the instruction sequence that will be executed if the conditions are satisfied. Unconditional branch instructions such as GOTO are used to unconditionally "jump" to (begin execution of) a different instruction sequence.

Machine level branch instructions are sometimes called jump instructions. Machine level jump instructions typically have unconditional and conditional forms where the latter may be taken or not taken depending on some condition. The truthness of this condition is typically evaluated and temporarily stored by some previous instruction (though not necessarily the one immediately before) and then used such as in jump if overflow-flag set. This temporary information is often stored in a flag register but may also be located elsewhere. There are also machines (or particular instructions) where the condition may be checked by the jump instruction itself, such as branch <label> if register X negative. When a branch is taken, the next instruction executed is defined by the argument to the jump instruction; when not taken, the next instruction executed is the instruction immediately following the jump instruction in memory so that the flow of control is unchanged.

Depending on computer architecture, the assembly language mnemonic for a jump instruction is typically some shortened form of the word jump or the word branch, 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.

Examples

This table lists the machine level branch/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 signal borrow and clear the carry-flag to signal no 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.

Performance problems with branch instructions

To achieve high performance, modern processors are pipelined: 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 requires knowing which instruction is going to be executed next, and (conditional) branch instructions make it impossible to know this in general, thus potentially causing stalls where the pipeline has to be restarted on a different part of the program.

Two techniques alleviate this situation. The first is branch prediction, which is implemented as part of modern processors. The processor attempts to guess the outcome of the conditional test and starts executing the branch that it thinks is going to be taken. The other technique is to write programs without branches, or with fewer branches, typically using bitwise operations instead.[1]

See also

Notes

  1. ↑ At least conceptually; see out-of-order execution.

References

  1. ↑ Knuth, Donald (2008). The Art of Computer Programming. Volume 4, Pre-fascicle 1A (Revision 6 ed.). pp. 48–49.

External links

This article is issued from Wikipedia - version of the Thursday, December 24, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.