Chris Lattner | c0b42e9 | 2007-10-23 06:27:55 +0000 | [diff] [blame] | 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: Adding JIT and Optimizer Support</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 | <div class="doc_title">Kaleidoscope: Adding JIT and Optimizer Support</div> |
| 15 | |
Chris Lattner | 128eb86 | 2007-11-05 19:06:59 +0000 | [diff] [blame] | 16 | <ul> |
Chris Lattner | 0e555b1 | 2007-11-05 20:04:56 +0000 | [diff] [blame] | 17 | <li><a href="index.html">Up to Tutorial Index</a></li> |
Chris Lattner | 128eb86 | 2007-11-05 19:06:59 +0000 | [diff] [blame] | 18 | <li>Chapter 4 |
| 19 | <ol> |
| 20 | <li><a href="#intro">Chapter 4 Introduction</a></li> |
| 21 | <li><a href="#trivialconstfold">Trivial Constant Folding</a></li> |
| 22 | <li><a href="#optimizerpasses">LLVM Optimization Passes</a></li> |
| 23 | <li><a href="#jit">Adding a JIT Compiler</a></li> |
| 24 | <li><a href="#code">Full Code Listing</a></li> |
| 25 | </ol> |
| 26 | </li> |
Chris Lattner | 0e555b1 | 2007-11-05 20:04:56 +0000 | [diff] [blame] | 27 | <li><a href="LangImpl5.html">Chapter 5</a>: Extending the Language: Control |
| 28 | Flow</li> |
Chris Lattner | 128eb86 | 2007-11-05 19:06:59 +0000 | [diff] [blame] | 29 | </ul> |
| 30 | |
Chris Lattner | c0b42e9 | 2007-10-23 06:27:55 +0000 | [diff] [blame] | 31 | <div class="doc_author"> |
| 32 | <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p> |
| 33 | </div> |
| 34 | |
| 35 | <!-- *********************************************************************** --> |
Chris Lattner | 128eb86 | 2007-11-05 19:06:59 +0000 | [diff] [blame] | 36 | <div class="doc_section"><a name="intro">Chapter 4 Introduction</a></div> |
Chris Lattner | c0b42e9 | 2007-10-23 06:27:55 +0000 | [diff] [blame] | 37 | <!-- *********************************************************************** --> |
| 38 | |
| 39 | <div class="doc_text"> |
| 40 | |
Chris Lattner | 128eb86 | 2007-11-05 19:06:59 +0000 | [diff] [blame] | 41 | <p>Welcome to Chapter 4 of the "<a href="index.html">Implementing a language |
Chris Lattner | a54c201 | 2007-11-07 05:28:43 +0000 | [diff] [blame] | 42 | with LLVM</a>" tutorial. Chapters 1-3 described the implementation of a simple |
| 43 | language and added support for generating LLVM IR. This chapter describes |
Chris Lattner | 128eb86 | 2007-11-05 19:06:59 +0000 | [diff] [blame] | 44 | two new techniques: adding optimizer support to your language, and adding JIT |
Chris Lattner | 41fcea3 | 2007-11-13 07:06:30 +0000 | [diff] [blame] | 45 | compiler support. These additions will demonstrate how to get nice, efficient code |
| 46 | for the Kaleidoscope language.</p> |
Chris Lattner | c0b42e9 | 2007-10-23 06:27:55 +0000 | [diff] [blame] | 47 | |
| 48 | </div> |
| 49 | |
| 50 | <!-- *********************************************************************** --> |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 51 | <div class="doc_section"><a name="trivialconstfold">Trivial Constant |
| 52 | Folding</a></div> |
Chris Lattner | c0b42e9 | 2007-10-23 06:27:55 +0000 | [diff] [blame] | 53 | <!-- *********************************************************************** --> |
| 54 | |
| 55 | <div class="doc_text"> |
| 56 | |
| 57 | <p> |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 58 | Our demonstration for Chapter 3 is elegant and easy to extend. Unfortunately, |
Duncan Sands | 89f6d88 | 2008-04-13 06:22:09 +0000 | [diff] [blame] | 59 | it does not produce wonderful code. The IRBuilder, however, does give us |
| 60 | obvious optimizations when compiling simple code:</p> |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 61 | |
| 62 | <div class="doc_code"> |
| 63 | <pre> |
| 64 | ready> <b>def test(x) 1+2+x;</b> |
| 65 | Read function definition: |
| 66 | define double @test(double %x) { |
| 67 | entry: |
| 68 | %addtmp = add double 3.000000e+00, %x |
| 69 | ret double %addtmp |
| 70 | } |
| 71 | </pre> |
| 72 | </div> |
| 73 | |
Duncan Sands | 89f6d88 | 2008-04-13 06:22:09 +0000 | [diff] [blame] | 74 | <p>This code is not a literal transcription of the AST built by parsing the |
| 75 | input. That would be: |
| 76 | |
| 77 | <div class="doc_code"> |
| 78 | <pre> |
| 79 | ready> <b>def test(x) 1+2+x;</b> |
| 80 | Read function definition: |
| 81 | define double @test(double %x) { |
| 82 | entry: |
| 83 | %addtmp = add double 2.000000e+00, 1.000000e+00 |
| 84 | %addtmp1 = add double %addtmp, %x |
| 85 | ret double %addtmp1 |
| 86 | } |
| 87 | </pre> |
| 88 | </div> |
| 89 | |
Gabor Greif | 94244f3 | 2009-03-11 20:04:08 +0000 | [diff] [blame] | 90 | <p>Constant folding, as seen above, in particular, is a very common and very |
Duncan Sands | 89f6d88 | 2008-04-13 06:22:09 +0000 | [diff] [blame] | 91 | important optimization: so much so that many language implementors implement |
| 92 | constant folding support in their AST representation.</p> |
| 93 | |
| 94 | <p>With LLVM, you don't need this support in the AST. Since all calls to build |
| 95 | LLVM IR go through the LLVM IR builder, the builder itself checked to see if |
| 96 | there was a constant folding opportunity when you call it. If so, it just does |
| 97 | the constant fold and return the constant instead of creating an instruction. |
| 98 | |
Chris Lattner | a54c201 | 2007-11-07 05:28:43 +0000 | [diff] [blame] | 99 | <p>Well, that was easy :). In practice, we recommend always using |
Duncan Sands | 89f6d88 | 2008-04-13 06:22:09 +0000 | [diff] [blame] | 100 | <tt>IRBuilder</tt> when generating code like this. It has no |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 101 | "syntactic overhead" for its use (you don't have to uglify your compiler with |
| 102 | constant checks everywhere) and it can dramatically reduce the amount of |
| 103 | LLVM IR that is generated in some cases (particular for languages with a macro |
| 104 | preprocessor or that use a lot of constants).</p> |
| 105 | |
Duncan Sands | 89f6d88 | 2008-04-13 06:22:09 +0000 | [diff] [blame] | 106 | <p>On the other hand, the <tt>IRBuilder</tt> is limited by the fact |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 107 | that it does all of its analysis inline with the code as it is built. If you |
| 108 | take a slightly more complex example:</p> |
| 109 | |
| 110 | <div class="doc_code"> |
| 111 | <pre> |
| 112 | ready> <b>def test(x) (1+2+x)*(x+(1+2));</b> |
| 113 | ready> Read function definition: |
| 114 | define double @test(double %x) { |
| 115 | entry: |
| 116 | %addtmp = add double 3.000000e+00, %x |
| 117 | %addtmp1 = add double %x, 3.000000e+00 |
| 118 | %multmp = mul double %addtmp, %addtmp1 |
| 119 | ret double %multmp |
| 120 | } |
| 121 | </pre> |
| 122 | </div> |
| 123 | |
| 124 | <p>In this case, the LHS and RHS of the multiplication are the same value. We'd |
| 125 | really like to see this generate "<tt>tmp = x+3; result = tmp*tmp;</tt>" instead |
Chris Lattner | 1ace67c | 2008-04-15 16:59:22 +0000 | [diff] [blame] | 126 | of computing "<tt>x+3</tt>" twice.</p> |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 127 | |
| 128 | <p>Unfortunately, no amount of local analysis will be able to detect and correct |
| 129 | this. This requires two transformations: reassociation of expressions (to |
| 130 | make the add's lexically identical) and Common Subexpression Elimination (CSE) |
| 131 | to delete the redundant add instruction. Fortunately, LLVM provides a broad |
| 132 | range of optimizations that you can use, in the form of "passes".</p> |
| 133 | |
| 134 | </div> |
| 135 | |
| 136 | <!-- *********************************************************************** --> |
| 137 | <div class="doc_section"><a name="optimizerpasses">LLVM Optimization |
| 138 | Passes</a></div> |
| 139 | <!-- *********************************************************************** --> |
| 140 | |
| 141 | <div class="doc_text"> |
| 142 | |
Chris Lattner | 41fcea3 | 2007-11-13 07:06:30 +0000 | [diff] [blame] | 143 | <p>LLVM provides many optimization passes, which do many different sorts of |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 144 | things and have different tradeoffs. Unlike other systems, LLVM doesn't hold |
| 145 | to the mistaken notion that one set of optimizations is right for all languages |
| 146 | and for all situations. LLVM allows a compiler implementor to make complete |
| 147 | decisions about what optimizations to use, in which order, and in what |
| 148 | situation.</p> |
| 149 | |
| 150 | <p>As a concrete example, LLVM supports both "whole module" passes, which look |
| 151 | across as large of body of code as they can (often a whole file, but if run |
| 152 | at link time, this can be a substantial portion of the whole program). It also |
| 153 | supports and includes "per-function" passes which just operate on a single |
| 154 | function at a time, without looking at other functions. For more information |
Chris Lattner | 41fcea3 | 2007-11-13 07:06:30 +0000 | [diff] [blame] | 155 | on passes and how they are run, see the <a href="../WritingAnLLVMPass.html">How |
Chris Lattner | a54c201 | 2007-11-07 05:28:43 +0000 | [diff] [blame] | 156 | to Write a Pass</a> document and the <a href="../Passes.html">List of LLVM |
| 157 | Passes</a>.</p> |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 158 | |
| 159 | <p>For Kaleidoscope, we are currently generating functions on the fly, one at |
| 160 | a time, as the user types them in. We aren't shooting for the ultimate |
| 161 | optimization experience in this setting, but we also want to catch the easy and |
| 162 | quick stuff where possible. As such, we will choose to run a few per-function |
| 163 | optimizations as the user types the function in. If we wanted to make a "static |
| 164 | Kaleidoscope compiler", we would use exactly the code we have now, except that |
| 165 | we would defer running the optimizer until the entire file has been parsed.</p> |
| 166 | |
| 167 | <p>In order to get per-function optimizations going, we need to set up a |
| 168 | <a href="../WritingAnLLVMPass.html#passmanager">FunctionPassManager</a> to hold and |
| 169 | organize the LLVM optimizations that we want to run. Once we have that, we can |
| 170 | add a set of optimizations to run. The code looks like this:</p> |
| 171 | |
| 172 | <div class="doc_code"> |
| 173 | <pre> |
Jeffrey Yasskin | f0356fe | 2010-01-27 20:34:15 +0000 | [diff] [blame^] | 174 | FunctionPassManager OurFPM(TheModule); |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 175 | |
Reid Kleckner | 60130f0 | 2009-08-26 20:58:25 +0000 | [diff] [blame] | 176 | // Set up the optimizer pipeline. Start with registering info about how the |
| 177 | // target lays out data structures. |
| 178 | OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData())); |
| 179 | // Do simple "peephole" optimizations and bit-twiddling optzns. |
| 180 | OurFPM.add(createInstructionCombiningPass()); |
| 181 | // Reassociate expressions. |
| 182 | OurFPM.add(createReassociatePass()); |
| 183 | // Eliminate Common SubExpressions. |
| 184 | OurFPM.add(createGVNPass()); |
| 185 | // Simplify the control flow graph (deleting unreachable blocks, etc). |
| 186 | OurFPM.add(createCFGSimplificationPass()); |
| 187 | |
Nick Lewycky | 422094c | 2009-09-13 21:38:54 +0000 | [diff] [blame] | 188 | OurFPM.doInitialization(); |
| 189 | |
Reid Kleckner | 60130f0 | 2009-08-26 20:58:25 +0000 | [diff] [blame] | 190 | // Set the global so the code gen can use this. |
| 191 | TheFPM = &OurFPM; |
| 192 | |
| 193 | // Run the main "interpreter loop" now. |
| 194 | MainLoop(); |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 195 | </pre> |
| 196 | </div> |
| 197 | |
Jeffrey Yasskin | f0356fe | 2010-01-27 20:34:15 +0000 | [diff] [blame^] | 198 | <p>This code defines a <tt>FunctionPassManager</tt>, "<tt>OurFPM</tt>". It |
| 199 | requires a pointer to the <tt>Module</tt> to construct itself. Once it is set |
| 200 | up, we use a series of "add" calls to add a bunch of LLVM passes. The first |
| 201 | pass is basically boilerplate, it adds a pass so that later optimizations know |
| 202 | how the data structures in the program are laid out. The |
| 203 | "<tt>TheExecutionEngine</tt>" variable is related to the JIT, which we will get |
| 204 | to in the next section.</p> |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 205 | |
| 206 | <p>In this case, we choose to add 4 optimization passes. The passes we chose |
| 207 | here are a pretty standard set of "cleanup" optimizations that are useful for |
Chris Lattner | 41fcea3 | 2007-11-13 07:06:30 +0000 | [diff] [blame] | 208 | a wide variety of code. I won't delve into what they do but, believe me, |
Chris Lattner | a54c201 | 2007-11-07 05:28:43 +0000 | [diff] [blame] | 209 | they are a good starting place :).</p> |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 210 | |
Chris Lattner | a54c201 | 2007-11-07 05:28:43 +0000 | [diff] [blame] | 211 | <p>Once the PassManager is set up, we need to make use of it. We do this by |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 212 | running it after our newly created function is constructed (in |
| 213 | <tt>FunctionAST::Codegen</tt>), but before it is returned to the client:</p> |
| 214 | |
| 215 | <div class="doc_code"> |
| 216 | <pre> |
| 217 | if (Value *RetVal = Body->Codegen()) { |
| 218 | // Finish off the function. |
| 219 | Builder.CreateRet(RetVal); |
| 220 | |
| 221 | // Validate the generated code, checking for consistency. |
| 222 | verifyFunction(*TheFunction); |
| 223 | |
Chris Lattner | a54c201 | 2007-11-07 05:28:43 +0000 | [diff] [blame] | 224 | <b>// Optimize the function. |
| 225 | TheFPM->run(*TheFunction);</b> |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 226 | |
| 227 | return TheFunction; |
| 228 | } |
| 229 | </pre> |
| 230 | </div> |
| 231 | |
Chris Lattner | 41fcea3 | 2007-11-13 07:06:30 +0000 | [diff] [blame] | 232 | <p>As you can see, this is pretty straightforward. The |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 233 | <tt>FunctionPassManager</tt> optimizes and updates the LLVM Function* in place, |
| 234 | improving (hopefully) its body. With this in place, we can try our test above |
| 235 | again:</p> |
| 236 | |
| 237 | <div class="doc_code"> |
| 238 | <pre> |
| 239 | ready> <b>def test(x) (1+2+x)*(x+(1+2));</b> |
| 240 | ready> Read function definition: |
| 241 | define double @test(double %x) { |
| 242 | entry: |
| 243 | %addtmp = add double %x, 3.000000e+00 |
| 244 | %multmp = mul double %addtmp, %addtmp |
| 245 | ret double %multmp |
| 246 | } |
| 247 | </pre> |
| 248 | </div> |
| 249 | |
| 250 | <p>As expected, we now get our nicely optimized code, saving a floating point |
Chris Lattner | a54c201 | 2007-11-07 05:28:43 +0000 | [diff] [blame] | 251 | add instruction from every execution of this function.</p> |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 252 | |
| 253 | <p>LLVM provides a wide variety of optimizations that can be used in certain |
Chris Lattner | 7271423 | 2007-10-25 17:52:39 +0000 | [diff] [blame] | 254 | circumstances. Some <a href="../Passes.html">documentation about the various |
| 255 | passes</a> is available, but it isn't very complete. Another good source of |
Chris Lattner | 41fcea3 | 2007-11-13 07:06:30 +0000 | [diff] [blame] | 256 | ideas can come from looking at the passes that <tt>llvm-gcc</tt> or |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 257 | <tt>llvm-ld</tt> run to get started. The "<tt>opt</tt>" tool allows you to |
| 258 | experiment with passes from the command line, so you can see if they do |
| 259 | anything.</p> |
| 260 | |
| 261 | <p>Now that we have reasonable code coming out of our front-end, lets talk about |
| 262 | executing it!</p> |
| 263 | |
| 264 | </div> |
| 265 | |
| 266 | <!-- *********************************************************************** --> |
| 267 | <div class="doc_section"><a name="jit">Adding a JIT Compiler</a></div> |
| 268 | <!-- *********************************************************************** --> |
| 269 | |
| 270 | <div class="doc_text"> |
| 271 | |
Chris Lattner | a54c201 | 2007-11-07 05:28:43 +0000 | [diff] [blame] | 272 | <p>Code that is available in LLVM IR can have a wide variety of tools |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 273 | applied to it. For example, you can run optimizations on it (as we did above), |
| 274 | you can dump it out in textual or binary forms, you can compile the code to an |
| 275 | assembly file (.s) for some target, or you can JIT compile it. The nice thing |
Chris Lattner | a54c201 | 2007-11-07 05:28:43 +0000 | [diff] [blame] | 276 | about the LLVM IR representation is that it is the "common currency" between |
| 277 | many different parts of the compiler. |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 278 | </p> |
| 279 | |
Chris Lattner | a54c201 | 2007-11-07 05:28:43 +0000 | [diff] [blame] | 280 | <p>In this section, we'll add JIT compiler support to our interpreter. The |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 281 | basic idea that we want for Kaleidoscope is to have the user enter function |
| 282 | bodies as they do now, but immediately evaluate the top-level expressions they |
| 283 | type in. For example, if they type in "1 + 2;", we should evaluate and print |
| 284 | out 3. If they define a function, they should be able to call it from the |
| 285 | command line.</p> |
| 286 | |
| 287 | <p>In order to do this, we first declare and initialize the JIT. This is done |
| 288 | by adding a global variable and a call in <tt>main</tt>:</p> |
| 289 | |
| 290 | <div class="doc_code"> |
| 291 | <pre> |
Chris Lattner | a54c201 | 2007-11-07 05:28:43 +0000 | [diff] [blame] | 292 | <b>static ExecutionEngine *TheExecutionEngine;</b> |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 293 | ... |
| 294 | int main() { |
| 295 | .. |
Jeffrey Yasskin | f0356fe | 2010-01-27 20:34:15 +0000 | [diff] [blame^] | 296 | <b>// Create the JIT. This takes ownership of the module. |
| 297 | TheExecutionEngine = EngineBuilder(TheModule).create();</b> |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 298 | .. |
| 299 | } |
| 300 | </pre> |
| 301 | </div> |
| 302 | |
| 303 | <p>This creates an abstract "Execution Engine" which can be either a JIT |
| 304 | compiler or the LLVM interpreter. LLVM will automatically pick a JIT compiler |
| 305 | for you if one is available for your platform, otherwise it will fall back to |
| 306 | the interpreter.</p> |
| 307 | |
| 308 | <p>Once the <tt>ExecutionEngine</tt> is created, the JIT is ready to be used. |
Chris Lattner | 41fcea3 | 2007-11-13 07:06:30 +0000 | [diff] [blame] | 309 | There are a variety of APIs that are useful, but the simplest one is the |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 310 | "<tt>getPointerToFunction(F)</tt>" method. This method JIT compiles the |
| 311 | specified LLVM Function and returns a function pointer to the generated machine |
| 312 | code. In our case, this means that we can change the code that parses a |
| 313 | top-level expression to look like this:</p> |
| 314 | |
| 315 | <div class="doc_code"> |
| 316 | <pre> |
| 317 | static void HandleTopLevelExpression() { |
Erick Tryzelaar | fd1ec5e | 2009-09-22 21:14:49 +0000 | [diff] [blame] | 318 | // Evaluate a top-level expression into an anonymous function. |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 319 | if (FunctionAST *F = ParseTopLevelExpr()) { |
| 320 | if (Function *LF = F->Codegen()) { |
| 321 | LF->dump(); // Dump the function for exposition purposes. |
| 322 | |
Chris Lattner | a54c201 | 2007-11-07 05:28:43 +0000 | [diff] [blame] | 323 | <b>// JIT the function, returning a function pointer. |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 324 | void *FPtr = TheExecutionEngine->getPointerToFunction(LF); |
| 325 | |
| 326 | // Cast it to the right type (takes no arguments, returns a double) so we |
| 327 | // can call it as a native function. |
Erick Tryzelaar | fd1ec5e | 2009-09-22 21:14:49 +0000 | [diff] [blame] | 328 | double (*FP)() = (double (*)())(intptr_t)FPtr; |
Chris Lattner | a54c201 | 2007-11-07 05:28:43 +0000 | [diff] [blame] | 329 | fprintf(stderr, "Evaluated to %f\n", FP());</b> |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 330 | } |
| 331 | </pre> |
| 332 | </div> |
| 333 | |
| 334 | <p>Recall that we compile top-level expressions into a self-contained LLVM |
| 335 | function that takes no arguments and returns the computed double. Because the |
| 336 | LLVM JIT compiler matches the native platform ABI, this means that you can just |
| 337 | cast the result pointer to a function pointer of that type and call it directly. |
Chris Lattner | 41fcea3 | 2007-11-13 07:06:30 +0000 | [diff] [blame] | 338 | This means, there is no difference between JIT compiled code and native machine |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 339 | code that is statically linked into your application.</p> |
| 340 | |
| 341 | <p>With just these two changes, lets see how Kaleidoscope works now!</p> |
| 342 | |
| 343 | <div class="doc_code"> |
| 344 | <pre> |
| 345 | ready> <b>4+5;</b> |
| 346 | define double @""() { |
| 347 | entry: |
| 348 | ret double 9.000000e+00 |
| 349 | } |
| 350 | |
| 351 | <em>Evaluated to 9.000000</em> |
| 352 | </pre> |
| 353 | </div> |
| 354 | |
| 355 | <p>Well this looks like it is basically working. The dump of the function |
| 356 | shows the "no argument function that always returns double" that we synthesize |
Erick Tryzelaar | fd1ec5e | 2009-09-22 21:14:49 +0000 | [diff] [blame] | 357 | for each top-level expression that is typed in. This demonstrates very basic |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 358 | functionality, but can we do more?</p> |
| 359 | |
| 360 | <div class="doc_code"> |
| 361 | <pre> |
Chris Lattner | 2e89f3a | 2007-10-31 07:30:39 +0000 | [diff] [blame] | 362 | ready> <b>def testfunc(x y) x + y*2; </b> |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 363 | Read function definition: |
| 364 | define double @testfunc(double %x, double %y) { |
| 365 | entry: |
| 366 | %multmp = mul double %y, 2.000000e+00 |
| 367 | %addtmp = add double %multmp, %x |
| 368 | ret double %addtmp |
| 369 | } |
| 370 | |
| 371 | ready> <b>testfunc(4, 10);</b> |
| 372 | define double @""() { |
| 373 | entry: |
| 374 | %calltmp = call double @testfunc( double 4.000000e+00, double 1.000000e+01 ) |
| 375 | ret double %calltmp |
| 376 | } |
| 377 | |
| 378 | <em>Evaluated to 24.000000</em> |
| 379 | </pre> |
| 380 | </div> |
| 381 | |
Jeffrey Yasskin | dc85724 | 2009-10-27 20:30:28 +0000 | [diff] [blame] | 382 | <p>This illustrates that we can now call user code, but there is something a bit |
| 383 | subtle going on here. Note that we only invoke the JIT on the anonymous |
| 384 | functions that <em>call testfunc</em>, but we never invoked it |
| 385 | on <em>testfunc</em> itself. What actually happened here is that the JIT |
| 386 | scanned for all non-JIT'd functions transitively called from the anonymous |
| 387 | function and compiled all of them before returning |
| 388 | from <tt>getPointerToFunction()</tt>.</p> |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 389 | |
Jeffrey Yasskin | dc85724 | 2009-10-27 20:30:28 +0000 | [diff] [blame] | 390 | <p>The JIT provides a number of other more advanced interfaces for things like |
| 391 | freeing allocated machine code, rejit'ing functions to update them, etc. |
| 392 | However, even with this simple code, we get some surprisingly powerful |
| 393 | capabilities - check this out (I removed the dump of the anonymous functions, |
| 394 | you should get the idea by now :) :</p> |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 395 | |
| 396 | <div class="doc_code"> |
| 397 | <pre> |
| 398 | ready> <b>extern sin(x);</b> |
| 399 | Read extern: |
| 400 | declare double @sin(double) |
| 401 | |
| 402 | ready> <b>extern cos(x);</b> |
| 403 | Read extern: |
| 404 | declare double @cos(double) |
| 405 | |
| 406 | ready> <b>sin(1.0);</b> |
| 407 | <em>Evaluated to 0.841471</em> |
Chris Lattner | 7271423 | 2007-10-25 17:52:39 +0000 | [diff] [blame] | 408 | |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 409 | ready> <b>def foo(x) sin(x)*sin(x) + cos(x)*cos(x);</b> |
| 410 | Read function definition: |
| 411 | define double @foo(double %x) { |
| 412 | entry: |
| 413 | %calltmp = call double @sin( double %x ) |
| 414 | %multmp = mul double %calltmp, %calltmp |
| 415 | %calltmp2 = call double @cos( double %x ) |
| 416 | %multmp4 = mul double %calltmp2, %calltmp2 |
| 417 | %addtmp = add double %multmp, %multmp4 |
| 418 | ret double %addtmp |
| 419 | } |
| 420 | |
| 421 | ready> <b>foo(4.0);</b> |
| 422 | <em>Evaluated to 1.000000</em> |
| 423 | </pre> |
| 424 | </div> |
| 425 | |
Chris Lattner | a54c201 | 2007-11-07 05:28:43 +0000 | [diff] [blame] | 426 | <p>Whoa, how does the JIT know about sin and cos? The answer is surprisingly |
| 427 | simple: in this |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 428 | example, the JIT started execution of a function and got to a function call. It |
| 429 | realized that the function was not yet JIT compiled and invoked the standard set |
| 430 | of routines to resolve the function. In this case, there is no body defined |
Chris Lattner | a54c201 | 2007-11-07 05:28:43 +0000 | [diff] [blame] | 431 | for the function, so the JIT ended up calling "<tt>dlsym("sin")</tt>" on the |
| 432 | Kaleidoscope process itself. |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 433 | Since "<tt>sin</tt>" is defined within the JIT's address space, it simply |
| 434 | patches up calls in the module to call the libm version of <tt>sin</tt> |
| 435 | directly.</p> |
| 436 | |
| 437 | <p>The LLVM JIT provides a number of interfaces (look in the |
| 438 | <tt>ExecutionEngine.h</tt> file) for controlling how unknown functions get |
| 439 | resolved. It allows you to establish explicit mappings between IR objects and |
| 440 | addresses (useful for LLVM global variables that you want to map to static |
| 441 | tables, for example), allows you to dynamically decide on the fly based on the |
Jeffrey Yasskin | dc85724 | 2009-10-27 20:30:28 +0000 | [diff] [blame] | 442 | function name, and even allows you to have the JIT compile functions lazily the |
| 443 | first time they're called.</p> |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 444 | |
Chris Lattner | 7271423 | 2007-10-25 17:52:39 +0000 | [diff] [blame] | 445 | <p>One interesting application of this is that we can now extend the language |
| 446 | by writing arbitrary C++ code to implement operations. For example, if we add: |
| 447 | </p> |
| 448 | |
| 449 | <div class="doc_code"> |
| 450 | <pre> |
| 451 | /// putchard - putchar that takes a double and returns 0. |
| 452 | extern "C" |
| 453 | double putchard(double X) { |
| 454 | putchar((char)X); |
| 455 | return 0; |
| 456 | } |
| 457 | </pre> |
| 458 | </div> |
| 459 | |
| 460 | <p>Now we can produce simple output to the console by using things like: |
| 461 | "<tt>extern putchard(x); putchard(120);</tt>", which prints a lowercase 'x' on |
Chris Lattner | a54c201 | 2007-11-07 05:28:43 +0000 | [diff] [blame] | 462 | the console (120 is the ASCII code for 'x'). Similar code could be used to |
Chris Lattner | 7271423 | 2007-10-25 17:52:39 +0000 | [diff] [blame] | 463 | implement file I/O, console input, and many other capabilities in |
| 464 | Kaleidoscope.</p> |
| 465 | |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 466 | <p>This completes the JIT and optimizer chapter of the Kaleidoscope tutorial. At |
| 467 | this point, we can compile a non-Turing-complete programming language, optimize |
| 468 | and JIT compile it in a user-driven way. Next up we'll look into <a |
| 469 | href="LangImpl5.html">extending the language with control flow constructs</a>, |
| 470 | tackling some interesting LLVM IR issues along the way.</p> |
| 471 | |
| 472 | </div> |
| 473 | |
| 474 | <!-- *********************************************************************** --> |
| 475 | <div class="doc_section"><a name="code">Full Code Listing</a></div> |
| 476 | <!-- *********************************************************************** --> |
| 477 | |
| 478 | <div class="doc_text"> |
| 479 | |
| 480 | <p> |
| 481 | Here is the complete code listing for our running example, enhanced with the |
| 482 | LLVM JIT and optimizer. To build this example, use: |
| 483 | </p> |
| 484 | |
| 485 | <div class="doc_code"> |
| 486 | <pre> |
| 487 | # Compile |
Erick Tryzelaar | fd1ec5e | 2009-09-22 21:14:49 +0000 | [diff] [blame] | 488 | g++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit interpreter native` -O3 -o toy |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 489 | # Run |
| 490 | ./toy |
| 491 | </pre> |
| 492 | </div> |
| 493 | |
Chris Lattner | 7c77089 | 2009-02-09 00:04:40 +0000 | [diff] [blame] | 494 | <p> |
| 495 | If you are compiling this on Linux, make sure to add the "-rdynamic" option |
| 496 | as well. This makes sure that the external functions are resolved properly |
| 497 | at runtime.</p> |
| 498 | |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 499 | <p>Here is the code:</p> |
| 500 | |
| 501 | <div class="doc_code"> |
| 502 | <pre> |
| 503 | #include "llvm/DerivedTypes.h" |
| 504 | #include "llvm/ExecutionEngine/ExecutionEngine.h" |
Nick Lewycky | 422094c | 2009-09-13 21:38:54 +0000 | [diff] [blame] | 505 | #include "llvm/ExecutionEngine/Interpreter.h" |
| 506 | #include "llvm/ExecutionEngine/JIT.h" |
Owen Anderson | d1fbd14 | 2009-07-08 20:50:47 +0000 | [diff] [blame] | 507 | #include "llvm/LLVMContext.h" |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 508 | #include "llvm/Module.h" |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 509 | #include "llvm/PassManager.h" |
| 510 | #include "llvm/Analysis/Verifier.h" |
| 511 | #include "llvm/Target/TargetData.h" |
Nick Lewycky | 422094c | 2009-09-13 21:38:54 +0000 | [diff] [blame] | 512 | #include "llvm/Target/TargetSelect.h" |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 513 | #include "llvm/Transforms/Scalar.h" |
Duncan Sands | 89f6d88 | 2008-04-13 06:22:09 +0000 | [diff] [blame] | 514 | #include "llvm/Support/IRBuilder.h" |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 515 | #include <cstdio> |
| 516 | #include <string> |
| 517 | #include <map> |
| 518 | #include <vector> |
| 519 | using namespace llvm; |
| 520 | |
| 521 | //===----------------------------------------------------------------------===// |
| 522 | // Lexer |
| 523 | //===----------------------------------------------------------------------===// |
| 524 | |
| 525 | // The lexer returns tokens [0-255] if it is an unknown character, otherwise one |
| 526 | // of these for known things. |
| 527 | enum Token { |
| 528 | tok_eof = -1, |
| 529 | |
| 530 | // commands |
| 531 | tok_def = -2, tok_extern = -3, |
| 532 | |
| 533 | // primary |
Erick Tryzelaar | fd1ec5e | 2009-09-22 21:14:49 +0000 | [diff] [blame] | 534 | tok_identifier = -4, tok_number = -5 |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 535 | }; |
| 536 | |
| 537 | static std::string IdentifierStr; // Filled in if tok_identifier |
| 538 | static double NumVal; // Filled in if tok_number |
| 539 | |
| 540 | /// gettok - Return the next token from standard input. |
| 541 | static int gettok() { |
| 542 | static int LastChar = ' '; |
| 543 | |
| 544 | // Skip any whitespace. |
| 545 | while (isspace(LastChar)) |
| 546 | LastChar = getchar(); |
| 547 | |
| 548 | if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]* |
| 549 | IdentifierStr = LastChar; |
| 550 | while (isalnum((LastChar = getchar()))) |
| 551 | IdentifierStr += LastChar; |
| 552 | |
| 553 | if (IdentifierStr == "def") return tok_def; |
| 554 | if (IdentifierStr == "extern") return tok_extern; |
| 555 | return tok_identifier; |
| 556 | } |
| 557 | |
| 558 | if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+ |
| 559 | std::string NumStr; |
| 560 | do { |
| 561 | NumStr += LastChar; |
| 562 | LastChar = getchar(); |
| 563 | } while (isdigit(LastChar) || LastChar == '.'); |
| 564 | |
| 565 | NumVal = strtod(NumStr.c_str(), 0); |
| 566 | return tok_number; |
| 567 | } |
| 568 | |
| 569 | if (LastChar == '#') { |
| 570 | // Comment until end of line. |
| 571 | do LastChar = getchar(); |
Chris Lattner | c80c23f | 2007-12-02 22:46:01 +0000 | [diff] [blame] | 572 | while (LastChar != EOF && LastChar != '\n' && LastChar != '\r'); |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 573 | |
| 574 | if (LastChar != EOF) |
| 575 | return gettok(); |
| 576 | } |
| 577 | |
| 578 | // Check for end of file. Don't eat the EOF. |
| 579 | if (LastChar == EOF) |
| 580 | return tok_eof; |
| 581 | |
| 582 | // Otherwise, just return the character as its ascii value. |
| 583 | int ThisChar = LastChar; |
| 584 | LastChar = getchar(); |
| 585 | return ThisChar; |
| 586 | } |
| 587 | |
| 588 | //===----------------------------------------------------------------------===// |
| 589 | // Abstract Syntax Tree (aka Parse Tree) |
| 590 | //===----------------------------------------------------------------------===// |
| 591 | |
Chris Lattner | c0b42e9 | 2007-10-23 06:27:55 +0000 | [diff] [blame] | 592 | /// ExprAST - Base class for all expression nodes. |
| 593 | class ExprAST { |
| 594 | public: |
| 595 | virtual ~ExprAST() {} |
| 596 | virtual Value *Codegen() = 0; |
| 597 | }; |
| 598 | |
| 599 | /// NumberExprAST - Expression class for numeric literals like "1.0". |
| 600 | class NumberExprAST : public ExprAST { |
| 601 | double Val; |
| 602 | public: |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 603 | NumberExprAST(double val) : Val(val) {} |
Chris Lattner | c0b42e9 | 2007-10-23 06:27:55 +0000 | [diff] [blame] | 604 | virtual Value *Codegen(); |
| 605 | }; |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 606 | |
| 607 | /// VariableExprAST - Expression class for referencing a variable, like "a". |
| 608 | class VariableExprAST : public ExprAST { |
| 609 | std::string Name; |
| 610 | public: |
| 611 | VariableExprAST(const std::string &name) : Name(name) {} |
| 612 | virtual Value *Codegen(); |
| 613 | }; |
| 614 | |
| 615 | /// BinaryExprAST - Expression class for a binary operator. |
| 616 | class BinaryExprAST : public ExprAST { |
| 617 | char Op; |
| 618 | ExprAST *LHS, *RHS; |
| 619 | public: |
| 620 | BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs) |
| 621 | : Op(op), LHS(lhs), RHS(rhs) {} |
| 622 | virtual Value *Codegen(); |
| 623 | }; |
| 624 | |
| 625 | /// CallExprAST - Expression class for function calls. |
| 626 | class CallExprAST : public ExprAST { |
| 627 | std::string Callee; |
| 628 | std::vector<ExprAST*> Args; |
| 629 | public: |
| 630 | CallExprAST(const std::string &callee, std::vector<ExprAST*> &args) |
| 631 | : Callee(callee), Args(args) {} |
| 632 | virtual Value *Codegen(); |
| 633 | }; |
| 634 | |
| 635 | /// PrototypeAST - This class represents the "prototype" for a function, |
Erick Tryzelaar | fd1ec5e | 2009-09-22 21:14:49 +0000 | [diff] [blame] | 636 | /// which captures its name, and its argument names (thus implicitly the number |
| 637 | /// of arguments the function takes). |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 638 | class PrototypeAST { |
| 639 | std::string Name; |
| 640 | std::vector<std::string> Args; |
| 641 | public: |
| 642 | PrototypeAST(const std::string &name, const std::vector<std::string> &args) |
| 643 | : Name(name), Args(args) {} |
| 644 | |
| 645 | Function *Codegen(); |
| 646 | }; |
| 647 | |
| 648 | /// FunctionAST - This class represents a function definition itself. |
| 649 | class FunctionAST { |
| 650 | PrototypeAST *Proto; |
| 651 | ExprAST *Body; |
| 652 | public: |
| 653 | FunctionAST(PrototypeAST *proto, ExprAST *body) |
| 654 | : Proto(proto), Body(body) {} |
| 655 | |
| 656 | Function *Codegen(); |
| 657 | }; |
| 658 | |
| 659 | //===----------------------------------------------------------------------===// |
| 660 | // Parser |
| 661 | //===----------------------------------------------------------------------===// |
| 662 | |
| 663 | /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current |
Erick Tryzelaar | fd1ec5e | 2009-09-22 21:14:49 +0000 | [diff] [blame] | 664 | /// token the parser is looking at. getNextToken reads another token from the |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 665 | /// lexer and updates CurTok with its results. |
| 666 | static int CurTok; |
| 667 | static int getNextToken() { |
| 668 | return CurTok = gettok(); |
| 669 | } |
| 670 | |
| 671 | /// BinopPrecedence - This holds the precedence for each binary operator that is |
| 672 | /// defined. |
| 673 | static std::map<char, int> BinopPrecedence; |
| 674 | |
| 675 | /// GetTokPrecedence - Get the precedence of the pending binary operator token. |
| 676 | static int GetTokPrecedence() { |
| 677 | if (!isascii(CurTok)) |
| 678 | return -1; |
| 679 | |
| 680 | // Make sure it's a declared binop. |
| 681 | int TokPrec = BinopPrecedence[CurTok]; |
| 682 | if (TokPrec <= 0) return -1; |
| 683 | return TokPrec; |
| 684 | } |
| 685 | |
| 686 | /// Error* - These are little helper functions for error handling. |
| 687 | ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;} |
| 688 | PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; } |
| 689 | FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; } |
| 690 | |
| 691 | static ExprAST *ParseExpression(); |
| 692 | |
| 693 | /// identifierexpr |
Chris Lattner | 20a0c80 | 2007-11-05 17:54:34 +0000 | [diff] [blame] | 694 | /// ::= identifier |
| 695 | /// ::= identifier '(' expression* ')' |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 696 | static ExprAST *ParseIdentifierExpr() { |
| 697 | std::string IdName = IdentifierStr; |
| 698 | |
Chris Lattner | 20a0c80 | 2007-11-05 17:54:34 +0000 | [diff] [blame] | 699 | getNextToken(); // eat identifier. |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 700 | |
| 701 | if (CurTok != '(') // Simple variable ref. |
| 702 | return new VariableExprAST(IdName); |
| 703 | |
| 704 | // Call. |
| 705 | getNextToken(); // eat ( |
| 706 | std::vector<ExprAST*> Args; |
Chris Lattner | 7115521 | 2007-11-06 01:39:12 +0000 | [diff] [blame] | 707 | if (CurTok != ')') { |
| 708 | while (1) { |
| 709 | ExprAST *Arg = ParseExpression(); |
| 710 | if (!Arg) return 0; |
| 711 | Args.push_back(Arg); |
Erick Tryzelaar | fd1ec5e | 2009-09-22 21:14:49 +0000 | [diff] [blame] | 712 | |
Chris Lattner | 7115521 | 2007-11-06 01:39:12 +0000 | [diff] [blame] | 713 | if (CurTok == ')') break; |
Erick Tryzelaar | fd1ec5e | 2009-09-22 21:14:49 +0000 | [diff] [blame] | 714 | |
Chris Lattner | 7115521 | 2007-11-06 01:39:12 +0000 | [diff] [blame] | 715 | if (CurTok != ',') |
Chris Lattner | 6c4be9c | 2008-04-14 16:44:41 +0000 | [diff] [blame] | 716 | return Error("Expected ')' or ',' in argument list"); |
Chris Lattner | 7115521 | 2007-11-06 01:39:12 +0000 | [diff] [blame] | 717 | getNextToken(); |
| 718 | } |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 719 | } |
| 720 | |
| 721 | // Eat the ')'. |
| 722 | getNextToken(); |
| 723 | |
| 724 | return new CallExprAST(IdName, Args); |
| 725 | } |
| 726 | |
| 727 | /// numberexpr ::= number |
| 728 | static ExprAST *ParseNumberExpr() { |
| 729 | ExprAST *Result = new NumberExprAST(NumVal); |
| 730 | getNextToken(); // consume the number |
| 731 | return Result; |
| 732 | } |
| 733 | |
| 734 | /// parenexpr ::= '(' expression ')' |
| 735 | static ExprAST *ParseParenExpr() { |
| 736 | getNextToken(); // eat (. |
| 737 | ExprAST *V = ParseExpression(); |
| 738 | if (!V) return 0; |
| 739 | |
| 740 | if (CurTok != ')') |
| 741 | return Error("expected ')'"); |
| 742 | getNextToken(); // eat ). |
| 743 | return V; |
| 744 | } |
| 745 | |
| 746 | /// primary |
| 747 | /// ::= identifierexpr |
| 748 | /// ::= numberexpr |
| 749 | /// ::= parenexpr |
| 750 | static ExprAST *ParsePrimary() { |
| 751 | switch (CurTok) { |
| 752 | default: return Error("unknown token when expecting an expression"); |
| 753 | case tok_identifier: return ParseIdentifierExpr(); |
| 754 | case tok_number: return ParseNumberExpr(); |
| 755 | case '(': return ParseParenExpr(); |
| 756 | } |
| 757 | } |
| 758 | |
| 759 | /// binoprhs |
| 760 | /// ::= ('+' primary)* |
| 761 | static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) { |
| 762 | // If this is a binop, find its precedence. |
| 763 | while (1) { |
| 764 | int TokPrec = GetTokPrecedence(); |
| 765 | |
| 766 | // If this is a binop that binds at least as tightly as the current binop, |
| 767 | // consume it, otherwise we are done. |
| 768 | if (TokPrec < ExprPrec) |
| 769 | return LHS; |
| 770 | |
| 771 | // Okay, we know this is a binop. |
| 772 | int BinOp = CurTok; |
| 773 | getNextToken(); // eat binop |
| 774 | |
| 775 | // Parse the primary expression after the binary operator. |
| 776 | ExprAST *RHS = ParsePrimary(); |
| 777 | if (!RHS) return 0; |
| 778 | |
| 779 | // If BinOp binds less tightly with RHS than the operator after RHS, let |
| 780 | // the pending operator take RHS as its LHS. |
| 781 | int NextPrec = GetTokPrecedence(); |
| 782 | if (TokPrec < NextPrec) { |
| 783 | RHS = ParseBinOpRHS(TokPrec+1, RHS); |
| 784 | if (RHS == 0) return 0; |
| 785 | } |
| 786 | |
| 787 | // Merge LHS/RHS. |
| 788 | LHS = new BinaryExprAST(BinOp, LHS, RHS); |
| 789 | } |
| 790 | } |
| 791 | |
| 792 | /// expression |
| 793 | /// ::= primary binoprhs |
| 794 | /// |
| 795 | static ExprAST *ParseExpression() { |
| 796 | ExprAST *LHS = ParsePrimary(); |
| 797 | if (!LHS) return 0; |
| 798 | |
| 799 | return ParseBinOpRHS(0, LHS); |
| 800 | } |
| 801 | |
| 802 | /// prototype |
| 803 | /// ::= id '(' id* ')' |
| 804 | static PrototypeAST *ParsePrototype() { |
| 805 | if (CurTok != tok_identifier) |
| 806 | return ErrorP("Expected function name in prototype"); |
| 807 | |
| 808 | std::string FnName = IdentifierStr; |
| 809 | getNextToken(); |
| 810 | |
| 811 | if (CurTok != '(') |
| 812 | return ErrorP("Expected '(' in prototype"); |
| 813 | |
| 814 | std::vector<std::string> ArgNames; |
| 815 | while (getNextToken() == tok_identifier) |
| 816 | ArgNames.push_back(IdentifierStr); |
| 817 | if (CurTok != ')') |
| 818 | return ErrorP("Expected ')' in prototype"); |
| 819 | |
| 820 | // success. |
| 821 | getNextToken(); // eat ')'. |
| 822 | |
| 823 | return new PrototypeAST(FnName, ArgNames); |
| 824 | } |
| 825 | |
| 826 | /// definition ::= 'def' prototype expression |
| 827 | static FunctionAST *ParseDefinition() { |
| 828 | getNextToken(); // eat def. |
| 829 | PrototypeAST *Proto = ParsePrototype(); |
| 830 | if (Proto == 0) return 0; |
| 831 | |
| 832 | if (ExprAST *E = ParseExpression()) |
| 833 | return new FunctionAST(Proto, E); |
| 834 | return 0; |
| 835 | } |
| 836 | |
| 837 | /// toplevelexpr ::= expression |
| 838 | static FunctionAST *ParseTopLevelExpr() { |
| 839 | if (ExprAST *E = ParseExpression()) { |
| 840 | // Make an anonymous proto. |
| 841 | PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>()); |
| 842 | return new FunctionAST(Proto, E); |
| 843 | } |
| 844 | return 0; |
| 845 | } |
| 846 | |
| 847 | /// external ::= 'extern' prototype |
| 848 | static PrototypeAST *ParseExtern() { |
| 849 | getNextToken(); // eat extern. |
| 850 | return ParsePrototype(); |
| 851 | } |
| 852 | |
| 853 | //===----------------------------------------------------------------------===// |
| 854 | // Code Generation |
| 855 | //===----------------------------------------------------------------------===// |
| 856 | |
| 857 | static Module *TheModule; |
Owen Anderson | d1fbd14 | 2009-07-08 20:50:47 +0000 | [diff] [blame] | 858 | static IRBuilder<> Builder(getGlobalContext()); |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 859 | static std::map<std::string, Value*> NamedValues; |
| 860 | static FunctionPassManager *TheFPM; |
| 861 | |
| 862 | Value *ErrorV(const char *Str) { Error(Str); return 0; } |
| 863 | |
| 864 | Value *NumberExprAST::Codegen() { |
Owen Anderson | 6f83c9c | 2009-07-27 20:59:43 +0000 | [diff] [blame] | 865 | return ConstantFP::get(getGlobalContext(), APFloat(Val)); |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 866 | } |
| 867 | |
| 868 | Value *VariableExprAST::Codegen() { |
| 869 | // Look this variable up in the function. |
| 870 | Value *V = NamedValues[Name]; |
| 871 | return V ? V : ErrorV("Unknown variable name"); |
| 872 | } |
| 873 | |
| 874 | Value *BinaryExprAST::Codegen() { |
| 875 | Value *L = LHS->Codegen(); |
| 876 | Value *R = RHS->Codegen(); |
| 877 | if (L == 0 || R == 0) return 0; |
| 878 | |
| 879 | switch (Op) { |
| 880 | case '+': return Builder.CreateAdd(L, R, "addtmp"); |
| 881 | case '-': return Builder.CreateSub(L, R, "subtmp"); |
| 882 | case '*': return Builder.CreateMul(L, R, "multmp"); |
| 883 | case '<': |
Chris Lattner | 7115521 | 2007-11-06 01:39:12 +0000 | [diff] [blame] | 884 | L = Builder.CreateFCmpULT(L, R, "cmptmp"); |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 885 | // Convert bool 0/1 to double 0.0 or 1.0 |
Nick Lewycky | 422094c | 2009-09-13 21:38:54 +0000 | [diff] [blame] | 886 | return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()), |
| 887 | "booltmp"); |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 888 | default: return ErrorV("invalid binary operator"); |
| 889 | } |
| 890 | } |
| 891 | |
| 892 | Value *CallExprAST::Codegen() { |
| 893 | // Look up the name in the global module table. |
| 894 | Function *CalleeF = TheModule->getFunction(Callee); |
| 895 | if (CalleeF == 0) |
| 896 | return ErrorV("Unknown function referenced"); |
| 897 | |
| 898 | // If argument mismatch error. |
| 899 | if (CalleeF->arg_size() != Args.size()) |
| 900 | return ErrorV("Incorrect # arguments passed"); |
| 901 | |
| 902 | std::vector<Value*> ArgsV; |
| 903 | for (unsigned i = 0, e = Args.size(); i != e; ++i) { |
| 904 | ArgsV.push_back(Args[i]->Codegen()); |
| 905 | if (ArgsV.back() == 0) return 0; |
| 906 | } |
| 907 | |
| 908 | return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp"); |
| 909 | } |
| 910 | |
| 911 | Function *PrototypeAST::Codegen() { |
| 912 | // Make the function type: double(double,double) etc. |
Nick Lewycky | 422094c | 2009-09-13 21:38:54 +0000 | [diff] [blame] | 913 | std::vector<const Type*> Doubles(Args.size(), |
| 914 | Type::getDoubleTy(getGlobalContext())); |
| 915 | FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()), |
| 916 | Doubles, false); |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 917 | |
Gabor Greif | df7d2b4 | 2008-04-19 22:25:09 +0000 | [diff] [blame] | 918 | Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule); |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 919 | |
| 920 | // If F conflicted, there was already something named 'Name'. If it has a |
| 921 | // body, don't allow redefinition or reextern. |
| 922 | if (F->getName() != Name) { |
| 923 | // Delete the one we just made and get the existing one. |
| 924 | F->eraseFromParent(); |
| 925 | F = TheModule->getFunction(Name); |
| 926 | |
| 927 | // If F already has a body, reject this. |
| 928 | if (!F->empty()) { |
| 929 | ErrorF("redefinition of function"); |
| 930 | return 0; |
| 931 | } |
| 932 | |
| 933 | // If F took a different number of args, reject. |
| 934 | if (F->arg_size() != Args.size()) { |
| 935 | ErrorF("redefinition of function with different # args"); |
| 936 | return 0; |
| 937 | } |
| 938 | } |
| 939 | |
| 940 | // Set names for all arguments. |
| 941 | unsigned Idx = 0; |
| 942 | for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size(); |
| 943 | ++AI, ++Idx) { |
| 944 | AI->setName(Args[Idx]); |
| 945 | |
| 946 | // Add arguments to variable symbol table. |
| 947 | NamedValues[Args[Idx]] = AI; |
| 948 | } |
| 949 | |
| 950 | return F; |
| 951 | } |
| 952 | |
| 953 | Function *FunctionAST::Codegen() { |
| 954 | NamedValues.clear(); |
| 955 | |
| 956 | Function *TheFunction = Proto->Codegen(); |
| 957 | if (TheFunction == 0) |
| 958 | return 0; |
| 959 | |
| 960 | // Create a new basic block to start insertion into. |
Owen Anderson | 1d0be15 | 2009-08-13 21:58:54 +0000 | [diff] [blame] | 961 | BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction); |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 962 | Builder.SetInsertPoint(BB); |
| 963 | |
| 964 | if (Value *RetVal = Body->Codegen()) { |
| 965 | // Finish off the function. |
| 966 | Builder.CreateRet(RetVal); |
| 967 | |
| 968 | // Validate the generated code, checking for consistency. |
| 969 | verifyFunction(*TheFunction); |
| 970 | |
| 971 | // Optimize the function. |
| 972 | TheFPM->run(*TheFunction); |
| 973 | |
| 974 | return TheFunction; |
| 975 | } |
| 976 | |
| 977 | // Error reading body, remove function. |
| 978 | TheFunction->eraseFromParent(); |
| 979 | return 0; |
| 980 | } |
| 981 | |
| 982 | //===----------------------------------------------------------------------===// |
| 983 | // Top-Level parsing and JIT Driver |
| 984 | //===----------------------------------------------------------------------===// |
| 985 | |
| 986 | static ExecutionEngine *TheExecutionEngine; |
| 987 | |
| 988 | static void HandleDefinition() { |
| 989 | if (FunctionAST *F = ParseDefinition()) { |
| 990 | if (Function *LF = F->Codegen()) { |
| 991 | fprintf(stderr, "Read function definition:"); |
| 992 | LF->dump(); |
| 993 | } |
| 994 | } else { |
| 995 | // Skip token for error recovery. |
| 996 | getNextToken(); |
| 997 | } |
| 998 | } |
| 999 | |
| 1000 | static void HandleExtern() { |
| 1001 | if (PrototypeAST *P = ParseExtern()) { |
| 1002 | if (Function *F = P->Codegen()) { |
| 1003 | fprintf(stderr, "Read extern: "); |
| 1004 | F->dump(); |
| 1005 | } |
| 1006 | } else { |
| 1007 | // Skip token for error recovery. |
| 1008 | getNextToken(); |
| 1009 | } |
| 1010 | } |
| 1011 | |
| 1012 | static void HandleTopLevelExpression() { |
Erick Tryzelaar | fd1ec5e | 2009-09-22 21:14:49 +0000 | [diff] [blame] | 1013 | // Evaluate a top-level expression into an anonymous function. |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 1014 | if (FunctionAST *F = ParseTopLevelExpr()) { |
| 1015 | if (Function *LF = F->Codegen()) { |
| 1016 | // JIT the function, returning a function pointer. |
| 1017 | void *FPtr = TheExecutionEngine->getPointerToFunction(LF); |
| 1018 | |
| 1019 | // Cast it to the right type (takes no arguments, returns a double) so we |
| 1020 | // can call it as a native function. |
Nick Lewycky | 422094c | 2009-09-13 21:38:54 +0000 | [diff] [blame] | 1021 | double (*FP)() = (double (*)())(intptr_t)FPtr; |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 1022 | fprintf(stderr, "Evaluated to %f\n", FP()); |
| 1023 | } |
| 1024 | } else { |
| 1025 | // Skip token for error recovery. |
| 1026 | getNextToken(); |
| 1027 | } |
| 1028 | } |
| 1029 | |
| 1030 | /// top ::= definition | external | expression | ';' |
| 1031 | static void MainLoop() { |
| 1032 | while (1) { |
| 1033 | fprintf(stderr, "ready> "); |
| 1034 | switch (CurTok) { |
| 1035 | case tok_eof: return; |
Erick Tryzelaar | fd1ec5e | 2009-09-22 21:14:49 +0000 | [diff] [blame] | 1036 | case ';': getNextToken(); break; // ignore top-level semicolons. |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 1037 | case tok_def: HandleDefinition(); break; |
| 1038 | case tok_extern: HandleExtern(); break; |
| 1039 | default: HandleTopLevelExpression(); break; |
| 1040 | } |
| 1041 | } |
| 1042 | } |
| 1043 | |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 1044 | //===----------------------------------------------------------------------===// |
| 1045 | // "Library" functions that can be "extern'd" from user code. |
| 1046 | //===----------------------------------------------------------------------===// |
| 1047 | |
| 1048 | /// putchard - putchar that takes a double and returns 0. |
| 1049 | extern "C" |
| 1050 | double putchard(double X) { |
| 1051 | putchar((char)X); |
| 1052 | return 0; |
| 1053 | } |
| 1054 | |
| 1055 | //===----------------------------------------------------------------------===// |
| 1056 | // Main driver code. |
| 1057 | //===----------------------------------------------------------------------===// |
| 1058 | |
| 1059 | int main() { |
Nick Lewycky | 422094c | 2009-09-13 21:38:54 +0000 | [diff] [blame] | 1060 | InitializeNativeTarget(); |
| 1061 | LLVMContext &Context = getGlobalContext(); |
| 1062 | |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 1063 | // Install standard binary operators. |
| 1064 | // 1 is lowest precedence. |
| 1065 | BinopPrecedence['<'] = 10; |
| 1066 | BinopPrecedence['+'] = 20; |
| 1067 | BinopPrecedence['-'] = 20; |
| 1068 | BinopPrecedence['*'] = 40; // highest. |
| 1069 | |
| 1070 | // Prime the first token. |
| 1071 | fprintf(stderr, "ready> "); |
| 1072 | getNextToken(); |
| 1073 | |
| 1074 | // Make the module, which holds all the code. |
Nick Lewycky | 422094c | 2009-09-13 21:38:54 +0000 | [diff] [blame] | 1075 | TheModule = new Module("my cool jit", Context); |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 1076 | |
Jeffrey Yasskin | f0356fe | 2010-01-27 20:34:15 +0000 | [diff] [blame^] | 1077 | // Create the JIT. This takes ownership of the module. |
| 1078 | TheExecutionEngine = EngineBuilder(TheModule).create(); |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 1079 | |
Jeffrey Yasskin | f0356fe | 2010-01-27 20:34:15 +0000 | [diff] [blame^] | 1080 | FunctionPassManager OurFPM(TheModule); |
Reid Kleckner | 60130f0 | 2009-08-26 20:58:25 +0000 | [diff] [blame] | 1081 | |
| 1082 | // Set up the optimizer pipeline. Start with registering info about how the |
| 1083 | // target lays out data structures. |
| 1084 | OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData())); |
| 1085 | // Do simple "peephole" optimizations and bit-twiddling optzns. |
| 1086 | OurFPM.add(createInstructionCombiningPass()); |
| 1087 | // Reassociate expressions. |
| 1088 | OurFPM.add(createReassociatePass()); |
| 1089 | // Eliminate Common SubExpressions. |
| 1090 | OurFPM.add(createGVNPass()); |
| 1091 | // Simplify the control flow graph (deleting unreachable blocks, etc). |
| 1092 | OurFPM.add(createCFGSimplificationPass()); |
| 1093 | |
Nick Lewycky | 422094c | 2009-09-13 21:38:54 +0000 | [diff] [blame] | 1094 | OurFPM.doInitialization(); |
| 1095 | |
Reid Kleckner | 60130f0 | 2009-08-26 20:58:25 +0000 | [diff] [blame] | 1096 | // Set the global so the code gen can use this. |
| 1097 | TheFPM = &OurFPM; |
| 1098 | |
| 1099 | // Run the main "interpreter loop" now. |
| 1100 | MainLoop(); |
| 1101 | |
| 1102 | TheFPM = 0; |
| 1103 | |
| 1104 | // Print out all of the generated code. |
| 1105 | TheModule->dump(); |
| 1106 | |
Chris Lattner | 118749e | 2007-10-25 06:23:36 +0000 | [diff] [blame] | 1107 | return 0; |
| 1108 | } |
Chris Lattner | c0b42e9 | 2007-10-23 06:27:55 +0000 | [diff] [blame] | 1109 | </pre> |
| 1110 | </div> |
| 1111 | |
Chris Lattner | 729eb14 | 2008-02-10 19:11:04 +0000 | [diff] [blame] | 1112 | <a href="LangImpl5.html">Next: Extending the language: control flow</a> |
Chris Lattner | c0b42e9 | 2007-10-23 06:27:55 +0000 | [diff] [blame] | 1113 | </div> |
| 1114 | |
| 1115 | <!-- *********************************************************************** --> |
| 1116 | <hr> |
| 1117 | <address> |
| 1118 | <a href="http://jigsaw.w3.org/css-validator/check/referer"><img |
| 1119 | src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a> |
| 1120 | <a href="http://validator.w3.org/check/referer"><img |
Chris Lattner | 8eef4b2 | 2007-10-23 06:30:50 +0000 | [diff] [blame] | 1121 | src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a> |
Chris Lattner | c0b42e9 | 2007-10-23 06:27:55 +0000 | [diff] [blame] | 1122 | |
| 1123 | <a href="mailto:sabre@nondot.org">Chris Lattner</a><br> |
| 1124 | <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br> |
| 1125 | Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $ |
| 1126 | </address> |
| 1127 | </body> |
| 1128 | </html> |