- Source: Jump threading
In computing, jump threading is a compiler optimization of one jump directly to a second jump. If the second condition is a subset 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.
Examples
The following pseudocode 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:
The above can be transformed into:
If the first branch is taken, x and y are both true (logical conjunction), hence evaluation of expression y || z is not needed (logical disjunction). Therefore, a jump to label jmp is performed.
See also
Switch (programming)
Spaghetti code
References
Kata Kunci Pencarian:
- Jump threading
- Threaded code
- Control-flow graph
- Threads (social network)
- GNU Compiler Collection
- Optimizing compiler
- Mexican jumping bean
- Indirect branch
- Sarah Harding
- Comparison of multi-paradigm programming languages
