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

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.

\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. 

\end{figure}   

\begin{lstlisting}[language=Scala,numbers=none]

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

\end{lstlisting}

\caption{Abstract syntax trees for the Fun language.\label{absfun}}

\end{figure}

\subsection*{CPS-Translations}

\end{document}

%%% Local Variables: 

%%% mode: latex

%%% TeX-master: t

%%% End: