Gitiles
Code Review Sign In
gerrit-public.fairphone.software / fp2-dev / platform / external / llvm / d3f0cddb62ccab81115f587bc2d3195fd307b2ed / . / docs / tutorial / LangImpl3.html
blob: 020cf925d9cc13020759cf36451706c13304fc88 [file] [log] [blame]
Chris Lattner2e902042007-10-22 07:01:42 +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>
6 <title>Kaleidoscope: Implementing code generation to LLVM IR</title>
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
14<div class="doc_title">Kaleidoscope: Code generation to LLVM IR</div>
15
16<div class="doc_author">
17 <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p>
18</div>
19
20<!-- *********************************************************************** -->
21<div class="doc_section"><a name="intro">Part 3 Introduction</a></div>
22<!-- *********************************************************************** -->
23
24<div class="doc_text">
25
26<p>Welcome to part 3 of the "<a href="index.html">Implementing a language with
27LLVM</a>" tutorial. This chapter shows you how to transform the <a
28href="LangImpl2.html">Abstract Syntax Tree built in Chapter 2</a> into LLVM IR.
29This will teach you a little bit about how LLVM does things, as well as
30demonstrate how easy it is to use. It's much more work to build a lexer and
31parser than it is to generate LLVM IR code.
32</p>
33
34</div>
35
36<!-- *********************************************************************** -->
37<div class="doc_section"><a name="basics">Code Generation setup</a></div>
38<!-- *********************************************************************** -->
39
40<div class="doc_text">
41
42<p>
43In order to generate LLVM IR, we want some simple setup to get started. First,
44we define virtual codegen methods in each AST class:</p>
45
46<div class="doc_code">
47<pre>
48/// ExprAST - Base class for all expression nodes.
49class ExprAST {
50public:
51 virtual ~ExprAST() {}
52 virtual Value *Codegen() = 0;
53};
54
55/// NumberExprAST - Expression class for numeric literals like "1.0".
56class NumberExprAST : public ExprAST {
57 double Val;
58public:
Chris Lattner28571ed2007-10-23 04:27:44 +0000[diff] [blame]59 explicit NumberExprAST(double val) : Val(val) {}
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]60 virtual Value *Codegen();
61};
62...
63</pre>
64</div>
65
Chris Lattner28571ed2007-10-23 04:27:44 +0000[diff] [blame]66<p>The Codegen() method says to emit IR for that AST node and all things it
67depends on, and they all return an LLVM Value object.
68"Value" is the class used to represent a "<a
69href="http://en.wikipedia.org/wiki/Static_single_assignment_form">Static Single
70Assignment (SSA)</a> register" or "SSA value" in LLVM. The most distinct aspect
71of SSA values is that their value is computed as the related instruction
72executes, and it does not get a new value until (and if) the instruction
73re-executes. In order words, there is no way to "change" an SSA value. For
74more information, please read up on <a
75href="http://en.wikipedia.org/wiki/Static_single_assignment_form">Static Single
76Assignment</a> - the concepts are really quite natural once you grok them.</p>
77
78<p>The
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]79second thing we want is an "Error" method like we used for parser, which will
80be used to report errors found during code generation (for example, use of an
81undeclared parameter):</p>
82
83<div class="doc_code">
84<pre>
85Value *ErrorV(const char *Str) { Error(Str); return 0; }
86
87static Module *TheModule;
88static LLVMBuilder Builder;
89static std::map&lt;std::string, Value*&gt; NamedValues;
90</pre>
91</div>
92
93<p>The static variables will be used during code generation. <tt>TheModule</tt>
94is the LLVM construct that contains all of the functions and global variables in
95a chunk of code. In many ways, it is the top-level structure that the LLVM IR
96uses to contain code.</p>
97
98<p>The <tt>Builder</tt> object is a helper object that makes it easy to generate
99LLVM instructions. The <tt>Builder</tt> keeps track of the current place to
100insert instructions and has methods to create new instructions.</p>
101
102<p>The <tt>NamedValues</tt> map keeps track of which values are defined in the
103current scope and what their LLVM representation is. In this form of
104Kaleidoscope, the only things that can be referenced are function parameters.
105As such, function parameters will be in this map when generating code for their
106function body.</p>
107
108<p>
109With these basics in place, we can start talking about how to generate code for
110each expression. Note that this assumes that the <tt>Builder</tt> has been set
111up to generate code <em>into</em> something. For now, we'll assume that this
112has already been done, and we'll just use it to emit code.
113</p>
114
115</div>
116
117<!-- *********************************************************************** -->
118<div class="doc_section"><a name="exprs">Expression Code Generation</a></div>
119<!-- *********************************************************************** -->
120
121<div class="doc_text">
122
123<p>Generating LLVM code for expression nodes is very straight-forward: less
124than 45 lines of commented code for all four of our expression nodes. First,
125we'll do numeric literals:</p>
126
127<div class="doc_code">
128<pre>
129Value *NumberExprAST::Codegen() {
130 return ConstantFP::get(Type::DoubleTy, APFloat(Val));
131}
132</pre>
133</div>
134
Chris Lattnerd3f0cdd2007-10-23 04:51:30 +0000[diff] [blame^]135<p>In the LLVM IR, numeric constants are represented with the
136<tt>ConstantFP</tt> class, which holds the numeric value in an <tt>APFloat</tt>
137internally (<tt>APFloat</tt> has the capability of holding floating point
138constants of <em>A</em>rbitrary <em>P</em>recision). This code basically just
139creates and returns a <tt>ConstantFP</tt>. Note that in the LLVM IR
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]140that constants are all uniqued together and shared. For this reason, the API
Chris Lattnerd3f0cdd2007-10-23 04:51:30 +0000[diff] [blame^]141uses "the foo::get(..)" idiom instead of "new foo(..)" or "foo::create(..).</p>
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]142
143<div class="doc_code">
144<pre>
145Value *VariableExprAST::Codegen() {
146 // Look this variable up in the function.
147 Value *V = NamedValues[Name];
148 return V ? V : ErrorV("Unknown variable name");
149}
150</pre>
151</div>
152
Chris Lattnerd3f0cdd2007-10-23 04:51:30 +0000[diff] [blame^]153<p>References to variables is also quite simple here. In the simple version
154of Kaleidoscope, we assume that the variable has already been emited somewhere
155and its value is available. In practice, the only values that can be in the
156<tt>NamedValues</tt> map are function arguments. This
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]157code simply checks to see that the specified name is in the map (if not, an
158unknown variable is being referenced) and returns the value for it.</p>
159
160<div class="doc_code">
161<pre>
162Value *BinaryExprAST::Codegen() {
163 Value *L = LHS-&gt;Codegen();
164 Value *R = RHS-&gt;Codegen();
165 if (L == 0 || R == 0) return 0;
166
167 switch (Op) {
168 case '+': return Builder.CreateAdd(L, R, "addtmp");
169 case '-': return Builder.CreateSub(L, R, "subtmp");
170 case '*': return Builder.CreateMul(L, R, "multmp");
171 case '&lt;':
172 L = Builder.CreateFCmpULT(L, R, "multmp");
173 // Convert bool 0/1 to double 0.0 or 1.0
174 return Builder.CreateUIToFP(L, Type::DoubleTy, "booltmp");
175 default: return ErrorV("invalid binary operator");
176 }
177}
178</pre>
179</div>
180
Chris Lattnerd3f0cdd2007-10-23 04:51:30 +0000[diff] [blame^]181<p>Binary operators start to get more interesting. The basic idea here is that
182we recursively emit code for the left-hand side of the expression, then the
183right-hand side, then we compute the result of the binary expression. In this
184code, we do a simple switch on the opcode to create the right LLVM instruction.
185</p>
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]186
Chris Lattnerd3f0cdd2007-10-23 04:51:30 +0000[diff] [blame^]187<p>In this example, the LLVM builder class is starting to show its value.
188Because it knows where to insert the newly created instruction, you just have to
189specificy what instruction to create (e.g. with <tt>CreateAdd</tt>), which
190operands to use (<tt>L</tt> and <tt>R</tt> here) and optionally provide a name
191for the generated instruction. One nice thing about LLVM is that the name is
192just a hint: if there are multiple additions in a single function, the first
193will be named "addtmp" and the second will be "autorenamed" by adding a suffix,
194giving it a name like "addtmp42". Local value names for instructions are purely
195optional, but it makes it much easier to read the IR dumps.</p>
196
197<p><a href="../LangRef.html#instref">LLVM instructions</a> are constrained to
198have very strict type properties: for example, the Left and Right operators of
199an <a href="../LangRef.html#i_add">add instruction</a> have to have the same
200type, and that the result of the add matches the operands. Because all values
201in Kaleidoscope are doubles, this makes for very simple code for add, sub and
202mul.</p>
203
204<p>On the other hand, LLVM specifies that the <a
205href="../LangRef.html#i_fcmp">fcmp instruction</a> always returns an 'i1' value
206(a one bit integer). However, Kaleidoscope wants the value to be a 0.0 or 1.0
207value. In order to get these semantics, we combine the fcmp instruction with
208a <a href="../LangRef.html#i_uitofp">uitofp instruction</a>. This instruction
209converts its input integer into a floating point value by treating the input
210as an unsigned value. In contrast, if we used the <a
211href="../LangRef.html#i_sitofp">sitofp instruction</a>, the Kaleidoscope '<'
212operator would return 0.0 and -1.0, depending on the input value.</p>
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]213
214<div class="doc_code">
215<pre>
216Value *CallExprAST::Codegen() {
217 // Look up the name in the global module table.
218 Function *CalleeF = TheModule-&gt;getFunction(Callee);
219 if (CalleeF == 0)
220 return ErrorV("Unknown function referenced");
221
222 // If argument mismatch error.
223 if (CalleeF-&gt;arg_size() != Args.size())
224 return ErrorV("Incorrect # arguments passed");
225
226 std::vector&lt;Value*&gt; ArgsV;
227 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
228 ArgsV.push_back(Args[i]-&gt;Codegen());
229 if (ArgsV.back() == 0) return 0;
230 }
231
232 return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
233}
234</pre>
235</div>
236
Chris Lattnerd3f0cdd2007-10-23 04:51:30 +0000[diff] [blame^]237<p>Code generation for function calls is quite straight-forward with LLVM. The
238code above first looks the name of the function up in the LLVM Module's symbol
239table. Recall that the LLVM Module is the container that holds all of the
240functions we are JIT'ing. By giving each function the same name as what the
241user specifies, we can use the LLVM symbol table to resolve function names for
242us.</p>
243
244<p>Once we have the function to call, we recursively codegen each argument that
245is to be passed in, and create an LLVM <a href="../LangRef.html#i_call">call
246instruction</a>. Note that LLVM uses the native C calling conventions by
247default, allowing these calls to call into standard library functions like
248"sin" and "cos" with no additional effort.</p>
249
250<p>This wraps up our handling of the four basic expressions that we have so far
251in Kaleidoscope. Feel free to go in and add some more. For example, by
252browsing the <a href="../LangRef.html">LLVM language reference</a> you'll find
253several other interesting instructions that are really easy to plug into our
254basic framework.</p>
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]255
256</div>
257
258<!-- *********************************************************************** -->
259<div class="doc_section"><a name="code">Conclusions and the Full Code</a></div>
260<!-- *********************************************************************** -->
261
262<div class="doc_text">
263
264<div class="doc_code">
265<pre>
266// To build this:
267// g++ -g toy.cpp `llvm-config --cppflags` `llvm-config --ldflags` \
268// `llvm-config --libs core` -I ~/llvm/include/
269// ./a.out
270// See example below.
271
272#include "llvm/DerivedTypes.h"
273#include "llvm/Module.h"
274#include "llvm/Support/LLVMBuilder.h"
275#include &lt;cstdio&gt;
276#include &lt;string&gt;
277#include &lt;map&gt;
278#include &lt;vector&gt;
279using namespace llvm;
280
281//===----------------------------------------------------------------------===//
282// Lexer
283//===----------------------------------------------------------------------===//
284
285// The lexer returns tokens [0-255] if it is an unknown character, otherwise one
286// of these for known things.
287enum Token {
288 tok_eof = -1,
289
290 // commands
291 tok_def = -2, tok_extern = -3,
292
293 // primary
294 tok_identifier = -4, tok_number = -5,
295};
296
297static std::string IdentifierStr; // Filled in if tok_identifier
298static double NumVal; // Filled in if tok_number
299
300/// gettok - Return the next token from standard input.
301static int gettok() {
302 static int LastChar = ' ';
303
304 // Skip any whitespace.
305 while (isspace(LastChar))
306 LastChar = getchar();
307
308 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
309 IdentifierStr = LastChar;
310 while (isalnum((LastChar = getchar())))
311 IdentifierStr += LastChar;
312
313 if (IdentifierStr == "def") return tok_def;
314 if (IdentifierStr == "extern") return tok_extern;
315 return tok_identifier;
316 }
317
318 if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+
319 std::string NumStr;
320 do {
321 NumStr += LastChar;
322 LastChar = getchar();
323 } while (isdigit(LastChar) || LastChar == '.');
324
325 NumVal = strtod(NumStr.c_str(), 0);
326 return tok_number;
327 }
328
329 if (LastChar == '#') {
330 // Comment until end of line.
331 do LastChar = getchar();
332 while (LastChar != EOF &amp;&amp; LastChar != '\n' &amp; LastChar != '\r');
333
334 if (LastChar != EOF)
335 return gettok();
336 }
337
338 // Check for end of file. Don't eat the EOF.
339 if (LastChar == EOF)
340 return tok_eof;
341
342 // Otherwise, just return the character as its ascii value.
343 int ThisChar = LastChar;
344 LastChar = getchar();
345 return ThisChar;
346}
347
348//===----------------------------------------------------------------------===//
349// Abstract Syntax Tree (aka Parse Tree)
350//===----------------------------------------------------------------------===//
351
352/// ExprAST - Base class for all expression nodes.
353class ExprAST {
354public:
355 virtual ~ExprAST() {}
356 virtual Value *Codegen() = 0;
357};
358
359/// NumberExprAST - Expression class for numeric literals like "1.0".
360class NumberExprAST : public ExprAST {
361 double Val;
362public:
Chris Lattner28571ed2007-10-23 04:27:44 +0000[diff] [blame]363 explicit NumberExprAST(double val) : Val(val) {}
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]364 virtual Value *Codegen();
365};
366
367/// VariableExprAST - Expression class for referencing a variable, like "a".
368class VariableExprAST : public ExprAST {
369 std::string Name;
370public:
Chris Lattner28571ed2007-10-23 04:27:44 +0000[diff] [blame]371 explicit VariableExprAST(const std::string &amp;name) : Name(name) {}
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]372 virtual Value *Codegen();
373};
374
375/// BinaryExprAST - Expression class for a binary operator.
376class BinaryExprAST : public ExprAST {
377 char Op;
378 ExprAST *LHS, *RHS;
379public:
380 BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
381 : Op(op), LHS(lhs), RHS(rhs) {}
382 virtual Value *Codegen();
383};
384
385/// CallExprAST - Expression class for function calls.
386class CallExprAST : public ExprAST {
387 std::string Callee;
388 std::vector&lt;ExprAST*&gt; Args;
389public:
390 CallExprAST(const std::string &amp;callee, std::vector&lt;ExprAST*&gt; &amp;args)
391 : Callee(callee), Args(args) {}
392 virtual Value *Codegen();
393};
394
395/// PrototypeAST - This class represents the "prototype" for a function,
396/// which captures its argument names as well as if it is an operator.
397class PrototypeAST {
398 std::string Name;
399 std::vector&lt;std::string&gt; Args;
400public:
401 PrototypeAST(const std::string &amp;name, const std::vector&lt;std::string&gt; &amp;args)
402 : Name(name), Args(args) {}
403
404 Function *Codegen();
405};
406
407/// FunctionAST - This class represents a function definition itself.
408class FunctionAST {
409 PrototypeAST *Proto;
410 ExprAST *Body;
411public:
412 FunctionAST(PrototypeAST *proto, ExprAST *body)
413 : Proto(proto), Body(body) {}
414
415 Function *Codegen();
416};
417
418//===----------------------------------------------------------------------===//
419// Parser
420//===----------------------------------------------------------------------===//
421
422/// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
423/// token the parser it looking at. getNextToken reads another token from the
424/// lexer and updates CurTok with its results.
425static int CurTok;
426static int getNextToken() {
427 return CurTok = gettok();
428}
429
430/// BinopPrecedence - This holds the precedence for each binary operator that is
431/// defined.
432static std::map&lt;char, int&gt; BinopPrecedence;
433
434/// GetTokPrecedence - Get the precedence of the pending binary operator token.
435static int GetTokPrecedence() {
436 if (!isascii(CurTok))
437 return -1;
438
439 // Make sure it's a declared binop.
440 int TokPrec = BinopPrecedence[CurTok];
441 if (TokPrec &lt;= 0) return -1;
442 return TokPrec;
443}
444
445/// Error* - These are little helper functions for error handling.
446ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
447PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
448FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
449
450static ExprAST *ParseExpression();
451
452/// identifierexpr
453/// ::= identifer
454/// ::= identifer '(' expression* ')'
455static ExprAST *ParseIdentifierExpr() {
456 std::string IdName = IdentifierStr;
457
458 getNextToken(); // eat identifer.
459
460 if (CurTok != '(') // Simple variable ref.
461 return new VariableExprAST(IdName);
462
463 // Call.
464 getNextToken(); // eat (
465 std::vector&lt;ExprAST*&gt; Args;
466 while (1) {
467 ExprAST *Arg = ParseExpression();
468 if (!Arg) return 0;
469 Args.push_back(Arg);
470
471 if (CurTok == ')') break;
472
473 if (CurTok != ',')
474 return Error("Expected ')'");
475 getNextToken();
476 }
477
478 // Eat the ')'.
479 getNextToken();
480
481 return new CallExprAST(IdName, Args);
482}
483
484/// numberexpr ::= number
485static ExprAST *ParseNumberExpr() {
486 ExprAST *Result = new NumberExprAST(NumVal);
487 getNextToken(); // consume the number
488 return Result;
489}
490
491/// parenexpr ::= '(' expression ')'
492static ExprAST *ParseParenExpr() {
493 getNextToken(); // eat (.
494 ExprAST *V = ParseExpression();
495 if (!V) return 0;
496
497 if (CurTok != ')')
498 return Error("expected ')'");
499 getNextToken(); // eat ).
500 return V;
501}
502
503/// primary
504/// ::= identifierexpr
505/// ::= numberexpr
506/// ::= parenexpr
507static ExprAST *ParsePrimary() {
508 switch (CurTok) {
509 default: return Error("unknown token when expecting an expression");
510 case tok_identifier: return ParseIdentifierExpr();
511 case tok_number: return ParseNumberExpr();
512 case '(': return ParseParenExpr();
513 }
514}
515
516/// binoprhs
517/// ::= ('+' primary)*
518static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
519 // If this is a binop, find its precedence.
520 while (1) {
521 int TokPrec = GetTokPrecedence();
522
523 // If this is a binop that binds at least as tightly as the current binop,
524 // consume it, otherwise we are done.
525 if (TokPrec &lt; ExprPrec)
526 return LHS;
527
528 // Okay, we know this is a binop.
529 int BinOp = CurTok;
530 getNextToken(); // eat binop
531
532 // Parse the primary expression after the binary operator.
533 ExprAST *RHS = ParsePrimary();
534 if (!RHS) return 0;
535
536 // If BinOp binds less tightly with RHS than the operator after RHS, let
537 // the pending operator take RHS as its LHS.
538 int NextPrec = GetTokPrecedence();
539 if (TokPrec &lt; NextPrec) {
540 RHS = ParseBinOpRHS(TokPrec+1, RHS);
541 if (RHS == 0) return 0;
542 }
543
544 // Merge LHS/RHS.
545 LHS = new BinaryExprAST(BinOp, LHS, RHS);
546 }
547}
548
549/// expression
550/// ::= primary binoprhs
551///
552static ExprAST *ParseExpression() {
553 ExprAST *LHS = ParsePrimary();
554 if (!LHS) return 0;
555
556 return ParseBinOpRHS(0, LHS);
557}
558
559/// prototype
560/// ::= id '(' id* ')'
561static PrototypeAST *ParsePrototype() {
562 if (CurTok != tok_identifier)
563 return ErrorP("Expected function name in prototype");
564
565 std::string FnName = IdentifierStr;
566 getNextToken();
567
568 if (CurTok != '(')
569 return ErrorP("Expected '(' in prototype");
570
571 std::vector&lt;std::string&gt; ArgNames;
572 while (getNextToken() == tok_identifier)
573 ArgNames.push_back(IdentifierStr);
574 if (CurTok != ')')
575 return ErrorP("Expected ')' in prototype");
576
577 // success.
578 getNextToken(); // eat ')'.
579
580 return new PrototypeAST(FnName, ArgNames);
581}
582
583/// definition ::= 'def' prototype expression
584static FunctionAST *ParseDefinition() {
585 getNextToken(); // eat def.
586 PrototypeAST *Proto = ParsePrototype();
587 if (Proto == 0) return 0;
588
589 if (ExprAST *E = ParseExpression())
590 return new FunctionAST(Proto, E);
591 return 0;
592}
593
594/// toplevelexpr ::= expression
595static FunctionAST *ParseTopLevelExpr() {
596 if (ExprAST *E = ParseExpression()) {
597 // Make an anonymous proto.
598 PrototypeAST *Proto = new PrototypeAST("", std::vector&lt;std::string&gt;());
599 return new FunctionAST(Proto, E);
600 }
601 return 0;
602}
603
604/// external ::= 'extern' prototype
605static PrototypeAST *ParseExtern() {
606 getNextToken(); // eat extern.
607 return ParsePrototype();
608}
609
610//===----------------------------------------------------------------------===//
611// Code Generation
612//===----------------------------------------------------------------------===//
613
614static Module *TheModule;
615static LLVMBuilder Builder;
616static std::map&lt;std::string, Value*&gt; NamedValues;
617
618Value *ErrorV(const char *Str) { Error(Str); return 0; }
619
620Value *NumberExprAST::Codegen() {
621 return ConstantFP::get(Type::DoubleTy, APFloat(Val));
622}
623
624Value *VariableExprAST::Codegen() {
625 // Look this variable up in the function.
626 Value *V = NamedValues[Name];
627 return V ? V : ErrorV("Unknown variable name");
628}
629
630Value *BinaryExprAST::Codegen() {
631 Value *L = LHS-&gt;Codegen();
632 Value *R = RHS-&gt;Codegen();
633 if (L == 0 || R == 0) return 0;
634
635 switch (Op) {
636 case '+': return Builder.CreateAdd(L, R, "addtmp");
637 case '-': return Builder.CreateSub(L, R, "subtmp");
638 case '*': return Builder.CreateMul(L, R, "multmp");
639 case '&lt;':
640 L = Builder.CreateFCmpULT(L, R, "multmp");
641 // Convert bool 0/1 to double 0.0 or 1.0
642 return Builder.CreateUIToFP(L, Type::DoubleTy, "booltmp");
643 default: return ErrorV("invalid binary operator");
644 }
645}
646
647Value *CallExprAST::Codegen() {
648 // Look up the name in the global module table.
649 Function *CalleeF = TheModule-&gt;getFunction(Callee);
650 if (CalleeF == 0)
651 return ErrorV("Unknown function referenced");
652
653 // If argument mismatch error.
654 if (CalleeF-&gt;arg_size() != Args.size())
655 return ErrorV("Incorrect # arguments passed");
656
657 std::vector&lt;Value*&gt; ArgsV;
658 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
659 ArgsV.push_back(Args[i]-&gt;Codegen());
660 if (ArgsV.back() == 0) return 0;
661 }
662
663 return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
664}
665
666Function *PrototypeAST::Codegen() {
667 // Make the function type: double(double,double) etc.
668 FunctionType *FT =
669 FunctionType::get(Type::DoubleTy, std::vector&lt;const Type*&gt;(Args.size(),
670 Type::DoubleTy),
671 false);
672
673 Function *F = new Function(FT, Function::ExternalLinkage, Name, TheModule);
674
675 // If F conflicted, there was already something named 'Name'. If it has a
676 // body, don't allow redefinition or reextern.
677 if (F-&gt;getName() != Name) {
678 // Delete the one we just made and get the existing one.
679 F-&gt;eraseFromParent();
680 F = TheModule-&gt;getFunction(Name);
681
682 // If F already has a body, reject this.
683 if (!F-&gt;empty()) {
684 ErrorF("redefinition of function");
685 return 0;
686 }
687
688 // If F took a different number of args, reject.
689 if (F-&gt;arg_size() != Args.size()) {
690 ErrorF("redefinition of function with different # args");
691 return 0;
692 }
693 }
694
695 // Set names for all arguments.
696 unsigned Idx = 0;
697 for (Function::arg_iterator AI = F-&gt;arg_begin(); Idx != Args.size();
698 ++AI, ++Idx) {
699 AI-&gt;setName(Args[Idx]);
700
701 // Add arguments to variable symbol table.
702 NamedValues[Args[Idx]] = AI;
703 }
704
705 return F;
706}
707
708Function *FunctionAST::Codegen() {
709 NamedValues.clear();
710
711 Function *TheFunction = Proto-&gt;Codegen();
712 if (TheFunction == 0)
713 return 0;
714
715 // Create a new basic block to start insertion into.
716 Builder.SetInsertPoint(new BasicBlock("entry", TheFunction));
717
718 if (Value *RetVal = Body-&gt;Codegen()) {
719 // Finish off the function.
720 Builder.CreateRet(RetVal);
721 return TheFunction;
722 }
723
724 // Error reading body, remove function.
725 TheFunction-&gt;eraseFromParent();
726 return 0;
727}
728
729//===----------------------------------------------------------------------===//
730// Top-Level parsing and JIT Driver
731//===----------------------------------------------------------------------===//
732
733static void HandleDefinition() {
734 if (FunctionAST *F = ParseDefinition()) {
735 if (Function *LF = F-&gt;Codegen()) {
736 fprintf(stderr, "Read function definition:");
737 LF-&gt;dump();
738 }
739 } else {
740 // Skip token for error recovery.
741 getNextToken();
742 }
743}
744
745static void HandleExtern() {
746 if (PrototypeAST *P = ParseExtern()) {
747 if (Function *F = P-&gt;Codegen()) {
748 fprintf(stderr, "Read extern: ");
749 F-&gt;dump();
750 }
751 } else {
752 // Skip token for error recovery.
753 getNextToken();
754 }
755}
756
757static void HandleTopLevelExpression() {
758 // Evaluate a top level expression into an anonymous function.
759 if (FunctionAST *F = ParseTopLevelExpr()) {
760 if (Function *LF = F-&gt;Codegen()) {
761 fprintf(stderr, "Read top-level expression:");
762 LF-&gt;dump();
763 }
764 } else {
765 // Skip token for error recovery.
766 getNextToken();
767 }
768}
769
770/// top ::= definition | external | expression | ';'
771static void MainLoop() {
772 while (1) {
773 fprintf(stderr, "ready&gt; ");
774 switch (CurTok) {
775 case tok_eof: return;
776 case ';': getNextToken(); break; // ignore top level semicolons.
777 case tok_def: HandleDefinition(); break;
778 case tok_extern: HandleExtern(); break;
779 default: HandleTopLevelExpression(); break;
780 }
781 }
782}
783
784
785
786//===----------------------------------------------------------------------===//
787// "Library" functions that can be "extern'd" from user code.
788//===----------------------------------------------------------------------===//
789
790/// putchard - putchar that takes a double and returns 0.
791extern "C"
792double putchard(double X) {
793 putchar((char)X);
794 return 0;
795}
796
797//===----------------------------------------------------------------------===//
798// Main driver code.
799//===----------------------------------------------------------------------===//
800
801int main() {
802 TheModule = new Module("my cool jit");
803
804 // Install standard binary operators.
805 // 1 is lowest precedence.
806 BinopPrecedence['&lt;'] = 10;
807 BinopPrecedence['+'] = 20;
808 BinopPrecedence['-'] = 20;
809 BinopPrecedence['*'] = 40; // highest.
810
811 // Prime the first token.
812 fprintf(stderr, "ready&gt; ");
813 getNextToken();
814
815 MainLoop();
816 TheModule-&gt;dump();
817 return 0;
818}
819
820/* Examples:
821
822def fib(x)
823 if (x &lt; 3) then
824 1
825 else
826 fib(x-1)+fib(x-2);
827
828fib(10);
829
830*/
831</pre>
832</div>
833</div>
834
835<!-- *********************************************************************** -->
836<hr>
837<address>
838 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
839 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
840 <a href="http://validator.w3.org/check/referer"><img
841 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!" /></a>
842
843 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
844 <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
845 Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $
846</address>
847</body>
848</html>