\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 Register Allocation}
\end{center}

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

\section*{Division of Labor}

Mike wrote the ReachingDefinitions.java code and DUChains. He also
produced some scripts to automate regression testing which was a big
win. He fixed a bug in the last phase where DeadCodeElimination could
sometimes break {\tt if} constructs. Finally, he fixed the calling
convention to be more n32 compliant-- there was a problem with passing
more than 8 arguments, since n32 apparently (from empirical
observation with gdb and cc) wants to use 64 bit words for each
parameter passed on the stack. Callouts to printf with more than 8
args now work, for example. Finally, a bug in the last phase caused
``-opt all'' to imply ``-spim'' which it should not, so he fixed that
too. Oh, right, and he did the substituting-in Symbolic Registers
trick \'{a} la the Whale book also.

Jim wrote the initial version of DUChains (which Mike later fixed so
it would actually be useful), as well as all the code for Web, which
allows us to produce webs out of individual DUChains. He also wrote
the code for InterferenceGraph (and the slave class AdjacencyEntry)
which generates the interference matrix, produces a graph, and colors
it.  We simplified the SpillCost heuristic (in InterferenceGraph,
since that is where we color and spill the graph) in order to simplify
the data structure of DUChains and the overall problem of graph
coloring.

Chris created the "proxy" concept, which allowed variables to be
magically mutated from stack locals to registers without modifying the
CFG or losing any of the information about the original variables. He
also optimized our BinOp and Store instructions to use these proxies,
and fixed a good number of previous bugs.


\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 -all, -opt all}: Turn on both optimizations
\item {\tt -spim, -opt spim}: output SPIM code instead of MIPS
\end{itemize}

\section*{Overview, Implementation and Insights}

The goal is to make efficient use of registers and keep as much of the
data being operated on in registers as possible, to avoid the huge
penalties associated with accessing memory. We only use the callee-saved
registers at the moment, though there are a few spare caller-saved ones
which we could certainly add to the register pool without much trouble.
The only care that would need to be taken would be to spill them across
procedure calls -- this penalty is one of the reasons we didn't do this
from the start. 

It is worthy to note at what stage the register allocation is
performed.  The code is in a low-IR state (or DelocalizedInstructions
as we ended up calling it) which is just a hair above actual assembly
language. At this level, all the temporaries that are needed are
created and used are in the control flow graph, so we can easily
assign temporaries to registers too, since in most cases they live for
a short time and are used to quickly create intermediate results--
they need not live on the stack generally. Also, before we allocate
registers, we run the optimizations selected by the user. Copy propagation
and especially dead-code elimination do a wonderful job of both producing
faster code on their own, and also reducing the strain on the register
allocator as unneeded definitions can be removed along with the DUChain
that would have been created if they hadn't been.

\subsection*{ReachingDefinitions and DUChains}
The Reaching Definitions are computed using the standard fixed-point
seeking algorithm presented in class and in the Whale book. Specifically,
we created a subclass of our existing FixedPointAlgorithm class to
specify the few details specific to this algorithm. After the solution
is found, Definition-Use Chains (class DUChain) are built to describe
all of the uses each definition can reach. This information is needed 
to create webs and ultimately the interference graph. A DUChain object
is able to perform substitution on the value it holds a definition for
and propagate that change to all uses, when the time to plug in a symbolic
register comes (after webs are created). It also needs to be able to determine
if it intersects with a second DUChain in order to come up with the edges
in the interference graph.

\subsection*{Web}
A Web is a group of DUChains that DEFine the same variable and have at
least one overlapping USE of that variable. To achieve this, a Web
checks each DUChain that we try to add to it to see if it is related -
that is, if any of its USEs are mirrored in the DUChains already in
the Web data structure. Web also handles checking for interferences -
an interference (for the InterferenceGraph) is defined as one web
having any of its DUChains overlap with the DUChains of another
Web. (Overlap is defined as one DUChain starting within another.)

\subsection*{InterferenceGraph and AdjacencyEntry}
The InterferenceGraph class handles all the actual grunge of producing
an interference matrix and an adjacency graph, and coloring the graph.
The InterferenceGraph constructor takes in a vector of DUChains and a
MethodDescriptor (for register allocation purposes). We build all our
webs within the InterferenceGraph, then we produce a square
interference matrix (not triangular - I chose to take the performance
hit and make it a square array for ease in calculating number of
intersections). After the interference matrix is built, we build a
vector of AdjacencyEntries, containing our color (as yet unassigned),
spill cost (as yet unassigned), number of interferences and adjacent
AdjacencyEntry ``nodes'', and the underlying Web that we are trying to
allocate a register for. If we treat our AdjacencyEntries as nodes in
our graph we need to color, we have built our adjacency graph at this
point. We then color the graph with the algorithm presented in lecture
- we push nodes with degree $<$ R onto a stack and eliminate their
links in the graph. If we get to a point where there are no nodes with
degree $<$ R, we take the node with the lowest spillcost off the graph
and fail to place it on the stack. Once the graph is empty, we color
only those nodes on the stack - the default state for a symbolic
register (the underlying data structure that each Web/AdjacencyEntry
represents) is spilled, so we don't really have to generate spill code,
only proxy code (which Chris deals with).

\section*{Wish list}
There are certainly other optimizations our compiler could be taught
about, even beyond the scope of the projects. For example, with the
FixedPointAlgorithmClass and now the ReachingDefinitions class, adding
Constant Propagation would be fairly simple. Constant folding is also
a simple operation that could be combined into the routine which
currently performs algebraic simplification. Also, the assembly output
could be more debugger friendly, by putting the {\tt .ent}s on the
right side of the procedure label and specifying stack frames (though
as it was, gdb was very helpful in debugging the programs our compiler
produced). All of these additions are reasonably easy to implement
with a little time due to the current structure of
things. Additionally it would be nice to develop a framework for
performing the instruction flow optimizations that the Espresso folks
had to do. Another thing it would be nice to have is a switch that
toggles the generation of comments in the assembly output.  Currently,
this is achieved by commenting or uncommenting the one line of code in
MIPSCodegen.comment() which puts commented NOPs in to make it easier
to find your away around the code (an absolute must for debugging, but
a waste in terms of efficiency). And last, but not least, the ability
to pass arrays through callouts would let us run the Mandelbrot
program.

\section*{Results}
We ran our code on all of the provided test cases, and it worked on
all cases except for 12-huge.dcf. This case is absolutely huge which
makes it a bit harder to run through the assembly and debugging
output. The answers were actually quite close to correct, off by small
integral amounts, which we found odd (see Final/tests/*diff). We
speculate that two symbolic registers were allocated to the same
register due to a boundary condition on the code to detect overlaps,
or something similarly odd. As far as more positive results go, we
were also able to verify the output of the various stages of our
algorithms. We verified that we were producing the correct DUChains
for a few program, that we combined them into Webs properly, that the
graph was colored correctly, that the register allocation was sane,
and that the instruction count was reduced. A quick timing analysis
demonstrated the code did indeed run faster. We would have liked to
have had more time to track down the one bug preventing us from
correctly compiling 12-huge.dcf (and 16-huge-dead.dcf, which is the
same with more dead code tossed in); however, we did not have that
luxury.

\end{document}
