% !TEX program = xelatex

\documentclass{article}

\usepackage{../style}

\usepackage{../langs}

\usepackage{../grammar}

\usepackage{../graphics}

\usetikzlibrary{calc,shapes,arrows}

\usepackage{framed}

\usepackage[belowskip=7pt,aboveskip=0pt]{caption}

\begin{document}

\fnote{\copyright{} Christian Urban, King's College London, 2017, 2018, 2019, 2020}

\section*{Handout 7 (Compilation)}

The purpose of a compiler is to transform a program a human can read and

write into code the machine can run as fast as possible. The fastest

code would be machine code the CPU can run directly, but it is often

good enough for improving the speed of a program to target a virtual

machine instead. This produces not the fastest possible code, but code

that is often pretty fast. This way of producing code has also the

advantage that the virtual machine takes care of things a compiler would

normally need to take care of (hairy things like explicit memory

management). 

As a first example in this module we will implement a compiler for the

very simple WHILE-language that we parsed in the last lecture. The

compiler will target the Java Virtual Machine (JVM), but not directly.

Pictorially the compiler will work as follows:

\begin{center}

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

                      node/.style={

                      rectangle,rounded corners=3mm,

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

                      minimum width=20mm,

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

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

  \node (A) at (0,0) [node,text width=1.6cm,text centered] {our compiler};

  \node (B) at (3.5,0) [node,text width=1.6cm,text centered] {Jasmin / Krakatau};

  \node (C) at (7.5,0) [node] {JVM};

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

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

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

  \end{tikzpicture}

  \end{center}

\noindent

The input will be WHILE-programs; the output will be assembly files

(with the file extension .j). Assembly files essentially contain

human-readable low-level code, meaning they are not just bits and bytes,

but rather something you can read and understand---with a bit of

practice of course. An \emph{assembler} will then translate the assembly

files into unreadable class- or binary-files the JVM or CPU can run.

Unfortunately, the Java ecosystem does not come with an assembler which

would be handy for our compiler-endeavour  (unlike Microsoft's  Common

Language Infrastructure for the .Net platform which has an assembler

out-of-the-box). As a substitute we shall use the 3rd-party programs

Jasmin and Krakatau 

\begin{itemize}

  \item \url{http://jasmin.sourceforge.net}

  \item \url{https://github.com/Storyyeller/Krakatau}

\end{itemize}

\noindent

The first is a Java program and the second a program written in Python.

Each of them allow us to generate \emph{assembly} files that are still

readable by humans, as opposed to class-files which are pretty much just

(horrible) zeros and ones. Jasmin (respectively Krakatau) will then take

our assembly files as input and generate the corresponding class-files for

us. 

What is good about the JVM is that it is a stack-based virtual machine,

a fact which will make it easy to generate code for arithmetic

expressions. For example when compiling the expression $1 + 2$ we need

to generate the following three instructions

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

ldc 1

ldc 2

iadd 

\end{lstlisting}

\noindent The first instruction loads the constant $1$ onto the stack,

the next one loads $2$, the third instruction adds both numbers together

replacing the top two elements of the stack with the result $3$. For

simplicity, we will consider throughout only arithmetic involving

integer numbers. This means our main JVM instructions for arithmetic

will be \instr{iadd}, \instr{isub}, \instr{imul}, \instr{idiv} and so on.

The \code{i} stands for integer instructions in the JVM (alternatives

are \code{d} for doubles, \code{l} for longs and \code{f} for floats

etc).

Recall our grammar for arithmetic expressions (\meta{E} is the

starting symbol):

\begin{plstx}[rhs style=, margin=3cm]

: \meta{E} ::= \meta{T} $+$ \meta{E}

         | \meta{T} $-$ \meta{E}

         | \meta{T}\\

: \meta{T} ::= \meta{F} $*$ \meta{T}

          | \meta{F} $\backslash$ \meta{T}

          | \meta{F}\\

: \meta{F} ::= ( \meta{E} )

          | \meta{Id}

          | \meta{Num}\\

\end{plstx}

\noindent where \meta{Id} stands for variables and \meta{Num}

for numbers. For the moment let us omit variables from arithmetic

expressions. Our parser will take this grammar and given an input

program produce an abstract syntax tree. For example we obtain for

the expression $1 + ((2 * 3) + (4 - 3))$ the following tree.

\begin{center}

\begin{tikzpicture}

\Tree [.$+$ [.$1$ ] [.$+$ [.$*$ $2$ $3$ ] [.$-$ $4$ $3$ ]]]

\end{tikzpicture}

\end{center}

\noindent To generate JVM code for this expression, we need to traverse

this tree in \emph{post-order} fashion and emit code for each

node---this traversal in \emph{post-order} fashion will produce code for

a stack-machine (which is what the JVM is). Doing so for the tree above

generates the instructions

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

ldc 1 

ldc 2 

ldc 3 

imul 

ldc 4 

ldc 3 

isub 

iadd 

iadd

\end{lstlisting}

\noindent If we ``run'' these instructions, the result $8$ will be on

top of the stack (I leave this to you to verify; the meaning of each

instruction should be clear). The result being on the top of the stack

will be an important convention we always observe in our compiler. Note,

that a different bracketing of the expression, for example $(1 + (2 *

3)) + (4 - 3)$, produces a different abstract syntax tree and thus also

a different list of instructions. 

Generating code in this post-order-traversal fashion is rather easy to

implement: it can be done with the following recursive

\textit{compile}-function, which takes the abstract syntax tree as an

argument:

\begin{center}

\begin{tabular}{lcl}

$\textit{compile}(n)$ & $\dn$ & $\instr{ldc}\; n$\\

$\textit{compile}(a_1 + a_2)$ & $\dn$ &

$\textit{compile}(a_1) \;@\;\textit{compile}(a_2)\;@\; \instr{iadd}$\\

$\textit{compile}(a_1 - a_2)$ & $\dn$ & 

$\textit{compile}(a_1) \;@\; \textit{compile}(a_2)\;@\; \instr{isub}$\\

$\textit{compile}(a_1 * a_2)$ & $\dn$ & 

$\textit{compile}(a_1) \;@\; \textit{compile}(a_2)\;@\; \instr{imul}$\\

$\textit{compile}(a_1 \backslash a_2)$ & $\dn$ & 

$\textit{compile}(a_1) \;@\; \textit{compile}(a_2)\;@\; \instr{idiv}$\\

\end{tabular}

\end{center}

\noindent

This is all fine, but our arithmetic expressions can contain variables

and we have not considered them yet. To fix this we will represent our

variables as \emph{local variables} of the JVM. Essentially, local

variables are an array or pointers to memory cells, containing in our

case only integers. Looking up a variable can be done with the

instruction

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

iload $index$

\end{lstlisting}

\noindent 

which places the content of the local variable $index$ onto 

the stack. Storing the top of the stack into a local variable 

can be done by the instruction

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

istore $index$

\end{lstlisting}

\noindent Note that this also pops off the top of the stack. One problem

we have to overcome, however, is that local variables are addressed, not

by identifiers (like \texttt{x}, \texttt{foo} and so on), but by numbers

(starting from $0$). Therefore our compiler needs to maintain a kind of

environment where variables are associated to numbers. This association

needs to be unique: if we muddle up the numbers, then we essentially

confuse variables and the consequence will usually be an erroneous

result. Our extended \textit{compile}-function for arithmetic

expressions will therefore take two arguments: the abstract syntax tree

and an environment, $E$, that maps identifiers to index-numbers.

\begin{center}

\begin{tabular}{lcl}

$\textit{compile}(n, E)$ & $\dn$ & $\instr{ldc}\;n$\\

$\textit{compile}(a_1 + a_2, E)$ & $\dn$ & 

$\textit{compile}(a_1, E) \;@\;\textit{compile}(a_2, E)\;@\; \instr{iadd}$\\

$\textit{compile}(a_1 - a_2, E)$ & $\dn$ &

$\textit{compile}(a_1, E) \;@\; \textit{compile}(a_2, E)\;@\; \instr{isub}$\\

$\textit{compile}(a_1 * a_2, E)$ & $\dn$ &

$\textit{compile}(a_1, E) \;@\; \textit{compile}(a_2, E)\;@\; \instr{imul}$\\

$\textit{compile}(a_1 \backslash a_2, E)$ & $\dn$ & 

$\textit{compile}(a_1, E) \;@\; \textit{compile}(a_2, E)\;@\; \instr{idiv}$\\

$\textit{compile}(x, E)$ & $\dn$ & $\instr{iload}\;E(x)$\\

\end{tabular}

\end{center}

\noindent In the last line we generate the code for variables where

$E(x)$ stands for looking up the environment to which index the variable

$x$ maps to. This is similar to the interpreter we saw earlier in the

module, which also needs an environment: the difference is that the

interpreter maintains a mapping from variables to current values (what

is the currently the value of a variable?), while compilers need a

mapping from variables to memory locations (where can I find the current

value for the variable in memory?).

There is a similar \textit{compile}-function for boolean

expressions, but it includes a ``trick'' to do with

\pcode{if}- and \pcode{while}-statements. To explain the issue

let us first describe the compilation of statements of the

WHILE-language. The clause for \pcode{skip} is trivial, since

we do not have to generate any instruction

\begin{center}

\begin{tabular}{lcl}

$\textit{compile}(\pcode{skip}, E)$ & $\dn$ & $([], E)$\\

\end{tabular}

\end{center}

\noindent whereby $[]$ is the empty list of instructions. Note that

the \textit{compile}-function for statements returns a pair, a

list of instructions (in this case the empty list) and an

environment for variables. The reason for the environment is

that assignments in the WHILE-language might change the

environment---clearly if a variable is used for the first

time, we need to allocate a new index and if it has been used

before, then we need to be able to retrieve the associated index.

This is reflected in the clause for compiling assignments, say

$x := a$:

\begin{center}

\begin{tabular}{lcl}

$\textit{compile}(x := a, E)$ & $\dn$ & 

$(\textit{compile}(a, E) \;@\;\instr{istore}\;index, E')$

\end{tabular}

\end{center}

\noindent We first generate code for the right-hand side of the

assignment (that is the arithmetic expression $a$) and then add an

\instr{istore}-instruction at the end. By convention running the code

for the arithmetic expression $a$ will leave the result on top of the

stack. After that the \instr{istore}-instruction, the result will be

stored in the index corresponding to the variable $x$. If the variable

$x$ has been used before in the program, we just need to look up what

the index is and return the environment unchanged (that is in this case

$E' = E$). However, if this is the first encounter of the variable $x$

in the program, then we have to augment the environment and assign $x$

with the largest index in $E$ plus one (that is $E' = E(x \mapsto

largest\_index + 1)$). To sum up, for the assignment $x := x + 1$ we

generate the following code snippet

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

iload $n_x$

ldc 1

iadd

istore $n_x$

\end{lstlisting}

\noindent 

where $n_x$ is the index (or pointer to the memory) for the variable

$x$. The Scala code for looking-up the index for the variable is as follow:

\begin{center}

\begin{tabular}{lcl}

$index \;=\; E\textit{.getOrElse}(x, |E|)$

\end{tabular}

\end{center}

\noindent

This implements the idea that in case the environment $E$ contains an

index for $x$, we return it. Otherwise we ``create'' a new index by

returning the size $|E|$ of the environment (that will be an index that

is guaranteed not to be used yet). In all this we take advantage of the

JVM which provides us with a potentially limitless supply of places

where we can store values of variables.

A bit more complicated is the generation of code for

\pcode{if}-statements, say

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

if $b$ then $cs_1$ else $cs_2$

\end{lstlisting}

\noindent where $b$ is a boolean expression and where both $cs_{1/2}$

are the statements for each of the \pcode{if}-branches. Let us assume we

already generated code for $b$ and and the two if-branches $cs_{1/2}$.

Then in the true-case the control-flow of the program needs to behave as

\begin{center}

\begin{tikzpicture}[node distance=2mm and 4mm,line cap=round,

 block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm,

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

 point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red},

 skip loop/.style={black, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}]

\node (A1) [point] {};

\node (b) [block, right=of A1] {code of $b$};

\node (A2) [point, right=of b] {};

\node (cs1) [block, right=of A2] {code of $cs_1$};

\node (A3) [point, right=of cs1] {};

\node (cs2) [block, right=of A3] {code of $cs_2$};

\node (A4) [point, right=of cs2] {};

\draw (A1) edge [->, black, line width=1mm] (b);

\draw (b) edge [->, black, line width=1mm] (cs1);

\draw (cs1) edge [->, black, line width=1mm,shorten >= -0.5mm] (A3);

\draw (A3) edge [->, black, skip loop] (A4);

\node [below=of cs2] {\raisebox{-5mm}{\small{}jump}};

\end{tikzpicture}

\end{center}

\noindent where we start with running the code for $b$; since

we are in the true case we continue with running the code for

$cs_1$. After this however, we must not run the code for

$cs_2$, but always jump to after the last instruction of $cs_2$

(the code for the \pcode{else}-branch). Note that this jump is

unconditional, meaning we always have to jump to the end of

$cs_2$. The corresponding instruction of the JVM is

\instr{goto}. In case $b$ turns out to be false we need the

control-flow

\begin{center}

\begin{tikzpicture}[node distance=2mm and 4mm,line cap=round,

 block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm,

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

 point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red},

 skip loop/.style={black, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}]

\node (A1) [point] {};

\node (b) [block, right=of A1] {code of $b$};

\node (A2) [point, right=of b] {};

\node (cs1) [block, right=of A2] {code of $cs_1$};

\node (A3) [point, right=of cs1] {};

\node (cs2) [block, right=of A3] {code of $cs_2$};

\node (A4) [point, right=of cs2] {};

\draw (A1) edge [->, black, line width=1mm] (b);

\draw (b) edge [->, black, line width=1mm,shorten >= -0.5mm] (A2);

\draw (A2) edge [skip loop] (A3);

\draw (A3) edge [->, black, line width=1mm] (cs2);

\draw (cs2) edge [->,black, line width=1mm] (A4);

\node [below=of cs1] {\raisebox{-5mm}{\small{}conditional jump}};

\end{tikzpicture}

\end{center}

\noindent where we now need a conditional jump (if the

if-condition is false) from the end of the code for the 

boolean to the beginning of the instructions $cs_2$. Once we 

are finished with running $cs_2$ we can continue with whatever

code comes after the if-statement.

The \instr{goto} and the conditional jumps need addresses to

where the jump should go. Since we are generating assembly

code for the JVM, we do not actually have to give (numeric)

addresses, but can just attach (symbolic) labels to our code.

These labels specify a target for a jump. Therefore the labels

need to be unique, as otherwise it would be ambiguous where a

jump should go to. A label, say \pcode{L}, is attached to assembly 

code like

\begin{lstlisting}[mathescape,numbers=none]

L:

  $\textit{instr\_1}$

  $\textit{instr\_2}$

    $\vdots$

\end{lstlisting}

\noindent where the label needs to be followed by a colon. The task of

the assembler (in our case Jasmin or Krakatau) is to resolve the labels

to actual (numeric) addresses, for example jump 10 instructions forward,

or 20 instructions backwards.

Recall the ``trick'' with compiling boolean expressions: the 

\textit{compile}-function for boolean expressions takes three

arguments: an abstract syntax tree, an environment for 

variable indices and also the label, $lab$, to where an conditional 

jump needs to go. The clause for the expression $a_1 = a_2$, 

for example, is as follows:

\begin{center}

\begin{tabular}{lcl}

$\textit{compile}(a_1 = a_2, E, lab)$ & $\dn$\\ 

\multicolumn{3}{l}{$\qquad\textit{compile}(a_1, E) \;@\;\textit{compile}(a_2, E)\;@\; \instr{if_icmpne}\;lab$}

\end{tabular}

\end{center}

\noindent where we are first generating code for the

subexpressions $a_1$ and $a_2$. This will mean after running

the corresponding code there will be two integers on top of

the stack. If they are equal, we do not have to do anything

(except for popping them off from the stack) and just continue

with the next instructions (see control-flow of ifs above).

However if they are \emph{not} equal, then we need to

(conditionally) jump to the label $lab$. This can be done with

the instruction

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

if_icmpne $lab$

\end{lstlisting}

To sum up, the third argument in the compile function for booleans

specifies where to jump, in case the condition is \emph{not} true. I

leave it to you to extend the \textit{compile}-function for the other

boolean expressions. Note that we need to jump whenever the boolean is

\emph{not} true, which means we have to ``negate'' the jump

condition---equals becomes not-equal, less becomes greater-or-equal. 

Other jump instructions for boolean operators are

\begin{center}

\begin{tabular}{l@{\hspace{10mm}}c@{\hspace{10mm}}l}

$\not=$ & $\Rightarrow$ & \instr{if_icmpeq}\\

$<$ & $\Rightarrow$ & \instr{if_icmpge}\\

$\le$ & $\Rightarrow$ & \instr{if_icmpgt}\\

\end{tabular}

\end{center}

\noindent and so on.   If you do not like this design (it can be the

source of some nasty, hard-to-detect errors), you can also change the

layout of the code and first give the code for the else-branch and then

for the if-branch. However in the case of while-loops this

``upside-down-inside-out'' way of generating code still seems the most

convenient.

We are now ready to give the compile function for 

if-statements---remember this function returns for statements a 

pair consisting of the code and an environment:

\begin{center}

\begin{tabular}{lcl}

$\textit{compile}(\pcode{if}\;b\;\pcode{then}\; cs_1\;\pcode{else}\; cs_2, E)$ & $\dn$\\ 

\multicolumn{3}{l}{$\qquad L_\textit{ifelse}\;$ (fresh label)}\\

\multicolumn{3}{l}{$\qquad L_\textit{ifend}\;$ (fresh label)}\\

\multicolumn{3}{l}{$\qquad (is_1, E') = \textit{compile}(cs_1, E)$}\\

\multicolumn{3}{l}{$\qquad (is_2, E'') = \textit{compile}(cs_2, E')$}\\

\multicolumn{3}{l}{$\qquad(\textit{compile}(b, E, L_\textit{ifelse})$}\\

\multicolumn{3}{l}{$\qquad\phantom{(}@\;is_1$}\\

\multicolumn{3}{l}{$\qquad\phantom{(}@\; \pcode{goto}\;L_\textit{ifend}$}\\

\multicolumn{3}{l}{$\qquad\phantom{(}@\;L_\textit{ifelse}:$}\\

\multicolumn{3}{l}{$\qquad\phantom{(}@\;is_2$}\\

\multicolumn{3}{l}{$\qquad\phantom{(}@\;L_\textit{ifend}:, E'')$}\\

\end{tabular}

\end{center}

\noindent In the first two lines we generate two fresh labels

for the jump addresses (just before the else-branch and just

after). In the next two lines we generate the instructions for

the two branches, $is_1$ and $is_2$. The final code will

be first the code for $b$ (including the label 

just-before-the-else-branch), then the \pcode{goto} for after

the else-branch, the label $L_\textit{ifelse}$, followed by

the instructions for the else-branch, followed by the 

after-the-else-branch label. Consider for example the 

if-statement:

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

if 1 = 1 then x := 2 else y := 3

\end{lstlisting}

\noindent 

The generated code is as follows:

\begin{lstlisting}[language=JVMIS,mathescape,numbers=left]