JVM Compilation Basics

Long ago, seemingly in another life, I wrote about compiling try/catch/finally statements for the JVM. Some people seemed interested in that, but I never followed it up with anything else about compiling to the JVM. Well, better late than never I figure. I’m probably going to attempt to write a series of posts describing how we implement certain Gosu features in terms of bytecode, but before those will make sense to anyone who hasn’t spent quality time with the JVM’s instruction set, I figured it would be worthwhile to go over some basics about what bytecode looks like on the JVM and how one goes about generating classes on the fly.

JVM Basics

As most Java programmers are probably at least vaguely aware, the Java Virtual Machine is a virtualized stack machine with a relatively simple instruction set. Rather than specifying registers as the targets of operations, each instruction operates on the contents of the stack, either pushing or popping elements off the stack as appropriate. Getting a field, for example, will push the value of that field onto the stack, adding two numbers will pop two elements off of the stack, and calling a method will pop off as many elements on the stack as there are arguments to the method (plus one for the this pointer if it’s an instance method) and then push on the result (if the method is non-void). Local variables are stored in numbered virtual registers (more or less), of which there are an unlimited number, and you can store to those register from the stack or load them back to the top of the stack. There are plenty of other details to get into, but that’s the big picture: a stack machine where you push stuff on, pop stuff off, and load/store to virtualized registers as need be.

The instruction set for the JVM is very simple, which is mostly a good thing. Constructs like if statements and loops aren’t present in the bytecode, and instead you need to implement them yourself in terms of GOTOs and conditional branches, which isn’t all that difficult. Features like exceptions and try/catch blocks are baked into the VM, but checked exceptions and finally blocks are entirely constructs of the compiler. (It’s sometimes surprising once you get into things to see the which Java language features have direct support in bytecode and which are essentially implemented by the Java compiler.)

That simplicity means that it’s actually fairly simple to compile to. Most importantly, there’s no real register allocation to worry about, no register spilling, and no stack frame pointer or return pointer to worry about managing. Compilation is essentially just a recursive tree traversal then: to call a method with two arguments, you compile the expression representing the root, compile the expression representing the first argument, compile the expression representing the second argument, and then emit the method call instruction. It doesn’t matter if that first argument is an identifier or a horrifically complicated chain of method calls, because after all the instructions for that expression execute there will be one new value pushed on the stack in the right position. Of course, there are some nasty gotchas in there (the words “bridge method” bring on an involuntary cringe) . . . but the basics at least are straightforward.

Code Generation Tools

