程序代写代做代考 scheme Bioinformatics flex algorithm file system ant Java Fortran assembler python computer architecture Finite State Automaton AI cache c++ Excel gui asp.net case study c# assembly mips junit x86 jvm interpreter compiler Hive data structure chain Introduction to Compiler Construction in a Java World

branch to topLabel if is true

While we branch on the condition false for the if-then-else statement, we would
branch on the condition true for the do-while statement.

In generating code for a condition, one needs a method of specifying three arguments:

1. The CLEmitter,

2. The target label for the branch, and

3. A boolean flag, onTrue. If onTrue is true, then the branch should be made on the
condition; if false, the branch should be made on the condition’s complement.

Thus, every boolean expression must support a version of codegen() with these three
arguments. For example, consider that for JGreaterThanOp is:

public void codegen(CLEmitter output , String targetLabel ,

boolean onTrue) {

lhs.codegen(output );

rhs.codegen(output );

output.addBranchInstruction(onTrue ? IF_ICMPGT : IF_ICMPLE ,

targetLabel );

}

A method of this sort is invoked on the condition controlling execution; for example, the
following codegen() for JIfStatement makes use of such a method in producing code for
the if-then-else statement.

public void codegen(CLEmitter output) {

String elseLabel = output.createLabel ();

String endLabel = output.createLabel ();

condition.codegen(output , elseLabel , false );

thenPart.codegen(output );

if (elsePart != null) {

output.addBranchInstruction(GOTO , endLabel );

}

output.addLabel(elseLabel );

if (elsePart != null) {

elsePart.codegen(output );

output.addLabel(endLabel );

}

}

Notice that method createLabel() creates a unique label each time it is invoked, and the
addLabel() and addBranchInstruction() methods compute the necessary offsets for the
actual JVM branches.

5Implementing the do-while statement is left as an exercise.

180 An Introduction to Compiler Construction in a Java World

5.3.2 Short-Circuited &&

Consider the logical && operator. In a logical expression like

arg1 && arg2

The semantics of Java, and so of j--, require that the evaluation of such an expression be
short-circuited. That is, if arg1 is false, arg2 is not evaluated; false is returned. If arg1
is true, the value of the entire expression depends on arg2. This can be expressed using
the Java conditional expression, as arg1 ? arg2 : false. How do we generate code for this
operator? The code to be generated depends of whether the branch for the entire expression
is to be made on true, or on false:

Branch to target when Branch to target when

arg1 && arg2 is true: arg1 && arg2 is false:

branch to skip if branch to target if

arg1 is false arg1 is false

branch to target when branch to target if

arg2 is true arg2 is false

skip: ...

For example, the code generated for

if (a > b && b > c) {

c = a;

}

else {

c = b;

}

would be

0: iload_1

1: iload_2

2: if_icmple 15

5: iload_2

6: iload_3

7: if_icmple 15

10: iload_1

11: istore_3

12: goto 17

15: iload_2

16: istore_3

17: ...

The codegen() method in JLogicalAndOp generates the code for the && operator:

public void codegen(CLEmitter output , String targetLabel ,

boolean onTrue) {

if (onTrue) {

String falseLabel = output.createLabel ();

lhs.codegen(output , falseLabel , false );

rhs.codegen(output , targetLabel , true);

output.addLabel(falseLabel );

} else {

lhs.codegen(output , targetLabel , false);

rhs.codegen(output , targetLabel , false);

}

}

JVM Code Generation 181

Notice that our method prevents unnecessary branches to branches. For example, consider
the slightly more complicated condition in

if (a > b && b > c && c > 5) {

c = a;

}

else {

c = b;

}

The JVM code produced for this targets the same exit on false, for each of the && opera-
tions:

0: iload_1

1: iload_2

2: if_icmple 18

5: iload_2

6: iload_3

7: if_icmple 18

10: iload_3

11: iconst_5

12: if_icmple 18

15: iinc 1, -1

18: ...

Branches to branches are avoided even when generating code for a deeply nested and com-
plex Boolean expression because we pass the target through nested recursive calls to this
special version of codegen().

The implementation of a || operator for a short-circuited logical or operation (not yet
in the j-- language) is left as an exercise.

5.3.3 Logical Not !

The code generation for the JLogicalNot operator ! is trivial: a branch on true becomes
a branch on false, and a branch on false becomes a branch on true:

public void codegen(CLEmitter output , String targetLabel ,

boolean onTrue) {

arg.codegen(output , targetLabel , !onTrue );

}

5.4 Generating Code for Message Expressions, Field Selection, and
Array Access Expressions

5.4.1 Message Expressions

Message expressions are what distinguish object-oriented programming languages from the
more traditional programming languages such as C. j--, like Java, is object-oriented.

Much of the work in decoding a message expression is done in analysis. By the time
the compiler has entered the code generation phase, any ambiguous targets have been
reclassified, instance messages have been distinguished from class (static) messages, implicit
targets have been made explicit, and the message’s signature has been determined.

In fact, by examining the target’s type (and if necessary, its sub-types) analysis can

182 An Introduction to Compiler Construction in a Java World

determine whether or not a viable message matching the signature of the message exists. Of
course, for instance messages, the actual message that is invoked cannot be determined until
run-time. That depends on the actual run-time object that is the target of the expression
and so is determined by the JVM. But the code generated for a message expression does
state everything that the compiler can determine.

JMessageExpression’s codegen() proceeds as follows:

1. If the message expression involves an instance message, codegen() generates code for
the target.

2. The message invocation instruction is determined: invokevirtual for instance mes-
sages and invokestatic for static messages.

3. The addMemberAccessInstruction() method is invoked to generate the message in-
vocation instruction; this method takes the following arguments:

(a) The instruction (invokevirtual or invokestatic).

(b) The JVM name for the target’s type.

(c) The message name.

(d) The descriptor of the invoked method, which was determined in analysis.

4. If the message expression is being used as a statement expression and the return type
of the method referred to in (d), and so the type of the message expression itself
is non-void, then method addNoArgInstruction() is invoked for generating a pop
instruction. This is necessary because executing the message expression will produce
a result on top of the stack, and this result is to be thrown away.

For example, the code generated for the message expression

... = s.square (6);

where square is an instance method, would be

aload s’

bipush 6

invokevirtual #6; // Method square :(I)I

Notice this leaves an integer result 36 on the stack. But if the message expression were used
as a statement, as in

s.square (6);

our compiler generates a pop instruction to dispose of the result6:

aload s’

bipush 6

invokevirtual #6; // Method square :(I)I

pop

We invoke static methods using invokestatic instructions. For example, say we wanted to
invoke the static method csquare; the message expression

.. = Square1.csquare (5);

would be translated as

6s’ indicates the stack frame offset for the local variable s.

JVM Code Generation 183

iconst_5

invokestatic #5; // Method csquare :(I)I

If we were to implement interfaces (this is left as an exercise), we would want to generate
the invokeinterface instruction.

5.4.2 Field Selection

When we talk about generating code for a field selection, we are interested in the case where
we want the value7 for the field selection expression. The case where the field selection occurs
as the target of an assignment statement is considered in the next section.

As for message expressions, much of the work in decoding a field selection occurs during
analysis. By the time the code generation phase begins, the compiler has determined all of
what it needs to know to generate code. JFieldSelection’s codegen() works as follows:

1. It generates code for its target. (If the target is a class, no code is generated.)

2. The compiler must again treat the special case a.length where a is an array. As was
noted in the discussion of analysis, this is a language hack. The code generated is also
a hack, making use of the special instruction arraylength.

3. Otherwise, it is treated as a proper field selection. The field selection instruction is
determined: getfield for instance fields and getstatic for static fields.

4. The addMemberAccessInstruction() method is invoked with the following argu-
ments:

(a) The instruction (getfield or getstatic)

(b) The JVM name for the target’s type

(c) The field name

(d) The JVM descriptor for the type of the field, and so the type of the result

For example, given that instanceField is indeed an instance field, the field selection

s.instanceField

would be translated as

aload s’

getfield instanceField:I

On the other hand, for a static field selection such as

Square1.staticField

our compiler would generate

getstatic staticField:I

7Actually, as we shall see in the next section, the field expression’s r-value.

184 An Introduction to Compiler Construction in a Java World

5.4.3 Array Access Expressions

Array access expressions in Java and so in j-- are pretty straightforward. For example, if
the variable a references an array object, and i is an integer, then

a[i]

is an array access expression. The variable a may be replaced by any primary expression
that evaluates to an array object, and i may be replaced by any expression evaluating to
an integer. The JVM code is just as straightforward. For example, if a is an integer array,
then the code produced for the array access expression would be

aload a’

iload i’

iaload

Instruction iaload pops an index i and an (integer) array a off the stack and replaces those
two items by the value for a[i].

In j--, as in Java, multiply dimensioned arrays are implemented as arrays of arrays8.
That is, j-- arrays are vectors.

5.5 Generating Code for Assignment and Similar Operations

5.5.1 Issues in Compiling Assignment

l-values and r-values

Consider a simple assignment statement;

x = y;

It does not seem to say very much; it asks that the value of variable y be stored (as the new
value) in variable x. Notice that we want different values for x and y when interpreting such
an assignment. We often say we want the l-value for x, and the r-value for y. We may think
of a variable’s l-value as its address or location (or in the case of local variables, its stack
frame offset), and we may think of a variable’s r-value as its content or the value stored in
(or, as the value of) the variable. This relationship is illustrated in Figure 5.1.

FIGURE 5.1 A variable’s l-value and r-value.

The names l-value and r-value come from the corresponding positions in the assignment
expression: the left-hand side of the = and the right-hand side of the =. Think of

l-value = r-value

Notice that while all expressions have r-values, many have no l-values. For example, if a is
an array of ten integers and o is an object with field f, C is a class with static field sf, and
x is a local variable, then all of

8Such arrays are known as Illife vectors, after their inventor, John K. Illife.

JVM Code Generation 185

a[3]

o.f

C.sf

x

have both l-values and r-values. That is, any of these may appear on the left-hand side or on
the right-hand side of an assignment operator. On the other hand, while all of the following
have r-values, none has an l-value:

5

x+5

Factorial.factorial (5)

None of these may meaningfully appear on the left-hand side of an assignment statement.
In compiling an assignment, compiling the right-hand side expression to produce code

for computing its r-value and leaving it on the stack is straightforward. But what code must
be generated for the left-hand side? In some cases, no code need be generated; for example,
assuming x and y are local integer variables, then compiling

x = y;

produces

iload y’

istore x’

where x’ and y’ are the stack offsets for x and y, respectively. On the other hand, compiling

a[x] = y;

produces

aload a’

iload x’

iload y’

iastore

This code loads (a reference to) the array a and an index x onto the stack. It then loads the
r-value for y onto the stack. The iastore (integer array store) instruction pops the value
for y, the index x, and the array a from the stack, and it stores y in the element indexed
by x in array a.

Assignment Expressions versus Assignment Statements

Another issue is that an assignment may act as an expression producing a result (on the
stack) or as a statement (syntactically, as a statement expression). That is, we can have

x = y;

or

z = x = y;

In the first case, the assignment x = y; is a statement; no value is left on the stack. But
in the second case, the x = y must assign the value of y to x but also leave a value (the
r-value for y) on the stack so that it may be popped off and assigned to z. That is, the code
might look something like

iload y’

dup

istore x’

istore z’

186 An Introduction to Compiler Construction in a Java World

The dup duplicates the r-value for y on top of the stack so there are two copies. Each of the
istore operations pops a value and stores it in the appropriate variable.

In parsing, when an expression is used as a statement, Parser’s statementExpression
() method sets a flag isStatementExpression in the expression node to true. The code
generation phase can make use of this flag in deciding when code must be produced for
duplicating r-values on the run-time stack.

Additional Assignment-Like Operations

The most important property of the assignment is its side effect. One uses the assignment
operation for its side effect, overwriting a variable’s r-value with another. There are other
Java (and j--) operations having the same sort of side effect. For example,

x--

++x

x += 6

are all expressions that have side effects. But they also denote values. The context in which
they are used determines whether or not we want the value left on the stack, or we simply
want the side effect.

5.5.2 Comparing Left-Hand Sides and Operations

The table below compares the various operations (labeled down the left) with an assortment
of left-hand sides (labeled across the top). We do not deal with string concatenation here,
but leave that to a later section.

