71 \end{tabular}% |
71 \end{tabular}% |
72 }; |
72 }; |
73 \end{tikzpicture} |
73 \end{tikzpicture} |
74 \end{center} |
74 \end{center} |
75 \end{frame} |
75 \end{frame} |
76 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
76 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
77 |
|
78 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
79 \tikzstyle{sensor}=[draw, fill=blue!20, text width=3.8em, line width=1mm, |
|
80 text centered, minimum height=2em,drop shadow] |
|
81 \tikzstyle{ann} = [above, text width=4em, text centered] |
|
82 \tikzstyle{sc} = [sensor, text width=7em, fill=red!20, |
|
83 minimum height=6em, rounded corners, drop shadow,line width=1mm] |
|
84 |
|
85 \begin{frame}[fragile,c] |
|
86 \frametitle{LLVM: Overview} |
|
87 |
|
88 \begin{tikzpicture} |
|
89 % Validation Layer is the same except that there are a set of nodes and links which are added |
|
90 |
|
91 \path (0,0) node (IR) [sc] {\textbf{LLVM-IR}\\ Optimisations}; |
|
92 \path (IR.west)+(-2.2,1.7) node (sou1) [sensor] {C++}; |
|
93 \path (IR.west)+(-2.2,0.5) node (sou2)[sensor] {C}; |
|
94 \path (IR.west)+(-2.2,-1.0) node (dots)[ann] {$\vdots$}; |
|
95 \path (IR.west)+(-2.2,-1.8) node (sou3)[sensor] {Haskell}; |
|
96 |
|
97 \path [draw,->,line width=1mm] (sou1.east) -- node [above] {} (IR.160); |
|
98 \path [draw,->,line width=1mm] (sou2.east) -- node [above] {} (IR.180); |
|
99 \path [draw,->,line width=1mm] (sou3.east) -- node [above] {} (IR.200); |
|
100 |
|
101 \path (IR.east)+(2.2,2.0) node (tar1)[sensor] {x86}; |
|
102 \path (IR.east)+(2.2,0.8) node (tar2)[sensor] {ARM}; |
|
103 \path (IR.east)+(2.2,-0.4) node (tar3)[sensor] {MIPS}; |
|
104 \path (IR.east)+(2.2,-1.6) node (tar4)[sensor] {RISC}; |
|
105 \path (IR.east)+(2.2,-2.8) node (tar5)[sensor] {Power PC}; |
|
106 \path (IR.east)+(2.2,-4.2) node (dots2)[ann] {$\vdots$}; |
|
107 |
|
108 \path [draw,<-,line width=1mm] (tar1.west) -- node [above] {} (IR.10); |
|
109 \path [draw,<-,line width=1mm] (tar2.west) -- node [above] {} (IR.5); |
|
110 \path [draw,<-,line width=1mm] (tar3.west) -- node [above] {} (IR.0); |
|
111 \path [draw,<-,line width=1mm] (tar4.west) -- node [above] {} (IR.-5); |
|
112 \path [draw,<-,line width=1mm] (tar5.west) -- node [above] {} (IR.-10); |
|
113 |
|
114 \end{tikzpicture} |
|
115 \end{frame} |
|
116 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
117 |
77 |
118 |
78 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
119 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
79 \begin{frame}[c,fragile] |
120 \begin{frame}[c,fragile] |
80 \frametitle{Static Single-Assignment} |
121 \frametitle{Static Single-Assignment} |
81 |
122 |
117 def fact(n) = if n == 0 then 1 else n * fact(n - 1) |
158 def fact(n) = if n == 0 then 1 else n * fact(n - 1) |
118 \end{lstlisting} |
159 \end{lstlisting} |
119 \end{frame} |
160 \end{frame} |
120 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
161 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
121 |
162 |
|
163 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
164 \begin{frame}[fragile,c] |
|
165 \frametitle{LLVM Types} |
|
166 |
|
167 \tt |
|
168 \begin{center} |
|
169 \begin{tabular}{ll} |
|
170 boolean & i1 \\ |
|
171 byte & i8 \\ |
|
172 short & i16\\ |
|
173 char & i16\\ |
|
174 integer & i32\\ |
|
175 long & i64\\ |
|
176 float & float\\ |
|
177 double & double\\ |
|
178 *\_ & pointer to \\ |
|
179 **\_ & pointer to a pointer to\\ |
|
180 \mbox{}[\_] & arrays of\\ |
|
181 \end{tabular} |
|
182 \end{center} |
|
183 |
|
184 \end{frame} |
|
185 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
186 |
|
187 |
122 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
188 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
123 \begin{frame}[c,fragile] |
189 \begin{frame}[c,fragile] |
124 |
190 |
125 |
191 |
126 \begin{lstlisting}[language=LLVM,numbers=none] |
192 \begin{lstlisting}[language=LLVM,numbers=none] |
134 %var = call i32 @foo(...args...) |
200 %var = call i32 @foo(...args...) |
135 \end{lstlisting} |
201 \end{lstlisting} |
136 |
202 |
137 \end{frame} |
203 \end{frame} |
138 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
204 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
205 |
|
206 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
207 \begin{frame}[fragile,c] |
|
208 \frametitle{Abstract Syntax Trees} |
|
209 \footnotesize |
|
210 |
|
211 \begin{lstlisting}[language=Scala,numbers=none,xleftmargin=-3mm] |
|
212 // Fun language (expressions) |
|
213 abstract class Exp |
|
214 abstract class BExp |
|
215 |
|
216 case class Call(name: String, args: List[Exp]) extends Exp |
|
217 case class If(a: BExp, e1: Exp, e2: Exp) extends Exp |
|
218 case class Write(e: Exp) extends Exp |
|
219 case class Var(s: String) extends Exp |
|
220 case class Num(i: Int) extends Exp |
|
221 case class Aop(o: String, a1: Exp, a2: Exp) extends Exp |
|
222 case class Sequence(e1: Exp, e2: Exp) extends Exp |
|
223 case class Bop(o: String, a1: Exp, a2: Exp) extends BExp |
|
224 \end{lstlisting} |
|
225 |
|
226 \end{frame} |
|
227 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
228 |
|
229 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
230 \begin{frame}[fragile,c] |
|
231 \frametitle{K-(Intermediate)Language} |
|
232 \footnotesize |
|
233 |
|
234 \begin{lstlisting}[language=Scala,numbers=none,xleftmargin=-3mm] |
|
235 abstract class KExp |
|
236 abstract class KVal |
|
237 |
|
238 // K-Values |
|
239 case class KVar(s: String) extends KVal |
|
240 case class KNum(i: Int) extends KVal |
|
241 case class Kop(o: String, v1: KVal, v2: KVal) extends KVal |
|
242 case class KCall(o: String, vrs: List[KVal]) extends KVal |
|
243 case class KWrite(v: KVal) extends KVal |
|
244 |
|
245 // K-Expressions |
|
246 case class KIf(x1: String, e1: KExp, e2: KExp) extends KExp |
|
247 case class KLet(x: String, v: KVal, e: KExp) extends KExp |
|
248 case class KReturn(v: KVal) extends KExp |
|
249 \end{lstlisting} |
|
250 |
|
251 \end{frame} |
|
252 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
253 |
|
254 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
255 \begin{frame}[fragile,c] |
|
256 \frametitle{KLet} |
|
257 |
|
258 \begin{lstlisting}[language=LLVM] |
|
259 tmp0 = add 1 a |
|
260 tmp1 = mul b 5 |
|
261 tmp2 = add 3 tmp1 |
|
262 tmp3 = add tmp0 tmp2 |
|
263 \end{lstlisting} |
|
264 |
|
265 \begin{lstlisting}[language=LLVMIR] |
|
266 KLet tmp0 , add 1 a in |
|
267 KLet tmp1 , mul b 5 in |
|
268 KLet tmp2 , add 3 tmp1 in |
|
269 KLet tmp3 , add tmp0 tmp2 in |
|
270 ... |
|
271 \end{lstlisting} |
|
272 |
|
273 \begin{lstlisting}[language=Scala,numbers=none] |
|
274 case class KLet(x: String, e1: KVal, e2: KExp) |
|
275 \end{lstlisting} |
|
276 |
|
277 \end{frame} |
|
278 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
279 |
|
280 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
281 \begin{frame}[fragile,c] |
|
282 \frametitle{KLet} |
|
283 |
|
284 \begin{lstlisting}[language=LLVM] |
|
285 tmp0 = add 1 a |
|
286 tmp1 = mul b 5 |
|
287 tmp2 = add 3 tmp1 |
|
288 tmp3 = add tmp0 tmp2 |
|
289 \end{lstlisting} |
|
290 |
|
291 \begin{lstlisting}[language=LLVMIR] |
|
292 let tmp0 = add 1 a in |
|
293 let tmp1 = mul b 5 in |
|
294 let tmp2 = add 3 tmp1 in |
|
295 let tmp3 = add tmp0 tmp2 in |
|
296 ... |
|
297 \end{lstlisting} |
|
298 |
|
299 \begin{lstlisting}[language=Scala,numbers=none] |
|
300 case class KLet(x: String, e1: KVal, e2: KExp) |
|
301 \end{lstlisting} |
|
302 |
|
303 \end{frame} |
|
304 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
305 |
|
306 |
|
307 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
308 \begin{frame}[fragile,c] |
|
309 \frametitle{CPS-Translation} |
|
310 \small |
|
311 |
|
312 \begin{lstlisting}[language=Scala,numbers=none] |
|
313 def CPS(e: Exp)(k: KVal => KExp) : KExp = |
|
314 e match { ... } |
|
315 \end{lstlisting} |
|
316 \bigskip\bigskip |
|
317 |
|
318 the continuation \texttt{k} can be thought of:\medskip |
|
319 |
|
320 \small |
|
321 \begin{lstlisting}[language=LLVMIR,numbers=none,xleftmargin=30mm,escapeinside={(*@}{@*)}] |
|
322 let tmp0 = add 1 a in |
|
323 let tmp1 = mul (*@$\Box$@*) 5 in |
|
324 let tmp2 = add 3 tmp1 in |
|
325 let tmp3 = add tmp0 tmp2 in |
|
326 KReturn tmp3 |
|
327 \end{lstlisting} |
|
328 |
|
329 \end{frame} |
|
330 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
331 |
|
332 |
139 |
333 |
140 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
334 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
141 \begin{frame}[c,fragile] |
335 \begin{frame}[c,fragile] |
142 |
336 |
143 |
337 |