A first example

As a first example of what we can do, consider the following simple (and not very useful) Java class:

   public class test {
   
       public void f(int i) {
           switch ( i ) {
           case 1 :
               System.out.println("Hello, world") ;
               break ;
           }
       }
   }

If this code is saved in the file test.java it can be compiled to give the class file test.class:

   javac test.java

To disassemble the class file we need to run D-Java:

   D-Java -o jasmin -n lvt -n lnt test.class >test.j

The flag -o jasmin tells D-Java to use Jasmin format for its output. The -n lvt and -n lnt flags prevent any debug information that might be in the class file from being written to the output. Since the aim is to produce optimised code we don't want to have it bloated with debug data. Also, the presence of the .line directives complicates the pattern matching required to detect candidates for optimisation.

The output of the disassembly is in the file test.j:

   ;>> test.class <<
   ;
   ; Output created by D-Java (Feb 18 1998)
   ; mailto:umsilve1@cc.umanitoba.ca
   ; Copyright (c) 1996-1997 Shawn Silverman
   ;

   ;Classfile version:
   ;    Major: 45
   ;    Minor: 3

   .source test.java
   .class  public test
   .super  java/lang/Object
   
   ; >> METHOD 1 <<
   .method public f(I)V
       .limit stack 2
       .limit locals 2
       iload_1
       tableswitch 1  ;high = 1
             Label1
           default : Label2
   Label1:
       getstatic java/lang/System/out Ljava/io/PrintStream;
       ldc "Hello, world"
       invokevirtual java/io/PrintStream/println(Ljava/lang/String;)V
       return
   Label2:
       return
   .end method
   
   ; >> METHOD 2 <<
   .method public <init>()V
       .limit stack 1
       .limit locals 1
       aload_0
       invokespecial java/lang/Object/<init>()V
       return
   .end method

One thing to note here is that there are two methods in the disassembled class file: the method f(), which we wrote, and a default constructor, which was provided by the compiler. Constructors in Java class files always have the special name <init>().

From an optimisation point of view the feature of interest is the last part of f():

       invokevirtual java/io/PrintStream/println(Ljava/lang/String;)V
       return
   Label2:
       return
   .end method

Clearly, the first return statement is superfluous. If we were to remove it we'd save one byte in the new class file. The copt rule to perform this change is:

       return
   Label%1:
       return
   =
   Label%1:
       return

To run the optimiser we use jopt, a simple shell script which runs copt and post-processes the output using awk.

   jopt test.j test.j1

This generates the new file test.j1, where, as expected, we find that the unnecessary return has gone:

       invokevirtual java/io/PrintStream/println(Ljava/lang/String;)V
   Label2:
       return
   .end method

Finally we can generate a new class file by assembling the source in test.j1 as follows:

   jasmin test.j1

For comparison we can also assemble test.j, the assembly language file before optimisation. The file sizes turn out to be:

   Original class file (javac)      468 bytes
   Unoptimised class file (jasmin)  368 bytes
   Optimised class file (jasmin)    367 bytes

Both the files generated by jasmin are considerably smaller than the original file produced by the compiler. This is because the line number table has been removed (due to the -n lnt argument to D-Java). Also, we see that the optimised class file is one byte smaller than the unoptimised one, the difference being the missing return statement.

But it doesn't work in general...

I chose this as the first example because it seemed to be a simple and uncontentious optimisation. However, Kuo Chiang has pointed out that in general this optimisation cannot be applied without further checking. Since such checking is beyond the scope of a simple peephole optimiser, this optimisation isn't included in the rules file.

The Java bytecode verifier checks that the level of the stack is consistent at each point in the program, no matter how that point is reached. In the original example above the second return can only be reached as a result of the jump to Label2. The optimisation means that two routes to the return are possible: falling through from above or a jump to Label2.

In this case the level of the stack at the return is the same, regardless of the route taken. However, it's possible to write assembly language code where this is not the case:

   .method static f(I)V
       .limit stack 2
       .limit locals 1
       iload_0
       iload_0
       ifne Label1
       pop
       return
   Label1:
       return
   .end method

In this example the stack is empty if the first return is reached, but has one item on it if the second is encountered. Removing the first return results in an error from the verifier:

   VERIFIER ERROR test.f(I)V:
   Inconsistent stack height 0 != 1