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: Implementing code generation to LLVM IR</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: Code generation to LLVM IR</h1> 15 16<ul> 17<li><a href="index.html">Up to Tutorial Index</a></li> 18<li>Chapter 3 19 <ol> 20 <li><a href="#intro">Chapter 3 Introduction</a></li> 21 <li><a href="#basics">Code Generation Setup</a></li> 22 <li><a href="#exprs">Expression Code Generation</a></li> 23 <li><a href="#funcs">Function Code Generation</a></li> 24 <li><a href="#driver">Driver Changes and Closing Thoughts</a></li> 25 <li><a href="#code">Full Code Listing</a></li> 26 </ol> 27</li> 28<li><a href="LangImpl4.html">Chapter 4</a>: Adding JIT and Optimizer 29Support</li> 30</ul> 31 32<div class="doc_author"> 33 <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p> 34</div> 35 36<!-- *********************************************************************** --> 37<h2><a name="intro">Chapter 3 Introduction</a></h2> 38<!-- *********************************************************************** --> 39 40<div> 41 42<p>Welcome to Chapter 3 of the "<a href="index.html">Implementing a language 43with LLVM</a>" tutorial. This chapter shows you how to transform the <a 44href="LangImpl2.html">Abstract Syntax Tree</a>, built in Chapter 2, into LLVM IR. 45This will teach you a little bit about how LLVM does things, as well as 46demonstrate how easy it is to use. It's much more work to build a lexer and 47parser than it is to generate LLVM IR code. :) 48</p> 49 50<p><b>Please note</b>: the code in this chapter and later require LLVM 2.2 or 51later. LLVM 2.1 and before will not work with it. Also note that you need 52to use a version of this tutorial that matches your LLVM release: If you are 53using an official LLVM release, use the version of the documentation included 54with your release or on the <a href="http://llvm.org/releases/">llvm.org 55releases page</a>.</p> 56 57</div> 58 59<!-- *********************************************************************** --> 60<h2><a name="basics">Code Generation Setup</a></h2> 61<!-- *********************************************************************** --> 62 63<div> 64 65<p> 66In order to generate LLVM IR, we want some simple setup to get started. First 67we define virtual code generation (codegen) methods in each AST class:</p> 68 69<div class="doc_code"> 70<pre> 71/// ExprAST - Base class for all expression nodes. 72class ExprAST { 73public: 74 virtual ~ExprAST() {} 75 <b>virtual Value *Codegen() = 0;</b> 76}; 77 78/// NumberExprAST - Expression class for numeric literals like "1.0". 79class NumberExprAST : public ExprAST { 80 double Val; 81public: 82 NumberExprAST(double val) : Val(val) {} 83 <b>virtual Value *Codegen();</b> 84}; 85... 86</pre> 87</div> 88 89<p>The Codegen() method says to emit IR for that AST node along with all the things it 90depends on, and they all return an LLVM Value object. 91"Value" is the class used to represent a "<a 92href="http://en.wikipedia.org/wiki/Static_single_assignment_form">Static Single 93Assignment (SSA)</a> register" or "SSA value" in LLVM. The most distinct aspect 94of SSA values is that their value is computed as the related instruction 95executes, and it does not get a new value until (and if) the instruction 96re-executes. In other words, there is no way to "change" an SSA value. For 97more information, please read up on <a 98href="http://en.wikipedia.org/wiki/Static_single_assignment_form">Static Single 99Assignment</a> - the concepts are really quite natural once you grok them.</p> 100 101<p>Note that instead of adding virtual methods to the ExprAST class hierarchy, 102it could also make sense to use a <a 103href="http://en.wikipedia.org/wiki/Visitor_pattern">visitor pattern</a> or some 104other way to model this. Again, this tutorial won't dwell on good software 105engineering practices: for our purposes, adding a virtual method is 106simplest.</p> 107 108<p>The 109second thing we want is an "Error" method like we used for the parser, which will 110be used to report errors found during code generation (for example, use of an 111undeclared parameter):</p> 112 113<div class="doc_code"> 114<pre> 115Value *ErrorV(const char *Str) { Error(Str); return 0; } 116 117static Module *TheModule; 118static IRBuilder<> Builder(getGlobalContext()); 119static std::map<std::string, Value*> NamedValues; 120</pre> 121</div> 122 123<p>The static variables will be used during code generation. <tt>TheModule</tt> 124is the LLVM construct that contains all of the functions and global variables in 125a chunk of code. In many ways, it is the top-level structure that the LLVM IR 126uses to contain code.</p> 127 128<p>The <tt>Builder</tt> object is a helper object that makes it easy to generate 129LLVM instructions. Instances of the <a 130href="http://llvm.org/doxygen/IRBuilder_8h-source.html"><tt>IRBuilder</tt></a> 131class template keep track of the current place to insert instructions and has 132methods to create new instructions.</p> 133 134<p>The <tt>NamedValues</tt> map keeps track of which values are defined in the 135current scope and what their LLVM representation is. (In other words, it is a 136symbol table for the code). In this form of Kaleidoscope, the only things that 137can be referenced are function parameters. As such, function parameters will 138be in this map when generating code for their function body.</p> 139 140<p> 141With these basics in place, we can start talking about how to generate code for 142each expression. Note that this assumes that the <tt>Builder</tt> has been set 143up to generate code <em>into</em> something. For now, we'll assume that this 144has already been done, and we'll just use it to emit code. 145</p> 146 147</div> 148 149<!-- *********************************************************************** --> 150<h2><a name="exprs">Expression Code Generation</a></h2> 151<!-- *********************************************************************** --> 152 153<div> 154 155<p>Generating LLVM code for expression nodes is very straightforward: less 156than 45 lines of commented code for all four of our expression nodes. First 157we'll do numeric literals:</p> 158 159<div class="doc_code"> 160<pre> 161Value *NumberExprAST::Codegen() { 162 return ConstantFP::get(getGlobalContext(), APFloat(Val)); 163} 164</pre> 165</div> 166 167<p>In the LLVM IR, numeric constants are represented with the 168<tt>ConstantFP</tt> class, which holds the numeric value in an <tt>APFloat</tt> 169internally (<tt>APFloat</tt> has the capability of holding floating point 170constants of <em>A</em>rbitrary <em>P</em>recision). This code basically just 171creates and returns a <tt>ConstantFP</tt>. Note that in the LLVM IR 172that constants are all uniqued together and shared. For this reason, the API 173uses the "foo::get(...)" idiom instead of "new foo(..)" or "foo::Create(..)".</p> 174 175<div class="doc_code"> 176<pre> 177Value *VariableExprAST::Codegen() { 178 // Look this variable up in the function. 179 Value *V = NamedValues[Name]; 180 return V ? V : ErrorV("Unknown variable name"); 181} 182</pre> 183</div> 184 185<p>References to variables are also quite simple using LLVM. In the simple version 186of Kaleidoscope, we assume that the variable has already been emitted somewhere 187and its value is available. In practice, the only values that can be in the 188<tt>NamedValues</tt> map are function arguments. This 189code simply checks to see that the specified name is in the map (if not, an 190unknown variable is being referenced) and returns the value for it. In future 191chapters, we'll add support for <a href="LangImpl5.html#for">loop induction 192variables</a> in the symbol table, and for <a 193href="LangImpl7.html#localvars">local variables</a>.</p> 194 195<div class="doc_code"> 196<pre> 197Value *BinaryExprAST::Codegen() { 198 Value *L = LHS->Codegen(); 199 Value *R = RHS->Codegen(); 200 if (L == 0 || R == 0) return 0; 201 202 switch (Op) { 203 case '+': return Builder.CreateFAdd(L, R, "addtmp"); 204 case '-': return Builder.CreateFSub(L, R, "subtmp"); 205 case '*': return Builder.CreateFMul(L, R, "multmp"); 206 case '<': 207 L = Builder.CreateFCmpULT(L, R, "cmptmp"); 208 // Convert bool 0/1 to double 0.0 or 1.0 209 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()), 210 "booltmp"); 211 default: return ErrorV("invalid binary operator"); 212 } 213} 214</pre> 215</div> 216 217<p>Binary operators start to get more interesting. The basic idea here is that 218we recursively emit code for the left-hand side of the expression, then the 219right-hand side, then we compute the result of the binary expression. In this 220code, we do a simple switch on the opcode to create the right LLVM instruction. 221</p> 222 223<p>In the example above, the LLVM builder class is starting to show its value. 224IRBuilder knows where to insert the newly created instruction, all you have to 225do is specify what instruction to create (e.g. with <tt>CreateFAdd</tt>), which 226operands to use (<tt>L</tt> and <tt>R</tt> here) and optionally provide a name 227for the generated instruction.</p> 228 229<p>One nice thing about LLVM is that the name is just a hint. For instance, if 230the code above emits multiple "addtmp" variables, LLVM will automatically 231provide each one with an increasing, unique numeric suffix. Local value names 232for instructions are purely optional, but it makes it much easier to read the 233IR dumps.</p> 234 235<p><a href="/LangRef.html#instref">LLVM instructions</a> are constrained by 236strict rules: for example, the Left and Right operators of 237an <a href="/LangRef.html#i_add">add instruction</a> must have the same 238type, and the result type of the add must match the operand types. Because 239all values in Kaleidoscope are doubles, this makes for very simple code for add, 240sub and mul.</p> 241 242<p>On the other hand, LLVM specifies that the <a 243href="/LangRef.html#i_fcmp">fcmp instruction</a> always returns an 'i1' value 244(a one bit integer). The problem with this is that Kaleidoscope wants the value to be a 0.0 or 1.0 value. In order to get these semantics, we combine the fcmp instruction with 245a <a href="/LangRef.html#i_uitofp">uitofp instruction</a>. This instruction 246converts its input integer into a floating point value by treating the input 247as an unsigned value. In contrast, if we used the <a 248href="/LangRef.html#i_sitofp">sitofp instruction</a>, the Kaleidoscope '<' 249operator would return 0.0 and -1.0, depending on the input value.</p> 250 251<div class="doc_code"> 252<pre> 253Value *CallExprAST::Codegen() { 254 // Look up the name in the global module table. 255 Function *CalleeF = TheModule->getFunction(Callee); 256 if (CalleeF == 0) 257 return ErrorV("Unknown function referenced"); 258 259 // If argument mismatch error. 260 if (CalleeF->arg_size() != Args.size()) 261 return ErrorV("Incorrect # arguments passed"); 262 263 std::vector<Value*> ArgsV; 264 for (unsigned i = 0, e = Args.size(); i != e; ++i) { 265 ArgsV.push_back(Args[i]->Codegen()); 266 if (ArgsV.back() == 0) return 0; 267 } 268 269 return Builder.CreateCall(CalleeF, ArgsV, "calltmp"); 270} 271</pre> 272</div> 273 274<p>Code generation for function calls is quite straightforward with LLVM. The 275code above initially does a function name lookup in the LLVM Module's symbol 276table. Recall that the LLVM Module is the container that holds all of the 277functions we are JIT'ing. By giving each function the same name as what the 278user specifies, we can use the LLVM symbol table to resolve function names for 279us.</p> 280 281<p>Once we have the function to call, we recursively codegen each argument that 282is to be passed in, and create an LLVM <a href="/LangRef.html#i_call">call 283instruction</a>. Note that LLVM uses the native C calling conventions by 284default, allowing these calls to also call into standard library functions like 285"sin" and "cos", with no additional effort.</p> 286 287<p>This wraps up our handling of the four basic expressions that we have so far 288in Kaleidoscope. Feel free to go in and add some more. For example, by 289browsing the <a href="/LangRef.html">LLVM language reference</a> you'll find 290several other interesting instructions that are really easy to plug into our 291basic framework.</p> 292 293</div> 294 295<!-- *********************************************************************** --> 296<h2><a name="funcs">Function Code Generation</a></h2> 297<!-- *********************************************************************** --> 298 299<div> 300 301<p>Code generation for prototypes and functions must handle a number of 302details, which make their code less beautiful than expression code 303generation, but allows us to illustrate some important points. First, lets 304talk about code generation for prototypes: they are used both for function 305bodies and external function declarations. The code starts with:</p> 306 307<div class="doc_code"> 308<pre> 309Function *PrototypeAST::Codegen() { 310 // Make the function type: double(double,double) etc. 311 std::vector<Type*> Doubles(Args.size(), 312 Type::getDoubleTy(getGlobalContext())); 313 FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()), 314 Doubles, false); 315 316 Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule); 317</pre> 318</div> 319 320<p>This code packs a lot of power into a few lines. Note first that this 321function returns a "Function*" instead of a "Value*". Because a "prototype" 322really talks about the external interface for a function (not the value computed 323by an expression), it makes sense for it to return the LLVM Function it 324corresponds to when codegen'd.</p> 325 326<p>The call to <tt>FunctionType::get</tt> creates 327the <tt>FunctionType</tt> that should be used for a given Prototype. Since all 328function arguments in Kaleidoscope are of type double, the first line creates 329a vector of "N" LLVM double types. It then uses the <tt>Functiontype::get</tt> 330method to create a function type that takes "N" doubles as arguments, returns 331one double as a result, and that is not vararg (the false parameter indicates 332this). Note that Types in LLVM are uniqued just like Constants are, so you 333don't "new" a type, you "get" it.</p> 334 335<p>The final line above actually creates the function that the prototype will 336correspond to. This indicates the type, linkage and name to use, as well as which 337module to insert into. "<a href="/LangRef.html#linkage">external linkage</a>" 338means that the function may be defined outside the current module and/or that it 339is callable by functions outside the module. The Name passed in is the name the 340user specified: since "<tt>TheModule</tt>" is specified, this name is registered 341in "<tt>TheModule</tt>"s symbol table, which is used by the function call code 342above.</p> 343 344<div class="doc_code"> 345<pre> 346 // If F conflicted, there was already something named 'Name'. If it has a 347 // body, don't allow redefinition or reextern. 348 if (F->getName() != Name) { 349 // Delete the one we just made and get the existing one. 350 F->eraseFromParent(); 351 F = TheModule->getFunction(Name); 352</pre> 353</div> 354 355<p>The Module symbol table works just like the Function symbol table when it 356comes to name conflicts: if a new function is created with a name that was previously 357added to the symbol table, the new function will get implicitly renamed when added to the 358Module. The code above exploits this fact to determine if there was a previous 359definition of this function.</p> 360 361<p>In Kaleidoscope, I choose to allow redefinitions of functions in two cases: 362first, we want to allow 'extern'ing a function more than once, as long as the 363prototypes for the externs match (since all arguments have the same type, we 364just have to check that the number of arguments match). Second, we want to 365allow 'extern'ing a function and then defining a body for it. This is useful 366when defining mutually recursive functions.</p> 367 368<p>In order to implement this, the code above first checks to see if there is 369a collision on the name of the function. If so, it deletes the function we just 370created (by calling <tt>eraseFromParent</tt>) and then calling 371<tt>getFunction</tt> to get the existing function with the specified name. Note 372that many APIs in LLVM have "erase" forms and "remove" forms. The "remove" form 373unlinks the object from its parent (e.g. a Function from a Module) and returns 374it. The "erase" form unlinks the object and then deletes it.</p> 375 376<div class="doc_code"> 377<pre> 378 // If F already has a body, reject this. 379 if (!F->empty()) { 380 ErrorF("redefinition of function"); 381 return 0; 382 } 383 384 // If F took a different number of args, reject. 385 if (F->arg_size() != Args.size()) { 386 ErrorF("redefinition of function with different # args"); 387 return 0; 388 } 389 } 390</pre> 391</div> 392 393<p>In order to verify the logic above, we first check to see if the pre-existing 394function is "empty". In this case, empty means that it has no basic blocks in 395it, which means it has no body. If it has no body, it is a forward 396declaration. Since we don't allow anything after a full definition of the 397function, the code rejects this case. If the previous reference to a function 398was an 'extern', we simply verify that the number of arguments for that 399definition and this one match up. If not, we emit an error.</p> 400 401<div class="doc_code"> 402<pre> 403 // Set names for all arguments. 404 unsigned Idx = 0; 405 for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size(); 406 ++AI, ++Idx) { 407 AI->setName(Args[Idx]); 408 409 // Add arguments to variable symbol table. 410 NamedValues[Args[Idx]] = AI; 411 } 412 return F; 413} 414</pre> 415</div> 416 417<p>The last bit of code for prototypes loops over all of the arguments in the 418function, setting the name of the LLVM Argument objects to match, and registering 419the arguments in the <tt>NamedValues</tt> map for future use by the 420<tt>VariableExprAST</tt> AST node. Once this is set up, it returns the Function 421object to the caller. Note that we don't check for conflicting 422argument names here (e.g. "extern foo(a b a)"). Doing so would be very 423straight-forward with the mechanics we have already used above.</p> 424 425<div class="doc_code"> 426<pre> 427Function *FunctionAST::Codegen() { 428 NamedValues.clear(); 429 430 Function *TheFunction = Proto->Codegen(); 431 if (TheFunction == 0) 432 return 0; 433</pre> 434</div> 435 436<p>Code generation for function definitions starts out simply enough: we just 437codegen the prototype (Proto) and verify that it is ok. We then clear out the 438<tt>NamedValues</tt> map to make sure that there isn't anything in it from the 439last function we compiled. Code generation of the prototype ensures that there 440is an LLVM Function object that is ready to go for us.</p> 441 442<div class="doc_code"> 443<pre> 444 // Create a new basic block to start insertion into. 445 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction); 446 Builder.SetInsertPoint(BB); 447 448 if (Value *RetVal = Body->Codegen()) { 449</pre> 450</div> 451 452<p>Now we get to the point where the <tt>Builder</tt> is set up. The first 453line creates a new <a href="http://en.wikipedia.org/wiki/Basic_block">basic 454block</a> (named "entry"), which is inserted into <tt>TheFunction</tt>. The 455second line then tells the builder that new instructions should be inserted into 456the end of the new basic block. Basic blocks in LLVM are an important part 457of functions that define the <a 458href="http://en.wikipedia.org/wiki/Control_flow_graph">Control Flow Graph</a>. 459Since we don't have any control flow, our functions will only contain one 460block at this point. We'll fix this in <a href="LangImpl5.html">Chapter 5</a> :).</p> 461 462<div class="doc_code"> 463<pre> 464 if (Value *RetVal = Body->Codegen()) { 465 // Finish off the function. 466 Builder.CreateRet(RetVal); 467 468 // Validate the generated code, checking for consistency. 469 verifyFunction(*TheFunction); 470 471 return TheFunction; 472 } 473</pre> 474</div> 475 476<p>Once the insertion point is set up, we call the <tt>CodeGen()</tt> method for 477the root expression of the function. If no error happens, this emits code to 478compute the expression into the entry block and returns the value that was 479computed. Assuming no error, we then create an LLVM <a 480href="/LangRef.html#i_ret">ret instruction</a>, which completes the function. 481Once the function is built, we call <tt>verifyFunction</tt>, which 482is provided by LLVM. This function does a variety of consistency checks on the 483generated code, to determine if our compiler is doing everything right. Using 484this is important: it can catch a lot of bugs. Once the function is finished 485and validated, we return it.</p> 486 487<div class="doc_code"> 488<pre> 489 // Error reading body, remove function. 490 TheFunction->eraseFromParent(); 491 return 0; 492} 493</pre> 494</div> 495 496<p>The only piece left here is handling of the error case. For simplicity, we 497handle this by merely deleting the function we produced with the 498<tt>eraseFromParent</tt> method. This allows the user to redefine a function 499that they incorrectly typed in before: if we didn't delete it, it would live in 500the symbol table, with a body, preventing future redefinition.</p> 501 502<p>This code does have a bug, though. Since the <tt>PrototypeAST::Codegen</tt> 503can return a previously defined forward declaration, our code can actually delete 504a forward declaration. There are a number of ways to fix this bug, see what you 505can come up with! Here is a testcase:</p> 506 507<div class="doc_code"> 508<pre> 509extern foo(a b); # ok, defines foo. 510def foo(a b) c; # error, 'c' is invalid. 511def bar() foo(1, 2); # error, unknown function "foo" 512</pre> 513</div> 514 515</div> 516 517<!-- *********************************************************************** --> 518<h2><a name="driver">Driver Changes and Closing Thoughts</a></h2> 519<!-- *********************************************************************** --> 520 521<div> 522 523<p> 524For now, code generation to LLVM doesn't really get us much, except that we can 525look at the pretty IR calls. The sample code inserts calls to Codegen into the 526"<tt>HandleDefinition</tt>", "<tt>HandleExtern</tt>" etc functions, and then 527dumps out the LLVM IR. This gives a nice way to look at the LLVM IR for simple 528functions. For example: 529</p> 530 531<div class="doc_code"> 532<pre> 533ready> <b>4+5</b>; 534Read top-level expression: 535define double @0() { 536entry: 537 ret double 9.000000e+00 538} 539</pre> 540</div> 541 542<p>Note how the parser turns the top-level expression into anonymous functions 543for us. This will be handy when we add <a href="LangImpl4.html#jit">JIT 544support</a> in the next chapter. Also note that the code is very literally 545transcribed, no optimizations are being performed except simple constant 546folding done by IRBuilder. We will 547<a href="LangImpl4.html#trivialconstfold">add optimizations</a> explicitly in 548the next chapter.</p> 549 550<div class="doc_code"> 551<pre> 552ready> <b>def foo(a b) a*a + 2*a*b + b*b;</b> 553Read function definition: 554define double @foo(double %a, double %b) { 555entry: 556 %multmp = fmul double %a, %a 557 %multmp1 = fmul double 2.000000e+00, %a 558 %multmp2 = fmul double %multmp1, %b 559 %addtmp = fadd double %multmp, %multmp2 560 %multmp3 = fmul double %b, %b 561 %addtmp4 = fadd double %addtmp, %multmp3 562 ret double %addtmp4 563} 564</pre> 565</div> 566 567<p>This shows some simple arithmetic. Notice the striking similarity to the 568LLVM builder calls that we use to create the instructions.</p> 569 570<div class="doc_code"> 571<pre> 572ready> <b>def bar(a) foo(a, 4.0) + bar(31337);</b> 573Read function definition: 574define double @bar(double %a) { 575entry: 576 %calltmp = call double @foo(double %a, double 4.000000e+00) 577 %calltmp1 = call double @bar(double 3.133700e+04) 578 %addtmp = fadd double %calltmp, %calltmp1 579 ret double %addtmp 580} 581</pre> 582</div> 583 584<p>This shows some function calls. Note that this function will take a long 585time to execute if you call it. In the future we'll add conditional control 586flow to actually make recursion useful :).</p> 587 588<div class="doc_code"> 589<pre> 590ready> <b>extern cos(x);</b> 591Read extern: 592declare double @cos(double) 593 594ready> <b>cos(1.234);</b> 595Read top-level expression: 596define double @1() { 597entry: 598 %calltmp = call double @cos(double 1.234000e+00) 599 ret double %calltmp 600} 601</pre> 602</div> 603 604<p>This shows an extern for the libm "cos" function, and a call to it.</p> 605 606 607<div class="doc_code"> 608<pre> 609ready> <b>^D</b> 610; ModuleID = 'my cool jit' 611 612define double @0() { 613entry: 614 %addtmp = fadd double 4.000000e+00, 5.000000e+00 615 ret double %addtmp 616} 617 618define double @foo(double %a, double %b) { 619entry: 620 %multmp = fmul double %a, %a 621 %multmp1 = fmul double 2.000000e+00, %a 622 %multmp2 = fmul double %multmp1, %b 623 %addtmp = fadd double %multmp, %multmp2 624 %multmp3 = fmul double %b, %b 625 %addtmp4 = fadd double %addtmp, %multmp3 626 ret double %addtmp4 627} 628 629define double @bar(double %a) { 630entry: 631 %calltmp = call double @foo(double %a, double 4.000000e+00) 632 %calltmp1 = call double @bar(double 3.133700e+04) 633 %addtmp = fadd double %calltmp, %calltmp1 634 ret double %addtmp 635} 636 637declare double @cos(double) 638 639define double @1() { 640entry: 641 %calltmp = call double @cos(double 1.234000e+00) 642 ret double %calltmp 643} 644</pre> 645</div> 646 647<p>When you quit the current demo, it dumps out the IR for the entire module 648generated. Here you can see the big picture with all the functions referencing 649each other.</p> 650 651<p>This wraps up the third chapter of the Kaleidoscope tutorial. Up next, we'll 652describe how to <a href="LangImpl4.html">add JIT codegen and optimizer 653support</a> to this so we can actually start running code!</p> 654 655</div> 656 657 658<!-- *********************************************************************** --> 659<h2><a name="code">Full Code Listing</a></h2> 660<!-- *********************************************************************** --> 661 662<div> 663 664<p> 665Here is the complete code listing for our running example, enhanced with the 666LLVM code generator. Because this uses the LLVM libraries, we need to link 667them in. To do this, we use the <a 668href="http://llvm.org/cmds/llvm-config.html">llvm-config</a> tool to inform 669our makefile/command line about which options to use:</p> 670 671<div class="doc_code"> 672<pre> 673# Compile 674clang++ -g -O3 toy.cpp `llvm-config --cppflags --ldflags --libs core` -o toy 675# Run 676/toy 677</pre> 678</div> 679 680<p>Here is the code:</p> 681 682<div class="doc_code"> 683<pre> 684// To build this: 685// See example below. 686 687#include "llvm/DerivedTypes.h" 688#include "llvm/IRBuilder.h" 689#include "llvm/LLVMContext.h" 690#include "llvm/Module.h" 691#include "llvm/Analysis/Verifier.h" 692#include <cstdio> 693#include <string> 694#include <map> 695#include <vector> 696using namespace llvm; 697 698//===----------------------------------------------------------------------===// 699// Lexer 700//===----------------------------------------------------------------------===// 701 702// The lexer returns tokens [0-255] if it is an unknown character, otherwise one 703// of these for known things. 704enum Token { 705 tok_eof = -1, 706 707 // commands 708 tok_def = -2, tok_extern = -3, 709 710 // primary 711 tok_identifier = -4, tok_number = -5 712}; 713 714static std::string IdentifierStr; // Filled in if tok_identifier 715static double NumVal; // Filled in if tok_number 716 717/// gettok - Return the next token from standard input. 718static int gettok() { 719 static int LastChar = ' '; 720 721 // Skip any whitespace. 722 while (isspace(LastChar)) 723 LastChar = getchar(); 724 725 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]* 726 IdentifierStr = LastChar; 727 while (isalnum((LastChar = getchar()))) 728 IdentifierStr += LastChar; 729 730 if (IdentifierStr == "def") return tok_def; 731 if (IdentifierStr == "extern") return tok_extern; 732 return tok_identifier; 733 } 734 735 if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+ 736 std::string NumStr; 737 do { 738 NumStr += LastChar; 739 LastChar = getchar(); 740 } while (isdigit(LastChar) || LastChar == '.'); 741 742 NumVal = strtod(NumStr.c_str(), 0); 743 return tok_number; 744 } 745 746 if (LastChar == '#') { 747 // Comment until end of line. 748 do LastChar = getchar(); 749 while (LastChar != EOF && LastChar != '\n' && LastChar != '\r'); 750 751 if (LastChar != EOF) 752 return gettok(); 753 } 754 755 // Check for end of file. Don't eat the EOF. 756 if (LastChar == EOF) 757 return tok_eof; 758 759 // Otherwise, just return the character as its ascii value. 760 int ThisChar = LastChar; 761 LastChar = getchar(); 762 return ThisChar; 763} 764 765//===----------------------------------------------------------------------===// 766// Abstract Syntax Tree (aka Parse Tree) 767//===----------------------------------------------------------------------===// 768 769/// ExprAST - Base class for all expression nodes. 770class ExprAST { 771public: 772 virtual ~ExprAST() {} 773 virtual Value *Codegen() = 0; 774}; 775 776/// NumberExprAST - Expression class for numeric literals like "1.0". 777class NumberExprAST : public ExprAST { 778 double Val; 779public: 780 NumberExprAST(double val) : Val(val) {} 781 virtual Value *Codegen(); 782}; 783 784/// VariableExprAST - Expression class for referencing a variable, like "a". 785class VariableExprAST : public ExprAST { 786 std::string Name; 787public: 788 VariableExprAST(const std::string &name) : Name(name) {} 789 virtual Value *Codegen(); 790}; 791 792/// BinaryExprAST - Expression class for a binary operator. 793class BinaryExprAST : public ExprAST { 794 char Op; 795 ExprAST *LHS, *RHS; 796public: 797 BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs) 798 : Op(op), LHS(lhs), RHS(rhs) {} 799 virtual Value *Codegen(); 800}; 801 802/// CallExprAST - Expression class for function calls. 803class CallExprAST : public ExprAST { 804 std::string Callee; 805 std::vector<ExprAST*> Args; 806public: 807 CallExprAST(const std::string &callee, std::vector<ExprAST*> &args) 808 : Callee(callee), Args(args) {} 809 virtual Value *Codegen(); 810}; 811 812/// PrototypeAST - This class represents the "prototype" for a function, 813/// which captures its name, and its argument names (thus implicitly the number 814/// of arguments the function takes). 815class PrototypeAST { 816 std::string Name; 817 std::vector<std::string> Args; 818public: 819 PrototypeAST(const std::string &name, const std::vector<std::string> &args) 820 : Name(name), Args(args) {} 821 822 Function *Codegen(); 823}; 824 825/// FunctionAST - This class represents a function definition itself. 826class FunctionAST { 827 PrototypeAST *Proto; 828 ExprAST *Body; 829public: 830 FunctionAST(PrototypeAST *proto, ExprAST *body) 831 : Proto(proto), Body(body) {} 832 833 Function *Codegen(); 834}; 835 836//===----------------------------------------------------------------------===// 837// Parser 838//===----------------------------------------------------------------------===// 839 840/// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current 841/// token the parser is looking at. getNextToken reads another token from the 842/// lexer and updates CurTok with its results. 843static int CurTok; 844static int getNextToken() { 845 return CurTok = gettok(); 846} 847 848/// BinopPrecedence - This holds the precedence for each binary operator that is 849/// defined. 850static std::map<char, int> BinopPrecedence; 851 852/// GetTokPrecedence - Get the precedence of the pending binary operator token. 853static int GetTokPrecedence() { 854 if (!isascii(CurTok)) 855 return -1; 856 857 // Make sure it's a declared binop. 858 int TokPrec = BinopPrecedence[CurTok]; 859 if (TokPrec <= 0) return -1; 860 return TokPrec; 861} 862 863/// Error* - These are little helper functions for error handling. 864ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;} 865PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; } 866FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; } 867 868static ExprAST *ParseExpression(); 869 870/// identifierexpr 871/// ::= identifier 872/// ::= identifier '(' expression* ')' 873static ExprAST *ParseIdentifierExpr() { 874 std::string IdName = IdentifierStr; 875 876 getNextToken(); // eat identifier. 877 878 if (CurTok != '(') // Simple variable ref. 879 return new VariableExprAST(IdName); 880 881 // Call. 882 getNextToken(); // eat ( 883 std::vector<ExprAST*> Args; 884 if (CurTok != ')') { 885 while (1) { 886 ExprAST *Arg = ParseExpression(); 887 if (!Arg) return 0; 888 Args.push_back(Arg); 889 890 if (CurTok == ')') break; 891 892 if (CurTok != ',') 893 return Error("Expected ')' or ',' in argument list"); 894 getNextToken(); 895 } 896 } 897 898 // Eat the ')'. 899 getNextToken(); 900 901 return new CallExprAST(IdName, Args); 902} 903 904/// numberexpr ::= number 905static ExprAST *ParseNumberExpr() { 906 ExprAST *Result = new NumberExprAST(NumVal); 907 getNextToken(); // consume the number 908 return Result; 909} 910 911/// parenexpr ::= '(' expression ')' 912static ExprAST *ParseParenExpr() { 913 getNextToken(); // eat (. 914 ExprAST *V = ParseExpression(); 915 if (!V) return 0; 916 917 if (CurTok != ')') 918 return Error("expected ')'"); 919 getNextToken(); // eat ). 920 return V; 921} 922 923/// primary 924/// ::= identifierexpr 925/// ::= numberexpr 926/// ::= parenexpr 927static ExprAST *ParsePrimary() { 928 switch (CurTok) { 929 default: return Error("unknown token when expecting an expression"); 930 case tok_identifier: return ParseIdentifierExpr(); 931 case tok_number: return ParseNumberExpr(); 932 case '(': return ParseParenExpr(); 933 } 934} 935 936/// binoprhs 937/// ::= ('+' primary)* 938static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) { 939 // If this is a binop, find its precedence. 940 while (1) { 941 int TokPrec = GetTokPrecedence(); 942 943 // If this is a binop that binds at least as tightly as the current binop, 944 // consume it, otherwise we are done. 945 if (TokPrec < ExprPrec) 946 return LHS; 947 948 // Okay, we know this is a binop. 949 int BinOp = CurTok; 950 getNextToken(); // eat binop 951 952 // Parse the primary expression after the binary operator. 953 ExprAST *RHS = ParsePrimary(); 954 if (!RHS) return 0; 955 956 // If BinOp binds less tightly with RHS than the operator after RHS, let 957 // the pending operator take RHS as its LHS. 958 int NextPrec = GetTokPrecedence(); 959 if (TokPrec < NextPrec) { 960 RHS = ParseBinOpRHS(TokPrec+1, RHS); 961 if (RHS == 0) return 0; 962 } 963 964 // Merge LHS/RHS. 965 LHS = new BinaryExprAST(BinOp, LHS, RHS); 966 } 967} 968 969/// expression 970/// ::= primary binoprhs 971/// 972static ExprAST *ParseExpression() { 973 ExprAST *LHS = ParsePrimary(); 974 if (!LHS) return 0; 975 976 return ParseBinOpRHS(0, LHS); 977} 978 979/// prototype 980/// ::= id '(' id* ')' 981static PrototypeAST *ParsePrototype() { 982 if (CurTok != tok_identifier) 983 return ErrorP("Expected function name in prototype"); 984 985 std::string FnName = IdentifierStr; 986 getNextToken(); 987 988 if (CurTok != '(') 989 return ErrorP("Expected '(' in prototype"); 990 991 std::vector<std::string> ArgNames; 992 while (getNextToken() == tok_identifier) 993 ArgNames.push_back(IdentifierStr); 994 if (CurTok != ')') 995 return ErrorP("Expected ')' in prototype"); 996 997 // success. 998 getNextToken(); // eat ')'. 999 1000 return new PrototypeAST(FnName, ArgNames); 1001} 1002 1003/// definition ::= 'def' prototype expression 1004static FunctionAST *ParseDefinition() { 1005 getNextToken(); // eat def. 1006 PrototypeAST *Proto = ParsePrototype(); 1007 if (Proto == 0) return 0; 1008 1009 if (ExprAST *E = ParseExpression()) 1010 return new FunctionAST(Proto, E); 1011 return 0; 1012} 1013 1014/// toplevelexpr ::= expression 1015static FunctionAST *ParseTopLevelExpr() { 1016 if (ExprAST *E = ParseExpression()) { 1017 // Make an anonymous proto. 1018 PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>()); 1019 return new FunctionAST(Proto, E); 1020 } 1021 return 0; 1022} 1023 1024/// external ::= 'extern' prototype 1025static PrototypeAST *ParseExtern() { 1026 getNextToken(); // eat extern. 1027 return ParsePrototype(); 1028} 1029 1030//===----------------------------------------------------------------------===// 1031// Code Generation 1032//===----------------------------------------------------------------------===// 1033 1034static Module *TheModule; 1035static IRBuilder<> Builder(getGlobalContext()); 1036static std::map<std::string, Value*> NamedValues; 1037 1038Value *ErrorV(const char *Str) { Error(Str); return 0; } 1039 1040Value *NumberExprAST::Codegen() { 1041 return ConstantFP::get(getGlobalContext(), APFloat(Val)); 1042} 1043 1044Value *VariableExprAST::Codegen() { 1045 // Look this variable up in the function. 1046 Value *V = NamedValues[Name]; 1047 return V ? V : ErrorV("Unknown variable name"); 1048} 1049 1050Value *BinaryExprAST::Codegen() { 1051 Value *L = LHS->Codegen(); 1052 Value *R = RHS->Codegen(); 1053 if (L == 0 || R == 0) return 0; 1054 1055 switch (Op) { 1056 case '+': return Builder.CreateFAdd(L, R, "addtmp"); 1057 case '-': return Builder.CreateFSub(L, R, "subtmp"); 1058 case '*': return Builder.CreateFMul(L, R, "multmp"); 1059 case '<': 1060 L = Builder.CreateFCmpULT(L, R, "cmptmp"); 1061 // Convert bool 0/1 to double 0.0 or 1.0 1062 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()), 1063 "booltmp"); 1064 default: return ErrorV("invalid binary operator"); 1065 } 1066} 1067 1068Value *CallExprAST::Codegen() { 1069 // Look up the name in the global module table. 1070 Function *CalleeF = TheModule->getFunction(Callee); 1071 if (CalleeF == 0) 1072 return ErrorV("Unknown function referenced"); 1073 1074 // If argument mismatch error. 1075 if (CalleeF->arg_size() != Args.size()) 1076 return ErrorV("Incorrect # arguments passed"); 1077 1078 std::vector<Value*> ArgsV; 1079 for (unsigned i = 0, e = Args.size(); i != e; ++i) { 1080 ArgsV.push_back(Args[i]->Codegen()); 1081 if (ArgsV.back() == 0) return 0; 1082 } 1083 1084 return Builder.CreateCall(CalleeF, ArgsV, "calltmp"); 1085} 1086 1087Function *PrototypeAST::Codegen() { 1088 // Make the function type: double(double,double) etc. 1089 std::vector<Type*> Doubles(Args.size(), 1090 Type::getDoubleTy(getGlobalContext())); 1091 FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()), 1092 Doubles, false); 1093 1094 Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule); 1095 1096 // If F conflicted, there was already something named 'Name'. If it has a 1097 // body, don't allow redefinition or reextern. 1098 if (F->getName() != Name) { 1099 // Delete the one we just made and get the existing one. 1100 F->eraseFromParent(); 1101 F = TheModule->getFunction(Name); 1102 1103 // If F already has a body, reject this. 1104 if (!F->empty()) { 1105 ErrorF("redefinition of function"); 1106 return 0; 1107 } 1108 1109 // If F took a different number of args, reject. 1110 if (F->arg_size() != Args.size()) { 1111 ErrorF("redefinition of function with different # args"); 1112 return 0; 1113 } 1114 } 1115 1116 // Set names for all arguments. 1117 unsigned Idx = 0; 1118 for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size(); 1119 ++AI, ++Idx) { 1120 AI->setName(Args[Idx]); 1121 1122 // Add arguments to variable symbol table. 1123 NamedValues[Args[Idx]] = AI; 1124 } 1125 1126 return F; 1127} 1128 1129Function *FunctionAST::Codegen() { 1130 NamedValues.clear(); 1131 1132 Function *TheFunction = Proto->Codegen(); 1133 if (TheFunction == 0) 1134 return 0; 1135 1136 // Create a new basic block to start insertion into. 1137 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction); 1138 Builder.SetInsertPoint(BB); 1139 1140 if (Value *RetVal = Body->Codegen()) { 1141 // Finish off the function. 1142 Builder.CreateRet(RetVal); 1143 1144 // Validate the generated code, checking for consistency. 1145 verifyFunction(*TheFunction); 1146 1147 return TheFunction; 1148 } 1149 1150 // Error reading body, remove function. 1151 TheFunction->eraseFromParent(); 1152 return 0; 1153} 1154 1155//===----------------------------------------------------------------------===// 1156// Top-Level parsing and JIT Driver 1157//===----------------------------------------------------------------------===// 1158 1159static void HandleDefinition() { 1160 if (FunctionAST *F = ParseDefinition()) { 1161 if (Function *LF = F->Codegen()) { 1162 fprintf(stderr, "Read function definition:"); 1163 LF->dump(); 1164 } 1165 } else { 1166 // Skip token for error recovery. 1167 getNextToken(); 1168 } 1169} 1170 1171static void HandleExtern() { 1172 if (PrototypeAST *P = ParseExtern()) { 1173 if (Function *F = P->Codegen()) { 1174 fprintf(stderr, "Read extern: "); 1175 F->dump(); 1176 } 1177 } else { 1178 // Skip token for error recovery. 1179 getNextToken(); 1180 } 1181} 1182 1183static void HandleTopLevelExpression() { 1184 // Evaluate a top-level expression into an anonymous function. 1185 if (FunctionAST *F = ParseTopLevelExpr()) { 1186 if (Function *LF = F->Codegen()) { 1187 fprintf(stderr, "Read top-level expression:"); 1188 LF->dump(); 1189 } 1190 } else { 1191 // Skip token for error recovery. 1192 getNextToken(); 1193 } 1194} 1195 1196/// top ::= definition | external | expression | ';' 1197static void MainLoop() { 1198 while (1) { 1199 fprintf(stderr, "ready> "); 1200 switch (CurTok) { 1201 case tok_eof: return; 1202 case ';': getNextToken(); break; // ignore top-level semicolons. 1203 case tok_def: HandleDefinition(); break; 1204 case tok_extern: HandleExtern(); break; 1205 default: HandleTopLevelExpression(); break; 1206 } 1207 } 1208} 1209 1210//===----------------------------------------------------------------------===// 1211// "Library" functions that can be "extern'd" from user code. 1212//===----------------------------------------------------------------------===// 1213 1214/// putchard - putchar that takes a double and returns 0. 1215extern "C" 1216double putchard(double X) { 1217 putchar((char)X); 1218 return 0; 1219} 1220 1221//===----------------------------------------------------------------------===// 1222// Main driver code. 1223//===----------------------------------------------------------------------===// 1224 1225int main() { 1226 LLVMContext &Context = getGlobalContext(); 1227 1228 // Install standard binary operators. 1229 // 1 is lowest precedence. 1230 BinopPrecedence['<'] = 10; 1231 BinopPrecedence['+'] = 20; 1232 BinopPrecedence['-'] = 20; 1233 BinopPrecedence['*'] = 40; // highest. 1234 1235 // Prime the first token. 1236 fprintf(stderr, "ready> "); 1237 getNextToken(); 1238 1239 // Make the module, which holds all the code. 1240 TheModule = new Module("my cool jit", Context); 1241 1242 // Run the main "interpreter loop" now. 1243 MainLoop(); 1244 1245 // Print out all of the generated code. 1246 TheModule->dump(); 1247 1248 return 0; 1249} 1250</pre> 1251</div> 1252<a href="LangImpl4.html">Next: Adding JIT and Optimizer Support</a> 1253</div> 1254 1255<!-- *********************************************************************** --> 1256<hr> 1257<address> 1258 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img 1259 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a> 1260 <a href="http://validator.w3.org/check/referer"><img 1261 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a> 1262 1263 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br> 1264 <a href="http://llvm.org/">The LLVM Compiler Infrastructure</a><br> 1265 Last modified: $Date$ 1266</address> 1267</body> 1268</html> 1269