Suppose you’re thinking you want to generate classes on the fly. What library should you use to do it? I’ll save you some trouble and say just go download ASM (http://asm.ow2.org/). If you’re serious about writing a compiler, you want something as fast and low-level as possible, and ASM fits the bill: it handles some nasty bits like constant pools, label hookups, and max frame size counting, but otherwise pretty much each method call you make to ASM corresponds directly to a single bytecode instruction. It also includes an awesome Eclipse plugin, which will let you write Java code, compile it, and then view both a pretty-printed view of the bytecode and the ASM calls necessary to generate that bytecode. Playing around like that is by far the best way to learn about how certain constructs can be implemented on the JVM.

Basic Construct #1 – Method Calls

I won’t get into how every Java construct compiles into bytecode, but a couple of examples of some common constructs goes a long way. First up: the trusty method call. All method calls work basically the same way: you push all the arguments onto the stack, with the implied this pointer for an instance method first followed by all the explicit arguments, and then you call one of the method invocation instructions, giving it the name of the class the method is on followed by the method’s signature, which includes the name of the method, the name of all parameter types, and the return type (which is interesting, because the return type is not necessary to uniquely identify the method; I’ve always assumed it was there for the sake of the verifier). In Java, there are actually four different instructions for making method calls: invokevirtual, invokeinterface, invokestatic, and invokespecial. (JDK7 adds in invokedynamic, which is a whole ‘nother topic).

invokevirtual has your standard OO dynamic dispatch behavior, where the method is assumed to be on the class in question or perhaps overridden on a subclass. invokevirtual can only be used for methods on classes and not for interface methods. In implementation terms, an invokevirtual call can be directly mapped to an offset into the class’s vtable, since all subclasses should have the same function signature in that slot. invokeinterface, on the other hand, is used to invoke methods that are defined on interfaces, and it requires a search at execution time through the root object’s classes to look for the method definition. Since the interface could be implemented by many different, unrelated classes, the method isn’t guaranteed to be at the same vtable offset in all those places, so it can’t be linked at class load time or after the first method execution, and instead has to be looked up dynamically. (Of course, once the JIT kicks in, if there’s only one common implementation of an interface, presumably that will all get compiled down along with some guard clauses that never fail, and the performance will presumably be analogous.) Even so, it’s still good practice to use invokevirtual instead of invokeinterface when you have the choice; for example, if you know that an object is an ArrayList and not just a List, you want to compile calls to the get(int) method call as an invokevirtual call against the method defined on ArrayList, not as an invokeinterface call against the method defined on List. In addition, for virtual calls it matters what class you invoke the method against: if you have a method foo() on MySuperClass and overridden on MySubClass, and you then invoke foo() on an instance statically determined to be a MySubClass object, you want to make sure to invoke it as such and use MySubClass as the target in the invoke instruction. Even though the method will dynamically dispatch whether you invoke it against MySuperClass or MySubClass, the verifier and access controller can have different behavior depending on which one you list: for example, if MySuperClass is in the package1 package, MySubClass is in the package2 package, the method is protected, and SomeOtherClass in package2 invokes foo() against a MySubClass instance, that’s legal, but if the invokevirtual call is compiled against MySuperClass, you’ll get an illegal access exception at runtime because SomeOtherClass can’t see protected methods declared on MySuperClass. (Not that we had that exact bug in our compiler at some point or anything . . . what kind of idiots would do that?)

invokestatic is basically exactly what you’d think it is: it statically invokes a method. In that case, there’s no implicit “this” pointer to push on prior to the method call, and no dynamic dispatch happens. The class and method in the instruction is exactly what gets invoked.

invokespecial is used for static dispatch of instance methods. Out of the box, as it were, that’s used in two situations: constructors and super.foo() method calls. Constructors are compiled as instance methods with the special name <init>, but you can’t have the constructor dynamically dispatch to some other method, so the compiler explicitly specifies that the call shouldn’t dynamic dispatch and should go exactly against the class listed. A similar case applies to super.foo() calls; in that case, you’re explicitly stating your intention to invoke a method on the superclass even though it’s overridden on the subclass, so the compiler needs to flag those as statically dispatching.

Basic Construct #2 – If Statements and Other Control Flow Constructs

As I mentioned above, control flow constructs on the JVM are all implemented in terms of conditional branches and gotos. The most basic branch instructions are IFEQ and IFNE which mean, respectively, jump the specified label if the top value on the stack is equal to 0 or not equal to 0 (note that boolean “false” is 0, and any non-zero value is “true.”) There are lots of other options as well, though: the primitive integer relational operators have branch variants, i.e. branch if the element just below the top of the stack is less than the element at the top of the stack. Note that, in the simplest compiler implementation, you’ll basically always use IFEQ and IFNE: since the test for the if statement is an expression, you’ll probably want to compile that expression the same way you would compile it if it were an argument to a method call or an assignment statement, which will leave you with either a 0 or a non-zero value on the stack. Implementing the if construct directly in terms of some of the other conditional branches compacts the bytecode a tiny bit and makes it more readable, but doesn’t affect performance much (if at all) in practice, so for the most part we haven’t bothered implementing that yet in Gosu.

To compile an if-else statement, for example, you essentially do a test on the if condition, and invert it: if the condition is false, skip over the body of the if statement, otherwise fall through and execute the body. If there’s an else block, at the end of the if statement body skip over the else block using a GOTO.

Essentially, to compile:

if (foo) {
  bar();
} else {
  baz();
}

You’ll end up with bytecode that looks like:

. . . push foo on the stack . . .
IFEQ L1
. . . call bar . . .
GOTO L2
L1
 . . . call baz() . . .
L2

So if foo is false, we skip over the call to bar and go to L1, which starts the body of the else statement. After the call to bar from within the if statement, we instead skip to L2, which is after the body of the else statement.

Loop constructs are basically the same thing, with the body of the loop ending with a backwards conditional branch or straight goto back to the start of the loop (depending on the kind of loop and how you decide to implement them).

An Example To Put It Together

To put that all together, here’s more of a full-featured example of how some simple Gosu code compiles down to Java bytecode. (The code in question is for the Josephus microbenchmark as described at http://blog.dhananjaynene.com/2008/07/performance-comparison-c-java-python-ruby-jython-jruby-groovy/).

Here’s the Gosu code for the “GosuPerson” class. It should be straightforward even if you don’t know Gosu:

(Note that the “ as Count,” etc. tokens after the instance variable declarations declare read/write properties to wrap those instance variables, which make down to getCount()/setCount() methods in bytecode).

package gw.internal.gosu.compiler.sample.benchmark.josephus

public class GosuPerson {
  var _count : int as Count
  var _prev : GosuPerson as Prev
  var _next : GosuPerson as Next

  construct( c : int ) {
    _count = c
  }

  function shout( shout : int, deadif : int ) : int {
    if( shout < deadif ) return shout + 1
    Prev.Next = Next
    Next.Prev = Prev
    return 1
  }
}

And here’s what that raw, unadulterated output looks like in ASM’s printout of that class (note that we’re having ASM compute MAXSTACK and MAXLOCAL so our calls to those methods always have an argument value of 0, so that’s what ASM prints out even though that’s not what will end up in the bytecode). See if you can do the mapping from source to bytecode yourself. A couple important hints to keep in mind. First of all, the LOAD/STORE instructions are used to load/store to the virtual registers. Method calls start with their arguments already in the appropriate registers, with the “this” pointer in register 0 followed by all the arguments. Secondly, many bytecode instructions have a prefix of I, F, D, L, or A to indicate what type they operate on: I means integer (i.e. boolean, byte, short, char, or int), F means float, D means double, L means long, and A means Object. Lastly, Object type names in Java start with an L and end with a ; while primitive type names are all single character, with most of the mappings being obvious with the exception of Z, which means “boolean.”.

(Note that our wordpress theme will cut off the right-hand-side of the code listing here, and it’s difficult to wrap it correctly, so if you want to read through the code listing in its entirety I’d suggest selecting all the text, copying, and pasting it into a text editor. My apologies for not taking the time to format this more readably.)

// class version 49.0 (49)
// access flags 33
public class gw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson implements gw/lang/reflect/gs/IGosuClassObject  {

  // compiled from: GosuPerson.gs

  // access flags 0
  I _count

  // access flags 0
  Lgw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson; _prev

  // access flags 0
  Lgw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson; _next

  // access flags 1
  public (I)V
   L0
    ALOAD 0
    INVOKESPECIAL java/lang/Object. ()V
   L1
    LINENUMBER 9 L1
    ALOAD 0
    ILOAD 1
    PUTFIELD gw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson._count : I
   L2
    RETURN
   L3
    LOCALVARIABLE this Lgw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson; L0 L3 0
    LOCALVARIABLE c I L0 L3 1
    MAXSTACK = 0
    MAXLOCALS = 0

  // access flags 1
  public getCount()I
   L0
    ALOAD 0
    GETFIELD gw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson._count : I
    IRETURN
   L1
    LOCALVARIABLE this Lgw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson; L0 L1 0
    MAXSTACK = 0
    MAXLOCALS = 0

  // access flags 1
  public setCount(I)V
   L0
    ALOAD 0
    ILOAD 1
    PUTFIELD gw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson._count : I
   L1
    RETURN
   L2
    LOCALVARIABLE this Lgw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson; L0 L2 0
    LOCALVARIABLE __value_ I L0 L2 1
    MAXSTACK = 0
    MAXLOCALS = 0

  // access flags 1
  public getPrev()Lgw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson;
   L0
    ALOAD 0
    GETFIELD gw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson._prev : Lgw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson;
    ARETURN
   L1
    LOCALVARIABLE this Lgw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson; L0 L1 0
    MAXSTACK = 0
    MAXLOCALS = 0

  // access flags 1
  public setPrev(Lgw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson;)V
   L0
    ALOAD 0
    ALOAD 1
    PUTFIELD gw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson._prev : Lgw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson;
   L1
    RETURN
   L2
    LOCALVARIABLE this Lgw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson; L0 L2 0
    LOCALVARIABLE __value_ Lgw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson; L0 L2 1
    MAXSTACK = 0
    MAXLOCALS = 0

  // access flags 1
  public getNext()Lgw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson;
   L0
    ALOAD 0
    GETFIELD gw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson._next : Lgw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson;
    ARETURN
   L1
    LOCALVARIABLE this Lgw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson; L0 L1 0
    MAXSTACK = 0
    MAXLOCALS = 0

  // access flags 1
  public setNext(Lgw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson;)V
   L0
    ALOAD 0
    ALOAD 1
    PUTFIELD gw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson._next : Lgw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson;
   L1
    RETURN
   L2
    LOCALVARIABLE this Lgw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson; L0 L2 0
    LOCALVARIABLE __value_ Lgw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson; L0 L2 1
    MAXSTACK = 0
    MAXLOCALS = 0

  // access flags 1
  public shout(II)I
   L0
    LINENUMBER 13 L0
    ILOAD 1
    ILOAD 2
    IF_ICMPLT L1
    ICONST_0
    GOTO L2
   L1
    ICONST_1
   L2
    IFEQ L3
   L4
    LINENUMBER 13 L4
    ILOAD 1
    ICONST_1
    IADD
    IRETURN
   L3
   L5
    LINENUMBER 14 L5
    ALOAD 0
    INVOKEVIRTUAL gw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson.getPrev ()Lgw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson;
    ALOAD 0
    INVOKEVIRTUAL gw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson.getNext ()Lgw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson;
    INVOKEVIRTUAL gw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson.setNext (Lgw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson;)V
   L6
    LINENUMBER 15 L6
    ALOAD 0
    INVOKEVIRTUAL gw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson.getNext ()Lgw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson;
    ALOAD 0
    INVOKEVIRTUAL gw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson.getPrev ()Lgw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson;
    INVOKEVIRTUAL gw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson.setPrev (Lgw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson;)V
   L7
    LINENUMBER 16 L7
    ICONST_1
    IRETURN
   L8
    LOCALVARIABLE this Lgw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson; L0 L8 0
    LOCALVARIABLE shout I L0 L8 1
    LOCALVARIABLE deadif I L0 L8 2
    MAXSTACK = 0
    MAXLOCALS = 0

  // access flags 4097
  public getIntrinsicType()Lgw/lang/reflect/IType;
   L0
    ALOAD 0
    INVOKESTATIC gw/internal/gosu/runtime/GosuRuntimeMethods.getType (Ljava/lang/Object;)Lgw/lang/reflect/IType;
    ARETURN
   L1
    LOCALVARIABLE this Lgw/internal/gosu/compiler/sample/benchmark/josephus/GosuPerson; L0 L1 0
    MAXSTACK = 0
    MAXLOCALS = 0

  // access flags 9
  public static $evalAnnotations()Ljava/util/Map;
   L0
    NEW gw/internal/gosu/annotations/AnnotationMap
    DUP
    INVOKESPECIAL gw/internal/gosu/annotations/AnnotationMap. ()V
    ASTORE 0
   L1
    ALOAD 0
    INVOKEVIRTUAL gw/internal/gosu/annotations/AnnotationMap.getAnnotations ()Ljava/util/Map;
    ARETURN
   L2
    LOCALVARIABLE builder Lgw/internal/gosu/annotations/AnnotationMap; L0 L2 0
    MAXSTACK = 0
    MAXLOCALS = 0
}


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s