diff -r d59bcff69998 -r b5b1bc0a603b slides/slides10.tex --- a/slides/slides10.tex Tue Dec 14 11:40:31 2021 +0000 +++ b/slides/slides10.tex Wed Dec 15 19:00:01 2021 +0000 @@ -73,7 +73,48 @@ \end{tikzpicture} \end{center} \end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\tikzstyle{sensor}=[draw, fill=blue!20, text width=3.8em, line width=1mm, + text centered, minimum height=2em,drop shadow] +\tikzstyle{ann} = [above, text width=4em, text centered] +\tikzstyle{sc} = [sensor, text width=7em, fill=red!20, + minimum height=6em, rounded corners, drop shadow,line width=1mm] + +\begin{frame}[fragile,c] +\frametitle{LLVM: Overview} + +\begin{tikzpicture} + % Validation Layer is the same except that there are a set of nodes and links which are added + + \path (0,0) node (IR) [sc] {\textbf{LLVM-IR}\\ Optimisations}; + \path (IR.west)+(-2.2,1.7) node (sou1) [sensor] {C++}; + \path (IR.west)+(-2.2,0.5) node (sou2)[sensor] {C}; + \path (IR.west)+(-2.2,-1.0) node (dots)[ann] {$\vdots$}; + \path (IR.west)+(-2.2,-1.8) node (sou3)[sensor] {Haskell}; + + \path [draw,->,line width=1mm] (sou1.east) -- node [above] {} (IR.160); + \path [draw,->,line width=1mm] (sou2.east) -- node [above] {} (IR.180); + \path [draw,->,line width=1mm] (sou3.east) -- node [above] {} (IR.200); + + \path (IR.east)+(2.2,2.0) node (tar1)[sensor] {x86}; + \path (IR.east)+(2.2,0.8) node (tar2)[sensor] {ARM}; + \path (IR.east)+(2.2,-0.4) node (tar3)[sensor] {MIPS}; + \path (IR.east)+(2.2,-1.6) node (tar4)[sensor] {RISC}; + \path (IR.east)+(2.2,-2.8) node (tar5)[sensor] {Power PC}; + \path (IR.east)+(2.2,-4.2) node (dots2)[ann] {$\vdots$}; + + \path [draw,<-,line width=1mm] (tar1.west) -- node [above] {} (IR.10); + \path [draw,<-,line width=1mm] (tar2.west) -- node [above] {} (IR.5); + \path [draw,<-,line width=1mm] (tar3.west) -- node [above] {} (IR.0); + \path [draw,<-,line width=1mm] (tar4.west) -- node [above] {} (IR.-5); + \path [draw,<-,line width=1mm] (tar5.west) -- node [above] {} (IR.-10); + +\end{tikzpicture} +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c,fragile] @@ -99,7 +140,7 @@ \mbox{}\bigskip\bigskip\bigskip -\begin{lstlisting}[language={},numbers=left] +\begin{lstlisting}[language=llvm,numbers=left] define i32 @fact (i32 %n) { %tmp_20 = icmp eq i32 %n, 0 br i1 %tmp_20, label %if_branch_24, label %else_branch_25 @@ -119,6 +160,31 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[fragile,c] +\frametitle{LLVM Types} + +\tt +\begin{center} +\begin{tabular}{ll} +boolean & i1 \\ +byte & i8 \\ +short & i16\\ +char & i16\\ +integer & i32\\ +long & i64\\ +float & float\\ +double & double\\ +*\_ & pointer to \\ +**\_ & pointer to a pointer to\\ +\mbox{}[\_] & arrays of\\ +\end{tabular} +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c,fragile] @@ -137,6 +203,134 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[fragile,c] +\frametitle{Abstract Syntax Trees} +\footnotesize + +\begin{lstlisting}[language=Scala,numbers=none,xleftmargin=-3mm] +// Fun language (expressions) +abstract class Exp +abstract class BExp + +case class Call(name: String, args: List[Exp]) extends Exp +case class If(a: BExp, e1: Exp, e2: Exp) extends Exp +case class Write(e: Exp) extends Exp +case class Var(s: String) extends Exp +case class Num(i: Int) extends Exp +case class Aop(o: String, a1: Exp, a2: Exp) extends Exp +case class Sequence(e1: Exp, e2: Exp) extends Exp +case class Bop(o: String, a1: Exp, a2: Exp) extends BExp +\end{lstlisting} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[fragile,c] +\frametitle{K-(Intermediate)Language} +\footnotesize + +\begin{lstlisting}[language=Scala,numbers=none,xleftmargin=-3mm] +abstract class KExp +abstract class KVal + +// K-Values +case class KVar(s: String) extends KVal +case class KNum(i: Int) extends KVal +case class Kop(o: String, v1: KVal, v2: KVal) extends KVal +case class KCall(o: String, vrs: List[KVal]) extends KVal +case class KWrite(v: KVal) extends KVal + +// K-Expressions +case class KIf(x1: String, e1: KExp, e2: KExp) extends KExp +case class KLet(x: String, v: KVal, e: KExp) extends KExp +case class KReturn(v: KVal) extends KExp +\end{lstlisting} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[fragile,c] +\frametitle{KLet} + +\begin{lstlisting}[language=LLVM] +tmp0 = add 1 a +tmp1 = mul b 5 +tmp2 = add 3 tmp1 +tmp3 = add tmp0 tmp2 +\end{lstlisting} + +\begin{lstlisting}[language=LLVMIR] + KLet tmp0 , add 1 a in + KLet tmp1 , mul b 5 in + KLet tmp2 , add 3 tmp1 in + KLet tmp3 , add tmp0 tmp2 in + ... +\end{lstlisting} + +\begin{lstlisting}[language=Scala,numbers=none] +case class KLet(x: String, e1: KVal, e2: KExp) +\end{lstlisting} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[fragile,c] +\frametitle{KLet} + +\begin{lstlisting}[language=LLVM] +tmp0 = add 1 a +tmp1 = mul b 5 +tmp2 = add 3 tmp1 +tmp3 = add tmp0 tmp2 +\end{lstlisting} + +\begin{lstlisting}[language=LLVMIR] + let tmp0 = add 1 a in + let tmp1 = mul b 5 in + let tmp2 = add 3 tmp1 in + let tmp3 = add tmp0 tmp2 in + ... +\end{lstlisting} + +\begin{lstlisting}[language=Scala,numbers=none] +case class KLet(x: String, e1: KVal, e2: KExp) +\end{lstlisting} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[fragile,c] +\frametitle{CPS-Translation} +\small + +\begin{lstlisting}[language=Scala,numbers=none] +def CPS(e: Exp)(k: KVal => KExp) : KExp = + e match { ... } +\end{lstlisting} +\bigskip\bigskip + +the continuation \texttt{k} can be thought of:\medskip + +\small +\begin{lstlisting}[language=LLVMIR,numbers=none,xleftmargin=30mm,escapeinside={(*@}{@*)}] +let tmp0 = add 1 a in +let tmp1 = mul (*@$\Box$@*) 5 in +let tmp2 = add 3 tmp1 in +let tmp3 = add tmp0 tmp2 in + KReturn tmp3 +\end{lstlisting} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c,fragile] @@ -710,7 +904,11 @@ \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - + +\begin{frame}<1-20>[c] +\end{frame} + + \end{document} %%% Local Variables: