1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
2 "http://www.w3.org/TR/html4/strict.dtd">
6 <title>Kaleidoscope: Conclusion and other useful LLVM tidbits</title>
7 <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
8 <meta name="author" content="Chris Lattner">
9 <link rel="stylesheet" href="../llvm.css" type="text/css">
14 <div class="doc_title">Kaleidoscope: Conclusion and other useful LLVM
20 <li><a href="#conclusion">Tutorial Conclusion</a></li>
21 <li><a href="#llvmirproperties">Properties of LLVM IR</a>
23 <li><a href="#targetindep">Target Independence</a></li>
24 <li><a href="#safety">Safety Guarantees</a></li>
25 <li><a href="#langspecific">Language-Specific Optimizations</a></li>
28 <li><a href="#tipsandtricks">Tips and Tricks</a>
30 <li><a href="#offsetofsizeof">Implementing portable
31 offsetof/sizeof</a></li>
32 <li><a href="#gcstack">Garbage Collected Stack Frames</a></li>
40 <div class="doc_author">
41 <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p>
44 <!-- *********************************************************************** -->
45 <div class="doc_section"><a name="conclusion">Tutorial Conclusion</a></div>
46 <!-- *********************************************************************** -->
48 <div class="doc_text">
50 <p>Welcome to the the final chapter of the "<a href="index.html">Implementing a
51 language with LLVM</a>" tutorial. In the course of this tutorial, we have grown
52 our little Kaleidoscope language from being a useless toy, to being a
53 semi-interesting (but probably still useless) toy. :)</p>
55 <p>It is interesting to see how far we've come, and how little code it has
56 taken. We built the entire lexer, parser, AST, code generator, and an
57 interactive run-loop (with a JIT!) by-hand in under 700 lines of
58 (non-comment/non-blank) code.</p>
60 <p>Our little language supports a couple of interesting features: it supports
61 user defined binary and unary operators, it uses JIT compilation for immediate
62 evaluation, and it supports a few control flow constructs with SSA construction.
65 <p>Part of the idea of this tutorial was to show you how easy and fun it can be
66 to define, build, and play with languages. Building a compiler need not be a
67 scary or mystical process! Now that you've seen some of the basics, I strongly
68 encourage you to take the code and hack on it. For example, try adding:</p>
71 <li><b>global variables</b> - While global variables have questional value in
72 modern software engineering, they are often useful when putting together quick
73 little hacks like the Kaleidoscope compiler itself. Fortunately, our current
74 setup makes it very easy to add global variables: just have value lookup check
75 to see if an unresolved variable is in the global variable symbol table before
76 rejecting it. To create a new global variable, make an instance of the LLVM
77 <tt>GlobalVariable</tt> class.</li>
79 <li><b>typed variables</b> - Kaleidoscope currently only supports variables of
80 type double. This gives the language a very nice elegance, because only
81 supporting one type means that you never have to specify types. Different
82 languages have different ways of handling this. The easiest way is to require
83 the user to specify types for every variable definition, and record the type
84 of the variable in the symbol table along with its Value*.</li>
86 <li><b>arrays, structs, vectors, etc</b> - Once you add types, you can start
87 extending the type system in all sorts of interesting ways. Simple arrays are
88 very easy and are quite useful for many different applications. Adding them is
89 mostly an exercise in learning how the LLVM <a
90 href="../LangRef.html#i_getelementptr">getelementptr</a> instruction works.
91 The getelementptr instruction is so nifty/unconventional, it <a
92 href="../GetElementPtr.html">has its own FAQ</a>!).</li>
94 <li><b>standard runtime</b> - Our current language allows the user to access
95 arbitrary external functions, and we use it for things like "printd" and
96 "putchard". As you extend the language to add higher-level constructs, often
97 these constructs make the most amount of sense to be lowered into calls into a
98 language-supplied runtime. For example, if you add hash tables to the language,
99 it would probably make sense to add the routines to a runtime, instead of
100 inlining them all the way.</li>
102 <li><b>memory management</b> - Currently we can only access the stack in
103 Kaleidoscope. It would also be useful to be able to allocate heap memory,
104 either with calls to the standard libc malloc/free interface or with a garbage
105 collector. If you choose to use garbage collection, note that LLVM fully
106 supports <a href="../GarbageCollection.html">Accurate Garbage Collection</a>
107 including algorithms that move objects and need to scan/update the stack.</li>
109 <li><b>debugger support</b> - LLVM supports generation of <a
110 href="../SourceLevelDebugging.html">DWARF Debug info</a> which is understood by
111 common debuggers like GDB. Adding support for debug info is fairly
112 straight-forward. The best way to understand it is to compile some C/C++ code
113 with "<tt>llvm-gcc -g -O0</tt>" and taking a look at what it produces.</li>
115 <li><b>exception handling support</b> - LLVM supports generation of <a
116 href="../ExceptionHandling.html">zero cost exceptions</a> which interoperate
117 with code compiled in other languages. You could also generate code by
118 implicitly making every function return an error value and checking it. You
119 could also make explicit use of setjmp/longjmp. There are many different ways
122 <li><b>object orientation, generics, database access, complex numbers,
123 geometric programming, ...</b> - Really, there is
124 no end of crazy features that you can add to the language.</li>
126 <li><b>unusual domains</b> - We've been talking about applying LLVM to a domain
127 that many people are interested in: building a compiler for a specific language.
128 However, there are many other domains that can use compiler technology that are
129 not typically considered. For example, LLVM has been used to implement OpenGL
130 graphics acceleration, translate C++ code to ActionScript, and many other
131 cute and clever things. Maybe you will be the first to JIT compile a regular
132 expression interpreter into native code with LLVM?</li>
137 Have fun - try doing something crazy and unusual. Building a language like
138 everyone else always has is much less fun than trying something a little crazy
139 and off the wall and seeing how it turns out. If you get stuck or want to talk
140 about it, feel free to email the <a
141 href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">llvmdev mailing
142 list</a>: it has lots of people who are interested in languages and are often
146 <p>Before we end, I want to talk about some "tips and tricks" for generating
147 LLVM IR. These are some of the more subtle things that may not be obvious, but
148 are very useful if you want to take advantage of LLVM's capabilities.</p>
152 <!-- *********************************************************************** -->
153 <div class="doc_section"><a name="llvmirproperties">Properties of LLVM
155 <!-- *********************************************************************** -->
157 <div class="doc_text">
159 <p>We have a couple common questions about code in the LLVM IR form, lets just
160 get these out of the way right now shall we?</p>
164 <!-- ======================================================================= -->
165 <div class="doc_subsubsection"><a name="targetindep">Target
166 Independence</a></div>
167 <!-- ======================================================================= -->
169 <div class="doc_text">
171 <p>Kaleidoscope is an example of a "portable language": any program written in
172 Kaleidoscope will work the same way on any target that it runs on. Many other
173 languages have this property, e.g. lisp, java, haskell, javascript, python, etc
174 (note that while these languages are portable, not all their libraries are).</p>
176 <p>One nice aspect of LLVM is that it is often capable of preserving language
177 independence in the IR: you can take the LLVM IR for a Kaleidoscope-compiled
178 program and run it on any target that LLVM supports, even emitting C code and
179 compiling that on targets that LLVM doesn't support natively. You can trivially
180 tell that the Kaleidoscope compiler generates target-independent code because it
181 never queries for any target-specific information when generating code.</p>
183 <p>The fact that LLVM provides a compact target-independent representation for
184 code gets a lot of people excited. Unfortunately, these people are usually
185 thinking about C or a language from the C family when they are asking questions
186 about language portability. I say "unfortunately", because there is really no
187 way to make (fully general) C code portable, other than shipping the source code
188 around (and of course, C source code is not actually portable in general
189 either - ever port a really old application from 32- to 64-bits?).</p>
191 <p>The problem with C (again, in its full generality) is that it is heavily
192 laden with target specific assumptions. As one simple example, the preprocessor
193 often destructively removes target-independence from the code when it processes
196 <div class="doc_code">
206 <p>While it is possible to engineer more and more complex solutions to problems
207 like this, it cannot be solved in full generality in a way better than shipping
208 the actual source code.</p>
210 <p>That said, there are interesting subsets of C that can be made portable. If
211 you are willing to fix primitive types to a fixed size (say int = 32-bits,
212 and long = 64-bits), don't care about ABI compatibility with existing binaries,
213 and are willing to give up some other minor features, you can have portable
214 code. This can even make real sense for specialized domains such as an
215 in-kernel language.</p>
219 <!-- ======================================================================= -->
220 <div class="doc_subsubsection"><a name="safety">Safety Guarantees</a></div>
221 <!-- ======================================================================= -->
223 <div class="doc_text">
225 <p>Many of the languages above are also "safe" languages: it is impossible for
226 a program written in Java to corrupt its address space and crash the process.
227 Safety is an interesting property that requires a combination of language
228 design, runtime support, and often operating system support.</p>
230 <p>It is certainly possible to implement a safe language in LLVM, but LLVM IR
231 does not itself guarantee safety. The LLVM IR allows unsafe pointer casts,
232 use after free bugs, buffer over-runs, and a variety of other problems. Safety
233 needs to be implemented as a layer on top of LLVM and, conveniently, several
234 groups have investigated this. Ask on the <a
235 href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">llvmdev mailing
236 list</a> if you are interested in more details.</p>
240 <!-- ======================================================================= -->
241 <div class="doc_subsubsection"><a name="langspecific">Language-Specific
242 Optimizations</a></div>
243 <!-- ======================================================================= -->
245 <div class="doc_text">
247 <p>One thing about LLVM that turns off many people is that it does not solve all
248 the world's problems in one system (sorry 'world hunger', someone else will have
249 to solve you some other day). One specific complaint is that people perceive
250 LLVM as being incapable of performing high-level language-specific optimization:
251 LLVM "loses too much information".</p>
253 <p>Unfortunately, this is really not the place to give you a full and unified
254 version of "Chris Lattner's theory of compiler design". Instead, I'll make a
255 few observations:</p>
257 <p>First, you're right that LLVM does lose information. For example, as of this
258 writing, there is no way to distinguish in the LLVM IR whether an SSA-value came
259 from a C "int" or a C "long" on an ILP32 machine (other than debug info). Both
260 get compiled down to an 'i32' value and the information about what it came from
261 is lost. The more general issue here is that the LLVM type system uses
262 "structural equivalence" instead of "name equivalence". Another place this
263 surprises people is if you have two types in a high-level language that have the
264 same structure (e.g. two different structs that have a single int field): these
265 types will compile down into a single LLVM type and it will be impossible to
266 tell what it came from.</p>
268 <p>Second, while LLVM does lose information, LLVM is not a fixed target: we
269 continue to enhance and improve it in many different ways. In addition to
270 adding new features (LLVM did not always support exceptions or debug info), we
271 also extend the IR to capture important information for optimization (e.g.
272 whether an argument is sign or zero extended, information about pointers
273 aliasing, etc. Many of the enhancements are user-driven: people want LLVM to
274 do some specific feature, so they go ahead and extend it to do so.</p>
276 <p>Third, it <em>is certainly possible</em> to add language-specific
277 optimizations, and you have a number of choices in how to do it. As one trivial
278 example, it is possible to add language-specific optimization passes that
279 "known" things about code compiled for a language. In the case of the C family,
280 there is an optimziation pass that "knows" about the standard C library
281 functions. If you call "exit(0)" in main(), it knows that it is safe to
282 optimize that into "return 0;" for example, because C specifies what the 'exit'
285 <p>In addition to simple library knowledge, it is possible to embed a variety of
286 other language-specific information into the LLVM IR. If you have a specific
287 need and run into a wall, please bring the topic up on the llvmdev list. At the
288 very worst, you can always treat LLVM as if it were a "dumb code generator" and
289 implement the high-level optimizations you desire in your front-end on the
290 language-specific AST.
295 <!-- *********************************************************************** -->
296 <div class="doc_section"><a name="tipsandtricks">Tips and Tricks</a></div>
297 <!-- *********************************************************************** -->
299 <div class="doc_text">
301 <p>There is a variety of useful tips and tricks that you come to know after
302 working on/with LLVM that aren't obvious at first glance. Instead of letting
303 everyone rediscover them, this section talks about some of these issues.</p>
307 <!-- ======================================================================= -->
308 <div class="doc_subsubsection"><a name="offsetofsizeof">Implementing portable
309 offsetof/sizeof</a></div>
310 <!-- ======================================================================= -->
312 <div class="doc_text">
314 <p>One interesting thing that comes up if you are trying to keep the code
315 generated by your compiler "target independent" is that you often need to know
316 the size of some LLVM type or the offset of some field in an llvm structure.
317 For example, you might need to pass the size of a type into a function that
318 allocates memory.</p>
320 <p>Unfortunately, this can vary widely across targets: for example the width of
321 a pointer is trivially target-specific. However, there is a <a
322 href="http://nondot.org/sabre/LLVMNotes/SizeOf-OffsetOf-VariableSizedStructs.txt">clever
323 way to use the getelementptr instruction</a> that allows you to compute this
324 in a portable way.</p>
328 <!-- ======================================================================= -->
329 <div class="doc_subsubsection"><a name="gcstack">Garbage Collected
330 Stack Frames</a></div>
331 <!-- ======================================================================= -->
333 <div class="doc_text">
335 <p>Some languages want to explicitly manage their stack frames, often so that
336 they are garbage collected or to allow easy implementation of closures. There
337 are often better ways to implement these features than explicit stack frames,
339 href="http://nondot.org/sabre/LLVMNotes/ExplicitlyManagedStackFrames.txt">LLVM
340 does support them if you want</a>. It requires your front-end to convert the
342 href="http://en.wikipedia.org/wiki/Continuation-passing_style">Continuation
343 Passing Style</a> and use of tail calls (which LLVM also supports).</p>
347 <!-- *********************************************************************** -->
350 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
351 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
352 <a href="http://validator.w3.org/check/referer"><img
353 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
355 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
356 <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
357 Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $