\fnote{\copyright{} Christian Urban, King's College London, 2019, 2023}

post-traversal of the abstract syntax tree, yes? One of the reasons

for this ease is that the JVM is a stack-based virtual machine and it

is therefore not hard to translate deeply-nested 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 are some operations and a chunk of

memory---compiler, or better compiler writers, do something with

them. Consequently, modern compilers need to go the extra mile in

order to generate code that is much easier and faster to process by

actual CPUs, rather than running code on virtual machines that

introduce an additional layer of indirection. 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.\footnote{\url{http://llvm.org}} For example we do not have to

worry about things like register allocations. By using LLVM, however,

we also have to pay price in the sense that generating code gets

harder\ldots{}unfortunately.

\subsection*{LLVM and LLVM-IR}

\noindent LLVM is a beautiful example

gcc with its myriad of front-ends for different programming languages (C++, Fortran,

time into a monolithic gigantic piece of m\ldots ehm complicated

software, which you

assembly language of Jasmin and Krakatau. Targetting LLVM-IR will also

allow us to benefit from the modular structure of the LLVM compiler

and we can let, for example, the compiler generate code for different

CPUs, say X86 or ARM.  That means we can be agnostic about where our

code is actually going to run.\footnote{Anybody want to try to run our

  programs on Android phones?}  We can also be somewhat ignorant about

optimising our code and about allocating memory efficiently: the LLVM

tools will take care of all this.

However, what we have to do in order to make LLVM to play ball is to

generate code in \emph{Static Single-Assignment} format (short SSA),

because that is what the LLVM-IR expects from us. A reason why LLVM

uses the SSA format, rather than JVM-like stack instructions, is that

stack instructions are 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 these obstacles 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 fast. This is what the SSA

format is designed for.

assignments where every tmp-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, function calls and so on.  Say, we have an expression

$((1 + a) + (foo(3 + 2) + (b * 5)))$, then the corresponding SSA format is

let tmp0 = add 1 a in

let tmp1 = add 3 2 in  

let tmp2 = call foo(tmp1)  

let tmp3 = mul b 5 in 

let tmp4 = add tmp2 tmp3 in 

let tmp5 = add tmp0 tmp4 in

  return tmp5 

\noindent where every tmp-variable is used only once (we could, for

example, not write \texttt{tmp1 = add tmp2 tmp3} in Line 5 even if this

would not change the overall result).

Before we start, let's however first have a look at the \emph{LLVM Intermediate

What is good about our toy Fun-language is that it basically only

earlier compiler). For example the simple Fun-program 

\noindent First notice that all ``local'' variable names, in this case

\texttt{x} and \texttt{tmp}, are prefixed with \texttt{\%} in the

LLVM-IR.  Temporary variables can be named with an identifier, such as

\texttt{tmp}, or numbers. In contrast, function names, since they are

``global'', need to be prefixed with an @-symbol. Also, the LLVM-IR is

a fully typed language. The \texttt{i32} type stands for 32-bit

integers. There are also types for 64-bit integers (\texttt{i64}),

chars (\texttt{i8}), floats, arrays and even pointer types. In the

code above, \texttt{sqr} takes an argument of type \texttt{i32} and

produces a result of type \texttt{i32} (the result type is in front of

the function name, like in C). Each arithmetic operation, for example

addition and 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, for the moment \texttt{i32}

everywhere will do. We do not have to generate any other types, but

obviously this is a limitation in our Fun-language (and which we

lift in the final CW).

condition? In the LLVM-IR, branching  if-conditions are implemented

The type \texttt{i1} stands for booleans. If the variable is true,

then this instruction jumps to the if-branch, which needs an explicit

label; otherwise it jumps to the else-branch, again with its own

label. This allows us to keep the meaning of the boolean expression

``as is'' when compiling if's---thanks god no more negating of

booleans.

unsigned representations of integers. I assume you know what this means,

otherwise just ask.

where the arguments can only be simple variables and numbers, but not compound

for the program (see Figure~\ref{lli} for a complete listing of the square function). Again

the \texttt{llc}-compiler and then \texttt{gcc}/\texttt{clang}, whereby \texttt{llc} generates

an object file and \texttt{gcc} (that is actually \texttt{clang} on my Mac) generates the

  calls the sqr-function in \texttt{@main} with the argument \texttt{5}

  (Line 20). The

  code for the \texttt{sqr} function is in Lines 13 -- 16. It stores

  the result of sqr in the variable called \texttt{\%i} and then

  prints out the contents of this variable in Line 21. The other

  code is boilerplate for printing out integers.\label{lli}}

Let's get back to our compiler: Remember compilers have to solve the

problem of bridging the gap between ``high-level'' programs and

``low-level'' hardware. If the gap is too wide for one step, 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

and optimising code easier. Like a real compiler we will use our own

stepping stone which I call the \emph{K-language}.

\begin{center}

  \begin{tikzpicture}[scale=0.9,font=\bf,

                      node/.style={

                      rectangle,rounded corners=3mm,

                      ultra thick,draw=black!50,minimum height=16mm, 

                      minimum width=20mm,

                      top color=white,bottom color=black!20}]

  %\node (0) at (-3,0) {};  

  \node (A) at (0.0,0) [node,text width=1.6cm,text centered,label=above:{\small\it{}source}] {Fun-Language};

  \node (B) at (3.5,0) [node,text width=1.6cm,text centered,label=above:{\small\it{}stepping stone}] {K-Language};

  \node (C) at (7.0,0) [node,text width=1.6cm,text centered,label=above:{\small\it{}target}] {LLVM-IR};

  \draw [->,line width=2.5mm] (A) -- node [above,pos=0.35] {} (B); 

  \draw [->,line width=2.5mm] (B) -- node [above,pos=0.35] {} (C); 

  \end{tikzpicture}

  \end{center}

  \noindent

  To see why we need a stepping stone for generating code in SSA-format,

  considder again arithmetic expressions such as

  $((1 + a) + (3 + (b * 5)))$. They need to be broken up into smaller

  ``atomic'' steps, like so

  return tmp3 

\end{lstlisting}

\noindent

Here \texttt{tmp3} will contain the result of what the whole

expression stands for. In each individual step we can only perform an

``atomic'' or ``trival'' operation, like addition or multiplication of

a number or a variable.  We are not allowed to have for example a

nested addition or an if-condition on the right-hand side of an

assignment. Such constraints are forced upon us because of how the SSA

format works in the LLVM-IR. To simplify matters we represent

assignments with two kinds of syntactic entities, namely

\emph{K-values} and \emph{K-expressions}. K-values are all ``things''

that can appear on the right-hand side of an equal. Say we have

the following definition for K-values:

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

enum KVal {

  case KVar(s: String)

  case KNum(n: Int)

  case KAop(op: String, v1: KVal, v2: KVal)

  case KCall(fname: String, args: List[KVal])

}

where a K-value can be a variable, a number or a ``trivial'' binary

operation, such as addition or multiplication. The two arguments of a

binary operation need to be K-values as well. Finally, we have

function calls, but again each argument of the function call needs to

be a K-value.  One point we need to be careful, however, is that the

arguments of the binary operations and function calls are in fact only

variables or numbers. To encode this constraint into the type-system

of Scala would make things too complicated---to satisfy this

constraint is therefore on us. For our Fun-language, we will later on

consider some further K-values.

Our K-expressions will encode the \texttt{let} and the \texttt{return}

from the SSA-format (again for the moment we only consider these two

constructors---later on we will have if-branches as well).

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

enum KExp {

  case KLet(x: String, v: KVal, e: KExp)

  case KReturn(v: KVal)

}

\end{lstlisting}

\noindent

By having in \texttt{KLet} taking first a string (standing for an

intermediate variable) and second a value, we can fulfil the SSA

constraint in assignments ``by construction''---there is no way we

could write anything else than a K-value.  Note that the third

argument of a \texttt{KLet} is again a K-expression, meaning either

another \texttt{KLet} or a \texttt{KReturn}. In this way we can

construct a sequence of computations and return a final result.  Of

course we also have to ensure that all intermediary computations are

given (fresh) names---we will use an (ugly) counter for this.

To sum up, K-values are the atomic operations that can be on the

right-hand side of assignemnts. The K-language is restricted such that

it is easy to generate the SSA format for the LLVM-IR. What remains to

be done is a translation of our Fun-language into the K-language. The

main difficulty is that we need to order the computationa---in teh

K-language we only have linear sequence of instructions to need to be

followed. Before we explain this, we have a look at some

CPS-translation.

into the CPS-translation for our Fun-language, let us look at 

seen as a kind of generalisation of tail-recursive functions.

So far we did not look at this generalisation in earnest.

Anyway

\noindent

The point of this section is that you are playing around with these

simple definitions and make sure they calculate the expected result.

In the next step, you should understand \emph{how} these functions

calculate the result with the continuations. 

\section*{Worked Example}

Let us now come back to the CPS-translations for the Fun-language. The

this conveniently, we use the CPS-translation mechanism. What continuations

essentially solve is the following problem: Given an expressions

\begin{equation}\label{exp}

(1 + 2) * (3 + 4)

\end{equation}  

\noindent

which of the subexpressions should be calculated first? We just arbitrarily

going to decide that it will be from left to right. This means we have

to tear the expression shown in \eqref{exp} apart as follows:

\[

(1 + 2) \qquad\text{and}\qquad  \Box * (3 + 4)

\]  

\noindent

The first one will give us a result, but the second one is not

really an expression that makes sense. It will only make sense

as the next step in the computation when we fill-in the result of

$1+2$ into the ``hole'' indicated by $\Box$. Such incomplete

expressions can be represented in Scala as functions

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

r => r * (3 + 4)

\end{lstlisting}  

\noindent

where \texttt{r} is any result that has been computed earlier. By the

way in lambda-calculus notation we would write

$\lambda r.\, r * (3 + 4)$ for the same function. To sum up, we use

sequence of instructions. In our case, continuations are functions of

type \code{KVal} to \code{KExp}. They can be seen as a sequence of

\code{KLet}s where there is a ``hole'' that needs to be

filled. Consider for example