% !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: + −