CMSC 430: 

Project 4: C-- Byte Code Generator & Peephole Optimizer

Your 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 will add the following simple peephole optimizations to your C-- compiler,
as part of either AST or bytecode generation:

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

Note that certain peephole optimizations can only be performed at 
bytecode level.


**********************************************
Setup
**********************************************

Project 4 requires a new library, JavaClass.  Download de.tar and extract 
its contents to the Java library directory in your CLASSPATH (same place 
where JLex and java_cup are located).  For Windows, extracting the tar file 
in c:\Java should place all the contents in c:\Java\de.

** Commands to build compiler (run script "go")

	java JLex.Main mycc.lex
	mv mycc.lex.java Yylex.java
	java java_cup.Main < mycc.cup
	javac -g -d . *.java

** Commands to test the compiler (run script "go1 <prog>")

	java mycc.parser $prog.c > $prog.log
	cat $prog.log
	javap -c $prog 
	java $prog

** Commands to test compiler optimizations (run script "go2 <prog>")

	java mycc.parser -O $prog.c > $prog.log
	cat $prog.log
	javap -c $prog 
	java $prog

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

**** Description of project files

(Files you need to modify)

mycc.lex                   Regular expressions & actions for scanner
                           (should require no changes from project 3)

mycc.cup                   Grammar & actions for parser
                           (add the following lines to end of parser.main(),
                            and also add any AST-level peephole optimizations)

                ClassFile class_file = new ClassFile(cname); // prepare codegen
                ClassFile.genCode(code, globalSymTab, optFlag); // generate code

ClassFile.java             Class to handle byte code generation
                           (most of your code changes, and any byte-code level
                            peephole optimizations)

(Files you should not need to modify)

Const.java                 Constants for mycc
symTabEntry.java           Symbol table entries
symTab.java                Symbol tables
astNode.java               AST nodes
astNodeList.java           list of AST nodes
expNode.java               expression nodes

sym.java                   produced by CUP from mycc.cup
parser.java                produced by CUP from mycc.cup
Yylex.java                 produced by JFlex

goAll       script for building & testing compiler on several test files
go          script for building compiler
go1 <prog>  script for testing compiler on one file <prog.c>
go2 <prog>  script for testing compile optimizations on one file <prog.c>
goTest      script for testing compiler on all test files
goToy       script for testing compiler on all toy test files

toy*.c      toy input files that the skeleton compiler can compile
test*.c     test input files for project
test*.out   example compiler output files from working project

*************************************************
Description of main data structures and functions
*************************************************

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