% !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, code generation was+
−
actually not so hard, no? One of the main reason for this ease is that+
−
the JVM is a stack-based virtual machine and it is, for example, not+
−
hard to translate arithmetic expressions into instructions manipulating+
−
the stack. The problem is that ``real'' CPUs, although supporting stack+
−
operations, are not really \emph{stack machines}. They are just not+
−
optimised for this way of calculating things. The design of CPUs is more+
−
like, here is a piece of memory---compiler, or compiler writer, do+
−
something with it. Otherwise get lost. So in the name of raw speed,+
−
modern compilers go the extra mile and 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 want to not 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, we target the LLVM Intermediate Language. In this way+
−
we can take advantage of the tools coming with LLVM and for example do not+
−
have to worry about things like that CPUs have only a limited amount of+
−
registers. +
−
+
−
LLVM\footnote{\url{http://llvm.org}} is a beautiful example that+
−
projects from Academia can make a difference in the world. LLVM was+
−
started in 2000 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.~gfortran, 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 was 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 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-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. 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 and which is the intermediate format that+
−
LLVM can use to do cool things (like targetting strange architectures)+
−
and allocating memory efficiently. +
−
+
−
The idea behind SSA is to use very simple variable assignments where+
−
every variable is assigned only once. The assignments also need to be+
−
extremely primitive in the sense that they can be just simple operations+
−
like addition, multiplication, jumps and so on. A typical 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. You cannot for example have+
−
+
−
\begin{lstlisting}[language=LLVM,numbers=none]+
−
    x := 1+
−
    y := 2     +
−
    x := x + y+
−
\end{lstlisting}+
−
+
−
\noindent because in this snippet \texttt{x} is assigned twice. There+
−
are sophisticated algorithm for imperative languages, like C, for+
−
efficiently transforming a program into SSA format, but we do not have+
−
to be concerned about those. 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, which stands for+
−
Continuation-Passing-Style---basically black art. So sit tight.+
−
+
−
\subsection*{CPS-Translations}+
−
+
−
What is good about our simple fun language is that it basically only +
−
contains expressions (be they arithmetic expressions or boolean expressions).+
−
The only exceptions are function definitions, for which we can easily+
−
use the mechanism of defining functions in LLVM-IR. For example the simple+
−
fun program +
−
+
−
\begin{lstlisting}[language=Scala,numbers=none]+
−
def dble(x) = x * x+
−
\end{lstlisting}+
−
+
−
\noindent+
−
can be compiled into the following LLVM-IR function:+
−
+
−
\begin{lstlisting}[language=LLVM]+
−
define i32 dble(i32 %x) {+
−
   %tmp =  mul i32 %x, % x+
−
   ret i32 %tmp+
−
}    +
−
\end{lstlisting}+
−
+
−
 +
−
\end{document}+
−
+
−
+
−
%%% Local Variables: +
−
%%% mode: latex+
−
%%% TeX-master: t+
−
%%% End: +
−