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