| blob | 64a62002c4ccdfa00a81667e313c8c752182d085 |
4 <html>
5 <head>
10 </head>
12 <body>
15 tidbits</div>
17 <ul>
20 <ol>
23 <ul>
27 </ul>
28 </li>
30 <ul>
32 offsetof/sizeof</a></li>
34 </ul>
35 </li>
36 </ol>
37 </li>
38 </ul>
43 </div>
45 <!-- *********************************************************************** -->
47 <!-- *********************************************************************** -->
52 language with LLVM</a>" tutorial. In the course of this tutorial, we have grown
53 our little Kaleidoscope language from being a useless toy, to being a
54 semi-interesting (but probably still useless) toy. :)</p>
56 <p>It is interesting to see how far we've come, and how little code it has
57 taken. We built the entire lexer, parser, AST, code generator, and an
58 interactive run-loop (with a JIT!) by-hand in under 700 lines of
59 (non-comment/non-blank) code.</p>
61 <p>Our little language supports a couple of interesting features: it supports
62 user defined binary and unary operators, it uses JIT compilation for immediate
63 evaluation, and it supports a few control flow constructs with SSA construction.
64 </p>
66 <p>Part of the idea of this tutorial was to show you how easy and fun it can be
67 to define, build, and play with languages. Building a compiler need not be a
68 scary or mystical process! Now that you've seen some of the basics, I strongly
69 encourage you to take the code and hack on it. For example, try adding:</p>
71 <ul>
73 modern software engineering, they are often useful when putting together quick
74 little hacks like the Kaleidoscope compiler itself. Fortunately, our current
75 setup makes it very easy to add global variables: just have value lookup check
76 to see if an unresolved variable is in the global variable symbol table before
77 rejecting it. To create a new global variable, make an instance of the LLVM
81 type double. This gives the language a very nice elegance, because only
82 supporting one type means that you never have to specify types. Different
83 languages have different ways of handling this. The easiest way is to require
84 the user to specify types for every variable definition, and record the type
85 of the variable in the symbol table along with its Value*.</li>
88 extending the type system in all sorts of interesting ways. Simple arrays are
89 very easy and are quite useful for many different applications. Adding them is
90 mostly an exercise in learning how the LLVM <a
92 is so nifty/unconventional, it <a
94 for recursive types (e.g. linked lists), make sure to read the <a
99 arbitrary external functions, and we use it for things like "printd" and
100 "putchard". As you extend the language to add higher-level constructs, often
101 these constructs make the most sense if they are lowered to calls into a
102 language-supplied runtime. For example, if you add hash tables to the language,
103 it would probably make sense to add the routines to a runtime, instead of
104 inlining them all the way.</li>
107 Kaleidoscope. It would also be useful to be able to allocate heap memory,
108 either with calls to the standard libc malloc/free interface or with a garbage
109 collector. If you would like to use garbage collection, note that LLVM fully
111 including algorithms that move objects and need to scan/update the stack.</li>
115 common debuggers like GDB. Adding support for debug info is fairly
116 straightforward. The best way to understand it is to compile some C/C++ code
121 with code compiled in other languages. You could also generate code by
122 implicitly making every function return an error value and checking it. You
123 could also make explicit use of setjmp/longjmp. There are many different ways
124 to go here.</li>
126 <li><b>object orientation, generics, database access, complex numbers,
127 geometric programming, ...</b> - Really, there is
128 no end of crazy features that you can add to the language.</li>
131 that many people are interested in: building a compiler for a specific language.
132 However, there are many other domains that can use compiler technology that are
133 not typically considered. For example, LLVM has been used to implement OpenGL
134 graphics acceleration, translate C++ code to ActionScript, and many other
135 cute and clever things. Maybe you will be the first to JIT compile a regular
136 expression interpreter into native code with LLVM?</li>
138 </ul>
140 <p>
141 Have fun - try doing something crazy and unusual. Building a language like
142 everyone else always has, is much less fun than trying something a little crazy
143 or off the wall and seeing how it turns out. If you get stuck or want to talk
144 about it, feel free to email the <a
146 list</a>: it has lots of people who are interested in languages and are often
147 willing to help out.
148 </p>
151 LLVM IR. These are some of the more subtle things that may not be obvious, but
152 are very useful if you want to take advantage of LLVM's capabilities.</p>
154 </div>
156 <!-- *********************************************************************** -->
158 IR</a></div>
159 <!-- *********************************************************************** -->
163 <p>We have a couple common questions about code in the LLVM IR form - lets just
164 get these out of the way right now, shall we?</p>
166 </div>
168 <!-- ======================================================================= -->
170 Independence</a></div>
171 <!-- ======================================================================= -->
176 Kaleidoscope will work the same way on any target that it runs on. Many other
177 languages have this property, e.g. lisp, java, haskell, javascript, python, etc
178 (note that while these languages are portable, not all their libraries are).</p>
180 <p>One nice aspect of LLVM is that it is often capable of preserving target
181 independence in the IR: you can take the LLVM IR for a Kaleidoscope-compiled
182 program and run it on any target that LLVM supports, even emitting C code and
183 compiling that on targets that LLVM doesn't support natively. You can trivially
184 tell that the Kaleidoscope compiler generates target-independent code because it
185 never queries for any target-specific information when generating code.</p>
187 <p>The fact that LLVM provides a compact, target-independent, representation for
188 code gets a lot of people excited. Unfortunately, these people are usually
189 thinking about C or a language from the C family when they are asking questions
190 about language portability. I say "unfortunately", because there is really no
191 way to make (fully general) C code portable, other than shipping the source code
192 around (and of course, C source code is not actually portable in general
195 <p>The problem with C (again, in its full generality) is that it is heavily
196 laden with target specific assumptions. As one simple example, the preprocessor
197 often destructively removes target-independence from the code when it processes
198 the input text:</p>
201 <pre>
202 #ifdef __i386__
203 int X = 1;
204 #else
205 int X = 42;
206 #endif
207 </pre>
208 </div>
210 <p>While it is possible to engineer more and more complex solutions to problems
211 like this, it cannot be solved in full generality in a way that is better than shipping
212 the actual source code.</p>
214 <p>That said, there are interesting subsets of C that can be made portable. If
215 you are willing to fix primitive types to a fixed size (say int = 32-bits,
216 and long = 64-bits), don't care about ABI compatibility with existing binaries,
217 and are willing to give up some other minor features, you can have portable
218 code. This can make sense for specialized domains such as an
219 in-kernel language.</p>
221 </div>
223 <!-- ======================================================================= -->
225 <!-- ======================================================================= -->
230 a program written in Java to corrupt its address space and crash the process
231 (assuming the JVM has no bugs).
232 Safety is an interesting property that requires a combination of language
233 design, runtime support, and often operating system support.</p>
235 <p>It is certainly possible to implement a safe language in LLVM, but LLVM IR
236 does not itself guarantee safety. The LLVM IR allows unsafe pointer casts,
237 use after free bugs, buffer over-runs, and a variety of other problems. Safety
238 needs to be implemented as a layer on top of LLVM and, conveniently, several
239 groups have investigated this. Ask on the <a
243 </div>
245 <!-- ======================================================================= -->
247 Optimizations</a></div>
248 <!-- ======================================================================= -->
252 <p>One thing about LLVM that turns off many people is that it does not solve all
253 the world's problems in one system (sorry 'world hunger', someone else will have
254 to solve you some other day). One specific complaint is that people perceive
255 LLVM as being incapable of performing high-level language-specific optimization:
258 <p>Unfortunately, this is really not the place to give you a full and unified
259 version of "Chris Lattner's theory of compiler design". Instead, I'll make a
260 few observations:</p>
262 <p>First, you're right that LLVM does lose information. For example, as of this
263 writing, there is no way to distinguish in the LLVM IR whether an SSA-value came
265 get compiled down to an 'i32' value and the information about what it came from
266 is lost. The more general issue here, is that the LLVM type system uses
268 surprises people is if you have two types in a high-level language that have the
269 same structure (e.g. two different structs that have a single int field): these
270 types will compile down into a single LLVM type and it will be impossible to
271 tell what it came from.</p>
273 <p>Second, while LLVM does lose information, LLVM is not a fixed target: we
274 continue to enhance and improve it in many different ways. In addition to
275 adding new features (LLVM did not always support exceptions or debug info), we
276 also extend the IR to capture important information for optimization (e.g.
277 whether an argument is sign or zero extended, information about pointers
278 aliasing, etc). Many of the enhancements are user-driven: people want LLVM to
279 include some specific feature, so they go ahead and extend it.</p>
282 optimizations, and you have a number of choices in how to do it. As one trivial
283 example, it is easy to add language-specific optimization passes that
284 "know" things about code compiled for a language. In the case of the C family,
285 there is an optimization pass that "knows" about the standard C library
286 functions. If you call "exit(0)" in main(), it knows that it is safe to
287 optimize that into "return 0;" because C specifies what the 'exit'
288 function does.</p>
290 <p>In addition to simple library knowledge, it is possible to embed a variety of
291 other language-specific information into the LLVM IR. If you have a specific
292 need and run into a wall, please bring the topic up on the llvmdev list. At the
293 very worst, you can always treat LLVM as if it were a "dumb code generator" and
294 implement the high-level optimizations you desire in your front-end, on the
295 language-specific AST.
296 </p>
298 </div>
300 <!-- *********************************************************************** -->
302 <!-- *********************************************************************** -->
306 <p>There is a variety of useful tips and tricks that you come to know after
307 working on/with LLVM that aren't obvious at first glance. Instead of letting
308 everyone rediscover them, this section talks about some of these issues.</p>
310 </div>
312 <!-- ======================================================================= -->
314 offsetof/sizeof</a></div>
315 <!-- ======================================================================= -->
319 <p>One interesting thing that comes up, if you are trying to keep the code
320 generated by your compiler "target independent", is that you often need to know
321 the size of some LLVM type or the offset of some field in an llvm structure.
322 For example, you might need to pass the size of a type into a function that
323 allocates memory.</p>
325 <p>Unfortunately, this can vary widely across targets: for example the width of
326 a pointer is trivially target-specific. However, there is a <a
328 way to use the getelementptr instruction</a> that allows you to compute this
329 in a portable way.</p>
331 </div>
333 <!-- ======================================================================= -->
335 Stack Frames</a></div>
336 <!-- ======================================================================= -->
340 <p>Some languages want to explicitly manage their stack frames, often so that
341 they are garbage collected or to allow easy implementation of closures. There
342 are often better ways to implement these features than explicit stack frames,
343 but <a
345 does support them,</a> if you want. It requires your front-end to convert the
346 code into <a
350 </div>
352 <!-- *********************************************************************** -->
353 <hr>
354 <address>
362 Last modified: $Date$
363 </address>
364 </body>
365 </html>