Gitiles
Code Review Sign In
gerrit-public.fairphone.software / fp2-dev / platform / external / llvm / c7d93bec47bacf1454959af652fc5f7f5923c19c / . / docs / tutorial / LangImpl6.html
blob: 17ba301d4ab2c6883decb1df46cf1c9aa717b091 [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
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000[diff] [blame]14<h1>Kaleidoscope: Extending the Language: User-defined Operators</h1>
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<!-- *********************************************************************** -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000[diff] [blame]37<h2><a name="intro">Chapter 6 Introduction</a></h2>
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]38<!-- *********************************************************************** -->
39
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000[diff] [blame]40<div>
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]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<!-- *********************************************************************** -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000[diff] [blame]63<h2><a name="idea">User-defined Operators: the Idea</a></h2>
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]64<!-- *********************************************************************** -->
65
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000[diff] [blame]66<div>
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]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<!-- *********************************************************************** -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000[diff] [blame]128<h2><a name="binary">User-defined Binary Operators</a></h2>
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]129<!-- *********************************************************************** -->
130
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000[diff] [blame]131<div>
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]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) {
Eric Christopher2214b812010-06-14 06:09:39 +0000[diff] [blame]280 case '+': return Builder.CreateFAdd(L, R, "addtmp");
281 case '-': return Builder.CreateFSub(L, R, "subtmp");
282 case '*': return Builder.CreateFMul(L, R, "multmp");
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]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
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +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<!-- *********************************************************************** -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000[diff] [blame]345<h2><a name="unary">User-defined Unary Operators</a></h2>
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]346<!-- *********************************************************************** -->
347
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000[diff] [blame]348<div>
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]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<!-- *********************************************************************** -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000[diff] [blame]494<h2><a name="example">Kicking the Tires</a></h2>
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]495<!-- *********************************************************************** -->
496
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000[diff] [blame]497<div>
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]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 Lattner6808cdc2010-06-21 20:31:30 +0000[diff] [blame]534# Define &gt; with the same precedence as &lt;.
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
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]798<!-- *********************************************************************** -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000[diff] [blame]799<h2><a name="code">Full Code Listing</a></h2>
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]800<!-- *********************************************************************** -->
801
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000[diff] [blame]802<div>
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]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
David Chisnallc7d93be2011-10-04 19:36:30 +0000[diff] [blame^]818<p>On some platforms, you will need to specify -rdynamic or -Wl,--export-dynamic
819when linking. This ensures that symbols defined in the main executable are
820exported to the dynamic linker and so are available for symbol resolution at
821run time. This is not needed if you compile your support code into a shared
822library, although doing that will cause problems on Windows.</p>
823
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]824<p>Here is the code:</p>
825
826<div class="doc_code">
827<pre>
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]828#include "llvm/DerivedTypes.h"
829#include "llvm/ExecutionEngine/ExecutionEngine.h"
Nick Lewycky422094c2009-09-13 21:38:54 +0000[diff] [blame]830#include "llvm/ExecutionEngine/JIT.h"
Owen Andersond1fbd142009-07-08 20:50:47 +0000[diff] [blame]831#include "llvm/LLVMContext.h"
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]832#include "llvm/Module.h"
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]833#include "llvm/PassManager.h"
834#include "llvm/Analysis/Verifier.h"
Dan Gohmanab7fa082010-11-16 17:28:22 +0000[diff] [blame]835#include "llvm/Analysis/Passes.h"
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]836#include "llvm/Target/TargetData.h"
Nick Lewycky422094c2009-09-13 21:38:54 +0000[diff] [blame]837#include "llvm/Target/TargetSelect.h"
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]838#include "llvm/Transforms/Scalar.h"
Duncan Sands89f6d882008-04-13 06:22:09 +0000[diff] [blame]839#include "llvm/Support/IRBuilder.h"
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]840#include &lt;cstdio&gt;
841#include &lt;string&gt;
842#include &lt;map&gt;
843#include &lt;vector&gt;
844using namespace llvm;
845
846//===----------------------------------------------------------------------===//
847// Lexer
848//===----------------------------------------------------------------------===//
849
850// The lexer returns tokens [0-255] if it is an unknown character, otherwise one
851// of these for known things.
852enum Token {
853 tok_eof = -1,
854
855 // commands
856 tok_def = -2, tok_extern = -3,
857
858 // primary
859 tok_identifier = -4, tok_number = -5,
860
861 // control
862 tok_if = -6, tok_then = -7, tok_else = -8,
863 tok_for = -9, tok_in = -10,
864
865 // operators
866 tok_binary = -11, tok_unary = -12
867};
868
869static std::string IdentifierStr; // Filled in if tok_identifier
870static double NumVal; // Filled in if tok_number
871
872/// gettok - Return the next token from standard input.
873static int gettok() {
874 static int LastChar = ' ';
875
876 // Skip any whitespace.
877 while (isspace(LastChar))
878 LastChar = getchar();
879
880 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
881 IdentifierStr = LastChar;
882 while (isalnum((LastChar = getchar())))
883 IdentifierStr += LastChar;
884
885 if (IdentifierStr == "def") return tok_def;
886 if (IdentifierStr == "extern") return tok_extern;
887 if (IdentifierStr == "if") return tok_if;
888 if (IdentifierStr == "then") return tok_then;
889 if (IdentifierStr == "else") return tok_else;
890 if (IdentifierStr == "for") return tok_for;
891 if (IdentifierStr == "in") return tok_in;
892 if (IdentifierStr == "binary") return tok_binary;
893 if (IdentifierStr == "unary") return tok_unary;
894 return tok_identifier;
895 }
896
897 if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+
898 std::string NumStr;
899 do {
900 NumStr += LastChar;
901 LastChar = getchar();
902 } while (isdigit(LastChar) || LastChar == '.');
903
904 NumVal = strtod(NumStr.c_str(), 0);
905 return tok_number;
906 }
907
908 if (LastChar == '#') {
909 // Comment until end of line.
910 do LastChar = getchar();
Chris Lattnerc80c23f2007-12-02 22:46:01 +0000[diff] [blame]911 while (LastChar != EOF &amp;&amp; LastChar != '\n' &amp;&amp; LastChar != '\r');
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]912
913 if (LastChar != EOF)
914 return gettok();
915 }
916
917 // Check for end of file. Don't eat the EOF.
918 if (LastChar == EOF)
919 return tok_eof;
920
921 // Otherwise, just return the character as its ascii value.
922 int ThisChar = LastChar;
923 LastChar = getchar();
924 return ThisChar;
925}
926
927//===----------------------------------------------------------------------===//
928// Abstract Syntax Tree (aka Parse Tree)
929//===----------------------------------------------------------------------===//
930
931/// ExprAST - Base class for all expression nodes.
932class ExprAST {
933public:
934 virtual ~ExprAST() {}
935 virtual Value *Codegen() = 0;
936};
937
938/// NumberExprAST - Expression class for numeric literals like "1.0".
939class NumberExprAST : public ExprAST {
940 double Val;
941public:
942 NumberExprAST(double val) : Val(val) {}
943 virtual Value *Codegen();
944};
945
946/// VariableExprAST - Expression class for referencing a variable, like "a".
947class VariableExprAST : public ExprAST {
948 std::string Name;
949public:
950 VariableExprAST(const std::string &amp;name) : Name(name) {}
951 virtual Value *Codegen();
952};
953
954/// UnaryExprAST - Expression class for a unary operator.
955class UnaryExprAST : public ExprAST {
956 char Opcode;
957 ExprAST *Operand;
958public:
959 UnaryExprAST(char opcode, ExprAST *operand)
960 : Opcode(opcode), Operand(operand) {}
961 virtual Value *Codegen();
962};
963
964/// BinaryExprAST - Expression class for a binary operator.
965class BinaryExprAST : public ExprAST {
966 char Op;
967 ExprAST *LHS, *RHS;
968public:
969 BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
970 : Op(op), LHS(lhs), RHS(rhs) {}
971 virtual Value *Codegen();
972};
973
974/// CallExprAST - Expression class for function calls.
975class CallExprAST : public ExprAST {
976 std::string Callee;
977 std::vector&lt;ExprAST*&gt; Args;
978public:
979 CallExprAST(const std::string &amp;callee, std::vector&lt;ExprAST*&gt; &amp;args)
980 : Callee(callee), Args(args) {}
981 virtual Value *Codegen();
982};
983
984/// IfExprAST - Expression class for if/then/else.
985class IfExprAST : public ExprAST {
986 ExprAST *Cond, *Then, *Else;
987public:
988 IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
989 : Cond(cond), Then(then), Else(_else) {}
990 virtual Value *Codegen();
991};
992
993/// ForExprAST - Expression class for for/in.
994class ForExprAST : public ExprAST {
995 std::string VarName;
996 ExprAST *Start, *End, *Step, *Body;
997public:
998 ForExprAST(const std::string &amp;varname, ExprAST *start, ExprAST *end,
999 ExprAST *step, ExprAST *body)
1000 : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
1001 virtual Value *Codegen();
1002};
1003
1004/// PrototypeAST - This class represents the "prototype" for a function,
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]1005/// which captures its name, and its argument names (thus implicitly the number
1006/// of arguments the function takes), as well as if it is an operator.
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1007class PrototypeAST {
1008 std::string Name;
1009 std::vector&lt;std::string&gt; Args;
1010 bool isOperator;
1011 unsigned Precedence; // Precedence if a binary op.
1012public:
1013 PrototypeAST(const std::string &amp;name, const std::vector&lt;std::string&gt; &amp;args,
1014 bool isoperator = false, unsigned prec = 0)
1015 : Name(name), Args(args), isOperator(isoperator), Precedence(prec) {}
1016
1017 bool isUnaryOp() const { return isOperator &amp;&amp; Args.size() == 1; }
1018 bool isBinaryOp() const { return isOperator &amp;&amp; Args.size() == 2; }
1019
1020 char getOperatorName() const {
1021 assert(isUnaryOp() || isBinaryOp());
1022 return Name[Name.size()-1];
1023 }
1024
1025 unsigned getBinaryPrecedence() const { return Precedence; }
1026
1027 Function *Codegen();
1028};
1029
1030/// FunctionAST - This class represents a function definition itself.
1031class FunctionAST {
1032 PrototypeAST *Proto;
1033 ExprAST *Body;
1034public:
1035 FunctionAST(PrototypeAST *proto, ExprAST *body)
1036 : Proto(proto), Body(body) {}
1037
1038 Function *Codegen();
1039};
1040
1041//===----------------------------------------------------------------------===//
1042// Parser
1043//===----------------------------------------------------------------------===//
1044
1045/// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]1046/// token the parser is looking at. getNextToken reads another token from the
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1047/// lexer and updates CurTok with its results.
1048static int CurTok;
1049static int getNextToken() {
1050 return CurTok = gettok();
1051}
1052
1053/// BinopPrecedence - This holds the precedence for each binary operator that is
1054/// defined.
1055static std::map&lt;char, int&gt; BinopPrecedence;
1056
1057/// GetTokPrecedence - Get the precedence of the pending binary operator token.
1058static int GetTokPrecedence() {
1059 if (!isascii(CurTok))
1060 return -1;
1061
1062 // Make sure it's a declared binop.
1063 int TokPrec = BinopPrecedence[CurTok];
1064 if (TokPrec &lt;= 0) return -1;
1065 return TokPrec;
1066}
1067
1068/// Error* - These are little helper functions for error handling.
1069ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
1070PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
1071FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
1072
1073static ExprAST *ParseExpression();
1074
1075/// identifierexpr
Chris Lattner20a0c802007-11-05 17:54:34 +0000[diff] [blame]1076/// ::= identifier
1077/// ::= identifier '(' expression* ')'
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1078static ExprAST *ParseIdentifierExpr() {
1079 std::string IdName = IdentifierStr;
1080
Chris Lattner20a0c802007-11-05 17:54:34 +0000[diff] [blame]1081 getNextToken(); // eat identifier.
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1082
1083 if (CurTok != '(') // Simple variable ref.
1084 return new VariableExprAST(IdName);
1085
1086 // Call.
1087 getNextToken(); // eat (
1088 std::vector&lt;ExprAST*&gt; Args;
1089 if (CurTok != ')') {
1090 while (1) {
1091 ExprAST *Arg = ParseExpression();
1092 if (!Arg) return 0;
1093 Args.push_back(Arg);
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]1094
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1095 if (CurTok == ')') break;
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]1096
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1097 if (CurTok != ',')
Chris Lattner6c4be9c2008-04-14 16:44:41 +0000[diff] [blame]1098 return Error("Expected ')' or ',' in argument list");
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1099 getNextToken();
1100 }
1101 }
1102
1103 // Eat the ')'.
1104 getNextToken();
1105
1106 return new CallExprAST(IdName, Args);
1107}
1108
1109/// numberexpr ::= number
1110static ExprAST *ParseNumberExpr() {
1111 ExprAST *Result = new NumberExprAST(NumVal);
1112 getNextToken(); // consume the number
1113 return Result;
1114}
1115
1116/// parenexpr ::= '(' expression ')'
1117static ExprAST *ParseParenExpr() {
1118 getNextToken(); // eat (.
1119 ExprAST *V = ParseExpression();
1120 if (!V) return 0;
1121
1122 if (CurTok != ')')
1123 return Error("expected ')'");
1124 getNextToken(); // eat ).
1125 return V;
1126}
1127
1128/// ifexpr ::= 'if' expression 'then' expression 'else' expression
1129static ExprAST *ParseIfExpr() {
1130 getNextToken(); // eat the if.
1131
1132 // condition.
1133 ExprAST *Cond = ParseExpression();
1134 if (!Cond) return 0;
1135
1136 if (CurTok != tok_then)
1137 return Error("expected then");
1138 getNextToken(); // eat the then
1139
1140 ExprAST *Then = ParseExpression();
1141 if (Then == 0) return 0;
1142
1143 if (CurTok != tok_else)
1144 return Error("expected else");
1145
1146 getNextToken();
1147
1148 ExprAST *Else = ParseExpression();
1149 if (!Else) return 0;
1150
1151 return new IfExprAST(Cond, Then, Else);
1152}
1153
Chris Lattner20a0c802007-11-05 17:54:34 +0000[diff] [blame]1154/// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1155static ExprAST *ParseForExpr() {
1156 getNextToken(); // eat the for.
1157
1158 if (CurTok != tok_identifier)
1159 return Error("expected identifier after for");
1160
1161 std::string IdName = IdentifierStr;
Chris Lattner20a0c802007-11-05 17:54:34 +0000[diff] [blame]1162 getNextToken(); // eat identifier.
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1163
1164 if (CurTok != '=')
1165 return Error("expected '=' after for");
1166 getNextToken(); // eat '='.
1167
1168
1169 ExprAST *Start = ParseExpression();
1170 if (Start == 0) return 0;
1171 if (CurTok != ',')
1172 return Error("expected ',' after for start value");
1173 getNextToken();
1174
1175 ExprAST *End = ParseExpression();
1176 if (End == 0) return 0;
1177
1178 // The step value is optional.
1179 ExprAST *Step = 0;
1180 if (CurTok == ',') {
1181 getNextToken();
1182 Step = ParseExpression();
1183 if (Step == 0) return 0;
1184 }
1185
1186 if (CurTok != tok_in)
1187 return Error("expected 'in' after for");
1188 getNextToken(); // eat 'in'.
1189
1190 ExprAST *Body = ParseExpression();
1191 if (Body == 0) return 0;
1192
1193 return new ForExprAST(IdName, Start, End, Step, Body);
1194}
1195
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1196/// primary
1197/// ::= identifierexpr
1198/// ::= numberexpr
1199/// ::= parenexpr
1200/// ::= ifexpr
1201/// ::= forexpr
1202static ExprAST *ParsePrimary() {
1203 switch (CurTok) {
1204 default: return Error("unknown token when expecting an expression");
1205 case tok_identifier: return ParseIdentifierExpr();
1206 case tok_number: return ParseNumberExpr();
1207 case '(': return ParseParenExpr();
1208 case tok_if: return ParseIfExpr();
1209 case tok_for: return ParseForExpr();
1210 }
1211}
1212
1213/// unary
1214/// ::= primary
1215/// ::= '!' unary
1216static ExprAST *ParseUnary() {
1217 // If the current token is not an operator, it must be a primary expr.
1218 if (!isascii(CurTok) || CurTok == '(' || CurTok == ',')
1219 return ParsePrimary();
1220
1221 // If this is a unary operator, read it.
1222 int Opc = CurTok;
1223 getNextToken();
1224 if (ExprAST *Operand = ParseUnary())
1225 return new UnaryExprAST(Opc, Operand);
1226 return 0;
1227}
1228
1229/// binoprhs
1230/// ::= ('+' unary)*
1231static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
1232 // If this is a binop, find its precedence.
1233 while (1) {
1234 int TokPrec = GetTokPrecedence();
1235
1236 // If this is a binop that binds at least as tightly as the current binop,
1237 // consume it, otherwise we are done.
1238 if (TokPrec &lt; ExprPrec)
1239 return LHS;
1240
1241 // Okay, we know this is a binop.
1242 int BinOp = CurTok;
1243 getNextToken(); // eat binop
1244
1245 // Parse the unary expression after the binary operator.
1246 ExprAST *RHS = ParseUnary();
1247 if (!RHS) return 0;
1248
1249 // If BinOp binds less tightly with RHS than the operator after RHS, let
1250 // the pending operator take RHS as its LHS.
1251 int NextPrec = GetTokPrecedence();
1252 if (TokPrec &lt; NextPrec) {
1253 RHS = ParseBinOpRHS(TokPrec+1, RHS);
1254 if (RHS == 0) return 0;
1255 }
1256
1257 // Merge LHS/RHS.
1258 LHS = new BinaryExprAST(BinOp, LHS, RHS);
1259 }
1260}
1261
1262/// expression
1263/// ::= unary binoprhs
1264///
1265static ExprAST *ParseExpression() {
1266 ExprAST *LHS = ParseUnary();
1267 if (!LHS) return 0;
1268
1269 return ParseBinOpRHS(0, LHS);
1270}
1271
1272/// prototype
1273/// ::= id '(' id* ')'
1274/// ::= binary LETTER number? (id, id)
1275/// ::= unary LETTER (id)
1276static PrototypeAST *ParsePrototype() {
1277 std::string FnName;
1278
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]1279 unsigned Kind = 0; // 0 = identifier, 1 = unary, 2 = binary.
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1280 unsigned BinaryPrecedence = 30;
1281
1282 switch (CurTok) {
1283 default:
1284 return ErrorP("Expected function name in prototype");
1285 case tok_identifier:
1286 FnName = IdentifierStr;
1287 Kind = 0;
1288 getNextToken();
1289 break;
1290 case tok_unary:
1291 getNextToken();
1292 if (!isascii(CurTok))
1293 return ErrorP("Expected unary operator");
1294 FnName = "unary";
1295 FnName += (char)CurTok;
1296 Kind = 1;
1297 getNextToken();
1298 break;
1299 case tok_binary:
1300 getNextToken();
1301 if (!isascii(CurTok))
1302 return ErrorP("Expected binary operator");
1303 FnName = "binary";
1304 FnName += (char)CurTok;
1305 Kind = 2;
1306 getNextToken();
1307
1308 // Read the precedence if present.
1309 if (CurTok == tok_number) {
1310 if (NumVal &lt; 1 || NumVal &gt; 100)
1311 return ErrorP("Invalid precedecnce: must be 1..100");
1312 BinaryPrecedence = (unsigned)NumVal;
1313 getNextToken();
1314 }
1315 break;
1316 }
1317
1318 if (CurTok != '(')
1319 return ErrorP("Expected '(' in prototype");
1320
1321 std::vector&lt;std::string&gt; ArgNames;
1322 while (getNextToken() == tok_identifier)
1323 ArgNames.push_back(IdentifierStr);
1324 if (CurTok != ')')
1325 return ErrorP("Expected ')' in prototype");
1326
1327 // success.
1328 getNextToken(); // eat ')'.
1329
1330 // Verify right number of names for operator.
1331 if (Kind &amp;&amp; ArgNames.size() != Kind)
1332 return ErrorP("Invalid number of operands for operator");
1333
1334 return new PrototypeAST(FnName, ArgNames, Kind != 0, BinaryPrecedence);
1335}
1336
1337/// definition ::= 'def' prototype expression
1338static FunctionAST *ParseDefinition() {
1339 getNextToken(); // eat def.
1340 PrototypeAST *Proto = ParsePrototype();
1341 if (Proto == 0) return 0;
1342
1343 if (ExprAST *E = ParseExpression())
1344 return new FunctionAST(Proto, E);
1345 return 0;
1346}
1347
1348/// toplevelexpr ::= expression
1349static FunctionAST *ParseTopLevelExpr() {
1350 if (ExprAST *E = ParseExpression()) {
1351 // Make an anonymous proto.
1352 PrototypeAST *Proto = new PrototypeAST("", std::vector&lt;std::string&gt;());
1353 return new FunctionAST(Proto, E);
1354 }
1355 return 0;
1356}
1357
1358/// external ::= 'extern' prototype
1359static PrototypeAST *ParseExtern() {
1360 getNextToken(); // eat extern.
1361 return ParsePrototype();
1362}
1363
1364//===----------------------------------------------------------------------===//
1365// Code Generation
1366//===----------------------------------------------------------------------===//
1367
1368static Module *TheModule;
Owen Andersond1fbd142009-07-08 20:50:47 +0000[diff] [blame]1369static IRBuilder&lt;&gt; Builder(getGlobalContext());
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1370static std::map&lt;std::string, Value*&gt; NamedValues;
1371static FunctionPassManager *TheFPM;
1372
1373Value *ErrorV(const char *Str) { Error(Str); return 0; }
1374
1375Value *NumberExprAST::Codegen() {
Owen Anderson6f83c9c2009-07-27 20:59:43 +0000[diff] [blame]1376 return ConstantFP::get(getGlobalContext(), APFloat(Val));
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1377}
1378
1379Value *VariableExprAST::Codegen() {
1380 // Look this variable up in the function.
1381 Value *V = NamedValues[Name];
1382 return V ? V : ErrorV("Unknown variable name");
1383}
1384
1385Value *UnaryExprAST::Codegen() {
1386 Value *OperandV = Operand-&gt;Codegen();
1387 if (OperandV == 0) return 0;
1388
1389 Function *F = TheModule-&gt;getFunction(std::string("unary")+Opcode);
1390 if (F == 0)
1391 return ErrorV("Unknown unary operator");
1392
1393 return Builder.CreateCall(F, OperandV, "unop");
1394}
1395
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1396Value *BinaryExprAST::Codegen() {
1397 Value *L = LHS-&gt;Codegen();
1398 Value *R = RHS-&gt;Codegen();
1399 if (L == 0 || R == 0) return 0;
1400
1401 switch (Op) {
Eric Christopher2214b812010-06-14 06:09:39 +0000[diff] [blame]1402 case '+': return Builder.CreateFAdd(L, R, "addtmp");
1403 case '-': return Builder.CreateFSub(L, R, "subtmp");
1404 case '*': return Builder.CreateFMul(L, R, "multmp");
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1405 case '&lt;':
Chris Lattner71155212007-11-06 01:39:12 +0000[diff] [blame]1406 L = Builder.CreateFCmpULT(L, R, "cmptmp");
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1407 // Convert bool 0/1 to double 0.0 or 1.0
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]1408 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
1409 "booltmp");
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1410 default: break;
1411 }
1412
1413 // If it wasn't a builtin binary operator, it must be a user defined one. Emit
1414 // a call to it.
1415 Function *F = TheModule-&gt;getFunction(std::string("binary")+Op);
1416 assert(F &amp;&amp; "binary operator not found!");
1417
1418 Value *Ops[] = { L, R };
1419 return Builder.CreateCall(F, Ops, Ops+2, "binop");
1420}
1421
1422Value *CallExprAST::Codegen() {
1423 // Look up the name in the global module table.
1424 Function *CalleeF = TheModule-&gt;getFunction(Callee);
1425 if (CalleeF == 0)
1426 return ErrorV("Unknown function referenced");
1427
1428 // If argument mismatch error.
1429 if (CalleeF-&gt;arg_size() != Args.size())
1430 return ErrorV("Incorrect # arguments passed");
1431
1432 std::vector&lt;Value*&gt; ArgsV;
1433 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
1434 ArgsV.push_back(Args[i]-&gt;Codegen());
1435 if (ArgsV.back() == 0) return 0;
1436 }
1437
1438 return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
1439}
1440
1441Value *IfExprAST::Codegen() {
1442 Value *CondV = Cond-&gt;Codegen();
1443 if (CondV == 0) return 0;
1444
1445 // Convert condition to a bool by comparing equal to 0.0.
1446 CondV = Builder.CreateFCmpONE(CondV,
Owen Anderson6f83c9c2009-07-27 20:59:43 +0000[diff] [blame]1447 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1448 "ifcond");
1449
1450 Function *TheFunction = Builder.GetInsertBlock()-&gt;getParent();
1451
1452 // Create blocks for the then and else cases. Insert the 'then' block at the
1453 // end of the function.
Owen Anderson1d0be152009-08-13 21:58:54 +0000[diff] [blame]1454 BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunction);
1455 BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else");
1456 BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont");
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1457
1458 Builder.CreateCondBr(CondV, ThenBB, ElseBB);
1459
1460 // Emit then value.
1461 Builder.SetInsertPoint(ThenBB);
1462
1463 Value *ThenV = Then-&gt;Codegen();
1464 if (ThenV == 0) return 0;
1465
1466 Builder.CreateBr(MergeBB);
1467 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
1468 ThenBB = Builder.GetInsertBlock();
1469
1470 // Emit else block.
1471 TheFunction-&gt;getBasicBlockList().push_back(ElseBB);
1472 Builder.SetInsertPoint(ElseBB);
1473
1474 Value *ElseV = Else-&gt;Codegen();
1475 if (ElseV == 0) return 0;
1476
1477 Builder.CreateBr(MergeBB);
1478 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
1479 ElseBB = Builder.GetInsertBlock();
1480
1481 // Emit merge block.
1482 TheFunction-&gt;getBasicBlockList().push_back(MergeBB);
1483 Builder.SetInsertPoint(MergeBB);
Jay Foad3ecfc862011-03-30 11:28:46 +0000[diff] [blame]1484 PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2,
Nick Lewycky422094c2009-09-13 21:38:54 +0000[diff] [blame]1485 "iftmp");
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1486
1487 PN-&gt;addIncoming(ThenV, ThenBB);
1488 PN-&gt;addIncoming(ElseV, ElseBB);
1489 return PN;
1490}
1491
1492Value *ForExprAST::Codegen() {
1493 // Output this as:
1494 // ...
1495 // start = startexpr
1496 // goto loop
1497 // loop:
1498 // variable = phi [start, loopheader], [nextvariable, loopend]
1499 // ...
1500 // bodyexpr
1501 // ...
1502 // loopend:
1503 // step = stepexpr
1504 // nextvariable = variable + step
1505 // endcond = endexpr
1506 // br endcond, loop, endloop
1507 // outloop:
1508
1509 // Emit the start code first, without 'variable' in scope.
1510 Value *StartVal = Start-&gt;Codegen();
1511 if (StartVal == 0) return 0;
1512
1513 // Make the new basic block for the loop header, inserting after current
1514 // block.
1515 Function *TheFunction = Builder.GetInsertBlock()-&gt;getParent();
1516 BasicBlock *PreheaderBB = Builder.GetInsertBlock();
Owen Anderson1d0be152009-08-13 21:58:54 +0000[diff] [blame]1517 BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1518
1519 // Insert an explicit fall through from the current block to the LoopBB.
1520 Builder.CreateBr(LoopBB);
1521
1522 // Start insertion in LoopBB.
1523 Builder.SetInsertPoint(LoopBB);
1524
1525 // Start the PHI node with an entry for Start.
Jay Foad3ecfc862011-03-30 11:28:46 +0000[diff] [blame]1526 PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, VarName.c_str());
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1527 Variable-&gt;addIncoming(StartVal, PreheaderBB);
1528
1529 // Within the loop, the variable is defined equal to the PHI node. If it
1530 // shadows an existing variable, we have to restore it, so save it now.
1531 Value *OldVal = NamedValues[VarName];
1532 NamedValues[VarName] = Variable;
1533
1534 // Emit the body of the loop. This, like any other expr, can change the
1535 // current BB. Note that we ignore the value computed by the body, but don't
1536 // allow an error.
1537 if (Body-&gt;Codegen() == 0)
1538 return 0;
1539
1540 // Emit the step value.
1541 Value *StepVal;
1542 if (Step) {
1543 StepVal = Step-&gt;Codegen();
1544 if (StepVal == 0) return 0;
1545 } else {
1546 // If not specified, use 1.0.
Owen Anderson6f83c9c2009-07-27 20:59:43 +0000[diff] [blame]1547 StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1548 }
1549
Chris Lattnerf57fcf72010-09-01 20:09:20 +0000[diff] [blame]1550 Value *NextVar = Builder.CreateFAdd(Variable, StepVal, "nextvar");
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1551
1552 // Compute the end condition.
1553 Value *EndCond = End-&gt;Codegen();
1554 if (EndCond == 0) return EndCond;
1555
1556 // Convert condition to a bool by comparing equal to 0.0.
1557 EndCond = Builder.CreateFCmpONE(EndCond,
Owen Anderson6f83c9c2009-07-27 20:59:43 +0000[diff] [blame]1558 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1559 "loopcond");
1560
1561 // Create the "after loop" block and insert it.
1562 BasicBlock *LoopEndBB = Builder.GetInsertBlock();
Owen Anderson1d0be152009-08-13 21:58:54 +0000[diff] [blame]1563 BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1564
1565 // Insert the conditional branch into the end of LoopEndBB.
1566 Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
1567
1568 // Any new code will be inserted in AfterBB.
1569 Builder.SetInsertPoint(AfterBB);
1570
1571 // Add a new entry to the PHI node for the backedge.
1572 Variable-&gt;addIncoming(NextVar, LoopEndBB);
1573
1574 // Restore the unshadowed variable.
1575 if (OldVal)
1576 NamedValues[VarName] = OldVal;
1577 else
1578 NamedValues.erase(VarName);
1579
1580
1581 // for expr always returns 0.0.
Owen Anderson1d0be152009-08-13 21:58:54 +0000[diff] [blame]1582 return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1583}
1584
1585Function *PrototypeAST::Codegen() {
1586 // Make the function type: double(double,double) etc.
Nick Lewycky422094c2009-09-13 21:38:54 +0000[diff] [blame]1587 std::vector&lt;const Type*&gt; Doubles(Args.size(),
1588 Type::getDoubleTy(getGlobalContext()));
1589 FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()),
1590 Doubles, false);
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1591
Gabor Greifdf7d2b42008-04-19 22:25:09 +0000[diff] [blame]1592 Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1593
1594 // If F conflicted, there was already something named 'Name'. If it has a
1595 // body, don't allow redefinition or reextern.
1596 if (F-&gt;getName() != Name) {
1597 // Delete the one we just made and get the existing one.
1598 F-&gt;eraseFromParent();
1599 F = TheModule-&gt;getFunction(Name);
1600
1601 // If F already has a body, reject this.
1602 if (!F-&gt;empty()) {
1603 ErrorF("redefinition of function");
1604 return 0;
1605 }
1606
1607 // If F took a different number of args, reject.
1608 if (F-&gt;arg_size() != Args.size()) {
1609 ErrorF("redefinition of function with different # args");
1610 return 0;
1611 }
1612 }
1613
1614 // Set names for all arguments.
1615 unsigned Idx = 0;
1616 for (Function::arg_iterator AI = F-&gt;arg_begin(); Idx != Args.size();
1617 ++AI, ++Idx) {
1618 AI-&gt;setName(Args[Idx]);
1619
1620 // Add arguments to variable symbol table.
1621 NamedValues[Args[Idx]] = AI;
1622 }
1623
1624 return F;
1625}
1626
1627Function *FunctionAST::Codegen() {
1628 NamedValues.clear();
1629
1630 Function *TheFunction = Proto-&gt;Codegen();
1631 if (TheFunction == 0)
1632 return 0;
1633
1634 // If this is an operator, install it.
1635 if (Proto-&gt;isBinaryOp())
1636 BinopPrecedence[Proto-&gt;getOperatorName()] = Proto-&gt;getBinaryPrecedence();
1637
1638 // Create a new basic block to start insertion into.
Owen Anderson1d0be152009-08-13 21:58:54 +0000[diff] [blame]1639 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1640 Builder.SetInsertPoint(BB);
1641
1642 if (Value *RetVal = Body-&gt;Codegen()) {
1643 // Finish off the function.
1644 Builder.CreateRet(RetVal);
1645
1646 // Validate the generated code, checking for consistency.
1647 verifyFunction(*TheFunction);
1648
1649 // Optimize the function.
1650 TheFPM-&gt;run(*TheFunction);
1651
1652 return TheFunction;
1653 }
1654
1655 // Error reading body, remove function.
1656 TheFunction-&gt;eraseFromParent();
1657
1658 if (Proto-&gt;isBinaryOp())
1659 BinopPrecedence.erase(Proto-&gt;getOperatorName());
1660 return 0;
1661}
1662
1663//===----------------------------------------------------------------------===//
1664// Top-Level parsing and JIT Driver
1665//===----------------------------------------------------------------------===//
1666
1667static ExecutionEngine *TheExecutionEngine;
1668
1669static void HandleDefinition() {
1670 if (FunctionAST *F = ParseDefinition()) {
1671 if (Function *LF = F-&gt;Codegen()) {
1672 fprintf(stderr, "Read function definition:");
1673 LF-&gt;dump();
1674 }
1675 } else {
1676 // Skip token for error recovery.
1677 getNextToken();
1678 }
1679}
1680
1681static void HandleExtern() {
1682 if (PrototypeAST *P = ParseExtern()) {
1683 if (Function *F = P-&gt;Codegen()) {
1684 fprintf(stderr, "Read extern: ");
1685 F-&gt;dump();
1686 }
1687 } else {
1688 // Skip token for error recovery.
1689 getNextToken();
1690 }
1691}
1692
1693static void HandleTopLevelExpression() {
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]1694 // Evaluate a top-level expression into an anonymous function.
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1695 if (FunctionAST *F = ParseTopLevelExpr()) {
1696 if (Function *LF = F-&gt;Codegen()) {
1697 // JIT the function, returning a function pointer.
1698 void *FPtr = TheExecutionEngine-&gt;getPointerToFunction(LF);
1699
1700 // Cast it to the right type (takes no arguments, returns a double) so we
1701 // can call it as a native function.
Nick Lewycky422094c2009-09-13 21:38:54 +0000[diff] [blame]1702 double (*FP)() = (double (*)())(intptr_t)FPtr;
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1703 fprintf(stderr, "Evaluated to %f\n", FP());
1704 }
1705 } else {
1706 // Skip token for error recovery.
1707 getNextToken();
1708 }
1709}
1710
1711/// top ::= definition | external | expression | ';'
1712static void MainLoop() {
1713 while (1) {
1714 fprintf(stderr, "ready&gt; ");
1715 switch (CurTok) {
1716 case tok_eof: return;
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]1717 case ';': getNextToken(); break; // ignore top-level semicolons.
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1718 case tok_def: HandleDefinition(); break;
1719 case tok_extern: HandleExtern(); break;
1720 default: HandleTopLevelExpression(); break;
1721 }
1722 }
1723}
1724
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1725//===----------------------------------------------------------------------===//
1726// "Library" functions that can be "extern'd" from user code.
1727//===----------------------------------------------------------------------===//
1728
1729/// putchard - putchar that takes a double and returns 0.
1730extern "C"
1731double putchard(double X) {
1732 putchar((char)X);
1733 return 0;
1734}
1735
1736/// printd - printf that takes a double prints it as "%f\n", returning 0.
1737extern "C"
1738double printd(double X) {
1739 printf("%f\n", X);
1740 return 0;
1741}
1742
1743//===----------------------------------------------------------------------===//
1744// Main driver code.
1745//===----------------------------------------------------------------------===//
1746
1747int main() {
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]1748 InitializeNativeTarget();
1749 LLVMContext &amp;Context = getGlobalContext();
1750
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1751 // Install standard binary operators.
1752 // 1 is lowest precedence.
1753 BinopPrecedence['&lt;'] = 10;
1754 BinopPrecedence['+'] = 20;
1755 BinopPrecedence['-'] = 20;
1756 BinopPrecedence['*'] = 40; // highest.
1757
1758 // Prime the first token.
1759 fprintf(stderr, "ready&gt; ");
1760 getNextToken();
1761
1762 // Make the module, which holds all the code.
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]1763 TheModule = new Module("my cool jit", Context);
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1764
Jeffrey Yasskinf0356fe2010-01-27 20:34:15 +0000[diff] [blame]1765 // Create the JIT. This takes ownership of the module.
Jeffrey Yasskin42fc5582010-02-11 19:15:20 +0000[diff] [blame]1766 std::string ErrStr;
NAKAMURA Takumi4d6deb02011-04-09 09:51:57 +0000[diff] [blame]1767 TheExecutionEngine = EngineBuilder(TheModule).setErrorStr(&amp;ErrStr).create();
Jeffrey Yasskin42fc5582010-02-11 19:15:20 +0000[diff] [blame]1768 if (!TheExecutionEngine) {
1769 fprintf(stderr, "Could not create ExecutionEngine: %s\n", ErrStr.c_str());
1770 exit(1);
1771 }
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1772
Jeffrey Yasskinf0356fe2010-01-27 20:34:15 +0000[diff] [blame]1773 FunctionPassManager OurFPM(TheModule);
Reid Kleckner60130f02009-08-26 20:58:25 +0000[diff] [blame]1774
1775 // Set up the optimizer pipeline. Start with registering info about how the
1776 // target lays out data structures.
1777 OurFPM.add(new TargetData(*TheExecutionEngine-&gt;getTargetData()));
Dan Gohmandfa1a792010-11-15 18:41:10 +0000[diff] [blame]1778 // Provide basic AliasAnalysis support for GVN.
1779 OurFPM.add(createBasicAliasAnalysisPass());
Reid Kleckner60130f02009-08-26 20:58:25 +0000[diff] [blame]1780 // Do simple "peephole" optimizations and bit-twiddling optzns.
1781 OurFPM.add(createInstructionCombiningPass());
1782 // Reassociate expressions.
1783 OurFPM.add(createReassociatePass());
1784 // Eliminate Common SubExpressions.
1785 OurFPM.add(createGVNPass());
1786 // Simplify the control flow graph (deleting unreachable blocks, etc).
1787 OurFPM.add(createCFGSimplificationPass());
1788
Nick Lewycky422094c2009-09-13 21:38:54 +0000[diff] [blame]1789 OurFPM.doInitialization();
1790
Reid Kleckner60130f02009-08-26 20:58:25 +0000[diff] [blame]1791 // Set the global so the code gen can use this.
1792 TheFPM = &amp;OurFPM;
1793
1794 // Run the main "interpreter loop" now.
1795 MainLoop();
1796
1797 TheFPM = 0;
1798
1799 // Print out all of the generated code.
1800 TheModule-&gt;dump();
1801
Chris Lattner58f2c872007-11-02 05:42:52 +0000[diff] [blame]1802 return 0;
1803}
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]1804</pre>
1805</div>
1806
Chris Lattner729eb142008-02-10 19:11:04 +0000[diff] [blame]1807<a href="LangImpl7.html">Next: Extending the language: mutable variables / SSA construction</a>
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]1808</div>
1809
1810<!-- *********************************************************************** -->
1811<hr>
1812<address>
1813 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
1814 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
1815 <a href="http://validator.w3.org/check/referer"><img
1816 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
1817
1818 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
NAKAMURA Takumib9a33632011-04-09 02:13:37 +0000[diff] [blame]1819 <a href="http://llvm.org/">The LLVM Compiler Infrastructure</a><br>
Dan Gohman523e3922010-02-03 17:27:31 +0000[diff] [blame]1820 Last modified: $Date$
Chris Lattnerc9d5d2c2007-11-01 06:49:54 +0000[diff] [blame]1821</address>
1822</body>
1823</html>