This is the first post in a series where we build upon a simple Java bytecode peephole optimiser: each post takes a single peephole optimisation for Java bytecode, shows how to implement it, and looks at the pitfalls to watch out for.

In this post we’ll implement one of the classic peephole optimisations: eliminating a redundant load after a store, and then we’ll take a look at one case where we cannot safely apply the optimisation.

The redundant load/store pattern

Let’s start with a simple Java method:

static int square(int n) {
    int y = n * n;
    return y + 1;
}

Compiling this and disassembling it with javap -c shows the value of n * n making a round trip through local variable slot 1:

static int square(int);
  Code:
       0: iload_0
       1: iload_0
       2: imul
       3: istore_1 <-- store n * n in slot 1 (y)
       4: iload_1  <-- load it straight back
       5: iconst_1
       6: iadd
       7: ireturn

At offset 3 the result is stored into the slot for y and at offset 4 it is immediately loaded back. But the value was already on the operand stack before the store consumed it, so instead of reloading it from the local variable we can duplicate it first with a dup instruction:

istore_1        dup
iload_1    =>   istore_1

The dup copies the top of the stack, the store consumes the copy, and the original value stays behind for the addition that follows: same value, same local variables, same stack afterwards.

This is one member of a small family of rewrites, all pairs of instructions that touch the same local variable slot. With two instructions and two things you can do to a slot, there are exactly four:

  • istore x; iload x becomes dup; istore x: the value is needed again, so copy it instead of reloading it.
  • iload x; istore x can be removed completely: it stores a value into the slot it was just loaded from.
  • istore x; istore x becomes pop; istore x: the first store is immediately overwritten, so it is dead.
  • iload x; iload x becomes iload x; dup: the second read of the slot is a copy of the first. There is a catch to this one, and it gets its own post later in the series.

There is an instance of that last one in square as well: the iload_0; iload_0 that loads n twice for computing n * n.

How much the first rewrite saves depends on the slot. In square it saves nothing: slots 0 to 3 have their own one-byte opcodes, so dup; istore_1 is the same number of bytes as istore_1; iload_1. From slot 4 upwards javac emits the two-byte forms, and then istore 6; iload 6 (four bytes) becomes dup; istore 6 (three).

There is a small cost too. The dup leaves an extra value on the operand stack, so a method’s max_stack can go up by one. The Class-File API recalculates that when it writes the class out, so nothing breaks but the method reserves one more stack slot than it did before.

The more useful gain is what we removed: a read of the local variable, and therefore the dependency on the slot. If slot 1 (used by variable y from the original source) turns out to be otherwise unused, a later dead-store optimisation can remove the istore and the dup entirely, which it couldn’t do while a load still read from the slot.

Peephole optimisations often work together, each applying a simple transformation, with one rewrite creating the opportunity for another.

Implementing the peephole transformation

We’ll add the peephole rewrite rule to the sliding window optimiser from the original peephole post. Optimisations plug into the optimiser through a small interface: a peephole looks at the start of the window and, if its pattern is there, returns a Rewrite holding the number of elements it matched and the elements that replace them. The window holds CodeElements, and each peephole is handed the ConstantPoolBuilder for the class being written, which a rewrite needs if its replacement adds constants. Ours doesn’t, so it ignores it.

record Rewrite(int matched, List<CodeElement> replacement) {}

interface Peephole {
    String name();
    Rewrite apply(CodeElement[] window, ConstantPoolBuilder pool);
}

Note: We pass DROP_LINE_NUMBERS and DROP_DEBUG to the Class-File API when parsing, so instructions sit directly next to each other in the window. Without that, javac’s line number table pseudo-instructions would appear between our store and our load and the pattern would never match.

Our pattern is two instructions long, so we only need to look at the first two elements of the window: a StoreInstruction, then a LoadInstruction for the same slot with the same TypeKind (we’ll only consider int types for this post). The replacement is the dup, built with StackInstruction, followed by the store we matched:

// Rewrites `istore x; iload x` to `dup; istore x`.
class StoreLoadRewrite implements Peephole {
    public String name() { return "storeLoad"; }

    public Rewrite apply(CodeElement[] window, ConstantPoolBuilder pool) {
        if (window[0] instanceof StoreInstruction store && store.typeKind() == TypeKind.INT &&
            window[1] instanceof LoadInstruction load && load.typeKind() == TypeKind.INT &&
            load.slot() == store.slot()) {
            return new Rewrite(2, List.of(StackInstruction.of(DUP), store));
        }
        return null; // no match
    }
}

Add the new peephole to the optimiser’s list, and the optimiser will try it at every window position. The optimiser takes a jar in and writes a jar out, so let’s put our square method in a class, compile it, and run the optimiser over it:

