\documentstyle[fullpage]{article}
\begin{document}
{\noindent \huge 6.035 Codegen 2b$_2$\hfill LE25}

\section{Register Coloring}

The registers are allocated using the {\tt intergraph} cluster:

\begin{verbatim}
intergraph = cluster is create, color

    node = struct[v:var, neighbors:set[int]]
    rep = sequence[node]

    create = proc(first:block, blocks:sequence[block], vars:sequence[var])
        returns(cvt)

    color = iter(graph:cvt) yields(var, int)

  end
\end{verbatim}
\noindent {\tt intergraph\$create} takes in a list of {\tt block}s and
a list of {\tt var}s, and iterates over the {\tt statement}s using the
live variable information (which existed in Codegen 2a for dead code
elimination) to determine the graph connections.

\noindent{\tt intergraph\$color} then colors the graph using essentially the
algorithm in the book.

\section{The One Size Doesn't Fits All Relaxation}

Originally, we tried to have one relaxation that would compute both
reaching definitions and available expressions. However, after missing
the deadline for codegen2b we realized that two seperate relaxtions
were better. Since the code for the two relaxations is almost
identical except for a few conditions here and there, they are both
implemented by the same routines in avail.clu. 

The key differences between our reaching definitions and our available
expressions is that our reaching definitions are the union of all
definitions that reach a point while the available expressions are the
intersection. Additionally, reaching definitions are only killed when
their LHS is assigned to while available expressions are killed when
either their LHS or their RHS is assigned to.

The three `propagation' optimizations (constant propagation, copy
propagation, and CSE) are all done at the same time, since (1) each
helps the others to work better, and (2) they work on orthogonal sets
of information (constant {\tt rhs}es, {\tt rvalue rhs}es, and {\tt
binary\_op rhs}es), so they don't interfere with each other.

We don't attempt to fully canonicalize expressions. However, we do
handle recognizing the same expression in different orders (ex. {\tt
a+b} and {\tt b+a} are recognized as being the same). Repeated
applications of the three optimizations should achieve the same end
result.

Since CSE and constant propagation are done at the same time, it
seemed silly to have separate flags for them, so they (and copy
propagation) both fall under `{\tt -cp}'.

\section{Division of Labor}
\begin{itemize}
\item[Greg] - graph coloring, bug fixes from 2a
\item[Dan] - modifications to {\tt codehoist.clu}, bug fixes from 2a
\item[Tom] - {\tt avail.clu}, testing of new code, 2b$_2$ fixes
\item[Hector] - {\tt propagate.clu}, testing of new code, 2b$_2$ fixes
\end{itemize}
\end{document}