<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass{article}

\usepackage{hyperref}
\usepackage{listings}
\usepackage{minted}
\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{tikz}
\usetikzlibrary{positioning}
\usetikzlibrary{automata,arrows}

\newcommand{\mailto}[1]{\href{mailto:#1}{\nolinkurl{#1}}}

\lstset{
         basicstyle=\ttfamily
}

\title{Lesson 4 \\
  \vspace{0.5cm}
  \large \textit{Solutions}}
\author{Compiler Design I (Kompilatorteknik I) 2017}
\date{}

\begin{document}
\maketitle

\noindent
\begin{quote}
  \emph{DISCLAIMER: In the code listings of the following exercises we use a
    syntax that closely resembles C. However the C language allows neither
    nested function definitions (which appear in Exercise 2) nor true
    by-reference parameter passing (which some parts of Exercise 1 assume).}
\end{quote}

\section{Parameter passing}

Suppose we have the following program:

\begin{minted}[linenos, frame=single]{c}
  int foo(int a) {
    int b = a++;
    return b * a
  }

  int bar(int b) {
    return foo(b);
  }

  int main() {
    int c;
    c = 6;
    return bar(c);
  }
\end{minted}

Assume that the compiler allocates all the variables in the stack.

\vspace{1em}

The single arguments of \texttt{foo} and \texttt{bar} can be passed either
\emph{by-value} or \emph{by-reference}. \textbf{For each of the four possible
combinations} (i.e. both arguments \emph{by-value}, \texttt{foo}'s argument
\emph{by-value} \&amp; \texttt{bar}'s argument \emph{by-reference}, etc.) describe:
\begin{enumerate}
\item What kind of data should the compiler put in the argument slots of the
  activation records for the calls on lines 7 and 13?
\item What kind of assembly code will be necessary to retrieve the value of
  variable \texttt{a} on line 2?
\end{enumerate}

\newpage

\subsection*{Answer}

\indent The aim of this exercise is to show how compilers handle calling-by-value and
calling-by-reference.

First of all it is important to understand that the code for the called function
is generated once and should be able to retrieve the value of the passed
argument regardless of what has happened before. Other calls to each function
might also be present and should work with the same code.

Therefore, if the argument is passed by value, it is always the value that
should be in the activation record. Similarly, if the argument is passed by
reference, its value should be retrievable with a single
``dereference''. \footnote{If we allow the first argument to be passed
  directly in a register (e.g. \texttt{\$a0}), then the value or reference is
  what is stored in the register. The code in this case is:

\begin{itemize}
\item If \texttt{foo} uses call-by-value:

No code needed, the value is already in the register.

\vspace{1em}

\item If \texttt{foo} uses call-by-reference:

\texttt{lw \$a0, 0(\$a0)}
\end{itemize}
}

\vspace{1em}

With the previous in mind, to retrieve the value (question 1.2):
\begin{itemize}
\item If \texttt{foo} uses call-by-value:

\texttt{lw \$a0, OFFSET(\$FP)}

\vspace{1em}

\item If \texttt{foo} uses call-by-reference:

\texttt{lw \$t0, OFFSET(\$FP)}

\texttt{lw \$a0, 0(\$t0)}
\end{itemize}

\noindent(Here \texttt{OFFSET} is the specific offset for the slot of the
argument.)

\vspace{1em}

With these in mind, for question 1.1, the contents of the argument slots of the
activation records will be:

\begin{itemize}
\item \texttt{foo} uses call-by-value \&amp; \texttt{bar} uses call-by-value:

\vspace{1em}

Both slots will contain actual values (i.e. the numeric representation of 6).

\vspace{1em}

\item \texttt{foo} uses call-by-value \&amp; \texttt{bar} uses call-by-reference:

\vspace{1em}

The slot for the call on line 13 contains the address of the variable
\texttt{c}, whereas the slot for the call on line 7 contains the actual value
retrieved from that address before the call (i.e 6).

\vspace{1em}

\item \texttt{foo} uses call-by-reference \&amp; \texttt{bar} uses call-by-value:

\vspace{1em}

The slot for the call on line 13 contains the value of the variable \texttt{c}
at the time of the call (i.e. 6), whereas the slot for the call on line 7
contains the address of the previous slot.

\vspace{1em}

\item \texttt{foo} uses call-by-reference \&amp; \texttt{bar} uses call-by-reference:

\vspace{1em}

The slot for the call on line 13 contains the address of the variable
\texttt{c}, and the same address is copied in the slot for the call on line 7.
The compiler knows that the function received an argument by reference and has
to pass it on by reference, therefore it copies the original reference.
\end{itemize}

\section{Activation records and scoping}

In the following listing we show an excerpt of a program in a language that
allows nested definition of functions, is \emph{statically scoped} and uses
\emph{calls-by-value}:

\begin{minted}[linenos, frame=single]{c++}
 int spam(int a, int b) {
  int egg(int x) {
    return x*a mod b;
  }
  return egg(3);
 }
\end{minted}

Suppose we have in our \texttt{main()} function a call to \texttt{spam(7,13);}. 
Assume that the compiler allocates all the variables (named and temporary) on the 
stack.

\begin{enumerate}
\item What will be the return value of this call?
\item Give a diagram of the state of the stack right before the return of the
  call to function \texttt{egg} on line 3. Your diagram should contain at least
  the following information regarding the calls to \texttt{spam} and \texttt{egg} 
  functions (including the initial call):
  \begin{enumerate}
  \item boundaries of the activation records
  \item location of the actual parameters for the calls to these functions
  \item location of the return values
  \item location of the return addresses
  \item location and contents of the control links and access links
  \item \emph{Optional:} Location of temporary variables
  \item \emph{Optional:} Contents of actual parameters
  \end{enumerate}
\item Show where the values of the following variables are located in the stack
  and describe the code that should be generated by the compiler to access these
  values in the specified locations (including any points of reference, like the
  stack pointer). You may use as many registers as you like to calculate any
  addresses that are needed:
  \begin{enumerate}
    \item Variable \texttt{x} on line 3
    \item Variable \texttt{a} on line 3
  \end{enumerate}
\end{enumerate}

\newpage

\paragraph{Answers}
\subparagraph{What will be the return value of this call?}
$spam(7,13) = 3*7\ mod\ 13 = 8$
\subparagraph{Stack}
The general idea for a stack layout that supports nested function definitions would look like the following diagram:
\begin{center}
  \emph{figure omitted from source code, since it's just a PDF anyway}
  %% \includegraphics[scale=.7]{./content/stack.pdf}
\end{center}

Following this idea, the stack right before the return of the \texttt{call} to egg looks like the following diagram:
\begin{center}
  \emph{figure omitted from source code, since it's just a PDF anyway}
  %% \includegraphics[scale=.7]{./content/full_stack.pdf}
\end{center}
\newpage
\subparagraph{Code}
\texttt{x} is retrieved directly by accessing the function's parameter inside the function frame:
\begin{verbatim}
  lw $t0, -4($fp)
\end{verbatim}
\texttt{a} is retireved using the access link in the function's frame, as it is defined in a higher scope.
\begin{verbatim}
  lw $t0, -c($fp)
  lw $t0, -8($t0)
\end{verbatim}

This code assumes that values have the size of a word.

\section{Code generation}

Suppose that we want to generate code for the expression:

\begin{minted}{haskell}
cond
   &lt;p1&gt; =&gt; &lt;e1&gt;;
   &lt;p2&gt; =&gt; &lt;e2&gt;;
   ...
   &lt;pn&gt; =&gt; &lt;en&gt;;
      1 =&gt; &lt;e{n+1}&gt;
dnoc
\end{minted}

The evaluation of a \texttt{cond} expression begins with the evaluation of the
predicate \texttt{&lt;p1&gt;} (if it exists, n can also be zero). If \texttt{&lt;p1&gt;}
evaluates to a non-zero value, then \texttt{&lt;e1&gt;} is evaluated, and the
evaluation of the \texttt{cond} expression is complete. If \texttt{&lt;p1&gt;}
evaluates to zero, then \texttt{&lt;p2&gt;} is evaluated, and this process is repeated
until one of the predicates evaluates to a non-zero value. The value of the cond
expression is the value of the expression \texttt{&lt;ei&gt;} corresponding to the
first predicate \texttt{&lt;pi&gt;} that evaluates to a non-zero value. If all the
predicates evaluate to zero, then the value of the \texttt{cond} expression is
\texttt{e\{n+1\}}.

Write a code generation function: \texttt{cgen(cond &lt;p1&gt; =&gt; &lt;e1&gt;; ...; &lt;pn&gt; =&gt; &lt;en&gt;; 1 =&gt; &lt;e\{n+1\}&gt; dnoc)} for this conditional expression.

\paragraph{Answers}
\begin{verbatim}
 cgen(cond &lt;pi&gt; =&gt; &lt;ei&gt;; &lt;p{i+1}&gt; =&gt; e{i+1}; ... &lt;p2&gt; =&gt; e2; &lt;p2&gt; =&gt; e2;) {
  cgen(&lt;p1&gt;); // assumes that the result is stored in a0
  emit("li $t0 0");
  emit("beq $a0 %t0 next");
  cgen(&lt;e1&gt;);
  emit("b exiti");
  emit("nexti:");
  cgen(cond &lt;p{i+1}&gt; =&gt; &lt;e{i+1}&gt;; ... &lt;pn&gt; =&gt; &lt;en&gt;; 1 =&gt; e{n+1};);
  emit("exiti:");
 }
\end{verbatim}
\newpage

\section{Local optimizations}

Consider the following basic block, in which all variables are integers and
\texttt{**} denotes exponentiation:

\begin{lstlisting}
  a := b + c
  z := a ** 2
  x := 0 * b
  y := b + c
  w := y * y
  u := x + 3
  v := u + w
\end{lstlisting}

Assume that the only variables that are live at the exit of this block are
\texttt{v} and \texttt{z}. In order, apply the following optimizations to this
basic block. Show the result of each transformation.

\begin{enumerate}
\item algebraic simplification
\item common sub-expression elimination
\item copy propagation
\item constant folding
\item dead code elimination
\end{enumerate}

When you have completed part 5, the resulting program will still not be optimal.
What optimizations, in what order, can you apply to optimize the result of 5
further?

\paragraph{Answer}

\subparagraph{}

\begin{tabular}{lll}

1) Algebraic optimization: &amp;
2) Common sub-expression elimination: &amp;
3) Copy propagation: \\

\begin{lstlisting}
  a := b + c
  z := a * a
  x := 0
  y := b + c
  w := y * y
  u := x + 3
  v := u + w
\end{lstlisting}

&amp;

\begin{lstlisting}
  a := b + c
  z := a * a
  x := 0
  y := a
  w := y * y
  u := x + 3
  v := u + w
\end{lstlisting}

&amp;

\begin{lstlisting}
  a := b + c
  z := a * a
  x := 0
  y := a
  w := a * a
  u := 0 + 3
  v := u + w
\end{lstlisting}

\\
\\
\\

4) Constant folding: &amp; 
5) Dead code elimination: \\

