
diff -r e32802acf952 -r eef6a56c185a handouts/ho09.tex
--- a/handouts/ho09.tex	Mon Jun 05 10:50:36 2023 +0100
+++ b/handouts/ho09.tex	Wed Jul 05 16:12:40 2023 +0100
@@ -19,29 +19,31 @@
 
 Reflecting on our two tiny compilers targetting the JVM, the code
 generation part was actually not so hard, no? Pretty much just some
-post-traversal of the abstract syntax tree, yes? One of the reasons
+post-traversal of the abstract syntax tree. Yes? One of the reasons
 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 instructions and a chunk of
+stack. That is pretty much the whole point of the JVM. 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 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 the LLVM-IR,
-however, we also have to pay price in the sense that generating code
-gets harder\ldots{}unfor\-tunately.
+tractable for this module, we target the \emph{LLVM Intermediate
+  Language} (LLVM-IR). 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 or peephole
+optimisations. By using the LLVM-IR, however, we also have to pay
+price in the sense that generating code gets
+harder\ldots{}unfor\-tunately nothing comes for free in life.
 
 \subsection*{LLVM and the LLVM-IR}
 
 \noindent LLVM is a beautiful example
-that projects from Academia can make a difference in the World. LLVM
+that projects from Academia can make a difference in the Real 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
 gcc with its myriad of front-ends for different programming languages (C++, Fortran,
@@ -73,14 +75,36 @@
 reason why LLVM 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 ``high-level'' code still run
-fast, but let's say that for the sake of argument we do not want to
-rely on it. We want to generate fast code 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.
+about with what is calculated on the stack. Have a look at the
+expression $((a + b) * 4) - (3 * (a + b))$ and the corresponding JVM
+instructions:
+
+\begin{lstlisting}[language=JVMIS, numbers=none,mathescape]
+iload a
+iload b
+iadd
+ldc 4
+imul
+ldc 3
+iload a
+iload b
+iadd
+imul
+isub
+\end{lstlisting}
+
+\noindent
+and try to reorganise the code such that you calculate the expression
+$(a + b)$ only once. This requires either quite a bit of
+math-understanding from the compiler or you need to add ``copy-and-fetch''
+of a result from a local variable.  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 ``high-level'' code still run fast, but let's say that
+for the sake of argument we do not want to rely on it. We want to
+generate fast code 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 have sequences of very
@@ -105,10 +129,12 @@
 example, not write \texttt{tmp1 = add tmp2 tmp3} in Line 5 even if
 this would not change the overall result). At the end we have a
 return-instruction wich contains the final result of the
-expression. As can be seen, the task we have to solve is to take apart
-compound expressions as shown above and transfrom them into a sequence
-of simple assignments. Note that this for example means we have to
-fix the order in which the expression is calculated. 
+expression. As can be seen the task we have to solve for generating
+SSA-code is to take apart compound expressions into its most basic
+''particles'' and transfrom them into a sequence of simple assignments
+that calculates the desired result. Note that this means we have to
+fix the order in which the expression is calculated, like from the
+left to right.
 
 There are sophisticated algorithms for imperative languages, like C,
 that efficiently transform high-level programs into SSA-format. But
@@ -355,14 +381,14 @@
 \end{lstlisting}
 
 \noindent
-By having in \texttt{KLet} taking first a string (standing for a
+By having \texttt{KLet} taking first a string (standing for a
 tmp-variable) and second a value, we can fulfil the SSA 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 indicate what is the final result of the
-computations.  According to the SSA-format, we also have to ensure
+sequence of computations and indicate what the final result of the
+computations is.  According to the SSA-format, we also have to ensure
 that all intermediary computations are given (fresh) names---we will
 use an (ugly) counter for this.
 
@@ -371,7 +397,7 @@
 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 computation---in the
-K-language we only have linear sequence of instructions. Before we
+K-language we only have linear sequences of instructions. Before we
 explain this, we have a look at some programs in CPS-style.
 
 
@@ -479,20 +505,21 @@
 
 Let us now come back to the CPS-translations for the Fun-language.
 Though we will start with a simpler subset containing only numbers,
-arithmetic expressions and function calls.  The main difficulty of
-generating instructions in SSA-format is that large compound
-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
+arithmetic expressions and function calls---no variables for the
+moment.  The main difficulty of generating instructions in SSA-format
+is that large compound 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 the 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 going to decide that the calculation will be from left to
+which of the subexpressions should be calculated first? We are going 
+arbitrarily to decide that the calculation will be from left to
 right. Other 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:
@@ -569,7 +596,7 @@
 be compiled. The result of the function is a K-expression, which later
 can be compiled into LLVM-IR code.
 
-In case we have numbers, then we can just pass them in CPS-translation
+In case we have numbers, then we can just pass them in the CPS-translation
 to the continuations because numbers need not be further teared apart
 as they are already primitive. Passing the number to the continuation
 means we apply the continuation like
@@ -595,7 +622,7 @@
 \noindent
 What we essentially have to do in this case is the following: compile
 the subexpressions \texttt{e1} and \texttt{e2}. They will produce some
-result that is stored in two temporary variables (assuming they are more
+result that is stored in two temporary variables (assuming \texttt{e1} and \texttt{e2} are more
 complicated than just numbers). We need to use these two temporary
 variables and feed them into a new assignment of the form
 
@@ -621,11 +648,13 @@
 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.
+plugging in a hole further down the line).  Hope this makes sense!? If not,
+play with the given code yourself.
 
 The last case we need to consider in our small expression language are
 function calls. For them remember each argument of the function
-call can in SSA-format only be a variable or a number.
+call can in SSA-format only be a variable or a number. Here is the
+complete code for this case:
 
 \begin{lstlisting}[language=Scala,numbers=left,xleftmargin=0mm]
 case Call(fname, args) => {
@@ -641,7 +670,7 @@
 \end{lstlisting}
 
 \noindent
-For this case we introduce an auxiliary function that compiles first all
+As can be seen, 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}
@@ -649,7 +678,7 @@
 argument \texttt{a} on the front of the list (the case \texttt{a::as}
 in Line 7), we call CPS recursively for the corresponding
 subexpression. The temporary variable containing the result for this
-argument we add to the end of the K-values we have already analysed
+argument, we add to the end of the K-values we have already analysed
 before. Again very conveniently we can use the recursive call to
 \texttt{aux} as the continuation for the computations that
 follow. When we reach the end of the argument list (the
@@ -703,19 +732,23 @@
 \section*{Next Steps}
 
 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.
+generate a valid program for the LLVM-IR---remember the K-language
+already enforces the SSA convention of a linear sequence of primitive
+instructions involving only unique temporary variables. 
+We leave this step 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




