Gitiles
Code Review Sign In
gerrit-public.fairphone.software / fp2-dev / platform / external / llvm / 1d0be15f89cb5056e20e2d24faa8d6afb1573bca / . / docs / tutorial / LangImpl6.html
blob: 33df2452b67d8aea875d7477ebbe15a9b80dbd51 [file] [log] [blame]
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
2 "http://www.w3.org/TR/html4/strict.dtd">
3
4<html>
5<head>
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]6 <title>Kaleidoscope: Extending the Language: User-defined Operators</title>
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]7 <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
8 <meta name="author" content="Chris Lattner">
9 <link rel="stylesheet" href="../llvm.css" type="text/css">
10</head>
11
12<body>
13
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]14<div class="doc_title">Kaleidoscope: Extending the Language: User-defined Operators</div>
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]15
Chris Lattner128eb862007-11-05 19:06:59 +0000[diff] [blame]16<ul>
Chris Lattner0e555b12007-11-05 20:04:56 +0000[diff] [blame]17<li><a href="index.html">Up to Tutorial Index</a></li>
Chris Lattner128eb862007-11-05 19:06:59 +0000[diff] [blame]18<li>Chapter 6
19 <ol>
20 <li><a href="#intro">Chapter 6 Introduction</a></li>
21 <li><a href="#idea">User-defined Operators: the Idea</a></li>
22 <li><a href="#binary">User-defined Binary Operators</a></li>
23 <li><a href="#unary">User-defined Unary Operators</a></li>
24 <li><a href="#example">Kicking the Tires</a></li>
25 <li><a href="#code">Full Code Listing</a></li>
26 </ol>
27</li>
Chris Lattner0e555b12007-11-05 20:04:56 +0000[diff] [blame]28<li><a href="LangImpl7.html">Chapter 7</a>: Extending the Language: Mutable
29Variables / SSA Construction</li>
Chris Lattner128eb862007-11-05 19:06:59 +0000[diff] [blame]30</ul>
31
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]32<div class="doc_author">
33 <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p>
34</div>
35
36<!-- *********************************************************************** -->
Chris Lattner128eb862007-11-05 19:06:59 +0000[diff] [blame]37<div class="doc_section"><a name="intro">Chapter 6 Introduction</a></div>
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]38<!-- *********************************************************************** -->
39
40<div class="doc_text">
41
Chris Lattner128eb862007-11-05 19:06:59 +0000[diff] [blame]42<p>Welcome to Chapter 6 of the "<a href="index.html">Implementing a language
43with LLVM</a>" tutorial. At this point in our tutorial, we now have a fully
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]44functional language that is fairly minimal, but also useful. There
45is still one big problem with it, however. Our language doesn't have many
46useful operators (like division, logical negation, or even any comparisons
47besides less-than).</p>
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]48
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]49<p>This chapter of the tutorial takes a wild digression into adding user-defined
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]50operators to the simple and beautiful Kaleidoscope language. This digression now gives
51us a simple and ugly language in some ways, but also a powerful one at the same time.
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]52One of the great things about creating your own language is that you get to
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]53decide what is good or bad. In this tutorial we'll assume that it is okay to
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]54use this as a way to show some interesting parsing techniques.</p>
55
Chris Lattner3616a8a2007-11-07 06:06:38 +0000[diff] [blame]56<p>At the end of this tutorial, we'll run through an example Kaleidoscope
57application that <a href="#example">renders the Mandelbrot set</a>. This gives
58an example of what you can build with Kaleidoscope and its feature set.</p>
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]59
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]60</div>
61
62<!-- *********************************************************************** -->
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]63<div class="doc_section"><a name="idea">User-defined Operators: the Idea</a></div>
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]64<!-- *********************************************************************** -->
65
66<div class="doc_text">
67
68<p>
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]69The "operator overloading" that we will add to Kaleidoscope is more general than
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]70languages like C++. In C++, you are only allowed to redefine existing
71operators: you can't programatically change the grammar, introduce new
72operators, change precedence levels, etc. In this chapter, we will add this
Chris Lattner3616a8a2007-11-07 06:06:38 +0000[diff] [blame]73capability to Kaleidoscope, which will let the user round out the set of
74operators that are supported.</p>
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]75
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]76<p>The point of going into user-defined operators in a tutorial like this is to
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]77show the power and flexibility of using a hand-written parser. Thus far, the parser
78we have been implementing uses recursive descent for most parts of the grammar and
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]79operator precedence parsing for the expressions. See <a
80href="LangImpl2.html">Chapter 2</a> for details. Without using operator
81precedence parsing, it would be very difficult to allow the programmer to
82introduce new operators into the grammar: the grammar is dynamically extensible
83as the JIT runs.</p>
84
85<p>The two specific features we'll add are programmable unary operators (right
86now, Kaleidoscope has no unary operators at all) as well as binary operators.
87An example of this is:</p>
88
89<div class="doc_code">
90<pre>
91# Logical unary not.
92def unary!(v)
93 if v then
94 0
95 else
96 1;
97
98# Define &gt; with the same precedence as &lt;.
99def binary&gt; 10 (LHS RHS)
Chris Lattner61ad4492007-11-23 22:19:33 +0000[diff] [blame]100 RHS &lt; LHS;
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]101
102# Binary "logical or", (note that it does not "short circuit")
103def binary| 5 (LHS RHS)
104 if LHS then
105 1
106 else if RHS then
107 1
108 else
109 0;
110
111# Define = with slightly lower precedence than relationals.
112def binary= 9 (LHS RHS)
113 !(LHS &lt; RHS | LHS &gt; RHS);
114</pre>
115</div>
116
117<p>Many languages aspire to being able to implement their standard runtime
118library in the language itself. In Kaleidoscope, we can implement significant
119parts of the language in the library!</p>
120
121<p>We will break down implementation of these features into two parts:
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]122implementing support for user-defined binary operators and adding unary
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]123operators.</p>
124
125</div>
126
127<!-- *********************************************************************** -->
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]128<div class="doc_section"><a name="binary">User-defined Binary Operators</a></div>
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]129<!-- *********************************************************************** -->
130
131<div class="doc_text">
132
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]133<p>Adding support for user-defined binary operators is pretty simple with our
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]134current framework. We'll first add support for the unary/binary keywords:</p>
135
136<div class="doc_code">
137<pre>
138enum Token {
139 ...
140 <b>// operators
141 tok_binary = -11, tok_unary = -12</b>
142};
143...
144static int gettok() {
145...
146 if (IdentifierStr == "for") return tok_for;
147 if (IdentifierStr == "in") return tok_in;
148 <b>if (IdentifierStr == "binary") return tok_binary;
149 if (IdentifierStr == "unary") return tok_unary;</b>
150 return tok_identifier;
151</pre>
152</div>
153
154<p>This just adds lexer support for the unary and binary keywords, like we
155did in <a href="LangImpl5.html#iflexer">previous chapters</a>. One nice thing
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]156about our current AST, is that we represent binary operators with full generalisation
157by using their ASCII code as the opcode. For our extended operators, we'll use this
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]158same representation, so we don't need any new AST or parser support.</p>
159
160<p>On the other hand, we have to be able to represent the definitions of these
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]161new operators, in the "def binary| 5" part of the function definition. In our
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]162grammar so far, the "name" for the function definition is parsed as the
163"prototype" production and into the <tt>PrototypeAST</tt> AST node. To
164represent our new user-defined operators as prototypes, we have to extend
165the <tt>PrototypeAST</tt> AST node like this:</p>
166
167<div class="doc_code">
168<pre>
169/// PrototypeAST - This class represents the "prototype" for a function,
170/// which captures its argument names as well as if it is an operator.
171class PrototypeAST {
172 std::string Name;
173 std::vector&lt;std::string&gt; Args;
174 <b>bool isOperator;
175 unsigned Precedence; // Precedence if a binary op.</b>
176public:
177 PrototypeAST(const std::string &amp;name, const std::vector&lt;std::string&gt; &amp;args,
178 <b>bool isoperator = false, unsigned prec = 0</b>)
179 : Name(name), Args(args), <b>isOperator(isoperator), Precedence(prec)</b> {}
180
181 <b>bool isUnaryOp() const { return isOperator &amp;&amp; Args.size() == 1; }
182 bool isBinaryOp() const { return isOperator &amp;&amp; Args.size() == 2; }
183
184 char getOperatorName() const {
185 assert(isUnaryOp() || isBinaryOp());
186 return Name[Name.size()-1];
187 }
188
189 unsigned getBinaryPrecedence() const { return Precedence; }</b>
190
191 Function *Codegen();
192};
193</pre>
194</div>
195
196<p>Basically, in addition to knowing a name for the prototype, we now keep track
197of whether it was an operator, and if it was, what precedence level the operator
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]198is at. The precedence is only used for binary operators (as you'll see below,
199it just doesn't apply for unary operators). Now that we have a way to represent
200the prototype for a user-defined operator, we need to parse it:</p>
201
202<div class="doc_code">
203<pre>
204/// prototype
205/// ::= id '(' id* ')'
206<b>/// ::= binary LETTER number? (id, id)</b>
207static PrototypeAST *ParsePrototype() {
208 std::string FnName;
209
210 <b>int Kind = 0; // 0 = identifier, 1 = unary, 2 = binary.
211 unsigned BinaryPrecedence = 30;</b>
212
213 switch (CurTok) {
214 default:
215 return ErrorP("Expected function name in prototype");
216 case tok_identifier:
217 FnName = IdentifierStr;
218 Kind = 0;
219 getNextToken();
220 break;
221 <b>case tok_binary:
222 getNextToken();
223 if (!isascii(CurTok))
224 return ErrorP("Expected binary operator");
225 FnName = "binary";
226 FnName += (char)CurTok;
227 Kind = 2;
228 getNextToken();
229
230 // Read the precedence if present.
231 if (CurTok == tok_number) {
232 if (NumVal &lt; 1 || NumVal &gt; 100)
233 return ErrorP("Invalid precedecnce: must be 1..100");
234 BinaryPrecedence = (unsigned)NumVal;
235 getNextToken();
236 }
237 break;</b>
238 }
239
240 if (CurTok != '(')
241 return ErrorP("Expected '(' in prototype");
242
243 std::vector&lt;std::string&gt; ArgNames;
244 while (getNextToken() == tok_identifier)
245 ArgNames.push_back(IdentifierStr);
246 if (CurTok != ')')
247 return ErrorP("Expected ')' in prototype");
248
249 // success.
250 getNextToken(); // eat ')'.
251
252 <b>// Verify right number of names for operator.
253 if (Kind &amp;&amp; ArgNames.size() != Kind)
254 return ErrorP("Invalid number of operands for operator");
255
256 return new PrototypeAST(FnName, ArgNames, Kind != 0, BinaryPrecedence);</b>
257}
258</pre>
259</div>
260
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]261<p>This is all fairly straightforward parsing code, and we have already seen
262a lot of similar code in the past. One interesting part about the code above is
263the couple lines that set up <tt>FnName</tt> for binary operators. This builds names
264like "binary@" for a newly defined "@" operator. This then takes advantage of the
265fact that symbol names in the LLVM symbol table are allowed to have any character in
266them, including embedded nul characters.</p>
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]267
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]268<p>The next interesting thing to add, is codegen support for these binary operators.
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]269Given our current structure, this is a simple addition of a default case for our
270existing binary operator node:</p>
271
272<div class="doc_code">
273<pre>
274Value *BinaryExprAST::Codegen() {
275 Value *L = LHS-&gt;Codegen();
276 Value *R = RHS-&gt;Codegen();
277 if (L == 0 || R == 0) return 0;
278
279 switch (Op) {
280 case '+': return Builder.CreateAdd(L, R, "addtmp");
281 case '-': return Builder.CreateSub(L, R, "subtmp");
282 case '*': return Builder.CreateMul(L, R, "multmp");
283 case '&lt;':
Chris Lattner71155212007-11-06 01:39:12 +0000[diff] [blame]284 L = Builder.CreateFCmpULT(L, R, "cmptmp");
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]285 // Convert bool 0/1 to double 0.0 or 1.0
Owen Anderson1d0be152009-08-13 21:58:54 +0000[diff] [blame^]286 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()), "booltmp");
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]287 <b>default: break;</b>
288 }
289
290 <b>// If it wasn't a builtin binary operator, it must be a user defined one. Emit
291 // a call to it.
292 Function *F = TheModule-&gt;getFunction(std::string("binary")+Op);
293 assert(F &amp;&amp; "binary operator not found!");
294
295 Value *Ops[] = { L, R };
296 return Builder.CreateCall(F, Ops, Ops+2, "binop");</b>
297}
298
299</pre>
300</div>
301
302<p>As you can see above, the new code is actually really simple. It just does
303a lookup for the appropriate operator in the symbol table and generates a
304function call to it. Since user-defined operators are just built as normal
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]305functions (because the "prototype" boils down to a function with the right
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]306name) everything falls into place.</p>
307
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]308<p>The final piece of code we are missing, is a bit of top level magic:</p>
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]309
310<div class="doc_code">
311<pre>
312Function *FunctionAST::Codegen() {
313 NamedValues.clear();
314
315 Function *TheFunction = Proto->Codegen();
316 if (TheFunction == 0)
317 return 0;
318
319 <b>// If this is an operator, install it.
320 if (Proto-&gt;isBinaryOp())
321 BinopPrecedence[Proto->getOperatorName()] = Proto->getBinaryPrecedence();</b>
322
323 // Create a new basic block to start insertion into.
Owen Anderson1d0be152009-08-13 21:58:54 +0000[diff] [blame^]324 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]325 Builder.SetInsertPoint(BB);
326
327 if (Value *RetVal = Body-&gt;Codegen()) {
328 ...
329</pre>
330</div>
331
332<p>Basically, before codegening a function, if it is a user-defined operator, we
333register it in the precedence table. This allows the binary operator parsing
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]334logic we already have in place to handle it. Since we are working on a fully-general operator precedence parser, this is all we need to do to "extend the grammar".</p>
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]335
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]336<p>Now we have useful user-defined binary operators. This builds a lot
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]337on the previous framework we built for other operators. Adding unary operators
Chris Lattner3616a8a2007-11-07 06:06:38 +0000[diff] [blame]338is a bit more challenging, because we don't have any framework for it yet - lets
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]339see what it takes.</p>
340
341</div>
342
343<!-- *********************************************************************** -->
344<div class="doc_section"><a name="unary">User-defined Unary Operators</a></div>
345<!-- *********************************************************************** -->
346
347<div class="doc_text">
348
349<p>Since we don't currently support unary operators in the Kaleidoscope
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]350language, we'll need to add everything to support them. Above, we added simple
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]351support for the 'unary' keyword to the lexer. In addition to that, we need an
352AST node:</p>
353
354<div class="doc_code">
355<pre>
356/// UnaryExprAST - Expression class for a unary operator.
357class UnaryExprAST : public ExprAST {
358 char Opcode;
359 ExprAST *Operand;
360public:
361 UnaryExprAST(char opcode, ExprAST *operand)
362 : Opcode(opcode), Operand(operand) {}
363 virtual Value *Codegen();
364};
365</pre>
366</div>
367
368<p>This AST node is very simple and obvious by now. It directly mirrors the
369binary operator AST node, except that it only has one child. With this, we
370need to add the parsing logic. Parsing a unary operator is pretty simple: we'll
371add a new function to do it:</p>
372
373<div class="doc_code">
374<pre>
375/// unary
376/// ::= primary
377/// ::= '!' unary
378static ExprAST *ParseUnary() {
379 // If the current token is not an operator, it must be a primary expr.
380 if (!isascii(CurTok) || CurTok == '(' || CurTok == ',')
381 return ParsePrimary();
382
383 // If this is a unary operator, read it.
384 int Opc = CurTok;
385 getNextToken();
386 if (ExprAST *Operand = ParseUnary())
387 return new UnaryExprAST(Opc, Operand);
388 return 0;
389}
390</pre>
391</div>
392
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]393<p>The grammar we add is pretty straightforward here. If we see a unary
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]394operator when parsing a primary operator, we eat the operator as a prefix and
395parse the remaining piece as another unary operator. This allows us to handle
396multiple unary operators (e.g. "!!x"). Note that unary operators can't have
397ambiguous parses like binary operators can, so there is no need for precedence
398information.</p>
399
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]400<p>The problem with this function, is that we need to call ParseUnary from somewhere.
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]401To do this, we change previous callers of ParsePrimary to call ParseUnary
402instead:</p>
403
404<div class="doc_code">
405<pre>
406/// binoprhs
407/// ::= ('+' unary)*
408static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
409 ...
410 <b>// Parse the unary expression after the binary operator.
411 ExprAST *RHS = ParseUnary();
412 if (!RHS) return 0;</b>
413 ...
414}
415/// expression
416/// ::= unary binoprhs
417///
418static ExprAST *ParseExpression() {
419 <b>ExprAST *LHS = ParseUnary();</b>
420 if (!LHS) return 0;
421
422 return ParseBinOpRHS(0, LHS);
423}
424</pre>
425</div>
426
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]427<p>With these two simple changes, we are now able to parse unary operators and build the
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]428AST for them. Next up, we need to add parser support for prototypes, to parse
429the unary operator prototype. We extend the binary operator code above
430with:</p>
431
432<div class="doc_code">
433<pre>
434/// prototype
435/// ::= id '(' id* ')'
436/// ::= binary LETTER number? (id, id)
437<b>/// ::= unary LETTER (id)</b>
438static PrototypeAST *ParsePrototype() {
439 std::string FnName;
440
441 int Kind = 0; // 0 = identifier, 1 = unary, 2 = binary.
442 unsigned BinaryPrecedence = 30;
443
444 switch (CurTok) {
445 default:
446 return ErrorP("Expected function name in prototype");
447 case tok_identifier:
448 FnName = IdentifierStr;
449 Kind = 0;
450 getNextToken();
451 break;
452 <b>case tok_unary:
453 getNextToken();
454 if (!isascii(CurTok))
455 return ErrorP("Expected unary operator");
456 FnName = "unary";
457 FnName += (char)CurTok;
458 Kind = 1;
459 getNextToken();
460 break;</b>
461 case tok_binary:
462 ...
463</pre>
464</div>
465
466<p>As with binary operators, we name unary operators with a name that includes
467the operator character. This assists us at code generation time. Speaking of,
468the final piece we need to add is codegen support for unary operators. It looks
469like this:</p>
470
471<div class="doc_code">
472<pre>
473Value *UnaryExprAST::Codegen() {
474 Value *OperandV = Operand->Codegen();
475 if (OperandV == 0) return 0;
476
477 Function *F = TheModule->getFunction(std::string("unary")+Opcode);
478 if (F == 0)
479 return ErrorV("Unknown unary operator");
480
481 return Builder.CreateCall(F, OperandV, "unop");
482}
483</pre>
484</div>
485
486<p>This code is similar to, but simpler than, the code for binary operators. It
487is simpler primarily because it doesn't need to handle any predefined operators.
488</p>
489
490</div>
491
492<!-- *********************************************************************** -->
493<div class="doc_section"><a name="example">Kicking the Tires</a></div>
494<!-- *********************************************************************** -->
495
496<div class="doc_text">
497
498<p>It is somewhat hard to believe, but with a few simple extensions we've
Chris Lattnerb5d81b32007-11-02 05:54:25 +0000[diff] [blame]499covered in the last chapters, we have grown a real-ish language. With this, we
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]500can do a lot of interesting things, including I/O, math, and a bunch of other
501things. For example, we can now add a nice sequencing operator (printd is
502defined to print out the specified value and a newline):</p>
503
504<div class="doc_code">
505<pre>
506ready&gt; <b>extern printd(x);</b>
507Read extern: declare double @printd(double)
508ready&gt; <b>def binary : 1 (x y) 0; # Low-precedence operator that ignores operands.</b>
509..
510ready&gt; <b>printd(123) : printd(456) : printd(789);</b>
511123.000000
512456.000000
513789.000000
514Evaluated to 0.000000
515</pre>
516</div>
517
Chris Lattnerb5d81b32007-11-02 05:54:25 +0000[diff] [blame]518<p>We can also define a bunch of other "primitive" operations, such as:</p>
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]519
520<div class="doc_code">
521<pre>
522# Logical unary not.
523def unary!(v)
524 if v then
525 0
526 else
527 1;
528
529# Unary negate.
530def unary-(v)
531 0-v;
532
Chris Lattner3616a8a2007-11-07 06:06:38 +0000[diff] [blame]533# Define &gt; with the same precedence as &gt;.
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]534def binary&gt; 10 (LHS RHS)
Chris Lattner61ad4492007-11-23 22:19:33 +0000[diff] [blame]535 RHS &lt; LHS;
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]536
537# Binary logical or, which does not short circuit.
538def binary| 5 (LHS RHS)
539 if LHS then
540 1
541 else if RHS then
542 1
543 else
544 0;
545
546# Binary logical and, which does not short circuit.
547def binary&amp; 6 (LHS RHS)
548 if !LHS then
549 0
550 else
551 !!RHS;
552
553# Define = with slightly lower precedence than relationals.
554def binary = 9 (LHS RHS)
555 !(LHS &lt; RHS | LHS &gt; RHS);
556
557</pre>
558</div>
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]559
560
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]561<p>Given the previous if/then/else support, we can also define interesting
562functions for I/O. For example, the following prints out a character whose
563"density" reflects the value passed in: the lower the value, the denser the
564character:</p>
565
566<div class="doc_code">
567<pre>
568ready&gt;
569<b>
570extern putchard(char)
571def printdensity(d)
572 if d &gt; 8 then
573 putchard(32) # ' '
574 else if d &gt; 4 then
575 putchard(46) # '.'
576 else if d &gt; 2 then
577 putchard(43) # '+'
578 else
579 putchard(42); # '*'</b>
580...
581ready&gt; <b>printdensity(1): printdensity(2): printdensity(3) :
582 printdensity(4): printdensity(5): printdensity(9): putchard(10);</b>
583*++..
584Evaluated to 0.000000
585</pre>
586</div>
587
588<p>Based on these simple primitive operations, we can start to define more
589interesting things. For example, here's a little function that solves for the
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]590number of iterations it takes a function in the complex plane to
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]591converge:</p>
592
593<div class="doc_code">
594<pre>
595# determine whether the specific location diverges.
596# Solve for z = z^2 + c in the complex plane.
597def mandleconverger(real imag iters creal cimag)
598 if iters &gt; 255 | (real*real + imag*imag &gt; 4) then
599 iters
600 else
601 mandleconverger(real*real - imag*imag + creal,
602 2*real*imag + cimag,
603 iters+1, creal, cimag);
604
605# return the number of iterations required for the iteration to escape
606def mandleconverge(real imag)
607 mandleconverger(real, imag, 0, real, imag);
608</pre>
609</div>
610
Chris Lattnerb5d81b32007-11-02 05:54:25 +0000[diff] [blame]611<p>This "z = z<sup>2</sup> + c" function is a beautiful little creature that is the basis
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]612for computation of the <a
613href="http://en.wikipedia.org/wiki/Mandelbrot_set">Mandelbrot Set</a>. Our
614<tt>mandelconverge</tt> function returns the number of iterations that it takes
615for a complex orbit to escape, saturating to 255. This is not a very useful
616function by itself, but if you plot its value over a two-dimensional plane,
Chris Lattner3616a8a2007-11-07 06:06:38 +0000[diff] [blame]617you can see the Mandelbrot set. Given that we are limited to using putchard
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]618here, our amazing graphical output is limited, but we can whip together
619something using the density plotter above:</p>
620
621<div class="doc_code">
622<pre>
Chris Lattner3616a8a2007-11-07 06:06:38 +0000[diff] [blame]623# compute and plot the mandlebrot set with the specified 2 dimensional range
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]624# info.
625def mandelhelp(xmin xmax xstep ymin ymax ystep)
626 for y = ymin, y &lt; ymax, ystep in (
627 (for x = xmin, x &lt; xmax, xstep in
628 printdensity(mandleconverge(x,y)))
629 : putchard(10)
630 )
631
632# mandel - This is a convenient helper function for ploting the mandelbrot set
Chris Lattner3616a8a2007-11-07 06:06:38 +0000[diff] [blame]633# from the specified position with the specified Magnification.
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]634def mandel(realstart imagstart realmag imagmag)
635 mandelhelp(realstart, realstart+realmag*78, realmag,
636 imagstart, imagstart+imagmag*40, imagmag);
637</pre>
638</div>
639
640<p>Given this, we can try plotting out the mandlebrot set! Lets try it out:</p>
641
642<div class="doc_code">
643<pre>
644ready&gt; <b>mandel(-2.3, -1.3, 0.05, 0.07);</b>
645*******************************+++++++++++*************************************
646*************************+++++++++++++++++++++++*******************************
647**********************+++++++++++++++++++++++++++++****************************
648*******************+++++++++++++++++++++.. ...++++++++*************************
649*****************++++++++++++++++++++++.... ...+++++++++***********************
650***************+++++++++++++++++++++++..... ...+++++++++*********************
651**************+++++++++++++++++++++++.... ....+++++++++********************
652*************++++++++++++++++++++++...... .....++++++++*******************
653************+++++++++++++++++++++....... .......+++++++******************
654***********+++++++++++++++++++.... ... .+++++++*****************
655**********+++++++++++++++++....... .+++++++****************
656*********++++++++++++++........... ...+++++++***************
657********++++++++++++............ ...++++++++**************
658********++++++++++... .......... .++++++++**************
659*******+++++++++..... .+++++++++*************
660*******++++++++...... ..+++++++++*************
661*******++++++....... ..+++++++++*************
662*******+++++...... ..+++++++++*************
663*******.... .... ...+++++++++*************
664*******.... . ...+++++++++*************
665*******+++++...... ...+++++++++*************
666*******++++++....... ..+++++++++*************
667*******++++++++...... .+++++++++*************
668*******+++++++++..... ..+++++++++*************
669********++++++++++... .......... .++++++++**************
670********++++++++++++............ ...++++++++**************
671*********++++++++++++++.......... ...+++++++***************
672**********++++++++++++++++........ .+++++++****************
673**********++++++++++++++++++++.... ... ..+++++++****************
674***********++++++++++++++++++++++....... .......++++++++*****************
675************+++++++++++++++++++++++...... ......++++++++******************
676**************+++++++++++++++++++++++.... ....++++++++********************
677***************+++++++++++++++++++++++..... ...+++++++++*********************
678*****************++++++++++++++++++++++.... ...++++++++***********************
679*******************+++++++++++++++++++++......++++++++*************************
680*********************++++++++++++++++++++++.++++++++***************************
681*************************+++++++++++++++++++++++*******************************
682******************************+++++++++++++************************************
683*******************************************************************************
684*******************************************************************************
685*******************************************************************************
686Evaluated to 0.000000
687ready&gt; <b>mandel(-2, -1, 0.02, 0.04);</b>
688**************************+++++++++++++++++++++++++++++++++++++++++++++++++++++
689***********************++++++++++++++++++++++++++++++++++++++++++++++++++++++++
690*********************+++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
691*******************+++++++++++++++++++++++++++++++++++++++++++++++++++++++++...
692*****************+++++++++++++++++++++++++++++++++++++++++++++++++++++++++.....
693***************++++++++++++++++++++++++++++++++++++++++++++++++++++++++........
694**************++++++++++++++++++++++++++++++++++++++++++++++++++++++...........
695************+++++++++++++++++++++++++++++++++++++++++++++++++++++..............
696***********++++++++++++++++++++++++++++++++++++++++++++++++++........ .
697**********++++++++++++++++++++++++++++++++++++++++++++++.............
698********+++++++++++++++++++++++++++++++++++++++++++..................
699*******+++++++++++++++++++++++++++++++++++++++.......................
700******+++++++++++++++++++++++++++++++++++...........................
701*****++++++++++++++++++++++++++++++++............................
702*****++++++++++++++++++++++++++++...............................
703****++++++++++++++++++++++++++...... .........................
704***++++++++++++++++++++++++......... ...... ...........
705***++++++++++++++++++++++............
706**+++++++++++++++++++++..............
707**+++++++++++++++++++................
708*++++++++++++++++++.................
709*++++++++++++++++............ ...
710*++++++++++++++..............
711*+++....++++................
712*.......... ...........
713*
714*.......... ...........
715*+++....++++................
716*++++++++++++++..............
717*++++++++++++++++............ ...
718*++++++++++++++++++.................
719**+++++++++++++++++++................
720**+++++++++++++++++++++..............
721***++++++++++++++++++++++............
722***++++++++++++++++++++++++......... ...... ...........
723****++++++++++++++++++++++++++...... .........................
724*****++++++++++++++++++++++++++++...............................
725*****++++++++++++++++++++++++++++++++............................
726******+++++++++++++++++++++++++++++++++++...........................
727*******+++++++++++++++++++++++++++++++++++++++.......................
728********+++++++++++++++++++++++++++++++++++++++++++..................
729Evaluated to 0.000000
730ready&gt; <b>mandel(-0.9, -1.4, 0.02, 0.03);</b>
731*******************************************************************************
732*******************************************************************************
733*******************************************************************************
734**********+++++++++++++++++++++************************************************
735*+++++++++++++++++++++++++++++++++++++++***************************************
736+++++++++++++++++++++++++++++++++++++++++++++**********************************
737++++++++++++++++++++++++++++++++++++++++++++++++++*****************************
738++++++++++++++++++++++++++++++++++++++++++++++++++++++*************************
739+++++++++++++++++++++++++++++++++++++++++++++++++++++++++**********************
740+++++++++++++++++++++++++++++++++.........++++++++++++++++++*******************
741+++++++++++++++++++++++++++++++.... ......+++++++++++++++++++****************
742+++++++++++++++++++++++++++++....... ........+++++++++++++++++++**************
743++++++++++++++++++++++++++++........ ........++++++++++++++++++++************
744+++++++++++++++++++++++++++......... .. ...+++++++++++++++++++++**********
745++++++++++++++++++++++++++........... ....++++++++++++++++++++++********
746++++++++++++++++++++++++............. .......++++++++++++++++++++++******
747+++++++++++++++++++++++............. ........+++++++++++++++++++++++****
748++++++++++++++++++++++........... ..........++++++++++++++++++++++***
749++++++++++++++++++++........... .........++++++++++++++++++++++*
750++++++++++++++++++............ ...........++++++++++++++++++++
751++++++++++++++++............... .............++++++++++++++++++
752++++++++++++++................. ...............++++++++++++++++
753++++++++++++.................. .................++++++++++++++
754+++++++++.................. .................+++++++++++++
755++++++........ . ......... ..++++++++++++
756++............ ...... ....++++++++++
757.............. ...++++++++++
758.............. ....+++++++++
759.............. .....++++++++
760............. ......++++++++
761........... .......++++++++
762......... ........+++++++
763......... ........+++++++
764......... ....+++++++
765........ ...+++++++
766....... ...+++++++
767 ....+++++++
768 .....+++++++
769 ....+++++++
770 ....+++++++
771 ....+++++++
772Evaluated to 0.000000
773ready&gt; <b>^D</b>
774</pre>
775</div>
776
777<p>At this point, you may be starting to realize that Kaleidoscope is a real
778and powerful language. It may not be self-similar :), but it can be used to
779plot things that are!</p>
780
781<p>With this, we conclude the "adding user-defined operators" chapter of the
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]782tutorial. We have successfully augmented our language, adding the ability to extend the
783language in the library, and we have shown how this can be used to build a simple but
Chris Lattner3616a8a2007-11-07 06:06:38 +0000[diff] [blame]784interesting end-user application in Kaleidoscope. At this point, Kaleidoscope
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]785can build a variety of applications that are functional and can call functions
Chris Lattnerb5d81b32007-11-02 05:54:25 +0000[diff] [blame]786with side-effects, but it can't actually define and mutate a variable itself.
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]787</p>
788
Chris Lattner3616a8a2007-11-07 06:06:38 +0000[diff] [blame]789<p>Strikingly, variable mutation is an important feature of some
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]790languages, and it is not at all obvious how to <a href="LangImpl7.html">add
791support for mutable variables</a> without having to add an "SSA construction"
792phase to your front-end. In the next chapter, we will describe how you can
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]793add variable mutation without building SSA in your front-end.</p>
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]794
795</div>
796
797
798<!-- *********************************************************************** -->
799<div class="doc_section"><a name="code">Full Code Listing</a></div>
800<!-- *********************************************************************** -->
801
802<div class="doc_text">
803
804<p>
805Here is the complete code listing for our running example, enhanced with the
806if/then/else and for expressions.. To build this example, use:
807</p>
808
809<div class="doc_code">
810<pre>
811 # Compile
812 g++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o toy
813 # Run
814 ./toy
815</pre>
816</div>
817
818<p>Here is the code:</p>
819
820<div class="doc_code">
821<pre>
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]822#include "llvm/DerivedTypes.h"
823#include "llvm/ExecutionEngine/ExecutionEngine.h"
Owen Andersond1fbd142009-07-08 20:50:47 +0000[diff] [blame]824#include "llvm/LLVMContext.h"
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]825#include "llvm/Module.h"
826#include "llvm/ModuleProvider.h"
827#include "llvm/PassManager.h"
828#include "llvm/Analysis/Verifier.h"
829#include "llvm/Target/TargetData.h"
830#include "llvm/Transforms/Scalar.h"
Duncan Sands89f6d882008-04-13 06:22:09 +0000[diff] [blame]831#include "llvm/Support/IRBuilder.h"
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]832#include &lt;cstdio&gt;
833#include &lt;string&gt;
834#include &lt;map&gt;
835#include &lt;vector&gt;
836using namespace llvm;
837
838//===----------------------------------------------------------------------===//
839// Lexer
840//===----------------------------------------------------------------------===//
841
842// The lexer returns tokens [0-255] if it is an unknown character, otherwise one
843// of these for known things.
844enum Token {
845 tok_eof = -1,
846
847 // commands
848 tok_def = -2, tok_extern = -3,
849
850 // primary
851 tok_identifier = -4, tok_number = -5,
852
853 // control
854 tok_if = -6, tok_then = -7, tok_else = -8,
855 tok_for = -9, tok_in = -10,
856
857 // operators
858 tok_binary = -11, tok_unary = -12
859};
860
861static std::string IdentifierStr; // Filled in if tok_identifier
862static double NumVal; // Filled in if tok_number
863
864/// gettok - Return the next token from standard input.
865static int gettok() {
866 static int LastChar = ' ';
867
868 // Skip any whitespace.
869 while (isspace(LastChar))
870 LastChar = getchar();
871
872 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
873 IdentifierStr = LastChar;
874 while (isalnum((LastChar = getchar())))
875 IdentifierStr += LastChar;
876
877 if (IdentifierStr == "def") return tok_def;
878 if (IdentifierStr == "extern") return tok_extern;
879 if (IdentifierStr == "if") return tok_if;
880 if (IdentifierStr == "then") return tok_then;
881 if (IdentifierStr == "else") return tok_else;
882 if (IdentifierStr == "for") return tok_for;
883 if (IdentifierStr == "in") return tok_in;
884 if (IdentifierStr == "binary") return tok_binary;
885 if (IdentifierStr == "unary") return tok_unary;
886 return tok_identifier;
887 }
888
889 if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+
890 std::string NumStr;
891 do {
892 NumStr += LastChar;
893 LastChar = getchar();
894 } while (isdigit(LastChar) || LastChar == '.');
895
896 NumVal = strtod(NumStr.c_str(), 0);
897 return tok_number;
898 }
899
900 if (LastChar == '#') {
901 // Comment until end of line.
902 do LastChar = getchar();
Chris Lattnerc80c23f2007-12-02 22:46:01 +0000[diff] [blame]903 while (LastChar != EOF &amp;&amp; LastChar != '\n' &amp;&amp; LastChar != '\r');
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]904
905 if (LastChar != EOF)
906 return gettok();
907 }
908
909 // Check for end of file. Don't eat the EOF.
910 if (LastChar == EOF)
911 return tok_eof;
912
913 // Otherwise, just return the character as its ascii value.
914 int ThisChar = LastChar;
915 LastChar = getchar();
916 return ThisChar;
917}
918
919//===----------------------------------------------------------------------===//
920// Abstract Syntax Tree (aka Parse Tree)
921//===----------------------------------------------------------------------===//
922
923/// ExprAST - Base class for all expression nodes.
924class ExprAST {
925public:
926 virtual ~ExprAST() {}
927 virtual Value *Codegen() = 0;
928};
929
930/// NumberExprAST - Expression class for numeric literals like "1.0".
931class NumberExprAST : public ExprAST {
932 double Val;
933public:
934 NumberExprAST(double val) : Val(val) {}
935 virtual Value *Codegen();
936};
937
938/// VariableExprAST - Expression class for referencing a variable, like "a".
939class VariableExprAST : public ExprAST {
940 std::string Name;
941public:
942 VariableExprAST(const std::string &amp;name) : Name(name) {}
943 virtual Value *Codegen();
944};
945
946/// UnaryExprAST - Expression class for a unary operator.
947class UnaryExprAST : public ExprAST {
948 char Opcode;
949 ExprAST *Operand;
950public:
951 UnaryExprAST(char opcode, ExprAST *operand)
952 : Opcode(opcode), Operand(operand) {}
953 virtual Value *Codegen();
954};
955
956/// BinaryExprAST - Expression class for a binary operator.
957class BinaryExprAST : public ExprAST {
958 char Op;
959 ExprAST *LHS, *RHS;
960public:
961 BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
962 : Op(op), LHS(lhs), RHS(rhs) {}
963 virtual Value *Codegen();
964};
965
966/// CallExprAST - Expression class for function calls.
967class CallExprAST : public ExprAST {
968 std::string Callee;
969 std::vector&lt;ExprAST*&gt; Args;
970public:
971 CallExprAST(const std::string &amp;callee, std::vector&lt;ExprAST*&gt; &amp;args)
972 : Callee(callee), Args(args) {}
973 virtual Value *Codegen();
974};
975
976/// IfExprAST - Expression class for if/then/else.
977class IfExprAST : public ExprAST {
978 ExprAST *Cond, *Then, *Else;
979public:
980 IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
981 : Cond(cond), Then(then), Else(_else) {}
982 virtual Value *Codegen();
983};
984
985/// ForExprAST - Expression class for for/in.
986class ForExprAST : public ExprAST {
987 std::string VarName;
988 ExprAST *Start, *End, *Step, *Body;
989public:
990 ForExprAST(const std::string &amp;varname, ExprAST *start, ExprAST *end,
991 ExprAST *step, ExprAST *body)
992 : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
993 virtual Value *Codegen();
994};
995
996/// PrototypeAST - This class represents the "prototype" for a function,
997/// which captures its argument names as well as if it is an operator.
998class PrototypeAST {
999 std::string Name;
1000 std::vector&lt;std::string&gt; Args;
1001 bool isOperator;
1002 unsigned Precedence; // Precedence if a binary op.
1003public:
1004 PrototypeAST(const std::string &amp;name, const std::vector&lt;std::string&gt; &amp;args,
1005 bool isoperator = false, unsigned prec = 0)
1006 : Name(name), Args(args), isOperator(isoperator), Precedence(prec) {}
1007
1008 bool isUnaryOp() const { return isOperator &amp;&amp; Args.size() == 1; }
1009 bool isBinaryOp() const { return isOperator &amp;&amp; Args.size() == 2; }
1010
1011 char getOperatorName() const {
1012 assert(isUnaryOp() || isBinaryOp());
1013 return Name[Name.size()-1];
1014 }
1015
1016 unsigned getBinaryPrecedence() const { return Precedence; }
1017
1018 Function *Codegen();
1019};
1020
1021/// FunctionAST - This class represents a function definition itself.
1022class FunctionAST {
1023 PrototypeAST *Proto;
1024 ExprAST *Body;
1025public:
1026 FunctionAST(PrototypeAST *proto, ExprAST *body)
1027 : Proto(proto), Body(body) {}
1028
1029 Function *Codegen();
1030};
1031
1032//===----------------------------------------------------------------------===//
1033// Parser
1034//===----------------------------------------------------------------------===//
1035
1036/// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
1037/// token the parser it looking at. getNextToken reads another token from the
1038/// lexer and updates CurTok with its results.
1039static int CurTok;
1040static int getNextToken() {
1041 return CurTok = gettok();
1042}
1043
1044/// BinopPrecedence - This holds the precedence for each binary operator that is
1045/// defined.
1046static std::map&lt;char, int&gt; BinopPrecedence;
1047
1048/// GetTokPrecedence - Get the precedence of the pending binary operator token.
1049static int GetTokPrecedence() {
1050 if (!isascii(CurTok))
1051 return -1;
1052
1053 // Make sure it's a declared binop.
1054 int TokPrec = BinopPrecedence[CurTok];
1055 if (TokPrec &lt;= 0) return -1;
1056 return TokPrec;
1057}
1058
1059/// Error* - These are little helper functions for error handling.
1060ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
1061PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
1062FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
1063
1064static ExprAST *ParseExpression();
1065
1066/// identifierexpr
Chris Lattner20a0c802007-11-05 17:54:34 +0000[diff] [blame]1067/// ::= identifier
1068/// ::= identifier '(' expression* ')'
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1069static ExprAST *ParseIdentifierExpr() {
1070 std::string IdName = IdentifierStr;
1071
Chris Lattner20a0c802007-11-05 17:54:34 +0000[diff] [blame]1072 getNextToken(); // eat identifier.
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1073
1074 if (CurTok != '(') // Simple variable ref.
1075 return new VariableExprAST(IdName);
1076
1077 // Call.
1078 getNextToken(); // eat (
1079 std::vector&lt;ExprAST*&gt; Args;
1080 if (CurTok != ')') {
1081 while (1) {
1082 ExprAST *Arg = ParseExpression();
1083 if (!Arg) return 0;
1084 Args.push_back(Arg);
1085
1086 if (CurTok == ')') break;
1087
1088 if (CurTok != ',')
Chris Lattner6c4be9c2008-04-14 16:44:41 +0000[diff] [blame]1089 return Error("Expected ')' or ',' in argument list");
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1090 getNextToken();
1091 }
1092 }
1093
1094 // Eat the ')'.
1095 getNextToken();
1096
1097 return new CallExprAST(IdName, Args);
1098}
1099
1100/// numberexpr ::= number
1101static ExprAST *ParseNumberExpr() {
1102 ExprAST *Result = new NumberExprAST(NumVal);
1103 getNextToken(); // consume the number
1104 return Result;
1105}
1106
1107/// parenexpr ::= '(' expression ')'
1108static ExprAST *ParseParenExpr() {
1109 getNextToken(); // eat (.
1110 ExprAST *V = ParseExpression();
1111 if (!V) return 0;
1112
1113 if (CurTok != ')')
1114 return Error("expected ')'");
1115 getNextToken(); // eat ).
1116 return V;
1117}
1118
1119/// ifexpr ::= 'if' expression 'then' expression 'else' expression
1120static ExprAST *ParseIfExpr() {
1121 getNextToken(); // eat the if.
1122
1123 // condition.
1124 ExprAST *Cond = ParseExpression();
1125 if (!Cond) return 0;
1126
1127 if (CurTok != tok_then)
1128 return Error("expected then");
1129 getNextToken(); // eat the then
1130
1131 ExprAST *Then = ParseExpression();
1132 if (Then == 0) return 0;
1133
1134 if (CurTok != tok_else)
1135 return Error("expected else");
1136
1137 getNextToken();
1138
1139 ExprAST *Else = ParseExpression();
1140 if (!Else) return 0;
1141
1142 return new IfExprAST(Cond, Then, Else);
1143}
1144
Chris Lattner20a0c802007-11-05 17:54:34 +0000[diff] [blame]1145/// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1146static ExprAST *ParseForExpr() {
1147 getNextToken(); // eat the for.
1148
1149 if (CurTok != tok_identifier)
1150 return Error("expected identifier after for");
1151
1152 std::string IdName = IdentifierStr;
Chris Lattner20a0c802007-11-05 17:54:34 +0000[diff] [blame]1153 getNextToken(); // eat identifier.
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1154
1155 if (CurTok != '=')
1156 return Error("expected '=' after for");
1157 getNextToken(); // eat '='.
1158
1159
1160 ExprAST *Start = ParseExpression();
1161 if (Start == 0) return 0;
1162 if (CurTok != ',')
1163 return Error("expected ',' after for start value");
1164 getNextToken();
1165
1166 ExprAST *End = ParseExpression();
1167 if (End == 0) return 0;
1168
1169 // The step value is optional.
1170 ExprAST *Step = 0;
1171 if (CurTok == ',') {
1172 getNextToken();
1173 Step = ParseExpression();
1174 if (Step == 0) return 0;
1175 }
1176
1177 if (CurTok != tok_in)
1178 return Error("expected 'in' after for");
1179 getNextToken(); // eat 'in'.
1180
1181 ExprAST *Body = ParseExpression();
1182 if (Body == 0) return 0;
1183
1184 return new ForExprAST(IdName, Start, End, Step, Body);
1185}
1186
1187
1188/// primary
1189/// ::= identifierexpr
1190/// ::= numberexpr
1191/// ::= parenexpr
1192/// ::= ifexpr
1193/// ::= forexpr
1194static ExprAST *ParsePrimary() {
1195 switch (CurTok) {
1196 default: return Error("unknown token when expecting an expression");
1197 case tok_identifier: return ParseIdentifierExpr();
1198 case tok_number: return ParseNumberExpr();
1199 case '(': return ParseParenExpr();
1200 case tok_if: return ParseIfExpr();
1201 case tok_for: return ParseForExpr();
1202 }
1203}
1204
1205/// unary
1206/// ::= primary
1207/// ::= '!' unary
1208static ExprAST *ParseUnary() {
1209 // If the current token is not an operator, it must be a primary expr.
1210 if (!isascii(CurTok) || CurTok == '(' || CurTok == ',')
1211 return ParsePrimary();
1212
1213 // If this is a unary operator, read it.
1214 int Opc = CurTok;
1215 getNextToken();
1216 if (ExprAST *Operand = ParseUnary())
1217 return new UnaryExprAST(Opc, Operand);
1218 return 0;
1219}
1220
1221/// binoprhs
1222/// ::= ('+' unary)*
1223static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
1224 // If this is a binop, find its precedence.
1225 while (1) {
1226 int TokPrec = GetTokPrecedence();
1227
1228 // If this is a binop that binds at least as tightly as the current binop,
1229 // consume it, otherwise we are done.
1230 if (TokPrec &lt; ExprPrec)
1231 return LHS;
1232
1233 // Okay, we know this is a binop.
1234 int BinOp = CurTok;
1235 getNextToken(); // eat binop
1236
1237 // Parse the unary expression after the binary operator.
1238 ExprAST *RHS = ParseUnary();
1239 if (!RHS) return 0;
1240
1241 // If BinOp binds less tightly with RHS than the operator after RHS, let
1242 // the pending operator take RHS as its LHS.
1243 int NextPrec = GetTokPrecedence();
1244 if (TokPrec &lt; NextPrec) {
1245 RHS = ParseBinOpRHS(TokPrec+1, RHS);
1246 if (RHS == 0) return 0;
1247 }
1248
1249 // Merge LHS/RHS.
1250 LHS = new BinaryExprAST(BinOp, LHS, RHS);
1251 }
1252}
1253
1254/// expression
1255/// ::= unary binoprhs
1256///
1257static ExprAST *ParseExpression() {
1258 ExprAST *LHS = ParseUnary();
1259 if (!LHS) return 0;
1260
1261 return ParseBinOpRHS(0, LHS);
1262}
1263
1264/// prototype
1265/// ::= id '(' id* ')'
1266/// ::= binary LETTER number? (id, id)
1267/// ::= unary LETTER (id)
1268static PrototypeAST *ParsePrototype() {
1269 std::string FnName;
1270
1271 int Kind = 0; // 0 = identifier, 1 = unary, 2 = binary.
1272 unsigned BinaryPrecedence = 30;
1273
1274 switch (CurTok) {
1275 default:
1276 return ErrorP("Expected function name in prototype");
1277 case tok_identifier:
1278 FnName = IdentifierStr;
1279 Kind = 0;
1280 getNextToken();
1281 break;
1282 case tok_unary:
1283 getNextToken();
1284 if (!isascii(CurTok))
1285 return ErrorP("Expected unary operator");
1286 FnName = "unary";
1287 FnName += (char)CurTok;
1288 Kind = 1;
1289 getNextToken();
1290 break;
1291 case tok_binary:
1292 getNextToken();
1293 if (!isascii(CurTok))
1294 return ErrorP("Expected binary operator");
1295 FnName = "binary";
1296 FnName += (char)CurTok;
1297 Kind = 2;
1298 getNextToken();
1299
1300 // Read the precedence if present.
1301 if (CurTok == tok_number) {
1302 if (NumVal &lt; 1 || NumVal &gt; 100)
1303 return ErrorP("Invalid precedecnce: must be 1..100");
1304 BinaryPrecedence = (unsigned)NumVal;
1305 getNextToken();
1306 }
1307 break;
1308 }
1309
1310 if (CurTok != '(')
1311 return ErrorP("Expected '(' in prototype");
1312
1313 std::vector&lt;std::string&gt; ArgNames;
1314 while (getNextToken() == tok_identifier)
1315 ArgNames.push_back(IdentifierStr);
1316 if (CurTok != ')')
1317 return ErrorP("Expected ')' in prototype");
1318
1319 // success.
1320 getNextToken(); // eat ')'.
1321
1322 // Verify right number of names for operator.
1323 if (Kind &amp;&amp; ArgNames.size() != Kind)
1324 return ErrorP("Invalid number of operands for operator");
1325
1326 return new PrototypeAST(FnName, ArgNames, Kind != 0, BinaryPrecedence);
1327}
1328
1329/// definition ::= 'def' prototype expression
1330static FunctionAST *ParseDefinition() {
1331 getNextToken(); // eat def.
1332 PrototypeAST *Proto = ParsePrototype();
1333 if (Proto == 0) return 0;
1334
1335 if (ExprAST *E = ParseExpression())
1336 return new FunctionAST(Proto, E);
1337 return 0;
1338}
1339
1340/// toplevelexpr ::= expression
1341static FunctionAST *ParseTopLevelExpr() {
1342 if (ExprAST *E = ParseExpression()) {
1343 // Make an anonymous proto.
1344 PrototypeAST *Proto = new PrototypeAST("", std::vector&lt;std::string&gt;());
1345 return new FunctionAST(Proto, E);
1346 }
1347 return 0;
1348}
1349
1350/// external ::= 'extern' prototype
1351static PrototypeAST *ParseExtern() {
1352 getNextToken(); // eat extern.
1353 return ParsePrototype();
1354}
1355
1356//===----------------------------------------------------------------------===//
1357// Code Generation
1358//===----------------------------------------------------------------------===//
1359
1360static Module *TheModule;
Owen Andersond1fbd142009-07-08 20:50:47 +0000[diff] [blame]1361static IRBuilder&lt;&gt; Builder(getGlobalContext());
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1362static std::map&lt;std::string, Value*&gt; NamedValues;
1363static FunctionPassManager *TheFPM;
1364
1365Value *ErrorV(const char *Str) { Error(Str); return 0; }
1366
1367Value *NumberExprAST::Codegen() {
Owen Anderson6f83c9c2009-07-27 20:59:43 +0000[diff] [blame]1368 return ConstantFP::get(getGlobalContext(), APFloat(Val));
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1369}
1370
1371Value *VariableExprAST::Codegen() {
1372 // Look this variable up in the function.
1373 Value *V = NamedValues[Name];
1374 return V ? V : ErrorV("Unknown variable name");
1375}
1376
1377Value *UnaryExprAST::Codegen() {
1378 Value *OperandV = Operand-&gt;Codegen();
1379 if (OperandV == 0) return 0;
1380
1381 Function *F = TheModule-&gt;getFunction(std::string("unary")+Opcode);
1382 if (F == 0)
1383 return ErrorV("Unknown unary operator");
1384
1385 return Builder.CreateCall(F, OperandV, "unop");
1386}
1387
1388
1389Value *BinaryExprAST::Codegen() {
1390 Value *L = LHS-&gt;Codegen();
1391 Value *R = RHS-&gt;Codegen();
1392 if (L == 0 || R == 0) return 0;
1393
1394 switch (Op) {
1395 case '+': return Builder.CreateAdd(L, R, "addtmp");
1396 case '-': return Builder.CreateSub(L, R, "subtmp");
1397 case '*': return Builder.CreateMul(L, R, "multmp");
1398 case '&lt;':
Chris Lattner71155212007-11-06 01:39:12 +0000[diff] [blame]1399 L = Builder.CreateFCmpULT(L, R, "cmptmp");
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1400 // Convert bool 0/1 to double 0.0 or 1.0
Owen Anderson1d0be152009-08-13 21:58:54 +0000[diff] [blame^]1401 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()), "booltmp");
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1402 default: break;
1403 }
1404
1405 // If it wasn't a builtin binary operator, it must be a user defined one. Emit
1406 // a call to it.
1407 Function *F = TheModule-&gt;getFunction(std::string("binary")+Op);
1408 assert(F &amp;&amp; "binary operator not found!");
1409
1410 Value *Ops[] = { L, R };
1411 return Builder.CreateCall(F, Ops, Ops+2, "binop");
1412}
1413
1414Value *CallExprAST::Codegen() {
1415 // Look up the name in the global module table.
1416 Function *CalleeF = TheModule-&gt;getFunction(Callee);
1417 if (CalleeF == 0)
1418 return ErrorV("Unknown function referenced");
1419
1420 // If argument mismatch error.
1421 if (CalleeF-&gt;arg_size() != Args.size())
1422 return ErrorV("Incorrect # arguments passed");
1423
1424 std::vector&lt;Value*&gt; ArgsV;
1425 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
1426 ArgsV.push_back(Args[i]-&gt;Codegen());
1427 if (ArgsV.back() == 0) return 0;
1428 }
1429
1430 return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
1431}
1432
1433Value *IfExprAST::Codegen() {
1434 Value *CondV = Cond-&gt;Codegen();
1435 if (CondV == 0) return 0;
1436
1437 // Convert condition to a bool by comparing equal to 0.0.
1438 CondV = Builder.CreateFCmpONE(CondV,
Owen Anderson6f83c9c2009-07-27 20:59:43 +0000[diff] [blame]1439 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1440 "ifcond");
1441
1442 Function *TheFunction = Builder.GetInsertBlock()-&gt;getParent();
1443
1444 // Create blocks for the then and else cases. Insert the 'then' block at the
1445 // end of the function.
Owen Anderson1d0be152009-08-13 21:58:54 +0000[diff] [blame^]1446 BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunction);
1447 BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else");
1448 BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont");
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1449
1450 Builder.CreateCondBr(CondV, ThenBB, ElseBB);
1451
1452 // Emit then value.
1453 Builder.SetInsertPoint(ThenBB);
1454
1455 Value *ThenV = Then-&gt;Codegen();
1456 if (ThenV == 0) return 0;
1457
1458 Builder.CreateBr(MergeBB);
1459 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
1460 ThenBB = Builder.GetInsertBlock();
1461
1462 // Emit else block.
1463 TheFunction-&gt;getBasicBlockList().push_back(ElseBB);
1464 Builder.SetInsertPoint(ElseBB);
1465
1466 Value *ElseV = Else-&gt;Codegen();
1467 if (ElseV == 0) return 0;
1468
1469 Builder.CreateBr(MergeBB);
1470 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
1471 ElseBB = Builder.GetInsertBlock();
1472
1473 // Emit merge block.
1474 TheFunction-&gt;getBasicBlockList().push_back(MergeBB);
1475 Builder.SetInsertPoint(MergeBB);
Owen Anderson1d0be152009-08-13 21:58:54 +0000[diff] [blame^]1476 PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), "iftmp");
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1477
1478 PN-&gt;addIncoming(ThenV, ThenBB);
1479 PN-&gt;addIncoming(ElseV, ElseBB);
1480 return PN;
1481}
1482
1483Value *ForExprAST::Codegen() {
1484 // Output this as:
1485 // ...
1486 // start = startexpr
1487 // goto loop
1488 // loop:
1489 // variable = phi [start, loopheader], [nextvariable, loopend]
1490 // ...
1491 // bodyexpr
1492 // ...
1493 // loopend:
1494 // step = stepexpr
1495 // nextvariable = variable + step
1496 // endcond = endexpr
1497 // br endcond, loop, endloop
1498 // outloop:
1499
1500 // Emit the start code first, without 'variable' in scope.
1501 Value *StartVal = Start-&gt;Codegen();
1502 if (StartVal == 0) return 0;
1503
1504 // Make the new basic block for the loop header, inserting after current
1505 // block.
1506 Function *TheFunction = Builder.GetInsertBlock()-&gt;getParent();
1507 BasicBlock *PreheaderBB = Builder.GetInsertBlock();
Owen Anderson1d0be152009-08-13 21:58:54 +0000[diff] [blame^]1508 BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1509
1510 // Insert an explicit fall through from the current block to the LoopBB.
1511 Builder.CreateBr(LoopBB);
1512
1513 // Start insertion in LoopBB.
1514 Builder.SetInsertPoint(LoopBB);
1515
1516 // Start the PHI node with an entry for Start.
Owen Anderson1d0be152009-08-13 21:58:54 +0000[diff] [blame^]1517 PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), VarName.c_str());
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1518 Variable-&gt;addIncoming(StartVal, PreheaderBB);
1519
1520 // Within the loop, the variable is defined equal to the PHI node. If it
1521 // shadows an existing variable, we have to restore it, so save it now.
1522 Value *OldVal = NamedValues[VarName];
1523 NamedValues[VarName] = Variable;
1524
1525 // Emit the body of the loop. This, like any other expr, can change the
1526 // current BB. Note that we ignore the value computed by the body, but don't
1527 // allow an error.
1528 if (Body-&gt;Codegen() == 0)
1529 return 0;
1530
1531 // Emit the step value.
1532 Value *StepVal;
1533 if (Step) {
1534 StepVal = Step-&gt;Codegen();
1535 if (StepVal == 0) return 0;
1536 } else {
1537 // If not specified, use 1.0.
Owen Anderson6f83c9c2009-07-27 20:59:43 +0000[diff] [blame]1538 StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1539 }
1540
1541 Value *NextVar = Builder.CreateAdd(Variable, StepVal, "nextvar");
1542
1543 // Compute the end condition.
1544 Value *EndCond = End-&gt;Codegen();
1545 if (EndCond == 0) return EndCond;
1546
1547 // Convert condition to a bool by comparing equal to 0.0.
1548 EndCond = Builder.CreateFCmpONE(EndCond,
Owen Anderson6f83c9c2009-07-27 20:59:43 +0000[diff] [blame]1549 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1550 "loopcond");
1551
1552 // Create the "after loop" block and insert it.
1553 BasicBlock *LoopEndBB = Builder.GetInsertBlock();
Owen Anderson1d0be152009-08-13 21:58:54 +0000[diff] [blame^]1554 BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1555
1556 // Insert the conditional branch into the end of LoopEndBB.
1557 Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
1558
1559 // Any new code will be inserted in AfterBB.
1560 Builder.SetInsertPoint(AfterBB);
1561
1562 // Add a new entry to the PHI node for the backedge.
1563 Variable-&gt;addIncoming(NextVar, LoopEndBB);
1564
1565 // Restore the unshadowed variable.
1566 if (OldVal)
1567 NamedValues[VarName] = OldVal;
1568 else
1569 NamedValues.erase(VarName);
1570
1571
1572 // for expr always returns 0.0.
Owen Anderson1d0be152009-08-13 21:58:54 +0000[diff] [blame^]1573 return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1574}
1575
1576Function *PrototypeAST::Codegen() {
1577 // Make the function type: double(double,double) etc.
Owen Anderson1d0be152009-08-13 21:58:54 +0000[diff] [blame^]1578 std::vector&lt;const Type*&gt; Doubles(Args.size(), Type::getDoubleTy(getGlobalContext()));
1579 FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()), Doubles, false);
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1580
Gabor Greifdf7d2b42008-04-19 22:25:09 +0000[diff] [blame]1581 Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1582
1583 // If F conflicted, there was already something named 'Name'. If it has a
1584 // body, don't allow redefinition or reextern.
1585 if (F-&gt;getName() != Name) {
1586 // Delete the one we just made and get the existing one.
1587 F-&gt;eraseFromParent();
1588 F = TheModule-&gt;getFunction(Name);
1589
1590 // If F already has a body, reject this.
1591 if (!F-&gt;empty()) {
1592 ErrorF("redefinition of function");
1593 return 0;
1594 }
1595
1596 // If F took a different number of args, reject.
1597 if (F-&gt;arg_size() != Args.size()) {
1598 ErrorF("redefinition of function with different # args");
1599 return 0;
1600 }
1601 }
1602
1603 // Set names for all arguments.
1604 unsigned Idx = 0;
1605 for (Function::arg_iterator AI = F-&gt;arg_begin(); Idx != Args.size();
1606 ++AI, ++Idx) {
1607 AI-&gt;setName(Args[Idx]);
1608
1609 // Add arguments to variable symbol table.
1610 NamedValues[Args[Idx]] = AI;
1611 }
1612
1613 return F;
1614}
1615
1616Function *FunctionAST::Codegen() {
1617 NamedValues.clear();
1618
1619 Function *TheFunction = Proto-&gt;Codegen();
1620 if (TheFunction == 0)
1621 return 0;
1622
1623 // If this is an operator, install it.
1624 if (Proto-&gt;isBinaryOp())
1625 BinopPrecedence[Proto-&gt;getOperatorName()] = Proto-&gt;getBinaryPrecedence();
1626
1627 // Create a new basic block to start insertion into.
Owen Anderson1d0be152009-08-13 21:58:54 +0000[diff] [blame^]1628 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1629 Builder.SetInsertPoint(BB);
1630
1631 if (Value *RetVal = Body-&gt;Codegen()) {
1632 // Finish off the function.
1633 Builder.CreateRet(RetVal);
1634
1635 // Validate the generated code, checking for consistency.
1636 verifyFunction(*TheFunction);
1637
1638 // Optimize the function.
1639 TheFPM-&gt;run(*TheFunction);
1640
1641 return TheFunction;
1642 }
1643
1644 // Error reading body, remove function.
1645 TheFunction-&gt;eraseFromParent();
1646
1647 if (Proto-&gt;isBinaryOp())
1648 BinopPrecedence.erase(Proto-&gt;getOperatorName());
1649 return 0;
1650}
1651
1652//===----------------------------------------------------------------------===//
1653// Top-Level parsing and JIT Driver
1654//===----------------------------------------------------------------------===//
1655
1656static ExecutionEngine *TheExecutionEngine;
1657
1658static void HandleDefinition() {
1659 if (FunctionAST *F = ParseDefinition()) {
1660 if (Function *LF = F-&gt;Codegen()) {
1661 fprintf(stderr, "Read function definition:");
1662 LF-&gt;dump();
1663 }
1664 } else {
1665 // Skip token for error recovery.
1666 getNextToken();
1667 }
1668}
1669
1670static void HandleExtern() {
1671 if (PrototypeAST *P = ParseExtern()) {
1672 if (Function *F = P-&gt;Codegen()) {
1673 fprintf(stderr, "Read extern: ");
1674 F-&gt;dump();
1675 }
1676 } else {
1677 // Skip token for error recovery.
1678 getNextToken();
1679 }
1680}
1681
1682static void HandleTopLevelExpression() {
1683 // Evaluate a top level expression into an anonymous function.
1684 if (FunctionAST *F = ParseTopLevelExpr()) {
1685 if (Function *LF = F-&gt;Codegen()) {
1686 // JIT the function, returning a function pointer.
1687 void *FPtr = TheExecutionEngine-&gt;getPointerToFunction(LF);
1688
1689 // Cast it to the right type (takes no arguments, returns a double) so we
1690 // can call it as a native function.
1691 double (*FP)() = (double (*)())FPtr;
1692 fprintf(stderr, "Evaluated to %f\n", FP());
1693 }
1694 } else {
1695 // Skip token for error recovery.
1696 getNextToken();
1697 }
1698}
1699
1700/// top ::= definition | external | expression | ';'
1701static void MainLoop() {
1702 while (1) {
1703 fprintf(stderr, "ready&gt; ");
1704 switch (CurTok) {
1705 case tok_eof: return;
1706 case ';': getNextToken(); break; // ignore top level semicolons.
1707 case tok_def: HandleDefinition(); break;
1708 case tok_extern: HandleExtern(); break;
1709 default: HandleTopLevelExpression(); break;
1710 }
1711 }
1712}
1713
1714
1715
1716//===----------------------------------------------------------------------===//
1717// "Library" functions that can be "extern'd" from user code.
1718//===----------------------------------------------------------------------===//
1719
1720/// putchard - putchar that takes a double and returns 0.
1721extern "C"
1722double putchard(double X) {
1723 putchar((char)X);
1724 return 0;
1725}
1726
1727/// printd - printf that takes a double prints it as "%f\n", returning 0.
1728extern "C"
1729double printd(double X) {
1730 printf("%f\n", X);
1731 return 0;
1732}
1733
1734//===----------------------------------------------------------------------===//
1735// Main driver code.
1736//===----------------------------------------------------------------------===//
1737
1738int main() {
1739 // Install standard binary operators.
1740 // 1 is lowest precedence.
1741 BinopPrecedence['&lt;'] = 10;
1742 BinopPrecedence['+'] = 20;
1743 BinopPrecedence['-'] = 20;
1744 BinopPrecedence['*'] = 40; // highest.
1745
1746 // Prime the first token.
1747 fprintf(stderr, "ready&gt; ");
1748 getNextToken();
1749
1750 // Make the module, which holds all the code.
Owen Andersond1fbd142009-07-08 20:50:47 +0000[diff] [blame]1751 TheModule = new Module("my cool jit", getGlobalContext());
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1752
1753 // Create the JIT.
Reid Kleckner4b1511b2009-07-18 00:42:18 +0000[diff] [blame]1754 TheExecutionEngine = EngineBuilder(TheModule).create();
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1755
1756 {
1757 ExistingModuleProvider OurModuleProvider(TheModule);
1758 FunctionPassManager OurFPM(&amp;OurModuleProvider);
1759
1760 // Set up the optimizer pipeline. Start with registering info about how the
1761 // target lays out data structures.
1762 OurFPM.add(new TargetData(*TheExecutionEngine-&gt;getTargetData()));
1763 // Do simple "peephole" optimizations and bit-twiddling optzns.
1764 OurFPM.add(createInstructionCombiningPass());
1765 // Reassociate expressions.
1766 OurFPM.add(createReassociatePass());
1767 // Eliminate Common SubExpressions.
1768 OurFPM.add(createGVNPass());
1769 // Simplify the control flow graph (deleting unreachable blocks, etc).
1770 OurFPM.add(createCFGSimplificationPass());
1771 // Set the global so the code gen can use this.
1772 TheFPM = &amp;OurFPM;
1773
1774 // Run the main "interpreter loop" now.
1775 MainLoop();
1776
1777 TheFPM = 0;
Chris Lattner515686b2008-02-05 06:18:42 +0000[diff] [blame]1778
1779 // Print out all of the generated code.
1780 TheModule-&gt;dump();
1781 } // Free module provider (and thus the module) and pass manager.
1782
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1783 return 0;
1784}
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]1785</pre>
1786</div>
1787
Chris Lattner729eb142008-02-10 19:11:04 +0000[diff] [blame]1788<a href="LangImpl7.html">Next: Extending the language: mutable variables / SSA construction</a>
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]1789</div>
1790
1791<!-- *********************************************************************** -->
1792<hr>
1793<address>
1794 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
1795 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
1796 <a href="http://validator.w3.org/check/referer"><img
1797 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
1798
1799 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
1800 <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
1801 Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $
1802</address>
1803</body>
1804</html>