\begin{lstlisting}
  a := b + c
  z := a * a
  x := 0
  y := a
  w := a * a
  u := 3
  v := u + w
\end{lstlisting}

&amp;

\begin{lstlisting}
  a := b + c
  z := a * a


  w := a * a
  u := 3
  v := u + w
\end{lstlisting}
\\
\\
\end{tabular}

Doing common sub-expression elimination, copy propagation, constant propagation and dead code elimination one more time, we get the final minimal form:

\begin{lstlisting}
  a := b + c
  z := a * a
  v := 3 + z
\end{lstlisting}

\section{Register allocation}

Consider the following program.

\begin{lstlisting}
  L0: e := 0
      b := 1
      d := 2
  L1: a := b + 2
      c := d + 5
      e := e + c
      f := a * a
      if f &lt; c goto L3
  L2: e := e + f
      goto L4
  L3: e := e + 2
  L4: d := d + 4
      b := b - 4
      if b != d goto L1
  L5:
\end{lstlisting}

This program uses six temporaries, \texttt{a}-\texttt{f}. Assume that the only
variable that is live on exit from this program is \texttt{e}. Draw the register
interference graph. (Drawing a control-flow graph and computing the sets of live
variables at every program point may be helpful.)

\paragraph{Answers}

First we draw the control flow graph:

