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