Presentation

1 files changed, 222 insertions, 0 deletions

diff --git a/presentation/pres.tex b/presentation/pres.tex
new file mode 100644
index 0000000..70aa594
--- /dev/null
+++ b/presentation/pres.tex
@@ -0,0 +1,222 @@
+\documentclass[british]{beamer}
+
+\usepackage[british]{babel}
+\usepackage[babel=true]{csquotes}
+
+\usepackage{tikz}
+\usetikzlibrary{calc}
+\usepackage{pgfplots}
+
+\title{Code generation for the Thumb-2 instruction set}
+\author[Camil Staps]{
+	Camil Staps\\[1em]\small{
+		\emph{Supervisors:}\\
+		prof. dr. dr.h.c. ir. M.J. Plasmeijer\\
+		drs. J.H.G. van Groningen}}
+\date{Monday 9\textsuperscript{th} January, 2017}
+
+\begin{document}
+
+\maketitle
+
+\section{Introduction}
+
+\begin{frame}{ARM and Thumb}
+	\begin{itemize}
+		\item Widely used in embedded systems
+		\item Three instruction sets:
+			\begin{itemize}
+				\item ARM (32-bit)
+				\item Thumb (16-bit)
+				\item Thumb-2 (mixture)
+			\end{itemize}
+		\item Thumb-2 advantages:
+			\begin{itemize}
+				\item Smaller code than ARM
+				\item Simpler devices than ARM
+				\item Faster than Thumb
+			\end{itemize}
+		\item Interesting differences for code generation:
+			\begin{itemize}
+				\item How to deal with instructions that do not exist in Thumb-2?
+				\item How to use as many 16-bit instructions as possible?
+			\end{itemize}
+	\end{itemize}
+\end{frame}
+
+\begin{frame}{Clean}
+	\begin{minipage}{.65\linewidth}
+		\begin{itemize}
+			\item Purely functional, lazy programming language
+			\item Compilation in several steps
+			\item Already had an ARM code generator
+			\item Made one for Thumb-2
+		\end{itemize}
+	\end{minipage}%
+	\begin{minipage}{.35\linewidth}
+		\centering
+		\footnotesize
+		\begin{tikzpicture}[every node/.style={rectangle,draw},every path/.style={draw},->]
+			\node (clean) {Clean};
+			\node[below of=clean] (core) {Core Clean};
+			\node[below of=core] (abc) {ABC-code};
+			\node[below of=abc] (abstr) {Abstract Von-Neumann};
+			\node[below of=abstr] (target) {Target machine};
+			\path (clean) -- (core) -- (abc) -- (abstr) -- (target);
+		\end{tikzpicture}
+	\end{minipage}
+\end{frame}
+
+\section{Register allocation}
+
+\begin{frame}{Register allocation --- introduction}
+	\begin{itemize}
+		\item ARM has 16 registers; Thumb only lower eight
+		\item Higher registers can be accessed through 32-bit instructions in Thumb-2
+		\item Want to put frequently used registers in lower half
+	\end{itemize}
+\end{frame}
+
+\begin{frame}{Register allocation --- collecting data}
+	\begin{itemize}
+		\item Count register usage in the Clean compiler:
+	\end{itemize}
+
+	\begin{center}
+	\begin{tikzpicture}
+		\scriptsize
+		\begin{axis}
+			[ xbar
+			, bar width=.5em
+			, xmin=0
+			, height=0.6\textheight
+			, symbolic y coords={S0,A ptr.,A0,Heap ptr.,A1,B0,A2,B ptr.,B1,S1,B2,B3,B4,Heap ctr.,A3}
+			, ytick=data
+			, scaled x ticks=real:1
+			, xtick scale label code/.code={}
+			, axis lines*=left
+			, compat={1.3}
+			]
+			\addplot coordinates {
+				(378618,S0)
+				(270274,A ptr.)
+				(218018,A0)
+				(166284,Heap ptr.)
+				(152821,A1)
+				(110390,B0)
+				(107481,A2)
+				(102640,B ptr.)
+				( 64496,B1)
+				( 55526,S1)
+				( 41092,B2)
+				( 25924,B3)
+				( 15699,B4)
+				( 14930,Heap ctr.)
+				(  9413,A3)
+			};
+			\draw ($({axis cs:85000,S0})-(0,2em)$) -- ($({axis cs:85000,A3})+(0,2em)$);
+		\end{axis}
+	\end{tikzpicture}
+\end{center}
+\end{frame}
+
+\begin{frame}{Register allocation --- the foreign function interface}
+	\begin{itemize}
+		\item ARM, Inc. describes how function calls should take place
+		\item Need to adhere to the specification to be able to link with C
+		\item Lowest four registers are not preserved upon a function call
+		\item Trade-off: code size vs. efficient foreign function interface
+	\end{itemize}
+\end{frame}
+
+\begin{frame}{Register allocation --- results}
+	\begin{center}
+		\begin{tikzpicture}
+			\begin{axis}
+				[ xbar
+				, width=.7\textwidth
+				, height=.5\textheight
+				, xmin=0, xmax=6000000
+				, xlabel={Bytes}
+				, ytick=\empty
+				, reverse stacked plots
+				, ymin=-1, ymax=1
+				, axis lines*=left
+				, nodes near coords, nodes near coords align=west
+				, reverse legend
+				, every axis plot/.append style={point meta=explicit symbolic}
+				, legend style={at={(0.5,-0.5)},anchor=north,legend columns=-1}
+				]
+				\addplot coordinates { (3827868,0) [81.6\%] };
+				\addplot coordinates { (4385964,0) [93.5\%] };
+				\addplot coordinates { (4692628,0) [100\%] };
+				\legend{Thumb (Code size), Thumb (FFI), ARM}
+			\end{axis}
+		\end{tikzpicture}
+	\end{center}
+\end{frame}
+
+\section{Results}
+
+\begin{frame}{Results}
+	\begin{itemize}
+		\item Benchmarks with Clean's \enquote{small examples}
+		\item Code size decrease: $\overline{x}=17.3\%, \sigma=6.3\text{pp.}$\\
+			Without tiny programs: $\overline{x}=21.0\%, \sigma=2.6\text{pp.}$
+		\item Running time increase: $\overline{x}=4.8\%, \sigma=3.1\text{pp.}$\\
+			Without tiny programs: $\overline{x}=3.7\%, \sigma=2.04\text{pp.}$
+		\item Subroutine calls are expensive,
+			so Thumb-2 performance is worse for highly recursive programs
+	\end{itemize}
+\end{frame}
+
+\begin{frame}{Matching programs and instruction sets?}
+	\begin{center}
+		\begin{tikzpicture}
+			\begin{axis}
+				[ width=.8\textwidth
+				, xlabel={Size decrease (\%)}
+				, ylabel={Running time increase (\%)}
+				, mark options={scale=2}
+				, scatter/classes={%
+					a={mark=x,draw=red},
+					b={mark=+,draw=black}}
+				]
+				\addplot[scatter,only marks,scatter src=explicit symbolic]
+					table[meta=label,row sep=crcr] {
+						x     y    label\\
+						12.8  11.9 a\\
+						18.6  3.6  b\\
+						9.8   5.1  a\\
+						18.9  5.9  b\\
+						18.9  3.7  b\\
+						20.1  5.4  a\\
+						22.9  0.9  a\\
+						0.0   2.6  a\\
+						20.0  5.2  b\\
+						22.0  0.0  b\\
+						12.1  8.0  a\\
+					};
+			\end{axis}
+		\end{tikzpicture}
+	\end{center}
+\end{frame}
+
+\section{Further work}
+
+\begin{frame}{Further work}
+	\begin{itemize}
+		\item Branch optimisation (up to 1.2pp. code size win)
+		\item Subroutine calls need extra instructions on Thumb-2;
+			optimise this to save up to 4pp. on code size
+	\end{itemize}
+
+	Overall expected code size win: $\approx$25\% (comparable to GCC)
+
+	\begin{itemize}
+		\item Copying collector needs some fine-tuning
+		\item Two other garbage collectors not considered yet
+	\end{itemize}
+\end{frame}
+
+\end{document}