CMSC 430, Spring 2009

Theory of Language Translation

Project 4 - C-- : Byte Code Generator

Due 11:59pm Mon, April 27th, 2009

Introduction

In this project you will add to your C-- compiler the ability to generate Java byte codes for the input program, and perform some simple peephole optimizations.

Getting Started

Project 4 will be implemented in Java in Eclipse. Download the following files:
  • Eclipse project archive file p4.zip
  • Archive code.out.zip containing sample byte code outputs from "javap -c"
You can import the project into Eclipse as an existing project in an archive file.

Changes

See project 2 description for description of project files and syntax/semantics of C--. Compared to project 3, there is one major change:

You should not need to make any changes to your scanner, parser, or type checker to perform code generation.

Building & Running Your C-- Compiler

** To build your mycc compiler 

        java JLex.Main mycc.lex
        mv -f mycc.lex.java mycc/Yylex.java
        java java_cup.Main mycc.cup
	mv -f sym.java mycc/sym.java
	mv -f parser.java mycc/parser.java
        javac -g -d . mycc/*.java

** To compile a C-- program foo.c using mycc

        java mycc.parser foo.c 

** To compile a C-- program foo.c using mycc, with optimizations turned on

        java mycc.parser -O foo.c 

** To examine the byte code produced by mycc

        javap -c foo.class

** To run the code produced by mycc

        java foo
The compiler will generate a Java class file .class for an input file named .c. You can examine the contents of the class file using ``javap -c'' to disassemble the class file.

The archive code.out.zip contains some sample byte code outputs of "javap -c" for the class file produced for the public test C-- files.

Requirements

Code Generation

Your main goal is to build a back end for C-- to generate Java byte codes from the AST created in project 3. You will use the skeleton back end in the file ClassFile.java, inserting calls to routines from the JavaClass libraries to generate a sequence of Java byte codes. You will also use information from your project 3 symbol table to assign storage for variables in your program.

You may assume that all input C-- programs are syntactically correct and without type errors.

Peephole Optimizations

In addition, you need to add the following simple peephole optimizations to your C-- compiler:

  • evaluate constant arithmetic expressions (e.g., 1+2 -> 3)
  • apply algebraic simplification (e.g., 0+x -> x)
  • fold constant relational expressions (e.g., 1 == 1 -> true)
  • simplify boolean expressions (e.g., true && x -> x)
  • simplify IF statements (e.g., IF (true) stmt1 ELSE stmt2 -> stmt1)

You must perform all your peephole optimizations at the AST level. You may do this in mycc.cup while generating your AST, or as a separate pass over the AST in ClassFile.java.

Main Classes

ClassFile

Documentation on Java bytecodes and the JavaClass library is available from the class web page. Be sure to take a quick look before starting the project. The procedures you need to implement in the compiler backend are:
  genProcCode()      Generate code for a procedure.  Allocate storage for local 
                     variables, then create code as a list of instructions.

  genInstCode()      Generate code for a C-- astNode representing
                     TREE_BLOCK, TREE_IF or TREE_WHILE statements.

  genExpCode()       Generate code for a C-- expNode representing
                     a single TREE_INSTRUCTION

  genOpCode()        Generate code for a C-- expNode representing an operand
The main data structure you will be manipulating is the InstructionList class. It maintains a list of Java byte code instruction equivalents that make up the output of the compiler back end. New instructions may be added to the list, and other InstructionLists may also be appended to existing list. New java byte codes instructions are created through constructors and added to an InstructionList. For instance, given the instruction list x, we can add a new instruction as follows:
   InstructionList x;

   genExpCode(x, op1);    // generate instructions for first operand, append to x
   genExpCode(x, op2);    // generate instructions for 2nd operand, append to x
   x.append(new IADD());  // generate IADD instruction, append to x
The append() function also returns an InstructionHandle (label) that can be used when generating conditional branch instructions:
   InstructionList x, y;
   InstructionHandle label;

   label = x.append(new NOP());   // returns label for conditional branch targets
   y.append(new IFEQ(labe1));     // create new conditional branch instruction 

Submission

You can submit your project in two ways:
  • Submit your mycc.lex, mycc.cup, and ClassFile.java files by first putting all files in a single .zip or .jar archive. The files should be at the top level of the archive, not in a subdirectory.

    You may create a jar archive containing mycc.cup, mycc.lex, and ClassFile.java by going to the directory containing your project, then either execute goJar (or goJar.bat) or type the following command directly:

    jar cf p4.jar mycc.cup mycc.lex ClassFile.java

    You can submit the resulting p4.jar archive to to the submit server by clicking on the submit link in the column "web submission".

    Select the p4.jar archive using the "Browse" button, then press the "Submit project!" button.

  • Submit directly by executing a Java program on a computer with Java and network access. Use the submit.jar file from the archive p4.zip, To submit, go to the directory containing your project, then either execute goSubmit (or goSubmit.bat) or type the following command directly:

    java -jar submit.jar

    You will be asked to enter your class account and password, then all files in the directory (and its subdirectories) will be put in a jar file and submitted to the submit server. If your submission is successful you will see the message:

    Successful submission # received for project 4

Academic Integrity

Please carefully read the academic honesty section of the course syllabus. In particular, remember that you are not allowed to show or copy any code for your project, either from the web or other students. Any evidence of impermissible cooperation on projects, use of disallowed materials or resources, or unauthorized use of computer accounts, will be submitted to the Student Honor Council, which could result in an XF for the course, or suspension or expulsion from the University. Be sure you understand what you are and what you are not permitted to do in regards to academic integrity when it comes to project assignments. These policies apply to all students, and the Student Honor Council does not consider lack of knowledge of the policies to be a defense for violating them. Full information is found in the course syllabus---please review it at this time.