60 |
60 |
61 \end{frame} |
61 \end{frame} |
62 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
62 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
63 |
63 |
64 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
64 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
65 \begin{frame}[t,fragile] |
|
66 \frametitle{Compiling AExps} |
|
67 |
|
68 For example \bl{$1 + ((2 * 3) + (4 - 3))$}:\medskip |
|
69 |
|
70 \begin{columns}[T] |
|
71 \begin{column}{.3\textwidth} |
|
72 \begin{center} |
|
73 \bl{\begin{tikzpicture} |
|
74 \tikzset{level distance=12mm,sibling distance=4mm} |
|
75 \tikzset{edge from parent/.style={draw,very thick}} |
|
76 \Tree [.$+$ [.$1$ ] [.$+$ [.$*$ $2$ $3$ ] [.$-$ $4$ $3$ ]]] |
|
77 \end{tikzpicture}} |
|
78 \end{center} |
|
79 \end{column} |
|
80 \begin{column}{.3\textwidth} |
|
81 \begin{lstlisting}[language=JVMIS,numbers=none] |
|
82 ldc 1 |
|
83 ldc 2 |
|
84 ldc 3 |
|
85 imul |
|
86 ldc 4 |
|
87 ldc 3 |
|
88 isub |
|
89 iadd |
|
90 iadd |
|
91 \end{lstlisting} |
|
92 \end{column} |
|
93 \end{columns}\bigskip |
|
94 |
|
95 \small |
|
96 Traverse tree in post-order \bl{$\Rightarrow$} code for |
|
97 stack-machine |
|
98 |
|
99 \end{frame} |
|
100 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
101 |
|
102 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
103 \begin{frame}[c,fragile] |
|
104 \frametitle{Compiling AExps} |
|
105 |
|
106 \bl{ |
|
107 \begin{center} |
|
108 \begin{tabular}{lcl} |
|
109 $\textit{compile}(n, E)$ & $\dn$ & $\pcode{ldc}\;n$\smallskip\\ |
|
110 $\textit{compile}(a_1 + a_2, E)$ & $\dn$ \\ |
|
111 \multicolumn{3}{c}{$\qquad\textit{compile}(a_1, E) \;@\;\textit{compile}(a_2, E)\;@\; \pcode{iadd}$}\smallskip\\ |
|
112 $\textit{compile}(a_1 - a_2, E)$ & $\dn$ \\ |
|
113 \multicolumn{3}{c}{$\qquad\textit{compile}(a_1, E) \;@\; \textit{compile}(a_2, E)\;@\; \pcode{isub}$}\smallskip\\ |
|
114 $\textit{compile}(a_1 * a_2, E)$ & $\dn$ \\ |
|
115 \multicolumn{3}{c}{$\qquad\textit{compile}(a_1, E) \;@\; \textit{compile}(a_2, E)\;@\; \pcode{imul}$}\smallskip\\ |
|
116 $\textit{compile}(a_1 \backslash a_2, E)$ & $\dn$\\ |
|
117 \multicolumn{3}{c}{$\qquad\textit{compile}(a_1, E) \;@\; \textit{compile}(a_2, E)\;@\; \pcode{idiv}$}\smallskip\\ |
|
118 $\textit{compile}(x, E)$ & $\dn$ & $\pcode{iload}\;E(x)$\\ |
|
119 \end{tabular} |
|
120 \end{center}} |
|
121 |
|
122 \end{frame} |
|
123 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
124 |
|
125 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
126 \begin{frame}[c,fragile] |
|
127 \frametitle{Compiling Ifs} |
|
128 |
|
129 For example |
|
130 |
|
131 \begin{lstlisting}[mathescape,numbers=none,language={}] |
|
132 if 1 = 1 then x := 2 else y := 3 |
|
133 \end{lstlisting} |
|
134 |
|
135 |
|
136 \begin{center} |
|
137 \begin{lstlisting}[mathescape,language=JVMIS,numbers=none] |
|
138 ldc 1 |
|
139 ldc 1 |
|
140 if_icmpne L_ifelse $\quad\tikz[remember picture] \node (C) {\mbox{}};$ |
|
141 ldc 2 |
|
142 istore 0 |
|
143 goto L_ifend $\quad\tikz[remember picture] \node (A) {\mbox{}};$ |
|
144 L_ifelse: $\quad\tikz[remember picture] \node[] (D) {\mbox{}};$ |
|
145 ldc 3 |
|
146 istore 1 |
|
147 L_ifend: $\quad\tikz[remember picture] \node[] (B) {\mbox{}};$ |
|
148 \end{lstlisting} |
|
149 \end{center} |
|
150 |
|
151 \begin{tikzpicture}[remember picture,overlay] |
|
152 \draw[->,very thick] (A) edge [->,to path={-- ++(10mm,0mm) |
|
153 -- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (B.east); |
|
154 \draw[->,very thick] (C) edge [->,to path={-- ++(10mm,0mm) |
|
155 -- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (D.east); |
|
156 \end{tikzpicture} |
|
157 |
|
158 \end{frame} |
|
159 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
160 |
|
161 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
162 \begin{frame}[c,fragile] |
|
163 \frametitle{Compiling Whiles} |
|
164 |
|
165 For example |
|
166 |
|
167 \begin{lstlisting}[mathescape,numbers=none,language={}] |
|
168 while x <= 10 do x := x + 1 |
|
169 \end{lstlisting} |
|
170 |
|
171 |
|
172 \begin{center} |
|
173 \begin{lstlisting}[mathescape,language=JVMIS,numbers=none] |
|
174 L_wbegin: $\quad\tikz[remember picture] \node[] (LB) {\mbox{}};$ |
|
175 iload 0 |
|
176 ldc 10 |
|
177 if_icmpgt L_wend $\quad\tikz[remember picture] \node (LC) {\mbox{}};$ |
|
178 iload 0 |
|
179 ldc 1 |
|
180 iadd |
|
181 istore 0 |
|
182 goto L_wbegin $\quad\tikz[remember picture] \node (LA) {\mbox{}};$ |
|
183 L_wend: $\quad\tikz[remember picture] \node[] (LD) {\mbox{}};$ |
|
184 \end{lstlisting} |
|
185 \end{center} |
|
186 |
|
187 \begin{tikzpicture}[remember picture,overlay] |
|
188 \draw[->,very thick] (LA) edge [->,to path={-- ++(12mm,0mm) |
|
189 -- ++(0mm,17.3mm) |- (\tikztotarget)},line width=1mm] (LB.east); |
|
190 \draw[->,very thick] (LC) edge [->,to path={-- ++(12mm,0mm) |
|
191 -- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (LD.east); |
|
192 \end{tikzpicture} |
|
193 |
|
194 \end{frame} |
|
195 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
196 |
|
197 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
198 \begin{frame}[c,fragile] |
|
199 \frametitle{Compiling Writes} |
|
200 |
|
201 \small |
|
202 \begin{lstlisting}[language=JVMIS,mathescape, |
|
203 numbers=none,xleftmargin=-6mm] |
|
204 .method public static write(I)V |
|
205 .limit locals 1 |
|
206 .limit stack 2 |
|
207 getstatic java/lang/System/out |
|
208 Ljava/io/PrintStream; |
|
209 iload 0 |
|
210 invokevirtual java/io/PrintStream/println(I)V |
|
211 return |
|
212 .end method |
|
213 |
|
214 |
|
215 |
|
216 iload $E(x)$ |
|
217 invokestatic XXX/XXX/write(I)V |
|
218 \end{lstlisting} |
|
219 |
|
220 \end{frame} |
|
221 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
222 |
|
223 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
224 \begin{frame}[c,fragile] |
|
225 \frametitle{Compiling Main} |
|
226 |
|
227 \footnotesize |
|
228 \begin{lstlisting}[language=JVMIS,mathescape, |
|
229 numbers=none,xleftmargin=-6mm] |
|
230 .class public XXX.XXX |
|
231 .super java/lang/Object |
|
232 |
|
233 .method public <init>()V |
|
234 aload_0 |
|
235 invokenonvirtual java/lang/Object/<init>()V |
|
236 return |
|
237 .end method |
|
238 |
|
239 .method public static main([Ljava/lang/String;)V |
|
240 .limit locals 200 |
|
241 .limit stack 200 |
|
242 |
|
243 $\textit{\ldots{}here comes the compiled code\ldots}$ |
|
244 |
|
245 return |
|
246 .end method |
|
247 \end{lstlisting} |
|
248 |
|
249 \end{frame} |
|
250 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
251 |
|
252 |
|
253 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
65 \begin{frame}[c,fragile] |
254 \begin{frame}[c,fragile] |
66 \frametitle{Functional Programming} |
255 \frametitle{Functional Programming} |
67 |
256 |
68 \footnotesize |
257 \footnotesize |
69 \begin{textblock}{13}(0.9,3) |
258 \begin{textblock}{13}(0.9,3) |
70 \begin{lstlisting}[basicstyle=\ttfamily, numbers=none] |
259 \begin{lstlisting}[]numbers=none] |
71 def fib(n) = if n == 0 then 0 |
260 def fib(n) = if n == 0 then 0 |
72 else if n == 1 then 1 |
261 else if n == 1 then 1 |
73 else fib(n - 1) + fib(n - 2); |
262 else fib(n - 1) + fib(n - 2); |
74 |
263 |
75 def fact(n) = if n == 0 then 1 else n * fact(n - 1); |
264 def fact(n) = if n == 0 then 1 else n * fact(n - 1); |
135 |
324 |
136 \end{frame} |
325 \end{frame} |
137 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
326 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
138 |
327 |
139 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
328 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
140 \begin{frame}[c] |
|
141 \frametitle{Arithmetic Functions} |
|
142 |
|
143 Compilation of some aritmetic functions: |
|
144 |
|
145 \begin{center} |
|
146 \begin{tabular}{lcl} |
|
147 \texttt{Aop("+", a1, a2)} & $\Rightarrow$ & \texttt{...iadd}\\ |
|
148 \texttt{Aop("-", a1, a2)} & $\Rightarrow$ & \texttt{...isub}\\ |
|
149 \texttt{Aop("*", a1, a2)} & $\Rightarrow$ & \texttt{...imul}\\ |
|
150 \texttt{Aop("/", a1, a2)} & $\Rightarrow$ & \texttt{...idiv}\\ |
|
151 \texttt{Aop("\%", a1, a2)} & $\Rightarrow$ & \texttt{...irem}\\ |
|
152 \end{tabular} |
|
153 \end{center} |
|
154 |
|
155 \end{frame} |
|
156 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
157 |
|
158 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
159 \begin{frame}[c] |
|
160 \frametitle{Boolean Expressions} |
|
161 |
|
162 Compilation of Boolean expressions: |
|
163 |
|
164 \begin{center} |
|
165 \begin{tikzpicture}[node distance=2mm and 4mm, |
|
166 block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm}, |
|
167 point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red}, |
|
168 skip loop/.style={red, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}] |
|
169 \node (A1) [point] {}; |
|
170 \node (b) [block, right=of A1] {code of \bl{$b$}}; |
|
171 \node (A2) [point, right=of b] {}; |
|
172 \node (cs1) [block, right=of A2] {code of \bl{$cs_1$}}; |
|
173 \node (A3) [point, right=of cs1] {}; |
|
174 \node (cs2) [block, right=of A3] {code of \bl{$cs_2$}}; |
|
175 \node (A4) [point, right=of cs2] {}; |
|
176 |
|
177 \only<1>{ |
|
178 \draw (A1) edge [->, red, line width=1mm] (b); |
|
179 \draw (b) edge [->, red, line width=1mm] (A2); |
|
180 \draw (A2) edge [skip loop] (A3); |
|
181 \draw (A3) edge [->, red, line width=1mm] (cs2); |
|
182 \draw (cs2) edge [->,red, line width=1mm] (A4); |
|
183 \node [below=of cs1] {\raisebox{-5mm}{\small{}conditional jump}};} |
|
184 \end{tikzpicture} |
|
185 \end{center} |
|
186 |
|
187 \begin{center} |
|
188 \begin{tabular}{lcl} |
|
189 \texttt{Bop("==", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpne...}\\ |
|
190 \texttt{Bop("!=", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpeq...}\\ |
|
191 \texttt{Bop("<", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpge...}\\ |
|
192 \texttt{Bop("<=", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpgt...}\\ |
|
193 \end{tabular} |
|
194 \end{center} |
|
195 |
|
196 \end{frame} |
|
197 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
198 |
|
199 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
200 \begin{frame}[c, fragile] |
329 \begin{frame}[c, fragile] |
201 \frametitle{Sequences} |
330 \frametitle{Sequences} |
202 |
331 |
203 Compiling \texttt{arg1 ; arg2}:\bigskip |
332 Compiling \texttt{exp1 ; exp2}:\bigskip |
204 |
333 |
205 |
334 |
206 \begin{lstlisting}[language=JVMIS, numbers=none] |
335 \begin{lstlisting}[mathescape,language=JVMIS, numbers=none] |
207 ...arg1... |
336 $\textit{compile}$(exp1) |
208 pop |
337 pop |
209 ...arg1... |
338 $\textit{compile}$(exp2) |
210 \end{lstlisting} |
339 \end{lstlisting} |
211 |
340 |
212 \end{frame} |
341 \end{frame} |
213 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
342 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
214 |
343 |
215 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
344 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
216 \begin{frame}[c, fragile] |
345 \begin{frame}[c, fragile] |
217 \frametitle{Write} |
346 \frametitle{Write} |
218 |
347 |
219 Compiling call to \texttt{write(arg)}:\bigskip |
348 Compiling call to \texttt{write(1+2)}:\bigskip |
220 |
349 |
221 |
350 |
222 \begin{lstlisting}[language=JVMIS, numbers=none] |
351 \begin{lstlisting}[mathescape,language=JVMIS, numbers=none] |
223 ...arg... |
352 $\textit{compile}$(1+2) |
224 dup |
353 dup |
225 invokestatic XXX/XXX/write(I)V |
354 invokestatic XXX/XXX/write(I)V |
226 \end{lstlisting}\bigskip |
355 \end{lstlisting}\bigskip |
227 |
356 |
228 \small |
357 \small |
229 needs a helper function |
358 needs the helper method |
230 |
359 |
231 \end{frame} |
360 \footnotesize |
232 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
361 \begin{lstlisting}[language=JVMIS, |
233 |
362 xleftmargin=2mm, |
234 |
363 numbers=none] |
235 |
364 .method public static write(I)V |
236 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
365 .limit locals 1 |
237 \begin{frame}[c, fragile] |
366 .limit stack 2 |
|
367 getstatic java/lang/System/out Ljava/io/PrintStream; |
|
368 iload 0 |
|
369 invokevirtual java/io/PrintStream/println(I)V |
|
370 return |
|
371 .end method |
|
372 \end{lstlisting} |
|
373 \end{frame} |
|
374 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
375 |
|
376 |
|
377 |
|
378 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
379 \begin{frame}[t, fragile] |
238 \frametitle{Function Definitions} |
380 \frametitle{Function Definitions} |
239 |
381 |
240 \footnotesize |
382 \footnotesize |
241 \begin{lstlisting}[language=JVMIS, |
383 \begin{lstlisting}[language=JVMIS, |
242 xleftmargin=2mm, |
384 xleftmargin=2mm, |
267 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
411 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
268 |
412 |
269 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
413 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
270 \begin{frame}[c, fragile] |
414 \begin{frame}[c, fragile] |
271 \frametitle{Stack Estimation} |
415 \frametitle{Stack Estimation} |
272 \footnotesize |
416 \small |
273 \begin{center} |
417 \mbox{}\\[-15mm] |
274 \begin{lstlisting}[language=Scala,basicstyle=\ttfamily, numbers=none] |
418 |
275 def max_stack_exp(e: Exp): Int = e match { |
419 \bl{\begin{center} |
276 case Call(_, args) => args.map(max_stack_exp).sum |
420 \begin{tabular}{@{\hspace{-4mm}}l@{\hspace{2mm}}c@{\hspace{2mm}}l@{}} |
277 case If(a, e1, e2) => max_stack_bexp(a) + |
421 $\textit{estimate}(n)$ & $\dn$ & $1$\\ |
278 (List(max_stack_exp(e1), max_stack_exp(e1)).max) |
422 $\textit{estimate}(x)$ & $\dn$ & $1$\\ |
279 case Write(e) => max_stack_exp(e) + 1 |
423 $\textit{estimate}(a_1\;aop\;a_2)$ & $\dn$ & |
280 case Var(_) => 1 |
424 $\textit{estimate}(a_1) + \textit{estimate}(a_2)$\\ |
281 case Num(_) => 1 |
425 $\textit{estimate}(\pcode{if}\;b\;\pcode{then}\;e_1\;\pcode{else}\;e_2)$ & $\dn$ & |
282 case Aop(_, a1, a2) => |
426 $\textit{estimate}(b) +$\\ |
283 max_stack_exp(a1) + max_stack_exp(a2) |
427 & & $\quad max(\textit{estimate}(e_1), \textit{estimate}(e_2))$\\ |
284 case Sequ(e1, e2) => |
428 $\textit{estimate}(\pcode{write}(e))$ & $\dn$ & |
285 List(max_stack_exp(e1), max_stack_exp(e2)).max |
429 $\textit{estimate}(e) + 1$\\ |
286 } |
430 $\textit{estimate}(e_1 ; e_2)$ & $\dn$ & |
287 |
431 $max(\textit{estimate}(e_1), \textit{estimate}(e_2))$\\ |
288 def max_stack_bexp(e: BExp): Int = e match { |
432 $\textit{estimate}(f(e_1, ..., e_n))$ & $\dn$ & |
289 case Bop(_, a1, a2) => |
433 $\sum_{i = 1..n}\;estimate(e_i)$\medskip\\ |
290 max_stack_exp(a1) + max_stack_exp(a2) |
434 $\textit{estimate}(a_1\;bop\;a_2)$ & $\dn$ & |
291 } |
435 $\textit{estimate}(a_1) + \textit{estimate}(a_2)$\\ |
292 \end{lstlisting} |
436 \end{tabular} |
293 \end{center} |
437 \end{center}} |
294 |
438 |
295 \end{frame} |
439 \end{frame} |
296 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
440 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
297 |
441 |
298 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
442 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
524 \end{textblock} |
668 \end{textblock} |
525 |
669 |
526 \end{frame} |
670 \end{frame} |
527 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
671 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
528 |
672 |
529 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
673 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
530 \mode<presentation>{ |
674 \begin{frame}[c] |
|
675 \frametitle{Dijkstra on Testing} |
|
676 |
|
677 \begin{bubble}[10cm] |
|
678 ``Program testing can be a very effective way to show the |
|
679 presence of bugs, but it is hopelessly inadequate for showing |
|
680 their absence.'' |
|
681 \end{bubble}\bigskip |
|
682 |
|
683 \small |
|
684 What is good about compilers: the either seem to work, |
|
685 or go horribly wrong (most of the time). |
|
686 |
|
687 \end{frame} |
|
688 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
689 |
|
690 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
531 \begin{frame}[c] |
691 \begin{frame}[c] |
532 |
692 \frametitle{\Large Proving Programs to be Correct} |
533 \large\bf |
693 |
534 Using a compiler, \\how can you mount the\\ perfect attack against a system? |
694 \begin{bubble}[10cm] |
535 |
695 \small |
536 \end{frame}} |
696 {\bf Theorem:} There are infinitely many prime |
537 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
697 numbers.\medskip\\ |
538 |
698 |
539 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
699 {\bf Proof} \ldots\\ |
540 \mode<presentation>{ |
700 \end{bubble}\bigskip |
|
701 |
|
702 |
|
703 similarly\bigskip |
|
704 |
|
705 \begin{bubble}[10cm] |
|
706 \small |
|
707 {\bf Theorem:} The program is doing what |
|
708 it is supposed to be doing.\medskip |
|
709 |
|
710 {\bf Long, long proof} \ldots\\ |
|
711 \end{bubble}\bigskip\medskip |
|
712 |
|
713 \small This can be a gigantic proof. The only hope is to have |
|
714 help from the computer. `Program' is here to be understood to be |
|
715 quite general (compiler, OS, \ldots). |
|
716 |
|
717 \end{frame} |
|
718 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
719 |
|
720 |
|
721 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
722 |
541 \begin{frame}[c] |
723 \begin{frame}[c] |
542 |
724 \frametitle{Can This Be Done?} |
543 {\large\bf |
725 |
544 What is a \alert{perfect} attack?}\bigskip |
726 \begin{itemize} |
545 |
727 \item in 2008, verification of a small C-compiler |
546 \begin{enumerate} |
728 \begin{itemize} |
547 \item you can potentially completely take over a target system |
729 \item ``if my input program has a certain behaviour, then the compiled machine code has the same behaviour'' |
548 \item your attack is (nearly) undetectable |
730 \item is as good as \texttt{gcc -O1}, but much, much less buggy |
549 \item the victim has (almost) no chance to recover |
731 \end{itemize} |
550 \end{enumerate} |
732 \end{itemize} |
551 |
733 |
552 \end{frame}} |
734 \begin{center} |
553 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
735 \includegraphics[scale=0.12]{../pics/compcert.png} |
554 |
736 \end{center} |
555 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
737 |
556 \mode<presentation>{ |
738 \end{frame} |
|
739 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
740 |
|
741 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
557 \begin{frame}[c] |
742 \begin{frame}[c] |
558 |
743 \frametitle{Fuzzy Testing C-Compilers} |
559 |
744 |
560 \begin{center} |
745 \begin{itemize} |
561 \begin{tikzpicture}[scale=1] |
746 \item tested GCC, LLVM and others by randomly generating |
562 |
747 C-programs |
563 \onslide<1->{ |
748 \item found more than 300 bugs in GCC and also |
564 \node (A) at (0,0) [draw=black, rectangle, very thick, minimum height=18mm, minimum width=17mm] {}; |
749 many in LLVM (some of them highest-level critical)\bigskip |
565 \node [below right] at (A.north west) {\footnotesize\begin{tabular}{@{}l@{}} |
750 \item about CompCert: |
566 \only<1,2>{clean}\only<3->{\alert{hacked}}\\compiler\end{tabular}};} |
751 |
567 |
752 \begin{bubble}[10cm]\small ``The striking thing about our CompCert |
568 |
753 results is that the middle-end bugs we found in all other |
569 \onslide<2->{ |
754 compilers are absent. As of early 2011, the under-development |
570 \node (B) at (-2,2) [draw=black, rectangle, very thick, minimum height=10mm, minimum width=12mm] {}; |
755 version of CompCert is the only compiler we have tested for |
571 \node [below right] at (B.north west) {\footnotesize\begin{tabular}{@{}l@{}}login\\(src)\end{tabular}}; |
756 which Csmith cannot find wrong-code errors. This is not for |
572 |
757 lack of trying: we have devoted about six CPU-years to the |
573 \node (C) at (2,2) [draw=black, rectangle, very thick, minimum height=10mm, minimum width=12mm] {}; |
758 task.'' |
574 \node [below right] at (C.north west) {\footnotesize\begin{tabular}{@{}l@{}}login\\(bin)\end{tabular}}; |
759 \end{bubble} |
575 |
760 \end{itemize} |
576 \draw[->, line width=2mm] (B) -- (C); |
761 |
577 } |
762 \end{frame} |
578 |
763 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
579 \onslide<3->{\node [above left=-1.5mm] at (C.south east) {\footnotesize \alert{$\blacksquare$}};} |
|
580 |
|
581 \end{tikzpicture} |
|
582 \end{center} |
|
583 |
|
584 \end{frame}} |
|
585 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
586 |
|
587 |
|
588 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
589 \mode<presentation>{ |
|
590 \begin{frame}[c] |
|
591 |
|
592 \begin{center} |
|
593 \begin{tikzpicture}[scale=1] |
|
594 |
|
595 \onslide<1->{ |
|
596 \node (A) at (0,0) [draw=black, rectangle, very thick, minimum height=18mm, minimum width=14mm] {}; |
|
597 \node [below right] at (A.north west) {\small V0.01}; |
|
598 \node [below right] (A1) at (A.south west) {\small Scala}; |
|
599 \node [below right] (A1) at (A1.south west) {\small\textcolor{gray}{host language}}; |
|
600 \node [above right] at (A.north west) {my compiler (src)};} |
|
601 |
|
602 \onslide<2->{ |
|
603 \node (B) at (1.8,0) [draw=black, rectangle, very thick, minimum height=18mm, minimum width=14mm] {}; |
|
604 \node [below right] at (B.north west) {\small V0.02}; |
|
605 \node [below right] at (B.south west) {\small Scala}; |
|
606 \node at (3,0) {\ldots}; |
|
607 |
|
608 \node (C) at (5,0) [draw=black, rectangle, very thick, minimum height=18mm, minimum width=14mm] {}; |
|
609 \node [below right] at (C.north west) {\small V1.00}; |
|
610 \node [below right] at (C.south west) {\small Scala};} |
|
611 |
|
612 \onslide<3->{ |
|
613 \node (D) at (6.8,0) [draw=black, rectangle, very thick, minimum height=18mm, minimum width=14mm] {}; |
|
614 \node [below right] at (D.north west) {\small V1.00}; |
|
615 |
|
616 \node (E) at (6.8,2) [draw=black, rectangle, very thick, minimum height=18mm, minimum width=14mm] {}; |
|
617 \node [below right] at (E.north west) {\small V1.01};} |
|
618 |
|
619 \onslide<4->{ |
|
620 \node (F) at (8.6,0) [draw=black, rectangle, very thick, minimum height=18mm, minimum width=14mm] {}; |
|
621 \node [below right] at (F.north west) {\small V1.01}; |
|
622 |
|
623 \node (G) at (8.6,2) [draw=black, rectangle, very thick, minimum height=18mm, minimum width=14mm] {}; |
|
624 \node [below right] at (G.north west) {\small V1.02}; |
|
625 \node at (9.8,0) {\ldots}; |
|
626 \node at (9.8,2) {\ldots}; |
|
627 \node at (8,-2) {\textcolor{gray}{\begin{tabular}{@{}l@{}}no host language\\needed\end{tabular}}}; |
|
628 } |
|
629 |
|
630 \end{tikzpicture} |
|
631 \end{center} |
|
632 |
|
633 \end{frame}} |
|
634 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
635 |
|
636 |
|
637 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
638 \mode<presentation>{ |
|
639 \begin{frame}<1-3> |
|
640 \frametitle{\LARGE\begin{tabular}{c}Hacking Compilers |
|
641 \end{tabular}} |
|
642 |
|
643 %Why is it so paramount to have a small trusted code base (TCB)? |
|
644 \bigskip\bigskip |
|
645 |
|
646 \begin{columns} |
|
647 \begin{column}{2.7cm} |
|
648 \begin{minipage}{2.5cm}% |
|
649 \begin{tabular}{c@ {}} |
|
650 \includegraphics[scale=0.2]{../pics/ken-thompson.jpg}\\[-1.8mm] |
|
651 \footnotesize Ken Thompson\\[-1.8mm] |
|
652 \footnotesize Turing Award, 1983\\ |
|
653 \end{tabular} |
|
654 \end{minipage} |
|
655 \end{column} |
|
656 \begin{column}{9cm} |
|
657 \begin{tabular}{l@ {\hspace{1mm}}p{8cm}} |
|
658 |
|
659 & Ken Thompson showed how to hide a Trojan Horse in a |
|
660 compiler \textcolor{red}{without} leaving any traces in the source code.\\[2mm] |
|
661 |
|
662 & No amount of source level verification will protect |
|
663 you from such Thompson-hacks.\\[2mm] |
|
664 |
|
665 & Therefore in safety-critical systems it is important to rely |
|
666 on only a very small TCB. |
|
667 \end{tabular} |
|
668 \end{column} |
|
669 \end{columns} |
|
670 |
|
671 \only<2>{ |
|
672 \begin{textblock}{6}(4,2) |
|
673 \begin{tikzpicture} |
|
674 \draw (0,0) node[inner sep=3mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] |
|
675 {\normalsize |
|
676 \begin{minipage}{8cm} |
|
677 \begin{quote} |
|
678 \includegraphics[scale=0.05]{../pics/evil.png} |
|
679 \begin{enumerate} |
|
680 \item[1)] Assume you ship the compiler as binary and also with sources. |
|
681 \item[2)] Make the compiler aware when it compiles itself. |
|
682 \item[3)] Add the Trojan horse. |
|
683 \item[4)] Compile. |
|
684 \item[5)] Delete Trojan horse from the sources of the compiler. |
|
685 \item[6)] Go on holiday for the rest of your life. ;o)\\[-7mm]\mbox{} |
|
686 \end{enumerate} |
|
687 \end{quote} |
|
688 \end{minipage}}; |
|
689 \end{tikzpicture} |
|
690 \end{textblock}} |
|
691 |
|
692 \end{frame}} |
|
693 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
694 |
|
695 |
|
696 |
764 |
697 \end{document} |
765 \end{document} |
698 |
766 |
699 %%% Local Variables: |
767 %%% Local Variables: |
700 %%% mode: latex |
768 %%% mode: latex |