1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
|
% 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}
|
