Branch (computer science)
Encyclopedia
A branch is sequence of code in a computer program
which is conditionally executed depending on whether the flow of control
is altered or not (at the branching point). The term can be used when referring to programs in high level languages as well as program written in machine code
or assembly language
. Explicit branches in high-level programming language
s usually take the form of conditional statement
s of various forms that encapsulates the branches of code that should be executed (or not) upon some condition; machine level instructions that define corresponding branches of code are denoted jump instructions. The principal function of a jump instruction can thus be compared to the GOTO
s needed to build control structures in older high level languages.
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 (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 . 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.
* 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.
Computer program
A computer program is a sequence of instructions written to perform a specified task with a computer. A computer requires programs to function, typically executing the program's instructions in a central processor. The program has an executable form that the computer can use directly to execute...
which is conditionally executed depending on whether the flow of control
Control flow
In computer science, control flow refers to the order in which the individual statements, instructions, or function calls of an imperative or a declarative program are executed or evaluated....
is altered or not (at the branching point). The term can be used when referring to programs in high level languages as well as program written in machine code
Machine code
Machine code or machine language is a system of impartible instructions executed directly by a computer's central processing unit. Each instruction performs a very specific task, typically either an operation on a unit of data Machine code or machine language is a system of impartible instructions...
or assembly language
Assembly language
An assembly language is a low-level programming language for computers, microprocessors, microcontrollers, and other programmable devices. It implements a symbolic representation of the machine codes and other constants needed to program a given CPU architecture...
. Explicit branches in high-level programming language
High-level programming language
A high-level programming language is a programming language with strong abstraction from the details of the computer. In comparison to low-level programming languages, it may use natural language elements, be easier to use, or be from the specification of the program, making the process of...
s usually take the form of conditional statement
Conditional statement
In computer science, conditional statements, conditional expressions and conditional constructs are features of a programming language which perform different computations or actions depending on whether a programmer-specified boolean condition evaluates to true or false...
s of various forms that encapsulates the branches of code that should be executed (or not) upon some condition; machine level instructions that define corresponding branches of code are denoted jump instructions. The principal function of a jump instruction can thus be compared to the GOTO
Goto
goto is a statement found in many computer programming languages. It is a combination of the English words go and to. It performs a one-way transfer of control to another line of code; in contrast a function call normally returns control...
s needed to build control structures in older high level languages.
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 (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 . 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
Computer architecture
In computer science and engineering, computer architecture is the practical art of selecting and interconnecting hardware components to create computers that meet functional, performance and cost goals and the formal modelling of those systems....
, the assembly language
Assembly language
An assembly language is a low-level programming language for computers, microprocessors, microcontrollers, and other programmable devices. It implements a symbolic representation of the machine codes and other constants needed to program a given CPU architecture...
mnemonic
Mnemonic
A mnemonic , or mnemonic device, is any learning technique that aids memory. To improve long term memory, mnemonic systems are used to make memorization easier. Commonly encountered mnemonics are often verbal, such as a very short poem or a special word used to help a person remember something,...
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.
Typical branch/jump instructions exemplified by some 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.
See also
- Branch delay slotBranch delay slotIn computer architecture, a delay slot is an instruction slot that gets executed without the effects of a preceding instruction. The most common form is a single arbitrary instruction located immediately after a branch instruction on a RISC or DSP architecture; this instruction will execute even if...
- Branch predictorBranch predictorIn computer architecture, a branch predictor is a digital circuit that tries to guess which way a branch will go before this is known for sure. The purpose of the branch predictor is to improve the flow in the instruction pipeline...
- Branch tableBranch tableIn computer programming, a branch table is a term used to describe an efficient method of transferring program control to another part of a program using a table of branch instructions. It is a form of multiway branch...
- Conditional (programming)
- Control flowControl flowIn computer science, control flow refers to the order in which the individual statements, instructions, or function calls of an imperative or a declarative program are executed or evaluated....
- Indirect branchIndirect branchAn indirect branch is a type of program control instruction present in some machine language instruction sets. Rather than specifying the address of the next instruction to execute, as in a direct branch, the argument specifies where the address is located...
- Instruction pipelineInstruction pipelineAn instruction pipeline is a technique used in the design of computers and other digital electronic devices to increase their instruction throughput ....
- Spaghetti codeSpaghetti codeSpaghetti code is a pejorative term for source code that has a complex and tangled control structure, especially one using many GOTOs, exceptions, threads, or other "unstructured" branching constructs. It is named such because program flow tends to look like a bowl of spaghetti, i.e. twisted and...
External links
- Free IA-32 and x86-64 documentation, provided by Intel
- The PDP-11 FAQ
- The ARM instruction set