Shevek (shevek) wrote,
Shevek
shevek

Things you aren't supposed to be able to do in Java

Given a language with a three-operand accessor and/or four-operand assign, for example, range lvalues (e.g. x[y..z] = { 4, 5, 6 }) or runtime access checking (e.g. obj.setGlobal(caller, name, value))), there are two major challenges when compiling for the JVM: Nonvoid assignment and increment.



While we're at it, we'll try to avoid use of an unbounded number of temporaries, or constructing a compiler which has to create callbacks to itself.

Let us define the operands to the assign to be x, y, z and v, consider an example operation to be x[y..z] = v.

Nonvoid assignment needs a dup_x3 without side effects, so we can compile:

compile(x)
compile(y)
compile(z)
compile(v)
dup_x3
assign_range

  x y z v
v x y z
v


Stack offsets have added spaces to make the correspondence easier to read. If you're used to thinking of a dup-type expression as "push a copy onto the top of the stack", it will help to think of it as "insert a copy further down the stack", especially for the dup_xN variants.

The closest I can get to dup_x3 requires an extra hook into the compiler after the assignment, which is not ideal, but do-able:

dup_x3 = dup2_x2 [assign_range] swap pop

    x y z v 
z v x y z v
z v
v z
v


The nonvoid assignment all lives within one routine in the compiler, so this is not really a problem.

Increment requires us to compile something like (conceptually, this is not machine code)
lvalue = x y z
rvalue = x y z; load_range: x y z => v (now the entire stack is x y z v)
add 1
assign


But we can't compile x, y and z twice, since they might have side effects, so we need to be able to turn an lvalue into an rvalue. In a normal 2-value addressing mode, we use dup2, so our 3 value addressing will require a dup3 sequence.

compile(x)
compile(y)
compile(z)
dup3 (duplicate lvalue)
load_range
1; add
assign_range

x y z
x y z x y z
x y z v
x y z v 1
x y z v'


But the JVM does not provide a dup3. We can construct a dup3 sequence, which is not ideal, but works:

dup3 = dup2_x1 pop pop dup_x2 dup_x2 pop dup2_x1

            x y z
        y z x y z 
        y z x
      x y z x 
    x x y z x 
    x x y z 
x y z x y z


The code then compiles as
compile(x)
compile(y)
compile(z)
dup3
compile(value)
assign_range
load_range


although the additional runtime expense is mostly incurred in the extra load_range.

A single temporary N can be used, and I think the fact that the recursive compile() routine is never called while a dup3 sequence is building counts as a proof at a single such temporary will suffice even for nested 4-value assignments

dup3 = astore_N dup2 aload_N dup_x2

x y z
x y
x y x y
x y x y z
x y z x y z


It probably doesn't matter which is used once the hotspot does liveness analysis. Also, I'm not actually sure that any sane language has an increment-like operator with any sort of three-operand addressing mode. 286 assembler doesn't count, that was an accident.

Some of these tricks are quite enjoyable, it's possible to do things like iterating over arrays without a temporary by constructing a rot3 sequence (javac uses three temporaries, again when you hit hotspot, it doesn't matter). Once you get the hang of dealing with lower values first, a lot of things, e.g. the loop iteration trick mentioned below just fall out. Maps are much easier since the Iterator is a single class 1 computational value.

However, this whole system doesn't work in general, because we've assumed throughout that we're using operations designed for class 2 computational values as a form of optimization to manipulate class 1 computational values, and the whole purpose of operations like pop2 and dup2/dup2_XN is to permit us to handle class 2 computational values in the traditional addressing modes. I have not (yet?) been able to extend the solutions above to allow 4 operation assignments where any of x y z or v is a class 2 computational value. It's probably faster and easier in any case to box everything up and/or shell out to a helper routine (which additionally reduces the size of the compiler, and the helper is an earlier candidate for hotspot than the inlined code would be).

Just for laughs:

dup4 = dup2_x2 pop2 dup2_x2 dup2_x2 pop2 dup2_x2


I'm fairly sure dup_x4 and dup5 are impossible. On the whole, the JVM is a lovely machine for doing the things you're meant to do, and much else besides, but one should never be afraid to shell out to a helper routine. The only things that can't be handled by helper routines are flow control and lvalues.

If I ever write on this topic again, I should probably describe how I did automatic class generation for function-expressions, e.g. Function f = ({ $1 + this.getFoo() - $(var) }); f.invoke(4); becomes the bytecode equivalent to:

private static class Inner$1 extends Function {
  private int V_0;
  public Inner$1(Object self, int v0) { super(self); V_0 = v0; }
  public void invoke(Object...) { ... }
}
Function f = new Inner$1(this, var);
f.invoke(...)




References:
http://java.sun.com/docs/books/jvms/second_edition/html/Instructions2.doc3.html

Tags: java
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 2 comments