\documentclass[11pt]{article}

\input{../latex/compilerstoolbox.sty}
\usepackage{homework}
\usepackage{csquotes}
\usepackage{caption,subcaption} % for having nested figures
\usepackage{makecell} % for multi-line tabulars

\newcommand{\assdate}{Tuesday, January 28, 2025 (11:59pm)}
\newcommand{\assnum}{1}
\newcommand{\asstitle}{Backend}
\newcommand{\lecturer}{Seth, Ben, and co}
\setlength{\headsep}{0.2in}

\begin{document}
\maketitle

\noindent\textbf{Reminder:} Assignments are individual assignments,
not done in pairs.  The work must be all your own.

You should submit your assignment as a PDF on Gradescope. If you have
any trouble enrolling on Gradescope, please contact the course staff ASAP.
Please read the late policy for written assignments on the course web page.


\section*{Problem 1: Code Generation (20 points)}

\begin{enumerate}
\item [(a)] Consecutive statements in a program can be represented in
  an AST by a \verb"seq" node that has two statements (possibly other
  \verb"seq"s) as children. For example, the program
\begin{verbatim}
   int x;
   x = 5 + 3;
   return x;
\end{verbatim}
  could be represented in an AST as
\begin{verbatim}
  declare("x", seq(assign("x",
                               plus(const(5), const(3))),
                        return(var("x"))))
\end{verbatim}

  The variable \verb"x" is declared for only a portion of the AST.
  This is achieved via a \verb"declare" node, the first subtree of
  which is a variable, and the second a subtree which the variable is
  declared for (called the \emph{scope} of the variable).

  Using this type of AST (see Figure \ref{fig:ast}), write
  down the AST for the following L1 program. Declarations that
  initialize the variable should be elaborated into a simple
  declaration followed by an assignment.

  \begin{figure}
    \begin{subfigure}[b]{.5\linewidth}
      \centering
      \begin{verbatim}
        datatype stmt =
            declare of string * stmt
          | seq of stmt * stmt
          | assign of string * expr
          | return of expr
      \end{verbatim}
      \vspace{29pt} % this aligns the top of the figures for some reason (??)
    \end{subfigure}
    \begin{subfigure}[b]{.5\linewidth}
      \centering
      \begin{verbatim}
        datatype expr =
            var of string
          | const of int
          | negate of expr
          | plus of expr * expr
          | mult of expr * expr
          | mod of expr * expr
          | div of expr * expr
      \end{verbatim}  
    \end{subfigure}
    \caption{AST datatypes}
    \label{fig:ast}
  \end{figure}

  Be sure to parse the code according to L1's specified
  precedence rules, which are the usual mathematical order of operations.

\begin{verbatim}
  int x;
  x = 1 + 2 * 3 + (-9);
  int y = (x + 2) / 4;
  return x % y;
\end{verbatim}

\item[(b)] When you extend from L1 to L2, you will need to extend the AST type
  to represent the new features. Write down a potential AST for the
  following program, extending the type in Figure \ref{fig:ast} with
  a reasonable AST representation for
  \verb'while', \verb'+=', and \verb'!=' (not equal). Assume
  that the variables \verb"x" and \verb"y" are declared elsewhere, but
  notice that the variable \verb"z" is only declared within the
  while loop.

\begin{verbatim}
  while (x != 5) {
    int z = x * x;
    y += z;
    x = x + 1;
  }
  return y;
\end{verbatim}

\item [(c)] Now you will perform instruction selection on the AST you created
in part (a) into three-operand assembly language by using the patterns in the
table below.  As a sample, the example AST from part (a) would be translated
(in a simplistic fashion) to the following program. Note that we, other than in class,
assume that the return instruction takes an operand to be returned as an argument.
\begin{verbatim}
  t0 <- 5
  t1 <- 3
  x <- t0 + t1
  t3 <- x
  ret t3
