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