% vim: spelllang=nl:
\documentclass{beamer}

\usepackage[dutch]{babel}

\usepackage{tikz}
\usetikzlibrary{calc}
\usepackage{pgfplots}

\title{Codegeneratie voor de Thumb-2 instructieset}
\author[Camil Staps]{
	Camil Staps\\[1em]\small{
		\emph{Begeleiders:}\\
		prof. dr. dr.h.c. ir. M.J. Plasmeijer\\
		drs. J.H.G. van Groningen}}
\date{Dinsdag 24 januari 2017}

\begin{document}

\maketitle

\section{Inleiding}

\begin{frame}{ARM en Thumb}
	\begin{itemize}
		\item Veel gebruikt in embedded systems
		\item Drie instructiesets:
			\begin{itemize}
				\item ARM (32-bit)
				\item Thumb (16-bit)
				\item Thumb-2 (combinatie)
			\end{itemize}
		\item Meeste processoren ondersteunen alledrie
		\item Voordelen van Thumb-2:
			\begin{itemize}
				\item Kleinere code dan ARM
				\item Simpelere systemen dan ARM
				\item Sneller dan Thumb
			\end{itemize}
		\item Interessante eigenschappen voor codegeneratie:
			\begin{itemize}
				\item Wat te doen met instructies die niet bestaan in Thumb-2?
				\item Hoe kunnen we het aantal 16-bit instructies maximaliseren?
			\end{itemize}
	\end{itemize}
\end{frame}

\begin{frame}{Clean}
	\begin{minipage}{.65\linewidth}
		\begin{itemize}
			\item Pure functionele luie programmeertaal
			\item Compilatie gaat in meerdere stappen
			\item Codegenerator voor ARM bestond al
			\item \emph{Case study}: aanpassen voor Thumb-2
		\end{itemize}
	\end{minipage}%
	\hfill
	\begin{minipage}{.3\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) {Abstracte Von-Neumann};
			\node[below of=abstr] (target) {Target machine};
			\path (clean) -- (core) -- (abc) -- (abstr) -- (target);
		\end{tikzpicture}
	\end{minipage}
\end{frame}

\section{Problemen oplossen}

\begin{frame}{Problemen oplossen}
	\begin{itemize}
		\item Program counter opslaan voor functieaanroepen
		\item Informatie in de laagste twee bits
		\item Kleinere constanten (memory load instructies)
	\end{itemize}
\end{frame}

\section{Registerallocatie}

\begin{frame}{Registerallocatie --- inleiding}
	\begin{itemize}
		\item ARM heeft 16 registers; Thumb kan alleen bij de laagste 8
		\item Hogere registers worden benaderd met 32-bit instructies in Thumb-2
		\item Zet veelgebruikte registers in de laagste helft
	\end{itemize}
\end{frame}

\begin{frame}{Registerallocatie --- data}
	\begin{itemize}
		\item Registergebruik in de Clean compiler:
	\end{itemize}

	\begin{center}
	\begin{tikzpicture}
		\scriptsize
		\begin{axis}
			[ xbar
			, bar width=.5em
			, xmin=0
			, height=0.6\textheight
			, symbolic y coords={Scratch 0,A-stack pointer,A-stack 0,Heap pointer,A-stack 1,B-stack 0,A-stack 2,B-stack pointer,B-stack 1,Scratch 1,B-stack 2,B-stack 3,B-stack 4,Heap counter,A-stack 3}
			, ytick=data
			, scaled x ticks=real:1
			, xtick scale label code/.code={}
			, axis lines*=left
			, compat={1.3}
			]
			\addplot coordinates {
				(378618,Scratch 0)
				(270274,A-stack pointer)
				(218018,A-stack 0)
				(166284,Heap pointer)
				(152821,A-stack 1)
				(110390,B-stack 0)
				(107481,A-stack 2)
				(102640,B-stack pointer)
				( 64496,B-stack 1)
				( 55526,Scratch 1)
				( 41092,B-stack 2)
				( 25924,B-stack 3)
				( 15699,B-stack 4)
				( 14930,Heap counter)
				(  9413,A-stack 3)
			};
			\draw ($({axis cs:85000,Scratch 0})-(0,2em)$) -- ($({axis cs:85000,A-stack 3})+(0,2em)$);
		\end{axis}
	\end{tikzpicture}
\end{center}
\end{frame}

\begin{frame}{Registerallocatie --- de foreign function interface}
	\begin{itemize}
		\item ARM, Inc. beschrijft hoe functieaanroepen plaatsvinden
		\item We moeten hieraan voldoen om met C te kunnen linken
		\item Laagste vier registers zijn functieargumenten
		\item Meeste functieargumenten komen van de B-stack
		\item Vier elementen van de B-stack in de laagste acht registers is te veel
		\item Trade-off: programmagrootte vs. effici\"ente foreign function interface
		\item Registerallocatie voor ARM optimaliseert de FFI
	\end{itemize}
\end{frame}

\begin{frame}{Registerallocatie --- resultaten}
	\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 (programmagrootte), Thumb (FFI), ARM}
			\end{axis}
		\end{tikzpicture}
	\end{center}
\end{frame}

\section{Resultaten}

\begin{frame}{Results}
	\begin{itemize}
		\item Benchmarks met Clean's \emph{small examples}
		\item Winst op programmagrootte: $\overline{x}=17.3\%, \sigma=6.3\text{pp.}$\\
			Zonder kleine programma's: $\overline{x}=21.0\%, \sigma=2.6\text{pp.}$
		\item Verlies op snelheid: $\overline{x}=4.8\%, \sigma=3.1\text{pp.}$\\
			Zonder kleine programma's: $\overline{x}=3.7\%, \sigma=2.04\text{pp.}$
		\item Functieaanroepen zijn duur,
			dus Thumb-2 geeft slechte resultaten voor programma's als Fibonacci
	\end{itemize}
\end{frame}

\begin{frame}{Programma's en instructiesets matchen?}
	\begin{center}
		\begin{tikzpicture}
			\begin{axis}
				[ width=.8\textwidth
				, xlabel={Winst programmagrootte (\%)}
				, ylabel={Verlies snelheid (\%)}
				, 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{Vooruit denken}

\begin{frame}{Vooruit denken}
	\begin{itemize}
		\item Branchoptimalisatie (tot 2.2pp. winst programmagrootte)
		\item Optimaliseer functieaanroepen voor tot $\approx4$pp. winst programmagrootte
		\item Thumb-2-\emph{only} instructies voor snelheidswinst
	\end{itemize}

	Uiteindelijke winst programmagrootte (schatting): $\approx$25\%

	\begin{itemize}
		\item Copying collector moet nog wat bijgeschaafd worden
		\item Andere garbage collectors zijn nog niet bekeken
		\item Foreign function interface moet verder getest worden
	\end{itemize}
\end{frame}

\end{document}