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