CSE P 501 Project IV - Code Generation

Due: Monday, June 9, at 11:00 pm. No late assignments will be accepted after that time.

Turn in your project using the assignment dropbox

Overview

The purpose of this final part of the project is to complete the compiler by adding code generation and implementing the runtime support needed to execute the generated x86 assembly code.  We suggest that you use the simple code generation strategy outlined in class to be sure of finishing the project, although you are free to do something different (i.e., better) if you have time. Whatever strategy you use, remember that simple, correct, and working is better than clever, complex, and not done. You will get much more out of the project if you have correct, simple implementations of most of the language rather than a broken, optimized implementations of a fragment.

Implementation Strategy 

Code generation incorporates many more-or-less independent tasks. One of the first things to do is figure out what to implement first, what to put off, and how to test your code as you go. The following sections outline one reasonable way to break the job down into smaller parts. We suggest that you tackle the job in roughly this order so you can get something working quickly, and add to it incrementally until you're done. Your experience implementing the first parts of the code generator also should give you insights that will ease implementation of the rest. 

Integer Expressions & System.out.println

Implement code generation for arithmetic expressions involving integer constants, the MiniJava System.out.println statement, and the basic prologue and return code for the MiniJava main method. This will give you enough to compile and run main programs that print the value of an integer expression.

Object Creation and Method Calls

Next, try implementing objects with methods, but without instance variables, method parameters, or local variables. This includes:

• Operator new (i.e., allocate an object with a method table pointer, but no fields)
• Generation of method tables for simple classes that don't extend other classes
• Methods with no parameters or local variables.

Once you've gotten this far, you should be able to run programs that create objects and call their methods. These methods can contain System.out.println statements to verify that objects are created and that evaluation and printing of arithmetic expressions works in this context.

Variables, Parameters, & Assignment 

Next try adding:

• Integer parameters and variables in methods, including assigning locations for these in method stack frames.
• Parameters and variables in expressions
• Assignment statements involving parameters and local variables

Control Flow

This involves:

• while, and if statements
• Boolean expressions, but only in the context of using these to control conditional statements and loops.

Classes and Instance Variables

Add the remaining code for classes that don't extend other classes, including calculating object sizes and assigning offsets to instance variables, and access to instance variables in expressions and as the targets of assignments. At this point, you should be able to compile and execute substantial programs.

Extended Classes

The main issue here is generating the right object layouts and method tables for extended classes, including handling method overriding properly. Once you've done that, dynamic dispatching of method calls should work, and you will have almost all of MiniJava working.

Arrays

We suggest you leave this until the end, since you can get everything else working without it.

The Rest 

Whatever is left, including any extensions you've added to the project, or items like storable Boolean values, which are not essential to the rest of the project.

C Bootstrap

As discussed in class, the easiest way to run the compiled x86 code is to call it from a trivial C program.  That ensures that the stack is properly set up when the compiled code begins, and provides a convenient place to put other functions that provide an interface between the compiled code and the external world. 

We have provided a small bootstrap program, boot.c, that we suggest you start with. Feel free to embellish this code as you wish. In particular, you may find that it is sometimes easier to have your compiler generate code that calls a C runtime function to do something instead of generating the full sequence of instructions directly in the assembly code. You can add such functions to the .c file.

Linux

If your group is targeting Linux, your compiler should output GNU assembly code.

To create an executable from boot.c and some assembly program generated by your compiler (test.s), simply execute:

gcc -o executable_name boot.c test.s

If you developing on a 64-bit platform, you need to pass the flag -m32 to gcc to force it to generate 32-bit code. Note that this will not work on attu -- you'll have to use attu32.cs, which is still running a 32-bit version of Linux.

You can also use GCC to look at examples of assembly code. This is useful if you want to find a set of instructions to implement some operation, but don't want to spend the rest of your life reading Intel manuals.

gcc -S foo.c

This will compile foo.c into foo.s, which you can open in an editor and inspect.

We've included a sample assembly program, demo.s, which will give you an idea of what you should emit. This is not a from a real MiniJava program, and your compiler will likely emit much more naive code, but it can serve as a good starting point.

Windows

If your group is targeting Windows, your compiler should output MASM assembly code.

The process for executing MASM code is a little more complex. First, you must set up your command line environment to be able to use the Visual Studio command line tools. If you have a full version of Visual Studio, you may have something named "Visual Studio Command Prompt" (or similar) in your start menu. If this is the case, you will likely be able to just start it and skip the next part of the instructions.

In my installation of Visual Studio Express, there is a script called vcvarsall.bat located in C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC Navigate to this directory (or a similar one on your installation) in Command Prompt and run this script. Now, you should be able to run the commands cl, ml, and link. I have not succeeded in getting this to work in PowerShell or Cygwin, but if you do, please post on the message board and explain how.

Assuming that you have boot.c and some assembly file, say, test.asm:

1. cl /c boot.c
   This will create an object file from boot.c
2. ml /c test.asm
   This will create an object file from test.asm
3. link test.obj boot.obj
   This will create an executable named test.exe

Just as with GCC, you can use cl to see examples of generated assembly code.

cl /c /Fa foo.c

This will compile foo.c into foo.asm. The /c flag means "compile only." This will also generate foo.obj. If you find a flag that suppresses this output, please let me know.

We've included a sample assembly program, demo.asm, which will give you an idea of what you should emit. This is not a from a real MiniJava program, and your compiler will likely emit much more naive code, but it can serve as a good starting point.

If you have any suggestions on how to improve this process, please post on the message board.

What to Turn In

• Submit an archive file containing only a directory named "minijava" (all lowercase) -- the root directory of your project. If you are developing for Linux, this should be a .tar file. If you are developing for Windows, it should be a .zip file. This should include two shell scripts:
• build.sh/build.cmd: When called, this should do whatever compilation steps are needed. Most likely, this will just call ant build.
• minijavac.sh/minijavac.cmd:
  • This should take a MiniJava program on stdin and write assembly code to stdout.
  • It should not write anything that is not assembly code to stdout -- this includes any output that Ant adds, or any diagnostic messages that you print.
  • It should exit with a zero exit code if and only if compilation is successful
  • When linked linked against your boot.c, your program should not produce any extraneous debugging output. It should only produce the output that the original program would produce if run in Java.
• Your boot.c file, with any modifications you have seen fit to make, should be in your src directory. To be clear, from the root of your archive file, it will be located in minijava/src/boot.c
• Please include a README.txt file containing the names, UW netID, and CSE netID, of all group members, as well as a short description of any challenges you faced in this part of the project, or anything else you would like the grader to know.
• Please run ant clean (or equivalent) before turning in your code to avoid turning in all your build artifacts. Similarly, please avoid turning in your entire .git folder, or the equivalent for whatever VCS you're using.
• If you are using Linux, your code should build and run attu32. Under Windows, it should run on Windows 7 with Java 1.7, Ant 1.9, CL 18, ML 12, and link 12. Your code should run with Java 1.7, but reasonable allowances will be made if your code ends up being incompatible with my version of ML, for example.
• Your group should turn in only a single copy.
• A small number of points will be assigned simply for following the turn-in instructions.