************************************
* CS 143 - Compilers - Summer 2011 *
************************************

Programming Project 4: TAC Generation
-------------------------------------

Homepage: http://github.com/dunecn/cs143-pp4

Author: Prakash Surya <[email protected]>

Goal:

In the final project, you will implement a back end for your compiler that will
generate code to be executed on the SPIM simulator. Finally, you get to the tru
product of all your labor -- running Decaf programs!

Design Decisions:

The code generation back end was implemented in multiple passes of the abstract
syntax tree (AST). The first pass is used to set up the memory location for any
global variables which might be present in the Decaf program. A second pass is
then used to set up the labels which are to be used for functions and methods.
Although, these two passes could probably be combined into a single pass, they
were implemented at different times and execution speed is not of importance.
The third and final pass of the AST is then to recursively generate the
intermediate representation (IR) of the program. As the tree is walked, each
nodes Emit method is called (in turn calling's it's children's Emit methods)
generating the IR code for that specific node.

Array are implemented as generic memory allocations, with some extra space
prepended to allocation to store it's size. For example:

        int[] arr;
        arr = NewArray(2, int);

corresponds to the following in memory representation:

        +-----+    +---+--------+--------+
        | arr |--->| 2 | arr[0] | arr[1] |
        +-----+    +---+--------+--------+

Objects are implemented as generic memory allocations, with some extra space
prepended to the allocation to store it's vtable. Derived member variables
contiguously follow inherited member variable in memory. Similarly, derived
method pointers contiguously follow inherited methods in a class's vtable. For
example:

        class B            { int x; M1() {} }
        class D1 extends B { int y; M1() {} }
        class D2 extends B { int y; M2() {} }

        B  b1;
        D1 d1;
        D2 d2;
        B  b2;

        B  b1 = new  B;
        D1 d1 = new D1;
        D2 d2 = new D2;
        B  b2 = new D2;

corresponds to the following in memory representation:

        +----+    +---------+------+
        | b1 |--->| b1.vtbl | b1.x |
        +----+    +---------+------+
                      |    +--------+
                      +--->| B.M1() |
                           +--------+

        +----+    +---------+------+------+
        | d1 |--->| d1.vtbl | d1.x | d1.y |
        +----+    +---------+------+------+
                      |     +---------+---------+
                      +---->| D1.M1() | D1.M1() |
                            +---------+---------+

        +----+    +---------+------+------+
        | d2 |--->| d2.vtbl | d2.x | d2.y |
        +----+    +---------+------+------+
                      |     +--------+---------+
                      +---->| B.M1() | D1.M1() |
                      |     +--------+---------+
        +----+    +---------+------+------+
        | b2 |--->| b2.vtbl | b2.x | b2.y |
        +----+    +---------+------+------+

Although this is not a very memory efficient way to implement polymorphism and
dynamic dispatch (the vtable for D1 instances are redundant), the
implementation was very straight forward.

Building:

To build the parser, the following are known dependences: make, flex, bison,
and gcc. Once those dependencies are properly installed, simply type 'make'
from within the top level directory. This should output the 'dcc' executable.

Usage:

The compiler reads input from stdin, and outputs to stdout and stderr. Thus, it
can be run interactively simply by executing the parser:

        $ ./dcc

In this mode, dcc will read in the text typed into the terminal and generate
code once it reads in the EOF character. To exit while in this mode,
input the EOF character (Ctrl+D on most systems) or abort with Ctrl+C.
Alternatively, a file can be redirected into the program using standard shell
redirection syntax:

        $ ./dcc < main.decaf

In this mode, dcc will read in the file and spew out the generated code. In
both of these modes, dcc will send normal output to stdout and error messages
to stderr.

Regression Testing:

As active development continues, it is important to ensure the parser
maintains it's proper behavior. Thus, the check.sh script, in conjunction with
test cases within the samples directory can be used. To run the regression
suite, simply execute the shell script:

        $ ./check.sh

This will try to execute the full regression suite contained in the samples
directory, and output whether dcc passed or failed a specific test. On failure,
a diff of the actual output with the expected output will also be displayed.

When adding new regression test cases, make sure two files are created for each
test case and are added to the samples directory. The input file fed to dcc
should have a file extension of either 'decaf' or 'frag', and the expected
output file should have a file extension of 'out'. Also, the input file and
expected output file for each test need to have a common base filename. Please
see the existing test cases contained in the samples directory if more
clarification is needed.