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