dOvs 2010

This assignment concerns the generation of Java bytecode from the transformed and analyzed Java code. It consists of the two phases Resources and Codegeneration. You must hand in two files resources.ml and codegeneration.ml that extend the skeleton.

When all phases up to and including the code generation have been completed, you will be able to run your compiler on its own, without having to rely on the online tester.

Instruction

The code is generated using the instruction types defined in the Instruction module. The type Instruction.instruction has a constructor representing each specific instruction and is named with an I followed by the assembly opcode name. The functions defined in the Instruction module are used by the stack limits calculator, the peephole optimizer and the code emitter.

The constructor of an instruction class takes a number of parameters corresponding to the parameters of the instruction. These will always have one of the following types (class names are implicitly in the dovs.instructions package):

int: An integer parameter, representing a local variable index or array dimensionality.
int32: A 32-bit integer parameter, representing an integer constant.
label: A label or a reference to a label.
condition: A data type representing the possible conditions in a conditional jump.
signature: The signature of a type or a field.
method_signature: The signature of a method.

The instruction constructors do not always correspond exactly to JVM instructions. In some cases, one instruction constructor can represent one of a number of different actual JVM instructions depending on the values of its parameters. The instructions that have special meaning in this sense are:

An Iif represents any conditional jump that compares a single value against zero or null.
An Iifcmp represents any conditional jump that compares two values against each other.
An Ildc_int represents any instruction that pushes an integer constant onto the stack.
An Ildc_string represents an ldc instruction whose argument is a string.
An Ilabel represents a label, i.e. a place in the code that other instructions can jump to. It does not correspond to a JVM instruction.

The set of instructions available to the compiler is fixed to the ones mentioned in the Instruction.instruction type. This set is more than sufficient to implement the whole Joos 2 language.

Resources

The Resources phase is responsible for calculating the local variable index for each local variable. The pass also calculates the signatures of types, fields and methods.

Transformations

For each TAst.LocalDecl node in the program, assign a local variable index to the variable and bind it with the RAst.LocalDecl constructor. The skeleton already contains code to do this which is correct but suboptimal.

Either (Joos 1) optimize indices to reuse offsets for locals in disjoint scopes. (See "Better Offsets" in code generation slide 6.)
or (Joos 2) optimize indices by implementing a liveness-analysis as described in static analysis from page 35. (See also "Clever Offsets" in code generation slide 7.)

Codegeneration

The Codegeneration phase builds instruction lists for the bodies of all methods and constructors.

Transformations

Joos 2: For every class, add a public, static void method called <clinit> taking no arguments and throwing no exceptions. This method should contain the code for initializing all static fields. Final static fields whose initializers are compile-time constants should be initialized before other static fields. Whether or not an expression is a compile-time constant can be checked (after the constant folding phase has been run) using the is_constant function.

For every method or constructor body in the program, generate a list of instructions corresponding to the code in the body and bind it to the method_body and constructor_body record labels.

The generation of JVM instructions for a body can be achieved by a single depth-first traversal of the code using the code generation templates described in the slides.

Code for initializing non-static fields should be executed immediately after the super constructor call of every constructor that calls a super constructor.

The Joos 0 compiler implements implicit string concatenation using the String.concat method. However, javac implements a series of implicit string concatenation operations as StringBuffer.append calls on the same StringBuffer object. The first strategy uses quadratic execution time in the number of consecutive string concatenation operations, while the latter only uses linear time.

Either (Joos 1): Implement string concatentation using String.concat,
or (Joos 2): Implement string concatenation using StringBuffer.append.

Documentation

You must post an entry in your group blog that explains how your code works and which problems you have encountered and solved in the process. Furthermore:

Translate the following code into jasmin by hand as defined by the code templates from the slides:
```
public int m(int a, int b) {
	if (a < b) {
		return 42;
	}
	return 123;
}
```
Write the same method in jasmin using fewer instructions than the translated version.
Explain why we use the code templates for translation when it is possible to write shorter code as in the above example.

You may furthermore:

Write a piece of jasmin code in which the stack height can vary for a particular program point (for instance depending on which branch we have taken).
Explain why the verifier considers such a program point problematic.