JVM Code Generation 187

x a[i] o.f C.sf
lhs = y iload y’

[dup]

istore x’

[dup_x2]

iastore

aload a’

iload i’

iload y’

putfield f

aload o’

iload y

[dup_x1]

iload y’

[dup]

putstatic sf

lhs += y iload x’

iload y’

iadd

[dup]

istore x’

iadd

[dup_x2]

iastore

aload a’

iload i’

dup2

iaload

iload y’

[dup_x1]

putfield f

aload o’

dup

getfield f

iload y’

iadd

getstatic sf

iload y’

iadd

[dup]

putstatic sf

++lhs iinc x’,1

[iload x’]

dup2

iaload

iconst_1

iadd

[dup_x2]

iastore

aload a’

iload i’

getfield f

iconst_1

iadd

[dup_x1]

putfield f

aload o’

dup

iadd

[dup]

putstatic sf

getstatic sf

iconst_1

lhs-- [iload x’]

iinc x’,1

dup2

iaload

[dup_x2]

iconst_1

isub

iastore

aload a’

iload i’

getfield f

[dup_x1]

iconst_1

isub

putfield f

aload o’

dup

iconst_1

isub

putstatic sf

getstatic sf

[dup]

The instructions in brackets [...] must be generated if and only if the operation is a sub-
expression of some other expression, that is, if the operation is not a statement expression.

Notice that there are all sorts of stack instructions for duplicating values and moving
them into various locations on the stack:

dup duplicates the top value on the stack (pushing a copy on top)

dup2 duplicates the top pair of items on the stack (pushing a second pair on top)

dup_x2 duplicates the top value, but copies it below the two items that are below the
original top value

dup_x1 duplicates the top value, but copies it below the single item that is below the
original top value

Figure 5.2 illustrates the effect of each of these. As one might guess, these instructions
were included in the JVM instruction set for just these sorts of operations.

188 An Introduction to Compiler Construction in a Java World

FIGURE 5.2 The effect of various duplication instructions.

The table above suggests that all of this is very complicated, but there is a pattern here,
which we may take advantage of in clarifying what code to generate.

5.5.3 Factoring Assignment-Like Operations

The table above suggests four sub-operations common to most of the assignment-like oper-
ations in j--. They may also be useful if and when we want to extend j-- and when adding
additional operations. These four sub-operations are

1. codegenLoadLhsLvalue() – this generates code to load any up-front data for the
left-hand side of an assignment needed for an eventual store, that is, its l-value.

2. codegenLoadLhsRvalue() – this generates code to load the r-value of the left-hand
side, needed for implementing, for example, the += operator.

3. codegenDuplicateRvalue() – this generates code to duplicate an r-value on the stack
and put it in a place where it will be on top of the stack once the store is executed.

4. codegenStore() – this generates the code necessary to perform the actual store.

The code needed for each of these differs for each potential left-hand side of an assignment:
a simple local variable x, an indexed array element a[i], an instance field o.f, and a static
field C.sf. The code necessary for each of the four operations, and for each left-hand side
form, is illustrated in the table below.

JVM Code Generation 189

x a[i] o.f C.sf
codegenLoadLhsLvalue() [none] aload a’

aload i’

aload o’ [none]

codegenLoadLhsRvalue() iload x’

iaload

dup2

getfield f

dup getstatic sf

codegenDuplicateRvalue() dup dup_x2 dup_x1 dup
codegenStore() istore x’ iastore putfield

f

putstatic sf

Our compiler defines an interface JLhs, which declares four abstract methods for these
four sub-operations. Each of JVariable, JArrayExpression, and JFieldSelection im-
plements JLhs. Of course, one must also be able to generate code for the right-hand side
expression. But codegen() is sufficient for that—indeed, that is its purpose.

For example, JPlusAssignOp’s codegen() makes use of all of these operations:

public void codegen(CLEmitter output) {

((JLhs) lhs). codegenLoadLhsLvalue(output );

if (lhs.type (). equals(Type.STRING )) {

rhs.codegen(output );

} else {

((JLhs) lhs). codegenLoadLhsRvalue(output );

rhs.codegen(output );

output.addNoArgInstruction(IADD);

}

if (! isStatementExpression) {

// Generate code to leave the r-value atop stack

((JLhs) lhs). codegenDuplicateRvalue(output );

}

((JLhs) lhs). codegenStore(output );

}

5.6 Generating Code for String Concatenation

The implementation of most unary and binary operators is straightforward; there is a JVM
instruction for each j-- operation. A case for which this does not apply is string concatena-
tion.

In j--, as in Java, the binary + operator is overloaded. If both of its operands are integers,
it denotes addition. But if either operand is a string then the operator denotes string
concatenation and the result is a string. String concatenation is the only j-- operation
where the operand types don’t have to match9.

The compiler’s analysis phase determines whether or not string concatenation is implied.
When it is, the concatenation is made explicit; that is, the operation’s AST is rewritten,
replacing JAddOp with a JStringConcatenationOp. Also, when x is a string, analysis re-
places

x +=

by

x = x +

9We leave the implementation of other implicit type conversions as an exercise.

190 An Introduction to Compiler Construction in a Java World

So, code generation is left with generating code for only the explicit string concatenation
operation. To implement string concatenation, the compiler generates code to do the fol-
lowing:

1. Create an empty string buffer, that is, a StringBuffer object, and initialize it.

2. Append any operands to that buffer. That StringBuffer’s append() method is over-
loaded to deal with any type makes handling operands of mixed types easy.

3. Invoke the toString() method on the string buffer to produce a String.

JStringConcatenationOp’s codegen() makes use of a helper method nestedCodegen()
for performing only step 2 for any nested string concatenation operations. This eliminates
the instantiation of unnecessary string buffers. For example, given the j-- expression

x + true + "cat" + 0

the compiler generates the following JVM code:

new java/lang/StringBuilder

dup

invokespecial StringBuilder ."":()V

aload x’

invokevirtual append :(Ljava/lang/String ;) StringBuilder;

iconst_1

invokevirtual append :(Z)Ljava/lang/StringBuilder;

ldc "cat"

invokevirtual append :(Ljava/lang/String ;)Ljava/lang/StringBuilder;

iconst_0

invokevirtual append :(I)Ljava/lang/StringBuilder;

invokevirtual StringBuilder.toString :() Ljava/lang/String;

5.7 Generating Code for Casts

Analysis determines both the validity of a cast and the necessary Converter, which encap-
sulates the code generated for the particular cast. Each Converter implements a method
codegen(), which generates any code necessary to the cast. For example, consider the con-
verter for casting a reference type to one of its sub-types; such a cast is called narrowing
and requires that a checkcast instruction be generated:

class NarrowReference implements Converter {

private Type target;

public NarrowReference(Type target) {

this.target = target;

}

public void codegen(CLEmitter output) {

output.addReferenceInstruction(CHECKCAST ,

target.jvmName ());

}

}

On the other hand, when any type is cast to itself (the identity cast), or when a reference
type is cast to one of its super types (called widening), no code need be generated.

JVM Code Generation 191

Casting an int to an Integer is called boxing and requires an invocation of the Integer
.valueOf() method:

invokestatic java/lang/Integer.valueOf :(I)Ljava/lang/Integer;

Casting an Integer to an int is called unboxing and requires an invocation of the
Integer.intValue() method:

invokevirtual java/lang/Integer.intValue :()I

Certain casts, from one primitive type to another, require that a special instruction be
executed. For example, the i2c instruction converts an int to a char. There is a Converter
defined for each valid conversion in j--.

5.8 Further Readings

[Lindholm and Yellin, 1999] is the authoritative reference for the JVM and its instruction
set; Chapter 7 in that text discusses some of the issues in compiling a high-level language
such as Java to the JVM.

An excellent introduction to compiling Microsoft’s R© .NET Common Language Runtime
(CLR) is [Gough and Gough, 2001].

[Strachey, 2000] introduces the notion of l-values and r-values.
A good introduction to the behavior of Java generics—one of our exercises below—

is [Bracha, 2004].

5.9 Exercises

Exercise 5.1. Add interfaces (as a type declaration) to j--. Make any changes that are
necessary to classes and class declarations for accommodating interfaces. Test your imple-
mentation thoroughly.

An interface defines a type that obeys a contract. Declare a variable to be of an interface
type and you can be sure that it will refer to objects that support certain behaviors. Any
class that implements the interface must support those same behaviors. Think of an interface
as a purely abstract class.

From the point of view of analysis, interfaces have all sorts of rules that must be enforced.
Method analyze(), in both JInterfaceDeclaration, and JClassDeclaration is where
most of these rules may be enforced. These rules include

1. Although an interface may have public, protected, or private modifiers, only
public is meaningful for interfaces not nested within other classes.

2. The compiler must also allow the modifiers abstract, static, and strictfp. The
abstract modifier is redundant (as all interfaces are abstract) but the compiler must
allow it. The static modifier has meaning only for member (nested) interfaces. The
strictfp modifier has meaning if and only if one is supporting (float or double)
floating-point arithmetic.

192 An Introduction to Compiler Construction in a Java World

3. An interface may extend any number of (super-) interfaces.

4. A class may implement as many interfaces as it likes. Notice that this will require our
changing the parser’s classDeclaration() method so that it parses an (optional)
implements-clause and stores a (possibly empty) list of interfaces.

5. Every field declaration in an interface is implicitly public, static, and final, but
any of these three modifiers may be present even if unnecessary. Every field must be
initialized. The initializing expression need not be constant and may reference other
fields appearing textually before the reference.

6. The initializing expression in an interface’s field declaration must involve only con-
stants or other static fields.

7. There are rules about the inheritance of fields; see the language specification.

8. Every method declaration in an interface is implicitly public and abstract but either
of these modifiers may be present in the declaration. Because the methods are abstract,
its body is always a semicolon.

9. An interface’s method can never be declared static or final, but class methods
implementing them can be final.

10. There are additional rules governing method inheritance, overriding, and overloading
abstract methods in interfaces; see the language specification.

11. Any class implementing an interface (or a list of interfaces) must implement all of the
methods of the interface(s).

In code generation, there are several facts to consider:

1. In the JVM, an interface is a kind of class. So, just as for a class, one uses CLEmitter’s
addClass() method for introducing an interface.

2. The list of modifiers for the addClass()’s formal parameter accessFlags must include
both interface and abstract. The superClass argument should be the JVM name
for java.lang.Object. Of course, the argument passed for superInterfaces should
be the (possibly empty) list of the super-interfaces (from the extends-clause).

3. The list of modifiers of any field defined by addField() must include public, static,
and final.

4. The list of modifiers of any method defined by addMethod() must include public and
abstract.

5. In invoking a method on an interface, that is, an object declared to be of a type defined
by an interface, one uses the invokeinterface instruction. Although less efficient
than invokevirtual, invokeinterface deals with the possibility of interfaces that
inherited multiple interfaces, and multiple classes implementing the same interface.

Otherwise, use JClassDeclaration as a guide to, and so a starting point for, imple-
menting JInterfaceDeclaration.

Exercise 5.2. Study the Java Language Specification [Gosling et al., 2005] and determine
what must be done to incorporate the final modifier into j--. Add the final modifier to j--,
adding it to your compiler and testing it thoroughly.

JVM Code Generation 193

Exercise 5.3. Add static initializers to j--, adding it to your compiler and testing it thor-
oughly.

A static initializer is a class (or interface) member. It is a block of initializing code that
is executed before the class enclosing it is referenced. It is identified by the static keyword
as in

static {

...

}

The code in the static initializer is executed before the enclosing class is referenced. As such,
the code goes into the method the same place that class field initializations go.
To learn more about static initializers, see Section 8.7 of the Java Language Specification
[Gosling et al., 2005]. The order that fields and static initializers are executed (and so the
order they appear in ) is the order that the members appear in the class; the only
exception to this is “that final class variables and fields of interfaces whose values are
compile-time constants are initialized first.” See Section 12.4.2 of [Gosling et al., 2005].

Rules that static initializers must follow include

1. It is a compile-time error to throw an exception or to return in the initializing code.

2. Static initializers may not refer to this or super.

3. There are restrictions in referring to class variables that are defined textually further
in the code.

Exercise 5.4. Add instance initializers to j--, adding it to your compiler and testing it
thoroughly.

An instance initializer is a block of initializing code that is executed each time an
instance of the enclosing class is instantiated. Therefore, its code goes into the constructors,
that is . Make sure this code is not executed twice, that is, in a constructor whose
code starts off with this().

Rules that instance initializers must follow include

1. It is a compile-time error to throw an exception or to return in the initializing code.

2. Instance initializers may refer to this.

Exercise 5.5. Java permits the declaration of methods of variable arity. For example, one
might declare a method

public void foo(int x, String y, int... z) { }

Invocations of foo require an int value for x, a String value for y, and then any number
(including zero) of ints, all of which are gathered into an implicitly declared integer array
z. Implementing variable arity methods requires declaring the implicit array at method
declaration time, and then gathering the (extra) actual arguments into an array at method
invocation time. Add variable arity methods to j--, adding them to your compiler and testing
them thoroughly.

Exercise 5.6. Add the do-while statement to j--, adding it to your compiler and testing it
thoroughly.

The do-while statement takes the form

do {

Statement

}

while (Test);

194 An Introduction to Compiler Construction in a Java World

The Statement is always executed at least once, and the Test is at the bottom of the loop.
As an example, consider

do {

sum = sum + i;

i = i 1;

} while (i > 0);

The Oracle Java compiler, javac would produce for this:

top: iload sum ’

iload i’

iadd

istore sum ’

iload i’

iconst_1

isub

istore i’

iload i’

ifgt top

Compiling the do-while statement is very much like compiling the while-statement.

Exercise 5.7. Add the classic for-statement to j--, adding it to your compiler and testing
it thoroughly. The classic for-statement may be reformulated as a while-statement, even in
Java. For example, the template

for (Initialization; Test; Increment)

Statement

may be expressed as

Initialization

while (Test) {

Statement;

Increment;

}

We must take into account the fact that either Initialization, Test, or Increment may be
empty, and translate appropriately. This means that the for-statement may be translated
in either of two ways:

1. We can generate JVM code directly, following the patterns illustrated in this chapter.

2. We can first rewrite the AST, replacing the JForStatement node with the block above,
and then apply codegen() to that sub-tree. Notice how the enclosing block captures
the limited scope of any variables declared in Initialization.

Which way is better?

Exercise 5.8. Add the enhanced for-statement to j--, adding it to your compiler and
testing it thoroughly. The Java enhanced for-statement is used to iterate over collections.
Syntactically, it looks something like

for (Type Identifier : Expression)

Statement

How this can be interpreted depends on the type of Expression. If Expression’s type is a
sub-type of Iterable, let I be the type of Expression.iterator(). Then our enhanced
for-statement may be expressed as the following classic for-statement:

JVM Code Generation 195

for (I i’ = Expression.iterator (); i’. hasNext () ;) {

Type Identifier = i’.next ();

Statement

}

The variable i’ is compiler generated in such a way as not to conflict with any other variables.
Otherwise, Expression must have an array type T[]. In this case, our enhanced for- statement
may be expressed as

T[] a’ = Expression;

for (int i’ = 0; i’ < a’. length; i’++) { Type Identifier= a’[i’]; Statement } The variables a’ and i’ are compiler generated in such a way as not to conflict with any other variables. This can be compiled similarly to the classic for- statement. Exercise 5.9. Study the Java Language Specification [Gosling et al., 2005] to determine what it would take to implement the continue-statement in your compiler. Then add the continue-statement to j--, adding them to your compiler and testing it thoroughly. Exercise 5.10. Study the Java Language Specification [Gosling et al., 2005] to determine what it would take to implement the break-statement in your compiler. Then add the break-statement to j--, adding it to your compiler and testing it thoroughly. Exercise 5.11. Add conditional expressions to j--, adding them to your compiler and testing them thoroughly. Conditional expressions are compiled in a manner identical to if-else statements. The only difference is that in this case, both the consequent and the alternative are expressions. For example, consider the assignment z = x > y ? x - y : y - x;

The javac compiler produces the following code for this:

43: iload_1

44: iload_2

45: if_icmple 54

48: iload_1

49: iload_2

50: isub

51: goto 57

54: iload_2

55: iload_1

56: isub

57: istore_3

As for the if-then statement, we compile the Boolean test expression using the 3-argument
version of codegen().

Exercise 5.12. Add the conditional or operator || to j--, adding it to your compiler and
testing it thoroughly. Make sure to avoid unnecessary branches to branches. The conditional
||, like the conditional &&, is short-circuited. That is, in

e1 || e2
if e1 evaluates to true, then e2 is not evaluated and the whole expression is true. For ex-

ample, javac compiles

196 An Introduction to Compiler Construction in a Java World

if (x < 0 || y > 0) {

x = y;

}

to produce

58: iload_1

59: iflt 66

62: iload_2

63: ifle 68

66: iload_2

67: istore_1

68: ...

Exercise 5.13. Write tests that involve conditional branches on nested Boolean expressions
that involve the, !, && and (if you have implemented it) || operator to insure that the
compiler is not generating branches to branches.

Exercise 5.14. Add the switch-statement to j--, adding it to your compiler and testing it
thoroughly.

The switch-statement is more involved than other control constructs. Fortunately, the
JVM provides special support for it. Code generation for the switch-statement is discussed
in Section 6.10 of the JVM specification [Lindholm and Yellin, 1999].

As an example, let us consider a method that makes use of a simple switch-statement.

int digitTight(char c) {

switch (c) {

case ’1’: return 1;

case ’0’: return 0;

case ’2’: return 2;

default: return -1;

}

}

This method converts digit characters ’0’, ’1’, and ’2’ to the integers they denote; any
other character is converted to −1. This is not the best way to do this conversion but it
makes for a simple example of the switch-statement. Let us take a look at the code that
javac produces, using the javap tool:

int digitTight(char);

Code:

Stack=1, Locals=2, Args_size =2

0: iload_1

1: tableswitch{ //48 to 50

48: 30;

49: 28;

50: 32;

default: 34 }

28: iconst_1

29: ireturn

30: iconst_0

31: ireturn

32: iconst_2

33: ireturn

34: iconst_m1

35: ireturn

Notice a few things here. First, the JVM uses a table to map the Unicode character repre-
sentations to the code locations for each of the corresponding cases. For example, 48 (the
Unicode representation for the character ’0’) maps to location 30, the location of the JVM

JVM Code Generation 197

code for the return 0;. Notice also that the characters have been sorted on their Unicode
values: 48, 49, and 50. Finally, because the characters are consecutive, the tableswitch
instruction can simply calculate an offset in the table to obtain the location to which it
wants to branch.

Now consider a second example, where the range of the characters we are switching on
is a little more sparse; that is, the characters are not consecutive, even when sorted.

int digitSparse(char c) {

switch (c) {

case ’4’: return 4;

case ’0’: return 0;

case ’8’: return 8;

default: return -1;

}

}

The code that javac produces for this takes into account this sparseness.

int digitSparse(char);

Code:

Stack=1, Locals=2, Args_size =2

0: iload_1

1: lookupswitch{ //3

48: 38;

52: 36;

56: 40;

default: 43 }

36: iconst_4

37: ireturn

38: iconst_0

39: ireturn

40: bipush 8

42: ireturn

43: iconst_m1

44: ireturn

Again, a table is used, but this time a lookupswitch instruction is used in place of the
previous tableswitch. The table here represents a list of pairs, each mapping a Unicode
representation for a character to a location. Again, the table is sorted on the Unicode
representations but the sequence of characters is too sparse to use the offset technique for
finding the appropriate code location. Rather, lookupswitch searches the table for the
character it is switching on and then branches to the corresponding location. Because the
table is sorted on the characters, a binary search strategy may be used for searching large
tables.

Consider one more example, where the sorted characters are almost but not quite se-
quential:

int digitClose(char c) {

switch (c) {

case ’1’: return 1;

case ’0’: return 0;

case ’3’: return 3;

default: return -1;

}

}

That the range of characters we are switching on is not too sparse suggests our using the
tableswitch instruction, which uses an offset to choose the proper location to branch to.
The javac compiler does just this, as illustrated by the following output provided by the
javap tool.

198 An Introduction to Compiler Construction in a Java World

int digitClose(char);

Code:

Stack=1, Locals=2, Args_size =2

0: iload_1

1: tableswitch{ //48 to 51

48: 34;

49: 32;

50: 38;

51: 36;

default: 38 }

32: iconst_1

33: ireturn

34: iconst_0

35: ireturn

36: iconst_3

37: ireturn

38: iconst_m1

39: ireturn

Notice a sequential table is produced. Of course, the entry for character ’2’ (Unicode 50)
maps to location 38 (the default case) because it is not one of the explicit cases.

So our compiler must construct a list of value-label pairs, mapping a case value to a
label we will emit to mark the location of code to branch to. We then sort that list on
the case values and decide, based on sparseness, whether to use a tableswitch instruction
(not sparse) or a lookupswitch (sparse) instruction. CLEmitter provides a method for each
choice.

CLEmitter’s addTABLESWITCHInstruction() method provides for several arguments: a
default label, a lower bound on the case values, an upper bound on the case values, and
a sequential list of labels.

CLEmitter’s addLOOKUPSWITCHInstruction() method provides for a different set of
arguments: a default label, a count of the number of value-label pairs in the table, and a
TreeMap that maps case values to labels.

Of course, our compiler must decide which of the two instructions to use.

The next three exercises deal with exception handling. Exception handling in Java is
captured by the try-catch-finally and throws-statement. Additionally, there is the throws-
clause, which serves to help the compiler ensure that there is a catch for every exception
thrown.

To illustrate the JVM code that is generated for exceptions, consider the following class
declaration:

import java.io.FileReader;

import java.io.FileWriter;

import java.lang.IndexOutOfBoundsException;

import java.lang.System;

import java.io.FileNotFoundException;

import java.io.IOException;

public class Copy {

private static final int EOF = -1; // end of file character rep.

public static void main(String [] args) throws IOException {

FileReader inStream = null;

FileWriter outStream = null;

int ch;

try {

// open the files

JVM Code Generation 199

inStream = new FileReader(args [0]);

outStream = new FileWriter(args [1]);

// copy

while ((ch = inStream.read ()) != EOF) {

outStream.write(ch);

}

}

catch (IndexOutOfBoundsException e) {

System.err.println(

"usage: java Copy1 sourcefile targetfile ");

}

catch (FileNotFoundException e) {

System.err.println(e); // rely on e’s toString ()

}

catch (IOException e) {

System.err.println(e);

}

finally { // close the files

inStream.close ();

outStream.close ();

}

}

void foo()

throws IOException {

throw new IOException ();

}

}

Notice that the closing of files in the finally-clause might cause an exception to be thrown.
We could either nest this closing of files within its own try-catch block or we could declare
that the method main might possibly throw an IOException. We do the latter here.

Exercise 5.15. Add the throw-statement to j--, adding it to your compiler and testing
it thoroughly. The throw-statement is straightforwardly compiled to JVM code using the
athrow instruction; for example,

throw new IOException ();

produces the following JVM code, which constructs, initializes, and throws the exception
object:

0: new #16; // class java/io/IOException

3: dup

4: invokespecial #17; // method java/io/IOException ."":()V

7: athrow

Exercise 5.16. Add the try-catch-finally-statement to j--, adding it to your compiler and
testing it thoroughly.

Let us look at the code generated by javac for method main() (above):

public static void main(java.lang.String []) throws java.io.IOException;

Code:

Stack=4, Locals=6, Args_size =1

0: aconst_null

1: astore_1

2: aconst_null

3: astore_2

4: new #2; //class java/io/FileReader

7: dup

8: aload_0

200 An Introduction to Compiler Construction in a Java World

9: iconst_0

10: aaload

11: invokespecial #3; // Method java/io/FileReader .""

:(Ljava/lang/String ;)V

14: astore_1

15: new #4; //class java/io/FileWriter

18: dup

19: aload_0

20: iconst_1

21: aaload

22: invokespecial #5; // Method java/io/FileWriter .""

:(Ljava/lang/String ;)V

25: astore_2

26: aload_1

27: invokevirtual #6; // Method java/io/FileReader.read :()I

30: dup

31: istore_3

32: iconst_m1

33: if_icmpeq 44

36: aload_2

37: iload_3

38: invokevirtual #7; // Method java/io/FileWriter.write :(I)V

41: goto 26

44: aload_1

45: invokevirtual #8; // Method java/io/FileReader.close :()V

