\documentstyle[12pt,fullpage,simplemargins]{article}

\setleftmargin{0.75in}
\setrightmargin{0.75in}
\settopmargin{0.75in}
\setbottommargin{0.75in}

\begin{document}
6.035 - Fall 1999 - TA: Daniel Barkalow \hspace{3in} le04
\begin{center} 
{\bf MIPS Code Generation}
\end{center}

\section*{Reintroducing le04}
    Chris Laas (golem)\\
    Mike Phillips (mpp)\\
    Jim Waldrop (jlwfnord)\\

\section*{Division of Labor}

The labor for this project was divided into three rough chunks. First,
we changed our tree of LowInstructions into a list of
DelocalizedInstructions. This (Phase 1) was mainly Mike's
responsibility.\\ Phase 2 was the assignment of registers and stack
storage slots to the aforementioned DelocalizedInstructions. We moved
the flattening and allocation of storage space from the LowInstruction
classes (where we had implemented them for the lowIR generation
portion of the compiler) into the DelocalizedInstruction
classes. Phase 2 was Chris's responsibility as he had already begun
moving address space flattening and allocation into the codegen
segment of the compile.\\ Phase 3 was the actual generation of MIPS
assembly code. The bulk of the ASM code was Jim's responsibility; Mike
did a good deal of work in Phase 3 on the calling convention.


\section*{Clarifications, Assumptions, Additions}

None.

\section*{Overview}

The purpose of this phase of the project was to finally {\bf generate
code}, however naively. Our design goals were to have unoptimized
output, but to construct things as we went to make it easier to
optimize later.  For example, we had a general facility for creating
temporaries, assigning them to real locations in a machine, and moving
their contents about. Only one specific piece of code deals with the
details and can be changed easily later; the rest of the code deals with
the concept abstractly.

\section*{Implementation and Insights}
A clear design from the outset helped to make this segment go more
smoothly, and will hopefully pay off with a clear division of code
modules.  Separating the code generation into three phases, one for
arithmetic and flow control generation, one for memory allocation, and
one for final output, allows more fine-grained access to the
information inherent in the program structure.

\subsection*{Phase One: LowIR to Delocalized Instructions}
The first step after the lowIR generation was to traverse the lowIR
graph into a flat sequence of Delocalized Instructions, much in the
same way that the lowIR pretty printed itself. This concept of a
Delocalized Instruction is basically a RISC-like instruction set where
the data locations (RValues and LValues) are abstracted and
deliberately vague. A large portion of the necessary assembler steps
can be performed in this phase. During the processing, additional
temporary variables are created as needed.  No details of the target
machine calling convention or address model are known or assumed. Things
are still fairly machine independent in this phase.

\subsection*{Phase Two: Physical memory allocation for variables}
Phase II is conceptually where the delocalized values get placed into
physical locations such as stack frame slots, registers, and global
data slots.  In this implementation, the allocation of space is
extremely simple-minded: all values are kept in physical memory
locations, and all temporaries are kept in the stack frame.  However,
because of the abstraction barrier erected between Phase II and the
other phases, we will later be able to optimize the allocation of
registers and stack fairly easily.

\subsection*{Phase Three: Generating actual code on the target machine}
%blah blah blah

For the calling convention, we selected n32 because it seemed in a few
ways better than o32. We liked being able to pass 8 values in
registers and not reverse space on the stack for them. We decided to
use the n32 calling convention between Decaf functions because it was
logical, we already had the code for from needing it for the library
callouts, and just in case one demented day we want to link against a
Decaf object file and have other functions call Decaf ones.\\

Our major tool in the codegen phase was the MIPSDelocalizedRegister,
which contained a MIPSRegister and implemented the DelocalizedLValue
interface. This allowed us to go almost directly from a listing of
DelocalizedInstructions to a listing of MIPS code. Since optimization
was not a strong concern in this phase of the project, we were able to
follow a rather simple instruction convention: load all values
required for the operation into a set of temp registers, do the
operation, put the result into the desired destination, with little
optimization or intelligence involved. However, our calling convention
routinely uses the same temp registers, and this seems like it will
allow a decent amount of optimization in the next phase.

\section*{Results}
Much to our delight, our compiler was able to pass all of the supplied
tests. Several of them stopped us up for a bit, but the clever notion
of inserting nops with comments flagging important features (like parts
of the calling convention) and xspim made it possible to debug these in
a reasonable amount of time. Boy is there a lot of room for optimizations
though. And more to the point, it actually works! :)

\end{document}
