12 \fnote{\copyright{} Christian Urban, King's College London, 2019} |
12 \fnote{\copyright{} Christian Urban, King's College London, 2019} |
13 |
13 |
14 |
14 |
15 \section*{Handout 9 (LLVM, SSA and CPS)} |
15 \section*{Handout 9 (LLVM, SSA and CPS)} |
16 |
16 |
17 Reflecting on our tiny compiler targetting the JVM, code generation was |
17 Reflecting on our tiny compiler targetting the JVM, the code generation |
18 actually not so hard, no? One of the main reason for this ease is that |
18 part was actually not so hard, no? Pretty much just some post-traversal |
19 the JVM is a stack-based virtual machine and it is, for example, not |
19 of the abstract syntax tree, yes? One of the main reason for this ease is |
20 hard to translate arithmetic expressions into instructions manipulating |
20 that the JVM is a stack-based virtual machine and it is therefore not |
21 the stack. The problem is that ``real'' CPUs, although supporting stack |
21 hard to translate arithmetic expressions into a sequence of instructions |
22 operations, are not really \emph{stack machines}. They are just not |
22 manipulating the stack. The problem is that ``real'' CPUs, although |
23 optimised for this way of calculating things. The design of CPUs is more |
23 supporting stack operations, are not really designed to be \emph{stack |
24 like, here is a piece of memory---compiler, or compiler writer, do |
24 machines}. The design of CPUs is more like, here is a chunk of |
25 something with it. Otherwise get lost. So in the name of raw speed, |
25 memory---compiler, or better compiler writers, do something with it. |
26 modern compilers go the extra mile and generate code that is much easier |
26 Consequently, modern compilers need to go the extra mile in order to generate |
27 and faster to process by CPUs. |
27 code that is much easier and faster to process by CPUs. |
|
28 |
28 |
29 |
29 Another reason why it makes sense to go the extra mile is that stack |
30 Another reason why it makes sense to go the extra mile is that stack |
30 instructions are very difficult to optimise---you cannot just re-arrange |
31 instructions are very difficult to optimise---you cannot just re-arrange |
31 instructions without messing about with what is calculated on the stack. |
32 instructions without messing about with what is calculated on the stack. |
32 Also it is hard to find out if all the calculations on the stack are |
33 Also it is hard to find out if all the calculations on the stack are |
33 actually necessary and not by chance dead code. The JVM has for all this |
34 actually necessary and not by chance dead code. The JVM has for all this |
34 sophisticated machinery to make such ``high-level'' code still run fast, |
35 sophisticated machinery to make such ``high-level'' code still run fast, |
35 but let's say that for the sake of argument we want to not rely on it. |
36 but let's say that for the sake of argument we do not want to rely on |
36 We want to generate fast code ourselves. This means we have to work around |
37 it. We want to generate fast code ourselves. This means we have to work |
37 the intricacies of what instructions CPUs can actually process. To make |
38 around the intricacies of what instructions CPUs can actually process. |
38 this all tractable, we target the LLVM Intermediate Language. In this way |
39 To make this all tractable for this module, we target the LLVM |
39 we can take advantage of the tools coming with LLVM and for example do not |
40 Intermediate Language. In this way we can take advantage of the tools |
40 have to worry about things like that CPUs have only a limited amount of |
41 coming with LLVM. For example we do not have to worry about things like |
41 registers. |
42 register allocations.\bigskip |
42 |
43 |
43 LLVM\footnote{\url{http://llvm.org}} is a beautiful example that |
44 \noindent LLVM\footnote{\url{http://llvm.org}} is a beautiful example |
44 projects from Academia can make a difference in the world. LLVM was |
45 that projects from Academia can make a difference in the world. LLVM |
45 started in 2000 by two researchers at the University of Illinois at |
46 started in 2000 as a project by two researchers at the University of |
46 Urbana–Champaign. At the time the behemoth of compilers was gcc with its |
47 Illinois at Urbana-Champaign. At the time the behemoth of compilers was |
47 myriad of front-ends for other languages (e.g.~gfortran, Ada, Go, |
48 gcc with its myriad of front-ends for other languages (e.g.~Fortran, |
48 Objective-C, Pascal etc). The problem was that gcc morphed over time |
49 Ada, Go, Objective-C, Pascal etc). The problem was that gcc morphed over |
49 into a monolithic gigantic piece of m\ldots ehm software, which you could |
50 time into a monolithic gigantic piece of m\ldots ehm software, which you |
50 not mess about in an afternoon. In contrast LLVM was a modular suite of |
51 could not mess about in an afternoon. In contrast, LLVM is designed to |
51 tools with which you could play around easily and try out something new. |
52 be a modular suite of tools with which you could play around easily and |
52 LLVM became a big player once Apple hired one of the original developers |
53 try out something new. LLVM became a big player once Apple hired one of |
53 (I cannot remember the reason why Apple did not want to use gcc, but |
54 the original developers (I cannot remember the reason why Apple did not |
54 maybe they were also just disgusted by big monolithic codebase). Anyway, |
55 want to use gcc, but maybe they were also just disgusted by its big |
55 LLVM is now the big player and gcc is more or less legacy. This does not |
56 monolithic codebase). Anyway, LLVM is now the big player and gcc is more |
56 mean that programming languages like C and C++ are dying out any time |
57 or less legacy. This does not mean that programming languages like C and |
57 soon---they are nicely supported by LLVM. |
58 C++ are dying out any time soon---they are nicely supported by LLVM. |
58 |
59 |
59 Targetting the LLVM-IR also means we can profit from the very modular |
60 Targetting the LLVM Intermediate Language, or Intermediate |
60 structure of the LLVM compiler and let for example the compiler generate |
61 Representation (short LLVM-IR), also means we can profit from the very |
61 code for X86, or ARM etc. We can be agnostic about where our code |
62 modular structure of the LLVM compiler and let for example the compiler |
62 actually runs. However, what we have to do is to generate code in |
63 generate code for X86, or ARM etc. That means we can be agnostic about |
63 \emph{Static Single-Assignment} format (short SSA), because that is what |
64 where our code actually runs. However, what we have to do is to generate |
64 the LLVM-IR expects from us and which is the intermediate format that |
65 code in \emph{Static Single-Assignment} format (short SSA), because that |
65 LLVM can use to do cool things (like targetting strange architectures) |
66 is what the LLVM-IR expects from us. LLVM-IR is the intermediate format |
66 and allocating memory efficiently. |
67 that LLVM uses for doing cool things, like targetting strange |
|
68 architectures, optimising code and allocating memory efficiently. |
67 |
69 |
68 The idea behind SSA is to use very simple variable assignments where |
70 The idea behind the SSA format is to use very simple variable |
69 every variable is assigned only once. The assignments also need to be |
71 assignments where every variable is assigned only once. The assignments |
70 extremely primitive in the sense that they can be just simple operations |
72 also need to be primitive in the sense that they can be just simple |
71 like addition, multiplication, jumps and so on. A typical program in SSA |
73 operations like addition, multiplication, jumps, comparisons and so on. |
72 is |
74 An idealised snippet of a program in SSA is |
73 |
75 |
74 \begin{lstlisting}[language=LLVM,numbers=none] |
76 \begin{lstlisting}[language=LLVM,numbers=none] |
75 x := 1 |
77 x := 1 |
76 y := 2 |
78 y := 2 |
77 z := x + y |
79 z := x + y |
78 \end{lstlisting} |
80 \end{lstlisting} |
79 |
81 |
80 \noindent where every variable is used only once. You cannot for example have |
82 \noindent where every variable is used only once (we could not write |
|
83 \texttt{x := x + y} in the last line for example). There are |
|
84 sophisticated algorithms for imperative languages, like C, that |
|
85 efficiently transform a high-level program into SSA format. But we can |
|
86 ignore them here. We want to compile a functional language and there |
|
87 things get much more interesting than just sophisticated. We will need |
|
88 to have a look at CPS translations, where the CPS stands for |
|
89 Continuation-Passing-Style---basically black programming art or |
|
90 abracadabra programming. So sit tight. |
81 |
91 |
82 \begin{lstlisting}[language=LLVM,numbers=none] |
92 \subsection*{LLVM-IR} |
83 x := 1 |
|
84 y := 2 |
|
85 x := x + y |
|
86 \end{lstlisting} |
|
87 |
93 |
88 \noindent because in this snippet \texttt{x} is assigned twice. There |
94 Before we start, lets first have a look at the \emph{LLVM Intermediate |
89 are sophisticated algorithm for imperative languages, like C, for |
95 Representation}. What is good about our simple Fun language is that it |
90 efficiently transforming a program into SSA format, but we do not have |
96 basically only contains expressions (be they arithmetic expressions or |
91 to be concerned about those. We want to compile a functional language |
97 boolean expressions). The exception is function definitions. Luckily, |
92 and there things get much more interesting than just sophisticated. We |
98 for them we can use the mechanism of defining functions in LLVM-IR. For |
93 will need to have a look at CPS translations, which stands for |
99 example the simple Fun program |
94 Continuation-Passing-Style---basically black art. So sit tight. |
|
95 |
100 |
96 \subsection*{CPS-Translations} |
|
97 |
|
98 What is good about our simple fun language is that it basically only |
|
99 contains expressions (be they arithmetic expressions or boolean expressions). |
|
100 The only exceptions are function definitions, for which we can easily |
|
101 use the mechanism of defining functions in LLVM-IR. For example the simple |
|
102 fun program |
|
103 |
101 |
104 \begin{lstlisting}[language=Scala,numbers=none] |
102 \begin{lstlisting}[language=Scala,numbers=none] |
105 def dble(x) = x * x |
103 def sqr(x) = x * x |
106 \end{lstlisting} |
104 \end{lstlisting} |
107 |
105 |
108 \noindent |
106 \noindent |
109 can be compiled into the following LLVM-IR function: |
107 can be compiled into the following LLVM-IR function: |
110 |
108 |
111 \begin{lstlisting}[language=LLVM] |
109 \begin{lstlisting}[language=LLVM] |
112 define i32 dble(i32 %x) { |
110 define i32 @sqr(i32 %x) { |
113 %tmp = mul i32 %x, % x |
111 %tmp = mul i32 %x, %x |
114 ret i32 %tmp |
112 ret i32 %tmp |
115 } |
113 } |
116 \end{lstlisting} |
114 \end{lstlisting} |
117 |
115 |
|
116 \noindent First to notice is that all variable names in the LLVM-IR are |
|
117 prefixed by \texttt{\%}; function names need to be prefixed with @. |
|
118 Also, the LLVM-IR is a fully typed language. The \texttt{i32} type stands |
|
119 for a 32-bit integer. There are also types for 64-bit integers, chars |
|
120 (\texttt{i8}), floats, arrays and even pointer types. In teh code above, |
|
121 \texttt{sqr} takes an argument of type \texttt{i32} and produces a |
|
122 result of type \texttt{i32}. Each arithmetic operation, like addition or |
|
123 multiplication, are also prefixed with the type they operate on. |
|
124 Obviously these types need to match up\ldots{} but since we have in our |
|
125 programs only integers, \texttt{i32} everywhere will do. |
118 |
126 |
|
127 Conveniently, you can use the program \texttt{lli}, which comes with LLVM, to interprete |
|
128 programs written in the LLVM-IR. So you can easily check whether the |
|
129 code you produced actually works. To get a running program that does |
|
130 something interesting you need to add some boilerplate about printing out |
|
131 numbers and a main-function that is the entrypoint for the program (see Figure~\ref{lli}). |
|
132 |
|
133 \begin{figure}[t] |
|
134 \lstinputlisting[language=LLVM]{../progs/sqr.ll} |
|
135 \caption{\label{lli}} |
|
136 \end{figure} |
|
137 |
|
138 \begin{figure}[t] |
|
139 \begin{lstlisting}[language=Scala,numbers=none] |
|
140 abstract class Exp extends Serializable |
|
141 abstract class BExp extends Serializable |
|
142 abstract class Decl extends Serializable |
|
143 |
|
144 case class Main(e: Exp) extends Decl |
|
145 case class Def(name: String, args: List[String], body: Exp) |
|
146 extends Decl |
|
147 |
|
148 case class Call(name: String, args: List[Exp]) extends Exp |
|
149 case class If(a: BExp, e1: Exp, e2: Exp) extends Exp |
|
150 case class Write(e: Exp) extends Exp |
|
151 case class Var(s: String) extends Exp |
|
152 case class Num(i: Int) extends Exp |
|
153 case class Aop(o: String, a1: Exp, a2: Exp) extends Exp |
|
154 case class Sequence(e1: Exp, e2: Exp) extends Exp |
|
155 case class Bop(o: String, a1: Exp, a2: Exp) extends BExp |
|
156 \end{lstlisting} |
|
157 \caption{Abstract syntax trees for the Fun language.\label{absfun}} |
|
158 \end{figure} |
|
159 |
|
160 |
|
161 |
|
162 \subsection*{CPS-Translations} |
|
163 |
|
164 |
119 \end{document} |
165 \end{document} |
120 |
166 |
121 |
167 |
122 %%% Local Variables: |
168 %%% Local Variables: |
123 %%% mode: latex |
169 %%% mode: latex |