48: aload_2

49: invokevirtual #9; // Method java/io/FileWriter.close :()V

52: goto 131

55: astore 4

57: getstatic #11; // Field java/lang/System.err:Ljava/io/PrintStream;

60: ldc #12; // String usage: java Copy1 sourcefile targetfile

62: invokevirtual #13; // Method java/io/PrintStream.println:

(Ljava/lang/String ;)V

65: aload_1

66: invokevirtual #8; // Method java/io/FileReader.close :()V

69: aload_2

70: invokevirtual #9; // Method java/io/FileWriter.close :()V

73: goto 131

76: astore 4

78: getstatic #11; // Field java/lang/System.err:Ljava/io/PrintStream;

81: aload 4

83: invokevirtual #15; // Method java/io/PrintStream.println:

(Ljava/lang/Object ;)V

86: aload_1

87: invokevirtual #8; // Method java/io/FileReader.close :()V

90: aload_2

91: invokevirtual #9; // Method java/io/FileWriter.close :()V

94: goto 131

97: astore 4

99: getstatic #11; // Field java/lang/System.err:Ljava/io/PrintStream;

102: aload 4

104: invokevirtual #15; // Method java/io/PrintStream.println:

(Ljava/lang/Object ;)V

107: aload_1

108: invokevirtual #8; // Method java/io/FileReader.close :()V

111: aload_2

112: invokevirtual #9; // Method java/io/FileWriter.close :()V

115: goto 131

118: astore 5

120: aload_1

121: invokevirtual #8; // Method java/io/FileReader.close :()V

124: aload_2

125: invokevirtual #9; // Method java/io/FileWriter.close :()V

128: aload 5

JVM Code Generation 201

130: athrow

131: return

Exception table:

from to target type

4 44 55 Class java/lang/IndexOutOfBoundsException

4 44 76 Class java/io/FileNotFoundException

4 44 97 Class java/io/IOException

4 44 118 any

55 65 118 any

76 86 118 any

97 107 118 any

118 120 118 any

The code for the try block ranges from location 4 up to (but not including location) 44.

4: new #2; //class java/io/FileReader

7: dup

8: aload_0

9: iconst_0

10: aaload

11: invokespecial #3; // Method java/io/FileReader ."":

(Ljava/lang/String ;)V

14: astore_1

15: new #4; //class java/io/FileWriter

18: dup

19: aload_0

20: iconst_1

21: aaload

22: invokespecial #5; // Method java/io/FileWriter ."":

(Ljava/lang/String ;)V

25: astore_2

26: aload_1

27: invokevirtual #6; // Method java/io/FileReader.read :()I

30: dup

31: istore_3

32: iconst_m1

33: if_icmpeq 44

36: aload_2

37: iload_3

38: invokevirtual #7; // Method java/io/FileWriter.write :(I)V

41: goto 26

Much of the exception handling control is specified in the exception table:

from to target type

4 44 55 Class java/lang/IndexOutOfBoundsException

4 44 76 Class java/io/FileNotFoundException

4 44 97 Class java/io/IOException

4 44 118 any

55 65 118 any

76 86 118 any

97 107 118 any

118 120 118 any

The first entry,

4 44 55 Class java/lang/IndexOutOfBoundsException

says that the exception handling applies to locations 4 up to (but not including) 44; con-
trol is transferred to location 55 if and when an exception of the given type (java.lang.
IndexOutOfBoundsException here) is raised. This entry captures the control for the first
catch-clause. Similarly, the next two table entries,

4 44 76 Class java/io/FileNotFoundException

202 An Introduction to Compiler Construction in a Java World

4 44 97 Class java/io/IOException

capture the control for the next two catch-clauses in the source code. The next five entries
in the table

4 44 118 any

55 65 118 any

76 86 118 any

97 107 118 any

118 120 118 any

apply to the try block, the three catch-clauses, and the finally-clause itself. These insure
that if an exception is raised in any of these, the code for the finally-clause is executed:

118: astore 5

120: aload_1

121: invokevirtual #8; // Method java/io/FileReader.close :()V

124: aload_2

125: invokevirtual #9; // Method java/io/FileWriter.close :()V

128: aload 5

130: athrow

Notice copies of the finally-clause code follow the try block and each of the catch-clauses,
insuring that the finally code is always executed10.

Invoke CLEmitter’s addExceptionHandler() method for emitting each entry in the
table. This method uses labels for identifying locations and is discussed in Appendix D
(D.3.2).

Exercise 5.17. Add the throws-clause to j--, adding it to your compiler and testing it
thoroughly. Make sure all the rules of exception handling are covered.

Much of the work here is ensuring that any exception that might be possibly thrown in
the invocation of the method is either caught by a catch-clause in a surrounding try-catch
block, or is covered by one of the exceptions in the throws declaration. See Section 11.2 of
the Java Language Specification [Gosling et al., 2005].

As far as the generated code goes, one needs to ensure that the invocation of the method
for adding a new method,

public void addMethod(ArrayList accessFlags ,

String name ,

String descriptor ,

ArrayList exceptions ,

boolean isSynthetic)

includes a list of the exceptions that the method throws, in internal form.

Exercise 5.18. Modify the Copy class to catch possible exceptions in the finally-clause:

finally { // close the files

try {

if (inStream != null) {

inStream.close ();

}

}

catch (Exception e) {

System.err.println (" Unable to close input stream .");

}

try {

10Another way to handle the finally-clause is to treat it as a subroutine, making use of the JVM’s jsr
and ret instructions. Consult Chapter 7 of [Lindholm and Yellin, 1999] for hints on using these instructions
for exception handling.

JVM Code Generation 203

if (outStream != null) {

outStream.close ();

}

}

catch (Exception e) {

System.err.println (" Unable to close output stream .");

}

}

Execute javap on the class files produced by both javap and by your extensions to j--.
Make sure you are generating the proper JVM code.

Exercise 5.19. Study the Java Language Specification [Gosling et al., 2005] to determine
what it would take to implement the assert-statement in your compiler. Then add the
assert-statement to j--, adding it to your compiler and testing it thoroughly.

The next three exercises involve adding primitive types to our compiler. (There is no
reason why we cannot add built-in reference types such as matrices for which we can overload
the arithmetic operators; but doing so would go against the spirit of Java.) And, because
the primitive types in Java that are not already in j-- are numeric types, the new types
must work in concert with the current types.

Exercise 5.20. Add the primitive type double to j--, adding it to your compiler and test-
ing it thoroughly. Adding double-precision floating-point numbers to j-- introduces several
wrinkles:

1. Arithmetic requires new JVM instructions, for example, dadd.

2. Each double-precision floating-point number occupies two words. This requires that
the offset be incremented by 2 each time a double variable is declared.

3. Mixed arithmetic introduces the need for implicit conversion.

For example, consider the following contrived method, where d and e are double-precision
variables and i is an integer variable:

void foo() {

int i = 4;

double d = 3.0;

double e = 5.0;

e = d * i;

}

The javac compiler produces the following JVM code:

void foo ();

Code:

Stack=4, Locals=6, Args_size =1

0: iconst_4

1: istore_1

2: ldc2_w #2; // double 3.0d

5: dstore_2

6: ldc2_w #4; // double 5.0d

9: dstore 4

11: dload_2

12: iload_1

13: i2d

14: dmul

15: dstore 4

17: return

204 An Introduction to Compiler Construction in a Java World

Notice several things here. First, notice that the stack offsets take account of i being a one-
word int, and d and e being two-word doubles. Second, notice the mix of types an iload
instruction is used to load the integer and a dload instruction is used to load the double-
precision value. The arithmetic is done in double precision, using the dmul instruction.
Therefore, the integer i must be promoted (converted to a more precise representation) to
a double-precision value using the i2d instruction.

In the assignment and arithmetic operations, analyze() must be modified for dealing
with this mixed arithmetic. In the case of a mix of int and double, the rule is pretty simple:
convert the int to a double. One will want to consult the Java Language Specification
[Gosling et al., 2005], especially Chapters 5 and 15. The rules are pretty easy to ferret out
for just ints and doubles.

Exercise 5.21. Add the primitive type long to j--, adding it to your compiler and testing it
thoroughly. When adding additional primitive types (to int and double), the rules become
more complicated. One must worry about when to do conversions and how to do them. One
must follow the Java Language Specification [Gosling et al., 2005].

Once one has more than two numeric types to deal with, it is probably best to re-think
the conversion scheme and build a simple framework for deciding how to promote one type
to another. There are fifteen primitive type conversion instructions available to us in the
JVM, and we will want to make effective use of them.

Exercise 5.22. Add the primitive type float to j--, adding it to your compiler and testing
it thoroughly.

Exercise 5.23. The JVM provides instructions making it relatively straightforward to add
synchronized-statement. Study the Java Language Specification [Gosling et al., 2005] to
determine what it would take to implement the synchronized-statement in your compiler.
Then add the synchronized-statement to j--, adding it to your compiler and testing it
thoroughly.

Exercise 5.24. (Small project) Study the Java Language Specification [Gosling et al., 2005]
to determine what it would take to implement nested classes in your compiler. Then add
nested classes to j--, adding it to your compiler and testing them thoroughly.

In implementing nested classes, one must take into account and enforce both the scope
rules and access rules. The j-- compiler includes a little helpful machinery as it stands, in
the form of a class context entry in the symbol table where nested classes might be stored.

Exercise 5.25. (Small project) Study the Java Language Specification [Gosling et al., 2005]
to determine what it would take to implement enum types in your compiler. Then add enum
types to j--, adding it to your compiler and testing them thoroughly.

The implementation of enum types simply requires enumerating the values supplied in
the type declaration and storing these values along with their enumeration; of course, one
must take into account explicit assignation in the declaration.

Exercise 5.26. (Large project) Study the Java Language Specification [Gosling et al.,
2005] and other articles to determine what it would take to implement generic types in your
compiler. Then add generic types to j--, adding it to your compiler and testing it thoroughly.
Implementing generic types is a major project. Generics are described in [Bracha, 2004].

Exercise 5.27. (Large project) Add implicit type conversions to your implementation of
j--, implementing them in your compiler and testing them thoroughly.

What makes this difficult is that it leads to complexity in the identification and selection
from applicable methods in resolving method invocation. There are hints to an implemen-
tation in the steps outlined in [Gosling et al., 2005].

Chapter 6

Translating JVM Code to MIPS Code

6.1 Introduction

6.1.1 What Happens to JVM Code?

Compilation is not necessarily over with after the class file is constructed. At “execution,”
the class is loaded into the JVM and then interpreted. In the Oracle HotSpotTMVM, once
a method has been executed several times, it is compiled to native code—code that can
be directly executed by the underlying computer. Once these hotspots in the code are
compiled, the native code is cached so that it may be re-used in subsequent invocations of
the method. So at run-time, control shifts back and forth between JVM code and native
code. Of course, the native code runs much faster than the interpreted JVM code. This
regimen takes advantage of the fact that nearly all programs spend most of their time
executing small regions of code.

This scenario is further complicated by the existence of at least two run-time environ-
ments. The VM that runs on a server performs many optimizations on the native code.
While these optimizations are expensive, they produce very fast code that, on a server,
runs over and over again. On the other hand, the VM that runs on a client computer,
such as a user’s personal workstation, performs fewer optimizations and thus minimizes the
one-time cost of compiling the method to native code.

Compiling JVM code to native code involves the following:

Register allocation. In the JVM code, all local variables, transients and instruction
operands are stored on the run-time stack. But the computer architectures we are
compiling to have a fixed number of (often eight or thirty-two) high-speed registers.
The native instructions often require that operands be in registers and permanently
assigning as many local variables and transients to registers makes for faster running
programs. When all registers are in use and the computation requires another, one
register must be spilled to memory. Register spilling, in turn, degrades performance,
so we want to minimize that.

Optimization. The code produced can be improved so as to run faster. In some instances,
invocations of methods having short bodies can be in lined, that is, replaced by the
bodies’ code.

Instruction selection. We must choose and generate the native code instructions suffi-
cient to perform the computations.

Run-time support. A certain amount of functional support is required at run-time. For
example, we need support for creating new objects on the heap. We also implement a
class that gives us basic input and output functionality for testing our programs.

One might reasonably ask, “Why don’t we simply compile the entire JVM program to

205

206 An Introduction to Compiler Construction in a Java World

