Programming Question

Programming Assignment 4 – Code GenerationOverview
The purpose of this part of the project is to add code generation to the compiler so that it can
produce x86-64 assembly code, and add the runtime support needed to execute compiled programs.
It is suggested that you use the simple code generation strategy outlined in class to be sure you get
running code on time, 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.
It is strongly recommended that you do thorough testing after you implement each part of the code
generator. Debugging of code generators can be difficult, and you will make your life easier if you
find bugs early, before your generator is too complex.
Modify your MiniJava main program so that when it is executed using the command
Java -C MiniJava filename.java
it will read the MiniJava program from the named input file, parse it and perform semantics checks,
then print on standard output a x86-64 gcc-compatible assembly-language translation of the input
program. The java command shown above will also need a -cp argument or CLASSPATH variable
as before to locate the compiled .class files and libraries.
If translation is successful, the compiler should terminate with System.exit(0). If any errors are
detected in the input program, including static semantics or type-checking errors, the compiler
should terminate using System.exit(1).
If errors are detected, the compiler does not need to produce any assembly language code, and, in
fact, should probably exit without attempting to generate code. The code generator should be able to
assume it is translating a correct MiniJava program and should not need to include error checks or
special cases to deal with incorrect code.
The output program should be a correct translation of the original MiniJava program and the
generated code should not produce runtime errors like segfaults, to the extent this is reasonable. In
particular, if a MiniJava program attempts to access an array element with an illegal (out of bounds)
subscript, execution should be terminated with an appropriate error message. It is up to you whether
the message contains the source line number of the error, although it would be useful to include this.
But you do not need to generate code to check all object references for possible null pointers or deal
with other situations where it would be unreasonable to try to detect problems.
Your MiniJava compiler should still be able to run the options for -S, -P, -T and -A and from the
previous assignments. It is up to you how to handle the program if these parameters are specified at
the same time as the -C option.
Implementation Strategy
Code generation incorporates several 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. It is suggest that you tackle the
job in roughly this order so you can get something compiled and running 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.
1. Integer Expressions & System.out.println
Get a main program containing System.out.println(17) to run. Then add code generation for
basic arithmetic expressions including only integer constants, +, -, * and parentheses. You will also
need the the basic prologue and return code for the MiniJava main method, which uses the x86-64
C language conventions.
2. 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.
3. Variables, Parameters, & Assignment
Next try adding:
•
•
•
Integer parameters and variables in methods, including assigning stack frame locations for
variables.
Parameters and variables in expressions
Assignment statements involving parameters and local variables
Suggestion: Some of the complexity dealing with methods is handling registers during method calls.
It can help to develop and test this incrementally — first a single, simple function argument, then
multiple arguments, then arguments that require evaluation of nested method calls.
4. Control Flow
This includes:
•
•
•
While loops
If statements
Boolean expressions, but only in the context of controlling conditional statements and loops.
5. 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 using instance variables in expressions and as the
target of assignments. At this point, you should be able to compile and execute substantial
programs.
6. 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.
7. Arrays
We suggest you leave this until late in the project, since you can get most everything else working
without arrays.
8. The Rest
Whatever is left, including items like storable Boolean values, which are not essential to the rest of
the project, and any extensions you’ve added to MiniJava or the compiler.
C Bootstrap
As discussed in class, the easiest way to run the compiled code is to call it from a trivial C program.
That ensures that the stack is properly set up when the compiled code begins execution, and
provides a convenient place to put other functions that provide an interface between the compiled
code and the outside world.
We have provided a small bootstrap program, boot.c, in the src/runtime directory of the starter
code and we suggest you start with this. 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. Be sure to update the
src/runtime/boot.c file with your changes. We will use the file found there to run your
compiled code.
Executing x86-64 Code with gcc
Your compiler should produce output containing x86-64 assembly language code suitable as input to
the GNU assembler as. You can compile and execute your generated code and the bootstrap
program using gcc, and you can use gdb to debug it at the x86-64 instruction level.
There is a sample assembler file demo.s in src/runtime that demonstrates the linkage
between boot.c and assembler code. This demo file does not contain a full MiniJava program, and
the code produced by your compiler will be different, but it should give you a decent idea of how the
setup is designed to work. Use this and boot.c as input to gcc to generate an executable demo
program. You can also use gcc to generate additional examples of x86-64 assembly code.
If foo.c contains C code, gcc -S foo.c will compile it and create a file foo.s with the
corresponding x86-64 code.
You should test your compiler by processing several MiniJava programs. By the time you’re done
you should be able to compile any of the MiniJava example programs distributed with the starter
code. Since a legal MiniJava program is also a legal full Java program, you can compare the
behavior of programs compiled and executed by your MiniJava compiler with the results produced
when the same program is compiled and executed using javac/java
What to Hand In
For this phase of the project the main things we will be looking for are the following:
•
•
•
•
That your compiler properly generates the code to X86-64 assembly code (-C option)
That your assembly code compiles with GCC.
Your program runs to completion and produces the correct output.
We also check several of the example MiniJava programs.
To submit your code, you must first clean the entire directory using the following command:
ant clean
After the directory has been cleaned, compress the entire minijava_starter directory structure into a
.zip file with the following name structure: csc348_hw5_[lastname]_[firstname].zip
Submit the code to D2L along with sample output in a text file in the submission folder. This is to
demonstrate that your code ran correctly before submitting it.
We will test your code by building and running your project using ant and Java from the command
line, using one or more sample programs from the project. Please make sure your program runs and
generates the correct output before submitting it.