% !TEX program = xelatex+
−
\documentclass{article}+
−
\usepackage{../style}+
−
\usepackage{../langs}+
−
\usepackage{../graphics}+
−
\usepackage{../grammar}+
−
%%\usepackage{multicol}+
−
+
−
%%\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}+
−
+
−
\begin{document}+
−
\fnote{\copyright{} Christian Urban, King's College London, 2019}+
−
+
−
+
−
\section*{Handout 9 (LLVM, SSA and CPS)}+
−
+
−
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+
−
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. 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+
−
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 other languages (e.g.~Fortran,+
−
Ada, Go, Objective-C, Pascal etc). The problem was that gcc morphed over+
−
time into a monolithic gigantic piece of m\ldots ehm software, which you+
−
could not mess about in an afternoon. In contrast, LLVM is designed to+
−
be a modular suite of tools with which you could play around easily and+
−
try out something new. LLVM became a big player once Apple hired one of+
−
the original developers (I cannot remember the reason why Apple did not+
−
want to use gcc, but maybe they were also just disgusted by its big+
−
monolithic codebase). Anyway, LLVM is now the big player and gcc is more+
−
or less legacy. This does not mean that programming languages like C and+
−
C++ are dying out any time soon---they are nicely supported by LLVM.+
−
+
−
Targetting the LLVM Intermediate Language, or Intermediate+
−
Representation (short LLVM-IR), also means we can profit from the very+
−
modular structure of the LLVM compiler and let for example the compiler+
−
generate code for X86, or ARM etc. That means we can be agnostic about+
−
where our code actually runs. However, what we have to do is to generate+
−
code in \emph{Static Single-Assignment} format (short SSA), because that+
−
is what the LLVM-IR expects from us. LLVM-IR is the intermediate format+
−
that LLVM uses for doing cool things, like targetting strange+
−
architectures, optimising code and allocating memory efficiently. +
−
+
−
The idea behind the SSA format is to use very simple variable+
−
assignments where every variable is assigned only once. The assignments+
−
also need to be primitive in the sense that they can be just simple+
−
operations like addition, multiplication, jumps, comparisons and so on.+
−
An idealised snippet of a program in SSA is +
−
+
−
\begin{lstlisting}[language=LLVM,numbers=none]+
−
    x := 1+
−
    y := 2     +
−
    z := x + y+
−
\end{lstlisting}+
−
+
−
\noindent where every variable is used only once (we could not write+
−
\texttt{x := x + y} in the last line for example).  There are+
−
sophisticated algorithms for imperative languages, like C, that+
−
efficiently transform a high-level program 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+
−
abracadabra programming. So sit tight.+
−
+
−
\subsection*{LLVM-IR}+
−
+
−
Before we start, lets first have a look at the \emph{LLVM Intermediate+
−
Representation}. What is good about our simple Fun language is that it+
−
basically only contains expressions (be they arithmetic expressions or+
−
boolean expressions). The exception is function definitions. Luckily,+
−
for them we can use the mechanism of defining functions in LLVM-IR. For+
−
example the simple Fun program +
−
+
−
+
−
\begin{lstlisting}[language=Scala,numbers=none]+
−
def sqr(x) = x * x+
−
\end{lstlisting}+
−
+
−
\noindent+
−
can be compiled into the following LLVM-IR function:+
−
+
−
\begin{lstlisting}[language=LLVM]+
−
define i32 @sqr(i32 %x) {+
−
   %tmp = mul i32 %x, %x+
−
   ret i32 %tmp+
−
}    +
−
\end{lstlisting}+
−
+
−
\noindent First to notice is that all variable names in the LLVM-IR are+
−
prefixed by \texttt{\%}; function names need to be prefixed with @.+
−
Also, the LLVM-IR is a fully typed language. The \texttt{i32} type stands+
−
for a 32-bit integer. There are also types for 64-bit integers, chars+
−
(\texttt{i8}), floats, arrays and even pointer types. In teh code above,+
−
\texttt{sqr} takes an argument of type \texttt{i32} and produces a+
−
result of type \texttt{i32}. Each arithmetic operation, like addition or+
−
multiplication, are also prefixed with the type they operate on.+
−
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 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{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}   +
−
+
−
+
−
    +
−
\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]+
−
// 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+
−
case class Write(e: Exp) extends Exp+
−
case class Var(s: String) extends Exp+
−
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  +
−
+
−
+
−
+
−
// 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}+
−
+
−
+
−
%%% Local Variables: +
−
%%% mode: latex+
−
%%% TeX-master: t+
−
%%% End: +
−