native code at the very start?” One reason is Java’s dynamic quality means we are not
exactly sure which code will be needed at compile time. Further, new classes may be loaded
while a Java program is executing. That HotSpot compilation can compete with static
compilation in performance is counter-intuitive to programmers. But Oracle has bench-
marks that demonstrate that the HotSpot VM often out-performs programs that have been
statically compiled to native code.

6.1.2 What We Will Do Here, and Why

Here we shall translate a small subset of JVM instructions to the native code for the
MIPS architecture. MIPS is a relatively modern reduced instruction set computer (RISC),
which has a set of simple but fast instructions that operate on values in registers; for this
reason it is often referred to as a register-based architecture—it relies on loads and stores
for moving values between memory and its thirty-two general-purpose registers. The RISC
architecture differs from the traditional complex instruction set computer (CISC), which
has fewer but more complex (and so slower) instructions with a wider range of operand
addressing capabilities; CISC operands can be expressed as registers, memory locations, or
a combination of both (allowing indexing), and so CISC architectures normally have fewer
(for example, eight) general-purpose registers. A popular CISC architecture is Intel’s family
of i86x computers.

More accurately, we will target the MIPS assembly language, which is directly inter-
preted by James Larus’s SPIM simulator [Larus, 2010], and is readily available for many
environments. We call this assembly language SPIM code. (SPIM is MIPS spelled back-
ward.)

Assembly code is a symbolic language for expressing a native code program. It captures
the native code program nicely because there is a one-to-one correspondence between it and
the bit pattern representing each individual instruction but it is more meaningful to the
reader.

Normally, a compiler will produce this assembly code and then use an assembler, i.e., a
simple translator for translating the assembly code to the bit representation of native code.

But the SPIM interpreter interprets the MIPS assembly code directly. This serves our
purpose just fine; we can produce sequences of MIPS instructions that are both readable
and can be executed directly for testing the code we generate.

Our goal here is illustrated in Figure 6.1. The work that we have already done is shown
using the dashed line. The work we intend to do here in this chapter and the next is shown
using the solid line.

FIGURE 6.1 Our j-- to SPIM compiler.

Here we can re-define what constitutes the IR, the front end, and the back end:

• JVM code is our new IR.

• The j-- to JVM translator (discussed in Chapters 1–5) is our new front end.

• The JVM-to-SPIM translator (discussed in this chapter and the next) is our new back
end.

Translating JVM Code to MIPS Code 207

6.1.3 Scope of Our Work

We translate a sufficient subset of the JVM to SPIM code to give the student a taste of
native code generation, some of the possibilities for optimization, and register allocation.
More precisely, we translate enough JVM code to SPIM code to handle the following j--
program1. The class spim.SPIM is a class that we have defined for accessing special SPIM
system routines for doing simple IO.

import spim.SPIM;

// Prints factorial of a number computed using recursive and iterative

// algorithms.

public class Factorial {

// Return the factorial of the given number computed recursively.

public static int computeRec(int n) {

if (n <= 0) { return 1; } else { return n * computeRec(n - 1); } } // Return the factorial of the given number computed iteratively. public static int computeIter(int n) { int result = 1; while ( n > 0 ) {

result = result * n--;

}

return result;

}

// Entry point; print factorial of a number computed using

// recursive and iterative algorithms.

public static void main(String [] args) {

int n = 7;

SPIM.printInt(Factorial.computeRec(n));

SPIM.printChar (’\n’);

SPIM.printInt(Factorial.computeIter(n));

SPIM.printChar (’\n’);

}

}

We handle static methods, conditional statements, while loops, recursive method invoca-
tions, and enough arithmetic to do a few computations. We must deal with some objects,
for example, constant strings. Although the program above refers to an array, it does not
really do anything with it so we do not implement array objects. Our run-time support is
minimal.

In order to determine just what JVM instructions must be handled, it is worth looking
at the output from running javap on the class file produced for this program.

public class Factorial extends java.lang.Object

minor version: 0

major version: 49

Constant pool:

... ...

{

public Factorial ();

Code:

1We also compile a few more programs, which are included in the code tree but are not discussed further
here: Fibonacci, GCD, Formals, and HelloWorld.

208 An Introduction to Compiler Construction in a Java World

Stack=1, Locals=1, Args_size =1

0: aload_0

1: invokespecial #8; // Method java/lang/Object."":()V

4: return

public static int computeRec(int);

Code:

Stack=3, Locals=1, Args_size =1

0: iload_0

1: iconst_0

2: if_icmpgt 10

5: iconst_1

6: ireturn

7: goto 19

10: iload_0

11: iload_0

12: iconst_1

13: isub

14: invokestatic #13; // Method computeRec :(I)I

17: imul

18: ireturn

19: nop

public static int computeIter(int);

Code:

Stack=2, Locals=2, Args_size =1

0: iconst_1

1: istore_1

2: iload_0

3: iconst_0

4: if_icmple 17

7: iload_1

8: iload_0

9: iinc 0, -1

12: imul

13: istore_1

14: goto 2

17: iload_1

18: ireturn

public static void main(java.lang.String []);

Code:

Stack=1, Locals=2, Args_size =1

0: bipush 7

2: istore_1

3: iload_1

4: invokestatic #13; // Method computeRec :(I)I

7: invokestatic #22; // Method spim/SPIM.printInt :(I)V

10: bipush 10

12: invokestatic #26; // Method spim/SPIM.printChar :(C)V

15: iload_1

16: invokestatic #28; // Method computeIter :(I)I

19: invokestatic #22; // Method spim/SPIM.printInt :(I)V

22: bipush 10

24: invokestatic #26; // Method spim/SPIM.printChar :(C)V

27: return

}

All methods (other than the default constructor) are static; thus, the plethora of
invokestatic instructions. Otherwise, we see lots of loads, stores, a few arithmetic opera-
tions and both conditional and unconditional branches. Translating additional instructions
is left as a set of exercises.

Translating JVM Code to MIPS Code 209

6.2 SPIM and the MIPS Architecture

SPIM and the MIPS computer it simulates are both nicely described by SPIM’s author
in [Larus, 2009]. Our brief description here is based on that.

6.2.1 MIPS Organization

The MIPS computer organization is sketched out in Figure 6.2.

FIGURE 6.2 The MIPS computer organization.

It has an integer central processing unit (CPU), which operates on thirty-two general-
purpose registers (numbered $0–$31); a separate floating- point coprocessor 1 (FPU), with
its own 32 registers ($f0–$f31) for doing single- precision (32-bit) and double- precision (64-
bit) floating point arithmetic, and coprocessor 0 for handling exceptions and interrupts, also
with its own set of registers, including a status register. There are instructions for moving
values from one register set to another. Our translation will focus on the integer-processing
unit; exercises may involve the reader’s dealing with the other coprocessors.

Programming the raw MIPS computer can be quite complicated, given its (time) delayed

210 An Introduction to Compiler Construction in a Java World

branches, delayed loads, caching, and memory latency. Fortunately, the MIPS assembler
models a virtual machine that both hides these timing issues and uses pseudo-instructions
to provide a slightly richer instruction set. By default, SPIM simulates this virtual machine,
although it can be configured to model the more complicated raw MIPS computer. We will
make use of the simpler, default assembly language.

6.2.2 Memory Organization

Memory is, by convention, divided into four segments, as illustrated in Figure 6.3 and
derived from [Larus, 2009].

FIGURE 6.3 SPIM memory organization.

Text segment. The program’s instructions go here, near the bottom end of memory, start-
ing at 400000hex. (The memory location below 400000hex are reserved.)

Static data segment. Static data, which exist for the duration of the program, go here,
starting at 1000000hex. This would be a good place to put constants (including con-
stant strings) and static fields. To access these values conveniently, MIPS designates
one of its thirty-two registers as $gp (register number 28), which points to the middle
of a 64K block data in this segment. Individual memory locations may be addressed
at fixed (positive or negative) offsets from $gp.

Dynamic data segment. Often called the heap, this is where objects and arrays are dy-
namically allocated during execution of the program. Many systems employ a garbage
collection to reclaim the space allocated to objects that are no longer of use. This seg-
ment starts just above the static data segment and grows upward, toward the run-time
stack.

Stack segment. The stack is like that for the JVM. Every time a routine is called, a new
stack frame is pushed onto the stack; every time a return is executed, a frame is
popped off. The stack starts at the top of memory and grows downward toward the
heap. That the dynamic data segment and stack segment start as far apart as possible
and grow toward each other leads to an effective use dynamic memory. We use the

Translating JVM Code to MIPS Code 211

$fp register (30) to point to the current stack frame and the $sp register (29) to point
to the last element on the stack.

MIPS and SPIM require that quantities be aligned on byte addresses that are multiples of
their size; for example, 32-bit words must be at addresses that are multiples of four, and 64-
bit doubles must be at addresses that are multiples of eight. Fortunately, the MIPS assembler
(and thus SPIM) provides program directives for correctly aligning data quantities. For
example, in

b: .byte 10

w: .word 324

the byte 10 is aligned on a byte boundary and may be addressed using the label b, and
the word 324 is aligned on a 4-byte boundary and may be addressed as w; w is guaranteed
to address a word whose address is evenly divisible by 4. There are assembler directives
for denoting and addressing data items of several types in the static data segment. See
Appendix E and [Larus, 2009].

Interestingly, SPIM does not define a byte order for quantities of several bytes; rather,
it adopts the byte order of the machine on which it is running. For example, on an Intel
x86 machine (Windows or Mac OS X on an Intel x86), the order is said to be little-endian,
meaning that the bytes in a word are ordered from right to left. On Sparc or a Power PC
(Solaris or Mac OS X on a Sparc), the order is said to be big-endian, meaning that the
bytes in a word are ordered from left to right. For example, given the directive

w: .byte 0, 1, 2, 3

if we address w as a word, the 0 will appear in the lowest-order byte on a little-endian
machine (as in Figure 6.4(a)) and in the highest order byte on a big-endian machine (as in
Figure 6.4(b)).

FIGURE 6.4 Little-endian versus big-endian.

For most of our work, the endian-ness of our underlying machine on which SPIM is
running should not matter.

6.2.3 Registers

Many of the thirty-two 32-bit general-purpose registers, by convention, are designated for
special uses and have alternative names that remind us of these uses:

$zero (register number 0) always holds the constant 0.

$at (1) is reserved for use by the assembler and should not be used by programmers or in
code generated by compilers.

$v0 and $v1 (2 and 3) are used for expression evaluation and as the results of a function.

$a0 – $a3 (4–7) are used for passing the first four arguments to routines; any additional
arguments are passed on the stack.

212 An Introduction to Compiler Construction in a Java World

$t0 – $t7 (8–15) are meant to hold temporary values that need not be preserved across
routine calls. If they must be preserved, it is up to the caller (the routine making the
call) to save them; hence they are called caller-saved registers.

$s0 – $s7 (16–23) are meant to hold values that must be preserved across routine calls.
It is up to the callee (the routine being called) to save these registers; hence they are
called callee-saved registers.

$t8 and $t9 (24 and 25) are caller-saved temporaries.

$k0 and $k1 (26 and 27) are reserved for use by the operating system kernel and so should
not be used by programmers or in code generated by compilers.

$gp (28) is a global pointer; it points to the middle of a 64K block of memory in the static
data segment.

$sp (29) is the stack pointer, pointing to the last location on the stack.

$fp (30) is the stack frame pointer, pointing to the latest frame on the stack.

$ra (31) is the return address register, holding the address to which execution should
continue upon return from the latest routine.

It is a good idea to follow these conventions when generating code; this allows our code to
cooperate with code produced elsewhere.

6.2.4 Routine Call and Return Convention

SPIM assumes we follow a particular protocol in implementing routine calls when one
routine (the caller) invokes another routine (the callee).

Most bookkeeping for routine invocation is recorded in a stack frame on the run-time
stack segment, much as like is done in the JVM; but here we must also deal with registers.
The stack frame for an invoked (callee) routine is illustrated in Figure 6.5.

SPIM has pretty well defined protocols for preparing for a call in the calling code, making
a call, saving registers in the frame at the start of a method, restoring the saved registers
from the frame at the end of a method, and executing a return to the calling code. We follow
these protocols closely in our run-time stack management and they are described where we
discuss our run-time stack in Section 6.3.5.

6.2.5 Input and Output

