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