Branch (computer science)
|This article does not cite any references or sources. (June 2009)|
A branch is an instruction in a computer program that may, when executed by a computer, cause the computer to begin execution of a different instruction sequence. Branch (or branching, branched) may also refer to the act of beginning execution of a different instruction sequence due to 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.
When executing (or "running") a program, a computer will fetch and execute instructions in sequence (in their order of appearance in the program) until it encounters a branch instruction. If the instruction is an unconditional branch, or it is conditional and the condition is satisfied, the computer will branch (fetch its next instruction from a different instruction sequence) as specified by the branch instruction. However, if the branch instruction is conditional and the condition is not satisfied, the computer will not branch; instead, it will continue executing the current instruction sequence, beginning with the instruction that follows the conditional branch instruction.
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.
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.
- Branch delay slot
- Branch predictor
- Branch table
- Conditional (programming)
- Control flow
- Indirect branch
- Instruction pipeline
- Spaghetti code