Code Generation

Setting Up the Project

Download the file final.zip [link]. This distribution contains four files—TigerC.java, ICodegen.java, Entry.java, and JVMGeneratorV.java. These files should be added to your project as follows:

tigerc
  --> src
        --> tigerc
               -- TigerC.java
               --> translate
                    -- Entry
                    -- ICodegen.java
                    --> jvm
                        -- JVMGeneratorV.java

Next are some modification to the build.xml file. In the interest of getting you more familiar with this essential component of the project, the burden of these changes is on you this time:

Strategy

This last part of the project is the largest, and it will have the least guidance. In its briefest statement, your job is to complete the JVMGeneratorV class and write all necessary supporting classes for that task. I suggest you attack this in stages.

Implement a partial code generator

Start by implementing code generation for the Tiger constructs that do not involve the declaration or use of variables, functions, or types. The generator will target the Java Virtual machine. In particular, complete the visit methods for the following AST constructs: ExpInt, ExpString, ExpNil, ExpOp, ExpIf, ExpIfElse, ExpSeq, ExpBreak, and ExpWhile.

Ideas

For all of the interesting control constructs, you're going to need a notion of unique labels that can be generated as needed. I suggest adding a Label class to the tigerc.translate package, with two constructors: one that generates a new, unique label name with each label instance and another which generates a label (not necessarily unique), based on the text of the label that is passed as an argument.

The Standard Library

For calls to the standard library, you'll use the TigerStdLib.class file, which you built from your Jasmin assembly code file. You'll want to have a structure, containing the entry labels for these methods, in order to facilitate calling them.

Procedure Calls

Complete the implementation of visit(ExpCall). In the JVM, this is quite straightforward, really, since we don't need to worry about a procedure's entry label (and hence don't need to store it in tigerc.semant.Entry.FunEntry). Just push each argument onto the current stack, then invoke the method that's been called. All necessary type information is already in the procedure's FunEntry record, of course.

However, this leads us to ...

Incorporating Type Information

Though semantic analysis has already filtered out ill-typed programs, we're going to need some information about expression types, in order to generate the correct JVM instructions. The task is much simpler here, since you can always assume that everything is correctly typed. Still, you're going to need to modify your JVMGenerator to include a "current expression type" value, and you're going to need a value environment (see tigerc.semant.SemantV.venv and tenv).

Happily, there's no need to check types. You just need to record the type of the last expression encountered. For example, in visit(ExpBreak), we add at the end of the method the statement

    this.currentT = VOID_T.inst;

(assuming that your JVMGeneratorV has a field declared as "Type currentT").

This also implies that you should include, as part of the skeleton of your visit(DeclGroupFunction) and visit(DeclVar) methods, statements sufficient to add the appropriate VarEntry and FunEntry bindings. I'd suggest making this much of the skeletons now (remember, you don't have to check anything, since you can assume everything is well-typed).

Putting It All Together

For the final stage, 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:

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:

print("Hello, world!\n")

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 8:30 am and 11:30 am on Sunday morning, you will meet with me to give a demo of your work. I will have a sign up sheet outside of my office door.

Code Architecture and Ideas

Over the next few classes, we will discuss 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.

Assorted Advice

The following is a summary of points made in the last week or two of classes:

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.


John H. E. Lasseter