docs/tutorial/LangImpl4.html

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