Putting It All Together
Over the semester, you have implemented the front end stages of a compiler for Tiger, plus code generation for the variable-free subset of the language.
In this final project, you are to complete your compiler, with support for a nearly-complete specification of Tiger. By "nearly complete", I mean everything except for nested procedure definitions.
Specifically, you must complete implementations in JVMGeneratorV of:
- visit(ExpLet), and the associated visit(Decl*)) and visit(Ty*) methods
- visit(ExpVar), visit(ExpAssign), and the associated visit(Var*) methods
- visit(ExpArray) and visit(ExpRecord)
- visit(ExpFor), which was omitted from Assignments 7 and 8 because of the need to support declaration of a for-loop's index variable
- The "type definition" expressions: visit(TyArray t), visit(TyName t), and visit(TyRecord t).
In addition, you must include a "main", which allows the user to specify a Tiger source file. This program should compile the specified source file to a Jasmin JVM assembly file (use the extension ".j" in the generated file name).
Testing Your Work
If you have not already done so, install a local copy of the Jasmin tool, available at http://jasmin.sourceforge.net/. Use of this tool is very straightforward: it takes a .j file and produces the corresponding .class file.
It's probably best not to waste time trying to integrate this with your Eclipse project (though a plugin does exist). Instead, run everything from the command line. Here's an example:
Suppose first that we have generated our standard library in a separate file, TigerStdLib.j:
.class TigerStdLib .super java/lang/Object .method public ()V aload_0 return .end method .method public static print(Ljava/lang/String;)V .limit stack 2 .limit locals 1 getstatic java/lang/System/out Ljava/io/PrintStream; aload_0 invokevirtual java/io/PrintStream/print(Ljava/lang/String;)V return .end method
Now suppose we have the Tiger source file myprog.tig:
You would compile your work with
$ java TigerC myprog.tig Code written to myprog.j
This should produce a Jasmin file similar to
; opening comments, if any .class Myprog .super java/lang/Object .method public ()V aload_0 return .end method ; end initial setup for class Myprog ; .method public static main([Ljava/lang/String;)V .limit locals 1 .limit stack 1 ldc "Hello, world!\n" invokestatic TigerStdLib/print(Ljava/lang/String;)V return .end method
You can then use Jasmin to produce JVM byte code:
$ java -jar jasmin.jar TigerStdLib.j Generated: TigerStdLib.class $ java -jar jasmin.jar myprog.j Generated: Myprog.class
This will create the files Myprog.class and TigerStdLib.class. You can now run your program as you would any other compiled Java program:
$ java Myprog Hello, world! $
Submitting Your Work
Turn in your completed tigerc project to your CPSC 433 class folder. Some time between 7:00 and 10:00 pm on Tuesday evening, you will meet with me to give a demo of your work. Other times on Monday the 12th or earlier on Tuesday may be possible, too. I will have a sign up sheet outside of my office door.
Code Architecture and Ideas
Over the past three weeks, we have discussed various ideas and techniques for implementing JVM generation of ordinary control flow, binary and unary operators, variable declaration and assignment, and procedure definition and calls.
In the labs given during the term, I required you to conform your solutions to specific architectural decisions. The purpose of that was to make the assignments as modular as possible, so that difficulty at one stage did not prevent success in the later stages. For this final effort, you are free to use my suggested design decisions or make your own. If you are unsure of your solution to one of the earlier stages of the compiler, please ask me for a binary of my solution. If you've followed the earlier architectural requirements, you should be able to plug in my .class files and have everything Just Work.
The following is a summary of points made in the last week or two of classes:
Like type checking, code generation is a function of both the AST and an environment. You'll want to add an Env to your JVMGeneratorV class. To do this, you'll need to reconsider the package-only visibility of the Env and related classes.
Variable access is always relative to the activation record ("stack frame") in which the variable is defined/used. Define a tigerc.codegen.IAccess interface, and implement it with a tigerc.codegen.jvm.JVMAccess class. This interface should require methods that provide the necessary instructions for accessing the variable as an L-value and as an R-value.
Add an tigerc.codegen.IFrame interface, and implement it with a tigerc.codegen.jvm.JVMFrame class. This interface should provide a method for allocating new variable accesses. Each call should generate an IAccess for a new offset in the frame. Since the JVM requires type information in all load and store instructions, your allocation method should take the Type of the variable as an argument.
Procedure definition should not result in code being generated immediately. Instead, each procedure definition should result in the construction of a fragment, consisting of a procedure's Label (the signature that will be generated in the appropriate .method directive), code for the procedure body, and the appropriate return statement. With JVM code, you can probably put all of this in one string, but assembling code for procedures is more complicated on other hardware, and it's a good idea to consider the parts separately. Each fragment should be added to a list, and the list should be generated as ".method public static" declarations when the JVMGeneratorV.emitProcedures() method is called.
Modify the definition of VarEntry to include a variable's IAccess. Since IAccess objects are irrelevant to type checking, hang on to the VarEntry constructor that only takes Symbol and Type values (for this older constructor, you can just set the IAccess field to null).
Modify the definition of FunEntry to include a procedure's generated Label. Also, if you generate the standard library in a separate file, modify the definition of FunEntry to include additional information about a procedure's definition in an external class. My solution adds a field of type Class<?> and three methods—setExternal(), getExternal(), and isExternal().
Implement record types as java.util.Hashtable objects. There are other approaches, but this one is probably the simplest.
For the top-level definition only, implement any declared variables with the ".field" directive. This will allow you to support global-variable access to these values in procedures. Alternatively, just refuse to support access to variables defined outside the scope of a procedure, even at top level.
Do not try to support nested procedure definitions, until you've completed everything else. They are difficult, I do not expect them of you, and solving them requires techniques we have not covered in class.
Nested Procedure Support
The presence of nested procedure definitions in a language gives rise to a problem known as the downward funarg problem. The real challenge arises in nested procedure bodies that access variables or procedures defined in an enclosing scope. In such cases, the procedure's frame must have access to the most recent frame of the statically-enclosing procedure. In the general case, this cannot be done with a frame's control link, but in JVM, it is flatly impossible to access another procedure/method frame at all, so the usual technique of adding a static link will not work.
Nonetheless, it is possible to solve this problem, and many languages that support nested procedure definitions have implementations on the JVM.
Completing this feature of the Tiger compiler is not required of any of you, but if you do so, there is a substantial reward: anyone who completes a Tiger compiler with correct support for nested procedures will earn a minimum grade of an A for the course, regardless of past performance. If you think you've got a correct solution, let me know in advance, and I'll help you set up a few test cases.