\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 Datapath Optimizations}
\end{center}

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

\section*{Division of Labor}

Chris wrote the algebraic simplifications and the toplevel of the
CopyPropagation FPA extension.  Jim wrote the DeadCodeElimination FPA
extension, and Mike wrote FixedPointAlgorithm.java and several of its
friends. As usual, each member of the team at one point had full and
solitary access to the entire code base and frobbed with things not
directly under his jurisdiction.

\section*{Clarifications, Assumptions, Additions}

To access the optimizations, use these switches on the command line:
\begin{itemize}
\item {\tt -cp, -opt cp}:  Copy propagation
\item {\tt -dce, -opt dce}: Dead code elimination
\item {\tt -spim, -opt spim}: output SPIM code instead of MIPS
\end{itemize}

\section*{Overview}

This project was directed towards datapath optimization - cutting out
pointless add's, sub's, mulo's, loads and stores in the finished
code. We attempted to implement 3 types of datapath optimization for
this project, and in addition implemented a rather general framework
for running any given FixedPointAlgorithm on a class.\\

\section*{Implementation and Insights}
Our overall implementation took 2 paths. First, we implemented
algebraic simplification as an integral part of our low-level
intermediate representation. Our algebraic simplification cannot be
turned off - then again, we decided that nobody in their right minds
would want to do so.\\

Next, we implemented two fixed-point algorithms, dead code elimination
and copy propagation, by creating a FixedPointAlgorithm class that
would perform a generic FPA optimization on a CFG of
DelocalizedInstructions (one step above machine code), and then
extending the FPA class to DeadCodeElimination.java, a
backward-traversing variable-based FPA, and CopyPropagation.java, a
forward-traversing expression-based FPA.\\

\section*{Specific datapath improvements}
\subsection*{Algebraic simplifications}
Algebraic simplification makes use of the Traversable nature of our
DelocalizedInstruction CFG to clean up any stray constants. This is
handled in IR2/MethodDescriptor.java. and makes use of the Traversal
class and Traversable interface.

\subsection*{Traversable interface}
The Traversable interface was initially a general helper set of
functions for performing algebraic simplifications (by traversing a
CFG of DelocalizedInstructions) and for producing the BasicBlock
``scaffolding'' and for walking down the scaffolding to execute a
FixedPointAlgorithm.

\subsection*{CFG (Control Flow Graph)}
We use a Control Flow Graph (CFG) to keep track of where our
DelocalizedInstructions are. DelocalizedInstructions are the
successors to the lowIR we had in phase 4 of the compiler project.

\subsection*{FixedPointAlgorithm structure}

Our FixedPointAlgorithm is a model of the framework given in class,
with as much code that was considered independent of the actual
subclass algorithms tossed in as possible, to keep things sane and
reduce code duplication and in the interests of building an expandable
system.\\
We encountered a slight problem in that the abstract class was
finished before either of the below concrete classes were implemented,
so the initial debugging was a little tough.  However, once we knew
that FPA was solid, it simplified debugging.

\subsection*{BasicBlock ``scaffolding''}
In order to run our FixedPointAlgorithm on our code, we created the
BasicBlock class. We construct a graph of BasicBlocks, each of which
point to the start and end DelocalizedInstruction within the
BasicBlock.  This way, we construct a ``scaffolding'' which we use to
run subclasses of FixedPointAlgorithm over our otherwise cumbersome
CFG of DelocalizedInstructions.

\subsection*{DeadCodeElimination and CopyPropagation extensions of FPA}
Dead Code Elimination is a backwards-traversal fixed point algorithm,
with a union confluence operator. It operates on variables. Copy
Propagation is a forward-traversal fixed point algorithm, with an
intersection confluence operator. It operates on expressions. We
implement a generate and a kill method within the concrete classes,
which FixedPointAlgorithm calls to produce the gen/kill sets. We also
implement the setInitialConditions method within the concrete classes
(as they are specific to the type of optimization being performed) and
the core optimize() function also resides within the concrete classes.
MethodDescriptor calls a FixedPointAlgorithm's getFixedPoint method,
which calculates in/out sets for each BasicBlock being optimized, sets
each BasicBlock's initial conditions, and calls optimize() on each in
turn.

