afl-material: comparison handouts/ho09.tex

equal deleted inserted replaced

-:0138618eff73
+:a04efdd5e7a3
 for this ease is that the JVM is a stack-based virtual machine and it
 is therefore not hard to translate deeply-nested arithmetic
 expressions into a sequence of instructions manipulating the
 stack. The problem is that ``real'' CPUs, although supporting stack
 operations, are not really designed to be \emph{stack machines}.  The
-design of CPUs is more like: Here are some operations and a chunk of
+design of CPUs is more like: Here are some instructions and a chunk of
 memory---compiler, or better compiler writers, do something with
 them. Consequently, modern compilers need to go the extra mile in
 order to generate code that is much easier and faster to process by
 actual CPUs, rather than running code on virtual machines that
 introduce an additional layer of indirection. To make this all
 tractable for this module, we target the LLVM Intermediate
 Language. In this way we can take advantage of the tools coming with
 LLVM.\footnote{\url{http://llvm.org}} For example we do not have to
-worry about things like register allocations. By using LLVM, however,
+worry about things like register allocations. By using the LLVM-IR,
-we also have to pay price in the sense that generating code gets
+however, we also have to pay price in the sense that generating code
-harder\ldots{}unfortunately.
+gets harder\ldots{}unfor\-tunately.
-\subsection*{LLVM and LLVM-IR}
+\subsection*{LLVM and the LLVM-IR}
 \noindent LLVM is a beautiful example
 that projects from Academia can make a difference in the World. LLVM
 started in 2000 as a project by two researchers at the  University of
 Illinois at Urbana-Champaign. At the time the behemoth of compilers was
 We will target the LLVM Intermediate Language, or LLVM Intermediate
 Representation (short LLVM-IR). The LLVM-IR looks very similar to the
 assembly language of Jasmin and Krakatau. Targetting LLVM-IR will also
 allow us to benefit from the modular structure of the LLVM compiler
-and we can let, for example, the compiler generate code for different
+and we can let the compiler generate code for different CPUs, for
-CPUs, say X86 or ARM.  That means we can be agnostic about where our
+example X86 or ARM.  That means we can be agnostic about where our
 code is actually going to run.\footnote{Anybody want to try to run our
 programs on Android phones?}  We can also be somewhat ignorant about
 optimising our code and about allocating memory efficiently: the LLVM
 tools will take care of all this.
 However, what we have to do in order to make LLVM to play ball is to
 generate code in \emph{Static Single-Assignment} format (short SSA),
 because that is what the LLVM-IR expects from us. A reason why LLVM
-uses the SSA format, rather than JVM-like stack instructions, is that
+uses the SSA-format, rather than JVM-like stack instructions, is that
 stack instructions are difficult to optimise---you cannot just
 re-arrange instructions without messing about with what is calculated
 on the stack. Also it is hard to find out if all the calculations on
 the stack are actually necessary and not by chance dead code. The JVM
 has for all these obstacles sophisticated machinery to make such
 ourselves. This means we have to work around the intricacies of what
 instructions CPUs can actually process fast. This is what the SSA
 format is designed for.
-The main idea behind the SSA format is to use very simple variable
+The main idea behind the SSA-format is to have sequences of very
-assignments where every tmp-variable is assigned only once. The
+simple variable assignments where every (tmp)variable is assigned only
-assignments also need to be primitive in the sense that they can be
+once. The assignments need to be simple in the sense that they can be
-just simple operations like addition, multiplication, jumps,
+just be primitive operations like addition, multiplication, jumps,
 comparisons, function calls and so on.  Say, we have an expression
-$((1 + a) + (foo(3 + 2) + (b * 5)))$, then the corresponding SSA format is
+$((1 + a) + (foo(3 + 2) + (b * 5)))$, then the corresponding sequence
+of assignments in SSA-format are:
 \begin{lstlisting}[language=LLVMIR,numbers=left]
 let tmp0 = add 1 a in
 let tmp1 = add 3 2 in
 let tmp2 = call foo(tmp1)
 let tmp4 = add tmp2 tmp3 in
 let tmp5 = add tmp0 tmp4 in
 return tmp5
 \end{lstlisting}
-\noindent where every tmp-variable is used only once (we could, for
+\noindent where every tmpX-variable is used only once (we could, for
 example, not write \texttt{tmp1 = add tmp2 tmp3} in Line 5 even if this
-would not change the overall result).
+would not change the overall result). At the end we have a return-instruction
+wich contains the final result of the expression.
 There are sophisticated algorithms for imperative languages, like C,
-that efficiently transform a high-level program into SSA format. But
+that efficiently transform high-level programs into SSA-format. But
 we can ignore them here. We want to compile a functional language and
 there things get much more interesting than just sophisticated. We
 will need to have a look at CPS translations, where the CPS stands for
-Continuation-Passing-Style---basically black programming art or
+\emph{Continuation-Passing-Style}---basically black programming art or
 abracadabra programming. So sit tight.
 \subsection*{LLVM-IR}
 Before we start, let's however first have a look at the \emph{LLVM Intermediate
 \end{lstlisting}
 \begin{figure}[t]\small
 \lstinputlisting[language=LLVM,numbers=left]{../progs/sqr.ll}
 \caption{An LLVM-IR program for calculating the square function. It
-calls the sqr-function in \texttt{@main} with the argument \texttt{5}
+calls the \texttt{sqr}-function in \texttt{@main} with the argument \texttt{5}
 (Line 20). The
-code for the \texttt{sqr} function is in Lines 13 -- 16. It stores
+code for the \texttt{sqr}-function is in Lines 13 -- 16. It stores
-the result of sqr in the variable called \texttt{\%i} and then
+the result of sqr in the variable called \texttt{\%1} and then
 prints out the contents of this variable in Line 21. The other
 code is boilerplate for printing out integers.\label{lli}}
 \end{figure}
 Here \texttt{tmp3} will contain the result of what the whole
 expression stands for. In each individual step we can only perform an
 ``atomic'' or ``trival'' operation, like addition or multiplication of
 a number or a variable.  We are not allowed to have for example a
 nested addition or an if-condition on the right-hand side of an
-assignment. Such constraints are forced upon us because of how the SSA
+assignment. Such constraints are forced upon us because of how the
-format works in the LLVM-IR. To simplify matters we represent
+SSA-format works in the LLVM-IR. To simplify matters we represent
 assignments with two kinds of syntactic entities, namely
 \emph{K-values} and \emph{K-expressions}. K-values are all ``things''
-that can appear on the right-hand side of an equal. Say we have
+that can appear on the right-hand side of an equal. Say we have the
-the following definition for K-values:
+following definition for K-values:
 \begin{lstlisting}[language=Scala,numbers=none]
 enum KVal {
 case KVar(s: String)
 case KNum(n: Int)
 where a K-value can be a variable, a number or a ``trivial'' binary
 operation, such as addition or multiplication. The two arguments of a
 binary operation need to be K-values as well. Finally, we have
 function calls, but again each argument of the function call needs to
 be a K-value.  One point we need to be careful, however, is that the
-arguments of the binary operations and function calls are in fact only
+arguments of the binary operations and function calls can in fact only
-variables or numbers. To encode this constraint into the type-system
+be variables or numbers. To encode this constraint into the type-system
-of Scala would make things too complicated---to satisfy this
+of Scala, however, would make things too complicated---to satisfy this
 constraint is therefore on us. For our Fun-language, we will later on
 consider some further K-values.
 Our K-expressions will encode the \texttt{let} and the \texttt{return}
 \end{lstlisting}
 \noindent
 By having in \texttt{KLet} taking first a string (standing for an
 intermediate variable) and second a value, we can fulfil the SSA
-constraint in assignments ``by construction''---there is no way we
+constraint in assignments ``by con\-struction''---there is no way we
 could write anything else than a K-value.  Note that the third
 argument of a \texttt{KLet} is again a K-expression, meaning either
 another \texttt{KLet} or a \texttt{KReturn}. In this way we can
 construct a sequence of computations and return a final result.  Of
 course we also have to ensure that all intermediary computations are
 given (fresh) names---we will use an (ugly) counter for this.
 To sum up, K-values are the atomic operations that can be on the
 right-hand side of assignemnts. The K-language is restricted such that
-it is easy to generate the SSA format for the LLVM-IR. What remains to
+it is easy to generate the SSA-format for the LLVM-IR. What remains to
 be done is a translation of our Fun-language into the K-language. The
-main difficulty is that we need to order the computationa---in teh
+main difficulty is that we need to order the computation---in the
-K-language we only have linear sequence of instructions to need to be
+K-language we only have linear sequence of instructions. Before we
-followed. Before we explain this, we have a look at some
+explain this, we have a look at some CPS-translation.
-CPS-translation.
 \subsection*{CPS-Translations}
-CPS stands for Continuation-Passing-Style. It is a kind of programming
+CPS stands for \emph{Continuation-Passing-Style}. It is a kind of programming
 technique often used in advanced functional programming. Before we delve
-into the CPS-translation for our Fun-language, let us look at
+into the CPS-translation for our Fun-language compiler, let us look at
 CPS-versions of some well-known functions. Consider
 \begin{lstlisting}[language=Scala, numbers=none]
 def fact(n: Int) : Int =
 if (n == 0) 1 else n * fact(n - 1)
 factC(3, identity)
 \end{lstlisting}
 \noindent
-This function is called with the number, in this case 3, and the
+This function is called with a number, in this case 3, and the
 identity-function (which returns just its input). The recursive
 calls are:
 \begin{lstlisting}[language=Scala, numbers=none]
 factC(2, x => identity(3 * x))
 (1 + 1) + 1
 3
 \end{lstlisting}
 \noindent
-The point of this section is that you are playing around with these
+The point of this section is that you should be playing around with these
 simple definitions and make sure they calculate the expected result.
 In the next step, you should understand \emph{how} these functions
 calculate the result with the continuations.
 \section*{Worked Example}
-Let us now come back to the CPS-translations for the Fun-language. The
+Let us now come back to the CPS-translations for the Fun-language.
-main difficulty of generating instructions in SSA format is that large
+Though we will start with a simpler subset containing only numbers,
-compound expressions need to be broken up into smaller pieces and
+arithmetic expressions and function calls.  The main difficulty of
-intermediate results need to be chained into later instructions. To do
+generating instructions in SSA-format is that large compound
-this conveniently, we use the CPS-translation mechanism. What continuations
+expressions need to be broken up into smaller pieces and intermediate
+results need to be chained into later instructions. To do this
+conveniently, we use the CPS-translation mechanism. What continuations
 essentially solve is the following problem: Given an expressions
 \begin{equation}\label{exp}
 (1 + 2) * (3 + 4)
 \end{equation}
 \noindent
-which of the subexpressions should be calculated first? We just arbitrarily
+which of the subexpressions should be calculated first? We just
-going to decide that it will be from left to right. This means we have
+arbitrarily going to decide that it will be from left to right. Other
-to tear the expression shown in \eqref{exp} apart as follows:
+languages make different choices---C famously is right to left. In our
+case this means we have to tear the expression shown in \eqref{exp}
+apart as follows:
 \[
 (1 + 2) \qquad\text{and}\qquad  \Box * (3 + 4)
 \]
 \noindent
-The first one will give us a result, but the second one is not
+The first subexpression can be calculated and will give us a result,
-really an expression that makes sense. It will only make sense
+but the second one is not really an expression that makes sense. It
-as the next step in the computation when we fill-in the result of
+will only make sense as the next step in the computation when we
-$1+2$ into the ``hole'' indicated by $\Box$. Such incomplete
+fill-in the result of $1+2$ into the ``hole'' indicated by
-expressions can be represented in Scala as functions
+$\Box$. Such incomplete expressions can be represented in Scala as
+functions
 \begin{lstlisting}[language=Scala, numbers=none]
 r => r * (3 + 4)
 \end{lstlisting}
 \noindent
 where \texttt{r} is any result that has been computed earlier. By the
-way in lambda-calculus notation we would write
+way, in lambda-calculus notation we would write
 $\lambda r.\, r * (3 + 4)$ for the same function. To sum up, we use
 functions (``continuations'') to represent what is coming next in a
 sequence of instructions. In our case, continuations are functions of
 type \code{KVal} to \code{KExp}. They can be seen as a sequence of
 \code{KLet}s where there is a ``hole'' that needs to be
 where in the second line is a $\Box$ which still expects a \code{KVal}
 to be filled in before it becomes a ``proper'' \code{KExp}. When we
 apply an argument to the continuation (remember they are functions)
 we essentially fill something into the corresponding hole.
-Lets look at concrete code. To simplify matters first,
+Lets look at some concrete code. To simplify matters,
 suppose our source language consists just of three kinds of expressions
 \begin{lstlisting}[language=Scala,numbers=none]
 enum Expr {
 case Num(n: Int)
 e match { ... }
 \end{lstlisting}
 \noindent
 where \code{k} is the continuation and \code{e} is the expression to
-be compiled. In case we have numbers, we can just pass them to the
+be compiled. The result of the function is a K-expression, which later
-continuations because numbers need not be further teared apart as they
+can be compiled into LLVM-IR code.
-are already atomic. Passing the number to the continuation means we
-apply the continuation like
+In case we have numbers, then we can just pass them in CPS-translation
+to the continuations because numbers need not be further teared apart
+as they are already atomic. Passing the number to the continuation
+means we apply the continuation like
 \begin{lstlisting}[language=Scala,numbers=none]
 case Num(i) => k(KNum(i))
 \end{lstlisting}
-\noindent This would just fill in the $\Box$ in a \code{KLet}-expression.
+\noindent This would fill in the $\Box$ in a \code{KLet}-expression.
-There is no need to create a temporary variable for simple numbers.
+Since \texttt{k} is a function from \texttt{KVar} to \texttt{KExp} we
-More interesting is the case for arithmetic operations.
+also optain the correct type for CPS, namely \texttt{KExp}.  There is
+no need to create a temporary variable for simple numbers.  More
+interesting is the case for arithmetic operations.
 \begin{lstlisting}[language=Scala,numbers=none,xleftmargin=0mm]
 case Aop(op, e1, e2) => {
 val z = Fresh("tmp")
 CPS(e1)(r1 =>
 \noindent
 Note that this assignment has two ``holes'', one for the left
 subexpression and one for the right subexpression. We can fill both
 holes by calling the CPS function twice---this is a bit of the black
 art in CPS. We can use the second call of CPS as the continuation
-of the first call: The reason is that
+of the first call. The reason is that
 \begin{lstlisting}[language=Scala,numbers=none,xleftmargin=0mm]
 r1 => CPS(e2)(r2 => KLet(z, KAop(op, r1, r2), k(KVar(z))))
 \end{lstlisting}
 we created the assignment with the fresh temporary variable
 \texttt{z}, we need to ``communicate'' that the result of the
 computation of the arithmetic expression is stored in \texttt{z} to the
 computations that follow. In this way we apply the continuation \texttt{k} with this
 new variable (essentially we are plugging in a hole further down the line).
+Hope this makes sense.
 The last case we need to consider in our small expression language are
 function calls.
-\begin{lstlisting}[language=Scala,numbers=none,xleftmargin=0mm]
+\begin{lstlisting}[language=Scala,numbers=left,xleftmargin=0mm]
 case Call(fname, args) => {
 def aux(args: List[Expr], vs: List[KVal]): KExp = args match {
 case Nil => {
 val z = Fresh("tmp")
 KLet(z, KCall(fname, vs), k(KVar(z)))
 \noindent
 For them we introduce an auxiliary function that compiles first all
 function arguments---remember in our source language we can have calls
 such as $foo(3 + 4, g(3))$ where we first have to create temporary
 variables (and computations) for each argument. Therefore \texttt{aux}
-analyses the arguments from left to right. In case there is an argument
+analyses the argument list from left to right. In case there is an
-\texttt{a} on the front of the list (the case \texttt{a::as}), we call
+argument \texttt{a} on the front of the list (the case \texttt{a::as}
-CPS recursively for the corresponding subexpression. The temporary variable
+in Line 7), we call CPS recursively for the corresponding
-containing the result for this argument we add to the end of the K-values we
+subexpression. The temporary variable containing the result for this
-have already analysed before. Again very conveniently we can use the
+argument we add to the end of the K-values we have already analysed
-recursive call to \texttt{aux} as the continuation for the computations
+before. Again very conveniently we can use the recursive call to
-that follow. If we reach the end of the argument list (the \texttt{Nil}-case),
+\texttt{aux} as the continuation for the computations that
-then we collect all the K-values \texttt{v1} to \texttt{vn} and call the
+follow. When we reach the end of the argument list (the
-function in the K-language like so
+\texttt{Nil}-case in Lines 3--6), then we collect all the K-values
+\texttt{v1} to \texttt{vn} and call the function in the K-language
+like so
 \begin{lstlisting}[language=LLVMIR,numbers=none,escapeinside={(*@}{@*)}]
 let z = call foo(v1,...,vn) in
 ...
 The last question we need to answer in the code (see Figure~\ref{cps}) is how we
 start the CPS-translation function, or more precisely with which continuation we
 should start CPS? It turns out that this initial continuation will be the last one that is
 called. What should be the last step in the computation? Yes, we need to return the
 temporary variable where the last result is stored (if it is a simple number, then we can
-just return this number). Therefore we cal CPS with the code
+just return this number). Therefore we call CPS with the code
 \begin{lstlisting}[language=Scala,numbers=none]
 def CPSi(e: Expr) : KExp = CPS(e)(KReturn(_))
 \end{lstlisting}
 \noindent
-where we give the function \code{KReturn(_)}.
+where we give the function \code{KReturn(_)} as the continuation. With
+this we completed the translation of expressions into our
+K-language. Figure~\ref{absfun} gives the complete datatypes for the
+ASTs of the Fun-language and the K-values and K-expressions for the
+K-language.
+Having obtained a K-expression, it is relatively straightforward to
+generate a valid program for the LLVM-IR. We leave this to the
+attentive reader. What else can we do?  Well it should be relatively
+easy to apply some common optimisations to the K-expressions. One
+optimisations is called constant folding---for example if we have an
+expression $3 + 4$ then we can replace it by just $5$ instead of
+generating code to compute $5$. Now this information needs to be
+propagated to the next computation step to see whether any further
+constant foldings are possible. Another useful technique is common
+subexpression elimination, meaning if you have twice a calculation of
+a function $foo(a)$, then we want to call it only once and store the
+result in a temporary variable that can be used instead of the second,
+or third, call to $foo(a)$. Again I leave this to the attentive reader
+to work out and implement.
 \begin{figure}[p]\small
 \begin{lstlisting}[language=Scala,numbers=none]
 // Fun language (expressions)
 case class Aop(o: String, a1: Exp, a2: Exp) extends Exp
 case class Sequence(e1: Exp, e2: Exp) extends Exp
 case class Bop(o: String, a1: Exp, a2: Exp) extends BExp
 // K-language (K-expressions, K-values)
 abstract class KExp
 abstract class KVal
 case class KVar(s: String) extends KVal
 case class KIf(x1: String, e1: KExp, e2: KExp) extends KExp
 case class KLet(x: String, v: KVal, e: KExp) extends KExp
 case class KReturn(v: KVal) extends KExp
 \end{lstlisting}
-\caption{Abstract syntax trees for the Fun-language.\label{absfun}}
+\caption{Abstract syntax trees for the Fun-language and the K-language.\label{absfun}}
 \end{figure}
 \noindent

changeset 909	a04efdd5e7a3
parent 908	0138618eff73
child 912	e32802acf952