|
150
|
1 ======================================================
|
|
|
2 Kaleidoscope: Conclusion and other useful LLVM tidbits
|
|
|
3 ======================================================
|
|
|
4
|
|
|
5 .. contents::
|
|
|
6 :local:
|
|
|
7
|
|
|
8 Tutorial Conclusion
|
|
|
9 ===================
|
|
|
10
|
|
|
11 Welcome to the final chapter of the "`Implementing a language with
|
|
|
12 LLVM <index.html>`_" tutorial. In the course of this tutorial, we have
|
|
|
13 grown our little Kaleidoscope language from being a useless toy, to
|
|
|
14 being a semi-interesting (but probably still useless) toy. :)
|
|
|
15
|
|
|
16 It is interesting to see how far we've come, and how little code it has
|
|
|
17 taken. We built the entire lexer, parser, AST, code generator, an
|
|
|
18 interactive run-loop (with a JIT!), and emitted debug information in
|
|
|
19 standalone executables - all in under 1000 lines of (non-comment/non-blank)
|
|
|
20 code.
|
|
|
21
|
|
|
22 Our little language supports a couple of interesting features: it
|
|
|
23 supports user defined binary and unary operators, it uses JIT
|
|
|
24 compilation for immediate evaluation, and it supports a few control flow
|
|
|
25 constructs with SSA construction.
|
|
|
26
|
|
|
27 Part of the idea of this tutorial was to show you how easy and fun it
|
|
|
28 can be to define, build, and play with languages. Building a compiler
|
|
|
29 need not be a scary or mystical process! Now that you've seen some of
|
|
|
30 the basics, I strongly encourage you to take the code and hack on it.
|
|
|
31 For example, try adding:
|
|
|
32
|
|
221
|
33 - **global variables** - While global variables have questionable value
|
|
150
|
34 in modern software engineering, they are often useful when putting
|
|
|
35 together quick little hacks like the Kaleidoscope compiler itself.
|
|
|
36 Fortunately, our current setup makes it very easy to add global
|
|
|
37 variables: just have value lookup check to see if an unresolved
|
|
|
38 variable is in the global variable symbol table before rejecting it.
|
|
|
39 To create a new global variable, make an instance of the LLVM
|
|
|
40 ``GlobalVariable`` class.
|
|
|
41 - **typed variables** - Kaleidoscope currently only supports variables
|
|
|
42 of type double. This gives the language a very nice elegance, because
|
|
|
43 only supporting one type means that you never have to specify types.
|
|
|
44 Different languages have different ways of handling this. The easiest
|
|
|
45 way is to require the user to specify types for every variable
|
|
|
46 definition, and record the type of the variable in the symbol table
|
|
|
47 along with its Value\*.
|
|
|
48 - **arrays, structs, vectors, etc** - Once you add types, you can start
|
|
|
49 extending the type system in all sorts of interesting ways. Simple
|
|
|
50 arrays are very easy and are quite useful for many different
|
|
|
51 applications. Adding them is mostly an exercise in learning how the
|
|
|
52 LLVM `getelementptr <../../LangRef.html#getelementptr-instruction>`_ instruction
|
|
|
53 works: it is so nifty/unconventional, it `has its own
|
|
|
54 FAQ <../../GetElementPtr.html>`_!
|
|
|
55 - **standard runtime** - Our current language allows the user to access
|
|
|
56 arbitrary external functions, and we use it for things like "printd"
|
|
|
57 and "putchard". As you extend the language to add higher-level
|
|
|
58 constructs, often these constructs make the most sense if they are
|
|
|
59 lowered to calls into a language-supplied runtime. For example, if
|
|
|
60 you add hash tables to the language, it would probably make sense to
|
|
|
61 add the routines to a runtime, instead of inlining them all the way.
|
|
|
62 - **memory management** - Currently we can only access the stack in
|
|
|
63 Kaleidoscope. It would also be useful to be able to allocate heap
|
|
|
64 memory, either with calls to the standard libc malloc/free interface
|
|
|
65 or with a garbage collector. If you would like to use garbage
|
|
|
66 collection, note that LLVM fully supports `Accurate Garbage
|
|
|
67 Collection <../../GarbageCollection.html>`_ including algorithms that
|
|
|
68 move objects and need to scan/update the stack.
|
|
|
69 - **exception handling support** - LLVM supports generation of `zero
|
|
|
70 cost exceptions <../../ExceptionHandling.html>`_ which interoperate with
|
|
|
71 code compiled in other languages. You could also generate code by
|
|
|
72 implicitly making every function return an error value and checking
|
|
|
73 it. You could also make explicit use of setjmp/longjmp. There are
|
|
|
74 many different ways to go here.
|
|
|
75 - **object orientation, generics, database access, complex numbers,
|
|
|
76 geometric programming, ...** - Really, there is no end of crazy
|
|
|
77 features that you can add to the language.
|
|
|
78 - **unusual domains** - We've been talking about applying LLVM to a
|
|
|
79 domain that many people are interested in: building a compiler for a
|
|
|
80 specific language. However, there are many other domains that can use
|
|
|
81 compiler technology that are not typically considered. For example,
|
|
|
82 LLVM has been used to implement OpenGL graphics acceleration,
|
|
|
83 translate C++ code to ActionScript, and many other cute and clever
|
|
|
84 things. Maybe you will be the first to JIT compile a regular
|
|
|
85 expression interpreter into native code with LLVM?
|
|
|
86
|
|
|
87 Have fun - try doing something crazy and unusual. Building a language
|
|
|
88 like everyone else always has, is much less fun than trying something a
|
|
|
89 little crazy or off the wall and seeing how it turns out. If you get
|
|
236
|
90 stuck or want to talk about it, please post on the `LLVM forums
|
|
|
91 <https://discourse.llvm.org>`_: it has lots of people who are interested
|
|
|
92 in languages and are often willing to help out.
|
|
150
|
93
|
|
|
94 Before we end this tutorial, I want to talk about some "tips and tricks"
|
|
|
95 for generating LLVM IR. These are some of the more subtle things that
|
|
|
96 may not be obvious, but are very useful if you want to take advantage of
|
|
|
97 LLVM's capabilities.
|
|
|
98
|
|
|
99 Properties of the LLVM IR
|
|
|
100 =========================
|
|
|
101
|
|
|
102 We have a couple of common questions about code in the LLVM IR form -
|
|
|
103 let's just get these out of the way right now, shall we?
|
|
|
104
|
|
|
105 Target Independence
|
|
|
106 -------------------
|
|
|
107
|
|
|
108 Kaleidoscope is an example of a "portable language": any program written
|
|
|
109 in Kaleidoscope will work the same way on any target that it runs on.
|
|
|
110 Many other languages have this property, e.g. lisp, java, haskell,
|
|
|
111 javascript, python, etc (note that while these languages are portable,
|
|
|
112 not all their libraries are).
|
|
|
113
|
|
|
114 One nice aspect of LLVM is that it is often capable of preserving target
|
|
|
115 independence in the IR: you can take the LLVM IR for a
|
|
|
116 Kaleidoscope-compiled program and run it on any target that LLVM
|
|
|
117 supports, even emitting C code and compiling that on targets that LLVM
|
|
|
118 doesn't support natively. You can trivially tell that the Kaleidoscope
|
|
|
119 compiler generates target-independent code because it never queries for
|
|
|
120 any target-specific information when generating code.
|
|
|
121
|
|
|
122 The fact that LLVM provides a compact, target-independent,
|
|
|
123 representation for code gets a lot of people excited. Unfortunately,
|
|
|
124 these people are usually thinking about C or a language from the C
|
|
|
125 family when they are asking questions about language portability. I say
|
|
|
126 "unfortunately", because there is really no way to make (fully general)
|
|
|
127 C code portable, other than shipping the source code around (and of
|
|
|
128 course, C source code is not actually portable in general either - ever
|
|
|
129 port a really old application from 32- to 64-bits?).
|
|
|
130
|
|
|
131 The problem with C (again, in its full generality) is that it is heavily
|
|
|
132 laden with target specific assumptions. As one simple example, the
|
|
|
133 preprocessor often destructively removes target-independence from the
|
|
|
134 code when it processes the input text:
|
|
|
135
|
|
|
136 .. code-block:: c
|
|
|
137
|
|
|
138 #ifdef __i386__
|
|
|
139 int X = 1;
|
|
|
140 #else
|
|
|
141 int X = 42;
|
|
|
142 #endif
|
|
|
143
|
|
|
144 While it is possible to engineer more and more complex solutions to
|
|
|
145 problems like this, it cannot be solved in full generality in a way that
|
|
|
146 is better than shipping the actual source code.
|
|
|
147
|
|
|
148 That said, there are interesting subsets of C that can be made portable.
|
|
|
149 If you are willing to fix primitive types to a fixed size (say int =
|
|
|
150 32-bits, and long = 64-bits), don't care about ABI compatibility with
|
|
|
151 existing binaries, and are willing to give up some other minor features,
|
|
|
152 you can have portable code. This can make sense for specialized domains
|
|
|
153 such as an in-kernel language.
|
|
|
154
|
|
|
155 Safety Guarantees
|
|
|
156 -----------------
|
|
|
157
|
|
|
158 Many of the languages above are also "safe" languages: it is impossible
|
|
|
159 for a program written in Java to corrupt its address space and crash the
|
|
|
160 process (assuming the JVM has no bugs). Safety is an interesting
|
|
|
161 property that requires a combination of language design, runtime
|
|
|
162 support, and often operating system support.
|
|
|
163
|
|
|
164 It is certainly possible to implement a safe language in LLVM, but LLVM
|
|
|
165 IR does not itself guarantee safety. The LLVM IR allows unsafe pointer
|
|
|
166 casts, use after free bugs, buffer over-runs, and a variety of other
|
|
|
167 problems. Safety needs to be implemented as a layer on top of LLVM and,
|
|
236
|
168 conveniently, several groups have investigated this. Ask on the `LLVM
|
|
|
169 forums <https://discourse.llvm.org>`_ if you are interested in more details.
|
|
150
|
170
|
|
|
171 Language-Specific Optimizations
|
|
|
172 -------------------------------
|
|
|
173
|
|
|
174 One thing about LLVM that turns off many people is that it does not
|
|
|
175 solve all the world's problems in one system. One specific
|
|
|
176 complaint is that people perceive LLVM as being incapable of performing
|
|
|
177 high-level language-specific optimization: LLVM "loses too much
|
|
|
178 information". Here are a few observations about this:
|
|
|
179
|
|
|
180 First, you're right that LLVM does lose information. For example, as of
|
|
|
181 this writing, there is no way to distinguish in the LLVM IR whether an
|
|
|
182 SSA-value came from a C "int" or a C "long" on an ILP32 machine (other
|
|
|
183 than debug info). Both get compiled down to an 'i32' value and the
|
|
|
184 information about what it came from is lost. The more general issue
|
|
|
185 here, is that the LLVM type system uses "structural equivalence" instead
|
|
|
186 of "name equivalence". Another place this surprises people is if you
|
|
|
187 have two types in a high-level language that have the same structure
|
|
|
188 (e.g. two different structs that have a single int field): these types
|
|
|
189 will compile down into a single LLVM type and it will be impossible to
|
|
|
190 tell what it came from.
|
|
|
191
|
|
|
192 Second, while LLVM does lose information, LLVM is not a fixed target: we
|
|
|
193 continue to enhance and improve it in many different ways. In addition
|
|
|
194 to adding new features (LLVM did not always support exceptions or debug
|
|
|
195 info), we also extend the IR to capture important information for
|
|
|
196 optimization (e.g. whether an argument is sign or zero extended,
|
|
|
197 information about pointers aliasing, etc). Many of the enhancements are
|
|
|
198 user-driven: people want LLVM to include some specific feature, so they
|
|
|
199 go ahead and extend it.
|
|
|
200
|
|
|
201 Third, it is *possible and easy* to add language-specific optimizations,
|
|
|
202 and you have a number of choices in how to do it. As one trivial
|
|
|
203 example, it is easy to add language-specific optimization passes that
|
|
|
204 "know" things about code compiled for a language. In the case of the C
|
|
|
205 family, there is an optimization pass that "knows" about the standard C
|
|
|
206 library functions. If you call "exit(0)" in main(), it knows that it is
|
|
|
207 safe to optimize that into "return 0;" because C specifies what the
|
|
|
208 'exit' function does.
|
|
|
209
|
|
|
210 In addition to simple library knowledge, it is possible to embed a
|
|
|
211 variety of other language-specific information into the LLVM IR. If you
|
|
|
212 have a specific need and run into a wall, please bring the topic up on
|
|
|
213 the llvm-dev list. At the very worst, you can always treat LLVM as if it
|
|
|
214 were a "dumb code generator" and implement the high-level optimizations
|
|
|
215 you desire in your front-end, on the language-specific AST.
|
|
|
216
|
|
|
217 Tips and Tricks
|
|
|
218 ===============
|
|
|
219
|
|
|
220 There is a variety of useful tips and tricks that you come to know after
|
|
|
221 working on/with LLVM that aren't obvious at first glance. Instead of
|
|
|
222 letting everyone rediscover them, this section talks about some of these
|
|
|
223 issues.
|
|
|
224
|
|
|
225 Implementing portable offsetof/sizeof
|
|
|
226 -------------------------------------
|
|
|
227
|
|
|
228 One interesting thing that comes up, if you are trying to keep the code
|
|
|
229 generated by your compiler "target independent", is that you often need
|
|
|
230 to know the size of some LLVM type or the offset of some field in an
|
|
|
231 llvm structure. For example, you might need to pass the size of a type
|
|
|
232 into a function that allocates memory.
|
|
|
233
|
|
|
234 Unfortunately, this can vary widely across targets: for example the
|
|
|
235 width of a pointer is trivially target-specific. However, there is a
|
|
|
236 `clever way to use the getelementptr
|
|
|
237 instruction <http://nondot.org/sabre/LLVMNotes/SizeOf-OffsetOf-VariableSizedStructs.txt>`_
|
|
|
238 that allows you to compute this in a portable way.
|
|
|
239
|
|
|
240 Garbage Collected Stack Frames
|
|
|
241 ------------------------------
|
|
|
242
|
|
|
243 Some languages want to explicitly manage their stack frames, often so
|
|
|
244 that they are garbage collected or to allow easy implementation of
|
|
|
245 closures. There are often better ways to implement these features than
|
|
|
246 explicit stack frames, but `LLVM does support
|
|
|
247 them, <http://nondot.org/sabre/LLVMNotes/ExplicitlyManagedStackFrames.txt>`_
|
|
|
248 if you want. It requires your front-end to convert the code into
|
|
|
249 `Continuation Passing
|
|
|
250 Style <http://en.wikipedia.org/wiki/Continuation-passing_style>`_ and
|
|
|
251 the use of tail calls (which LLVM also supports).
|
|
|
252
|