\end{verbatim}
We aren't performing register allocation yet (that's for problem 2),
so we will continue to refer to variables by their names and generate
new temp variables as necessary. Use top-down code generation just as
described in lecture, with no optimizations (see Figure \ref{fig:codegen}).

\begin{figure}
  \renewcommand{\cellalign}{lc} % for makecell alignment
  \setlength{\tabcolsep}{1em} % for horizontal padding
  \renewcommand{\arraystretch}{1.25} % for vertical padding
  \begin{subfigure}[b]{.5\linewidth}
    \begin{tabular}{|c|c|}
      \hline
      $ s                $  & $ \m{cogen}(s)                    $ \\
      \hline\hline
      $ \m{declare}(x,s) $  & $ \m{cogen}(s)                    $ \\ \hline
      $ \m{assign}(x,e)  $  & $ \m{cogen}(x,e)                  $ \\ \hline
      $ \m{return}(e)    $  & \makecell{
                                $ \m{cogen}(t,e)  $ \\
                                $ \m{ret}\, t     $
                              } \\ \hline
      $ \m{seq}(s_1, s_2) $ & \makecell{
                                $ \m{cogen}(s_1)  $ \\
                                $ \m{cogen}(s_2)  $
                              } \\ \hline
    \end{tabular}
  \end{subfigure}
  \begin{subfigure}[b]{.5\linewidth}
    \centering
    \begin{tabular}{|c|c|}
      \hline
      $e$                   & $ \m{cogen}(d,e)         $ \\
      \hline\hline
      $\m{const}(c)     $   & $ d \leftarrow c         $ \\ \hline
      $\m{var}(x)       $   & $ d \leftarrow x         $ \\ \hline
      $\m{negate}(e_1)  $   & \makecell{
                                $ \m{cogen}(t_1)    $ \\
                                $ d \leftarrow -t_1 $ 
                              } \\ \hline
      $\m{plus}(e_1, e_2) $ & \makecell{
                                $ \m{cogen}(t_1,e_1)     $ \\
                                $ \m{cogen}(t_2,e_2)     $ \\
                                $ d \leftarrow t_1 + t_2 $
                              } \\ \hline
      $\m{times}(e_1, e_2) $& \makecell{
                                $ \m{cogen}(t_1,e_1)     $ \\
                                $ \m{cogen}(t_2,e_2)     $ \\
                                $ d \leftarrow t_1 * t_2 $
                              } \\ \hline
      \ldots                & \ldots
    \end{tabular}
  \end{subfigure}
  \caption{
    Top-down code generation rules for statements (l) and expressions (r).
    Temporaries ($t, t_1, t_2$) in each rule are assumed to be fresh.
  }
  \label{fig:codegen}
\end{figure}

\end{enumerate}


\clearpage

\section*{Problem 2: Register Allocation (25 points)}

In this question you will perform the register allocation algorithm
discussed in class on a small assembly program which computes
$\log_2(6x-2)+1$ (in the code given, the input $x$ is hardcoded to be
42).

The target of your compilation will be a three-address machine with as
many registers as you need (though the algorithm will still be trying
to use as few as possible).  The registers are named
$r_0, \ldots, r_n$.

\begin{quote}
\begin{verbatim}
  L00: t0 <- 42 // "input"
  L01: t1 <- 6
  L02: t2 <- t0 * t1
  L03: t3 <- 2
  L04: t4 <- t2 - t3
  L05: t5 <- 1
  L06: t6 <- 0
  L07: t7 <- 1

  label .loop
  L08: t4 <- t4 >> t5 
  L09: t6 <- t6 + t7
  L10: branch t4 .loop .exit

  label .exit
  L11: ret t6
\end{verbatim}
\end{quote}


\begin{enumerate}

\item[(a)] Compute the live-out sets for each line in the above program.
  The definition of live-out is as follows:

