In
computing
Computing is any goal-oriented activity requiring, benefiting from, or creating computer, computing machinery. It includes the study and experimentation of algorithmic processes, and the development of both computer hardware, hardware and softw ...
, jump threading is a
compiler optimization
An optimizing compiler is a compiler designed to generate code that is optimized in aspects such as minimizing program execution time, memory usage, storage size, and power consumption. Optimization is generally implemented as a sequence of op ...
of one jump directly to a second jump. If the second condition is a
subset
In mathematics, a Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they a ...
or
inverse of the first, it can be eliminated, or threaded through the first jump.
This is easily done in a single pass through the program, following acyclic chained jumps until the compiler arrives at a fixed point.
Benefits
The primary benefit of jump threading is the reduction of the amount of dynamically executed jumps. This makes way for further optimizations as there is a decrease in the number of conditionals, which will improve performance. On average one can expect 2-3 instructions being omitted as a result from a successful removal of a
runtime branch
A branch, also called a ramus in botany, is a stem that grows off from another stem, or when structures like veins in leaves are divided into smaller veins.
History and etymology
In Old English, there are numerous words for branch, includ ...
.
Examples
The following
pseudocode
In computer science, pseudocode is a description of the steps in an algorithm using a mix of conventions of programming languages (like assignment operator, conditional operator, loop) with informal, usually self-explanatory, notation of actio ...
demonstrates when a jump may be threaded.
10. a = SomeNumber();
20. IF a > 10 GOTO 50
...
50. IF a > 0 GOTO 100
...
The jump on line 50 will always be taken if the jump on line 20 is taken. Therefore, for as long as line 100 is within the reachable range of the jump (or the size of the jump doesn't matter), the jump on line 20 may safely be modified to jump directly to line 100.
Another example shows jump threading of 2 partial overlap conditions:
void baz(bool x, bool y, bool z)
The above can be transformed into:
void baz(bool x, bool y, bool z)
If the first branch is taken,
x and
y are both
true
True most commonly refers to truth, the state of being in congruence with fact or reality.
True may also refer to:
Places
* True, West Virginia, an unincorporated community in the United States
* True, Wisconsin, a town in the United States
* ...
(
logical conjunction
In logic, mathematics and linguistics, ''and'' (\wedge) is the Truth function, truth-functional operator of conjunction or logical conjunction. The logical connective of this operator is typically represented as \wedge or \& or K (prefix) or ...
), hence evaluation of
expression y , , z is not needed (
logical disjunction
In logic, disjunction (also known as logical disjunction, logical or, logical addition, or inclusive disjunction) is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is ...
). Therefore, a jump to
label
A label (as distinct from signage) is a piece of paper, plastic film, cloth, metal, or other material affixed to a container or product. Labels are most often affixed to packaging and containers using an adhesive, or sewing when affix ...
jmp is performed.
See also
*
Switch (programming)
In computer programming languages, a switch statement is a type of selection control mechanism used to allow the value of a variable (programming), variable or expression to change the control flow of program execution via search and map.
Switc ...
*
Spaghetti code
Spaghetti code is a pejorative phrase for difficult-to- maintain and unstructured computer source code. Code being developed with poor structure can be due to any of several factors, such as volatile project requirements, lack of programming style ...
References
Compiler optimizations
{{plt-stub