Lab 3: Code Generators

Lab Overview

The first code generator: the C code generator is required. All other three code generators: Java bytecode, Dalvik bytecode, and x86 are optional. However, you are encouraged to try the three, for it will give you deeper knowledge and insight of a code generator.

Getting Started

First check out the source for Lab3 at:

  $ git commit -am 'my solution to lab2'
  $ git checkout -b Lab3 origin/Lab3

Again, you will need to merge your code from Lab2 into the new local Lab3 branch:

  $ git merge Lab2

  $ git commit -am 'lab3 init'

You should first import the new Lab3 code into your Eclipse and browse through the source code, which contains these new packages:

codegen.C    classes operating on the C AST (translator, pretty printer, etc..) codegen.C.*    data structures defining the C AST codegen.bytecode    classes operating on the Java bytecode AST codegen.bytecode.*    data structures defining the Java bytecode AST codegen.dalvik    classes operating on the Dalvik bytecode AST codegen.dalvik.*    data structures defining the Dalvik bytecode AST codegen.x86    data structures and classes for the x86 code generator runtime/*    a simple runtime system

Hand-in Procedure

Part A: The C Code Generator

Abstract Syntax Trees for C

  $ java -cp bin Tiger -testFac

Virtual Function Tables

Java only allows single inheritance, so the inheritance relationship between all classes forms a tree with the sole Object as the root class. The first question one must answer is what fields and methods a class may contain, that is, one should calculate, for each class, the fields and methods for that class. The key point to note here is that the fields and methods in a given class C include not only the ones directly declared in that class C, but also the ones inherited from the current class C's parent class, and from the parent's parent class, and so on, until reaching the tree root class Object. So, the inheritance relationship are cascaded.

As Java only allows single inheritance, so the prefixing algorithm works well for this. The basic idea of the prefixing algorithm can be illustrated by the following pseudo-code:

  void prefixing ()
  {
    build the inheritance tree t for all classes;     // every class is a tree vertex, with "Object" as the tree root
    foreach (class C in the tree t, in a BFS order) {    // visit the tree "t" in a breadth first order
        make a fresh empty class NewC;
        copy all fields from C's parent into NewC;
        append all fields from C to NewC;
        copy all methods from C's parent into NewC;
        append all methods from C to NewC;  // what about method overriding?
        delete the class C;
    }
  }

There is a subtlety in this algorithm: in order to compile method overriding correctly, one should overwrite the corresponding method slots from the parent class, instead of appending it to the methods in the parent class. By the word "corresponding", we mean methods with same names (as MiniJava does not allow method overloading).

class A{
  int x;
  int y;
  void f(){}
  void g(){}
}
class B extends A{
  int x;
  int z;
  void h(){}
  void g(){}
}

The prefixing algorithm will make all classes closed, that is, no class will inherit from any other classes, and all references to instance variables and methods will be limited to the current class.

The current implementation of the prefixing algorithm in the Tiger compiler makes use of a slightly different algorithm than the algorithm above. The algorithm in the Tiger compiler makes use of table to store all the inheritance tree nodes (the definition of the table is in the file codegen.C.ClassTable.java). Essentially, this table is a mapping from class name to the class' containing fields and methods. And the inherit method in that class takes as input a class name c and calculates all fields and methods for that class c.

  class C1{
    int x1;
  }
  class C2 extends C1{
    int x2;
  }
  ...
  class Cn extends Cn-1{
    int xn;
  }

Generating C from Java

To this point, your Tiger compiler should compile any legal MiniJava program to a corresponding legal C program. You should test your compiler thoroughly before continuing. For instance, to test your Tiger compiler on the test case test/Factorial.java, just compile the MiniJava program like this:

  $ java -cp bin Tiger ../test/Factorial.java -codegen C

  $ gcc -c Factorial.java.c

Fix any possible bugs and don't forget to do regression testing.

A Minimal Runtime

Browse through the directory runtime/, in which resides the minimal runtime system we offered you. You may find:

gc.c code for the garbage collector lib code for the library main.c program entry point runtime.c a wrapper

Especially, the file gc.c contains the preliminary skeleton code for a garbage collector (though for now, it is a shame to call it a garbage collector because it just allocates memory but never reclaims them).

  $ gcc Factorial.java.c runtime/runtime.c

It will be very boring to type various commands on the prompt for the entire compilation pipeline: Tiger compiling, gcc compiling, linking. etc.. A much more convenient way to do this is to add some glue code into Tiger so that it can do all these steps in an automatic manner.

This completes the C code generator. To this point, your Tiger compiler can generate executables for any legal MiniJava programs. Don't forget to test your Tiger compiler thoroughly.

Part B: The Java Bytecode Generator

Abstract Syntax for Java Bytecode

The first difficulty is easy to resolve: one just choose, from the Java bytecode instruction set, a subset that is enough to compile the MiniJava subset of Java. It's your job next to figure out such a subset of the Java bytecode instructions.

To resolve the second difficulty, one can choose a Java bytecode assembler which can assemble instructions in readable text form into binary forms which can be executed by a JVM. This process is very much like that a traditional assembler assembles assembly program into binaries. With the bytecode assembler, your Tiger compiler can generate text form Java bytecode instructions and leave the tedious work of assembling to the bytecode assembler. Nevertheless to say, writing a bytecode assembler from scratch is, though conceptually simple, tedious and too much work. Fortunately, there are some mature third party assembler that you can use in your Tiger compiler. To be specific, the Java bytecode assembler you'll use in this lab is called Jasmin. There is no specific reason why we choose Jasmin among many such assemblers. But Jasmin has been the oldest Java bytecode assembler and has been used widely in many projects. Jasmin has become the de-facto assembly format for Java bytecode.

Generating Java Bytecode

     the value of code_length item must be less than 65536.

Part C: The Dalvik Bytecode Generator

Abstract Syntax for Dalvik Bytecode

The first difficulty is easy to resolve: one just choose, from the Dalvik bytecode instruction set, a subset that is enough to compile the MiniJava subset of Java. It's your job next to figure out such a subset of the Dalvik bytecode instructions.

To resolve the second difficulty, one can choose a Dalvik bytecode assembler which can assemble instuctions in readable text form into binary forms which can be executed by a DVM. This process is very much like that a traditional assembler assembles assembly program into binaries. With the bytecode assembler, your Tiger compiler can generate text form Dalvik bytecode instructions and leave the tedious work of assembling to the bytecode assembler. Nevertheless to say, writing a bytecode assembler from scratch is, though conceptually simple, tedious and too much work. Fortunately, there are some mature third party assembler that you can use in your Tiger compiler. To be specific, the Dalvik bytecode assembler you'll use in this lab is called Smali. There is no specific reason why we choose Smali among many such assemblers. But Smali has been the most popular Dalvik bytecode assembler and has been used widely in many projects. Smali has become the de-facto assembly format for Dalvik bytecode.

  // assemble the "HelloWorld.smali" to "classes.dex"
  $ java -jar smali.jar -o classes.dex HelloWorld.smali
  // compress the .dex to a package
  $ zip HelloWorld.zip classes.dex
  // push the package to your (virtual) Android devices
  $ adb push HelloWorld.zip /data/local
  // run the program using the Dalvik VM
  $ adb shell dalvikvm -cp /data/local/HelloWorld.zip HelloWorld

Generating Dalvik Bytecode

     Because, in practice, it is uncommon for a method to need 
     more than 16 registers, and because needing more than eight 
     registers is reasonably common, many instructions may only 
     address the first 16 registers. When reasonably possible, 
     instructions allow references to up to the first 256 registers. 
     In cases where an instruction variant isn't available to address 
     a desired register, it is expected that the register contents 
     get moved from the original register to a low register (before 
     the operation) and/or moved from a low result register to a high 
     register (after the operation).

Part D: An x86 Generator

Handin