$ javac Square.java
$ jar cf square.jar Square.class
$ java Optimizer.java square.jar square-opt.jar
storeLoad: 1

Disassembling the class from the optimised jar shows the rewrite occurred, exactly as expected:

static int square(int);
  Code:
       0: iload_0
       1: iload_0
       2: imul
       3: dup       <-- dup replaced iload_1
       4: istore_1
       5: iconst_1
       6: iadd
       7: ireturn

Does this peephole always work? Let’s take a look at another example.

The same pattern in a loop

Try the same rewrite on a method with a loop in it:

static int countdown(int n) {
    int y = n;
    while (y > 0) y--;
    return y;
}

Here int y = n stores into slot 1 and the loop condition reads the slot straight back, so our pattern is in this method too, right? At offsets 1 and 2:

static int countdown(int);
  Code:
       0: iload_0
       1: istore_1  <-- store n in slot 1 (y)
       2: iload_1   <-- the loop starts here
       3: ifle 12
       6: iinc 1, -1
       9: goto 2
      12: iload_1
      13: ireturn

Running the optimiser over this does nothing though:

$ javac Countdown.java
$ jar cf countdown.jar Countdown.class
$ java Optimizer.java countdown.jar countdown-opt.jar

Not a single match, so there are no counts to print.

Remember how we stripped out line number pseudo-instructions so that they don’t interrupt our pattern matching? Well, line numbers aren’t the only pseudo-instructions. The peephole didn’t match anything in this example because of the LabelTarget pseudo-instruction that sits between the store and the load:

window[0] = istore_1
window[1] = LabelTarget   <-- the goto at offset 9 jumps here
window[2] = iload_1

A LabelTarget marks a position that some other instruction jumps to: here, the goto at offset 9 jumps to offset 2. So window[1] is a label rather than a load, and the pattern doesn’t match.

That might look like a limitation of our simple matcher, but actually it is essential for correctness.

Suppose we matched across it anyway: keep labels out of the window as we fill it, and splice them back in after the replacement. The label sat in front of the iload_1, and the replacement, dup; istore_1, has no load in it, so the label ends up in front of the ifle, and the goto at offset 9 jumps there.

Now, there are two ways to reach that ifle and they disagree about the stack: entering from the top, the dup has left a value on the stack to test; coming round the loop from the goto, the stack is empty. A class file records the stack and locals at each jump target, in its stack map table, and there can only be one description per target, so this method cannot be written at all. The Class-File API’s frame generator, the one I dug into in Same Bytecode, Two Verdicts, reports a stack size mismatch at the goto:

$ java Optimizer.java countdown.jar countdown-opt.jar
Error optimizing Countdown.class: Stack size mismatch at bytecode offset 9 of method countdown(int)
  - max stack: 65535
    max locals: 65535
    attributes: []
    //stack map frame @0: {locals: [int], stack: []}
    0: {opcode: ILOAD_0, slot: 0}
    1: {opcode: DUP}
    2: {opcode: ISTORE_1, slot: 1}
    3: {opcode: IFLE, target: 12}
    6: {opcode: IINC, slot: 1, const: -1}
    9: {opcode: GOTO, target: 3}
    12: {opcode: ILOAD_1, slot: 1}
    13: {opcode: IRETURN}

storeLoad: 1

The match is counted before the class fails to write, which is why storeLoad: 1 still appears; the original Countdown.class is copied into the output jar unoptimised.

The listing shows the damage: the goto at offset 9 now targets offset 3, the ifle, and reaching it from the top leaves the dup’s value on the stack while reaching it round the loop leaves nothing.

Our rewrite assumed nothing jumps into the middle of the two instructions it matched.

Basic blocks

That assumption has a name: a basic block is a maximal sequence of instructions that control can only enter at the first instruction, and only leave at the last. Blocks begin at: the method entry, at jump targets and exception handlers, and after a branch. They end at a branch, at a return, or just before the next block begins.

Every rewrite we add will assume something about the stack or the locals in the pattern it matched. Inside a basic block that is safe, because the instructions always run one after the other. Across a boundary it isn’t, so: a peephole match must not cross a basic block boundary.

Our current window matcher gets this for free: a jump target shows up as a pseudo-instruction label, and a label fails every pattern.

Refusing the match is conservative: a match spanning a jump target might be safe, if every jumping path happens to arrive with a compatible stack, but proving that means building a control flow graph and simulating the stack across it. That is exactly the analysis machinery peephole optimisations avoid, so refusing is the cheap, correct answer.

Next steps

As an exercise, try implementing the other rewrites as peepholes of their own: removing iload x; istore x, and turning istore x; istore x into pop; istore x. Then try generalising all three beyond int: long and double values occupy two stack slots, so the dup becomes a dup2 and the pop becomes a pop2.

If you haven’t already read them, check out the related posts: