diff -r 85b961f1eee9 -r f824e1331fc6 slides/slides09.tex --- a/slides/slides09.tex Tue Nov 26 22:45:06 2013 +0000 +++ b/slides/slides09.tex Wed Nov 27 08:49:51 2013 +0000 @@ -21,7 +21,7 @@ \usetikzlibrary{plotmarks} \usepackage{graphicx} \usepackage{pgfplots} - +\setmonofont{Consolas} \definecolor{javared}{rgb}{0.6,0,0} % for strings \definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments @@ -95,7 +95,7 @@ tabsize=2, showspaces=false, showstringspaces=false} - + % beamer stuff \renewcommand{\slidecaption}{AFL 09, King's College London, 27.~November 2013} @@ -200,11 +200,12 @@ \begin{frame}[c] {\large\bf -What is a perfect attack?} +What is a \alert{perfect} attack?}\bigskip \begin{enumerate} \item you can potentially completely take over a target system \item your attack is (nearly) undetectable +\item the victim has (almost) no chance to recover \end{enumerate} \end{frame}} @@ -220,24 +221,25 @@ \onslide<1->{ \node (A) at (0,0) [draw=black, rectangle, very thick, minimum height=18mm, minimum width=17mm] {}; - \node [below right] at (A.north west) {\footnotesize\begin{tabular}{@{}l@{}}clean\\compiler\end{tabular}};} + \node [below right] at (A.north west) {\footnotesize\begin{tabular}{@{}l@{}} + \only<1,2>{clean}\only<3->{\alert{hacked}}\\compiler\end{tabular}};} \onslide<2->{ - \node (B) at (0,3) [draw=black, rectangle, very thick, minimum height=8mm, minimum width=12mm] {}; - \node [below right] at (B.north west) {\footnotesize login}; - \node [above right] at (B.south west) {\footnotesize \alert{infected}}; - \node [right] at (B.east) {\ldots}; + \node (B) at (-2,2) [draw=black, rectangle, very thick, minimum height=10mm, minimum width=12mm] {}; + \node [below right] at (B.north west) {\footnotesize\begin{tabular}{@{}l@{}}login\\(src)\end{tabular}}; + + \node (C) at (2,2) [draw=black, rectangle, very thick, minimum height=10mm, minimum width=12mm] {}; + \node [below right] at (C.north west) {\footnotesize\begin{tabular}{@{}l@{}}login\\(bin)\end{tabular}}; + + \draw[->, line width=2mm] (B) -- (C); } - + + \onslide<3->{\node [above left=-1.5mm] at (C.south east) {\footnotesize \alert{$\blacksquare$}};} - - \end{tikzpicture} \end{center} - - \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -246,7 +248,6 @@ \mode{ \begin{frame}[c] - \begin{center} \begin{tikzpicture}[scale=1] @@ -281,13 +282,13 @@ \node (G) at (8.6,2) [draw=black, rectangle, very thick, minimum height=18mm, minimum width=14mm] {}; \node [below right] at (G.north west) {\small V1.02}; \node at (9.8,0) {\ldots}; - \node at (9.8,2) {\ldots};} + \node at (9.8,2) {\ldots}; + \node at (8,-2) {\textcolor{gray}{\begin{tabular}{@{}l@{}}no host language\\needed\end{tabular}}}; + } \end{tikzpicture} \end{center} - - \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -355,6 +356,70 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{ \begin{frame}[c] +\frametitle{Our Compiler} + + \begin{center} + \begin{tikzpicture}[scale=1] + + \node (0) at (-2.3,0) {}; + + \node (A) at (0,0) [draw=black, rectangle, very thick, minimum height=18mm, minimum width=20mm] {}; + \node [below right] at (A.north west) {lexer}; + + \node (B) at (3,0) [draw=black, rectangle, very thick, minimum height=18mm, minimum width=20mm] {}; + \node [below right=1mm] at (B.north west) {\mbox{}\hspace{-1mm}parser}; + + \node (C) at (6,0) [draw=black, rectangle, very thick, minimum height=18mm, minimum width=20mm] {}; + \node [below right] at (C.north west) {\mbox{}\hspace{-1mm}code gen}; + + \node (1) at (8.4,0) {}; + + \draw [->,line width=4mm] (0) -- (A); + \draw [->,line width=4mm] (A) -- (B); + \draw [->,line width=4mm] (B) -- (C); + \draw [->,line width=4mm] (C) -- (1); + \end{tikzpicture} + \end{center} + +lexer input: string\medskip\\ +lexer output: sequence of tokens\\ +\mbox{}\hfill(white space and comments filtered out)\medskip\\ +parser output: abstract syntax tree\medskip\\ +code gen output: assembler byte code / \\ +\mbox{}\hfill assembler machine code +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{\begin{tabular}{c}For-Loops\end{tabular}} + + +\begin{center}\Large +\texttt{for} \;\textit{Id} \texttt{:=} \textit{AExp}\; \texttt{upto} \;\textit{AExp}\; \texttt{do} \textit{Block} +\end{center}\bigskip + +\begin{center} +\begin{minipage}{8cm} +\begin{tabular}{l} +\texttt{for i := 2 upto 4 do \{}\\ +\hspace{5mm}\texttt{write i}\\ +\texttt{\}}\ +\end{tabular} +\end{minipage} +\end{center} +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] \frametitle{\begin{tabular}{c}While-Language\end{tabular}} @@ -364,7 +429,8 @@ & $|$ & $Id := AExp$\\ & $|$ & $\text{if}\; B\!Exp \;\text{then}\; Block \;\text{else}\; Block$\\ & $|$ & $\text{while}\; B\!Exp \;\text{do}\; Block$\\ - & $|$ & $\alert{\text{write}\; Id}$\medskip\\ + & $|$ & $\alert{\text{write}\; Id}$\\ + & $|$ & $\alert{\text{read}\; Id}$\medskip\\ $Stmts$ & $\rightarrow$ & $Stmt \;\text{;}\; Stmts$\\ & $|$ & $Stmt$\medskip\\ $Block$ & $\rightarrow$ & $\{ Stmts \}$\\ @@ -378,18 +444,7 @@ \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Fibonacci Numbers\end{tabular}} -\mbox{}\\[-18mm]\mbox{} - -{\lstset{language=While}\fontsize{10}{12}\selectfont -\texttt{\lstinputlisting{../progs/fib.while}}} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{ @@ -437,421 +492,7 @@ \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Test Program\end{tabular}} - -\mbox{}\\[-18mm]\mbox{} - -{\lstset{language=While}\fontsize{10}{12}\selectfont -\texttt{\lstinputlisting{../progs/loops.while}}} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] -\frametitle{\begin{tabular}{c}Interpreted Code\end{tabular}} - -\begin{center} -\begin{tikzpicture} -\begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=secs, legend style=small] -\addplot+[smooth] file {interpreted.data}; -\end{axis} -\end{tikzpicture} -\end{center} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Java Virtual Machine\end{tabular}} - -\begin{itemize} -\item introduced in 1995 -\item is a stack-based VM (like Postscript, CLR of .Net) -\item contains a JIT compiler -\item many languages take advantage of JVM's infrastructure (JRE) -\item is garbage collected $\Rightarrow$ no buffer overflows -\item some languages compiled to the JVM: Scala, Clojure\ldots -\end{itemize} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] -\frametitle{\begin{tabular}{c}Compiling AExps\end{tabular}} - -{\Large\bl{1 + 2}} - -\begin{center} -\bl{\begin{tabular}{l} -ldc 1\\ -ldc 2\\ -iadd\\ -\end{tabular}} -\end{center}\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] -\frametitle{\begin{tabular}{c}Compiling AExps\end{tabular}} - -{\Large\bl{1 + 2 + 3}} - -\begin{center} -\bl{\begin{tabular}{l} -ldc 1\\ -ldc 2\\ -iadd\\ -ldc 3\\ -iadd\\ -\end{tabular}} -\end{center} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] -\frametitle{\begin{tabular}{c}Compiling AExps\end{tabular}} - -{\Large\bl{1 + (2 + 3)}} - -\begin{center} -\bl{\begin{tabular}{l} -ldc 1\\ -ldc 2\\ -ldc 3\\ -iadd\\ -iadd\\ -\end{tabular}} -\end{center}\bigskip\pause -\vfill - -\bl{dadd, fadd, ladd, \ldots} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] -\frametitle{\begin{tabular}{c}Compiling AExps\end{tabular}} - -\begin{center} -\bl{\begin{tabular}{@{}lcl@{}} -$\text{compile}(n)$ & $\dn$ & $\text{ldc}\;n$\\ -$\text{compile}(a_1 + a_2)$ & $\dn$\\ -\multicolumn{3}{l}{$\qquad\text{compile}(a_1) \;@\;\text{compile}(a_2)\;@\; \text{iadd}$}\smallskip\\ -$\text{compile}(a_1 - a_2)$ & $\dn$\\ -\multicolumn{3}{l}{$\qquad\text{compile}(a_1) \;@\; \text{compile}(a_2)\;@\; \text{isub}$}\smallskip\\ -$\text{compile}(a_1 * a_2)$ & $\dn$\\ -\multicolumn{3}{l}{$\qquad\text{compile}(a_1) \;@\; \text{compile}(a_2)\;@\; \text{imul}$}\smallskip\\ -\end{tabular}} -\end{center}\pause - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] -\frametitle{\begin{tabular}{c}Compiling AExps\end{tabular}} - -{\Large\bl{1 + 2 * 3 + (4 - 3)}} - -\begin{center} -\bl{\begin{tabular}{l} -ldc 1\\ -ldc 2\\ -ldc 3\\ -imul\\ -ldc 4\\ -ldc 3\\ -isub\\ -iadd\\ -iadd\\ -\end{tabular}} -\end{center} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] -\frametitle{\begin{tabular}{c}Variables\end{tabular}} - -{\Large\bl{$x := 5 + y * 2$}}\bigskip\pause - -\begin{itemize} -\item lookup: \bl{$\text{iload}\; index$} -\item store: \bl{$\text{istore}\; index$} -\end{itemize}\bigskip\pause - -while compilating we have to maintain a map between our identifiers and the -Java bytecode indices - -\begin{center} -\bl{$\text{compile}(a, E)$} -\end{center} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] -\frametitle{\begin{tabular}{c}Compiling AExps\end{tabular}} - -\begin{center} -\bl{\begin{tabular}{@{}lcl@{}} -$\text{compile}(n, E)$ & $\dn$ & $\text{ldc}\;n$\\ -$\text{compile}(a_1 + a_2, E)$ & $\dn$\\ -\multicolumn{3}{l}{$\qquad\text{compile}(a_1, E) \;@\;\text{compile}(a_2. E)\;@\; \text{iadd}$}\smallskip\\ -$\text{compile}(a_1 - a_2, E)$ & $\dn$\\ -\multicolumn{3}{l}{$\qquad\text{compile}(a_1, E) \;@\; \text{compile}(a_2, E)\;@\; \text{isub}$}\smallskip\\ -$\text{compile}(a_1 * a_2, E)$ & $\dn$\\ -\multicolumn{3}{l}{$\qquad\text{compile}(a_1, E) \;@\; \text{compile}(a_2, E)\;@\; \text{imul}$}\bigskip\\ -$\text{compile}(x, E)$ & $\dn$ & $\text{iload}\;E(x)$\\ -\end{tabular}} -\end{center}\pause - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] -\frametitle{\begin{tabular}{c}Compiling Statements\end{tabular}} - -We return a list of instructions and an environment for the variables - -\begin{center} -\bl{\begin{tabular}{@{}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}} -$\text{compile}(\text{skip}, E)$ & $\dn$ & $(N\!il, E)$\bigskip\\ -$\text{compile}(x := a, E)$ & $\dn$\\ -\multicolumn{3}{l}{$(\text{compile}(a, E) \;@\;\text{istore}\;index, E(x\mapsto index))$}\\ -\end{tabular}} -\end{center}\medskip - -where \bl{$index$} is \bl{$E(x)$} if it is already defined, or if it is not then the largest index not yet seen - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] -\frametitle{\begin{tabular}{c}Compiling AExps\end{tabular}} - -{\Large\bl{$x := x + 1$}} - -\begin{center} -\bl{\begin{tabular}{l} -iload $n_x$\\ -ldc 1\\ -iadd\\ -istore $n_x$\\ -\end{tabular}} -\end{center} - -where \bl{$n_x$} is the index corresponding to the variable \bl{$x$} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] -\frametitle{\begin{tabular}{c}Compiling Ifs\end{tabular}} - -{\Large\bl{$\text{if}\;b\;\text{then}\;cs_1\;\text{else}\;cs_2$}}\bigskip\bigskip - -\onslide<2->{Case }\only<2>{{\bf True}:}\only<3>{{\bf False}:} - -\begin{center} -\begin{tikzpicture}[node distance=2mm and 4mm, - block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm}, - point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red}, - skip loop/.style={red, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}] -\node (A1) [point] {}; -\node (b) [block, right=of A1] {code of \bl{$b$}}; -\node (A2) [point, right=of b] {}; -\node (cs1) [block, right=of A2] {code of \bl{$cs_1$}}; -\node (A3) [point, right=of cs1] {}; -\node (cs2) [block, right=of A3] {code of \bl{$cs_2$}}; -\node (A4) [point, right=of cs2] {}; - -\only<2>{ -\draw (A1) edge [->, red, line width=1mm] (b); -\draw (b) edge [->, red, line width=1mm] (cs1); -\draw (cs1) edge [->, red, line width=1mm] (A3); -\draw (A3) edge [->,skip loop] (A4); -\node [below=of cs2] {\raisebox{-5mm}{\small{}jump}};} -\only<3>{ -\draw (A1) edge [->, red, line width=1mm] (b); -\draw (b) edge [->, red, line width=1mm] (A2); -\draw (A2) edge [skip loop] (A3); -\draw (A3) edge [->, red, line width=1mm] (cs2); -\draw (cs2) edge [->,red, line width=1mm] (A4); -\node [below=of cs1] {\raisebox{-5mm}{\small{}conditional jump}};} -\end{tikzpicture} -\end{center} - - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Conditional Jumps\end{tabular}} - -\begin{minipage}{1.1\textwidth} -\begin{itemize} -\item \bl{if\_icmpeq $label$} if two ints are equal, then jump\medskip -\item \bl{if\_icmpne $label$} if two ints aren't equal, then jump\medskip -\item \bl{if\_icmpge $label$} if one int is greater or equal then another, then jump -\item[]\ldots -\end{itemize} -\end{minipage}\pause - - -\begin{center} -\bl{\begin{tabular}{l} -$L_1$:\\ -\hspace{5mm}if\_icmpeq\;$L_2$\\ -\hspace{5mm}iload 1\\ -\hspace{5mm}ldc 1\\ -\hspace{5mm}iadd\\ -\hspace{5mm}if\_icmpeq\;$L_1$\\ -$L_2$: -\end{tabular}} -\end{center} - -\begin{textblock}{3.5}(11,12) -\only<3>{labels must be unique} -\end{textblock} -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] -\frametitle{\begin{tabular}{c}Compiling BExps\end{tabular}} - -{\Large\bl{$a_1 = a_2$}} - -\begin{center} -\bl{\begin{tabular}{lcl} -$\text{compile}(a_1 = a_2, E, lab)$ & $\dn$\\ -\multicolumn{3}{l}{$\quad\text{compile}(a_1, E) \;@\;\text{compile}(a_2, E)\;@\; \text{if\_icmpne}\;lab$} -\end{tabular}} -\end{center} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] -\frametitle{\begin{tabular}{c}Compiling Ifs\end{tabular}} - -{\Large\bl{if $b$ then $cs_1$ else $cs_2$}} - -\begin{center} -\bl{\begin{tabular}{lcl} -$\text{compile}(\text{if}\;b\;\text{then}\; cs_1\;\text{else}\; cs_2, E)$ & $\dn$\\ -\multicolumn{3}{l}{$\quad l_{ifelse}\;$ \textcolor{black}{(fresh label)}}\\ -\multicolumn{3}{l}{$\quad l_{ifend}\;$ \textcolor{black}{(fresh label)}}\\ -\multicolumn{3}{l}{$\quad (is_1, E') = \text{compile}(cs_1, E)$}\\ -\multicolumn{3}{l}{$\quad (is_2, E'') = \text{compile}(cs_2, E')$}\\ -\multicolumn{3}{l}{$\quad(\text{compile}(b, E, l_{ifelse})$}\\ -\multicolumn{3}{l}{$\quad\phantom{(}@\;is_1$}\\ -\multicolumn{3}{l}{$\quad\phantom{(}@\; \text{goto}\;l_{ifend}$}\\ -\multicolumn{3}{l}{$\quad\phantom{(}@\;l_{ifelse}:$}\\ -\multicolumn{3}{l}{$\quad\phantom{(}@\;is_2$}\\ -\multicolumn{3}{l}{$\quad\phantom{(}@\;l_{ifend}:, E'')$}\\ -\end{tabular}} -\end{center} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] -\frametitle{\begin{tabular}{c}Compiling Whiles\end{tabular}} - -{\Large\bl{$\text{while}\;b\;\text{do}\;cs$}}\bigskip\bigskip - -\onslide<2->{Case }\only<2>{{\bf True}:}\only<3>{{\bf False}:} - -\begin{center} -\begin{tikzpicture}[node distance=2mm and 4mm, - block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm}, - point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red}, - skip loop/.style={red, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}] -\node (A0) [point, left=of A1] {}; -\node (A1) [point] {}; -\node (b) [block, right=of A1] {code of \bl{$b$}}; -\node (A2) [point, right=of b] {}; -\node (cs1) [block, right=of A2] {code of \bl{$cs$}}; -\node (A3) [point, right=of cs1] {}; -\node (A4) [point, right=of A3] {}; - -\only<2>{ -\draw (A0) edge [->, red, line width=1mm] (b); -\draw (b) edge [->, red, line width=1mm] (cs1); -\draw (cs1) edge [->, red, line width=1mm] (A3); -\draw (A3) edge [->,skip loop] (A1);} -\only<3>{ -\draw (A0) edge [->, red, line width=1mm] (b); -\draw (b) edge [->, red, line width=1mm] (A2); -\draw (A2) edge [skip loop] (A3); -\draw (A3) edge [->, red, line width=1mm] (A4);} -\end{tikzpicture} -\end{center} - - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] -\frametitle{\begin{tabular}{c}Compiling Whiles\end{tabular}} - -{\Large\bl{while $b$ do $cs$}} - -\begin{center} -\bl{\begin{tabular}{lcl} -$\text{compile}(\text{while}\; b\; \text{do} \;cs, E)$ & $\dn$\\ -\multicolumn{3}{l}{$\quad l_{wbegin}\;$ \textcolor{black}{(fresh label)}}\\ -\multicolumn{3}{l}{$\quad l_{wend}\;$ \textcolor{black}{(fresh label)}}\\ -\multicolumn{3}{l}{$\quad (is, E') = \text{compile}(cs_1, E)$}\\ -\multicolumn{3}{l}{$\quad(l_{wbegin}:$}\\ -\multicolumn{3}{l}{$\quad\phantom{(}@\;\text{compile}(b, E, l_{wend})$}\\ -\multicolumn{3}{l}{$\quad\phantom{(}@\;is$}\\ -\multicolumn{3}{l}{$\quad\phantom{(}@\; \text{goto}\;l_{wbegin}$}\\ -\multicolumn{3}{l}{$\quad\phantom{(}@\;l_{wend}:, E')$}\\ -\end{tabular}} -\end{center} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{ \begin{frame}[t] @@ -909,100 +550,6 @@ \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Next Compiler Phases\end{tabular}} - -\begin{itemize} -\item assembly $\Rightarrow$ byte code (class file) -\item labels $\Rightarrow$ absolute or relative jumps\bigskip\bigskip -\item \texttt{javap} is a disassembler for class files -\end{itemize} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] -\frametitle{\begin{tabular}{c}Compiled Code\end{tabular}} - -\begin{center} -\begin{tikzpicture} -\begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=secs, legend style=small] -\addplot+[smooth] file {compiled.data}; -\end{axis} -\end{tikzpicture} -\end{center} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] -\frametitle{\begin{tabular}{c}Compiled vs.~Interpreted Code\end{tabular}} - -\begin{center} -\begin{tikzpicture} -\begin{loglogaxis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=secs, legend style=small] -\addplot+[smooth] file {interpreted.data}; -\addplot+[smooth] file {compiled.data}; -\end{loglogaxis} -\end{tikzpicture} -\end{center} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] -\frametitle{\begin{tabular}{c}Compiled vs.~Interpreted Code\end{tabular}} - -\begin{center} -\begin{tikzpicture} -\begin{axis}[axis x line=bottom, axis y line=left, ylabel=secs, - xlabel=n, - enlargelimits=0.05, - ybar interval=0.7, legend style=small] -\addplot file {interpreted2.data}; -\addplot file {compiled2.data}; -%\legend{interpreted, compiled} -\end{axis} -\end{tikzpicture} -\end{center} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] -\frametitle{\begin{tabular}{c}What Next\end{tabular}} - -\begin{itemize} -\item register spilling -\item dead code removal -\item loop optimisations -\item instruction selection -\item type checking -\item concurrency -\item fuzzy testing -\item verification\bigskip\\ - -\item GCC, LLVM, tracing JITs -\end{itemize} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - \end{document} %%% Local Variables: