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