| blob | 79bf5f82aa973849cef9586fa4d5dd3c7460a005 |
4 <html>
5 <head>
10 </head>
12 <body>
16 <ul>
19 <ol>
22 <ol>
28 </ol>
29 </li>
31 <ol>
37 </ol>
38 </li>
40 </ol>
41 </li>
43 User-defined Operators</li>
44 </ul>
48 </div>
50 <!-- *********************************************************************** -->
52 <!-- *********************************************************************** -->
58 Kaleidoscope language and included support for generating LLVM IR, followed by
59 optimizations and a JIT compiler. Unfortunately, as presented, Kaleidoscope is
60 mostly useless: it has no control flow other than call and return. This means
61 that you can't have conditional branches in the code, significantly limiting its
62 power. In this episode of "build that compiler", we'll extend Kaleidoscope to
63 have an if/then/else expression plus a simple 'for' loop.</p>
65 </div>
67 <!-- *********************************************************************** -->
69 <!-- *********************************************************************** -->
73 <p>
74 Extending Kaleidoscope to support if/then/else is quite straightforward. It
75 basically requires adding lexer support for this "new" concept to the lexer,
76 parser, AST, and LLVM code emitter. This example is nice, because it shows how
77 easy it is to "grow" a language over time, incrementally extending it as new
78 ideas are discovered.</p>
81 want. The basic idea is that we want to be able to write this sort of thing:
82 </p>
85 <pre>
86 def fib(x)
88 1
89 else
91 </pre>
92 </div>
94 <p>In Kaleidoscope, every construct is an expression: there are no statements.
95 As such, the if/then/else expression needs to return a value like any other.
96 Since we're using a mostly functional form, we'll have it evaluate its
97 conditional, then return the 'then' or 'else' value based on how the condition
100 <p>The semantics of the if/then/else expression is that it evaluates the
101 condition to a boolean equality value: 0.0 is considered to be false and
102 everything else is considered to be true.
103 If the condition is true, the first subexpression is evaluated and returned, if
104 the condition is false, the second subexpression is evaluated and returned.
105 Since Kaleidoscope allows side-effects, this behavior is important to nail down.
106 </p>
109 pieces.</p>
111 </div>
113 <!-- ======================================================================= -->
115 If/Then/Else</a></div>
116 <!-- ======================================================================= -->
121 <p>The lexer extensions are straightforward. First we add new enum values
122 for the relevant tokens:</p>
125 <pre>
126 // control
128 </pre>
129 </div>
131 <p>Once we have that, we recognize the new keywords in the lexer. This is pretty simple
132 stuff:</p>
135 <pre>
136 ...
137 if (IdentifierStr == "def") return tok_def;
138 if (IdentifierStr == "extern") return tok_extern;
140 if (IdentifierStr == "then") return tok_then;
142 return tok_identifier;
143 </pre>
144 </div>
146 </div>
148 <!-- ======================================================================= -->
150 If/Then/Else</a></div>
151 <!-- ======================================================================= -->
158 <pre>
159 /// IfExprAST - Expression class for if/then/else.
160 class IfExprAST : public ExprAST {
161 ExprAST *Cond, *Then, *Else;
162 public:
163 IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
164 : Cond(cond), Then(then), Else(_else) {}
165 virtual Value *Codegen();
166 };
167 </pre>
168 </div>
172 </div>
174 <!-- ======================================================================= -->
176 If/Then/Else</a></div>
177 <!-- ======================================================================= -->
181 <p>Now that we have the relevant tokens coming from the lexer and we have the
182 AST node to build, our parsing logic is relatively straightforward. First we
183 define a new parsing function:</p>
186 <pre>
187 /// ifexpr ::= 'if' expression 'then' expression 'else' expression
188 static ExprAST *ParseIfExpr() {
189 getNextToken(); // eat the if.
191 // condition.
192 ExprAST *Cond = ParseExpression();
193 if (!Cond) return 0;
195 if (CurTok != tok_then)
196 return Error("expected then");
197 getNextToken(); // eat the then
199 ExprAST *Then = ParseExpression();
202 if (CurTok != tok_else)
203 return Error("expected else");
205 getNextToken();
207 ExprAST *Else = ParseExpression();
208 if (!Else) return 0;
210 return new IfExprAST(Cond, Then, Else);
211 }
212 </pre>
213 </div>
218 <pre>
219 static ExprAST *ParsePrimary() {
220 switch (CurTok) {
221 default: return Error("unknown token when expecting an expression");
222 case tok_identifier: return ParseIdentifierExpr();
223 case tok_number: return ParseNumberExpr();
224 case '(': return ParseParenExpr();
226 }
227 }
228 </pre>
229 </div>
231 </div>
233 <!-- ======================================================================= -->
235 <!-- ======================================================================= -->
239 <p>Now that we have it parsing and building the AST, the final piece is adding
240 LLVM code generation support. This is the most interesting part of the
241 if/then/else example, because this is where it starts to introduce new concepts.
242 All of the code above has been thoroughly described in previous chapters.
243 </p>
245 <p>To motivate the code we want to produce, lets take a look at a simple
246 example. Consider:</p>
249 <pre>
250 extern foo();
251 extern bar();
252 def baz(x) if x then foo() else bar();
253 </pre>
254 </div>
256 <p>If you disable optimizations, the code you'll (soon) get from Kaleidoscope
257 looks like this:</p>
260 <pre>
261 declare double @foo()
263 declare double @bar()
265 define double @baz(double %x) {
266 entry:
267 %ifcond = fcmp one double %x, 0.000000e+00
268 br i1 %ifcond, label %then, label %else
270 then: ; preds = %entry
271 %calltmp = call double @foo()
272 br label %ifcont
274 else: ; preds = %entry
275 %calltmp1 = call double @bar()
276 br label %ifcont
278 ifcont: ; preds = %else, %then
279 %iftmp = phi double [ %calltmp, %then ], [ %calltmp1, %else ]
280 ret double %iftmp
281 }
282 </pre>
283 </div>
285 <p>To visualize the control flow graph, you can use a nifty feature of the LLVM
289 see this graph:</p>
296 inserting actual calls into the code and recompiling or by calling these in the
297 debugger. LLVM has many nice features for visualizing various graphs.</p>
299 <p>Getting back to the generated code, it is fairly simple: the entry block
300 evaluates the conditional expression ("x" in our case here) and compares the
302 instruction ('one' is "Ordered and Not Equal"). Based on the result of this
304 the expressions for the true/false cases.</p>
306 <p>Once the then/else blocks are finished executing, they both branch back to the
307 'ifcont' block to execute the code that happens after the if/then/else. In this
308 case the only thing left to do is to return to the caller of the function. The
309 question then becomes: how does the code know which expression to return?</p>
311 <p>The answer to this question involves an important SSA operation: the
315 article</a> is a good introduction and there are various other introductions to
316 it available on your favorite search engine. The short version is that
318 from. The Phi operation takes on the value corresponding to the input control
319 block. In this case, if control comes in from the "then" block, it gets the
324 simple and elegant front-end will have to start generating SSA form in order to
325 use LLVM!". Fortunately, this is not the case, and we strongly advise
327 unless there is an amazingly good reason to do so. In practice, there are two
328 sorts of values that float around in code written for your average imperative
329 programming language that might need Phi nodes:</p>
331 <ol>
333 <li>Values that are implicit in the structure of your AST, such as the Phi node
334 in this case.</li>
335 </ol>
339 in depth. For now, just believe me that you don't need SSA construction to
340 handle this case. For #2, you have the choice of using the techniques that we will
341 describe for #1, or you can insert Phi nodes directly, if convenient. In this
342 case, it is really really easy to generate the Phi node, so we choose to do it
343 directly.</p>
347 </div>
349 <!-- ======================================================================= -->
351 If/Then/Else</a></div>
352 <!-- ======================================================================= -->
360 <pre>
361 Value *IfExprAST::Codegen() {
362 Value *CondV = Cond->Codegen();
365 // Convert condition to a bool by comparing equal to 0.0.
366 CondV = Builder.CreateFCmpONE(CondV,
367 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
368 "ifcond");
369 </pre>
370 </div>
372 <p>This code is straightforward and similar to what we saw before. We emit the
373 expression for the condition, then compare that value to zero to get a truth
377 <pre>
378 Function *TheFunction = Builder.GetInsertBlock()->getParent();
380 // Create blocks for the then and else cases. Insert the 'then' block at the
381 // end of the function.
382 BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunction);
383 BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else");
384 BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont");
386 Builder.CreateCondBr(CondV, ThenBB, ElseBB);
387 </pre>
388 </div>
390 <p>This code creates the basic blocks that are related to the if/then/else
391 statement, and correspond directly to the blocks in the example above. The
392 first line gets the current Function object that is being built. It
393 gets this by asking the builder for the current BasicBlock, and asking that
397 into the constructor for the "then" block. This causes the constructor to
398 automatically insert the new block into the end of the specified function. The
399 other two blocks are created, but aren't yet inserted into the function.</p>
401 <p>Once the blocks are created, we can emit the conditional branch that chooses
402 between them. Note that creating new blocks does not implicitly affect the
403 IRBuilder, so it is still inserting into the block that the condition
404 went into. Also note that it is creating a branch to the "then" block and the
406 This is all ok: it is the standard way that LLVM supports forward
407 references.</p>
410 <pre>
411 // Emit then value.
412 Builder.SetInsertPoint(ThenBB);
414 Value *ThenV = Then->Codegen();
417 Builder.CreateBr(MergeBB);
418 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
419 ThenBB = Builder.GetInsertBlock();
420 </pre>
421 </div>
423 <p>After the conditional branch is inserted, we move the builder to start
424 inserting into the "then" block. Strictly speaking, this call moves the
425 insertion point to be at the end of the specified block. However, since the
426 "then" block is empty, it also starts out by inserting at the beginning of the
427 block. :)</p>
430 from the AST. To finish off the "then" block, we create an unconditional branch
431 to the merge block. One interesting (and very important) aspect of the LLVM IR
434 instruction</a> such as return or branch. This means that all control flow,
436 violate this rule, the verifier will emit an error.</p>
438 <p>The final line here is quite subtle, but is very important. The basic issue
439 is that when we create the Phi node in the merge block, we need to set up the
440 block/value pairs that indicate how the Phi will work. Importantly, the Phi
441 node expects to have an entry for each predecessor of the block in the CFG. Why
442 then, are we getting the current block when we just set it to ThenBB 5 lines
443 above? The problem is that the "Then" expression may actually itself change the
444 block that the Builder is emitting into if, for example, it contains a nested
445 "if/then/else" expression. Because calling Codegen recursively could
446 arbitrarily change the notion of the current block, we are required to get an
447 up-to-date value for code that will set up the Phi node.</p>
450 <pre>
451 // Emit else block.
452 TheFunction->getBasicBlockList().push_back(ElseBB);
453 Builder.SetInsertPoint(ElseBB);
455 Value *ElseV = Else->Codegen();
458 Builder.CreateBr(MergeBB);
459 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
460 ElseBB = Builder.GetInsertBlock();
461 </pre>
462 </div>
464 <p>Code generation for the 'else' block is basically identical to codegen for
465 the 'then' block. The only significant difference is the first line, which adds
466 the 'else' block to the function. Recall previously that the 'else' block was
467 created, but not added to the function. Now that the 'then' and 'else' blocks
468 are emitted, we can finish up with the merge code:</p>
471 <pre>
472 // Emit merge block.
473 TheFunction->getBasicBlockList().push_back(MergeBB);
474 Builder.SetInsertPoint(MergeBB);
475 PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()),
476 "iftmp");
478 PN->addIncoming(ThenV, ThenBB);
479 PN->addIncoming(ElseV, ElseBB);
480 return PN;
481 }
482 </pre>
483 </div>
486 to the Function object (it was previously floating, like the else block above).
487 The second block changes the insertion point so that newly created code will go
488 into the "merge" block. Once that is done, we need to create the PHI node and
489 set up the block/value pairs for the PHI.</p>
491 <p>Finally, the CodeGen function returns the phi node as the value computed by
492 the if/then/else expression. In our example above, this returned value will
493 feed into the code for the top-level function, which will create the return
494 instruction.</p>
496 <p>Overall, we now have the ability to execute conditional code in
497 Kaleidoscope. With this extension, Kaleidoscope is a fairly complete language
498 that can calculate a wide variety of numeric functions. Next up we'll add
499 another useful expression that is familiar from non-functional languages...</p>
501 </div>
503 <!-- *********************************************************************** -->
505 <!-- *********************************************************************** -->
509 <p>Now that we know how to add basic control flow constructs to the language,
510 we have the tools to add more powerful things. Lets add something more
511 aggressive, a 'for' expression:</p>
514 <pre>
515 extern putchard(char)
516 def printstar(n)
520 # print 100 '*' characters
521 printstar(100);
522 </pre>
523 </div>
526 a starting value, while the condition ("i < n" in this case) is true,
527 incrementing by an optional step value ("1.0" in this case). If the step value
528 is omitted, it defaults to 1.0. While the loop is true, it executes its
529 body expression. Because we don't have anything better to return, we'll just
530 define the loop as always returning 0.0. In the future when we have mutable
531 variables, it will get more useful.</p>
533 <p>As before, lets talk about the changes that we need to Kaleidoscope to
534 support this.</p>
536 </div>
538 <!-- ======================================================================= -->
540 the 'for' Loop</a></div>
541 <!-- ======================================================================= -->
548 <pre>
549 ... in enum Token ...
550 // control
554 ... in gettok ...
555 if (IdentifierStr == "def") return tok_def;
556 if (IdentifierStr == "extern") return tok_extern;
557 if (IdentifierStr == "if") return tok_if;
558 if (IdentifierStr == "then") return tok_then;
559 if (IdentifierStr == "else") return tok_else;
562 return tok_identifier;
563 </pre>
564 </div>
566 </div>
568 <!-- ======================================================================= -->
570 the 'for' Loop</a></div>
571 <!-- ======================================================================= -->
575 <p>The AST node is just as simple. It basically boils down to capturing
576 the variable name and the constituent expressions in the node.</p>
579 <pre>
580 /// ForExprAST - Expression class for for/in.
581 class ForExprAST : public ExprAST {
582 std::string VarName;
583 ExprAST *Start, *End, *Step, *Body;
584 public:
585 ForExprAST(const std::string &varname, ExprAST *start, ExprAST *end,
586 ExprAST *step, ExprAST *body)
587 : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
588 virtual Value *Codegen();
589 };
590 </pre>
591 </div>
593 </div>
595 <!-- ======================================================================= -->
597 the 'for' Loop</a></div>
598 <!-- ======================================================================= -->
602 <p>The parser code is also fairly standard. The only interesting thing here is
603 handling of the optional step value. The parser code handles it by checking to
604 see if the second comma is present. If not, it sets the step value to null in
605 the AST node:</p>
608 <pre>
609 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
610 static ExprAST *ParseForExpr() {
611 getNextToken(); // eat the for.
613 if (CurTok != tok_identifier)
614 return Error("expected identifier after for");
616 std::string IdName = IdentifierStr;
617 getNextToken(); // eat identifier.
619 if (CurTok != '=')
620 return Error("expected '=' after for");
621 getNextToken(); // eat '='.
624 ExprAST *Start = ParseExpression();
626 if (CurTok != ',')
627 return Error("expected ',' after for start value");
628 getNextToken();
630 ExprAST *End = ParseExpression();
633 // The step value is optional.
634 ExprAST *Step = 0;
635 if (CurTok == ',') {
636 getNextToken();
637 Step = ParseExpression();
639 }
641 if (CurTok != tok_in)
642 return Error("expected 'in' after for");
643 getNextToken(); // eat 'in'.
645 ExprAST *Body = ParseExpression();
648 return new ForExprAST(IdName, Start, End, Step, Body);
649 }
650 </pre>
651 </div>
653 </div>
655 <!-- ======================================================================= -->
657 the 'for' Loop</a></div>
658 <!-- ======================================================================= -->
662 <p>Now we get to the good part: the LLVM IR we want to generate for this thing.
663 With the simple example above, we get this LLVM IR (note that this dump is
664 generated with optimizations disabled for clarity):
665 </p>
668 <pre>
669 declare double @putchard(double)
671 define double @printstar(double %n) {
672 entry:
673 ; initial value = 1.0 (inlined into phi)
674 br label %loop
676 loop: ; preds = %loop, %entry
677 %i = phi double [ 1.000000e+00, %entry ], [ %nextvar, %loop ]
678 ; body
679 %calltmp = call double @putchard(double 4.200000e+01)
680 ; increment
681 %nextvar = fadd double %i, 1.000000e+00
683 ; termination test
684 %cmptmp = fcmp ult double %i, %n
685 %booltmp = uitofp i1 %cmptmp to double
686 %loopcond = fcmp one double %booltmp, 0.000000e+00
687 br i1 %loopcond, label %loop, label %afterloop
689 afterloop: ; preds = %loop
690 ; loop always returns 0.0
691 ret double 0.000000e+00
692 }
693 </pre>
694 </div>
696 <p>This loop contains all the same constructs we saw before: a phi node, several
697 expressions, and some basic blocks. Lets see how this fits together.</p>
699 </div>
701 <!-- ======================================================================= -->
703 the 'for' Loop</a></div>
704 <!-- ======================================================================= -->
708 <p>The first part of Codegen is very simple: we just output the start expression
709 for the loop value:</p>
712 <pre>
713 Value *ForExprAST::Codegen() {
714 // Emit the start code first, without 'variable' in scope.
715 Value *StartVal = Start->Codegen();
717 </pre>
718 </div>
720 <p>With this out of the way, the next step is to set up the LLVM basic block
721 for the start of the loop body. In the case above, the whole loop body is one
722 block, but remember that the body code itself could consist of multiple blocks
723 (e.g. if it contains an if/then/else or a for/in expression).</p>
726 <pre>
727 // Make the new basic block for the loop header, inserting after current
728 // block.
729 Function *TheFunction = Builder.GetInsertBlock()->getParent();
730 BasicBlock *PreheaderBB = Builder.GetInsertBlock();
731 BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
733 // Insert an explicit fall through from the current block to the LoopBB.
734 Builder.CreateBr(LoopBB);
735 </pre>
736 </div>
738 <p>This code is similar to what we saw for if/then/else. Because we will need
739 it to create the Phi node, we remember the block that falls through into the
740 loop. Once we have that, we create the actual block that starts the loop and
741 create an unconditional branch for the fall-through between the two blocks.</p>
744 <pre>
745 // Start insertion in LoopBB.
746 Builder.SetInsertPoint(LoopBB);
748 // Start the PHI node with an entry for Start.
749 PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), VarName.c_str());
750 Variable->addIncoming(StartVal, PreheaderBB);
751 </pre>
752 </div>
755 for the loop body. To begin with, we move the insertion point and create the
756 PHI node for the loop induction variable. Since we already know the incoming
757 value for the starting value, we add it to the Phi node. Note that the Phi will
758 eventually get a second value for the backedge, but we can't set it up yet
759 (because it doesn't exist!).</p>
762 <pre>
763 // Within the loop, the variable is defined equal to the PHI node. If it
764 // shadows an existing variable, we have to restore it, so save it now.
765 Value *OldVal = NamedValues[VarName];
766 NamedValues[VarName] = Variable;
768 // Emit the body of the loop. This, like any other expr, can change the
769 // current BB. Note that we ignore the value computed by the body, but don't
770 // allow an error.
772 return 0;
773 </pre>
774 </div>
776 <p>Now the code starts to get more interesting. Our 'for' loop introduces a new
777 variable to the symbol table. This means that our symbol table can now contain
778 either function arguments or loop variables. To handle this, before we codegen
779 the body of the loop, we add the loop variable as the current value for its
780 name. Note that it is possible that there is a variable of the same name in the
781 outer scope. It would be easy to make this an error (emit an error and return
782 null if there is already an entry for VarName) but we choose to allow shadowing
783 of variables. In order to handle this correctly, we remember the Value that
785 no shadowed variable).</p>
787 <p>Once the loop variable is set into the symbol table, the code recursively
788 codegen's the body. This allows the body to use the loop variable: any
789 references to it will naturally find it in the symbol table.</p>
792 <pre>
793 // Emit the step value.
794 Value *StepVal;
795 if (Step) {
796 StepVal = Step->Codegen();
798 } else {
799 // If not specified, use 1.0.
800 StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
801 }
803 Value *NextVar = Builder.CreateFAdd(Variable, StepVal, "nextvar");
804 </pre>
805 </div>
807 <p>Now that the body is emitted, we compute the next value of the iteration
809 will be the value of the loop variable on the next iteration of the loop.</p>
812 <pre>
813 // Compute the end condition.
814 Value *EndCond = End->Codegen();
815 if (EndCond == 0) return EndCond;
817 // Convert condition to a bool by comparing equal to 0.0.
818 EndCond = Builder.CreateFCmpONE(EndCond,
819 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
820 "loopcond");
821 </pre>
822 </div>
824 <p>Finally, we evaluate the exit value of the loop, to determine whether the
825 loop should exit. This mirrors the condition evaluation for the if/then/else
826 statement.</p>
829 <pre>
830 // Create the "after loop" block and insert it.
831 BasicBlock *LoopEndBB = Builder.GetInsertBlock();
832 BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
834 // Insert the conditional branch into the end of LoopEndBB.
835 Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
837 // Any new code will be inserted in AfterBB.
838 Builder.SetInsertPoint(AfterBB);
839 </pre>
840 </div>
842 <p>With the code for the body of the loop complete, we just need to finish up
843 the control flow for it. This code remembers the end block (for the phi node), then creates the block for the loop exit ("afterloop"). Based on the value of the
844 exit condition, it creates a conditional branch that chooses between executing
845 the loop again and exiting the loop. Any future code is emitted in the
849 <pre>
850 // Add a new entry to the PHI node for the backedge.
851 Variable->addIncoming(NextVar, LoopEndBB);
853 // Restore the unshadowed variable.
854 if (OldVal)
855 NamedValues[VarName] = OldVal;
856 else
857 NamedValues.erase(VarName);
859 // for expr always returns 0.0.
860 return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
861 }
862 </pre>
863 </div>
866 value, we can add the incoming value to the loop PHI node. After that, we
867 remove the loop variable from the symbol table, so that it isn't in scope after
868 the for loop. Finally, code generation of the for loop always returns 0.0, so
872 the tutorial. In this chapter we added two control flow constructs, and used them to motivate a couple of aspects of the LLVM IR that are important for front-end implementors
873 to know. In the next chapter of our saga, we will get a bit crazier and add
875 language.</p>
877 </div>
879 <!-- *********************************************************************** -->
881 <!-- *********************************************************************** -->
885 <p>
886 Here is the complete code listing for our running example, enhanced with the
887 if/then/else and for expressions.. To build this example, use:
888 </p>
891 <pre>
892 # Compile
893 g++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o toy
894 # Run
895 ./toy
896 </pre>
897 </div>
902 <pre>
903 #include "llvm/DerivedTypes.h"
904 #include "llvm/ExecutionEngine/ExecutionEngine.h"
905 #include "llvm/ExecutionEngine/JIT.h"
906 #include "llvm/LLVMContext.h"
907 #include "llvm/Module.h"
908 #include "llvm/PassManager.h"
909 #include "llvm/Analysis/Verifier.h"
910 #include "llvm/Target/TargetData.h"
911 #include "llvm/Target/TargetSelect.h"
912 #include "llvm/Transforms/Scalar.h"
913 #include "llvm/Support/IRBuilder.h"
918 using namespace llvm;
920 //===----------------------------------------------------------------------===//
921 // Lexer
922 //===----------------------------------------------------------------------===//
925 // of these for known things.
926 enum Token {
927 tok_eof = -1,
929 // commands
932 // primary
935 // control
938 };
940 static std::string IdentifierStr; // Filled in if tok_identifier
941 static double NumVal; // Filled in if tok_number
943 /// gettok - Return the next token from standard input.
944 static int gettok() {
945 static int LastChar = ' ';
947 // Skip any whitespace.
948 while (isspace(LastChar))
949 LastChar = getchar();
951 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
952 IdentifierStr = LastChar;
953 while (isalnum((LastChar = getchar())))
954 IdentifierStr += LastChar;
956 if (IdentifierStr == "def") return tok_def;
957 if (IdentifierStr == "extern") return tok_extern;
958 if (IdentifierStr == "if") return tok_if;
959 if (IdentifierStr == "then") return tok_then;
960 if (IdentifierStr == "else") return tok_else;
961 if (IdentifierStr == "for") return tok_for;
962 if (IdentifierStr == "in") return tok_in;
963 return tok_identifier;
964 }
967 std::string NumStr;
968 do {
969 NumStr += LastChar;
970 LastChar = getchar();
971 } while (isdigit(LastChar) || LastChar == '.');
973 NumVal = strtod(NumStr.c_str(), 0);
974 return tok_number;
975 }
977 if (LastChar == '#') {
978 // Comment until end of line.
979 do LastChar = getchar();
982 if (LastChar != EOF)
983 return gettok();
984 }
986 // Check for end of file. Don't eat the EOF.
987 if (LastChar == EOF)
988 return tok_eof;
990 // Otherwise, just return the character as its ascii value.
991 int ThisChar = LastChar;
992 LastChar = getchar();
993 return ThisChar;
994 }
996 //===----------------------------------------------------------------------===//
997 // Abstract Syntax Tree (aka Parse Tree)
998 //===----------------------------------------------------------------------===//
1000 /// ExprAST - Base class for all expression nodes.
1001 class ExprAST {
1002 public:
1003 virtual ~ExprAST() {}
1004 virtual Value *Codegen() = 0;
1005 };
1007 /// NumberExprAST - Expression class for numeric literals like "1.0".
1008 class NumberExprAST : public ExprAST {
1009 double Val;
1010 public:
1011 NumberExprAST(double val) : Val(val) {}
1012 virtual Value *Codegen();
1013 };
1015 /// VariableExprAST - Expression class for referencing a variable, like "a".
1016 class VariableExprAST : public ExprAST {
1017 std::string Name;
1018 public:
1019 VariableExprAST(const std::string &name) : Name(name) {}
1020 virtual Value *Codegen();
1021 };
1023 /// BinaryExprAST - Expression class for a binary operator.
1024 class BinaryExprAST : public ExprAST {
1025 char Op;
1026 ExprAST *LHS, *RHS;
1027 public:
1028 BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
1029 : Op(op), LHS(lhs), RHS(rhs) {}
1030 virtual Value *Codegen();
1031 };
1033 /// CallExprAST - Expression class for function calls.
1034 class CallExprAST : public ExprAST {
1035 std::string Callee;
1037 public:
1039 : Callee(callee), Args(args) {}
1040 virtual Value *Codegen();
1041 };
1043 /// IfExprAST - Expression class for if/then/else.
1044 class IfExprAST : public ExprAST {
1045 ExprAST *Cond, *Then, *Else;
1046 public:
1047 IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
1048 : Cond(cond), Then(then), Else(_else) {}
1049 virtual Value *Codegen();
1050 };
1052 /// ForExprAST - Expression class for for/in.
1053 class ForExprAST : public ExprAST {
1054 std::string VarName;
1055 ExprAST *Start, *End, *Step, *Body;
1056 public:
1057 ForExprAST(const std::string &varname, ExprAST *start, ExprAST *end,
1058 ExprAST *step, ExprAST *body)
1059 : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
1060 virtual Value *Codegen();
1061 };
1063 /// PrototypeAST - This class represents the "prototype" for a function,
1064 /// which captures its name, and its argument names (thus implicitly the number
1065 /// of arguments the function takes).
1066 class PrototypeAST {
1067 std::string Name;
1069 public:
1071 : Name(name), Args(args) {}
1073 Function *Codegen();
1074 };
1076 /// FunctionAST - This class represents a function definition itself.
1077 class FunctionAST {
1078 PrototypeAST *Proto;
1079 ExprAST *Body;
1080 public:
1081 FunctionAST(PrototypeAST *proto, ExprAST *body)
1082 : Proto(proto), Body(body) {}
1084 Function *Codegen();
1085 };
1087 //===----------------------------------------------------------------------===//
1088 // Parser
1089 //===----------------------------------------------------------------------===//
1091 /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
1092 /// token the parser is looking at. getNextToken reads another token from the
1093 /// lexer and updates CurTok with its results.
1094 static int CurTok;
1095 static int getNextToken() {
1096 return CurTok = gettok();
1097 }
1099 /// BinopPrecedence - This holds the precedence for each binary operator that is
1100 /// defined.
1103 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
1104 static int GetTokPrecedence() {
1105 if (!isascii(CurTok))
1106 return -1;
1108 // Make sure it's a declared binop.
1109 int TokPrec = BinopPrecedence[CurTok];
1111 return TokPrec;
1112 }
1114 /// Error* - These are little helper functions for error handling.
1116 PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
1117 FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
1119 static ExprAST *ParseExpression();
1121 /// identifierexpr
1122 /// ::= identifier
1123 /// ::= identifier '(' expression* ')'
1124 static ExprAST *ParseIdentifierExpr() {
1125 std::string IdName = IdentifierStr;
1127 getNextToken(); // eat identifier.
1129 if (CurTok != '(') // Simple variable ref.
1130 return new VariableExprAST(IdName);
1132 // Call.
1133 getNextToken(); // eat (
1135 if (CurTok != ')') {
1136 while (1) {
1137 ExprAST *Arg = ParseExpression();
1138 if (!Arg) return 0;
1139 Args.push_back(Arg);
1141 if (CurTok == ')') break;
1143 if (CurTok != ',')
1144 return Error("Expected ')' or ',' in argument list");
1145 getNextToken();
1146 }
1147 }
1149 // Eat the ')'.
1150 getNextToken();
1152 return new CallExprAST(IdName, Args);
1153 }
1155 /// numberexpr ::= number
1156 static ExprAST *ParseNumberExpr() {
1157 ExprAST *Result = new NumberExprAST(NumVal);
1158 getNextToken(); // consume the number
1159 return Result;
1160 }
1162 /// parenexpr ::= '(' expression ')'
1163 static ExprAST *ParseParenExpr() {
1164 getNextToken(); // eat (.
1165 ExprAST *V = ParseExpression();
1166 if (!V) return 0;
1168 if (CurTok != ')')
1169 return Error("expected ')'");
1170 getNextToken(); // eat ).
1171 return V;
1172 }
1174 /// ifexpr ::= 'if' expression 'then' expression 'else' expression
1175 static ExprAST *ParseIfExpr() {
1176 getNextToken(); // eat the if.
1178 // condition.
1179 ExprAST *Cond = ParseExpression();
1180 if (!Cond) return 0;
1182 if (CurTok != tok_then)
1183 return Error("expected then");
1184 getNextToken(); // eat the then
1186 ExprAST *Then = ParseExpression();
1189 if (CurTok != tok_else)
1190 return Error("expected else");
1192 getNextToken();
1194 ExprAST *Else = ParseExpression();
1195 if (!Else) return 0;
1197 return new IfExprAST(Cond, Then, Else);
1198 }
1200 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
1201 static ExprAST *ParseForExpr() {
1202 getNextToken(); // eat the for.
1204 if (CurTok != tok_identifier)
1205 return Error("expected identifier after for");
1207 std::string IdName = IdentifierStr;
1208 getNextToken(); // eat identifier.
1210 if (CurTok != '=')
1211 return Error("expected '=' after for");
1212 getNextToken(); // eat '='.
1215 ExprAST *Start = ParseExpression();
1217 if (CurTok != ',')
1218 return Error("expected ',' after for start value");
1219 getNextToken();
1221 ExprAST *End = ParseExpression();
1224 // The step value is optional.
1225 ExprAST *Step = 0;
1226 if (CurTok == ',') {
1227 getNextToken();
1228 Step = ParseExpression();
1230 }
1232 if (CurTok != tok_in)
1233 return Error("expected 'in' after for");
1234 getNextToken(); // eat 'in'.
1236 ExprAST *Body = ParseExpression();
1239 return new ForExprAST(IdName, Start, End, Step, Body);
1240 }
1242 /// primary
1243 /// ::= identifierexpr
1244 /// ::= numberexpr
1245 /// ::= parenexpr
1246 /// ::= ifexpr
1247 /// ::= forexpr
1248 static ExprAST *ParsePrimary() {
1249 switch (CurTok) {
1250 default: return Error("unknown token when expecting an expression");
1251 case tok_identifier: return ParseIdentifierExpr();
1252 case tok_number: return ParseNumberExpr();
1253 case '(': return ParseParenExpr();
1254 case tok_if: return ParseIfExpr();
1255 case tok_for: return ParseForExpr();
1256 }
1257 }
1259 /// binoprhs
1260 /// ::= ('+' primary)*
1261 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
1262 // If this is a binop, find its precedence.
1263 while (1) {
1264 int TokPrec = GetTokPrecedence();
1266 // If this is a binop that binds at least as tightly as the current binop,
1267 // consume it, otherwise we are done.
1268 if (TokPrec < ExprPrec)
1269 return LHS;
1271 // Okay, we know this is a binop.
1272 int BinOp = CurTok;
1273 getNextToken(); // eat binop
1275 // Parse the primary expression after the binary operator.
1276 ExprAST *RHS = ParsePrimary();
1277 if (!RHS) return 0;
1279 // If BinOp binds less tightly with RHS than the operator after RHS, let
1280 // the pending operator take RHS as its LHS.
1281 int NextPrec = GetTokPrecedence();
1282 if (TokPrec < NextPrec) {
1283 RHS = ParseBinOpRHS(TokPrec+1, RHS);
1285 }
1287 // Merge LHS/RHS.
1288 LHS = new BinaryExprAST(BinOp, LHS, RHS);
1289 }
1290 }
1292 /// expression
1293 /// ::= primary binoprhs
1294 ///
1295 static ExprAST *ParseExpression() {
1296 ExprAST *LHS = ParsePrimary();
1297 if (!LHS) return 0;
1299 return ParseBinOpRHS(0, LHS);
1300 }
1302 /// prototype
1303 /// ::= id '(' id* ')'
1304 static PrototypeAST *ParsePrototype() {
1305 if (CurTok != tok_identifier)
1306 return ErrorP("Expected function name in prototype");
1308 std::string FnName = IdentifierStr;
1309 getNextToken();
1311 if (CurTok != '(')
1312 return ErrorP("Expected '(' in prototype");
1315 while (getNextToken() == tok_identifier)
1316 ArgNames.push_back(IdentifierStr);
1317 if (CurTok != ')')
1318 return ErrorP("Expected ')' in prototype");
1320 // success.
1321 getNextToken(); // eat ')'.
1323 return new PrototypeAST(FnName, ArgNames);
1324 }
1326 /// definition ::= 'def' prototype expression
1327 static FunctionAST *ParseDefinition() {
1328 getNextToken(); // eat def.
1329 PrototypeAST *Proto = ParsePrototype();
1332 if (ExprAST *E = ParseExpression())
1333 return new FunctionAST(Proto, E);
1334 return 0;
1335 }
1337 /// toplevelexpr ::= expression
1338 static FunctionAST *ParseTopLevelExpr() {
1339 if (ExprAST *E = ParseExpression()) {
1340 // Make an anonymous proto.
1342 return new FunctionAST(Proto, E);
1343 }
1344 return 0;
1345 }
1347 /// external ::= 'extern' prototype
1348 static PrototypeAST *ParseExtern() {
1349 getNextToken(); // eat extern.
1350 return ParsePrototype();
1351 }
1353 //===----------------------------------------------------------------------===//
1354 // Code Generation
1355 //===----------------------------------------------------------------------===//
1357 static Module *TheModule;
1358 static IRBuilder<> Builder(getGlobalContext());
1360 static FunctionPassManager *TheFPM;
1362 Value *ErrorV(const char *Str) { Error(Str); return 0; }
1364 Value *NumberExprAST::Codegen() {
1365 return ConstantFP::get(getGlobalContext(), APFloat(Val));
1366 }
1368 Value *VariableExprAST::Codegen() {
1369 // Look this variable up in the function.
1370 Value *V = NamedValues[Name];
1371 return V ? V : ErrorV("Unknown variable name");
1372 }
1374 Value *BinaryExprAST::Codegen() {
1375 Value *L = LHS->Codegen();
1376 Value *R = RHS->Codegen();
1379 switch (Op) {
1380 case '+': return Builder.CreateFAdd(L, R, "addtmp");
1381 case '-': return Builder.CreateFSub(L, R, "subtmp");
1382 case '*': return Builder.CreateFMul(L, R, "multmp");
1383 case '<':
1384 L = Builder.CreateFCmpULT(L, R, "cmptmp");
1386 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
1387 "booltmp");
1388 default: return ErrorV("invalid binary operator");
1389 }
1390 }
1392 Value *CallExprAST::Codegen() {
1393 // Look up the name in the global module table.
1394 Function *CalleeF = TheModule->getFunction(Callee);
1395 if (CalleeF == 0)
1396 return ErrorV("Unknown function referenced");
1398 // If argument mismatch error.
1399 if (CalleeF->arg_size() != Args.size())
1400 return ErrorV("Incorrect # arguments passed");
1403 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
1404 ArgsV.push_back(Args[i]->Codegen());
1406 }
1408 return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
1409 }
1411 Value *IfExprAST::Codegen() {
1412 Value *CondV = Cond->Codegen();
1415 // Convert condition to a bool by comparing equal to 0.0.
1416 CondV = Builder.CreateFCmpONE(CondV,
1417 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
1418 "ifcond");
1420 Function *TheFunction = Builder.GetInsertBlock()->getParent();
1422 // Create blocks for the then and else cases. Insert the 'then' block at the
1423 // end of the function.
1424 BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunction);
1425 BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else");
1426 BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont");
1428 Builder.CreateCondBr(CondV, ThenBB, ElseBB);
1430 // Emit then value.
1431 Builder.SetInsertPoint(ThenBB);
1433 Value *ThenV = Then->Codegen();
1436 Builder.CreateBr(MergeBB);
1437 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
1438 ThenBB = Builder.GetInsertBlock();
1440 // Emit else block.
1441 TheFunction->getBasicBlockList().push_back(ElseBB);
1442 Builder.SetInsertPoint(ElseBB);
1444 Value *ElseV = Else->Codegen();
1447 Builder.CreateBr(MergeBB);
1448 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
1449 ElseBB = Builder.GetInsertBlock();
1451 // Emit merge block.
1452 TheFunction->getBasicBlockList().push_back(MergeBB);
1453 Builder.SetInsertPoint(MergeBB);
1454 PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()),
1455 "iftmp");
1457 PN->addIncoming(ThenV, ThenBB);
1458 PN->addIncoming(ElseV, ElseBB);
1459 return PN;
1460 }
1462 Value *ForExprAST::Codegen() {
1463 // Output this as:
1464 // ...
1465 // start = startexpr
1466 // goto loop
1467 // loop:
1468 // variable = phi [start, loopheader], [nextvariable, loopend]
1469 // ...
1470 // bodyexpr
1471 // ...
1472 // loopend:
1473 // step = stepexpr
1474 // nextvariable = variable + step
1475 // endcond = endexpr
1476 // br endcond, loop, endloop
1477 // outloop:
1479 // Emit the start code first, without 'variable' in scope.
1480 Value *StartVal = Start->Codegen();
1483 // Make the new basic block for the loop header, inserting after current
1484 // block.
1485 Function *TheFunction = Builder.GetInsertBlock()->getParent();
1486 BasicBlock *PreheaderBB = Builder.GetInsertBlock();
1487 BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
1489 // Insert an explicit fall through from the current block to the LoopBB.
1490 Builder.CreateBr(LoopBB);
1492 // Start insertion in LoopBB.
1493 Builder.SetInsertPoint(LoopBB);
1495 // Start the PHI node with an entry for Start.
1496 PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), VarName.c_str());
1497 Variable->addIncoming(StartVal, PreheaderBB);
1499 // Within the loop, the variable is defined equal to the PHI node. If it
1500 // shadows an existing variable, we have to restore it, so save it now.
1501 Value *OldVal = NamedValues[VarName];
1502 NamedValues[VarName] = Variable;
1504 // Emit the body of the loop. This, like any other expr, can change the
1505 // current BB. Note that we ignore the value computed by the body, but don't
1506 // allow an error.
1508 return 0;
1510 // Emit the step value.
1511 Value *StepVal;
1512 if (Step) {
1513 StepVal = Step->Codegen();
1515 } else {
1516 // If not specified, use 1.0.
1517 StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
1518 }
1520 Value *NextVar = Builder.CreateFAdd(Variable, StepVal, "nextvar");
1522 // Compute the end condition.
1523 Value *EndCond = End->Codegen();
1524 if (EndCond == 0) return EndCond;
1526 // Convert condition to a bool by comparing equal to 0.0.
1527 EndCond = Builder.CreateFCmpONE(EndCond,
1528 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
1529 "loopcond");
1531 // Create the "after loop" block and insert it.
1532 BasicBlock *LoopEndBB = Builder.GetInsertBlock();
1533 BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
1535 // Insert the conditional branch into the end of LoopEndBB.
1536 Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
1538 // Any new code will be inserted in AfterBB.
1539 Builder.SetInsertPoint(AfterBB);
1541 // Add a new entry to the PHI node for the backedge.
1542 Variable->addIncoming(NextVar, LoopEndBB);
1544 // Restore the unshadowed variable.
1545 if (OldVal)
1546 NamedValues[VarName] = OldVal;
1547 else
1548 NamedValues.erase(VarName);
1551 // for expr always returns 0.0.
1552 return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
1553 }
1555 Function *PrototypeAST::Codegen() {
1556 // Make the function type: double(double,double) etc.
1558 Type::getDoubleTy(getGlobalContext()));
1559 FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()),
1560 Doubles, false);
1562 Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
1564 // If F conflicted, there was already something named 'Name'. If it has a
1565 // body, don't allow redefinition or reextern.
1566 if (F->getName() != Name) {
1567 // Delete the one we just made and get the existing one.
1568 F->eraseFromParent();
1569 F = TheModule->getFunction(Name);
1571 // If F already has a body, reject this.
1572 if (!F->empty()) {
1573 ErrorF("redefinition of function");
1574 return 0;
1575 }
1577 // If F took a different number of args, reject.
1578 if (F->arg_size() != Args.size()) {
1579 ErrorF("redefinition of function with different # args");
1580 return 0;
1581 }
1582 }
1584 // Set names for all arguments.
1585 unsigned Idx = 0;
1586 for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
1587 ++AI, ++Idx) {
1588 AI->setName(Args[Idx]);
1590 // Add arguments to variable symbol table.
1591 NamedValues[Args[Idx]] = AI;
1592 }
1594 return F;
1595 }
1597 Function *FunctionAST::Codegen() {
1598 NamedValues.clear();
1600 Function *TheFunction = Proto->Codegen();
1601 if (TheFunction == 0)
1602 return 0;
1604 // Create a new basic block to start insertion into.
1605 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
1606 Builder.SetInsertPoint(BB);
1608 if (Value *RetVal = Body->Codegen()) {
1609 // Finish off the function.
1610 Builder.CreateRet(RetVal);
1612 // Validate the generated code, checking for consistency.
1613 verifyFunction(*TheFunction);
1615 // Optimize the function.
1616 TheFPM->run(*TheFunction);
1618 return TheFunction;
1619 }
1621 // Error reading body, remove function.
1622 TheFunction->eraseFromParent();
1623 return 0;
1624 }
1626 //===----------------------------------------------------------------------===//
1627 // Top-Level parsing and JIT Driver
1628 //===----------------------------------------------------------------------===//
1630 static ExecutionEngine *TheExecutionEngine;
1632 static void HandleDefinition() {
1633 if (FunctionAST *F = ParseDefinition()) {
1634 if (Function *LF = F->Codegen()) {
1635 fprintf(stderr, "Read function definition:");
1636 LF->dump();
1637 }
1638 } else {
1639 // Skip token for error recovery.
1640 getNextToken();
1641 }
1642 }
1644 static void HandleExtern() {
1645 if (PrototypeAST *P = ParseExtern()) {
1646 if (Function *F = P->Codegen()) {
1647 fprintf(stderr, "Read extern: ");
1648 F->dump();
1649 }
1650 } else {
1651 // Skip token for error recovery.
1652 getNextToken();
1653 }
1654 }
1656 static void HandleTopLevelExpression() {
1657 // Evaluate a top-level expression into an anonymous function.
1658 if (FunctionAST *F = ParseTopLevelExpr()) {
1659 if (Function *LF = F->Codegen()) {
1660 // JIT the function, returning a function pointer.
1661 void *FPtr = TheExecutionEngine->getPointerToFunction(LF);
1663 // Cast it to the right type (takes no arguments, returns a double) so we
1664 // can call it as a native function.
1665 double (*FP)() = (double (*)())(intptr_t)FPtr;
1666 fprintf(stderr, "Evaluated to %f\n", FP());
1667 }
1668 } else {
1669 // Skip token for error recovery.
1670 getNextToken();
1671 }
1672 }
1674 /// top ::= definition | external | expression | ';'
1675 static void MainLoop() {
1676 while (1) {
1677 fprintf(stderr, "ready> ");
1678 switch (CurTok) {
1679 case tok_eof: return;
1680 case ';': getNextToken(); break; // ignore top-level semicolons.
1681 case tok_def: HandleDefinition(); break;
1682 case tok_extern: HandleExtern(); break;
1683 default: HandleTopLevelExpression(); break;
1684 }
1685 }
1686 }
1688 //===----------------------------------------------------------------------===//
1690 //===----------------------------------------------------------------------===//
1692 /// putchard - putchar that takes a double and returns 0.
1693 extern "C"
1694 double putchard(double X) {
1695 putchar((char)X);
1696 return 0;
1697 }
1699 //===----------------------------------------------------------------------===//
1700 // Main driver code.
1701 //===----------------------------------------------------------------------===//
1703 int main() {
1704 InitializeNativeTarget();
1705 LLVMContext &Context = getGlobalContext();
1707 // Install standard binary operators.
1708 // 1 is lowest precedence.
1710 BinopPrecedence['+'] = 20;
1711 BinopPrecedence['-'] = 20;
1712 BinopPrecedence['*'] = 40; // highest.
1714 // Prime the first token.
1715 fprintf(stderr, "ready> ");
1716 getNextToken();
1718 // Make the module, which holds all the code.
1719 TheModule = new Module("my cool jit", Context);
1721 // Create the JIT. This takes ownership of the module.
1722 std::string ErrStr;
1723 TheExecutionEngine = EngineBuilder(TheModule).setErrorStr(&ErrStr).create();
1724 if (!TheExecutionEngine) {
1725 fprintf(stderr, "Could not create ExecutionEngine: %s\n", ErrStr.c_str());
1726 exit(1);
1727 }
1729 FunctionPassManager OurFPM(TheModule);
1731 // Set up the optimizer pipeline. Start with registering info about how the
1732 // target lays out data structures.
1733 OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData()));
1734 // Do simple "peephole" optimizations and bit-twiddling optzns.
1735 OurFPM.add(createInstructionCombiningPass());
1736 // Reassociate expressions.
1737 OurFPM.add(createReassociatePass());
1738 // Eliminate Common SubExpressions.
1739 OurFPM.add(createGVNPass());
1740 // Simplify the control flow graph (deleting unreachable blocks, etc).
1741 OurFPM.add(createCFGSimplificationPass());
1743 OurFPM.doInitialization();
1745 // Set the global so the code gen can use this.
1746 TheFPM = &OurFPM;
1748 // Run the main "interpreter loop" now.
1749 MainLoop();
1751 TheFPM = 0;
1753 // Print out all of the generated code.
1754 TheModule->dump();
1756 return 0;
1757 }
1758 </pre>
1759 </div>
1762 </div>
1764 <!-- *********************************************************************** -->
1765 <hr>
1766 <address>
1774 Last modified: $Date$
1775 </address>
1776 </body>
1777 </html>