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