\renewcommand{\succ}[1]{\text{succ}\left(#1\right)}
\newcommand{\uses}[1]{\text{Uses}\left(#1\right)}
\newcommand{\defs}[1]{\text{Defs}\left(#1\right)}
\newcommand{\livein}[1]{\text{LiveIn}\left(#1\right)}
\newcommand{\liveout}[1]{\text{LiveOut}\left(#1\right)}

\begin{itemize}
  \item $\succ{l} =$ set of lines that could immediately follow $l$
  \item $\uses{l} =$ set of variables whose value is used in line $l$
  \item $\defs{l} =$ set of variables defined in line $l$
  \item $\livein{l} = \left(\liveout{l} - \defs{l}\right) \cup \uses{l}$
  \item $\liveout{l} = \bigcup_{s \in \succ{l}} \livein{s}$
\end{itemize}

\item[(b)] Construct the interference graph for the program. If you
  don't want to actually draw a graph, you can just list the variables
  that each variable interferes with. You should also state whether
  the graph is chordal.

  Recall that two variables $x, y$ interfere if at some line $l$,
  $x \in \defs{l}$ and $y \in \liveout{l}$.

\item[(c)] Use the maximum cardinality search algorithm we described
  in lecture, starting from \verb't7', to construct a simplicial elimination
  ordering. Then, using this ordering, use the greedy graph coloring described
  in class to assign registers $r_0, \ldots, r_n$ to temps.

\end{enumerate}

Now we will add a restriction to our three-address assembly language:
the register $r_0$ \textit{must} be used as the return register (in
other words, the operand of \verb'ret' must be \verb'r0'). Similarly,
in the shift instruction \( d \leftarrow s_1 \;\mbox{\tt >>}\; s_2 \),
the same register $r_0$ \textit{must} be to hold $s_2$, the magnitude
of the shift.
\footnote{These restrictions are \textit{definitely not}
foreshadowing the restrictions you may encounter in x86\_64 assembly\dots}

\begin{enumerate}

\item[(d)] Why does this represent a problem for our sample program?
  Give a slightly modified but equivalent version of the
  program that does not have this problem.

\item[(e)] Do the graph coloring algorithm like in 1(c) on this modified program.
This time, allocate your registers in a way such that $t_7$ is assigned to the
register with the highest possible number, and explain how you did this.

\end{enumerate}


\clearpage

\section*{Problem 3: Chordal Graphs \& SSA (10 points)}

Recall that a \textit{chordal} graph is a graph where every cycle of
length 4 or larger contains a chord (an edge that connects to vertices
on the cycle but is not part of the cycle).

\begin{enumerate}

\item[(a)] Write a program in three-address assembly that has a
  non-chordal interference graph and uses not more than 4 temps. Draw
  the interference graph.

\item[(b)] Rename the temps in your program so that you get an
  equivalent program that assigns every temp at most once (the
  resulting program is in SSA form). Draw the interference graph of
  the modified program. Is the graph chordal?

\end{enumerate}


\clearpage

\section*{Problem 4 (0 points, optional)}

A relevant quote from Stephen Dolan:
\begin{quote}
It is well-known that the x86 instruction set is baroque, overcomplicated, and
redundantly redundant. We show just how much fluff it has by demonstrating that
it remains Turing-complete when reduced to just one instruction.
\end{quote}

\noindent Did you know that all of instruction selection is bogus? We're going to
(partially) show that we don't need any instructions other than \verb+mov+ to
implement an L1 compiler.

\begin{enumerate}

\item[(a)] Assuming $x$ and $y$ are registers containing two possibly equal
values, and we'd like $R$ to contain a 1 if they're equal and 0 if not. Write
three lines of x86 assembly that checks for equality using only \verb+mov+
instructions.

\item[(b)] So why aren't we just doing this instead? In 1 sentence, explain why
it \textit{might} not make sense to compile all code to only \verb+mov+ instructions.

\end{enumerate}

\end{document}