The MIPS computer is said to have memory-mapped IO, meaning the input and output
device registers are referred to as special, reserved addresses in memory. Although SPIM
does simulate this for a simple console, it also provides a set of system calls for accessing
simple input and output functions. We shall use these system calls for our work.

Translating JVM Code to MIPS Code 213

FIGURE 6.5 A stack frame.

6.3 Our Translator

6.3.1 Organization of Our Translator

Our JVM-to-SPIM translator is based on those described by Christian Wimmer [Wimmer,
2004] and Hanspeter Mössenböck [Mössenböck, 2000], which are in turn versions of the Sun
(now Oracle) HotSpot Client Compiler. Our translator differs in several ways from those
described by Wimmer and Mössenböck, and while theirs produce native code for the Intel
86x, ours targets SPIM, a simulator for the MIPS32 architecture.

Roughly, the phases proceed as illustrated in Figure 6.6.
In the first phase, the JVM code is parsed and translated to a control-flow graph,

composed of basic blocks. A basic block consists of a linear sequence of instructions with
just one entry point at the start of the block, and one exit point at the end; otherwise, there
are no branches into or out of the block. The instructions are of a high level and preserve
the tree structure of expressions; following Wimmer, we call this a high-level intermediate
representation (HIR). Organizing the code in this way makes it more amenable to analysis.

In the second (optional) phase, various optimizations may be applied to improve the
code, making it faster and often smaller.

In the third phase, a lower-level representation of the code is constructed, assigning ex-

214 An Introduction to Compiler Construction in a Java World

FIGURE 6.6 Phases of the JVM-to-SPIM translator.

plicit virtual registers to the operands of the instructions; there is no limit to the number
of virtual registers used. Following Wimmer, we call this a low-level intermediate represen-
tation (LIR). The instructions are very close to the instructions in our target instruction
set, SPIM.

In the fourth phase, we perform register allocation. The thirty-two physical registers in
the MIPS architecture (and thus in SPIM) are assigned to take the place of virtual registers.
Register allocation is discussed in Chapter 7.

In the fifth and final phase, we generate SPIM code—our goal.
The names of all classes participating in the translation from JVM code to SPIM code

begin with the letter N (the N stands for Native). The translation is directed by the driver,
NEmitter; most of the steps are directed by its constructor NEmitter().

NEmitter() iterates through the classes and methods for each class, constructing the
control-flow graph of HIR instructions for each method, doing any optimizations, rewriting
the HIR as LIR and performing register allocation.

SPIM code is emitted by the driver (Main or JavaCCMain) using NEmitter’s write()
method.

6.3.2 HIR Control-Flow Graph

The Control-Flow Graph

The first step is to scan through the JVM instructions and construct a flow graph of basic
blocks. A basic block is a sequence of instructions with just one entry point at the start and
one exit point at the end; otherwise, there are no branches into or out of the instruction
sequence.

To see what happens here, consider the JVM code for the method computeIter() from
our Factorial example:

public static int computeIter(int);

Code:

Stack=2, Locals=2, Args_size =1

0: const_1

1: istore_1

2: iload_0

3: iconst_0

Translating JVM Code to MIPS Code 215

4: if_icmple 17

7: iload_1

8: iload_0

9: iinc 0, -1

12: imul

13: istore_1

14: goto 2

17: iload_1

18: ireturn

We have inserted line breaks to delineate basic blocks. The entry point is the iconst_1
instruction at location 0 so that begins a basic block; let us call it B1. The iload_0 at
location 2 is the target of the goto instruction (at 14) so that also must start a basic block;
we call it B2. B2 extends through the if_icmple instruction; the block must end there
because it is a branch. The next basic block (B3) begins at location 7 and extends to the
goto at location 14. Finally, the iload_1 at location 17 is the target of the if_icmple
branch at location 4 so it starts basic block B4. B4 extends to the end of the method and
is terminated by the ireturn instruction.

The control-flow graph, expressed as a graph constructed from these basic blocks is
illustrated in Figure 6.7; we have added an extra special entry block B0, for making further
analysis simpler. The boxes represent the basic blocks and the arrows indicate the flow of
control among the blocks; indeed, all control flow information is captured in the graph.
Notice that the boxes and arrows are not really necessary to follow the flow of control
among blocks; we put them there in the figure only for emphasis. You will notice that the
first line of text within each box identifies the block, a list of any successor blocks (labeled
by succ:) and a list of any predecessor blocks (labeled by pred:). For example, block B3
has a predecessor B2 indicating that control flows from the end of block B2 into the start
of B3; B3 also has a successor B2 indicating that control flows from the end of B3 to the
start of block B3. We add an extra beginning block B0 for the method’s entry point.

The denotation [LH] on the first line of B2 indicates that B2 is a loop header—the first
block in a loop. The denotation [LT] on the first line of B3 indicates that B3 is a loop
tail—the last block in a loop (and a predecessor of the loop header). This information is
used later in identifying loops for performing optimizations and ordering blocks for optimal
register allocation.

The pairs of numbers within square brackets, for example [7, 14] on the first line of
B3, denote the ranges of JVM instructions captured in the block.

The keyword dom: labels the basic block’s immediate dominator. In our graph, a node d
is said to dominate a node n if every path from the entry node (B0) to n must go through
d. A node d strictly dominates n if it dominates n but is not the same as n. Finally, node d
is an immediate dominator of node n if d strictly dominates n but does not dominate any
other node that strictly dominates n. That is, it is the node on the path from the entry node
to n that is the “closest” to n. Dominators are useful for certain optimizations, including
the lifting of loop-invariant code (see Section 6.3.3).

The State Vector

Local variables are tracked in a state vector called locals and are indexed in this vector
by their location in the JVM stack frame. The current state of this vector at the end of a
block’s instruction sequence is printed on the block’s second line and labeled with Locals:.
The values are listed in positional order and each value is represented by the instruction id
for the instruction that computes it.

For example, in B0 this vector has just one element, corresponding to the method’s

216 An Introduction to Compiler Construction in a Java World

FIGURE 6.7 HIR flow graph for Factorial.computeIter().

formal argument n. I0 identifies the instruction LDLOC 0 that loads the value (for n) from
position 0 on the stack2; notice the instruction is typed to be integer by the I in I0. In B1,
the vector has two elements: the first is I0 for n and the second is I2 for result.

HIR Instructions

The instruction sequence within each basic block is of a higher level than is JVM code.
These sequences capture the expression trees from the original source. We follow [Wimmer,

2The argument actually will be in register $a0 in the SPIM code, following SPIM convention.

Translating JVM Code to MIPS Code 217

2004] in calling this a high-level intermediate representation (HIR). For example, the Java
statement

w = x + y + z;

might be represented in HIR by

I8: I0 + I1

I9: I8 + I2

The I0, I1, and I2 refer to the instruction ids labeling instructions that compute values for
x, y and z, respectively. So the instruction labeled I8 computes the sum of the values for
x and y, and then the instruction labeled I9 sums that with the value for z to produce a
value for w. Think of this as an abstract syntax tree such as that illustrated in Figure 6.8.
The I is a type label, indicating the type is (in this case) an integer.

FIGURE 6.8 (HIR) AST for w = x + y + z.

The instruction for loading a constant is simply the constant itself. For example, consider
block B1 in Figure 6.7. It has just the single instruction

I2: 1

which is to say, the temporary I2 (later, I2 will be allocated a register) is loaded with the
constant 1. 1 is that instruction that loads the constant 1.

Not all instructions generate values. For example, the instruction

6: if I3 <= I5 then B4 else B3 in block B2 produces no value but transfers control to either B4 or B3. Of course, the 6: has no type associated with it. As we shall see in Section 6.3.3, HIR lends itself to various optimizations. Static Single Assignment (SSA) Form Our HIR employs static single assignment (SSA) form, where for every variable, there is just one place in the method where that variable is assigned a value. This means that when a variable is re-assigned in the method, one must create a new version for it. For example, given the simple sequence x = 3; x = x + y; the second assignment to x requires that we create a new version. For example, we might subscript our variables to distinguish different versions. 218 An Introduction to Compiler Construction in a Java World x1 = 3; x1 = x1 + y1; In the HIR, we represent a variable’s value by the instruction that computed it and we track these values in the state vector. The value in a state vector’s element may change as we sequence through the block’s instructions. If the next block has just one predecessor, it can copy the predecessor’s state vector at its start; if there are more than two predecessors, the states must be merged. For example, consider the following j-- method, where the variables are in SSA form. static int ssa(int w1) { if (w1 > 0) {

w2 = 1;

}

else {

w3 = 2;

}

return w?;

}

In the statement,

return w?;

which w do we return, w2 or w3? Well, it depends on which of the two paths is taken through
the if-then-else statement. In terms of basic blocks, it is as illustrated in Figure 6.9.

FIGURE 6.9 The SSA merge problem.

We solve this problem using what is called a Phi function, a special HIR instruction
that captures the possibility of a variable having one of several values. In our example, the
final block would contain the following code.

w4 = [w2 w3];
return w4;

The [w2 w3] represents a Phi function with two operands: the operand w2 captures the
possibility that one branch of the if-then-else was taken and the w3 captures the possibility
that the other branch was taken. Of course, the target SPIM has no representation for
this but we shall remove these special Phi instructions before attempting to generate SPIM
instructions. We can still do analysis on it. The data flow is illustrated in Figure 6.10.

Translating JVM Code to MIPS Code 219

FIGURE 6.10 Phi functions solve the SSA merge problem.

Another place where Phi functions are needed are in loop headers. Recall that, a loop
header is a basic block having at least one incoming backward branch and at least two
predecessors, as is illustrated in Figure 6.11.

FIGURE 6.11 Phi functions in loop headers.

Unfortunately, a changed variable flowing in from a backward branch is known only
after the block has been fully processed. For this reason, at loop headers, we conservatively
define Phi functions for all variables and then remove redundant Phi functions later. In the
first instance, w2 can be defined as a Phi function with operands w1 and w2:

w2 = [w1 w2]

Then, when w is later incremented, the second operand may be overwritten by the new w3.

w2 = [w1 w3]

220 An Introduction to Compiler Construction in a Java World

Of course, a redundant Phi function will not be changed. If the w is never modified in the
loop body, the Phi function instruction takes the form

w2 = [w1 w2]

and can be removed as it is apparent that w has not been changed.
Phi functions are tightly bound to state vectors. When a block is processed:

• If the block has just a single predecessor, then it may inherit the state vector of that
predecessor; the states are simply copied.

• If the block has more than one predecessor, then those states in the vectors that differ
must be merged using Phi functions.

• For loop headers we conservatively create Phi functions for all variables, and then
later remove redundant Phi functions.

In block B2 in the code for Factorial (Figure 6.7), I3 and I4 identify the instructions

I3: [ I0 I8 ]

I4: [ I2 I9 ]

These are Phi function instructions capturing the local variable n and result respectively.
I3 is a Phi function with operands I0 and I8; I4 is a Phi function with operands I2 and
I9.

Control-Flow Graph Construction

The best place to look at the translation process is the constructor NEmitter() in class
NEmitter. For each method, the control-flow graph of HIR is constructed in several steps:

1. The NControlFlowGraph constructor is invoked on the method. This produces the
control-flow graph cfg. In this first step, the JVM code is translated to sequences of
tuples:

(a) Objects of type NBasicBlock represent the basic blocks in the control-flow graph.
The control flow is captured by the links successors in each block. There are
also the links predecessors for analysis.

(b) The JVM code is first translated to a list of tuples, corresponding to the JVM
instructions. Each block stores its sequence of tuples in an ArrayList, tuples.
For example, the blocks of tuples for our Factorial example, computeIter()
are as follows:

B0

B1

0: iconst_1

1: istore_1

B2

2: iload_0

3: iconst_0

4: if_icmple 0 13

B3

7: iload_1

8: iload_0

9: iinc 0 255

12: imul

Translating JVM Code to MIPS Code 221

13: istore_1

14: goto 255 244

B4

17: iload_1

18: ireturn

This use of tuples is not strictly necessary but it makes the translation to HIR
easier.

2. The message expression

cfg.detectLoops(cfg.basicBlocks.get(0), null);

detects loop headers and loop tails. This information may be used for lifting invariant
code from loops during the optimization phase and for ordering blocks for register
allocation.

3. The message expression

cfg.removeUnreachableBlocks ();