\section*{Results}
\subsection*{Order of Operations}
We perform copy propagation before we perform dead code elimination,
thus using the dead code elimination to clean up propagated copies
that we don't need.
\subsection*{Algebraic Simplification}
Please see test 18-algebraic.dcf in our Dataflow/tests directory.
{\bf 18-algebraic.dcf}
\begin{verbatim}
class Program
{
    void main()
    {
	int a;

	a = 1 * 2 + 3 - 4 * 5 - 6 + 7 * 8;
	callout("printf", "should be something or other: %d\n", a);
    }
}
\end{verbatim}
\subsection*{Copy Propagation}
This is a diff of a portion of 02-expr.dcf, found in our tests
directory off of our Dataflow directory. Note the fact that several
loads have been changed to load from the local variables at -36 and
-32 on the stack.
\begin{verbatim}
> gdiff -u testcopy2.{unopt,opt}
--- testcopy2.unopt Sun Nov 28 19:16:47 1999
+++ testcopy2.opt   Sun Nov 28 19:18:00 1999
@ -56,19 +56,19 @
    sw $25,-36($30)
    lw $15,-36($30)
    sw $15,-28($30)
-   lw $15,-28($30)
+   lw $15,-36($30)
    sw $15,-16($30)
-   lw $15,-28($30)
+   lw $15,-36($30)
    lw $24,0($23)
    add $25,$15,$24
    sw $25,-32($30)
    lw $15,-32($30)
    sw $15,-24($30)
-   lw $15,-24($30)
+   lw $15,-32($30)
    sw $15,-12($30)
-   lw $15,-16($30)
+   lw $15,-36($30)
    sw $15,-20($30)
-   lw $15,-24($30)
+   lw $15,-32($30)
    sw $15,-28($30)
 label_1:
    nop     # test's epilogue
\end{verbatim}
%$
\subsection*{Dead Code Elimination}
A sample of Decaf code containing dead code is provided below and in
our repository under tests/03a-math-dead.dcf. We compiled this code
with DCE turned both on and off, and we trimmed out the two offending
dead code statements.\\
{\bf The Code:}\\
\begin{verbatim}
class Program
{
    void main () 
    {
        int i1, i2;
    
        i1 = -2147483647 - 1;
        callout("printf","min int operation: result should be -2147483648, is: %d\n",i1);
        i1 = (100-50)*2;
  	callout("printf","paren assoc: result should be 100, is: %d\n",i1);
  	i1 = 100 - 50 - 40;
        callout("printf","- assoc: result should be 10, is: %d\n",i1); 
  	i1 = 100 - 50 + 40;
        callout("printf","-,+ assoc: result should be 90, is: %d\n",i1);
  	i1 = 100 - 5 * 4;
        callout("printf","- * assoc: result should be 80, is: %d\n",i1);
  	i2 = 10 * 5 - 4;
        callout("printf","result should be 46, is: %d\n",i2);
  	i1 = ----3;
	i2 = 1 + 1;
        callout("printf","uminus: result should be 3, is: %d\n",i1);
  	i1 = 3;
	i1 = 3 + 4;
  	i1 = i1 * i1 - -2;
        callout("printf","*, -, uses var: result should be 11, is: %d\n",i1);
        i1 = 3 * 4 - 2 * 5;
        callout("printf","*,- assoc: result should be 2, is: %d\n",i1);
    }
}
\end{verbatim}
{\bf The diff:}\\
\begin{verbatim}
--- 3a-opt      Mon Nov 29 10:32:10 1999
+++ 3a-unopt    Mon Nov 29 10:31:31 1999
@@ -143,6 +143,8 @@
        li $24,1
        add $25,$15,$24
        sw $25,-96($30)
+       lw $15,-96($30)
+       sw $15,-12($30)
        nop             # Function call: 2 args, 0 callersaves, 0 padding
        nop             # Placement of arguments
        lw $5,-16($30)
@@ -151,6 +153,8 @@
        nop             # Clean up from callout
        nop             # Function callout sequence completed
        sw $2,-92($30)
+       li $15,3
+       sw $15,-16($30)
        li $15,3
        li $24,4
        add $25,$15,$24
\end{verbatim}
\end{document}
