| blob | ddddc423209334c4d1a8f12ca3fd7faa2f19bfa5 |
4 <html>
5 <head>
6 <title>Kaleidoscope: Extending the Language: Mutable Variables / SSA
7 construction</title>
11 </head>
13 <body>
17 <ul>
20 <ol>
26 Mutation</a></li>
30 </ol>
31 </li>
33 tidbits</li>
34 </ul>
38 </div>
40 <!-- *********************************************************************** -->
42 <!-- *********************************************************************** -->
48 respectable, albeit simple, <a
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
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>
66 </div>
68 <!-- *********************************************************************** -->
70 <!-- *********************************************************************** -->
74 <p>
75 To understand why mutable variables cause complexities in SSA construction,
76 consider this extremely simple C example:
77 </p>
80 <pre>
81 int G, H;
82 int test(_Bool Condition) {
83 int X;
84 if (Condition)
85 X = G;
86 else
87 X = H;
88 return X;
89 }
90 </pre>
91 </div>
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>
99 <pre>
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) {
104 entry:
105 br i1 %Condition, label %cond_true, label %cond_false
107 cond_true:
108 %X.0 = load i32* @G
109 br label %cond_next
111 cond_false:
112 %X.1 = load i32* @H
113 br label %cond_next
115 cond_next:
117 ret i32 %X.2
118 }
119 </pre>
120 </div>
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
134 assignments to mutable variables?". The issue here is that LLVM
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
138 logic.</p>
140 </div>
142 <!-- *********************************************************************** -->
144 <!-- *********************************************************************** -->
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
155 demand.</p>
157 <p>
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.
162 </p>
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
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
174 <pre>
175 define i32 @example() {
176 entry:
177 %X = alloca i32 ; type of %X is i32*.
178 ...
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
182 ...
183 </pre>
184 </div>
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>
193 <pre>
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) {
198 entry:
199 %X = alloca i32 ; type of %X is i32*.
200 br i1 %Condition, label %cond_true, label %cond_false
202 cond_true:
203 %X.0 = load i32* @G
204 store i32 %X.0, i32* %X ; Update X
205 br label %cond_next
207 cond_false:
208 %X.1 = load i32* @H
209 store i32 %X.1, i32* %X ; Update X
210 br label %cond_next
212 cond_next:
213 %X.2 = load i32* %X ; Read X
214 ret i32 %X.2
215 }
216 </pre>
217 </div>
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>
222 <ol>
227 </ol>
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
235 get:</p>
238 <pre>
240 @G = weak global i32 0
241 @H = weak global i32 0
243 define i32 @test(i1 %Condition) {
244 entry:
245 br i1 %Condition, label %cond_true, label %cond_false
247 cond_true:
248 %X.0 = load i32* @G
249 br label %cond_next
251 cond_false:
252 %X.1 = load i32* @H
253 br label %cond_next
255 cond_next:
257 ret i32 %X.01
258 }
259 </pre>
260 </div>
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>
268 <ol>
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>
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
287 </ol>
289 <p>
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>
298 <ul>
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
302 fixed early.</li>
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.
308 </li>
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>
314 </ul>
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
318 variables now!
319 </p>
321 </div>
323 <!-- *********************************************************************** -->
325 Kaleidoscope</a></div>
326 <!-- *********************************************************************** -->
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>
334 <ol>
337 </ol>
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>
346 <pre>
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.
352 def fib(x)
354 1
355 else
358 # Iterative fib.
359 def fibi(x)
365 b;
367 # Call it.
368 fibi(10);
369 </pre>
370 </div>
372 <p>
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.
376 </p>
378 </div>
380 <!-- *********************************************************************** -->
382 Mutation</a></div>
383 <!-- *********************************************************************** -->
387 <p>
388 The symbol table in Kaleidoscope is managed at code generation time by the
390 that holds the double value for the named variable. In order to support
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>
397 <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
402 locations.
403 </p>
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>
410 <pre>
412 </pre>
413 </div>
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
417 function:</p>
420 <pre>
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) {
426 TheFunction->getEntryBlock().begin());
427 return TmpB.CreateAlloca(Type::getDoubleTy(getGlobalContext()), 0,
428 VarName.c_str());
429 }
430 </pre>
431 </div>
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
441 slot:</p>
444 <pre>
445 Value *VariableExprAST::Codegen() {
446 // Look this variable up in the function.
447 Value *V = NamedValues[Name];
450 <b>// Load the value.
451 return Builder.CreateLoad(V, Name.c_str());</b>
452 }
453 </pre>
454 </div>
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
459 the unabridged code):</p>
462 <pre>
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();
472 <b>// Store the value into the alloca.
473 Builder.CreateStore(StartVal, Alloca);</b>
474 ...
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.CreateFAdd(CurVar, StepVal, "nextvar");
484 Builder.CreateStore(NextVar, Alloca);</b>
485 ...
486 </pre>
487 </div>
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>
498 <pre>
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;
512 }
513 }
514 </pre>
515 </div>
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
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>
526 <pre>
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());
536 </pre>
537 </div>
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>
544 <pre>
545 define double @fib(double %x) {
546 entry:
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
556 br label %ifcont
558 else: ; preds = %entry
560 %subtmp = fsub double %x3, 1.000000e+00
561 %calltmp = call double @fib(double %subtmp)
563 %subtmp5 = fsub double %x4, 2.000000e+00
564 %calltmp6 = call double @fib(double %subtmp5)
565 %addtmp = fadd double %calltmp, %calltmp6
566 br label %ifcont
568 ifcont: ; preds = %else, %then
569 %iftmp = phi double [ 1.000000e+00, %then ], [ %addtmp, %else ]
570 ret double %iftmp
571 }
572 </pre>
573 </div>
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>
586 <pre>
587 define double @fib(double %x) {
588 entry:
590 %booltmp = uitofp i1 %cmptmp to double
591 %ifcond = fcmp one double %booltmp, 0.000000e+00
592 br i1 %ifcond, label %then, label %else
594 then:
595 br label %ifcont
597 else:
599 %calltmp = call double @fib(double %subtmp)
601 %calltmp6 = call double @fib(double %subtmp5)
602 %addtmp = fadd double %calltmp, %calltmp6
603 br label %ifcont
605 ifcont: ; preds = %else, %then
606 %iftmp = phi double [ 1.000000e+00, %then ], [ %addtmp, %else ]
607 ret double %iftmp
608 }
609 </pre>
610 </div>
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>
619 <pre>
620 define double @fib(double %x) {
621 entry:
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
627 else:
628 %subtmp = fsub double %x, 1.000000e+00
629 %calltmp = call double @fib(double %subtmp)
630 %subtmp5 = fsub double %x, 2.000000e+00
631 %calltmp6 = call double @fib(double %subtmp5)
632 %addtmp = fadd double %calltmp, %calltmp6
633 ret double %addtmp
635 ifcont:
636 ret double 1.000000e+00
637 }
638 </pre>
639 </div>
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>
648 </div>
650 <!-- *********************************************************************** -->
652 <!-- *********************************************************************** -->
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>
662 <pre>
663 int main() {
664 // Install standard binary operators.
665 // 1 is lowest precedence.
668 BinopPrecedence['+'] = 20;
669 BinopPrecedence['-'] = 20;
670 </pre>
671 </div>
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>
678 <pre>
679 Value *BinaryExprAST::Codegen() {
680 // Special case '=' because we don't want to emit the LHS as an expression.
681 if (Op == '=') {
682 // Assignment requires the LHS to be an identifier.
684 if (!LHSE)
685 return ErrorV("destination of '=' must be a variable");
686 </pre>
687 </div>
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
694 </p>
697 <pre>
698 // Codegen the RHS.
699 Value *Val = RHS->Codegen();
702 // Look up the name.
703 Value *Variable = NamedValues[LHSE->getName()];
706 Builder.CreateStore(Val, Variable);
707 return Val;
708 }
709 ...
710 </pre>
711 </div>
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
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>
721 <pre>
722 # Function to print a double.
723 extern printd(x);
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;
729 def test(x)
730 printd(x) :
731 x = 4 :
732 printd(x);
734 test(123);
735 </pre>
736 </div>
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
742 add this next!
743 </p>
745 </div>
747 <!-- *********************************************************************** -->
749 Variables</a></div>
750 <!-- *********************************************************************** -->
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>
760 <pre>
761 enum Token {
762 ...
763 <b>// var definition
765 ...
766 }
767 ...
768 static int gettok() {
769 ...
770 if (IdentifierStr == "in") return tok_in;
771 if (IdentifierStr == "binary") return tok_binary;
772 if (IdentifierStr == "unary") return tok_unary;
774 return tok_identifier;
775 ...
776 </pre>
777 </div>
779 <p>The next step is to define the AST node that we will construct. For var/in,
780 it looks like this:</p>
783 <pre>
784 /// VarExprAST - Expression class for var/in
785 class VarExprAST : public ExprAST {
787 ExprAST *Body;
788 public:
790 ExprAST *body)
791 : VarNames(varnames), Body(body) {}
793 virtual Value *Codegen();
794 };
795 </pre>
796 </div>
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>
807 <pre>
808 /// primary
809 /// ::= identifierexpr
810 /// ::= numberexpr
811 /// ::= parenexpr
812 /// ::= ifexpr
813 /// ::= forexpr
815 static ExprAST *ParsePrimary() {
816 switch (CurTok) {
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();
824 }
825 }
826 </pre>
827 </div>
832 <pre>
833 /// varexpr ::= 'var' identifier ('=' expression)?
834 // (',' identifier ('=' expression)?)* 'in' expression
835 static ExprAST *ParseVarExpr() {
836 getNextToken(); // eat the var.
840 // At least one variable name is required.
841 if (CurTok != tok_identifier)
842 return Error("expected identifier after var");
843 </pre>
844 </div>
846 <p>The first part of this code parses the list of identifier/expr pairs into the
850 <pre>
851 while (1) {
852 std::string Name = IdentifierStr;
853 getNextToken(); // eat identifier.
855 // Read the optional initializer.
856 ExprAST *Init = 0;
857 if (CurTok == '=') {
858 getNextToken(); // eat the '='.
860 Init = ParseExpression();
862 }
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");
872 }
873 </pre>
874 </div>
876 <p>Once all the variables are parsed, we then parse the body and create the
877 AST node:</p>
880 <pre>
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();
889 return new VarExprAST(VarNames, Body);
890 }
891 </pre>
892 </div>
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>
898 <pre>
899 Value *VarExprAST::Codegen() {
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;
908 </pre>
909 </div>
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>
916 <pre>
917 // Emit the initializer before adding the variable to scope, this prevents
918 // the initializer from referencing the variable itself, and permits stuff
919 // like this:
920 // var a = 1 in
921 // var a = a in ... # refers to outer 'a'.
922 Value *InitVal;
923 if (Init) {
924 InitVal = Init->Codegen();
926 } else { // If not specified, use 0.0.
927 InitVal = ConstantFP::get(getGlobalContext(), APFloat(0.0));
928 }
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
934 // we unrecurse.
935 OldBindings.push_back(NamedValues[VarName]);
937 // Remember this binding.
938 NamedValues[VarName] = Alloca;
939 }
940 </pre>
941 </div>
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>
949 <pre>
950 // Codegen the body, now that all vars are in scope.
951 Value *BodyVal = Body->Codegen();
953 </pre>
954 </div>
959 <pre>
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.
965 return BodyVal;
966 }
967 </pre>
968 </div>
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>
979 </div>
981 <!-- *********************************************************************** -->
983 <!-- *********************************************************************** -->
987 <p>
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:
990 </p>
993 <pre>
994 # Compile
995 g++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o toy
996 # Run
997 ./toy
998 </pre>
999 </div>
1004 <pre>
1005 #include "llvm/DerivedTypes.h"
1006 #include "llvm/ExecutionEngine/ExecutionEngine.h"
1007 #include "llvm/ExecutionEngine/JIT.h"
1008 #include "llvm/LLVMContext.h"
1009 #include "llvm/Module.h"
1010 #include "llvm/PassManager.h"
1011 #include "llvm/Analysis/Verifier.h"
1012 #include "llvm/Analysis/Passes.h"
1013 #include "llvm/Target/TargetData.h"
1014 #include "llvm/Target/TargetSelect.h"
1015 #include "llvm/Transforms/Scalar.h"
1016 #include "llvm/Support/IRBuilder.h"
1021 using namespace llvm;
1023 //===----------------------------------------------------------------------===//
1024 // Lexer
1025 //===----------------------------------------------------------------------===//
1028 // of these for known things.
1029 enum Token {
1030 tok_eof = -1,
1032 // commands
1035 // primary
1038 // control
1042 // operators
1045 // var definition
1046 tok_var = -13
1047 };
1049 static std::string IdentifierStr; // Filled in if tok_identifier
1050 static double NumVal; // Filled in if tok_number
1052 /// gettok - Return the next token from standard input.
1053 static int gettok() {
1054 static int LastChar = ' ';
1056 // Skip any whitespace.
1057 while (isspace(LastChar))
1058 LastChar = getchar();
1060 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
1061 IdentifierStr = LastChar;
1062 while (isalnum((LastChar = getchar())))
1063 IdentifierStr += LastChar;
1065 if (IdentifierStr == "def") return tok_def;
1066 if (IdentifierStr == "extern") return tok_extern;
1067 if (IdentifierStr == "if") return tok_if;
1068 if (IdentifierStr == "then") return tok_then;
1069 if (IdentifierStr == "else") return tok_else;
1070 if (IdentifierStr == "for") return tok_for;
1071 if (IdentifierStr == "in") return tok_in;
1072 if (IdentifierStr == "binary") return tok_binary;
1073 if (IdentifierStr == "unary") return tok_unary;
1074 if (IdentifierStr == "var") return tok_var;
1075 return tok_identifier;
1076 }
1079 std::string NumStr;
1080 do {
1081 NumStr += LastChar;
1082 LastChar = getchar();
1083 } while (isdigit(LastChar) || LastChar == '.');
1085 NumVal = strtod(NumStr.c_str(), 0);
1086 return tok_number;
1087 }
1089 if (LastChar == '#') {
1090 // Comment until end of line.
1091 do LastChar = getchar();
1094 if (LastChar != EOF)
1095 return gettok();
1096 }
1098 // Check for end of file. Don't eat the EOF.
1099 if (LastChar == EOF)
1100 return tok_eof;
1102 // Otherwise, just return the character as its ascii value.
1103 int ThisChar = LastChar;
1104 LastChar = getchar();
1105 return ThisChar;
1106 }
1108 //===----------------------------------------------------------------------===//
1109 // Abstract Syntax Tree (aka Parse Tree)
1110 //===----------------------------------------------------------------------===//
1112 /// ExprAST - Base class for all expression nodes.
1113 class ExprAST {
1114 public:
1115 virtual ~ExprAST() {}
1116 virtual Value *Codegen() = 0;
1117 };
1119 /// NumberExprAST - Expression class for numeric literals like "1.0".
1120 class NumberExprAST : public ExprAST {
1121 double Val;
1122 public:
1123 NumberExprAST(double val) : Val(val) {}
1124 virtual Value *Codegen();
1125 };
1127 /// VariableExprAST - Expression class for referencing a variable, like "a".
1128 class VariableExprAST : public ExprAST {
1129 std::string Name;
1130 public:
1131 VariableExprAST(const std::string &name) : Name(name) {}
1132 const std::string &getName() const { return Name; }
1133 virtual Value *Codegen();
1134 };
1136 /// UnaryExprAST - Expression class for a unary operator.
1137 class UnaryExprAST : public ExprAST {
1138 char Opcode;
1139 ExprAST *Operand;
1140 public:
1141 UnaryExprAST(char opcode, ExprAST *operand)
1142 : Opcode(opcode), Operand(operand) {}
1143 virtual Value *Codegen();
1144 };
1146 /// BinaryExprAST - Expression class for a binary operator.
1147 class BinaryExprAST : public ExprAST {
1148 char Op;
1149 ExprAST *LHS, *RHS;
1150 public:
1151 BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
1152 : Op(op), LHS(lhs), RHS(rhs) {}
1153 virtual Value *Codegen();
1154 };
1156 /// CallExprAST - Expression class for function calls.
1157 class CallExprAST : public ExprAST {
1158 std::string Callee;
1160 public:
1162 : Callee(callee), Args(args) {}
1163 virtual Value *Codegen();
1164 };
1166 /// IfExprAST - Expression class for if/then/else.
1167 class IfExprAST : public ExprAST {
1168 ExprAST *Cond, *Then, *Else;
1169 public:
1170 IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
1171 : Cond(cond), Then(then), Else(_else) {}
1172 virtual Value *Codegen();
1173 };
1175 /// ForExprAST - Expression class for for/in.
1176 class ForExprAST : public ExprAST {
1177 std::string VarName;
1178 ExprAST *Start, *End, *Step, *Body;
1179 public:
1180 ForExprAST(const std::string &varname, ExprAST *start, ExprAST *end,
1181 ExprAST *step, ExprAST *body)
1182 : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
1183 virtual Value *Codegen();
1184 };
1186 /// VarExprAST - Expression class for var/in
1187 class VarExprAST : public ExprAST {
1189 ExprAST *Body;
1190 public:
1192 ExprAST *body)
1193 : VarNames(varnames), Body(body) {}
1195 virtual Value *Codegen();
1196 };
1198 /// PrototypeAST - This class represents the "prototype" for a function,
1199 /// which captures its name, and its argument names (thus implicitly the number
1200 /// of arguments the function takes), as well as if it is an operator.
1201 class PrototypeAST {
1202 std::string Name;
1204 bool isOperator;
1205 unsigned Precedence; // Precedence if a binary op.
1206 public:
1208 bool isoperator = false, unsigned prec = 0)
1209 : Name(name), Args(args), isOperator(isoperator), Precedence(prec) {}
1214 char getOperatorName() const {
1215 assert(isUnaryOp() || isBinaryOp());
1216 return Name[Name.size()-1];
1217 }
1219 unsigned getBinaryPrecedence() const { return Precedence; }
1221 Function *Codegen();
1223 void CreateArgumentAllocas(Function *F);
1224 };
1226 /// FunctionAST - This class represents a function definition itself.
1227 class FunctionAST {
1228 PrototypeAST *Proto;
1229 ExprAST *Body;
1230 public:
1231 FunctionAST(PrototypeAST *proto, ExprAST *body)
1232 : Proto(proto), Body(body) {}
1234 Function *Codegen();
1235 };
1237 //===----------------------------------------------------------------------===//
1238 // Parser
1239 //===----------------------------------------------------------------------===//
1241 /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
1242 /// token the parser is looking at. getNextToken reads another token from the
1243 /// lexer and updates CurTok with its results.
1244 static int CurTok;
1245 static int getNextToken() {
1246 return CurTok = gettok();
1247 }
1249 /// BinopPrecedence - This holds the precedence for each binary operator that is
1250 /// defined.
1253 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
1254 static int GetTokPrecedence() {
1255 if (!isascii(CurTok))
1256 return -1;
1258 // Make sure it's a declared binop.
1259 int TokPrec = BinopPrecedence[CurTok];
1261 return TokPrec;
1262 }
1264 /// Error* - These are little helper functions for error handling.
1266 PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
1267 FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
1269 static ExprAST *ParseExpression();
1271 /// identifierexpr
1272 /// ::= identifier
1273 /// ::= identifier '(' expression* ')'
1274 static ExprAST *ParseIdentifierExpr() {
1275 std::string IdName = IdentifierStr;
1277 getNextToken(); // eat identifier.
1279 if (CurTok != '(') // Simple variable ref.
1280 return new VariableExprAST(IdName);
1282 // Call.
1283 getNextToken(); // eat (
1285 if (CurTok != ')') {
1286 while (1) {
1287 ExprAST *Arg = ParseExpression();
1288 if (!Arg) return 0;
1289 Args.push_back(Arg);
1291 if (CurTok == ')') break;
1293 if (CurTok != ',')
1294 return Error("Expected ')' or ',' in argument list");
1295 getNextToken();
1296 }
1297 }
1299 // Eat the ')'.
1300 getNextToken();
1302 return new CallExprAST(IdName, Args);
1303 }
1305 /// numberexpr ::= number
1306 static ExprAST *ParseNumberExpr() {
1307 ExprAST *Result = new NumberExprAST(NumVal);
1308 getNextToken(); // consume the number
1309 return Result;
1310 }
1312 /// parenexpr ::= '(' expression ')'
1313 static ExprAST *ParseParenExpr() {
1314 getNextToken(); // eat (.
1315 ExprAST *V = ParseExpression();
1316 if (!V) return 0;
1318 if (CurTok != ')')
1319 return Error("expected ')'");
1320 getNextToken(); // eat ).
1321 return V;
1322 }
1324 /// ifexpr ::= 'if' expression 'then' expression 'else' expression
1325 static ExprAST *ParseIfExpr() {
1326 getNextToken(); // eat the if.
1328 // condition.
1329 ExprAST *Cond = ParseExpression();
1330 if (!Cond) return 0;
1332 if (CurTok != tok_then)
1333 return Error("expected then");
1334 getNextToken(); // eat the then
1336 ExprAST *Then = ParseExpression();
1339 if (CurTok != tok_else)
1340 return Error("expected else");
1342 getNextToken();
1344 ExprAST *Else = ParseExpression();
1345 if (!Else) return 0;
1347 return new IfExprAST(Cond, Then, Else);
1348 }
1350 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
1351 static ExprAST *ParseForExpr() {
1352 getNextToken(); // eat the for.
1354 if (CurTok != tok_identifier)
1355 return Error("expected identifier after for");
1357 std::string IdName = IdentifierStr;
1358 getNextToken(); // eat identifier.
1360 if (CurTok != '=')
1361 return Error("expected '=' after for");
1362 getNextToken(); // eat '='.
1365 ExprAST *Start = ParseExpression();
1367 if (CurTok != ',')
1368 return Error("expected ',' after for start value");
1369 getNextToken();
1371 ExprAST *End = ParseExpression();
1374 // The step value is optional.
1375 ExprAST *Step = 0;
1376 if (CurTok == ',') {
1377 getNextToken();
1378 Step = ParseExpression();
1380 }
1382 if (CurTok != tok_in)
1383 return Error("expected 'in' after for");
1384 getNextToken(); // eat 'in'.
1386 ExprAST *Body = ParseExpression();
1389 return new ForExprAST(IdName, Start, End, Step, Body);
1390 }
1392 /// varexpr ::= 'var' identifier ('=' expression)?
1393 // (',' identifier ('=' expression)?)* 'in' expression
1394 static ExprAST *ParseVarExpr() {
1395 getNextToken(); // eat the var.
1399 // At least one variable name is required.
1400 if (CurTok != tok_identifier)
1401 return Error("expected identifier after var");
1403 while (1) {
1404 std::string Name = IdentifierStr;
1405 getNextToken(); // eat identifier.
1407 // Read the optional initializer.
1408 ExprAST *Init = 0;
1409 if (CurTok == '=') {
1410 getNextToken(); // eat the '='.
1412 Init = ParseExpression();
1414 }
1416 VarNames.push_back(std::make_pair(Name, Init));
1418 // End of var list, exit loop.
1419 if (CurTok != ',') break;
1420 getNextToken(); // eat the ','.
1422 if (CurTok != tok_identifier)
1423 return Error("expected identifier list after var");
1424 }
1426 // At this point, we have to have 'in'.
1427 if (CurTok != tok_in)
1428 return Error("expected 'in' keyword after 'var'");
1429 getNextToken(); // eat 'in'.
1431 ExprAST *Body = ParseExpression();
1434 return new VarExprAST(VarNames, Body);
1435 }
1437 /// primary
1438 /// ::= identifierexpr
1439 /// ::= numberexpr
1440 /// ::= parenexpr
1441 /// ::= ifexpr
1442 /// ::= forexpr
1443 /// ::= varexpr
1444 static ExprAST *ParsePrimary() {
1445 switch (CurTok) {
1446 default: return Error("unknown token when expecting an expression");
1447 case tok_identifier: return ParseIdentifierExpr();
1448 case tok_number: return ParseNumberExpr();
1449 case '(': return ParseParenExpr();
1450 case tok_if: return ParseIfExpr();
1451 case tok_for: return ParseForExpr();
1452 case tok_var: return ParseVarExpr();
1453 }
1454 }
1456 /// unary
1457 /// ::= primary
1458 /// ::= '!' unary
1459 static ExprAST *ParseUnary() {
1460 // If the current token is not an operator, it must be a primary expr.
1461 if (!isascii(CurTok) || CurTok == '(' || CurTok == ',')
1462 return ParsePrimary();
1464 // If this is a unary operator, read it.
1465 int Opc = CurTok;
1466 getNextToken();
1467 if (ExprAST *Operand = ParseUnary())
1468 return new UnaryExprAST(Opc, Operand);
1469 return 0;
1470 }
1472 /// binoprhs
1473 /// ::= ('+' unary)*
1474 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
1475 // If this is a binop, find its precedence.
1476 while (1) {
1477 int TokPrec = GetTokPrecedence();
1479 // If this is a binop that binds at least as tightly as the current binop,
1480 // consume it, otherwise we are done.
1481 if (TokPrec < ExprPrec)
1482 return LHS;
1484 // Okay, we know this is a binop.
1485 int BinOp = CurTok;
1486 getNextToken(); // eat binop
1488 // Parse the unary expression after the binary operator.
1489 ExprAST *RHS = ParseUnary();
1490 if (!RHS) return 0;
1492 // If BinOp binds less tightly with RHS than the operator after RHS, let
1493 // the pending operator take RHS as its LHS.
1494 int NextPrec = GetTokPrecedence();
1495 if (TokPrec < NextPrec) {
1496 RHS = ParseBinOpRHS(TokPrec+1, RHS);
1498 }
1500 // Merge LHS/RHS.
1501 LHS = new BinaryExprAST(BinOp, LHS, RHS);
1502 }
1503 }
1505 /// expression
1506 /// ::= unary binoprhs
1507 ///
1508 static ExprAST *ParseExpression() {
1509 ExprAST *LHS = ParseUnary();
1510 if (!LHS) return 0;
1512 return ParseBinOpRHS(0, LHS);
1513 }
1515 /// prototype
1516 /// ::= id '(' id* ')'
1517 /// ::= binary LETTER number? (id, id)
1518 /// ::= unary LETTER (id)
1519 static PrototypeAST *ParsePrototype() {
1520 std::string FnName;
1523 unsigned BinaryPrecedence = 30;
1525 switch (CurTok) {
1526 default:
1527 return ErrorP("Expected function name in prototype");
1528 case tok_identifier:
1529 FnName = IdentifierStr;
1530 Kind = 0;
1531 getNextToken();
1532 break;
1533 case tok_unary:
1534 getNextToken();
1535 if (!isascii(CurTok))
1536 return ErrorP("Expected unary operator");
1537 FnName = "unary";
1538 FnName += (char)CurTok;
1539 Kind = 1;
1540 getNextToken();
1541 break;
1542 case tok_binary:
1543 getNextToken();
1544 if (!isascii(CurTok))
1545 return ErrorP("Expected binary operator");
1546 FnName = "binary";
1547 FnName += (char)CurTok;
1548 Kind = 2;
1549 getNextToken();
1551 // Read the precedence if present.
1552 if (CurTok == tok_number) {
1554 return ErrorP("Invalid precedecnce: must be 1..100");
1555 BinaryPrecedence = (unsigned)NumVal;
1556 getNextToken();
1557 }
1558 break;
1559 }
1561 if (CurTok != '(')
1562 return ErrorP("Expected '(' in prototype");
1565 while (getNextToken() == tok_identifier)
1566 ArgNames.push_back(IdentifierStr);
1567 if (CurTok != ')')
1568 return ErrorP("Expected ')' in prototype");
1570 // success.
1571 getNextToken(); // eat ')'.
1573 // Verify right number of names for operator.
1574 if (Kind && ArgNames.size() != Kind)
1575 return ErrorP("Invalid number of operands for operator");
1577 return new PrototypeAST(FnName, ArgNames, Kind != 0, BinaryPrecedence);
1578 }
1580 /// definition ::= 'def' prototype expression
1581 static FunctionAST *ParseDefinition() {
1582 getNextToken(); // eat def.
1583 PrototypeAST *Proto = ParsePrototype();
1586 if (ExprAST *E = ParseExpression())
1587 return new FunctionAST(Proto, E);
1588 return 0;
1589 }
1591 /// toplevelexpr ::= expression
1592 static FunctionAST *ParseTopLevelExpr() {
1593 if (ExprAST *E = ParseExpression()) {
1594 // Make an anonymous proto.
1596 return new FunctionAST(Proto, E);
1597 }
1598 return 0;
1599 }
1601 /// external ::= 'extern' prototype
1602 static PrototypeAST *ParseExtern() {
1603 getNextToken(); // eat extern.
1604 return ParsePrototype();
1605 }
1607 //===----------------------------------------------------------------------===//
1608 // Code Generation
1609 //===----------------------------------------------------------------------===//
1611 static Module *TheModule;
1612 static IRBuilder<> Builder(getGlobalContext());
1614 static FunctionPassManager *TheFPM;
1616 Value *ErrorV(const char *Str) { Error(Str); return 0; }
1618 /// CreateEntryBlockAlloca - Create an alloca instruction in the entry block of
1619 /// the function. This is used for mutable variables etc.
1620 static AllocaInst *CreateEntryBlockAlloca(Function *TheFunction,
1621 const std::string &VarName) {
1623 TheFunction->getEntryBlock().begin());
1624 return TmpB.CreateAlloca(Type::getDoubleTy(getGlobalContext()), 0,
1625 VarName.c_str());
1626 }
1628 Value *NumberExprAST::Codegen() {
1629 return ConstantFP::get(getGlobalContext(), APFloat(Val));
1630 }
1632 Value *VariableExprAST::Codegen() {
1633 // Look this variable up in the function.
1634 Value *V = NamedValues[Name];
1637 // Load the value.
1638 return Builder.CreateLoad(V, Name.c_str());
1639 }
1641 Value *UnaryExprAST::Codegen() {
1642 Value *OperandV = Operand->Codegen();
1646 if (F == 0)
1647 return ErrorV("Unknown unary operator");
1649 return Builder.CreateCall(F, OperandV, "unop");
1650 }
1652 Value *BinaryExprAST::Codegen() {
1653 // Special case '=' because we don't want to emit the LHS as an expression.
1654 if (Op == '=') {
1655 // Assignment requires the LHS to be an identifier.
1657 if (!LHSE)
1658 return ErrorV("destination of '=' must be a variable");
1659 // Codegen the RHS.
1660 Value *Val = RHS->Codegen();
1663 // Look up the name.
1664 Value *Variable = NamedValues[LHSE->getName()];
1667 Builder.CreateStore(Val, Variable);
1668 return Val;
1669 }
1671 Value *L = LHS->Codegen();
1672 Value *R = RHS->Codegen();
1675 switch (Op) {
1676 case '+': return Builder.CreateFAdd(L, R, "addtmp");
1677 case '-': return Builder.CreateFSub(L, R, "subtmp");
1678 case '*': return Builder.CreateFMul(L, R, "multmp");
1679 case '<':
1680 L = Builder.CreateFCmpULT(L, R, "cmptmp");
1682 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
1683 "booltmp");
1684 default: break;
1685 }
1687 // If it wasn't a builtin binary operator, it must be a user defined one. Emit
1688 // a call to it.
1692 Value *Ops[] = { L, R };
1694 }
1696 Value *CallExprAST::Codegen() {
1697 // Look up the name in the global module table.
1698 Function *CalleeF = TheModule->getFunction(Callee);
1699 if (CalleeF == 0)
1700 return ErrorV("Unknown function referenced");
1702 // If argument mismatch error.
1703 if (CalleeF->arg_size() != Args.size())
1704 return ErrorV("Incorrect # arguments passed");
1707 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
1708 ArgsV.push_back(Args[i]->Codegen());
1710 }
1712 return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
1713 }
1715 Value *IfExprAST::Codegen() {
1716 Value *CondV = Cond->Codegen();
1719 // Convert condition to a bool by comparing equal to 0.0.
1720 CondV = Builder.CreateFCmpONE(CondV,
1721 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
1722 "ifcond");
1724 Function *TheFunction = Builder.GetInsertBlock()->getParent();
1726 // Create blocks for the then and else cases. Insert the 'then' block at the
1727 // end of the function.
1728 BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunction);
1729 BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else");
1730 BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont");
1732 Builder.CreateCondBr(CondV, ThenBB, ElseBB);
1734 // Emit then value.
1735 Builder.SetInsertPoint(ThenBB);
1737 Value *ThenV = Then->Codegen();
1740 Builder.CreateBr(MergeBB);
1741 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
1742 ThenBB = Builder.GetInsertBlock();
1744 // Emit else block.
1745 TheFunction->getBasicBlockList().push_back(ElseBB);
1746 Builder.SetInsertPoint(ElseBB);
1748 Value *ElseV = Else->Codegen();
1751 Builder.CreateBr(MergeBB);
1752 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
1753 ElseBB = Builder.GetInsertBlock();
1755 // Emit merge block.
1756 TheFunction->getBasicBlockList().push_back(MergeBB);
1757 Builder.SetInsertPoint(MergeBB);
1758 PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()),
1759 "iftmp");
1761 PN->addIncoming(ThenV, ThenBB);
1762 PN->addIncoming(ElseV, ElseBB);
1763 return PN;
1764 }
1766 Value *ForExprAST::Codegen() {
1767 // Output this as:
1768 // var = alloca double
1769 // ...
1770 // start = startexpr
1771 // store start -> var
1772 // goto loop
1773 // loop:
1774 // ...
1775 // bodyexpr
1776 // ...
1777 // loopend:
1778 // step = stepexpr
1779 // endcond = endexpr
1780 //
1781 // curvar = load var
1782 // nextvar = curvar + step
1783 // store nextvar -> var
1784 // br endcond, loop, endloop
1785 // outloop:
1787 Function *TheFunction = Builder.GetInsertBlock()->getParent();
1789 // Create an alloca for the variable in the entry block.
1790 AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);
1792 // Emit the start code first, without 'variable' in scope.
1793 Value *StartVal = Start->Codegen();
1796 // Store the value into the alloca.
1797 Builder.CreateStore(StartVal, Alloca);
1799 // Make the new basic block for the loop header, inserting after current
1800 // block.
1801 BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
1803 // Insert an explicit fall through from the current block to the LoopBB.
1804 Builder.CreateBr(LoopBB);
1806 // Start insertion in LoopBB.
1807 Builder.SetInsertPoint(LoopBB);
1809 // Within the loop, the variable is defined equal to the PHI node. If it
1810 // shadows an existing variable, we have to restore it, so save it now.
1811 AllocaInst *OldVal = NamedValues[VarName];
1812 NamedValues[VarName] = Alloca;
1814 // Emit the body of the loop. This, like any other expr, can change the
1815 // current BB. Note that we ignore the value computed by the body, but don't
1816 // allow an error.
1818 return 0;
1820 // Emit the step value.
1821 Value *StepVal;
1822 if (Step) {
1823 StepVal = Step->Codegen();
1825 } else {
1826 // If not specified, use 1.0.
1827 StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
1828 }
1830 // Compute the end condition.
1831 Value *EndCond = End->Codegen();
1832 if (EndCond == 0) return EndCond;
1834 // Reload, increment, and restore the alloca. This handles the case where
1835 // the body of the loop mutates the variable.
1836 Value *CurVar = Builder.CreateLoad(Alloca, VarName.c_str());
1837 Value *NextVar = Builder.CreateFAdd(CurVar, StepVal, "nextvar");
1838 Builder.CreateStore(NextVar, Alloca);
1840 // Convert condition to a bool by comparing equal to 0.0.
1841 EndCond = Builder.CreateFCmpONE(EndCond,
1842 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
1843 "loopcond");
1845 // Create the "after loop" block and insert it.
1846 BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
1848 // Insert the conditional branch into the end of LoopEndBB.
1849 Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
1851 // Any new code will be inserted in AfterBB.
1852 Builder.SetInsertPoint(AfterBB);
1854 // Restore the unshadowed variable.
1855 if (OldVal)
1856 NamedValues[VarName] = OldVal;
1857 else
1858 NamedValues.erase(VarName);
1861 // for expr always returns 0.0.
1862 return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
1863 }
1865 Value *VarExprAST::Codegen() {
1868 Function *TheFunction = Builder.GetInsertBlock()->getParent();
1870 // Register all variables and emit their initializer.
1871 for (unsigned i = 0, e = VarNames.size(); i != e; ++i) {
1872 const std::string &VarName = VarNames[i].first;
1873 ExprAST *Init = VarNames[i].second;
1875 // Emit the initializer before adding the variable to scope, this prevents
1876 // the initializer from referencing the variable itself, and permits stuff
1877 // like this:
1878 // var a = 1 in
1879 // var a = a in ... # refers to outer 'a'.
1880 Value *InitVal;
1881 if (Init) {
1882 InitVal = Init->Codegen();
1884 } else { // If not specified, use 0.0.
1885 InitVal = ConstantFP::get(getGlobalContext(), APFloat(0.0));
1886 }
1888 AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);
1889 Builder.CreateStore(InitVal, Alloca);
1891 // Remember the old variable binding so that we can restore the binding when
1892 // we unrecurse.
1893 OldBindings.push_back(NamedValues[VarName]);
1895 // Remember this binding.
1896 NamedValues[VarName] = Alloca;
1897 }
1899 // Codegen the body, now that all vars are in scope.
1900 Value *BodyVal = Body->Codegen();
1903 // Pop all our variables from scope.
1904 for (unsigned i = 0, e = VarNames.size(); i != e; ++i)
1905 NamedValues[VarNames[i].first] = OldBindings[i];
1907 // Return the body computation.
1908 return BodyVal;
1909 }
1911 Function *PrototypeAST::Codegen() {
1912 // Make the function type: double(double,double) etc.
1914 Type::getDoubleTy(getGlobalContext()));
1915 FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()),
1916 Doubles, false);
1918 Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
1920 // If F conflicted, there was already something named 'Name'. If it has a
1921 // body, don't allow redefinition or reextern.
1922 if (F->getName() != Name) {
1923 // Delete the one we just made and get the existing one.
1924 F->eraseFromParent();
1925 F = TheModule->getFunction(Name);
1927 // If F already has a body, reject this.
1928 if (!F->empty()) {
1929 ErrorF("redefinition of function");
1930 return 0;
1931 }
1933 // If F took a different number of args, reject.
1934 if (F->arg_size() != Args.size()) {
1935 ErrorF("redefinition of function with different # args");
1936 return 0;
1937 }
1938 }
1940 // Set names for all arguments.
1941 unsigned Idx = 0;
1942 for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
1943 ++AI, ++Idx)
1944 AI->setName(Args[Idx]);
1946 return F;
1947 }
1949 /// CreateArgumentAllocas - Create an alloca for each argument and register the
1950 /// argument in the symbol table so that references to it will succeed.
1951 void PrototypeAST::CreateArgumentAllocas(Function *F) {
1952 Function::arg_iterator AI = F->arg_begin();
1953 for (unsigned Idx = 0, e = Args.size(); Idx != e; ++Idx, ++AI) {
1954 // Create an alloca for this variable.
1955 AllocaInst *Alloca = CreateEntryBlockAlloca(F, Args[Idx]);
1957 // Store the initial value into the alloca.
1958 Builder.CreateStore(AI, Alloca);
1960 // Add arguments to variable symbol table.
1961 NamedValues[Args[Idx]] = Alloca;
1962 }
1963 }
1965 Function *FunctionAST::Codegen() {
1966 NamedValues.clear();
1968 Function *TheFunction = Proto->Codegen();
1969 if (TheFunction == 0)
1970 return 0;
1972 // If this is an operator, install it.
1973 if (Proto->isBinaryOp())
1976 // Create a new basic block to start insertion into.
1977 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
1978 Builder.SetInsertPoint(BB);
1980 // Add all arguments to the symbol table and create their allocas.
1981 Proto->CreateArgumentAllocas(TheFunction);
1983 if (Value *RetVal = Body->Codegen()) {
1984 // Finish off the function.
1985 Builder.CreateRet(RetVal);
1987 // Validate the generated code, checking for consistency.
1988 verifyFunction(*TheFunction);
1990 // Optimize the function.
1991 TheFPM->run(*TheFunction);
1993 return TheFunction;
1994 }
1996 // Error reading body, remove function.
1997 TheFunction->eraseFromParent();
1999 if (Proto->isBinaryOp())
2000 BinopPrecedence.erase(Proto->getOperatorName());
2001 return 0;
2002 }
2004 //===----------------------------------------------------------------------===//
2005 // Top-Level parsing and JIT Driver
2006 //===----------------------------------------------------------------------===//
2008 static ExecutionEngine *TheExecutionEngine;
2010 static void HandleDefinition() {
2011 if (FunctionAST *F = ParseDefinition()) {
2012 if (Function *LF = F->Codegen()) {
2013 fprintf(stderr, "Read function definition:");
2014 LF->dump();
2015 }
2016 } else {
2017 // Skip token for error recovery.
2018 getNextToken();
2019 }
2020 }
2022 static void HandleExtern() {
2023 if (PrototypeAST *P = ParseExtern()) {
2024 if (Function *F = P->Codegen()) {
2025 fprintf(stderr, "Read extern: ");
2026 F->dump();
2027 }
2028 } else {
2029 // Skip token for error recovery.
2030 getNextToken();
2031 }
2032 }
2034 static void HandleTopLevelExpression() {
2035 // Evaluate a top-level expression into an anonymous function.
2036 if (FunctionAST *F = ParseTopLevelExpr()) {
2037 if (Function *LF = F->Codegen()) {
2038 // JIT the function, returning a function pointer.
2039 void *FPtr = TheExecutionEngine->getPointerToFunction(LF);
2041 // Cast it to the right type (takes no arguments, returns a double) so we
2042 // can call it as a native function.
2043 double (*FP)() = (double (*)())(intptr_t)FPtr;
2044 fprintf(stderr, "Evaluated to %f\n", FP());
2045 }
2046 } else {
2047 // Skip token for error recovery.
2048 getNextToken();
2049 }
2050 }
2052 /// top ::= definition | external | expression | ';'
2053 static void MainLoop() {
2054 while (1) {
2055 fprintf(stderr, "ready> ");
2056 switch (CurTok) {
2057 case tok_eof: return;
2058 case ';': getNextToken(); break; // ignore top-level semicolons.
2059 case tok_def: HandleDefinition(); break;
2060 case tok_extern: HandleExtern(); break;
2061 default: HandleTopLevelExpression(); break;
2062 }
2063 }
2064 }
2066 //===----------------------------------------------------------------------===//
2068 //===----------------------------------------------------------------------===//
2070 /// putchard - putchar that takes a double and returns 0.
2071 extern "C"
2072 double putchard(double X) {
2073 putchar((char)X);
2074 return 0;
2075 }
2078 extern "C"
2079 double printd(double X) {
2080 printf("%f\n", X);
2081 return 0;
2082 }
2084 //===----------------------------------------------------------------------===//
2085 // Main driver code.
2086 //===----------------------------------------------------------------------===//
2088 int main() {
2089 InitializeNativeTarget();
2090 LLVMContext &Context = getGlobalContext();
2092 // Install standard binary operators.
2093 // 1 is lowest precedence.
2094 BinopPrecedence['='] = 2;
2096 BinopPrecedence['+'] = 20;
2097 BinopPrecedence['-'] = 20;
2098 BinopPrecedence['*'] = 40; // highest.
2100 // Prime the first token.
2101 fprintf(stderr, "ready> ");
2102 getNextToken();
2104 // Make the module, which holds all the code.
2105 TheModule = new Module("my cool jit", Context);
2107 // Create the JIT. This takes ownership of the module.
2108 std::string ErrStr;
2109 TheExecutionEngine = EngineBuilder(TheModule).setErrorStr(&ErrStr).create();
2110 if (!TheExecutionEngine) {
2111 fprintf(stderr, "Could not create ExecutionEngine: %s\n", ErrStr.c_str());
2112 exit(1);
2113 }
2115 FunctionPassManager OurFPM(TheModule);
2117 // Set up the optimizer pipeline. Start with registering info about how the
2118 // target lays out data structures.
2119 OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData()));
2120 // Provide basic AliasAnalysis support for GVN.
2121 OurFPM.add(createBasicAliasAnalysisPass());
2122 // Promote allocas to registers.
2123 OurFPM.add(createPromoteMemoryToRegisterPass());
2124 // Do simple "peephole" optimizations and bit-twiddling optzns.
2125 OurFPM.add(createInstructionCombiningPass());
2126 // Reassociate expressions.
2127 OurFPM.add(createReassociatePass());
2128 // Eliminate Common SubExpressions.
2129 OurFPM.add(createGVNPass());
2130 // Simplify the control flow graph (deleting unreachable blocks, etc).
2131 OurFPM.add(createCFGSimplificationPass());
2133 OurFPM.doInitialization();
2135 // Set the global so the code gen can use this.
2136 TheFPM = &OurFPM;
2138 // Run the main "interpreter loop" now.
2139 MainLoop();
2141 TheFPM = 0;
2143 // Print out all of the generated code.
2144 TheModule->dump();
2146 return 0;
2147 }
2148 </pre>
2149 </div>
2152 </div>
2154 <!-- *********************************************************************** -->
2155 <hr>
2156 <address>
2164 Last modified: $Date$
2165 </address>
2166 </body>
2167 </html>