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