--- a/handouts/ho09.tex Mon Oct 28 13:34:03 2019 +0000
+++ b/handouts/ho09.tex Fri Nov 01 13:21:51 2019 +0000
@@ -16,30 +16,19 @@
Reflecting on our tiny compiler 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 main reason for this ease is
-that the JVM is a stack-based virtual machine and it is therefore not
+of the abstract syntax tree, yes? One of the main reason for this ease
+is that the JVM is a stack-based virtual machine and it is therefore not
hard to translate 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 is a chunk of
memory---compiler, or better compiler writers, do something with it.
-Consequently, modern compilers need to go the extra mile in order to generate
-code that is much easier and faster to process by CPUs.
-
-
-Another reason why it makes sense to go the extra mile is that stack
-instructions are very 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 this
-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.
-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. For example we do not have to worry about things like
-register allocations.\bigskip
+Consequently, modern compilers need to go the extra mile in order to
+generate code that is much easier and faster to process by CPUs. 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. For example we do not have to worry about things like register
+allocations.\bigskip
\noindent LLVM\footnote{\url{http://llvm.org}} is a beautiful example
that projects from Academia can make a difference in the world. LLVM
@@ -124,26 +113,48 @@
Obviously these types need to match up\ldots{} but since we have in our
programs only integers, \texttt{i32} everywhere will do.
-Conveniently, you can use the program \texttt{lli}, which comes with LLVM, to interprete
-programs written in the LLVM-IR. So you can easily check whether the
-code you produced actually works. To get a running program that does
-something interesting you need to add some boilerplate about printing out
-numbers and a main-function that is the entrypoint for the program (see Figure~\ref{lli}).
+Conveniently, you can use the program \texttt{lli}, which comes with
+LLVM, to interpret programs written in the LLVM-IR. So you can easily
+check whether the code you produced actually works. To get a running
+program that does something interesting you need to add some boilerplate
+about printing out numbers and a main-function that is the entrypoint
+for the program (see Figure~\ref{lli}). You can generate a binary for
+this program using \texttt{llc}-compiler in order to generate an object
+file and then use gcc (clang) for generating a binary:
-\begin{figure}[t]
-\lstinputlisting[language=LLVM]{../progs/sqr.ll}
-\caption{\label{lli}}
+\begin{lstlisting}[language=bash,numbers=none]
+llc -filetype=obj sqr.ll
+gcc sqr.o -o a.out
+./a.out
+\end{lstlisting}
+
+\begin{figure}[t]\small
+\lstinputlisting[language=LLVM,numbers=left]{../progs/sqr.ll}
+\caption{An LLVM-IR program for calculating the square function. The
+interesting function is \texttt{sqr} in Lines 13 -- 16. The main
+function calls \texttt{sqr} and prints out the result. The other
+code is boilerplate for printing out integers.\label{lli}}
\end{figure}
-\begin{figure}[t]
+
+
+\subsection*{Our Own Intermediate Language}
+
+Remember compilers have to solve the problem of bridging the gap between
+``high-level'' programs and ``low-level'' hardware. If the gap is tool
+wide then a good strategy is to lay a stepping stone somewhere in
+between. The LLVM-IR itself is such a stepping stone to make the task of
+generating code easier. Like a real compiler we will use another
+stepping stone which I call \emph{K-language}. For this remember
+expressions (and boolean expressions) in the Fun language are given by
+the code on top of Figure~\ref{absfun}
+
+
+\begin{figure}[p]\small
\begin{lstlisting}[language=Scala,numbers=none]
-abstract class Exp extends Serializable
-abstract class BExp extends Serializable
-abstract class Decl extends Serializable
-
-case class Main(e: Exp) extends Decl
-case class Def(name: String, args: List[String], body: Exp)
- extends Decl
+// Fun-language (expressions)
+abstract class Exp
+abstract class BExp
case class Call(name: String, args: List[Exp]) extends Exp
case class If(a: BExp, e1: Exp, e2: Exp) extends Exp
@@ -152,16 +163,45 @@
case class Num(i: Int) extends Exp
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
+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 KNum(i: Int) extends KVal
+case class Kop(o: String, v1: KVal, v2: KVal) extends KVal
+case class KCall(o: String, vrs: List[KVal]) extends KVal
+case class KWrite(v: KVal) extends KVal
+
+case class KIf(x1: String, e1: KExp, e2: KExp) extends KExp
+case class KLet(x: String, e1: KVal, e2: KExp) extends KExp
+case class KReturn(v: KVal) extends KExp
\end{lstlisting}
\caption{Abstract syntax trees for the Fun language.\label{absfun}}
\end{figure}
-
+
\subsection*{CPS-Translations}
+
+
+
+Another reason why it makes sense to go the extra mile is that stack
+instructions are very 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 this
+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.
+
\end{document}