Run DCE after a LoopFlatten test to reduce spurious output [nfc]
[llvm-project.git] / llvm / docs / tutorial / MyFirstLanguageFrontend / LangImpl10.rst
blob7b9105bde7a6fe124628e73a7e3645bd5cfff4be
1 ======================================================
2 Kaleidoscope: Conclusion and other useful LLVM tidbits
3 ======================================================
5 .. contents::
6    :local:
8 Tutorial Conclusion
9 ===================
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. :)
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.
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.
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:
33 -  **global variables** - While global variables have questionable 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>`_!
55 -  **standard runtime** - Our current language allows the user to access
56    arbitrary external functions, and we use it for things like "printd"
57    and "putchard". As you extend the language to add higher-level
58    constructs, often these constructs make the most sense if they are
59    lowered to calls into a language-supplied runtime. For example, if
60    you add hash tables to the language, it would probably make sense to
61    add the routines to a runtime, instead of inlining them all the way.
62 -  **memory management** - Currently we can only access the stack in
63    Kaleidoscope. It would also be useful to be able to allocate heap
64    memory, either with calls to the standard libc malloc/free interface
65    or with a garbage collector. If you would like to use garbage
66    collection, note that LLVM fully supports `Accurate Garbage
67    Collection <../../GarbageCollection.html>`_ including algorithms that
68    move objects and need to scan/update the stack.
69 -  **exception handling support** - LLVM supports generation of `zero
70    cost exceptions <../../ExceptionHandling.html>`_ which interoperate with
71    code compiled in other languages. You could also generate code by
72    implicitly making every function return an error value and checking
73    it. You could also make explicit use of setjmp/longjmp. There are
74    many different ways to go here.
75 -  **object orientation, generics, database access, complex numbers,
76    geometric programming, ...** - Really, there is no end of crazy
77    features that you can add to the language.
78 -  **unusual domains** - We've been talking about applying LLVM to a
79    domain that many people are interested in: building a compiler for a
80    specific language. However, there are many other domains that can use
81    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 clever
84    things. Maybe you will be the first to JIT compile a regular
85    expression interpreter into native code with LLVM?
87 Have fun - try doing something crazy and unusual. Building a language
88 like everyone else always has, is much less fun than trying something a
89 little crazy or off the wall and seeing how it turns out. If you get
90 stuck or want to talk about it, please post on the `LLVM forums 
91 <https://discourse.llvm.org>`_: it has lots of people who are interested
92 in languages and are often willing to help out.
94 Before we end this tutorial, I want to talk about some "tips and tricks"
95 for generating LLVM IR. These are some of the more subtle things that
96 may not be obvious, but are very useful if you want to take advantage of
97 LLVM's capabilities.
99 Properties of the LLVM IR
100 =========================
102 We have a couple of common questions about code in the LLVM IR form -
103 let's just get these out of the way right now, shall we?
105 Target Independence
106 -------------------
108 Kaleidoscope is an example of a "portable language": any program written
109 in Kaleidoscope will work the same way on any target that it runs on.
110 Many other languages have this property, e.g. lisp, java, haskell,
111 javascript, python, etc (note that while these languages are portable,
112 not all their libraries are).
114 One nice aspect of LLVM is that it is often capable of preserving target
115 independence in the IR: you can take the LLVM IR for a
116 Kaleidoscope-compiled program and run it on any target that LLVM
117 supports, even emitting C code and compiling that on targets that LLVM
118 doesn't support natively. You can trivially tell that the Kaleidoscope
119 compiler generates target-independent code because it never queries for
120 any target-specific information when generating code.
122 The fact that LLVM provides a compact, target-independent,
123 representation for code gets a lot of people excited. Unfortunately,
124 these people are usually thinking about C or a language from the C
125 family when they are asking questions about language portability. I say
126 "unfortunately", because there is really no way to make (fully general)
127 C code portable, other than shipping the source code around (and of
128 course, C source code is not actually portable in general either - ever
129 port a really old application from 32- to 64-bits?).
131 The problem with C (again, in its full generality) is that it is heavily
132 laden with target specific assumptions. As one simple example, the
133 preprocessor often destructively removes target-independence from the
134 code when it processes the input text:
136 .. code-block:: c
138     #ifdef __i386__
139       int X = 1;
140     #else
141       int X = 42;
142     #endif
144 While it is possible to engineer more and more complex solutions to
145 problems like this, it cannot be solved in full generality in a way that
146 is better than shipping the actual source code.
148 That said, there are interesting subsets of C that can be made portable.
149 If you are willing to fix primitive types to a fixed size (say int =
150 32-bits, and long = 64-bits), don't care about ABI compatibility with
151 existing binaries, and are willing to give up some other minor features,
152 you can have portable code. This can make sense for specialized domains
153 such as an in-kernel language.
155 Safety Guarantees
156 -----------------
158 Many of the languages above are also "safe" languages: it is impossible
159 for a program written in Java to corrupt its address space and crash the
160 process (assuming the JVM has no bugs). Safety is an interesting
161 property that requires a combination of language design, runtime
162 support, and often operating system support.
164 It is certainly possible to implement a safe language in LLVM, but LLVM
165 IR does not itself guarantee safety. The LLVM IR allows unsafe pointer
166 casts, use after free bugs, buffer over-runs, and a variety of other
167 problems. Safety needs to be implemented as a layer on top of LLVM and,
168 conveniently, several groups have investigated this. Ask on the `LLVM
169 forums <https://discourse.llvm.org>`_ if you are interested in more details.
171 Language-Specific Optimizations
172 -------------------------------
174 One thing about LLVM that turns off many people is that it does not
175 solve all the world's problems in one system.  One specific
176 complaint is that people perceive LLVM as being incapable of performing
177 high-level language-specific optimization: LLVM "loses too much
178 information".  Here are a few observations about this:
180 First, you're right that LLVM does lose information. For example, as of
181 this writing, there is no way to distinguish in the LLVM IR whether an
182 SSA-value came from a C "int" or a C "long" on an ILP32 machine (other
183 than debug info). Both get compiled down to an 'i32' value and the
184 information about what it came from is lost. The more general issue
185 here, is that the LLVM type system uses "structural equivalence" instead
186 of "name equivalence". Another place this surprises people is if you
187 have two types in a high-level language that have the same structure
188 (e.g. two different structs that have a single int field): these types
189 will compile down into a single LLVM type and it will be impossible to
190 tell what it came from.
192 Second, while LLVM does lose information, LLVM is not a fixed target: we
193 continue to enhance and improve it in many different ways. In addition
194 to adding new features (LLVM did not always support exceptions or debug
195 info), we also extend the IR to capture important information for
196 optimization (e.g. whether an argument is sign or zero extended,
197 information about pointers aliasing, etc). Many of the enhancements are
198 user-driven: people want LLVM to include some specific feature, so they
199 go ahead and extend it.
201 Third, it is *possible and easy* to add language-specific optimizations,
202 and you have a number of choices in how to do it. As one trivial
203 example, it is easy to add language-specific optimization passes that
204 "know" things about code compiled for a language. In the case of the C
205 family, there is an optimization pass that "knows" about the standard C
206 library functions. If you call "exit(0)" in main(), it knows that it is
207 safe to optimize that into "return 0;" because C specifies what the
208 'exit' function does.
210 In addition to simple library knowledge, it is possible to embed a
211 variety of other language-specific information into the LLVM IR. If you
212 have a specific need and run into a wall, please bring the topic up on
213 the llvm-dev list. At the very worst, you can always treat LLVM as if it
214 were a "dumb code generator" and implement the high-level optimizations
215 you desire in your front-end, on the language-specific AST.
217 Tips and Tricks
218 ===============
220 There is a variety of useful tips and tricks that you come to know after
221 working on/with LLVM that aren't obvious at first glance. Instead of
222 letting everyone rediscover them, this section talks about some of these
223 issues.
225 Implementing portable offsetof/sizeof
226 -------------------------------------
228 One interesting thing that comes up, if you are trying to keep the code
229 generated by your compiler "target independent", is that you often need
230 to know the size of some LLVM type or the offset of some field in an
231 llvm structure. For example, you might need to pass the size of a type
232 into a function that allocates memory.
234 Unfortunately, this can vary widely across targets: for example the
235 width of a pointer is trivially target-specific. However, there is a
236 `clever way to use the getelementptr
237 instruction <http://nondot.org/sabre/LLVMNotes/SizeOf-OffsetOf-VariableSizedStructs.txt>`_
238 that allows you to compute this in a portable way.
240 Garbage Collected Stack Frames
241 ------------------------------
243 Some languages want to explicitly manage their stack frames, often so
244 that they are garbage collected or to allow easy implementation of
245 closures. There are often better ways to implement these features than
246 explicit stack frames, but `LLVM does support
247 them, <http://nondot.org/sabre/LLVMNotes/ExplicitlyManagedStackFrames.txt>`_
248 if you want. It requires your front-end to convert the code into
249 `Continuation Passing
250 Style <http://en.wikipedia.org/wiki/Continuation-passing_style>`_ and
251 the use of tail calls (which LLVM also supports).