# HG changeset patch # User Christian Urban # Date 1572614511 0 # Node ID 8fc109f36b78cb634fb5c232a20f54263df84a3b # Parent ff3b48da282cdb1c852485fc87ad6c3599591471 updated diff -r ff3b48da282c -r 8fc109f36b78 handouts/ho09.pdf Binary file handouts/ho09.pdf has changed diff -r ff3b48da282c -r 8fc109f36b78 handouts/ho09.tex --- 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} diff -r ff3b48da282c -r 8fc109f36b78 progs/fun_llvm.scala --- a/progs/fun_llvm.scala Mon Oct 28 13:34:03 2019 +0000 +++ b/progs/fun_llvm.scala Fri Nov 01 13:21:51 2019 +0000 @@ -106,13 +106,14 @@ aux(args, Nil) } case Sequence(e1, e2) => - CPS(e1)(y1 => CPS(e2)(y2 => k(y2))) + CPS(e1)(_ => CPS(e2)(y2 => k(y2))) case Write(e) => { val z = Fresh("tmp") CPS(e)(y => KLet(z, KWrite(y), k(KVar(z)))) } } +//initial continuation def CPSi(e: Exp) = CPS(e)(KReturn) // some testcases @@ -190,8 +191,8 @@ case KLet(x: String, v: KVal, e: KExp) => i"%$x = ${compile_val(v)}" ++ compile_exp(e) case KIf(x, e1, e2) => { - val if_br = Fresh("if_br") - val else_br = Fresh("else_br") + val if_br = Fresh("if_branch") + val else_br = Fresh("else_branch") i"br i1 %$x, label %$if_br, label %$else_br" ++ l"\n$if_br" ++ compile_exp(e1) ++ @@ -208,7 +209,7 @@ define i32 @printInt(i32 %x) { %t0 = getelementptr [4 x i8], [4 x i8]* @.str, i32 0, i32 0 - call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0), i32 %x) + call i32 (i8*, ...) @printf(i8* %t0, i32 %x) ret i32 %x }