removes unreachable blocks, for example, blocks resulting from jumps that come after
a return instruction.

4. The message expression,

cfg.computeDominators(cfg.basicBlocks.get(0), null);

computes an immediate dominator for each basic block, that closest predecessor
through which all paths must pass to reach the target block. It is a useful place
to insert invariant code that is lifted out of a loop in optimization.

5. The message expression

cfg.tuplesToHir ();

converts the tuples representation to HIR, stored as a sequence of HIR instructions
in the array list, hir for each block. As the tuples are scanned, their execution is
simulated, using a stack to keep track of newly created values and instruction ids.
The HIR is in SSA form, with (sometimes redundant) Phi function instructions.

6. The message expression

cfg.eliminateRedundantPhiFunctions ();

eliminates unnecessary Phi functions and replaces them with their simpler values as
discussed above.

The HIR is now ready for further analysis.

6.3.3 Simple Optimizations on the HIR

That the HIR is in SSA form makes it amenable to several simple optimizations—
improvements to the HIR code; these improvements make for fewer instructions and/or
faster programs.

Local optimizations are improvements made based on analysis of the linear sequence

222 An Introduction to Compiler Construction in a Java World

of instructions within a basic block. Global optimizations require an analysis of the whole
control graph and involve what is called data-flow analysis3.

One can make important improvements to the code even with analysis within single
basic blocks. Moreover, the SSA form of the HIR allows us to deal with sequences of code
that cross basic block boundaries, as long as we do not deal with those values produced by
Phi functions.

Inlining

The cost of calling a routine (for invoking a method) can be considerable. In addition the
control-flow management and stack frame management, register values must be saved on
the stack. But in certain cases, the code of a callee’s body can replace the call sequence in
the caller’s code, saving the overhead of a routine call. We call this inlining.

Inlining usually makes sense for methods whose only purpose is to access a field as in
getters and setters.

For example, consider the following two methods, defined within a class Getter.

static int getA() {

return Getter.a;

}

static void foo() {

int i;

i = getA ();

}

The a in Getter.a refers to a static field declared in Getter. We can replace the getA()
with the field selection directly:

static void foo() {

int i;

i = Getter.a;

}

Inlining makes sense only when the callee’s code is relatively short. Also, when modeling
a virtual method call, we must be able to determine the routine that should be called at
compile-time. One also should be on the lookout for nested recursive calls; repeated inlining
could go on indefinitely.

A simple strategy for enabling inlining is to keep track of the number of instructions
within the HIR for a method and whether or not that method makes nested calls; this
information can be computed as the HIR for a method is constructed. Inlining method in-
vocations can create further opportunities for inlining. Inlining can also create opportunities
for other optimizations.

Constant Folding and Constant Propagation

Expressions having operands that are both constants, for example,

3 + 4

or even variables whose values are known to be constants, for example,

int i = 3;

int j = 4;

... i + j ...

3We describe a detailed data-flow analysis algorithm for computing liveness intervals for variables as
part of register allocation in Section 7.4.1

Translating JVM Code to MIPS Code 223

can be folded, that is, replaced by their constant value.
For example, consider the Java method

static void foo1() {

int i = 1;

int j = 2;

int k = i + j + 3;

}

and corresponding HIR code

B0 succ: B1

Locals:

0: 0

1: 1

2: 2

B1 [0, 10] dom: B0 pred: B0

Locals:

0: I3

1: I4

2: I7

I3: 1

I4: 2

I5: I3 + I4

I6: 3

I7: I5 + I6

8: return

The instruction I3 + I4 at I5: can be replaced by the constant 3, and the I5 + I6 at
I7: can replaced by the constant 6.

A strategy for implementing is to associate a hash table with each basic block for storing
the constant values associated with instruction ids. As we scan a block’s instructions, an
instruction defining a constant is added to the hash table, keyed by its id. If we come across
an instruction whose operands are already stored in this hash table of constants, we can
perform the operation immediately and store the result in that same table, keyed by the
instruction’s id. This analysis may be carried across basic block boundaries, so long as we
do not store instruction ids for instructions representing Phi functions.

Common Sub-Expression Elimination (CSE) within Basic Blocks

Another optimization one may make is common sub-expression elimination, where we iden-
tify expressions that are re-evaluated even if their operands are unchanged.

For example, consider the following method, unlikely as it may be.

void foo(int i) {

int j = i * i * i;

int k = i * i * i;

}

We can replace

int k = i * i * i;

in foo() with the more efficient

int k = j;

To see how we might recognize common sub-expressions, consider the HIR code for the
original version of foo():.

224 An Introduction to Compiler Construction in a Java World

B0 succ: B1

Locals: I0

I0: LDLOC 0

B1 [0, 12] dom: B0 pred: B0

Locals: I0 I4 I6

I3: I0 * I0

I4: I3 * I0

I5: I0 * I0

I6: I5 * I0

7: return

We sequence through the instructions, registering each in the block’s hash table, indexed
by the instruction and its operand(s); the value stored is the instruction id. As for constant
propagation, we cannot trust values defined by Phi functions without further data-flow
analysis, so we do not register such instructions.

At I6:, the reference to I5 can replaced by I3. More importantly, any subsequent
reference to I6 could be replaced by I4.

Of course, we are not likely to see such a method with such obvious common sub-
expressions. But common sub-expressions do arise in places one might not expect them. For
example, consider the following C Language fragment:

for (i = 0; i < 1000; i++) { for (j = 0; j < 1000; j++) { c[i][j] = a[i][j] + b[i][j]; } } The C compiler represents the matrices as linear byte sequences, one row of elements after another; this is called row major form4. If a, b, and c are integer matrices, and the base address of c is c’, then the byte memory address of c[i][j] is c’ + i * 4 * 1000 + j * 4 The factor i is there because it is the (counting from zero) ith row; the factor 1000 is there because there are 1,000 elements in a row; and the factor 4 is there (twice) because there are 4 bytes in an integer word. Likewise, the addresses of a[i][j] and b[i][j] are a’ + i * 4 * 1000 + j * 4 and b’ + i * 4 * 1000 + j * 4 respectively. So, eliminating the common offsets, i * 4 * 1000 + j * 4 can save us a lot of computation, particularly because the inner loop is executed a million times! But in Java, matrices are not laid out this way. Rather, in the expression a[i][j] the sub-expression a[i] yields an integer array object, call it ai, from which we can index the jth element, ai[j] So, we cannot expect the same savings. On the other hand, the expression a[i] never changes in the inner loop; only the j is being incremented. We say that, within the inner 4In FORTRAN, matrices are stored as a sequence of columns, which is in column major form. Translating JVM Code to MIPS Code 225 loop, the expression a[i] is invariant; that is, it is a loop invariant expression. We deal with these in the next section. And as we shall see below, there is still much to be gained from common sub-expression elimination when it comes to dealing with Java arrays. Lifting Loop Invariant Code Loop invariant expressions can be lifted out of the loop and computed in the predecessor block to the loop header. For example, consider the j-- code for summing the two matrices from the previous section5. int i = 0; while (i <= 999) { int j = 0; while (j <= 999) { c[i][j] = a[i][j] + b[i][j]; j = j + 1;; } i = i + 1; } This can be rewritten as int i = 0; while (i <= 999) { int[] ai = a[i]; int[] bi = b[i]; int[] ci = c[i]; int j = 0; while (j <= 999) { ci[j] = ai[j] + bi[j]; j = j + 1;; } i = i + 1; } Thus, a[i], b[i], and c[i] need be evaluated just 1,000 times instead of 1,000,000 times. This optimization is more difficult than the others. Basically, the expression a[i] is invariant if either 1. i is constant, or 2. All the definitions of i that reach the expression are outside the loop, or 3. Only one definition of i reaches the expression, and the definition is loop invariant. But that the HIR conforms to SSA makes it possible. Any code that is lifted must be lifted to an additional block, which is inserted before the loop header. Invariant expressions can be distinguished from expressions defined within the loop by the fact that they are registered in the hash tables for dominators of the loop header. Both a loop header and its immediate dominator are stored in the blocks. To find previous dominators, one just links back through the block list via the immediate dominator links. Computations involving invariant operands may be moved to the end of a loop header’s immediate dominator block. 5The for-loop is not part of the j-- language so we use the equivalent while-loop notation. If you have implemented for-loops in your compiler by rewriting them as while-loops, then you should produce similar HIR. 226 An Introduction to Compiler Construction in a Java World Array Bounds Check Elimination When indexing an array, we must check that the index is within bounds. For example, in our example of matrix multiplication, in the assignment c[i][j] = a[i][j] + b[i][j]; The i and j must be tested to make sure each is greater than or equal than zero, and less than 1,000. And this must be done for each of c, a, and b. But if we know that a, b, and c are all of like dimensions, then once the check is done for a, it need not be repeated for b and c. Given that the inner loop in our earlier matrix multiplication example is executed one million times, we have saved two million checks! Again, a clever compiler can analyze the context in which the statement c[i][j] = a[i][j] + b[i][j]; is executed (for example, within a nested for-loop) and show that the indices are never out of bounds. When the arrays for a, b and c are created in a loop header’s dominator, this is straightforward; other more complicated control graphs may warrant more extensive data- flow analysis (below). Moreover, an array index operation such as a[i] can be registered in the hash table, ensuring that subsequent occurrences, in the same basic block or in subsequent blocks where the operation is not involved in a Phi function, need not be re- checked. Null Check Elimination Every time we send a message to an object, or access a field of an object, we must insure that the object is not the special null object. For example, in ...a.f... we will want to make sure that a is non-null before computing the offset to the field f. But we may know that a is non-null; for example, we may have already checked it as in the following. ...a.f... ...a.g... ...a.h... Once we have done the null-check for ...a.f... there is no reason to do it again for either a.g or a.h. Again, the ids of checked operands can be stored in the hash tables attached to blocks. If they are found subsequently, they need not be checked again. A Need for Data-Flow Analysis The HIR does not expose every opportunity for optimization, particularly those involving back branches (in loops); for this to happen we would need full data-flow analysis where we compute where in the code computed values remain valid. We use data-flow analysis in Section 7.4.1 to compute such liveness intervals for virtual registers (variables) in the LIR as a prerequisite to register allocation; look there for a detailed data-flow analysis algorithm. On the other hand, the HIR does expose many opportunities for optimization, partic- ularly for the effort involved. The amount of code improvement achieved in proportion to the time spent is important in a just-in-time (or hot spot) compiler such as we use for processing JVM code. Translating JVM Code to MIPS Code 227 A full discussion of compiler optimization is outside the scope of this text; see the Further Readings section (Section 6.4) at the end of this chapter for detailed discussions of code optimization techniques. Summary At a panel discussion on compiler optimization, Kathleen Knobe observed that, rather than to put all of one’s efforts into just one or two optimizations, it is best to attempt all of them, even if they cannot be done perfectly. We have not implemented any of these optimizations, but leave them as exercises. Of course, one of the best optimizations one can make is to replace references to local variables with references to registers by allocating registers for holding local variable values. We discuss register allocation in Chapter 7. 6.3.4 Low-Level Intermediate Representation (LIR) The HIR lends itself to optimization but is not necessarily suitable for register allocation. For this reason we translate it into a low-level intermediate representation (LIR) where • Phi functions are removed from the code and replaced by explicit moves, and • Instruction operands are expressed as explicit virtual registers. For example, the LIR for Factorial.computeIter() is given below; notice that we retain the control-flow graph from the HIR. Notice also that we have allocated virtual registers to the computation. One may have an arbitrary number of virtual registers. In register allocation, we shall map these virtual registers to actual physical registers on the MIPS architecture. Because there might be many more virtual registers than physical registers, the mapping may require that some physical registers be spilled to stack locations and reloaded when the spilled values are needed again. Notice that each instruction is addressed at a location that is a multiple of five; this leaves room for spills and loads (at intervening locations). computeIter (I)I B0 B1 0: LDC [1] [V32|I] 5: MOVE $a0 [V33|I] 10: MOVE [V32|I] [V34|I] B2 15: LDC [0] [V35|I] 20: BRANCH [LE] [V33|I] [V35|I] B4 B3 25: LDC [-1] [V36|I] 30: ADD [V33|I] [V36|I] [V37|I] 35: MUL [V34|I] [V33|I] [V38|I] 40: MOVE [V38|I] [V34|I] 45: MOVE [V37|I] [V33|I] 50: BRANCH B2 B4 55: MOVE [V34|I] $v0 60: RETURN $v0 228 An Introduction to Compiler Construction in a Java World In this case, seven virtual registers V32–V38 are allocated to the LIR computation. Two physical registers, $a0 for the argument n and $v0 for the return value, are referred to by their symbolic names; that we use these physical registers indicates that SPIM expects values to be stored in them. Notice that LIR instructions are read from left to right. For example, the load constant instruction 0: LDC [1] [V32|I] in block B1, loads the constant integer 1 into the integer virtual register V32; the |I notation types the virtual register as an integer. Notice that we start enumerating virtual registers beginning at 32; the numbers 0 through 31 are reserved for enumerating physical registers. The next instruction, 5: MOVE $a0 [V33|I] copies the value from the integer physical register $a0 into the integer virtual register V33. The add instruction in block B3, 30: ADD [V33|I] [V36|I] [V37|I] adds the integer values from registers V33 and V36 and puts the sum in V37. Notice that we enumerate the LIR instructions by multiples of five. This eases the insertion of spill (and restore) instructions, which may be required for register allocation (and are discussed in Chapter 7). The process of translating HIR to LIR is relatively straightforward and is a two-step process. 1. First, the NEmitter constructor invokes the NControlFlowGraph method hirToLir() on the control-flow graph: cfg.hirToLir (); The method hitToLir() iterates through the array of HIR instructions for the control- flow graph translating each to an LIR instruction, relying on a method toLir(), which is defined for each HIR instruction. 2. NEmitter invokes the NControlFlowGraph method resolvePhiFunctions() on the control-flow graph: cfg.resolvePhiFunctions (); This method resolves Phi function instructions, replacing them by move instructions near the end of the predecessor blocks. For example, the Phi function from Figure 6.10 and now repeated in Figure 6.12(a) resolves to the moves in Figure 6.12(b). One must make sure to place any move instructions before any branches in the predecessor blocks. Translating JVM Code to MIPS Code 229 FIGURE 6.12 Resolving Phi functions. 6.3.5 Simple Run-Time Environment Introduction An actual run-time environment supporting code produced for Java would require: 1. A naming convention. 2. A run-time stack. 3. A representation for arrays and objects. 4. A heap, that is, an area of memory from which arrays and objects may be dynamically allocated. The heap should offer some sort of garbage collection, making objects that are no longer in use available for (re-)allocation. 5. A run-time library of code that supports the Java API. To do all of this here would be beyond the scope of this text. Given that our goal is to have a taste of native code generation, including register allocation, we do much less. We implement just enough of the run-time environment for supporting our running the Factorial example (and a few more examples, which are included in our code tree). Naming Convention We use a simple naming mechanism that takes account of just classes and their members. Methods are represented in SPIM by routines with assembly language names of the form ., where names a method in a class . For example, the
computeIter() method in class Factorial would have the entry point