\begin{tikzpicture}[-&gt;,&gt;=stealth',very thick]
  \tikzset{
    state/.style={
      rectangle,
      draw=black, very thick,
      inner sep=2pt,
      text centered
    },
  }

  \node[initial, state] (L0) {
    \begin{tabular}{c}
      \texttt{L0: e:= 0}\\
      $\{e\}$\\
      \texttt{b:= 0}\\
      $\{b,e\}$\\
      \texttt{d:= 2}\\
    \end{tabular}
};
  
  \node[state, right of=L0, node distance=13em] (L1) {
    \begin{tabular}{c}
      \texttt{L1: a := b + 2}\\
      $\{a,b,d,e\}$\\
      \texttt{c := d + 5}\\
      $\{a,b,c,d,e\}$\\
      \texttt{e := e + c}\\
      $\{a,b,c,d,e\}$\\
      \texttt{f := a * a}\\
      $\{b,c,d,e,f\}$\\
      \texttt{if f &lt; c goto L3}
    \end{tabular}
  };
  
  \node[state, above right of=L1, node distance=15em] (L2) {
    \begin{tabular}{c}
      \texttt{L2: e := e + f}\\
      $\{b,d,e\}$\\
      \texttt{goto L4}
    \end{tabular}
  };
  
  \node[state, below right of=L1, node distance=15em] (L3) {
    \texttt{L3: e := e + 2}
  };

  \node[state, right of=L1, node distance=15em] (L4) {
    \begin{tabular}{c}
      \texttt{L4: d := d + 4}\\
      $\{b,d,e\}$\\
      \texttt{b := b - 4}\\
      $\{b,d,e\}$\\
      \texttt{if b != d goto L1}
    \end{tabular}
  };
  
  \node[state, right of=L4, node distance=10em] (L5) {
    \texttt{L5:}
  };
    
  \path (L0) edge node[anchor=south,above]{$\{b,d,e\}$} (L1);
  \path (L1) edge node[anchor=south,left]{$\{b,d,e,f\}$} (L2);
  \path (L1) edge node[anchor=south,left]{$\{b,d,e\}$} (L3);
  \path (L2) edge node[anchor=south,right]{$\{b,d,e\}$} (L4);
  \path (L3) edge node[anchor=south,right]{$\{b,d,e\}$} (L4);
  \path (L4) edge node[anchor=south,above]{$\{b,d,e\}$} (L1);
  \path (L4) edge node[anchor=south,above]{$\{e\}$} (L5);
\end{tikzpicture}

The register interference graph is therefore:

\centering
\begin{tikzpicture}[]
  \tikzset{
    state/.style={
      circle,
      draw=black,
      very thick,
      minimum height=2em,
      node distance = 4em
  }}
  \node[state] (a) {$a$};
  \node[state, below right of=a] (b) {$b$};
  \node[state, right of=b] (c) {$c$};
  \node[state, above right of=c] (d) {$d$};
  \node[state, above left of=d] (e) {$e$};
  \node[state, left of=e] (f) {$f$};

  \path[-] (a) edge (b) edge (c) edge (d) edge (e);
  \path[-] (b) edge (c) edge (d) edge (e) edge (f);
  \path[-] (c) edge (d) edge (e) edge (f);
  \path[-] (d) edge (e) edge (f);
  \path[-] (e) edge (f);

\end{tikzpicture}

\end{document}
</pre></body></html>