1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
2 "http://www.w3.org/TR/html4/strict.dtd">
6 <title>Kaleidoscope: Extending the Language: Mutable Variables / SSA
8 <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
9 <meta name="author" content="Chris Lattner">
10 <link rel="stylesheet" href="../llvm.css" type="text/css">
15 <div class="doc_title">Kaleidoscope: Extending the Language: Mutable Variables</div>
18 <li><a href="index.html">Up to Tutorial Index</a></li>
21 <li><a href="#intro">Chapter 7 Introduction</a></li>
22 <li><a href="#why">Why is this a hard problem?</a></li>
23 <li><a href="#memory">Memory in LLVM</a></li>
24 <li><a href="#kalvars">Mutable Variables in Kaleidoscope</a></li>
25 <li><a href="#adjustments">Adjusting Existing Variables for
27 <li><a href="#assignment">New Assignment Operator</a></li>
28 <li><a href="#localvars">User-defined Local Variables</a></li>
29 <li><a href="#code">Full Code Listing</a></li>
32 <li><a href="LangImpl8.html">Chapter 8</a>: Conclusion and other useful LLVM
36 <div class="doc_author">
37 <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p>
40 <!-- *********************************************************************** -->
41 <div class="doc_section"><a name="intro">Chapter 7 Introduction</a></div>
42 <!-- *********************************************************************** -->
44 <div class="doc_text">
46 <p>Welcome to Chapter 7 of the "<a href="index.html">Implementing a language
47 with LLVM</a>" tutorial. In chapters 1 through 6, we've built a very
48 respectable, albeit simple, <a
49 href="http://en.wikipedia.org/wiki/Functional_programming">functional
50 programming language</a>. In our journey, we learned some parsing techniques,
51 how to build and represent an AST, how to build LLVM IR, and how to optimize
52 the resultant code as well as JIT compile it.</p>
54 <p>While Kaleidoscope is interesting as a functional language, the fact that it
55 is functional makes it "too easy" to generate LLVM IR for it. In particular, a
56 functional language makes it very easy to build LLVM IR directly in <a
57 href="http://en.wikipedia.org/wiki/Static_single_assignment_form">SSA form</a>.
58 Since LLVM requires that the input code be in SSA form, this is a very nice
59 property and it is often unclear to newcomers how to generate code for an
60 imperative language with mutable variables.</p>
62 <p>The short (and happy) summary of this chapter is that there is no need for
63 your front-end to build SSA form: LLVM provides highly tuned and well tested
64 support for this, though the way it works is a bit unexpected for some.</p>
68 <!-- *********************************************************************** -->
69 <div class="doc_section"><a name="why">Why is this a hard problem?</a></div>
70 <!-- *********************************************************************** -->
72 <div class="doc_text">
75 To understand why mutable variables cause complexities in SSA construction,
76 consider this extremely simple C example:
79 <div class="doc_code">
82 int test(_Bool Condition) {
93 <p>In this case, we have the variable "X", whose value depends on the path
94 executed in the program. Because there are two different possible values for X
95 before the return instruction, a PHI node is inserted to merge the two values.
96 The LLVM IR that we want for this example looks like this:</p>
98 <div class="doc_code">
100 @G = weak global i32 0 ; type of @G is i32*
101 @H = weak global i32 0 ; type of @H is i32*
103 define i32 @test(i1 %Condition) {
105 br i1 %Condition, label %cond_true, label %cond_false
116 %X.2 = phi i32 [ %X.1, %cond_false ], [ %X.0, %cond_true ]
122 <p>In this example, the loads from the G and H global variables are explicit in
123 the LLVM IR, and they live in the then/else branches of the if statement
124 (cond_true/cond_false). In order to merge the incoming values, the X.2 phi node
125 in the cond_next block selects the right value to use based on where control
126 flow is coming from: if control flow comes from the cond_false block, X.2 gets
127 the value of X.1. Alternatively, if control flow comes from cond_true, it gets
128 the value of X.0. The intent of this chapter is not to explain the details of
129 SSA form. For more information, see one of the many <a
130 href="http://en.wikipedia.org/wiki/Static_single_assignment_form">online
133 <p>The question for this article is "who places the phi nodes when lowering
134 assignments to mutable variables?". The issue here is that LLVM
135 <em>requires</em> that its IR be in SSA form: there is no "non-ssa" mode for it.
136 However, SSA construction requires non-trivial algorithms and data structures,
137 so it is inconvenient and wasteful for every front-end to have to reproduce this
142 <!-- *********************************************************************** -->
143 <div class="doc_section"><a name="memory">Memory in LLVM</a></div>
144 <!-- *********************************************************************** -->
146 <div class="doc_text">
148 <p>The 'trick' here is that while LLVM does require all register values to be
149 in SSA form, it does not require (or permit) memory objects to be in SSA form.
150 In the example above, note that the loads from G and H are direct accesses to
151 G and H: they are not renamed or versioned. This differs from some other
152 compiler systems, which do try to version memory objects. In LLVM, instead of
153 encoding dataflow analysis of memory into the LLVM IR, it is handled with <a
154 href="../WritingAnLLVMPass.html">Analysis Passes</a> which are computed on
158 With this in mind, the high-level idea is that we want to make a stack variable
159 (which lives in memory, because it is on the stack) for each mutable object in
160 a function. To take advantage of this trick, we need to talk about how LLVM
161 represents stack variables.
164 <p>In LLVM, all memory accesses are explicit with load/store instructions, and
165 it is carefully designed not to have (or need) an "address-of" operator. Notice
166 how the type of the @G/@H global variables is actually "i32*" even though the
167 variable is defined as "i32". What this means is that @G defines <em>space</em>
168 for an i32 in the global data area, but its <em>name</em> actually refers to the
169 address for that space. Stack variables work the same way, except that instead of
170 being declared with global variable definitions, they are declared with the
171 <a href="../LangRef.html#i_alloca">LLVM alloca instruction</a>:</p>
173 <div class="doc_code">
175 define i32 @example() {
177 %X = alloca i32 ; type of %X is i32*.
179 %tmp = load i32* %X ; load the stack value %X from the stack.
180 %tmp2 = add i32 %tmp, 1 ; increment it
181 store i32 %tmp2, i32* %X ; store it back
186 <p>This code shows an example of how you can declare and manipulate a stack
187 variable in the LLVM IR. Stack memory allocated with the alloca instruction is
188 fully general: you can pass the address of the stack slot to functions, you can
189 store it in other variables, etc. In our example above, we could rewrite the
190 example to use the alloca technique to avoid using a PHI node:</p>
192 <div class="doc_code">
194 @G = weak global i32 0 ; type of @G is i32*
195 @H = weak global i32 0 ; type of @H is i32*
197 define i32 @test(i1 %Condition) {
199 %X = alloca i32 ; type of %X is i32*.
200 br i1 %Condition, label %cond_true, label %cond_false
204 store i32 %X.0, i32* %X ; Update X
209 store i32 %X.1, i32* %X ; Update X
213 %X.2 = load i32* %X ; Read X
219 <p>With this, we have discovered a way to handle arbitrary mutable variables
220 without the need to create Phi nodes at all:</p>
223 <li>Each mutable variable becomes a stack allocation.</li>
224 <li>Each read of the variable becomes a load from the stack.</li>
225 <li>Each update of the variable becomes a store to the stack.</li>
226 <li>Taking the address of a variable just uses the stack address directly.</li>
229 <p>While this solution has solved our immediate problem, it introduced another
230 one: we have now apparently introduced a lot of stack traffic for very simple
231 and common operations, a major performance problem. Fortunately for us, the
232 LLVM optimizer has a highly-tuned optimization pass named "mem2reg" that handles
233 this case, promoting allocas like this into SSA registers, inserting Phi nodes
234 as appropriate. If you run this example through the pass, for example, you'll
237 <div class="doc_code">
239 $ <b>llvm-as < example.ll | opt -mem2reg | llvm-dis</b>
240 @G = weak global i32 0
241 @H = weak global i32 0
243 define i32 @test(i1 %Condition) {
245 br i1 %Condition, label %cond_true, label %cond_false
256 %X.01 = phi i32 [ %X.1, %cond_false ], [ %X.0, %cond_true ]
262 <p>The mem2reg pass implements the standard "iterated dominance frontier"
263 algorithm for constructing SSA form and has a number of optimizations that speed
264 up (very common) degenerate cases. The mem2reg optimization pass is the answer to dealing
265 with mutable variables, and we highly recommend that you depend on it. Note that
266 mem2reg only works on variables in certain circumstances:</p>
269 <li>mem2reg is alloca-driven: it looks for allocas and if it can handle them, it
270 promotes them. It does not apply to global variables or heap allocations.</li>
272 <li>mem2reg only looks for alloca instructions in the entry block of the
273 function. Being in the entry block guarantees that the alloca is only executed
274 once, which makes analysis simpler.</li>
276 <li>mem2reg only promotes allocas whose uses are direct loads and stores. If
277 the address of the stack object is passed to a function, or if any funny pointer
278 arithmetic is involved, the alloca will not be promoted.</li>
280 <li>mem2reg only works on allocas of <a
281 href="../LangRef.html#t_classifications">first class</a>
282 values (such as pointers, scalars and vectors), and only if the array size
283 of the allocation is 1 (or missing in the .ll file). mem2reg is not capable of
284 promoting structs or arrays to registers. Note that the "scalarrepl" pass is
285 more powerful and can promote structs, "unions", and arrays in many cases.</li>
290 All of these properties are easy to satisfy for most imperative languages, and
291 we'll illustrate it below with Kaleidoscope. The final question you may be
292 asking is: should I bother with this nonsense for my front-end? Wouldn't it be
293 better if I just did SSA construction directly, avoiding use of the mem2reg
294 optimization pass? In short, we strongly recommend that you use this technique
295 for building SSA form, unless there is an extremely good reason not to. Using
296 this technique is:</p>
299 <li>Proven and well tested: llvm-gcc and clang both use this technique for local
300 mutable variables. As such, the most common clients of LLVM are using this to
301 handle a bulk of their variables. You can be sure that bugs are found fast and
304 <li>Extremely Fast: mem2reg has a number of special cases that make it fast in
305 common cases as well as fully general. For example, it has fast-paths for
306 variables that are only used in a single block, variables that only have one
307 assignment point, good heuristics to avoid insertion of unneeded phi nodes, etc.
310 <li>Needed for debug info generation: <a href="../SourceLevelDebugging.html">
311 Debug information in LLVM</a> relies on having the address of the variable
312 exposed so that debug info can be attached to it. This technique dovetails
313 very naturally with this style of debug info.</li>
316 <p>If nothing else, this makes it much easier to get your front-end up and
317 running, and is very simple to implement. Lets extend Kaleidoscope with mutable
323 <!-- *********************************************************************** -->
324 <div class="doc_section"><a name="kalvars">Mutable Variables in
325 Kaleidoscope</a></div>
326 <!-- *********************************************************************** -->
328 <div class="doc_text">
330 <p>Now that we know the sort of problem we want to tackle, lets see what this
331 looks like in the context of our little Kaleidoscope language. We're going to
332 add two features:</p>
335 <li>The ability to mutate variables with the '=' operator.</li>
336 <li>The ability to define new variables.</li>
339 <p>While the first item is really what this is about, we only have variables
340 for incoming arguments as well as for induction variables, and redefining those only
341 goes so far :). Also, the ability to define new variables is a
342 useful thing regardless of whether you will be mutating them. Here's a
343 motivating example that shows how we could use these:</p>
345 <div class="doc_code">
347 # Define ':' for sequencing: as a low-precedence operator that ignores operands
348 # and just returns the RHS.
349 def binary : 1 (x y) y;
351 # Recursive fib, we could do this before.
360 <b>var a = 1, b = 1, c in</b>
361 (for i = 3, i < x in
373 In order to mutate variables, we have to change our existing variables to use
374 the "alloca trick". Once we have that, we'll add our new operator, then extend
375 Kaleidoscope to support new variable definitions.
380 <!-- *********************************************************************** -->
381 <div class="doc_section"><a name="adjustments">Adjusting Existing Variables for
383 <!-- *********************************************************************** -->
385 <div class="doc_text">
388 The symbol table in Kaleidoscope is managed at code generation time by the
389 '<tt>NamedValues</tt>' map. This map currently keeps track of the LLVM "Value*"
390 that holds the double value for the named variable. In order to support
391 mutation, we need to change this slightly, so that it <tt>NamedValues</tt> holds
392 the <em>memory location</em> of the variable in question. Note that this
393 change is a refactoring: it changes the structure of the code, but does not
394 (by itself) change the behavior of the compiler. All of these changes are
395 isolated in the Kaleidoscope code generator.</p>
398 At this point in Kaleidoscope's development, it only supports variables for two
399 things: incoming arguments to functions and the induction variable of 'for'
400 loops. For consistency, we'll allow mutation of these variables in addition to
401 other user-defined variables. This means that these will both need memory
405 <p>To start our transformation of Kaleidoscope, we'll change the NamedValues
406 map so that it maps to AllocaInst* instead of Value*. Once we do this, the C++
407 compiler will tell us what parts of the code we need to update:</p>
409 <div class="doc_code">
411 static std::map<std::string, AllocaInst*> NamedValues;
415 <p>Also, since we will need to create these alloca's, we'll use a helper
416 function that ensures that the allocas are created in the entry block of the
419 <div class="doc_code">
421 /// CreateEntryBlockAlloca - Create an alloca instruction in the entry block of
422 /// the function. This is used for mutable variables etc.
423 static AllocaInst *CreateEntryBlockAlloca(Function *TheFunction,
424 const std::string &VarName) {
425 IRBuilder<> TmpB(&TheFunction->getEntryBlock(),
426 TheFunction->getEntryBlock().begin());
427 return TmpB.CreateAlloca(Type::getDoubleTy(getGlobalContext()), 0,
433 <p>This funny looking code creates an IRBuilder object that is pointing at
434 the first instruction (.begin()) of the entry block. It then creates an alloca
435 with the expected name and returns it. Because all values in Kaleidoscope are
436 doubles, there is no need to pass in a type to use.</p>
438 <p>With this in place, the first functionality change we want to make is to
439 variable references. In our new scheme, variables live on the stack, so code
440 generating a reference to them actually needs to produce a load from the stack
443 <div class="doc_code">
445 Value *VariableExprAST::Codegen() {
446 // Look this variable up in the function.
447 Value *V = NamedValues[Name];
448 if (V == 0) return ErrorV("Unknown variable name");
450 <b>// Load the value.
451 return Builder.CreateLoad(V, Name.c_str());</b>
456 <p>As you can see, this is pretty straightforward. Now we need to update the
457 things that define the variables to set up the alloca. We'll start with
458 <tt>ForExprAST::Codegen</tt> (see the <a href="#code">full code listing</a> for
459 the unabridged code):</p>
461 <div class="doc_code">
463 Function *TheFunction = Builder.GetInsertBlock()->getParent();
465 <b>// Create an alloca for the variable in the entry block.
466 AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);</b>
468 // Emit the start code first, without 'variable' in scope.
469 Value *StartVal = Start->Codegen();
470 if (StartVal == 0) return 0;
472 <b>// Store the value into the alloca.
473 Builder.CreateStore(StartVal, Alloca);</b>
476 // Compute the end condition.
477 Value *EndCond = End->Codegen();
478 if (EndCond == 0) return EndCond;
480 <b>// Reload, increment, and restore the alloca. This handles the case where
481 // the body of the loop mutates the variable.
482 Value *CurVar = Builder.CreateLoad(Alloca);
483 Value *NextVar = Builder.CreateAdd(CurVar, StepVal, "nextvar");
484 Builder.CreateStore(NextVar, Alloca);</b>
489 <p>This code is virtually identical to the code <a
490 href="LangImpl5.html#forcodegen">before we allowed mutable variables</a>. The
491 big difference is that we no longer have to construct a PHI node, and we use
492 load/store to access the variable as needed.</p>
494 <p>To support mutable argument variables, we need to also make allocas for them.
495 The code for this is also pretty simple:</p>
497 <div class="doc_code">
499 /// CreateArgumentAllocas - Create an alloca for each argument and register the
500 /// argument in the symbol table so that references to it will succeed.
501 void PrototypeAST::CreateArgumentAllocas(Function *F) {
502 Function::arg_iterator AI = F->arg_begin();
503 for (unsigned Idx = 0, e = Args.size(); Idx != e; ++Idx, ++AI) {
504 // Create an alloca for this variable.
505 AllocaInst *Alloca = CreateEntryBlockAlloca(F, Args[Idx]);
507 // Store the initial value into the alloca.
508 Builder.CreateStore(AI, Alloca);
510 // Add arguments to variable symbol table.
511 NamedValues[Args[Idx]] = Alloca;
517 <p>For each argument, we make an alloca, store the input value to the function
518 into the alloca, and register the alloca as the memory location for the
519 argument. This method gets invoked by <tt>FunctionAST::Codegen</tt> right after
520 it sets up the entry block for the function.</p>
522 <p>The final missing piece is adding the mem2reg pass, which allows us to get
523 good codegen once again:</p>
525 <div class="doc_code">
527 // Set up the optimizer pipeline. Start with registering info about how the
528 // target lays out data structures.
529 OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData()));
530 <b>// Promote allocas to registers.
531 OurFPM.add(createPromoteMemoryToRegisterPass());</b>
532 // Do simple "peephole" optimizations and bit-twiddling optzns.
533 OurFPM.add(createInstructionCombiningPass());
534 // Reassociate expressions.
535 OurFPM.add(createReassociatePass());
539 <p>It is interesting to see what the code looks like before and after the
540 mem2reg optimization runs. For example, this is the before/after code for our
541 recursive fib function. Before the optimization:</p>
543 <div class="doc_code">
545 define double @fib(double %x) {
547 <b>%x1 = alloca double
548 store double %x, double* %x1
549 %x2 = load double* %x1</b>
550 %cmptmp = fcmp ult double %x2, 3.000000e+00
551 %booltmp = uitofp i1 %cmptmp to double
552 %ifcond = fcmp one double %booltmp, 0.000000e+00
553 br i1 %ifcond, label %then, label %else
555 then: ; preds = %entry
558 else: ; preds = %entry
559 <b>%x3 = load double* %x1</b>
560 %subtmp = sub double %x3, 1.000000e+00
561 %calltmp = call double @fib( double %subtmp )
562 <b>%x4 = load double* %x1</b>
563 %subtmp5 = sub double %x4, 2.000000e+00
564 %calltmp6 = call double @fib( double %subtmp5 )
565 %addtmp = add double %calltmp, %calltmp6
568 ifcont: ; preds = %else, %then
569 %iftmp = phi double [ 1.000000e+00, %then ], [ %addtmp, %else ]
575 <p>Here there is only one variable (x, the input argument) but you can still
576 see the extremely simple-minded code generation strategy we are using. In the
577 entry block, an alloca is created, and the initial input value is stored into
578 it. Each reference to the variable does a reload from the stack. Also, note
579 that we didn't modify the if/then/else expression, so it still inserts a PHI
580 node. While we could make an alloca for it, it is actually easier to create a
581 PHI node for it, so we still just make the PHI.</p>
583 <p>Here is the code after the mem2reg pass runs:</p>
585 <div class="doc_code">
587 define double @fib(double %x) {
589 %cmptmp = fcmp ult double <b>%x</b>, 3.000000e+00
590 %booltmp = uitofp i1 %cmptmp to double
591 %ifcond = fcmp one double %booltmp, 0.000000e+00
592 br i1 %ifcond, label %then, label %else
598 %subtmp = sub double <b>%x</b>, 1.000000e+00
599 %calltmp = call double @fib( double %subtmp )
600 %subtmp5 = sub double <b>%x</b>, 2.000000e+00
601 %calltmp6 = call double @fib( double %subtmp5 )
602 %addtmp = add double %calltmp, %calltmp6
605 ifcont: ; preds = %else, %then
606 %iftmp = phi double [ 1.000000e+00, %then ], [ %addtmp, %else ]
612 <p>This is a trivial case for mem2reg, since there are no redefinitions of the
613 variable. The point of showing this is to calm your tension about inserting
614 such blatent inefficiencies :).</p>
616 <p>After the rest of the optimizers run, we get:</p>
618 <div class="doc_code">
620 define double @fib(double %x) {
622 %cmptmp = fcmp ult double %x, 3.000000e+00
623 %booltmp = uitofp i1 %cmptmp to double
624 %ifcond = fcmp ueq double %booltmp, 0.000000e+00
625 br i1 %ifcond, label %else, label %ifcont
628 %subtmp = sub double %x, 1.000000e+00
629 %calltmp = call double @fib( double %subtmp )
630 %subtmp5 = sub double %x, 2.000000e+00
631 %calltmp6 = call double @fib( double %subtmp5 )
632 %addtmp = add double %calltmp, %calltmp6
636 ret double 1.000000e+00
641 <p>Here we see that the simplifycfg pass decided to clone the return instruction
642 into the end of the 'else' block. This allowed it to eliminate some branches
643 and the PHI node.</p>
645 <p>Now that all symbol table references are updated to use stack variables,
646 we'll add the assignment operator.</p>
650 <!-- *********************************************************************** -->
651 <div class="doc_section"><a name="assignment">New Assignment Operator</a></div>
652 <!-- *********************************************************************** -->
654 <div class="doc_text">
656 <p>With our current framework, adding a new assignment operator is really
657 simple. We will parse it just like any other binary operator, but handle it
658 internally (instead of allowing the user to define it). The first step is to
659 set a precedence:</p>
661 <div class="doc_code">
664 // Install standard binary operators.
665 // 1 is lowest precedence.
666 <b>BinopPrecedence['='] = 2;</b>
667 BinopPrecedence['<'] = 10;
668 BinopPrecedence['+'] = 20;
669 BinopPrecedence['-'] = 20;
673 <p>Now that the parser knows the precedence of the binary operator, it takes
674 care of all the parsing and AST generation. We just need to implement codegen
675 for the assignment operator. This looks like:</p>
677 <div class="doc_code">
679 Value *BinaryExprAST::Codegen() {
680 // Special case '=' because we don't want to emit the LHS as an expression.
682 // Assignment requires the LHS to be an identifier.
683 VariableExprAST *LHSE = dynamic_cast<VariableExprAST*>(LHS);
685 return ErrorV("destination of '=' must be a variable");
689 <p>Unlike the rest of the binary operators, our assignment operator doesn't
690 follow the "emit LHS, emit RHS, do computation" model. As such, it is handled
691 as a special case before the other binary operators are handled. The other
692 strange thing is that it requires the LHS to be a variable. It is invalid to
693 have "(x+1) = expr" - only things like "x = expr" are allowed.
696 <div class="doc_code">
699 Value *Val = RHS->Codegen();
700 if (Val == 0) return 0;
703 Value *Variable = NamedValues[LHSE->getName()];
704 if (Variable == 0) return ErrorV("Unknown variable name");
706 Builder.CreateStore(Val, Variable);
713 <p>Once we have the variable, codegen'ing the assignment is straightforward:
714 we emit the RHS of the assignment, create a store, and return the computed
715 value. Returning a value allows for chained assignments like "X = (Y = Z)".</p>
717 <p>Now that we have an assignment operator, we can mutate loop variables and
718 arguments. For example, we can now run code like this:</p>
720 <div class="doc_code">
722 # Function to print a double.
725 # Define ':' for sequencing: as a low-precedence operator that ignores operands
726 # and just returns the RHS.
727 def binary : 1 (x y) y;
738 <p>When run, this example prints "123" and then "4", showing that we did
739 actually mutate the value! Okay, we have now officially implemented our goal:
740 getting this to work requires SSA construction in the general case. However,
741 to be really useful, we want the ability to define our own local variables, lets
747 <!-- *********************************************************************** -->
748 <div class="doc_section"><a name="localvars">User-defined Local
750 <!-- *********************************************************************** -->
752 <div class="doc_text">
754 <p>Adding var/in is just like any other other extensions we made to
755 Kaleidoscope: we extend the lexer, the parser, the AST and the code generator.
756 The first step for adding our new 'var/in' construct is to extend the lexer.
757 As before, this is pretty trivial, the code looks like this:</p>
759 <div class="doc_code">
768 static int gettok() {
770 if (IdentifierStr == "in") return tok_in;
771 if (IdentifierStr == "binary") return tok_binary;
772 if (IdentifierStr == "unary") return tok_unary;
773 <b>if (IdentifierStr == "var") return tok_var;</b>
774 return tok_identifier;
779 <p>The next step is to define the AST node that we will construct. For var/in,
780 it looks like this:</p>
782 <div class="doc_code">
784 /// VarExprAST - Expression class for var/in
785 class VarExprAST : public ExprAST {
786 std::vector<std::pair<std::string, ExprAST*> > VarNames;
789 VarExprAST(const std::vector<std::pair<std::string, ExprAST*> > &varnames,
791 : VarNames(varnames), Body(body) {}
793 virtual Value *Codegen();
798 <p>var/in allows a list of names to be defined all at once, and each name can
799 optionally have an initializer value. As such, we capture this information in
800 the VarNames vector. Also, var/in has a body, this body is allowed to access
801 the variables defined by the var/in.</p>
803 <p>With this in place, we can define the parser pieces. The first thing we do is add
804 it as a primary expression:</p>
806 <div class="doc_code">
809 /// ::= identifierexpr
814 <b>/// ::= varexpr</b>
815 static ExprAST *ParsePrimary() {
817 default: return Error("unknown token when expecting an expression");
818 case tok_identifier: return ParseIdentifierExpr();
819 case tok_number: return ParseNumberExpr();
820 case '(': return ParseParenExpr();
821 case tok_if: return ParseIfExpr();
822 case tok_for: return ParseForExpr();
823 <b>case tok_var: return ParseVarExpr();</b>
829 <p>Next we define ParseVarExpr:</p>
831 <div class="doc_code">
833 /// varexpr ::= 'var' identifier ('=' expression)?
834 // (',' identifier ('=' expression)?)* 'in' expression
835 static ExprAST *ParseVarExpr() {
836 getNextToken(); // eat the var.
838 std::vector<std::pair<std::string, ExprAST*> > VarNames;
840 // At least one variable name is required.
841 if (CurTok != tok_identifier)
842 return Error("expected identifier after var");
846 <p>The first part of this code parses the list of identifier/expr pairs into the
847 local <tt>VarNames</tt> vector.
849 <div class="doc_code">
852 std::string Name = IdentifierStr;
853 getNextToken(); // eat identifier.
855 // Read the optional initializer.
858 getNextToken(); // eat the '='.
860 Init = ParseExpression();
861 if (Init == 0) return 0;
864 VarNames.push_back(std::make_pair(Name, Init));
866 // End of var list, exit loop.
867 if (CurTok != ',') break;
868 getNextToken(); // eat the ','.
870 if (CurTok != tok_identifier)
871 return Error("expected identifier list after var");
876 <p>Once all the variables are parsed, we then parse the body and create the
879 <div class="doc_code">
881 // At this point, we have to have 'in'.
882 if (CurTok != tok_in)
883 return Error("expected 'in' keyword after 'var'");
884 getNextToken(); // eat 'in'.
886 ExprAST *Body = ParseExpression();
887 if (Body == 0) return 0;
889 return new VarExprAST(VarNames, Body);
894 <p>Now that we can parse and represent the code, we need to support emission of
895 LLVM IR for it. This code starts out with:</p>
897 <div class="doc_code">
899 Value *VarExprAST::Codegen() {
900 std::vector<AllocaInst *> OldBindings;
902 Function *TheFunction = Builder.GetInsertBlock()->getParent();
904 // Register all variables and emit their initializer.
905 for (unsigned i = 0, e = VarNames.size(); i != e; ++i) {
906 const std::string &VarName = VarNames[i].first;
907 ExprAST *Init = VarNames[i].second;
911 <p>Basically it loops over all the variables, installing them one at a time.
912 For each variable we put into the symbol table, we remember the previous value
913 that we replace in OldBindings.</p>
915 <div class="doc_code">
917 // Emit the initializer before adding the variable to scope, this prevents
918 // the initializer from referencing the variable itself, and permits stuff
921 // var a = a in ... # refers to outer 'a'.
924 InitVal = Init->Codegen();
925 if (InitVal == 0) return 0;
926 } else { // If not specified, use 0.0.
927 InitVal = ConstantFP::get(getGlobalContext(), APFloat(0.0));
930 AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);
931 Builder.CreateStore(InitVal, Alloca);
933 // Remember the old variable binding so that we can restore the binding when
935 OldBindings.push_back(NamedValues[VarName]);
937 // Remember this binding.
938 NamedValues[VarName] = Alloca;
943 <p>There are more comments here than code. The basic idea is that we emit the
944 initializer, create the alloca, then update the symbol table to point to it.
945 Once all the variables are installed in the symbol table, we evaluate the body
946 of the var/in expression:</p>
948 <div class="doc_code">
950 // Codegen the body, now that all vars are in scope.
951 Value *BodyVal = Body->Codegen();
952 if (BodyVal == 0) return 0;
956 <p>Finally, before returning, we restore the previous variable bindings:</p>
958 <div class="doc_code">
960 // Pop all our variables from scope.
961 for (unsigned i = 0, e = VarNames.size(); i != e; ++i)
962 NamedValues[VarNames[i].first] = OldBindings[i];
964 // Return the body computation.
970 <p>The end result of all of this is that we get properly scoped variable
971 definitions, and we even (trivially) allow mutation of them :).</p>
973 <p>With this, we completed what we set out to do. Our nice iterative fib
974 example from the intro compiles and runs just fine. The mem2reg pass optimizes
975 all of our stack variables into SSA registers, inserting PHI nodes where needed,
976 and our front-end remains simple: no "iterated dominance frontier" computation
977 anywhere in sight.</p>
981 <!-- *********************************************************************** -->
982 <div class="doc_section"><a name="code">Full Code Listing</a></div>
983 <!-- *********************************************************************** -->
985 <div class="doc_text">
988 Here is the complete code listing for our running example, enhanced with mutable
989 variables and var/in support. To build this example, use:
992 <div class="doc_code">
995 g++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o toy
1001 <p>Here is the code:</p>
1003 <div class="doc_code">
1005 #include "llvm/DerivedTypes.h"
1006 #include "llvm/ExecutionEngine/ExecutionEngine.h"
1007 #include "llvm/ExecutionEngine/Interpreter.h"
1008 #include "llvm/ExecutionEngine/JIT.h"
1009 #include "llvm/LLVMContext.h"
1010 #include "llvm/Module.h"
1011 #include "llvm/ModuleProvider.h"
1012 #include "llvm/PassManager.h"
1013 #include "llvm/Analysis/Verifier.h"
1014 #include "llvm/Target/TargetData.h"
1015 #include "llvm/Target/TargetSelect.h"
1016 #include "llvm/Transforms/Scalar.h"
1017 #include "llvm/Support/IRBuilder.h"
1018 #include <cstdio>
1019 #include <string>
1020 #include <map>
1021 #include <vector>
1022 using namespace llvm;
1024 //===----------------------------------------------------------------------===//
1026 //===----------------------------------------------------------------------===//
1028 // The lexer returns tokens [0-255] if it is an unknown character, otherwise one
1029 // of these for known things.
1034 tok_def = -2, tok_extern = -3,
1037 tok_identifier = -4, tok_number = -5,
1040 tok_if = -6, tok_then = -7, tok_else = -8,
1041 tok_for = -9, tok_in = -10,
1044 tok_binary = -11, tok_unary = -12,
1050 static std::string IdentifierStr; // Filled in if tok_identifier
1051 static double NumVal; // Filled in if tok_number
1053 /// gettok - Return the next token from standard input.
1054 static int gettok() {
1055 static int LastChar = ' ';
1057 // Skip any whitespace.
1058 while (isspace(LastChar))
1059 LastChar = getchar();
1061 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
1062 IdentifierStr = LastChar;
1063 while (isalnum((LastChar = getchar())))
1064 IdentifierStr += LastChar;
1066 if (IdentifierStr == "def") return tok_def;
1067 if (IdentifierStr == "extern") return tok_extern;
1068 if (IdentifierStr == "if") return tok_if;
1069 if (IdentifierStr == "then") return tok_then;
1070 if (IdentifierStr == "else") return tok_else;
1071 if (IdentifierStr == "for") return tok_for;
1072 if (IdentifierStr == "in") return tok_in;
1073 if (IdentifierStr == "binary") return tok_binary;
1074 if (IdentifierStr == "unary") return tok_unary;
1075 if (IdentifierStr == "var") return tok_var;
1076 return tok_identifier;
1079 if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+
1083 LastChar = getchar();
1084 } while (isdigit(LastChar) || LastChar == '.');
1086 NumVal = strtod(NumStr.c_str(), 0);
1090 if (LastChar == '#') {
1091 // Comment until end of line.
1092 do LastChar = getchar();
1093 while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');
1095 if (LastChar != EOF)
1099 // Check for end of file. Don't eat the EOF.
1100 if (LastChar == EOF)
1103 // Otherwise, just return the character as its ascii value.
1104 int ThisChar = LastChar;
1105 LastChar = getchar();
1109 //===----------------------------------------------------------------------===//
1110 // Abstract Syntax Tree (aka Parse Tree)
1111 //===----------------------------------------------------------------------===//
1113 /// ExprAST - Base class for all expression nodes.
1116 virtual ~ExprAST() {}
1117 virtual Value *Codegen() = 0;
1120 /// NumberExprAST - Expression class for numeric literals like "1.0".
1121 class NumberExprAST : public ExprAST {
1124 NumberExprAST(double val) : Val(val) {}
1125 virtual Value *Codegen();
1128 /// VariableExprAST - Expression class for referencing a variable, like "a".
1129 class VariableExprAST : public ExprAST {
1132 VariableExprAST(const std::string &name) : Name(name) {}
1133 const std::string &getName() const { return Name; }
1134 virtual Value *Codegen();
1137 /// UnaryExprAST - Expression class for a unary operator.
1138 class UnaryExprAST : public ExprAST {
1142 UnaryExprAST(char opcode, ExprAST *operand)
1143 : Opcode(opcode), Operand(operand) {}
1144 virtual Value *Codegen();
1147 /// BinaryExprAST - Expression class for a binary operator.
1148 class BinaryExprAST : public ExprAST {
1152 BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
1153 : Op(op), LHS(lhs), RHS(rhs) {}
1154 virtual Value *Codegen();
1157 /// CallExprAST - Expression class for function calls.
1158 class CallExprAST : public ExprAST {
1160 std::vector<ExprAST*> Args;
1162 CallExprAST(const std::string &callee, std::vector<ExprAST*> &args)
1163 : Callee(callee), Args(args) {}
1164 virtual Value *Codegen();
1167 /// IfExprAST - Expression class for if/then/else.
1168 class IfExprAST : public ExprAST {
1169 ExprAST *Cond, *Then, *Else;
1171 IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
1172 : Cond(cond), Then(then), Else(_else) {}
1173 virtual Value *Codegen();
1176 /// ForExprAST - Expression class for for/in.
1177 class ForExprAST : public ExprAST {
1178 std::string VarName;
1179 ExprAST *Start, *End, *Step, *Body;
1181 ForExprAST(const std::string &varname, ExprAST *start, ExprAST *end,
1182 ExprAST *step, ExprAST *body)
1183 : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
1184 virtual Value *Codegen();
1187 /// VarExprAST - Expression class for var/in
1188 class VarExprAST : public ExprAST {
1189 std::vector<std::pair<std::string, ExprAST*> > VarNames;
1192 VarExprAST(const std::vector<std::pair<std::string, ExprAST*> > &varnames,
1194 : VarNames(varnames), Body(body) {}
1196 virtual Value *Codegen();
1199 /// PrototypeAST - This class represents the "prototype" for a function,
1200 /// which captures its name, and its argument names (thus implicitly the number
1201 /// of arguments the function takes), as well as if it is an operator.
1202 class PrototypeAST {
1204 std::vector<std::string> Args;
1206 unsigned Precedence; // Precedence if a binary op.
1208 PrototypeAST(const std::string &name, const std::vector<std::string> &args,
1209 bool isoperator = false, unsigned prec = 0)
1210 : Name(name), Args(args), isOperator(isoperator), Precedence(prec) {}
1212 bool isUnaryOp() const { return isOperator && Args.size() == 1; }
1213 bool isBinaryOp() const { return isOperator && Args.size() == 2; }
1215 char getOperatorName() const {
1216 assert(isUnaryOp() || isBinaryOp());
1217 return Name[Name.size()-1];
1220 unsigned getBinaryPrecedence() const { return Precedence; }
1222 Function *Codegen();
1224 void CreateArgumentAllocas(Function *F);
1227 /// FunctionAST - This class represents a function definition itself.
1229 PrototypeAST *Proto;
1232 FunctionAST(PrototypeAST *proto, ExprAST *body)
1233 : Proto(proto), Body(body) {}
1235 Function *Codegen();
1238 //===----------------------------------------------------------------------===//
1240 //===----------------------------------------------------------------------===//
1242 /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
1243 /// token the parser is looking at. getNextToken reads another token from the
1244 /// lexer and updates CurTok with its results.
1246 static int getNextToken() {
1247 return CurTok = gettok();
1250 /// BinopPrecedence - This holds the precedence for each binary operator that is
1252 static std::map<char, int> BinopPrecedence;
1254 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
1255 static int GetTokPrecedence() {
1256 if (!isascii(CurTok))
1259 // Make sure it's a declared binop.
1260 int TokPrec = BinopPrecedence[CurTok];
1261 if (TokPrec <= 0) return -1;
1265 /// Error* - These are little helper functions for error handling.
1266 ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
1267 PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
1268 FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
1270 static ExprAST *ParseExpression();
1274 /// ::= identifier '(' expression* ')'
1275 static ExprAST *ParseIdentifierExpr() {
1276 std::string IdName = IdentifierStr;
1278 getNextToken(); // eat identifier.
1280 if (CurTok != '(') // Simple variable ref.
1281 return new VariableExprAST(IdName);
1284 getNextToken(); // eat (
1285 std::vector<ExprAST*> Args;
1286 if (CurTok != ')') {
1288 ExprAST *Arg = ParseExpression();
1290 Args.push_back(Arg);
1292 if (CurTok == ')') break;
1295 return Error("Expected ')' or ',' in argument list");
1303 return new CallExprAST(IdName, Args);
1306 /// numberexpr ::= number
1307 static ExprAST *ParseNumberExpr() {
1308 ExprAST *Result = new NumberExprAST(NumVal);
1309 getNextToken(); // consume the number
1313 /// parenexpr ::= '(' expression ')'
1314 static ExprAST *ParseParenExpr() {
1315 getNextToken(); // eat (.
1316 ExprAST *V = ParseExpression();
1320 return Error("expected ')'");
1321 getNextToken(); // eat ).
1325 /// ifexpr ::= 'if' expression 'then' expression 'else' expression
1326 static ExprAST *ParseIfExpr() {
1327 getNextToken(); // eat the if.
1330 ExprAST *Cond = ParseExpression();
1331 if (!Cond) return 0;
1333 if (CurTok != tok_then)
1334 return Error("expected then");
1335 getNextToken(); // eat the then
1337 ExprAST *Then = ParseExpression();
1338 if (Then == 0) return 0;
1340 if (CurTok != tok_else)
1341 return Error("expected else");
1345 ExprAST *Else = ParseExpression();
1346 if (!Else) return 0;
1348 return new IfExprAST(Cond, Then, Else);
1351 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
1352 static ExprAST *ParseForExpr() {
1353 getNextToken(); // eat the for.
1355 if (CurTok != tok_identifier)
1356 return Error("expected identifier after for");
1358 std::string IdName = IdentifierStr;
1359 getNextToken(); // eat identifier.
1362 return Error("expected '=' after for");
1363 getNextToken(); // eat '='.
1366 ExprAST *Start = ParseExpression();
1367 if (Start == 0) return 0;
1369 return Error("expected ',' after for start value");
1372 ExprAST *End = ParseExpression();
1373 if (End == 0) return 0;
1375 // The step value is optional.
1377 if (CurTok == ',') {
1379 Step = ParseExpression();
1380 if (Step == 0) return 0;
1383 if (CurTok != tok_in)
1384 return Error("expected 'in' after for");
1385 getNextToken(); // eat 'in'.
1387 ExprAST *Body = ParseExpression();
1388 if (Body == 0) return 0;
1390 return new ForExprAST(IdName, Start, End, Step, Body);
1393 /// varexpr ::= 'var' identifier ('=' expression)?
1394 // (',' identifier ('=' expression)?)* 'in' expression
1395 static ExprAST *ParseVarExpr() {
1396 getNextToken(); // eat the var.
1398 std::vector<std::pair<std::string, ExprAST*> > VarNames;
1400 // At least one variable name is required.
1401 if (CurTok != tok_identifier)
1402 return Error("expected identifier after var");
1405 std::string Name = IdentifierStr;
1406 getNextToken(); // eat identifier.
1408 // Read the optional initializer.
1410 if (CurTok == '=') {
1411 getNextToken(); // eat the '='.
1413 Init = ParseExpression();
1414 if (Init == 0) return 0;
1417 VarNames.push_back(std::make_pair(Name, Init));
1419 // End of var list, exit loop.
1420 if (CurTok != ',') break;
1421 getNextToken(); // eat the ','.
1423 if (CurTok != tok_identifier)
1424 return Error("expected identifier list after var");
1427 // At this point, we have to have 'in'.
1428 if (CurTok != tok_in)
1429 return Error("expected 'in' keyword after 'var'");
1430 getNextToken(); // eat 'in'.
1432 ExprAST *Body = ParseExpression();
1433 if (Body == 0) return 0;
1435 return new VarExprAST(VarNames, Body);
1439 /// ::= identifierexpr
1445 static ExprAST *ParsePrimary() {
1447 default: return Error("unknown token when expecting an expression");
1448 case tok_identifier: return ParseIdentifierExpr();
1449 case tok_number: return ParseNumberExpr();
1450 case '(': return ParseParenExpr();
1451 case tok_if: return ParseIfExpr();
1452 case tok_for: return ParseForExpr();
1453 case tok_var: return ParseVarExpr();
1460 static ExprAST *ParseUnary() {
1461 // If the current token is not an operator, it must be a primary expr.
1462 if (!isascii(CurTok) || CurTok == '(' || CurTok == ',')
1463 return ParsePrimary();
1465 // If this is a unary operator, read it.
1468 if (ExprAST *Operand = ParseUnary())
1469 return new UnaryExprAST(Opc, Operand);
1474 /// ::= ('+' unary)*
1475 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
1476 // If this is a binop, find its precedence.
1478 int TokPrec = GetTokPrecedence();
1480 // If this is a binop that binds at least as tightly as the current binop,
1481 // consume it, otherwise we are done.
1482 if (TokPrec < ExprPrec)
1485 // Okay, we know this is a binop.
1487 getNextToken(); // eat binop
1489 // Parse the unary expression after the binary operator.
1490 ExprAST *RHS = ParseUnary();
1493 // If BinOp binds less tightly with RHS than the operator after RHS, let
1494 // the pending operator take RHS as its LHS.
1495 int NextPrec = GetTokPrecedence();
1496 if (TokPrec < NextPrec) {
1497 RHS = ParseBinOpRHS(TokPrec+1, RHS);
1498 if (RHS == 0) return 0;
1502 LHS = new BinaryExprAST(BinOp, LHS, RHS);
1507 /// ::= unary binoprhs
1509 static ExprAST *ParseExpression() {
1510 ExprAST *LHS = ParseUnary();
1513 return ParseBinOpRHS(0, LHS);
1517 /// ::= id '(' id* ')'
1518 /// ::= binary LETTER number? (id, id)
1519 /// ::= unary LETTER (id)
1520 static PrototypeAST *ParsePrototype() {
1523 unsigned Kind = 0; // 0 = identifier, 1 = unary, 2 = binary.
1524 unsigned BinaryPrecedence = 30;
1528 return ErrorP("Expected function name in prototype");
1529 case tok_identifier:
1530 FnName = IdentifierStr;
1536 if (!isascii(CurTok))
1537 return ErrorP("Expected unary operator");
1539 FnName += (char)CurTok;
1545 if (!isascii(CurTok))
1546 return ErrorP("Expected binary operator");
1548 FnName += (char)CurTok;
1552 // Read the precedence if present.
1553 if (CurTok == tok_number) {
1554 if (NumVal < 1 || NumVal > 100)
1555 return ErrorP("Invalid precedecnce: must be 1..100");
1556 BinaryPrecedence = (unsigned)NumVal;
1563 return ErrorP("Expected '(' in prototype");
1565 std::vector<std::string> ArgNames;
1566 while (getNextToken() == tok_identifier)
1567 ArgNames.push_back(IdentifierStr);
1569 return ErrorP("Expected ')' in prototype");
1572 getNextToken(); // eat ')'.
1574 // Verify right number of names for operator.
1575 if (Kind && ArgNames.size() != Kind)
1576 return ErrorP("Invalid number of operands for operator");
1578 return new PrototypeAST(FnName, ArgNames, Kind != 0, BinaryPrecedence);
1581 /// definition ::= 'def' prototype expression
1582 static FunctionAST *ParseDefinition() {
1583 getNextToken(); // eat def.
1584 PrototypeAST *Proto = ParsePrototype();
1585 if (Proto == 0) return 0;
1587 if (ExprAST *E = ParseExpression())
1588 return new FunctionAST(Proto, E);
1592 /// toplevelexpr ::= expression
1593 static FunctionAST *ParseTopLevelExpr() {
1594 if (ExprAST *E = ParseExpression()) {
1595 // Make an anonymous proto.
1596 PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>());
1597 return new FunctionAST(Proto, E);
1602 /// external ::= 'extern' prototype
1603 static PrototypeAST *ParseExtern() {
1604 getNextToken(); // eat extern.
1605 return ParsePrototype();
1608 //===----------------------------------------------------------------------===//
1610 //===----------------------------------------------------------------------===//
1612 static Module *TheModule;
1613 static IRBuilder<> Builder(getGlobalContext());
1614 static std::map<std::string, AllocaInst*> NamedValues;
1615 static FunctionPassManager *TheFPM;
1617 Value *ErrorV(const char *Str) { Error(Str); return 0; }
1619 /// CreateEntryBlockAlloca - Create an alloca instruction in the entry block of
1620 /// the function. This is used for mutable variables etc.
1621 static AllocaInst *CreateEntryBlockAlloca(Function *TheFunction,
1622 const std::string &VarName) {
1623 IRBuilder<> TmpB(&TheFunction->getEntryBlock(),
1624 TheFunction->getEntryBlock().begin());
1625 return TmpB.CreateAlloca(Type::getDoubleTy(getGlobalContext()), 0,
1629 Value *NumberExprAST::Codegen() {
1630 return ConstantFP::get(getGlobalContext(), APFloat(Val));
1633 Value *VariableExprAST::Codegen() {
1634 // Look this variable up in the function.
1635 Value *V = NamedValues[Name];
1636 if (V == 0) return ErrorV("Unknown variable name");
1639 return Builder.CreateLoad(V, Name.c_str());
1642 Value *UnaryExprAST::Codegen() {
1643 Value *OperandV = Operand->Codegen();
1644 if (OperandV == 0) return 0;
1646 Function *F = TheModule->getFunction(std::string("unary")+Opcode);
1648 return ErrorV("Unknown unary operator");
1650 return Builder.CreateCall(F, OperandV, "unop");
1653 Value *BinaryExprAST::Codegen() {
1654 // Special case '=' because we don't want to emit the LHS as an expression.
1656 // Assignment requires the LHS to be an identifier.
1657 VariableExprAST *LHSE = dynamic_cast<VariableExprAST*>(LHS);
1659 return ErrorV("destination of '=' must be a variable");
1661 Value *Val = RHS->Codegen();
1662 if (Val == 0) return 0;
1664 // Look up the name.
1665 Value *Variable = NamedValues[LHSE->getName()];
1666 if (Variable == 0) return ErrorV("Unknown variable name");
1668 Builder.CreateStore(Val, Variable);
1672 Value *L = LHS->Codegen();
1673 Value *R = RHS->Codegen();
1674 if (L == 0 || R == 0) return 0;
1677 case '+': return Builder.CreateAdd(L, R, "addtmp");
1678 case '-': return Builder.CreateSub(L, R, "subtmp");
1679 case '*': return Builder.CreateMul(L, R, "multmp");
1681 L = Builder.CreateFCmpULT(L, R, "cmptmp");
1682 // Convert bool 0/1 to double 0.0 or 1.0
1683 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
1688 // If it wasn't a builtin binary operator, it must be a user defined one. Emit
1690 Function *F = TheModule->getFunction(std::string("binary")+Op);
1691 assert(F && "binary operator not found!");
1693 Value *Ops[] = { L, R };
1694 return Builder.CreateCall(F, Ops, Ops+2, "binop");
1697 Value *CallExprAST::Codegen() {
1698 // Look up the name in the global module table.
1699 Function *CalleeF = TheModule->getFunction(Callee);
1701 return ErrorV("Unknown function referenced");
1703 // If argument mismatch error.
1704 if (CalleeF->arg_size() != Args.size())
1705 return ErrorV("Incorrect # arguments passed");
1707 std::vector<Value*> ArgsV;
1708 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
1709 ArgsV.push_back(Args[i]->Codegen());
1710 if (ArgsV.back() == 0) return 0;
1713 return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
1716 Value *IfExprAST::Codegen() {
1717 Value *CondV = Cond->Codegen();
1718 if (CondV == 0) return 0;
1720 // Convert condition to a bool by comparing equal to 0.0.
1721 CondV = Builder.CreateFCmpONE(CondV,
1722 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
1725 Function *TheFunction = Builder.GetInsertBlock()->getParent();
1727 // Create blocks for the then and else cases. Insert the 'then' block at the
1728 // end of the function.
1729 BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunction);
1730 BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else");
1731 BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont");
1733 Builder.CreateCondBr(CondV, ThenBB, ElseBB);
1736 Builder.SetInsertPoint(ThenBB);
1738 Value *ThenV = Then->Codegen();
1739 if (ThenV == 0) return 0;
1741 Builder.CreateBr(MergeBB);
1742 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
1743 ThenBB = Builder.GetInsertBlock();
1746 TheFunction->getBasicBlockList().push_back(ElseBB);
1747 Builder.SetInsertPoint(ElseBB);
1749 Value *ElseV = Else->Codegen();
1750 if (ElseV == 0) return 0;
1752 Builder.CreateBr(MergeBB);
1753 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
1754 ElseBB = Builder.GetInsertBlock();
1756 // Emit merge block.
1757 TheFunction->getBasicBlockList().push_back(MergeBB);
1758 Builder.SetInsertPoint(MergeBB);
1759 PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()),
1762 PN->addIncoming(ThenV, ThenBB);
1763 PN->addIncoming(ElseV, ElseBB);
1767 Value *ForExprAST::Codegen() {
1769 // var = alloca double
1771 // start = startexpr
1772 // store start -> var
1780 // endcond = endexpr
1782 // curvar = load var
1783 // nextvar = curvar + step
1784 // store nextvar -> var
1785 // br endcond, loop, endloop
1788 Function *TheFunction = Builder.GetInsertBlock()->getParent();
1790 // Create an alloca for the variable in the entry block.
1791 AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);
1793 // Emit the start code first, without 'variable' in scope.
1794 Value *StartVal = Start->Codegen();
1795 if (StartVal == 0) return 0;
1797 // Store the value into the alloca.
1798 Builder.CreateStore(StartVal, Alloca);
1800 // Make the new basic block for the loop header, inserting after current
1802 BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
1804 // Insert an explicit fall through from the current block to the LoopBB.
1805 Builder.CreateBr(LoopBB);
1807 // Start insertion in LoopBB.
1808 Builder.SetInsertPoint(LoopBB);
1810 // Within the loop, the variable is defined equal to the PHI node. If it
1811 // shadows an existing variable, we have to restore it, so save it now.
1812 AllocaInst *OldVal = NamedValues[VarName];
1813 NamedValues[VarName] = Alloca;
1815 // Emit the body of the loop. This, like any other expr, can change the
1816 // current BB. Note that we ignore the value computed by the body, but don't
1818 if (Body->Codegen() == 0)
1821 // Emit the step value.
1824 StepVal = Step->Codegen();
1825 if (StepVal == 0) return 0;
1827 // If not specified, use 1.0.
1828 StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
1831 // Compute the end condition.
1832 Value *EndCond = End->Codegen();
1833 if (EndCond == 0) return EndCond;
1835 // Reload, increment, and restore the alloca. This handles the case where
1836 // the body of the loop mutates the variable.
1837 Value *CurVar = Builder.CreateLoad(Alloca, VarName.c_str());
1838 Value *NextVar = Builder.CreateAdd(CurVar, StepVal, "nextvar");
1839 Builder.CreateStore(NextVar, Alloca);
1841 // Convert condition to a bool by comparing equal to 0.0.
1842 EndCond = Builder.CreateFCmpONE(EndCond,
1843 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
1846 // Create the "after loop" block and insert it.
1847 BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
1849 // Insert the conditional branch into the end of LoopEndBB.
1850 Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
1852 // Any new code will be inserted in AfterBB.
1853 Builder.SetInsertPoint(AfterBB);
1855 // Restore the unshadowed variable.
1857 NamedValues[VarName] = OldVal;
1859 NamedValues.erase(VarName);
1862 // for expr always returns 0.0.
1863 return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
1866 Value *VarExprAST::Codegen() {
1867 std::vector<AllocaInst *> OldBindings;
1869 Function *TheFunction = Builder.GetInsertBlock()->getParent();
1871 // Register all variables and emit their initializer.
1872 for (unsigned i = 0, e = VarNames.size(); i != e; ++i) {
1873 const std::string &VarName = VarNames[i].first;
1874 ExprAST *Init = VarNames[i].second;
1876 // Emit the initializer before adding the variable to scope, this prevents
1877 // the initializer from referencing the variable itself, and permits stuff
1880 // var a = a in ... # refers to outer 'a'.
1883 InitVal = Init->Codegen();
1884 if (InitVal == 0) return 0;
1885 } else { // If not specified, use 0.0.
1886 InitVal = ConstantFP::get(getGlobalContext(), APFloat(0.0));
1889 AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);
1890 Builder.CreateStore(InitVal, Alloca);
1892 // Remember the old variable binding so that we can restore the binding when
1894 OldBindings.push_back(NamedValues[VarName]);
1896 // Remember this binding.
1897 NamedValues[VarName] = Alloca;
1900 // Codegen the body, now that all vars are in scope.
1901 Value *BodyVal = Body->Codegen();
1902 if (BodyVal == 0) return 0;
1904 // Pop all our variables from scope.
1905 for (unsigned i = 0, e = VarNames.size(); i != e; ++i)
1906 NamedValues[VarNames[i].first] = OldBindings[i];
1908 // Return the body computation.
1912 Function *PrototypeAST::Codegen() {
1913 // Make the function type: double(double,double) etc.
1914 std::vector<const Type*> Doubles(Args.size(),
1915 Type::getDoubleTy(getGlobalContext()));
1916 FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()),
1919 Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
1921 // If F conflicted, there was already something named 'Name'. If it has a
1922 // body, don't allow redefinition or reextern.
1923 if (F->getName() != Name) {
1924 // Delete the one we just made and get the existing one.
1925 F->eraseFromParent();
1926 F = TheModule->getFunction(Name);
1928 // If F already has a body, reject this.
1929 if (!F->empty()) {
1930 ErrorF("redefinition of function");
1934 // If F took a different number of args, reject.
1935 if (F->arg_size() != Args.size()) {
1936 ErrorF("redefinition of function with different # args");
1941 // Set names for all arguments.
1943 for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
1945 AI->setName(Args[Idx]);
1950 /// CreateArgumentAllocas - Create an alloca for each argument and register the
1951 /// argument in the symbol table so that references to it will succeed.
1952 void PrototypeAST::CreateArgumentAllocas(Function *F) {
1953 Function::arg_iterator AI = F->arg_begin();
1954 for (unsigned Idx = 0, e = Args.size(); Idx != e; ++Idx, ++AI) {
1955 // Create an alloca for this variable.
1956 AllocaInst *Alloca = CreateEntryBlockAlloca(F, Args[Idx]);
1958 // Store the initial value into the alloca.
1959 Builder.CreateStore(AI, Alloca);
1961 // Add arguments to variable symbol table.
1962 NamedValues[Args[Idx]] = Alloca;
1966 Function *FunctionAST::Codegen() {
1967 NamedValues.clear();
1969 Function *TheFunction = Proto->Codegen();
1970 if (TheFunction == 0)
1973 // If this is an operator, install it.
1974 if (Proto->isBinaryOp())
1975 BinopPrecedence[Proto->getOperatorName()] = Proto->getBinaryPrecedence();
1977 // Create a new basic block to start insertion into.
1978 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
1979 Builder.SetInsertPoint(BB);
1981 // Add all arguments to the symbol table and create their allocas.
1982 Proto->CreateArgumentAllocas(TheFunction);
1984 if (Value *RetVal = Body->Codegen()) {
1985 // Finish off the function.
1986 Builder.CreateRet(RetVal);
1988 // Validate the generated code, checking for consistency.
1989 verifyFunction(*TheFunction);
1991 // Optimize the function.
1992 TheFPM->run(*TheFunction);
1997 // Error reading body, remove function.
1998 TheFunction->eraseFromParent();
2000 if (Proto->isBinaryOp())
2001 BinopPrecedence.erase(Proto->getOperatorName());
2005 //===----------------------------------------------------------------------===//
2006 // Top-Level parsing and JIT Driver
2007 //===----------------------------------------------------------------------===//
2009 static ExecutionEngine *TheExecutionEngine;
2011 static void HandleDefinition() {
2012 if (FunctionAST *F = ParseDefinition()) {
2013 if (Function *LF = F->Codegen()) {
2014 fprintf(stderr, "Read function definition:");
2018 // Skip token for error recovery.
2023 static void HandleExtern() {
2024 if (PrototypeAST *P = ParseExtern()) {
2025 if (Function *F = P->Codegen()) {
2026 fprintf(stderr, "Read extern: ");
2030 // Skip token for error recovery.
2035 static void HandleTopLevelExpression() {
2036 // Evaluate a top-level expression into an anonymous function.
2037 if (FunctionAST *F = ParseTopLevelExpr()) {
2038 if (Function *LF = F->Codegen()) {
2039 // JIT the function, returning a function pointer.
2040 void *FPtr = TheExecutionEngine->getPointerToFunction(LF);
2042 // Cast it to the right type (takes no arguments, returns a double) so we
2043 // can call it as a native function.
2044 double (*FP)() = (double (*)())(intptr_t)FPtr;
2045 fprintf(stderr, "Evaluated to %f\n", FP());
2048 // Skip token for error recovery.
2053 /// top ::= definition | external | expression | ';'
2054 static void MainLoop() {
2056 fprintf(stderr, "ready> ");
2058 case tok_eof: return;
2059 case ';': getNextToken(); break; // ignore top-level semicolons.
2060 case tok_def: HandleDefinition(); break;
2061 case tok_extern: HandleExtern(); break;
2062 default: HandleTopLevelExpression(); break;
2067 //===----------------------------------------------------------------------===//
2068 // "Library" functions that can be "extern'd" from user code.
2069 //===----------------------------------------------------------------------===//
2071 /// putchard - putchar that takes a double and returns 0.
2073 double putchard(double X) {
2078 /// printd - printf that takes a double prints it as "%f\n", returning 0.
2080 double printd(double X) {
2085 //===----------------------------------------------------------------------===//
2086 // Main driver code.
2087 //===----------------------------------------------------------------------===//
2090 InitializeNativeTarget();
2091 LLVMContext &Context = getGlobalContext();
2093 // Install standard binary operators.
2094 // 1 is lowest precedence.
2095 BinopPrecedence['='] = 2;
2096 BinopPrecedence['<'] = 10;
2097 BinopPrecedence['+'] = 20;
2098 BinopPrecedence['-'] = 20;
2099 BinopPrecedence['*'] = 40; // highest.
2101 // Prime the first token.
2102 fprintf(stderr, "ready> ");
2105 // Make the module, which holds all the code.
2106 TheModule = new Module("my cool jit", Context);
2108 ExistingModuleProvider *OurModuleProvider =
2109 new ExistingModuleProvider(TheModule);
2111 // Create the JIT. This takes ownership of the module and module provider.
2112 TheExecutionEngine = EngineBuilder(OurModuleProvider).create();
2114 FunctionPassManager OurFPM(OurModuleProvider);
2116 // Set up the optimizer pipeline. Start with registering info about how the
2117 // target lays out data structures.
2118 OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData()));
2119 // Promote allocas to registers.
2120 OurFPM.add(createPromoteMemoryToRegisterPass());
2121 // Do simple "peephole" optimizations and bit-twiddling optzns.
2122 OurFPM.add(createInstructionCombiningPass());
2123 // Reassociate expressions.
2124 OurFPM.add(createReassociatePass());
2125 // Eliminate Common SubExpressions.
2126 OurFPM.add(createGVNPass());
2127 // Simplify the control flow graph (deleting unreachable blocks, etc).
2128 OurFPM.add(createCFGSimplificationPass());
2130 OurFPM.doInitialization();
2132 // Set the global so the code gen can use this.
2133 TheFPM = &OurFPM;
2135 // Run the main "interpreter loop" now.
2140 // Print out all of the generated code.
2141 TheModule->dump();
2148 <a href="LangImpl8.html">Next: Conclusion and other useful LLVM tidbits</a>
2151 <!-- *********************************************************************** -->
2154 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
2155 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
2156 <a href="http://validator.w3.org/check/referer"><img
2157 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
2159 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
2160 <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
2161 Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $