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.[1] This is easily done in a single pass through the program, following acyclic chained jumps until the compiler arrives at a fixed point.
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 runtimebranch.[2]
Examplesedit
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:
jump, threading, confused, with, threaded, code, this, article, needs, additional, citations, verification, please, help, improve, this, article, adding, citations, reliable, sources, unsourced, material, challenged, removed, find, sources, news, newspapers, b. Not to be confused with threaded code This article needs additional citations for verification Please help improve this article by adding citations to reliable sources Unsourced material may be challenged and removed Find sources Jump threading news newspapers books scholar JSTOR December 2009 Learn how and when to remove this template message 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 1 This is easily done in a single pass through the program following acyclic chained jumps until the compiler arrives at a fixed point Contents 1 Benefits 2 Examples 3 See also 4 ReferencesBenefits editThe 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 2 Examples editThe following pseudocode demonstrates when a jump may be threaded 10 a SomeNumber 20 IF a gt 10 GOTO 50 50 IF a gt 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 if x amp amp y bar if y z foo The above can be transformed into void baz bool x bool y bool z if x amp amp y bar goto jmp if y z jmp foo 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 2 See also editSwitch programming Spaghetti codeReferences edit Optimize Options Using the GNU Compiler Collection GCC a b A gentle introduction to jump threading optimizations Red Hat Developer developers redhat com Retrieved 2023 01 08 nbsp This computer science article is a stub You can help Wikipedia by expanding it vte G displaystyle Gamma vdash nbsp This programming language theory or type theory related article is a stub You can help Wikipedia by expanding it vte Retrieved from https en wikipedia org w index php title Jump threading amp oldid 1183137256, wikipedia, wiki, book, books, library,
