\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 Low-level IR generation project}
\end{center}

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

\section*{Division of Labor}

As always, these are not cut and dried divisions of labor.\\

Chris: Initial conversion from high-level IR to low-level IR.\\

Mike: Pretty-printing and filling out some of the destructuring
routines. \\

Jim: Address space hacking. Keeping everything nice and flat.\\


\section*{Clarifications, Assumptions, Additions}

None.

\section*{Overview}

The purpose of this project was to be able to spit out as low-level an
IR as we could for a given Decaf program without actually knowing
anything about the underlying system that the program would eventually
be tasked to run on. We had to destructure and short-circuit our
elegant higher-level IR into a mass of pseudo-assembly, and then be
able to pretty-print what we had (which had technical difficulties of
its own). We also had to manage some address scoping issues, which
were made a lot easier by some of the simplifications inherent to Decaf.

\section*{Implementation Issues and Insights}

\subsection*{Low-level IR}
We destructure our high-level IR instructions into very simple low-level ones.
The major players are the following types of nodes, or low-level instructions:
\begin{enumerate}
\item {\bf enter} This node appears at the start of a method and
indicates how much space must be allocated on the stack for parameters
and locals when the method is invoked.
\item {\bf exit}  The complement to {\tt enter}, this will be our signal to
restore the stack pointer to its pre-invocation state.
\item {\bf nop} Do nothing, of course.
\item {\bf cbr} Conditional branch. If the given condition is true, then the
branch is taken to the specified label. Otherwise execution proceeds to the
next node.
\item {\bf st} Store a value in a memory location. The address and data must 
both be computed.
\item {\bf ld} Read a value from a memory location. The address must
be computed.
\item {\bf return} This instruction signals that the given value, once
computed, will be the return value of the method invocation. Then,
control must proceed to the {\tt exit} node of the method to terminate
its execution.  After a method is destructured we make an additional
pass to it to locate any return instructions and make sure their {\tt
next} node is the {\tt exit}.
\end{enumerate}

We also needed to handle short-circuiting of boolean expressions to
avoid unnecessary work (and to comply to the spec!). For this reason,
an {\tt if} expression with several booleans {\tt and}ed or {\tt or}ed
together is essentially broken into sub {\tt if} expressions, each
testing a different boolean, with sharing of the {\tt then} and {\tt
else} blocks as appropriate.

\subsection*{Pretty-printer}
Once we have destructured the entire program, it is necessary to print
out the low IR code for each method. The pretty-printer starts at the
first node in the method, an Enter node, and prints all the nodes that
are encountered from there on. Labels are created during the
destructuring process and only where they might be needed. The
candidate targets for branching are the two sub code blocks in an {\tt
if} statement (in case short-circuiting occurs), the node immediately
after an {\tt if}, the first node in the {\tt while} expansion, the
node after the body of a {\tt while}, and the {\tt exit} node. To show
what cycles in the graph look like, after a labeled node is printed
for the first time, subsequent references to that will use the notation
``---$>$ label.'' 


\subsection*{Flattened address space} 
To make this work, we calculated all of the offsets in an initial pass
through all of the symbol tables of the high-level IR. Then, we went
through the high-level IR and destructured, short-circuited and
flattened it into a low-level IR. We needed to store within our
variable descriptors (a) their offset and (b) whether or not they were
global variables. We store our offsets as RValues(a class that
includes a significant number of arithmetic operations in our IR), not
as ints - this allows us to build low-level instruction trees like
those shown in the lecture notes at the expense of having a bit more
overhead and having to process the RValue nodes when pretty-printing and
ultimately when compiling.

\newpage
\section*{Code}
Attached.

\section*{Known Problems and Wish List}
And and Or expressions are only short circuited if they appear as the
condition of a conditional branch instruction. We would need temporary
variables to do this properly, so we'll save this for codegen. Also,
we didn't code in the checks for array bounds yet, but we haven't
forgotten it-- just another task for codegen time.

\end{document}