Factorial.computeIter:

Static fields are similarly named; for example, a static integer field staticIntField in class
Factorial would translate to SPIM assembly language as

Factorial.staticIntField: .word 0

String literals in the data segment have labels that suggest what they label, for example,
Constant..String1:.

230 An Introduction to Compiler Construction in a Java World

Run-Time Stack

Our run-time stack conforms to the run-time convention described for SPIM in [Larus,
2009] and our Section 6.2.4. Each time a method is invoked, a new stack frame of the type
illustrated in Figure 6.5 is pushed onto the stack. Upon return from the method, the same
frame is popped off the stack.

When the caller wants to invoke a callee, it does the following:

1. Argument passing. The first four arguments are passed in registers $a0 to $a3. Any
additional arguments are pushed onto the stack and thus will appear at the beginning
of the callee’s stack frame.

2. Caller-saved registers. Registers $a0 to $a3 and $t0 to $t9 can be used by the callee
without its having to save their values, so it is up to the caller to save any registers
whose values it expects to use after the call, within its own stack frame before executing
the call.

3. Executing the call. After arguments have passed and caller registers have been saved,
we execute the jal instruction, which jumps to the callee’s first instruction and saves
the return address in register $ra.

Once a routine (the callee) has been invoked, it must first do the following:

1. Push stack frame. Allocate memory for its new stack frame by subtracting the frame’s
size from the stack pointer $sp. (Recall, the stack grows downward in memory.)

2. Callee-saved registers. The callee must save any of $s0 to $s7, $fp, and $ra before
altering any of them because the caller expects their values will be preserved. We
must always save $fp. $ra must be saved only if the callee invokes another routine.

3. The frame pointer. The new $fp = $sp + stack frame size − 4.

The stack frame for an invoked (callee) routine is illustrated in Figure 6.13.
Once it has done its work, the callee returns control to the caller by doing the following:

1. Return value. If the callee returns a value, it must put that value in register $0.

2. Callee-saved registers. All callee-saved registers that were saved at the start of the
routine are restored.

3. Stack frame. The stack frame is popped from the stack, restoring register $fp from its
saved location in the frame, and adding the frame size to register $sp.

4. Return. Execute the return instruction, which causes a jump to the address in register
$ra.

A Layout for Objects

Although we mean only to support static methods, objects do leak into our implementation.
For example, method main() takes as its sole argument an array of strings.

Although, we do not really support objects, doing so need not be difficult. [Corliss and
Lewis, 2007]) propose layouts, which we use here. For example, an arbitrary object might
be organized as in Figure 6.14.

Translating JVM Code to MIPS Code 231

FIGURE 6.13 A stack frame.

FIGURE 6.14 Layout for an object.

The type tag identifies the type (that is, the class) of the object. The size in bytes is the
number of bytes that must be allocated to represent the object; this number is rounded up
to a multiple of 4 so that objects begin on word boundaries. The dispatch table pointer is
the address of a dispatch table, which contains the address of each method for the object’s
class.

The dispatch table may be allocated in the data segment and keeps track of both in-
herited and defined methods. When code is generated for the class, entries in the table are
first copied from the superclass. Then entries for newly defined method are added; over-
riding method entries replace the overridden entries in the table and other method entries
are simply added at the end. Entries are added in the order they are declared in the class
declaration. In this way, the dispatch table for a class keeps track of the proper (inherited,
overriding, or newly defined) methods that are applicable to each class. A dispatch table
for class may be labeled (and addressed) in the data segment using the name

232 An Introduction to Compiler Construction in a Java World

.. Dispatch:

The double period distinguishes this name from a method named Dispatch().
The order of fields in an object is also important because a class inherits fields from a

superclass. In constructing the format of an object, first any inherited fields are allocated.
Then any newly defined fields are allocated. Java semantics require that space is allocated to
all newly defined fields, even those with the same names as inherited fields; the “overridden”
fields can are always available through casting an object to its superclass.

For each class, we also maintain a class template in the data segment, which among
other things may include a typical copy of an object of that class that can be copied to the
heap during allocation. We name this

.. Template:

For example, consider the following j-- code, which defines two classes: Foo and Bar.

public class Foo {

int field1 = 1;

int field2 = 2;

int f() {

return field1 + field2;

}

int foo() {

return field1;

}

}

class Bar extends Foo {

int field3 = 3;

int field1 = 4;

int f() {

return field1 + field2 + field3;

}

int bar() {

return field1;

}

}

Consider an object of class Foo, illustrated in Figure 6.15.

Translating JVM Code to MIPS Code 233

FIGURE 6.15 Layout and dispatch table for Foo.

Assuming the type tag for Foo is 46,

Foo..Tag: .word 4

The SPIM code for a template for Foo might look like

Foo.. Template:

.word Foo..Tag

.word 20

.word Foo.. Dispatch

.word 0

.word 0

The fields have initial values of zero. It is the responsibility of the routine for Foo
to initialize them to 1 and 2, respectively.

The construction of the dispatch table for Foo follows these steps:

1. First the methods for Foo’s superclass (Object) are copied into the table. (Here we as-
sume we have given Object just the three methods clone(), equals() and toString
()).

2. Then we add the methods defined in Foo to the dispatch table: f() and foo().

The SPIM code for this dispatch table might look something like the following:

Foo.. Dispatch:

.word 5 # the number of entries in our table

.word Object.clone

.word Object.equals

.word Object.toString

.word Foo.f

.word Foo.foo

6This assumes that, 1 represents a string, 2 represents an array, and 3 represents an Object.

234 An Introduction to Compiler Construction in a Java World

The layout and dispatch table for class Bar, which extends class Foo, is illustrated in Figure
6.16.

FIGURE 6.16 Layout and dispatch table for Bar.

Assuming the type tag for Bar is 5,

Bar..Tag: .word 5

The SPIM code for a template for Bar might look like

Bar.. Template:

.word Bar..Tag

.word 28

.word Bar.. Dispatch

.word 0

.word 0

.word 0

.word 0

Again, the fields have initial values of zero. It is the responsibility of the routine for
Foo and Bar to initialize them to 1,2, 3, and 4, respectively.

The construction of the dispatch table for Bar follows these steps:

1. First the methods for Bar’s superclass (Foo) are copied into the table.

2. Then we add the methods defined in Bar to the dispatch table. The method Bar.f()
overrides, and so replaces Foo.f() in the table; the new Bar.bar() is simply added
to the table.

The SPIM code for this dispatch table might look something like the following:

Translating JVM Code to MIPS Code 235

Bar.. Dispatch:

.word 6 # the number of entries in our table

.word Object.clone

.word Object.equals

.word Object.toString

.word Bar.f

.word Foo.foo

.word Bar.bar

Arrays are a special kind of object; they are dynamically allocated on the heap but lie
outside the Object hierarchy. A possible layout for an array is illustrated in Figure 6.17.

FIGURE 6.17 Layout for an array.

Arrays have a type tag of 1. The size in bytes is the size of the array object in bytes,
that is, 12 + n ∗ bytes, where n is the number of elements in the array and bytes is the
number of bytes in each element. The array length is the number of elements in the array;
any implementation of the JVM arraylength instruction must compute this value. The
array elements follow. The size of the array object should be rounded up to a multiple of
4 to make sure the next object is word aligned. Notice that an array indexing expression
a[i] would translate to the heap address a + 12 + i ∗ bytes, where a is the address of the
array object on the heap and bytes is the number of bytes in a single element.

Strings are also special objects; while they are part of the Object hierarchy, they are
final and so they may not be sub-classed. This means we can do without a dispatch table
pointer in string objects; we can maintain one dispatch table for all string operations:

String .. Dispatch:

.word m # m is the number of entries in the table

.word String.clone

.word String.equals

.word String.toString

... addresses of methods for Strings ...

Which String methods we implement is arbitrary and is left as an exercise.
A possible layout for a string is illustrated in Figure 6.18.

FIGURE 6.18 Layout for a string.

The type tag for a string is 2. Its size in bytes is the number of bytes that must be
allocated to represent the string object; it is 12 + size + 1 rounded up to a multiple of 4,
where size is the number of characters in the string. String size is the number of characters
in the string. The sequence of characters is terminated with an extra null character, with
Unicode representation 0; the null character is necessary so that our strings are compatible
with SPIM strings.

236 An Introduction to Compiler Construction in a Java World

Constant strings may be allocated in the data segment, which is to say, we may generate
constant strings in the data segment; strings in the data segment will then look exactly like
those on the heap (the dynamic segment). For example, the constant "Hello World!" might
be represented at the label Constant..String1:.

Constant .. String1:

.word 2 # tag 2 indicates a string.

.word 28 # size of object in bytes.

.word 12 # string length (not including null terminator ).

.asciiz "Hello World!" # string terminated by null character 0.

.align 2 # next object is on a word boundary.

The reader will have noticed that all objects on the heap share three words (12 bytes)
of information at the start of each object. This complicates the addressing of components
in the object. For example, the first element of an array a is at address a + 12; the first
character of a string s is at s+12; and the first field of an object o is at address o+12. That
12 must be added to an object’s address each time we want an array’s element, a string’s
character or an object’s field can be expensive. We can do away with this expense by having
our pointer, which we use to reference the object, always point into the object 12 bytes as
illustrated in Figure 6.19.

FIGURE 6.19 An alternative addressing scheme for objects on the heap.

Dynamic Allocation

The logic for allocating free space on the heap is pretty simple in our (oversimplified) model.

obj = heapPointer;

heapPointer +=