<p>Consider a compiler whose target language is some virtual machine bytecode. The jump instructions have to encode the size of their jumps. For example, in <a href="https://en.m.wikipedia.org/wiki/List_of_Java_bytecode_instructions" rel="noreferrer">JVM bytecode</a> the <code>goto</code> instruction has three bytes: one byte for the jump opcode and two bytes for the jump length. For jumps longer than 2^15, the JVM provides an alternative <code>goto_w</code> instruction that uses four bytes for the jump length.</p>
<p>If the target language only has one jump instruction, a popular approach for emitting a forward jump is <strong>backpatching</strong>. The code generator does one pass over the program, appending bytecodes to the bytecode list. When we encounter a forward jump, we leave the  jump length blank. When we encounter the target of the jump, we go back to fill-in those jump lengths. <strong>But can we backpatch in languages that have more than one forward jump instruction?</strong> When it's time to emit the forward jump, how do we know which variant to pick, if we don't yet know how many bytes we'll need for the jump length? How does Java choose between<code>goto</code> and <code>goto_w</code>, when it's generating bytecode?</p>

<compilers><bytecode><code-generation>
How can we backpatch differently-sized jump instructions?
CC BY-SA 4.0
2023-06-20T00:49:54.413Z
My understanding of the "actual" Java compiler is it never makes this choice for any given jump (it just uses `goto_w` exclusively once the method is long enough), so it may not be the most useful reference point, though it's a good question more generally.
Michael Homer
CC BY-SA 4.0
2023-06-20T00:53:41.127Z
Interesting. Could you please write that up as an answer? Also, would you know how Java decides if a method is too long? (I suppose it can't count bytecode length itself, before the bytecode has been generated)
hugomg
CC BY-SA 4.0
2023-06-20T02:12:51.857Z
If I'm understanding the problem right, can't you just represent the emitted bytecode in a representation that allows you to backpatch in instructions of varying sizes? E.g., a linked list of bytestrings? Or alternatively, I guess you could always add two NOPs after the short jump instruction, to be overwritten if it needs to be long?
rydwolf
CC BY-SA 4.0
2023-06-20T02:30:21.313Z
Perhaps if we represented the program as a list of basic blocks, as is done in the compiler middle-end. Then the jump targets would be stable even if we changed the size of the instructions inside the blocks. However, the backend tends to prefer flat lists of instructions, because of performance... NOPs would be a non-starter: the whole point of using the shorter 2-byte instruction is to save space.
hugomg
CC BY-SA 4.0
2023-08-10T23:40:35.423Z
If you want to do it purely by backpatching, you need to use a goto_w for forward jumps where you don't yet know the destination.  But if you're instead building in chunks with relocations you later link together, you can do better.
Chris Dodd
CC BY-SA 4.0
2023-08-11T20:04:03.613Z
You may also want to look into how assemblers for physical machines with variable length instruction coding do it, too.  For example, the x86 architecture has various different size jump instructions, and many assemblers will offer to pick the correct size for you (although the one I'm most familiar with, NASM, does so using multiple passes, so that may not help).
occipita
<p>If you only have long/short jumps and other standard instructions then the &quot;start with all jumps small and increase only if needed&quot; algorithm is optimal. This is the case for JVM.</p>
<p>However, it is <em>not</em> the case for assembly language/machine code for many modern CPUs (e.g. x86 or x86-64), because assembly language is often padded for performance reasons.</p>
<p>Consider, say, a <code>while</code> loop:</p>
<pre class="lang-c prettyprint-override"><code>while (i &gt; 0) {
    /* Body of loop */
}
</code></pre>
<p>This might get compiled to something like this (using an x86-like assembly):</p>
<pre><code>    jmp loop_start

    # Pay attention to the following line
    .align 32
loop_top:
     # Body of loop

loop_start:
    test i, 0
    jg loop_top
</code></pre>
<p>The top of the loop is typically aligned so that when the branch occurs, we fill the CPU's decode stage in one cycle. If <code>loop_top</code> were the <em>last</em> byte in a cache line, and the first instruction in the loop body were more than one byte in size, we would have to wait two cycles for the first instruction to be decoded.</p>
<p>In addition to jump instructions, this padding directive is <em>also</em> a variable-size (pseudo-)instruction. Perversely, it can cause some branches to need to be changed from long to short. This general case is known to be NP-complete.</p>
<p>For some classic papers on the topic, see:</p>
<ul>
<li>Edward Robertson, <em><a href="https://dl.acm.org/doi/10.1145/357062.357067" rel="noreferrer">Code Generation and Storage Allocation for Machines with Span-Dependent Instructions</a></em>.</li>
<li>Thomas Szymanski, <em><a href="https://dl.acm.org/doi/10.1145/359460.359474" rel="noreferrer">Assembling code for machines with span-dependent instructions</a></em>.</li>
</ul>

CC BY-SA 4.0
2023-06-20T14:12:16.647Z
2023-06-20T23:58:32.430Z
2023-06-20T23:58:32.430Z
Pseudonym
CC BY-SA 4.0
2023-06-20T20:10:27.167Z
I wish I could accept two answers.
hugomg
CC BY-SA 4.0
2024-11-25T04:48:36.430Z
Szymanski shows that optimizing branches with targets of the form `label ± constant` is NP-complete (an unrealistic problem, as Robertson points out on page 75). Robertson shows NP-completeness when reordering is allowed to bring operands into range. Neither paper seems to show that the variant with short/long branches to labels and alignment padding and no reordering is NP-complete. I'm pretty sure it's solvable in linear time by dynamic programming (for a fixed maximum alignment at least).
benrg
CC BY-SA 4.0
2024-12-21T20:25:27.237Z
@benrg: The fact that a problem may be NP-complete or NP-hard does not necessarily imply that it's difficult to find good solutions.  Some language designers seem to be more interested in constraining languages to avoid making NP-complete or NP-hard problems in optimization, ignoring the fact that relatively simple heuristics may often find solutions for unconstrained problems which are better than the optimal solutions for more constrained problems.
supercat
CC BY-SA 4.0
2024-12-21T20:34:06.980Z
@benrg: Scenarios where attempting optimization X at the same time as other optimizations would break other things often lead to NP-hard problems, but simple algorithms like "If the benefits of using X can be shown to exceed any *plausible* benfits from other optimizations that might be rendered impossible by using X, use X; otherwise don't" don't.  They may not find all of the cases where X would be useful, but they'll find more cases than would be possible if language designers eliminated X for the purpose of avoiding NP-hard problems.
supercat
<p>An optimal solution can be found by representing it as an <a href="https://en.wikipedia.org/wiki/Constrained_optimization" rel="nofollow noreferrer">constrained optimisation problem</a>. Invent a variable for each jump instruction saying how many bytes that instruction takes, represent the jump lengths as sums of those variables (and constants for the sections of bytecode with known lengths), and then minimise the total length of bytecode subject to those constraints.</p>
<p>Note that we have to do this for both forwards and backwards jumps, since we don't know the lengths of backwards jumps until we know the sizes of the jump instructions they jump across, which may include forwards jumps.</p>
<p>It might help to see an example:</p>
<pre><code>label1:
    [50 bytes]
    jump label3
    [60 bytes]
label2:
    [70 bytes]
    jump label2
    [80 bytes]
    jump label2
    [90 bytes]
label3:
    [100 bytes]
    jump label1
</code></pre>
<p>Invent variables <span class="math-container">$x_1, x_2, x_3, x_4$</span> each with the domain <span class="math-container">$\{3, 4\}$</span> for the four jumps respectively; the value of the variable means the number of bytes used by that jump instruction.</p>
<p>Then we can write some constraints:</p>
<ul>
<li><span class="math-container">$(60 + 70 + x_2 + 80 + x_3 + 90 &lt; 256) \lor (x_1 = 4)$</span></li>
<li><span class="math-container">$(70 &lt; 256) \lor (x_2 = 4)$</span></li>
<li><span class="math-container">$(70 + x_2 + 80 &lt; 256) \lor (x_3 = 4)$</span></li>
<li><span class="math-container">$(50 + x_1 + 60 + 70 + x_2 + 80 + x_3 + 90 + 100 &lt; 256) \lor (x_4 = 4)$</span></li>
</ul>
<p>The optimal solution is <span class="math-container">$(x_1, x_2, x_3, x_4) = (4, 3, 3, 4)$</span>. This example is simple enough to solve by hand, but in practice you would write an algorithm (or use a constraint programming library) which would solve the general case.</p>

CC BY-SA 4.0
2023-06-20T12:59:16.090Z
2023-08-10T23:30:53.717Z
2023-08-10T23:30:53.717Z
kaya3
CC BY-SA 4.0
2023-08-11T14:20:28.227Z
@Bbrk24 perhaps you could edit, e.g. `(50+x₁+60+70+x₂+80+x₃+90+100<256) ∨ (x₄=4)` for the last line.
Toby Speight
CC BY-SA 4.0
2023-08-11T14:23:03.057Z
@TobySpeight We have MathJax now, so it's a moot point anyways. When this was first posted a couple months ago, I actually saw "\lor" and not "∨", but now it's fine.
Bbrk24
CC BY-SA 4.0
2023-08-11T14:26:51.310Z
The TeX notation is still a pain, even with browser scripting enabled, as it renders subscripts and superscripts as just formatted numbers, resulting in e.g. `x1` when copied elsewhere (it's a particular nuisance with numbers such as 2³², which completely changes meaning when presented as 232....)
Toby Speight
CC BY-SA 4.0
2023-08-11T14:50:58.977Z
@TobySpeight Unfortunately that applies to HTML `<sup>` and `<sub>` tags too, and many Unicode symbols [don't work everywhere](https://langdev.meta.stackexchange.com/a/562/89) (also, Unicode subscripts and superscripts are smaller and harder to read, and harder to write). MathJax also has some [good accessibility features](https://docs.mathjax.org/en/latest/basic/accessibility.html).
kaya3
<p>The abstraction in the compiler might not be exactly that of the emitted instructions. I.e. the problem can be avoided performing all operations on an instruction class with instruction lists being pointers to instruction objects and then generating all the code top-down. In that case, you'd know the size of variable size cross jumps when emitting them.</p>

CC BY-SA 4.0
2023-08-11T16:59:08.540Z
2023-08-11T16:59:08.540Z
feldentm
CC BY-SA 4.0
2023-08-11T18:48:53.160Z
I don't see how this would work when two jump instructions each must go past each other. For example in `A ... (jump to B) ... (jump to A) ... B`, you don't know how far the first jump is until you know whether the second jump is short or long, but you also don't know how far the second jump is until you know whether the first jump is short or long. Could you give an example of how your approach would handle this kind of case?
kaya3
CC BY-SA 4.0
2023-08-12T16:18:18.710Z
Assuming that you could always choose to use the longer form, you'd perform an approximation pass and choose the shorter form only if you are sure that it is always correct. In essence, you propagate an upper and lower length of the resulting program.
feldentm
<p>I can't answer more generally, but the mainline Java compiler sidesteps the issue of backpatching different instruction sizes: whenever <code>goto_w</code> will be required at all, every jump in the method uses it, even short ones, and it just retries the compilation with all long jumps when short jumps didn't pan out. This is just a try-and-see approach, nothing fancy.</p>
<hr />
<p>You can see this happening in decompilation without too much trouble. Take a program like</p>
<pre class="lang-java prettyprint-override"><code>public class GotoTest {
    public static void main(String[] args) {
        for (int i = 0; i &lt; 100000; ) {
            i += 1234;
            ... // repeated several times
            for (int j = 0; j &lt; i; j++) { i += 123; }
            i += 1234;
            ... // and very many more of them
        }
    }
}
</code></pre>
<p>and then you can inspect the bytecode with <code>javap -c</code> to find the inner short loop:</p>
<pre class="lang-none prettyprint-override"><code>      55: iinc_w        1, 1234
      61: iconst_0
      62: istore_2
      63: iload_2
      64: iload_1
      65: if_icmplt     73
      68: goto_w        84
      73: iinc          1, 123
      76: iinc          2, 1
      79: goto_w        63
      84: iinc_w        1, 1234
</code></pre>
<p>You can see that it's using <code>goto_w</code> even to go from 68 to 84 and 79 to 63, well within range of ordinary <code>goto</code>.</p>
<hr />
<p>I'm not sure this is required anywhere, but it is intended behaviour described in <a href="https://github.com/openjdk/jdk/blob/b2e86aef65f4d579896b6db83aaad408b6c580d4/src/jdk.compiler/share/classes/com/sun/tools/javac/jvm/Gen.java#L944" rel="nofollow noreferrer">a documentation comment in the JDK source</a>:</p>
<blockquote>
<ul>
<li>@param fatcode  A flag that indicates whether all jumps are
within 32K.  We first invoke this method under
the assumption that fatcode == false, i.e. all
jumps are within 32K.  If this fails, fatcode
is set to true and we try again.</li>
</ul>
</blockquote>
<p>They take the fatcode flag into account when they <a href="https://github.com/openjdk/jdk/blob/b2e86aef65f4d579896b6db83aaad408b6c580d4/src/jdk.compiler/share/classes/com/sun/tools/javac/jvm/Code.java#L1439" rel="nofollow noreferrer">emit a jump instruction</a>:</p>
<pre class="lang-java prettyprint-override"><code>public int emitJump(int opcode) {
    if (fatcode) {
        ...
        emitop4(opcode + goto_w - goto_, 0);
        ...
    } else {
        emitop2(opcode, 0);
    }
}
</code></pre>
<p>When compiling a method, it optimistically tries expecting short jumps, and when that fails it tries again making them all long; it's a from-scratch recompilation of the method with wide instructions inserted and addresses recalculated (other methods don't change). The answer to &quot;how does it know which variant to pick&quot; is just that it already tried using the other version, which doesn't feel elegant but obviously works.</p>

CC BY-SA 4.0
2023-06-20T01:32:23.563Z
2023-06-20T02:42:40.640Z
2023-06-20T02:42:40.640Z
Michael Homer
CC BY-SA 4.0
2023-06-20T02:42:54.560Z
Impressive! This answer goes above and beyond what I expected.
hugomg
# How can we backpatch differently-sized jump instructions?
Posted by: username_0 on 2023-06-20
Consider a compiler whose target language is some virtual machine bytecode. The jump instructions have to encode the size of their jumps. For example, in [JVM bytecode](https://en.m.wikipedia.org/wiki/List_of_Java_bytecode_instructions) the `goto` instruction has three bytes: one byte for the jump opcode and two bytes for the jump length. For jumps longer than 2^15, the JVM provides an alternative `goto_w` instruction that uses four bytes for the jump length.

If the target language only has one jump instruction, a popular approach for emitting a forward jump is **backpatching**. The code generator does one pass over the program, appending bytecodes to the bytecode list. When we encounter a forward jump, we leave the jump length blank. When we encounter the target of the jump, we go back to fill-in those jump lengths. **But can we backpatch in languages that have more than one forward jump instruction?** When it's time to emit the forward jump, how do we know which variant to pick, if we don't yet know how many bytes we'll need for the jump length? How does Java choose between`goto` and `goto_w`, when it's generating bytecode?
**Tags:** compilers bytecode code-generation
> **Comments:**
> **username_1**: My understanding of the "actual" Java compiler is it never makes this choice for any given jump (it just uses `goto_w` exclusively once the method is long enough), so it may not be the most useful reference point, though it's a good question more generally.  
> **username_0**: Interesting. Could you please write that up as an answer? Also, would you know how Java decides if a method is too long? (I suppose it can't count bytecode length itself, before the bytecode has been generated)  
> **username_2**: If I'm understanding the problem right, can't you just represent the emitted bytecode in a representation that allows you to backpatch in instructions of varying sizes? E.g., a linked list of bytestrings? Or alternatively, I guess you could always add two NOPs after the short jump instruction, to be overwritten if it needs to be long?  
> **username_0**: Perhaps if we represented the program as a list of basic blocks, as is done in the compiler middle-end. Then the jump targets would be stable even if we changed the size of the instructions inside the blocks. However, the backend tends to prefer flat lists of instructions, because of performance... NOPs would be a non-starter: the whole point of using the shorter 2-byte instruction is to save space.  
> **username_3**: If you want to do it purely by backpatching, you need to use a goto_w for forward jumps where you don't yet know the destination.  But if you're instead building in chunks with relocations you later link together, you can do better.  
> **username_4**: You may also want to look into how assemblers for physical machines with variable length instruction coding do it, too.  For example, the x86 architecture has various different size jump instructions, and many assemblers will offer to pick the correct size for you (although the one I'm most familiar with, NASM, does so using multiple passes, so that may not help).  
---
## 4 answers
### Answer by username_1 on 2023-06-20. Score: 5 | Accepted answer
I can't answer more generally, but the mainline Java compiler sidesteps the issue of backpatching different instruction sizes: whenever goto_w will be required at all, every jump in the method uses it, even short ones, and it just retries the compilation with all long jumps when short jumps didn't pan out. This is just a try-and-see approach, nothing fancy.

You can see this happening in decompilation without too much trouble. Take a program like
public class GotoTest {
    public static void main(String[] args) {
        for (int i = 0; i < 100000; ) {
            i += 1234;
            ... // repeated several times
            for (int j = 0; j < i; j++) { i += 123; }
            i += 1234;
            ... // and very many more of them
        }
    }
}

and then you can inspect the bytecode with javap -c to find the inner short loop:
      55: iinc_w        1, 1234
      61: iconst_0
      62: istore_2
      63: iload_2
      64: iload_1
      65: if_icmplt     73
      68: goto_w        84
      73: iinc          1, 123
      76: iinc          2, 1
      79: goto_w        63
      84: iinc_w        1, 1234

You can see that it's using goto_w even to go from 68 to 84 and 79 to 63, well within range of ordinary goto.

I'm not sure this is required anywhere, but it is intended behaviour described in a documentation comment in the JDK source:


@param fatcode  A flag that indicates whether all jumps are
within 32K.  We first invoke this method under
the assumption that fatcode == false, i.e. all
jumps are within 32K.  If this fails, fatcode
is set to true and we try again.


They take the fatcode flag into account when they emit a jump instruction:
public int emitJump(int opcode) {
    if (fatcode) {
        ...
        emitop4(opcode + goto_w - goto_, 0);
        ...
    } else {
        emitop2(opcode, 0);
    }
}

When compiling a method, it optimistically tries expecting short jumps, and when that fails it tries again making them all long; it's a from-scratch recompilation of the method with wide instructions inserted and addresses recalculated (other methods don't change). The answer to "how does it know which variant to pick" is just that it already tried using the other version, which doesn't feel elegant but obviously works.
> **Comments:**
> **username_0** (2023-06-20): Impressive! This answer goes above and beyond what I expected.  
---
### Answer by username_5 on 2023-06-20. Score: 10
If you only have long/short jumps and other standard instructions then the "start with all jumps small and increase only if needed" algorithm is optimal. This is the case for JVM.
However, it is not the case for assembly language/machine code for many modern CPUs (e.g. x86 or x86-64), because assembly language is often padded for performance reasons.
Consider, say, a while loop:
while (i > 0) {
    /* Body of loop */
}

This might get compiled to something like this (using an x86-like assembly):
    jmp loop_start

    # Pay attention to the following line
    .align 32
loop_top:
     # Body of loop

loop_start:
    test i, 0
    jg loop_top

The top of the loop is typically aligned so that when the branch occurs, we fill the CPU's decode stage in one cycle. If loop_top were the last byte in a cache line, and the first instruction in the loop body were more than one byte in size, we would have to wait two cycles for the first instruction to be decoded.
In addition to jump instructions, this padding directive is also a variable-size (pseudo-)instruction. Perversely, it can cause some branches to need to be changed from long to short. This general case is known to be NP-complete.
For some classic papers on the topic, see:

Edward Robertson, Code Generation and Storage Allocation for Machines with Span-Dependent Instructions.
Thomas Szymanski, Assembling code for machines with span-dependent instructions.
> **Comments:**
> **username_0** (2023-06-20): I wish I could accept two answers.  
> **username_6** (2024-11-25): Szymanski shows that optimizing branches with targets of the form `label ± constant` is NP-complete (an unrealistic problem, as Robertson points out on page 75). Robertson shows NP-completeness when reordering is allowed to bring operands into range. Neither paper seems to show that the variant with short/long branches to labels and alignment padding and no reordering is NP-complete. I'm pretty sure it's solvable in linear time by dynamic programming (for a fixed maximum alignment at least).  
> **username_7** (2024-12-21): @benrg: The fact that a problem may be NP-complete or NP-hard does not necessarily imply that it's difficult to find good solutions.  Some language designers seem to be more interested in constraining languages to avoid making NP-complete or NP-hard problems in optimization, ignoring the fact that relatively simple heuristics may often find solutions for unconstrained problems which are better than the optimal solutions for more constrained problems.  
> **username_7** (2024-12-21): @benrg: Scenarios where attempting optimization X at the same time as other optimizations would break other things often lead to NP-hard problems, but simple algorithms like "If the benefits of using X can be shown to exceed any *plausible* benfits from other optimizations that might be rendered impossible by using X, use X; otherwise don't" don't.  They may not find all of the cases where X would be useful, but they'll find more cases than would be possible if language designers eliminated X for the purpose of avoiding NP-hard problems.  
---
### Answer by username_8 on 2023-06-20. Score: 5
An optimal solution can be found by representing it as an constrained optimisation problem. Invent a variable for each jump instruction saying how many bytes that instruction takes, represent the jump lengths as sums of those variables (and constants for the sections of bytecode with known lengths), and then minimise the total length of bytecode subject to those constraints.
Note that we have to do this for both forwards and backwards jumps, since we don't know the lengths of backwards jumps until we know the sizes of the jump instructions they jump across, which may include forwards jumps.
It might help to see an example:
label1:
    [50 bytes]
    jump label3
    [60 bytes]
label2:
    [70 bytes]
    jump label2
    [80 bytes]
    jump label2
    [90 bytes]
label3:
    [100 bytes]
    jump label1

Invent variables $x_1, x_2, x_3, x_4$ each with the domain $\{3, 4\}$ for the four jumps respectively; the value of the variable means the number of bytes used by that jump instruction.
Then we can write some constraints:

$(60 + 70 + x_2 + 80 + x_3 + 90 < 256) \lor (x_1 = 4)$
$(70 < 256) \lor (x_2 = 4)$
$(70 + x_2 + 80 < 256) \lor (x_3 = 4)$
$(50 + x_1 + 60 + 70 + x_2 + 80 + x_3 + 90 + 100 < 256) \lor (x_4 = 4)$

The optimal solution is $(x_1, x_2, x_3, x_4) = (4, 3, 3, 4)$. This example is simple enough to solve by hand, but in practice you would write an algorithm (or use a constraint programming library) which would solve the general case.
> **Comments:**
> **username_9** (2023-08-11): @Bbrk24 perhaps you could edit, e.g. `(50+x₁+60+70+x₂+80+x₃+90+100<256) ∨ (x₄=4)` for the last line.  
> **username_10** (2023-08-11): @TobySpeight We have MathJax now, so it's a moot point anyways. When this was first posted a couple months ago, I actually saw "\lor" and not "∨", but now it's fine.  
> **username_9** (2023-08-11): The TeX notation is still a pain, even with browser scripting enabled, as it renders subscripts and superscripts as just formatted numbers, resulting in e.g. `x1` when copied elsewhere (it's a particular nuisance with numbers such as 2³², which completely changes meaning when presented as 232....)  
> **username_8** (2023-08-11): @TobySpeight Unfortunately that applies to HTML `<sup>` and `<sub>` tags too, and many Unicode symbols [don't work everywhere](https://langdev.meta.stackexchange.com/a/562/89) (also, Unicode subscripts and superscripts are smaller and harder to read, and harder to write). MathJax also has some [good accessibility features](https://docs.mathjax.org/en/latest/basic/accessibility.html).  
---
### Answer by username_11 on 2023-08-11. Score: 2
The abstraction in the compiler might not be exactly that of the emitted instructions. I.e. the problem can be avoided performing all operations on an instruction class with instruction lists being pointers to instruction objects and then generating all the code top-down. In that case, you'd know the size of variable size cross jumps when emitting them.
> **Comments:**
> **username_8** (2023-08-11): I don't see how this would work when two jump instructions each must go past each other. For example in `A ... (jump to B) ... (jump to A) ... B`, you don't know how far the first jump is until you know whether the second jump is short or long, but you also don't know how far the second jump is until you know whether the first jump is short or long. Could you give an example of how your approach would handle this kind of case?  
> **username_11** (2023-08-12): Assuming that you could always choose to use the longer form, you'd perform an approximation pass and choose the shorter form only if you are sure that it is always correct. In essence, you propagate an upper and lower length of the resulting program.  
---
