253 lines · plain
1======================================================2Kaleidoscope: Conclusion and other useful LLVM tidbits3======================================================4 5.. contents::6 :local:7 8Tutorial Conclusion9===================10 11Welcome to the final chapter of the "`Implementing a language with12LLVM <index.html>`_" tutorial. In the course of this tutorial, we have13grown our little Kaleidoscope language from being a useless toy, to14being a semi-interesting (but probably still useless) toy. :)15 16It is interesting to see how far we've come, and how little code it has17taken. We built the entire lexer, parser, AST, code generator, an18interactive run-loop (with a JIT!), and emitted debug information in19standalone executables - all in under 1000 lines of (non-comment/non-blank)20code.21 22Our little language supports a couple of interesting features: it23supports user defined binary and unary operators, it uses JIT24compilation for immediate evaluation, and it supports a few control flow25constructs with SSA construction.26 27Part of the idea of this tutorial was to show you how easy and fun it28can be to define, build, and play with languages. Building a compiler29need not be a scary or mystical process! Now that you've seen some of30the basics, I strongly encourage you to take the code and hack on it.31For example, try adding:32 33- **global variables** - While global variables have questionable value34 in modern software engineering, they are often useful when putting35 together quick little hacks like the Kaleidoscope compiler itself.36 Fortunately, our current setup makes it very easy to add global37 variables: just have value lookup check to see if an unresolved38 variable is in the global variable symbol table before rejecting it.39 To create a new global variable, make an instance of the LLVM40 ``GlobalVariable`` class.41- **typed variables** - Kaleidoscope currently only supports variables42 of type double. This gives the language a very nice elegance, because43 only supporting one type means that you never have to specify types.44 Different languages have different ways of handling this. The easiest45 way is to require the user to specify types for every variable46 definition, and record the type of the variable in the symbol table47 along with its Value\*.48- **arrays, structs, vectors, etc** - Once you add types, you can start49 extending the type system in all sorts of interesting ways. Simple50 arrays are very easy and are quite useful for many different51 applications. Adding them is mostly an exercise in learning how the52 LLVM `getelementptr <../../LangRef.html#getelementptr-instruction>`_ instruction53 works: it is so nifty/unconventional, it `has its own54 FAQ <../../GetElementPtr.html>`_!55- **standard runtime** - Our current language allows the user to access56 arbitrary external functions, and we use it for things like "printd"57 and "putchard". As you extend the language to add higher-level58 constructs, often these constructs make the most sense if they are59 lowered to calls into a language-supplied runtime. For example, if60 you add hash tables to the language, it would probably make sense to61 add the routines to a runtime, instead of inlining them all the way.62- **memory management** - Currently we can only access the stack in63 Kaleidoscope. It would also be useful to be able to allocate heap64 memory, either with calls to the standard libc malloc/free interface65 or with a garbage collector. If you would like to use garbage66 collection, note that LLVM fully supports `Accurate Garbage67 Collection <../../GarbageCollection.html>`_ including algorithms that68 move objects and need to scan/update the stack.69- **exception handling support** - LLVM supports generation of `zero70 cost exceptions <../../ExceptionHandling.html>`_ which interoperate with71 code compiled in other languages. You could also generate code by72 implicitly making every function return an error value and checking73 it. You could also make explicit use of setjmp/longjmp. There are74 many different ways to go here.75- **object orientation, generics, database access, complex numbers,76 geometric programming, ...** - Really, there is no end of crazy77 features that you can add to the language.78- **unusual domains** - We've been talking about applying LLVM to a79 domain that many people are interested in: building a compiler for a80 specific language. However, there are many other domains that can use81 compiler technology that are not typically considered. For example,82 LLVM has been used to implement OpenGL graphics acceleration,83 translate C++ code to ActionScript, and many other cute and clever84 things. Maybe you will be the first to JIT compile a regular85 expression interpreter into native code with LLVM?86 87Have fun - try doing something crazy and unusual. Building a language88like everyone else always has, is much less fun than trying something a89little crazy or off the wall and seeing how it turns out. If you get90stuck or want to talk about it, please post on the `LLVM forums 91<https://discourse.llvm.org>`_: it has lots of people who are interested92in languages and are often willing to help out.93 94Before we end this tutorial, I want to talk about some "tips and tricks"95for generating LLVM IR. These are some of the more subtle things that96may not be obvious, but are very useful if you want to take advantage of97LLVM's capabilities.98 99Properties of the LLVM IR100=========================101 102We have a couple of common questions about code in the LLVM IR form -103let's just get these out of the way right now, shall we?104 105Target Independence106-------------------107 108Kaleidoscope is an example of a "portable language": any program written109in Kaleidoscope will work the same way on any target that it runs on.110Many other languages have this property, e.g. lisp, java, haskell,111javascript, python, etc (note that while these languages are portable,112not all their libraries are).113 114One nice aspect of LLVM is that it is often capable of preserving target115independence in the IR: you can take the LLVM IR for a116Kaleidoscope-compiled program and run it on any target that LLVM117supports, even emitting C code and compiling that on targets that LLVM118doesn't support natively. You can trivially tell that the Kaleidoscope119compiler generates target-independent code because it never queries for120any target-specific information when generating code.121 122The fact that LLVM provides a compact, target-independent,123representation for code gets a lot of people excited. Unfortunately,124these people are usually thinking about C or a language from the C125family when they are asking questions about language portability. I say126"unfortunately", because there is really no way to make (fully general)127C code portable, other than shipping the source code around (and of128course, C source code is not actually portable in general either - ever129port a really old application from 32- to 64-bits?).130 131The problem with C (again, in its full generality) is that it is heavily132laden with target-specific assumptions. As one simple example, the133preprocessor often destructively removes target-independence from the134code when it processes the input text:135 136.. code-block:: c137 138 #ifdef __i386__139 int X = 1;140 #else141 int X = 42;142 #endif143 144While it is possible to engineer more and more complex solutions to145problems like this, it cannot be solved in full generality in a way that146is better than shipping the actual source code.147 148That said, there are interesting subsets of C that can be made portable.149If you are willing to fix primitive types to a fixed size (say int =15032-bits, and long = 64-bits), don't care about ABI compatibility with151existing binaries, and are willing to give up some other minor features,152you can have portable code. This can make sense for specialized domains153such as an in-kernel language.154 155Safety Guarantees156-----------------157 158Many of the languages above are also "safe" languages: it is impossible159for a program written in Java to corrupt its address space and crash the160process (assuming the JVM has no bugs). Safety is an interesting161property that requires a combination of language design, runtime162support, and often operating system support.163 164It is certainly possible to implement a safe language in LLVM, but LLVM165IR does not itself guarantee safety. The LLVM IR allows unsafe pointer166casts, use after free bugs, buffer over-runs, and a variety of other167problems. Safety needs to be implemented as a layer on top of LLVM and,168conveniently, several groups have investigated this. Ask on the `LLVM169forums <https://discourse.llvm.org>`_ if you are interested in more details.170 171Language-Specific Optimizations172-------------------------------173 174One thing about LLVM that turns off many people is that it does not175solve all the world's problems in one system. One specific176complaint is that people perceive LLVM as being incapable of performing177high-level language-specific optimization: LLVM "loses too much178information". Here are a few observations about this:179 180First, you're right that LLVM does lose information. For example, as of181this writing, there is no way to distinguish in the LLVM IR whether an182SSA-value came from a C "int" or a C "long" on an ILP32 machine (other183than debug info). Both get compiled down to an 'i32' value and the184information about what it came from is lost. The more general issue185here, is that the LLVM type system uses "structural equivalence" instead186of "name equivalence". Another place this surprises people is if you187have two types in a high-level language that have the same structure188(e.g. two different structs that have a single int field): these types189will compile down into a single LLVM type and it will be impossible to190tell what it came from.191 192Second, while LLVM does lose information, LLVM is not a fixed target: we193continue to enhance and improve it in many different ways. In addition194to adding new features (LLVM did not always support exceptions or debug195info), we also extend the IR to capture important information for196optimization (e.g. whether an argument is sign or zero extended,197information about pointers aliasing, etc). Many of the enhancements are198user-driven: people want LLVM to include some specific feature, so they199go ahead and extend it.200 201Third, it is *possible and easy* to add language-specific optimizations,202and you have a number of choices in how to do it. As one trivial203example, it is easy to add language-specific optimization passes that204"know" things about code compiled for a language. In the case of the C205family, there is an optimization pass that "knows" about the standard C206library functions. If you call "exit(0)" in main(), it knows that it is207safe to optimize that into "return 0;" because C specifies what the208'exit' function does.209 210In addition to simple library knowledge, it is possible to embed a211variety of other language-specific information into the LLVM IR. If you212have a specific need and run into a wall, please bring the topic up on213the llvm-dev list. At the very worst, you can always treat LLVM as if it214were a "dumb code generator" and implement the high-level optimizations215you desire in your front-end, on the language-specific AST.216 217Tips and Tricks218===============219 220There is a variety of useful tips and tricks that you come to know after221working on/with LLVM that aren't obvious at first glance. Instead of222letting everyone rediscover them, this section talks about some of these223issues.224 225Implementing portable offsetof/sizeof226-------------------------------------227 228One interesting thing that comes up, if you are trying to keep the code229generated by your compiler "target independent", is that you often need230to know the size of some LLVM type or the offset of some field in an231llvm structure. For example, you might need to pass the size of a type232into a function that allocates memory.233 234Unfortunately, this can vary widely across targets: for example the235width of a pointer is trivially target-specific. However, there is a236`clever way to use the getelementptr237instruction <http://nondot.org/sabre/LLVMNotes/SizeOf-OffsetOf-VariableSizedStructs.txt>`_238that allows you to compute this in a portable way.239 240Garbage Collected Stack Frames241------------------------------242 243Some languages want to explicitly manage their stack frames, often so244that they are garbage collected or to allow easy implementation of245closures. There are often better ways to implement these features than246explicit stack frames, but `LLVM does support247them, <http://nondot.org/sabre/LLVMNotes/ExplicitlyManagedStackFrames.txt>`_248if you want. It requires your front-end to convert the code into249`Continuation Passing250Style <http://en.wikipedia.org/wiki/Continuation-passing_style>`_ and251the use of tail calls (which LLVM also supports).252 253